3 Level-of-Detail Algorithmen
Mit dem Problem einer intelligenten Vermaschung und Detailreduzierung haben sich schon sehr
viele Forschungs- und Arbeitsgruppen auseinandergesetzt und sehr leistungsfähige Verfahren
entwickelt.
Da eine Punktwolke aus einem 3D-Laserscan nur eine Oberfläche beschreibt, kann man diese als
eine Art Landschaft interpretieren, auf die sich ,,Terrain"-LOD-Algorithmen anwenden lassen,
weshalb wir uns in dieser Arbeit nur auf solche Verfahren beschränken. Im Folgenden sollen einige
populäre Verfahren und deren Unterschiede betrachtet werden.
3.1 Top-Down und Bottom-Up
Im Vergleich zu generellen LOD-Techniken lassen sich Terrain-LOD-Algorithmen nach ihrem
Ansatz zur Vereinfachung in zwei Typen gliedern: top-down und bottom-up. Bei einem top-down
Algorithmus beginnt man für gewöhnlich mit zwei oder vier Dreiecken für die gesamte Region und
fügt anschließend progressiv neue Dreiecke hinzu, bis die gewünschte Auflösung erreicht ist. Diese
Techniken werden auch Subdivisions- oder Verfeinerungsmethoden genannt. Im Gegensatz dazu,
startet ein bottom-up-Algorithmus mit dem höchstaufgelösten Mesh und entfernt iterativ Vertices
aus der Triangulierung, bis der gewünschte Grad an Detailreduzierung erreicht ist. Diese Techniken
nennt man auch Dezimierungs- oder Vereinfachungsmethoden. Bottom-up-Ansätze finden meist die
minimale Anzahl an nötigen Dreiecken für eine vorgegebene Genauigkeit, stellen jedoch als
Voraussetzung, dass das komplette Modell gleich zu Beginn schon verfügbar ist und benötigen
deshalb mehr Speicher und Rechenleistung.
3.2 Reguläre Gitter und TINs
Ein weiteres wichtiges Unterscheidungsmerkmal zwischen Terrain-LOD-Algorithmen, ist die Art
der verwendeten Struktur, die das Terrain repräsentiert. Die zwei häufigsten benutzen Ansätze sind
regulär vermaschte Höhenfelder (reguläre Gitter) und triangulierte irreguläre Gitter (triangulated
irregular networks = TIN). Reguläre Gitter benutzen ein Array von Höhenwerten für x- und y-
Werte, die alle einen gleichförmigen Abstand besitzen.
Generell können TINs eine Oberfläche genauer approximieren, benötigen also weniger Dreiecke als
andere Verfahren. Zum Beispiel können hiermit großflächige ebene Regionen mit einem groben
Gitter erfasst werden, während die unebenen Regionen durch ein hochaufgelöstes Gitter dargestellt
werden. Im Vergleich dazu sind reguläre Gitter sehr viel ungenauer als TINs, da sie die gleiche
Auflösung für die gesamte Region besitzen, ganz gleich, ob die Gebiete eben oder uneben sind.
Jedoch bieten reguläre Gitter den Vorteil, dass sie leichter zu speichern und zu manipulieren sind
und man dadurch einen schnellen Zugriff auf beliebige Höhenwerte hat, weshalb wir uns in dieser
Arbeit auf reguläre Gitter beschränken.
3.3 Der SOAR-Algorithmus von Lindstrom et al.
Einer der ersten Echtzeit LOD-Algorithmen für Höhenfelder war die frühe Arbeit von Lindstrom et
al. Dieser Algorithmus benutzt ein reguläres Gitter und eine vom Benutzer definierte Screen-Space
Fehlertoleranz, um den Grad der Vereinfachung zu steuern [SOAR]. Der Algorithmus ist
konzeptionell vom Typ bottom-up, beginnt also mit dem kompletten Modell bei seiner höchsten
Auflösung und vereinfacht die Dreiecke progressiv, bis die gewünschte Genauigkeit erreicht ist.
Jedoch wird in der Praxis das Mesh in rechteckige Blöcke unterteilt und zunächst eine top-down
Vereinfachung auf diese Blocks angewandt, gefolgt von einer Vertex-Reduzierung innerhalb dieser
Blocks. Die bottom-up Rekursion entsteht, wenn ein Vertex (Knotenpunkt) von einem aktiven
12