1.1 Surface reconstruction

Probably the most obvious application of scattered data interpolation and approximation

is the reconstruction of a surface S. Here, it is crucial to distinguish between explicit and

implicit surfaces. Explicit surfaces play an important role in terrain modeling, for example.

They can be represented as the graph of a function f : ’ R de¬ned on some region

⊆ Rd , where d is in general given by d = 2. Staying with the terminology of terrain

modeling, the data sites X ⊆ depict certain points on a map, while a data value f j = f (x j )

describes the height at the point x j . The data sites might form a regular grid, they might

be situated on isolines (as in Figure 1.1), or they might have no structure at all. The region

itself might also carry some additional information; for example, it could represent the

earth. Such additional information should be taken into account during the reconstruction

process.

The reconstruction of an implicit surface, or more precisely of a compact, orientable

manifold, is even more demanding. Such surfaces appear for example as sculptures, machine

parts, and archaeological artifacts. They are often digitized using laser scanners, which easily

produce huge point clouds X = {x1 , . . . , x N } ⊆ S consisting of several million points in

R3 . In this situation, the surface S can no longer be represented as the graph of a single

1

2 Applications and motivations

Fig. 1.1 Reconstruction of a glacier from isolines.

Fig. 1.2 Reconstruction (on the right) of the Stanford dragon (on the left).

function f . There are in the main two different approaches to building accurate models

for implicit surfaces. In the ¬rst approach, one tries to ¬nd local parameterizations of the

object that allow an ef¬cient rendering. However, for complicated models (such as the

dragon shown in Figure 1.2) this approach is limited. In the second approach, one tries

to describe S as the zero-level set of a function F, i.e. S = {x ∈ : F(x) = 0}. Such

an implicit representation easily delivers function-based operations, for example shape

blending or deformation or any other constructive solid geometry (CSG) operation such as

the union, difference, or intersection of two or more objects.

The function F can be evaluated everywhere, which allows stepless zooming and smooth

detail-extraction. Furthermore, it gives, to a certain extent, a measure of how far away a

point x ∈ is from the surface. Moreover, the surface normal is determined by the gradient

of F whenever the representation is smooth enough.

The price we have to pay for such ¬‚exibility is that an implicit surface does not auto-

matically lead to a fast visualization. An additional step is necessary, which is normally

provided by either a ray-tracer or a polygonizer. But, for both, suf¬ciently good and ap-

propriate solutions exist. Since our measured point cloud X is a subset of the surface S we

are looking for an approximate solution s that satis¬es s(x j ) = 0 for all x j ∈ X . Obviously

these interpolation conditions do not suf¬ce to determine an accurate approximation to the

1.1 Surface reconstruction 3

surface, since, for example, the zero function satis¬es them. The remedy for this problem

is to add additional off-surface points. To make this approach work, we assume that our

surface is the boundary of a compact set and that the function F can be chosen such that F is

positive inside and negative outside that set. We also need surface normals to the unknown

surface. If the data comes from a mesh or from a laser scanner that provides also normal

information via its position during the scanning process these normals are immediately

to hand. Otherwise, they have to be estimated from the point cloud itself, which can be

done in two steps. In the ¬rst step, for each point x j ∈ X we search its K N nearest

neighbors in X and try to determine a local tangent plane. This can be done by a principal

component analysis. Let us assume that N (x j ) contains the indices of these neighbors. Then

we compute the center of gravity of {xk : k ∈ N (x j )}, i.e. x j := K ’1 k∈N (x j ) xk , and the

ˆ

associated covariance matrix

(xk ’ x j )(xk ’ x j )T ∈ R3—3 .

ˆ ˆ

Cov (x j ) :=

k∈N (x j )

The eigenvalues of this positive semi-de¬nite matrix can be computed numerically or even

analytically. They indicate how closely the neighborhood {xk : k ∈ N (x j )} of x j determines

a plane. To be more precise, if we have two eigenvalues that are close together and a

third one, which is signi¬cantly smaller than the others, then the eigenvectors for the ¬rst

two eigenvalues determine the plane, while the eigenvector for the smallest eigenvalue

determines the normal to this plane. Hence, we have a tool for not only determining the

normal but also deciding whether a normal can be ¬tted at all.

