David Heitzinger
which deals with the triangulation of multiple slices. Developments in Photogrammetry concentrated mainly on 2.5D-
surfaces, which covered most of the possible applications. Only in recent years the reconstruction of man-made objects
has become very important and several methods have been presented: Lang and Förstner (1996), Rottensteiner (1998)
and Englert (1998). These methods are fully three-dimensional, but can not be used for arbitrary surfaces.
For the triangulation of points, sampled on an arbitrary surface in 9U, various algorithms are existing. An excellent
overview of the most important methods is given by Mencl and Müller (1997b). Other methods are presented e.g. by
Edelsbrunner and Mücke (1994), Choi et al. ( 1988) and Uray and Pinz (1995).
Some of these algorithms are designed for specific needs or certain data sources, others are of a more general purpose.
But none of them is designed to fulfil especially the requirements of applications in the field of photogrammetry.
1.2 Problem Definition
For modelling arbitrary surfaces in 9? a flexible approach is necessary. One of the best approaches is a triangulation of
the data points. A triangulation is an irregular topologic structuring of the data, but it can immediately be used for sur-
face representation: the triangles can be used as planar facets or they can be replaced by curved triangular surface-
patches (s. Pfeifer and Pottmann 1996). Hence the aim of this work is, to find a 3D-triangulation of a given point set.
The algorithm has to fulfil some additional requirements:
* Inclusion of lines: the measurement of topographic lines is one of the most important advantages of photogrammet-
ric measurement. These lines have to be included in the triangulation as constraints.
* Use of additional information: e.g. from different sources of measurement, different hints can be deduced how the
triangulation has to look like.
e Surface representation: the triangulation is the base of the actual surface representation, hence it has to be con-
structed considering the geometry of the surface.
2 KNOWLEDGE ABOUT THE DATA
Different kinds of measurement have different characteristics. These characteristics should be exploited as far as possi-
ble when generating the triangulation. If the algorithm is capable to include this information, this capability will be
called knowledge: the program will know how to generate a triangulation, if a certain precondition is satisfied.
Every reconstruction algorithm uses some knowledge about the expected input. This knowledge is incorporated in the
algorithm how to compute the triangulation. Seldomly, this knowledge is formulated explicitly. An example for the
explicit formulation of rules is given by Mencl and Miiller (1997a).
In this work it has been tried to formulate all possible knowledge. Seven categories have been introduced, from which
the most interesting aspects will be discussed shortly:
* Knowledge about the properties of the original surface: assumptions about the shape and properties of the sur-
face: CO, C1- continuity, open or closed surfaces, no self-intersections.
* Knowledge about the measurement of the surface: important are three aspects: discretization, point distribution
and data source. Discretization has to meet the requirements of some Sampling Theorem (s. Tempfli, 1982, or
Boissonnat, 1984). Data source, i.e. the type of measurement, gives the most important conditions for the surface
reconstruction. For photogrammetric needs the following types have been identified as necessary: contourlines by
digitisation or direct measurement, topographic measurement, automated measurement and profiles (s. Figure 2).
a b c d
Figure 2, examples for (a) automatic data sampling, (b) profile measurement, (c) contourlines and (d) photogram-
metric measurement.
These different categories have been considered in this work. The main characteristics are:
Contourlines: the complete surface is sampled by intersection with multiple horizontal planes.
382 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
