A similar functional that may be applied to linear networks
is based on so-called ‘umbrella vectors’ which are associ-
ated with each vertex P; of the net. If P; has k; neigh-
bours Q:;, j — 1,..., ki, the umbrella vector at P; is defined
as [Kobbelt,1995]:
ki
1
AP, =P, — Qu (4)
dy
The euclidean length of AP; can be seen as a discrete meas-
ure for the mean curvature at P;. This results in the fairness
functional
U= ) lap” (5)
=1
An application is the refinement of a network. New vertices
are inserted such that U is minimized.
2.3 Predicting surface data
‘Prediction is a surface interpolation and approximation
method ([Wild,1983]). It uses radial basis functions which
are well studied in approximation theory, numerical analysis
and CAGD (e.g. [Hoschek,1993]). The surface is considered
to be a bivariate function which shall be approximated by the
prediction function. The prediction function is sufficiently of-
ten differentiable, therefore surface normals and curvature can
be calculated. It is also possible to force the prediction func-
tion to have certain derivatives at given points. Thus tangents
to the surface in a given direction or surface normals can be
prescribed.
3 RELATED WORK
There is a rich literature in CAGD dealing with the construc-
tion of surfaces based on polynomial patches. Most methods
are covered in the monograph [Hoschek,1993]. We therefore
just point to a few more recent developments.
Generalizations of the classical minimum norm networks by
G. Nielson to parametric surface design have been discussed
in [Kolb,1995]. The methods are global and therefore not
applicable for huge data sets.
An elegant approach for dealing with smooth surfaces com-
posed of triangular or rectangular polynomial patches are the
surface splines in [Peters, 1995]. For the present application,
the method would generate too many patches.
Approximately smooth surfaces have been investigated in
[Mann,1992]. The patches require curvature information at
the vertices and yield very pleasing results if enough data are
available for producing good curvature estimates. This does
not really correspond to the present scenario.
A very promising approach to surface modeling are the hier-
archical techniques in [Eck,1995]. They work very well on
TINs and more generally on so-called subdivision surfaces.
Some ingredients of these algorithms, such as parametriza-
tion based on harmonic maps, may also be useful for our
application.
In view of the lack of a single method that would satisfy all our
requirements we decided to implement our own version, which
is an appropriate combination of known techniques taylored
towards the applications we have in mind.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
4 ESTIMATION OF NORMALS
4.1 Estimating the surface normals
The process of estimating the surface normals must be inde-
pendent of the coordinate system and local. For each point
P, its surface normal n, its tangent plane 7 respectively, is
calculated.
To make it a local process, only a neighbourhood of a point
P is used to calculate the surface normal at P. The neig-
bourhood (Qi, Q»,...) of a point can either be defined via
generations of points (topological norm) in the triangulation
around this point or via distances (euclidean norm). The set
of points (Qi, Q»,...] having a distance to the centerpoint
P less than or equal to s can be described as a subset of the
neighbourhood of P with n generations, where the points in
the n-th generation have a distance to P larger than or equal
to s. This definition prevents including points which are close
to P in the sense of distance but lie completely elsewhere on
the surface. This situation can arise for example when inter-
polating the surface data of a cave. Still there may exist one
or more points Q; in the neighbourhood of P which will have
to be excluded from the estimation process. This results from
an estimation technique, where we need surface regions that
are definable as graphs of bivariate functions over an appropri-
ate parameter plane (using the approach in [Opitz, 1994], this
restriction could be avoided however). To find these points,
the direct way from P to Qj; via the edges of the triangulation
has to be examined. If one of the slopes of the planes against
an approximate tangent plane at P exceeds a threshold value
(e.g. 80°), then Q; has to be excluded (see Figure 3).
[ree points Sit
Figure 3: Interpolation in a cave
To guarantee that the estimation of n is independent of the
coordinate system, the interpolation is done in a local coor-
dinate system whose (z,y)-plane is the actual approximate
tangent plane 7 of the point P. The plane 7 is updated in
an iterative process. The starting value ro for the iteration
can either be a result of the triangulation process, or can be
computed by averaging the normal vectors of the triangles
meeting at P. The iteration runs as follows:
1. The points Q; and P are transformed into a coordinate
system based on an approximation for the tangent plane
(ny
2. Prediction yields a surface, whose tangent plane at P
delivers the next approximation (7;41). If desired, fil-
tering can be performed in this step as well.
3. If the angle between 7; and 7;41 is smaller than a cer-
tain threshold value, the process is stopped. Otherwise
Ti+1 Serves as a new entry for step 1.
The curvature can also be computed from the prediction func-
tion. This could be used for constructing the curves between
two \
vertic
4.2
Bour
of th
vertic
must
plane
norm.
Thet
comp
exam
comp
where
these
deteri
point:
of th
The c
€(ta)
three,
The :
presci
ectior
left a
the c
in the
dering
c(t.)
pletel
derive
of the
(inter
anoth
Norm
a sur
surfac
vectoi
param
this c
as ex
and I
To
DP
into a
point:
triang
of al
points
are:
point:
norm:
functi
Thep
mals,
bounc
struct
data.