The second step deals with orienting consistently the normals just created. If two data

points x j and xk are close then their associated normalized normals · j and ·k must point

in nearly the same direction, which means that · T ·k ≈ 1. This relation should hold for all

j

points that are suf¬ciently close. To make this more precise, we use graph theory. First,

we build a Riemann graph. This graph has a vertex for every normal · j and an edge e j,k

between the vertices of · j and ·k if and only if j ∈ N (xk ) or k ∈ N (x j ). The cost or weight

w(e j,k ) of such an edge measures the deviation of the normals · j and ·k ; for example,

we could choose w(e j,k ) = 1 ’ |· T ·k |. Hence, the normals are taken to be consistently

j

oriented if we can ¬nd directions b j ∈ {’1, 1} such that e j,k b j bk w(e j,k ) is minimized.

Unfortunately, it is possible to show that this problem is NP-hard and hence that we can only

¬nd an approximate solution. The idea is simply to start with an arbitrary normal and then

to propagate the orientation to neighboring normals. To this end, we compute the minimal

spanning tree or forest for the Riemann graph. Since the number of edges in this graph

is proportional to N , any reasonable algorithm for this problem, for example Kruskal™s

algorithm, will work ¬ne in an acceptable amount of time. After that, we propagate the

orientations by traversing the minimal spanning tree.

Once we have oriented the normals, this allows us to extend the given data sets by off-

surface points. This can be done by for example adding one point along each normal on

the outside and one on the inside of the surface. Special care is necessary to avoid the

4 Applications and motivations

situation where an outside point belonging to one normal is actually an interior point in

another part of the surface or that a supposedly interior point is so far away from its associated

surface point that it is actually outside the surface at another place. The associated function

values that s should attain are chosen to be proportional to the signed distance of the point

from the surface.

Another possible way of adding off-surface points is based on the following fact. Suppose

that x is a point which should be added. If x j denotes its nearest neighbor in X and if X is

a suf¬ciently dense sample of S, then x j comes close to the projection of x onto S. Hence

if x j is approximately equal to x then the latter is a point of S itself. Otherwise, if the angle

between the line through x j and x on the one hand and the normal · j (pointing outwards)

on the other hand is less than 90 degrees then the point is outside the surface; if the angle

is greater than 90 degrees then it is inside the surface.

After augmenting our initial data set by off-surface points, we are now back to a classical

interpolation or approximation problem.

1.2 Fluid“structure interaction in aeroelasticity

Aereolasticity is the science that studies, among other things, the behavior of an elastic

aircraft during ¬‚ight. This behavior is in¬‚uenced by the interaction between the deforma-

tions of the elastic structure caused by the ¬‚uid ¬‚ow, and the impact that the aerodynamic

forces would have on a rigid structural framework. To model these different aspects in a

physically correct manner, different models have been developed, adapted to the speci¬c

problems.

The related aeroelastic problem can be described in a coupled-¬eld formulation, where the

interaction between the ¬‚uid and structural models is limited to the exchange of boundary

conditions. This loose coupling has the advantage that each component of the coupled

problem can be handled as an isolated entity. However, the challenging task is to reconcile

the bene¬ts of this isolated view with a realistic treatment of the new physical effects arising

from the interaction.

Let us make this more precise. Suppose at ¬rst that we are interested only in computing

the ¬‚ow ¬eld around a given aircraft. This can be modeled mathematically by the Navier“

Stokes or the Euler equations, which can be solved numerically using for example a ¬nite-

volume code. Such a solver requires a detailed model of the aircraft and its surroundings.

In particular, the surface of the aircraft has to be rendered with a very high resolution, as

indicated in the right-hand part of Figure 1.3. Let us suppose that our solver has computed

a solution, which consists of a velocity ¬eld and a pressure distribution. For the time being,

we are not interested in the problem of how such a solution can be computed. For us, it is

crucial that the pressure distribution creates loads on the aircraft, which might and probably

will lead to a deformation. So the next step is to compute the deformation from the loads

or forces acting on the aircraft.

Obviously, though, a model having a ¬ne resolution of the surface of the aircraft is not

necessary for describing its structure; this might even impede the numerical stability. Hence,

1.2 Fluid“structure interaction in aeroelasticity 5