Norbert Pfeifer
Institute for Photogrammetry and Remote Sensing
Technical University of Vienna, Austria
Surface Models on the Basis of a Triangular Mesh — Surface Reconstruction
Helmut Pottmann
Institute of Geometry
Technical University of Vienna, Austria
IWG III/IV - Conceptual Aspects of GIS
April 1996
KEY WORDS: Digital terrain models, CAGD, surface reconstruction, approximate geometric continuity, Bézier triangle
ABSTRACT
Given is a triangulation of points on a surface which may be of abitrary topology. The aim is to reconstruct the surface using
triangular patches. We present a solution that combines approaches from photogrammetry and from computer aided geometric
design. The surface model built is capable of handling all kinds of surface data like normal vectors and break lines. The faces
of the triangulation are replaced by triangular Bézier patches that meet smoothly along their boundary curves. The smoothness
condition is weakened a bit to the concept of eG1-continuity, which allows us to use polynomial patches of low degree, in most
cases without splitting.
1 INTRODUCTION
The problem of fitting a surface to a set of data points has
been investigated in several scientific disciplines. On one hand
there are the photogrammetetrists who are interested in build-
ing a Digital Terrain Model (DTM) from measured points on
the earth's surface. In recent years the field of interest spread
into medicine, modelling of buildings and many areas more.
On the other hand there is the Computer Aided Geometric
Design (CAGD) community, which has been investigating the
same task from a different point of view and being motiv-
ated mainly by applications in Computer Aided Design. This
paper aims at presenting a surface model, founded on the
knowledge of both sides. It has the following characteristics:
e [he model has no shape restrictions and it is independ-
ent of the coordinate system.
e [hesurface model is built on a triangulation of the data
points, so the original measurements may be preserved.
Filtering of measurement errors may be incorporated.
e The surface is smooth, except for so-called break lines
where a difference in the first derivatives is desired. In
this context 'smooth' means tangent plane continuous.
e |t is possible to master the set of data for a whole
country.
e [he used methods are local. This means that the in-
sertion of a new face in the triangulation influences the
shape of the surface only in a restricted neighbourhood
of this face.
Current digital terrain models do not satisfy all the character-
istics described above. Many surface models are only 2.5 di-
mensional, which means that they can be described as graphs
of bivariate functions. This approach does not allow one to
represent bridges, overhangs, caves or similar effects. Surface
models built of flat triangles (triangular irregular networks —
TINs) either lack smoothness or require a large number of
points to establish the desired smoothness. It stands to reason
to utilize a spatial triangular mesh (a TIN) as a basis for tri-
angular patches which establish the smoothness. Therefore
the following steps are to be taken:
1. Estimation of surface normals at the vertices of the
triangulation and filtering of measurement errors.
638
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
2. Constructing a curve mesh that interpolates the vertices
of the triangulation as well as the surface normals at
these vertices. The curves of the mesh are the boundary
curves of the triangular patches.
3. Constructing triangular surface patches that interpolate
these vertex data and these boundary curves of the
network. Furthermore two adjacent patches must have
the same tangent planes (with small deviations allowed)
along their common boundary curve.
This is a common approach to the stated problem. Our con-
tributions are as follows. In step 2, we also determine the field
of surface normals along the boundary curves. This field is
discretized by computing some of its representatives at vari-
ous positions along the edge. The three fields of surface
normals along boundary curves, which are the delimiters of
one triangular face, are then approximated or interpolated
in step 3. Hereby the interpolation conditions regarding the
boundary curves are still fulfilled. Because discretized fields
are used instead of interpolating the continous fields, two ad-
jacent patches do not exactly join smoothly, but possess some
deviation angle e. We take care that ¢ is sufficiently small and
thus it will have no disturbing effects when shading the sur-
face, computing contour lines, calculating volumes, etc. To
regularize the solution, the eG! algorithm is combined with
the minimization of an appropriate fairness measure.
Let us briefly outline our presentation. In section 2, some pre-
liminaries are described: the theory of Bézier triangles, which
are a geometric representation of polynomial surfaces, some
aspects of variational surface design and prediction. In sec-
tion 3, related work from CAGD as well as photogrammetry
Is presented. Section 4 deals with the estimation of surface
normals and the computation of boundary curves along with
their normal vector fields. Section 5 shows how to insert the
patches into the mesh of curves. In the concluding remarks
we list the possibilities obtained with our approach.
2 PRELIMINARIES
2.1 Bézier triangles
Since Bézier triangles are rarely used in photogram-
metry, we give a short introduction (for more details, see
[Hoschek,1993]). A Bézier triangle (triangular Bézier patch)
repre:
of a c
Figur
shape
paran
triang
triple
n =<
P 300
The |
paran
de C:
Bézie
m= 2
