of 
he 
of 
se 
g 
  
3D-Surface Modelling with Basic Topologic Elements 
A. Halmer, D. Heitzinger, H. Kager, Inst. f. Photogrammetrie und Fernerkundung, TU Wien 
commission IV, working-group 4 
KEY WORDS: DEM/DTM, Surface, GIS, Triangulation Algorithms, Three-dimensional Surface Modeling 
ABSTRACT 
Systems for modelling of surfaces are an indispensible tool in geodesy, photogrammetry, geo-informatics and many other 
disciplines. Common systems are designed for applications dealing with the surface of the earth. In general, these systems fail in 
modelling more complex structures, such as parts of the human body or artificial buildings. In this paper an alternate system to 
model arbitrary surfaces is presented. 
The surface is decomposed into basic topological elements: nodes, edges, triangles - and tetrahedrons for bodies. The structure of 
the surface is determined by the topological relations between these basic elements. These topologic relations have to be deduced 
from the scattered data-points, what is done by a triangulation of the measured surface-points. The triangulation uses a local order- 
criterion which utilizes the surface-normals in the data-points. A major element in modelling of surfaces are lines, such as break- 
lines, contour-lines or boundary-lines. These lines are topological constraints and are incorporated within the triangulation. To gain 
a better representation and to filter errors of measurement, these lines are approximated by piecewise cubic polynomials in space. 
The adjustment is done locally by a fully three-dimensional algorithm working on a sub-network. 
KURZFASSUNG 
Systeme zur Modellierung von Oberflüchen sind ein wichtiges Hilfsmittel in Geodäsie, Photogrammetrie, im Geo-Informations- 
wesen und vielen anderen Bereichen. Die dabei gebräuchlichen Systeme sind auf die Modellierung der Erdoberfläche zugeschnit- 
ten. Komplexere Flächenstrukturen (Kunstbauten, menschliche Körperteile, etc.) können damit i.a. nicht modelliert werden. In 
dieser Arbeit wird ein alternatives Konzept zur Modellierung beliebiger Oberflächen vorgestellt. 
Die Fläche wird in topologische Grundelemente zerlegt: Knoten, Kanten, Dreiecke - und Tetraeder für Körper. Die Gesamtstruktur 
der Fläche wird durch die Nachbarschaftsbeziehungen zwischen diesen Grundelementen beschrieben. Die gemessenen 
Oberflächenpunkte liegen meist als unstrukturierte Punktwolke vor. Daraus sind die topologischen Beziehungen abzuleiten. Dies 
erfolgt durch eine Triangulation (=Dreiecksvermaschung) der Datenpunkte. Die Triangulierung verwendet ein lokales Ordnungs- 
kriterium, welches die Flächennormalen in den Punkten ausnutzt. Bei der Modellierung von Oberflächen stellen Linien, wie 
Bruchlinien, Formlinien oder Randlinien, ein zentrales Element dar. Diese Linien werden als topologische Zwangsbedingungen in 
die Triangulation aufgenommen. Um eine gute Oberflächenmodellierung zu erreichen, und um zufällige Meßfehler zu filtern, 
werden die Linien durch kubische Splinekurven approximiert. Die Ausgleichung erfolgt lokal in Subnetzen und arbeitet völlig 
dreidimensional. 
1. INTRODUCTION tiality to model arbitrary surfaces. Resulting from problems 
with common systems for terrain-modelling, there arises a set 
In many parts of science the necessity of a mathematical re- of requirements: 
presentation of surfaces occurs. In the field of geo-science this ' Usage of the original data as a main element in model- 
surface often is the surface of the earth. To perform the various ling. 
operations with the surface, a model of the surface is to be * Possibility of dynamical editing of the data - the aim is 
created first. In geo-sciences the so called Digital Terrain progressive sampling'. 
Models', in short DTM are commonly used: The surface is * Local algorithms instead of global ones. 
represented by a regular grid. The heights in this grid, together * Smooth surface representation with filtering of random 
with algorithms for interpolation, form the model of the surface errors. 
(Kraus, 1987). Such kind of surface-models is very efficient for * Separate smoothing of lines. 
many applications. But sometimes problems occur: e.g. the * Modelling of thematic attributes. 
modelling of vertical walls or overhangs is not possible. These * Automatic detection of gross errors. 
problems can only be solved with a new and different way of * Automatic reduction of redundant data. 
modelling. In this paper a different approach to avoid these 
problems is presented. 2.2 Theoretical model 
Common digital terrain models, as well as Geo-Information- 
2. BASIC CONCEPT Systems, are based on two-dimensional data-models, i.e. the 
general data-structure and the used algorithms are essentially 
2.1 Requirements 2D. The modelling of the surface happens in the ground plane 
and the object-height is reduced to an attribute of the twodi- 
The main requirements for a new concept of surface-modelling mensional points. Hence the surface is represented in the form 
are independence of the coordinate-system, as well as indepen- 
dence of the orientation of the surface in space, and the poten- z=fxy), with f generally the object-height. 
407 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996