[Back]


Books and Book Editorships:

N. Pfeifer:
"3D Terrain Models on the Basis of a Triangulation";
Geowissenschaftliche Mitteilungen, Heft 65, 2002, ISBN: 3-9500791-7-3; 127 pages.



English abstract:
This work provides an overview on terrain modelling techniques. Terrain models, or in order to be more general, topographic surface models, play an important role in many fields of science and practice where a relation to a location, i.e. a ?geo-relation? is given. These models describe the height as a function of the location. In this definition lies a restriction, because only one height is allowed at one ground-plane position. Therefore, the currently used models are often termed 2.5D terrain models. The modelling of overhangs is not possible within such an approach. The aim of this work is to put aside this limitation and provide methods for 3D terrain modelling where not only the above restrictions do not apply anymore, but also more general surfaces with tunnels and cave systems can be reconstructed. Another terrain property which plays an important role in this work is its smoothness: a model shall be smooth. An exception is introduced at so-called breaklines where the terrain shape has a sharp edge.

There are several ways in order to build terrain models with the above characteristics (fully 3D and smooth). In this work, emphasis is put on those approaches which reconstruct the surface on the basis of a triangulation. Two different techniques are treated with great detail: the patch work and the subdivision approach. For each of those two, one method was developed which considers the special requirements in terrain modelling. The main contribution of this work to terrain modelling are those new methods. The generation, improvement, and thinning of triangulations is not treated within this work, but references to the relevant literature are given.

Generally, the reconstruction of a patch work proceeds as follows. Given is a triangulation, which has ? as expected ? planar faces. For each edge a curve is determined which interpolates the end points. In the next step, triangular patches are inserted into a triple of boundary curves spanned over the edges of each triangle. As the patches interpolate the boundary curve a G0 surface (a geometrically continuous surface) is obtained. However, this is not enough, because a smooth surface (G1, geometric continuity of order one, i.e. tangent plane continuity) is desired. Adjacent patches must therefore interpolate not only the boundary curves, but also share a common field of cross boundary derivatives. This is the general approach for patch work surfaces.

The patch work method which is proposed in this work starts with an enhancement of the triangulation. (It has to be mentioned that this method was partly developed in my Diploma Thesis ? written in German ?, though it is not embedded in the context of terrain modelling there.) As the measurement of terrain points and lines is always burdened with random errors (depending on the measurement device characteristics) these errors should be removed first. This can be achieved by kriging, whereby for each point of the triangulation (i.e. each vertex) a filter value is determined from its neighboring points. In this step also the surface normal vectors in the points can be estimated, but alternative methods for the estimation of the normal vector, e.g. by averaging those of the triangles which are incident to that vertex, are possible, too. Now, not only the position, but also the surface normal vector is prescribed for each vertex. The patches which are to be reconstructed over each face of the triangulation are polynomials of degree four and they are described with Beziér triangles which allow a geometric interpretation of the coefficients of the (bivariate) polynomial. In the next step, boundary curves of polynomial degree three are computed which ?replace? the edges of the triangulation. These curves interpolate the end points of the edge and the curve tangents in those points are perpendicular to the normal vectors. This determines the boundaries of each patch. The missing parameters (i.e. coefficients of the polynomial) influence the shape in the interior of the patch and also the tangent planes of the patch along the boundaries. A field of normal vectors is estimated for each boundary curve by blending the normal vectors from the end points into each other. The ?inner? parameters of a patch are now determined in a way that the normal vector fields are approximately perpendicular to the tangent planes of the patch along the boundaries in a least squares sense. As this field is ?only? approximated and not interpolated this scheme is called epsilon-G1 (i.e. approximately tangent plane continuous).

The second technique for surface reconstruction over a triangulation is the so-called subdivision. In this approach the given triangulation is refined in steps, and in each step new vertices and edges are inserted into the triangulation. This is performed in a way that the smoothness of the triangulation is increased in each level, the angles between adjacent triangles converge towards 180. The limit surface, reached after an infinite number of subdivision steps, is smooth. An advantage of this approach is that the surface description is always composed of small triangles which allows to apply simple algorithms for intersections and similar tasks. The size of the triangles depends on the number of subdivision steps (i.e. the refinement level). This is the general approach for subdivision surfaces.

Also in the reconstruction technique (developed in this work) for topographic surfaces which is based on subdivision a removal of random measurement errors has to be performed first. The refinement rule applied here is the so-called edge midpoint subdivision where in one step one vertex is inserted into each edge and the triangulation is updated. The subdivision is based on the estimation of local surfaces in each vertex. A local surface is estimated which approximates the vertex of interest and its neighbors. The co-ordinates of the new points are obtained by averaging the two local surfaces in either edge end point. To achieve this, a point, representative for the edge midpoint, is computed on both local surfaces and the mean of these two is the new point. Also the ?old? points obtain new co-ordinates, namely their position on the local approximating surfaces. Special modifications are introduced in order to interpolate the originally given points.

The approaches are compared to each other with examples based on real photogrammetric and geodetic observations as well as on synthetic terrain data. It turns out that the surfaces obtained by the developed subdivision approach meet the requirements in topographic terrain modelling better.

German abstract:
Der Titel der vorliegenden Arbeit ist ?3D-Geländemodelle auf Basis einer Triangulierung?. Digitale Geländemodelle (abgekürzt DGM), also Beschreibungen der Höhe und Lage der Erdoberfläche in einer Form, die für die Bearbeitung auf Computern geeignet ist, werden in vielen Gebieten der Wissenschaft und Praxis erfolgreich eingesetzt. Die Anwendungen reichen von der Ableitung von Höhenschichtlinien für topographische Karten bis zur Modellierung des Wasserabflusses nach einem Unwetterereignis, um nur zwei zu nennen. In vielen geographischen Informationssystemen sind Geländemodelle ein unverzichtbarer Bestandteil. Die dort verwendeten Modelle unterliegen aber einer Einschränkung. Mathematisch formuliert sind sie Graphen bivariater Funktionen. Mehr von einer praktischen Seite beleuchtet heißt das, dass die Modellierung von Überhängen unmöglich ist, von steilen Wänden und Klippen nur sehr unzureichend möglich ist, und Höhlensysteme, aber auch Brücken ebenso nicht modelliert werden können. Um dieses Charakteristikum zum Ausdruck zu bringen werden solche Modelle oft als ?2.5D? bezeichnet. In dieser Arbeit werden Methoden zur Ableitung von Geländemodellen vorgestellt, die diesen Beschränkungen nicht unterliegen. Ein weiterer wichtiger Aspekt ist die Glattheit des Modells. Das uns umgebende Gelände ist im Allgemeinen glatt, mit Ausnahme der sogenannten Geländekanten, und daher soll auch ein DGM davon glatt sein. Es gibt verschiedene Möglichkeiten glatte 3D-Geländemodelle zu erzeugen, aber diese Arbeit ist auf jene Methoden beschränkt, die mittels einer Triangulierung erstellt werden. Die Erzeugung, Verbesserung und Ausdünnung von Triangulierungen ist nicht behandelt, aber Verweise auf die Literatur sind angegeben.

Zwei verschiedene Ansätze um aus einer Triangulierung eine glatte Oberfläche zu erzeugen werden vorgestellt: Flächenverbände mit parametrischen Patches und Subdivision (Unterteilungsflächen). Im Rahmen der beiden Zugänge ist jeweils eine Methode entwickelt worden, die den Anforderungen in der topographischen Geländemodellierung genügt.

Beiden entwickelten Verfahren ist gemein, dass zuerst eine Filterung der Triangulierung durchgeführt werden muss. Die Messung von Punkten und Linien am Gelände erfolgt immer mit zufälligen Fehlern, die von dem jeweils verwendeten Verfahren abhängen. Zur Filterung wird die sogenannte Einzelpunktprädiktion angewandt, die eine qualifizierte Eliminierung der zufälligen Messfehler erlaubt. Für jeden Punkt, also jeden Knoten der Triangulierung, wird eine verbesserte Position aufgrund der Lage seiner benachbarten Punkte geschätzt. Die Differenz von der beobachteten zur ?fehlerfreien? Position ist der Verbesserungsvektor.

Glatte Flächenverbände über einer Triangulierung werden im Allgemeinen schrittweise erstellt. Zuerst wird für jede Kante der Triangulierung eine Kurve auf der Fläche bestimmt, die die beiden Kantenendpunkte verbindet. Die in einem Knoten der Triangulierung, also in einem der gegebenen Punkte, zusammentreffenden Kurven müssen zu einer gemeinsamen Tangentialebene an die Fläche passen. Die Tangenten in den Kurvenendpunkten müssen also in einer Ebene liegen. Jedes Dreieck der Triangulierung wird nun durch ein gekrümmtes dreieckiges Flächenstück (einen Patch) ersetzt, das die Randkurven zu den Dreieckskanten interpoliert. Damit erhält man eine stetige Fläche, was aber noch nicht ausreicht, da eine glatte Fläche rekonstruiert werden soll. Bei der Bestimmung der Patches muss daher eine Konstruktion angewandt werden, die sicherstellt, dass benachbarte Patches nicht nur die Randkurve teilen, sondern auch dasselbe Feld von Tangentialebenen entlang dieser Kurve haben. Eine solche Fläche wird als geometrisch stetig erster Ordnung bezeichnet (G1).

Die entwickelte Methode basiert auf (bivariaten) polynomialen Patches vierten Grades, die als Beziér-Dreiecke beschrieben werden. Der Vorteil der Beschreibung auf Basis der Beziér- Bernstein-Polynome liegt darin, dass die Koeffizienten des Polynoms in dieser Form eine geometrische Bedeutung haben. Wie oben erwähnt, werden zuerst die zufälligen Messfehler eliminiert. In diesem Schritt kann auch die Tangentialebene an die Fläche im jeweiligen Punkt abgeschätzt werden. Alternativ dazu kann der Normalvektor beispielsweise auch durch Mittelung der Normalvektoren aller Dreiecke, die in einem Punkt zusammentreffen, festgelegt werden. Im nächsten Schritt werden die Randkurven der Patches bestimmt, die in diesem Fall (univariate) Polynome vom Grad drei sind. Die Tangenten in den Endpunkten müssen normal zu den vorher bestimmten Normalvektoren sein. Damit sind die Randkurven der Patches bestimmt, es müssen noch die ?inneren Parameter? (also Koeffizienten des Polynoms) bestimmt werden, die sowohl die Form des Patches im Inneren, also auch die Tangentialebenen entlang der drei Randkurven beeinflussen. Im folgenden Schritt wird entlang dieser Randkurven ein Feld von Normalvektoren bestimmt, indem die beiden Endpunkt-Normalen ineinander überblendet werden. Zu jedem Randkurvenpunkt gibt es somit einen Normalvektor zur Fläche. Die inneren Parameter der Patches werden nun so bestimmt, dass die Tangentialebenen der Patches möglichst normal auf die abgeschätzten Normalvektoren sind, die Minimierung erfolgt im Kleinste-Quadrate-Sinn. Da im Allgemeinen keine exakte Interpolation dieser Normalvektorenfelder, sondern nur eine Approximation möglich ist, entsteht keine vollständig glatte, sondern nur eine approximativ glatte Fläche, man spricht auch von ?Epsilon-Stetigkeit? (epsilon-G1). Wenn zwischen zwei benachbarten Patches die Winkel zwischen den aufeinander treffenden Tangentialebenen zu groß sind, müssen die Patches unterteilt werden um mehr Freiheitsgrade und somit einen besseren Übergang zu gewährleisten. (Es soll erwähnt werden, dass diese Methode teilweise in meiner Diplomarbeit entwickelt wurde, obschon sie dort nicht so sehr im Kontext der Geländemodellierung steht.)


Die zweite Methode, die zum Erstellen von glatten 3D-Geländemodellen untersucht worden ist, arbeitet nach dem Subdivision-Prinzip. Die Triangulierung wird dabei schrittweise unterteilt, wobei mehr und mehr Punkte und Kanten eingefügt werden. Die Winkel zwischen benachbarten Dreiecken nähern sich dabei 180, wodurch die Grenzfläche, die man theoretisch nach unendlich vielen Unterteilungsschritten erhält, glatt ist. Ein großer Vorteil dieses Verfahrens ist, dass unabhängig vom Unterteilungsniveau immer eine Triangulierung vorliegt. Für diese Datenstruktur sind viele Algorithmen, also z.B. Darstellung, Verschneidung u.s.w., sehr einfach. Je nach gestellter Aufgabe kann das den Genauigkeitsanforderungen entsprechende Niveau herangezogen werden.


Auch bei der entwickelten Subdivision-Methode zur Rekonstuktion der Geländefläche müssen, wie oben erwähnt, die zufälligen Messfehler zuerst eliminiert werden. Im angewandten Unterteilungsschema wird in jeder Kante ein zusätzlicher Punkt eingefügt, der aber nicht der geometrische Kantenmittelpunkt sein muss. Ein Verfeinerungsschritt besteht im Einfügen von einem Punkt in jede Kante und der entsprechenden zusätzlichen Vermaschung der Triangulierung. Die Koordinaten der neu einzufügenden Punkte werden wie folgt bestimmt: in beiden Kantenendpunkten wird eine lokale Fläche abgeschätzt. Diese approximiert den Kantenendpunkt und seine Nachbarpunkte. Für die beiden Flächen wird dann jeweils ein für den Kantenmittelpunkt repräsentativer Punkt auf den lokalen Flächen bestimmt. Das Mittel der beiden so erhaltenen Punkte ist die Position des neu einzufügenden Punktes. Auch die Kantenendpunkte erhalten neue Positionen, nämlich jene, die den jeweiligen Punkten auf der lokalen Fläche entsprechen. In den ursprünglich gegebenen Punkten werden keine rein approximierenden Flächen verwendet, sondern die dort verwendeten lokalen Flächen interpolieren den ursprünglich gegebenen Punkt und approximieren seine Nachbarn. Dadurch interpoliert die Grenzfläche die Punkte der gegebenen Triangulierung.

Anhand von Vergleichen zwischen der Subdivision- und der Flächenverband-Methode wird untersucht, welches Verfahren den Anforderungen in der topographischen Geländemodellierung besser entspricht. Dazu werden sowohl tatsächliche Messungen am Gelände als auch synthetische Beispiele herangezogen. In den untersuchten Fällen sind mit den Unterteilungs- Flächen, also mit Subdivision, bessere Ergebnisse erzielt worden.

Ein kurzer Ausblick auf die Anwendungen von Geländemodellen, die Überhänge, Höhlen, etc. enthalten, wird im letzten Kapitel gegeben.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_119332.pdf


Created from the Publication Database of the Vienna University of Technology.