Zustand in einen inaktiven (und umgekehrt) überführt wird. An dieser Stelle müssen die Dreiecke
vereinigt oder geteilt (merge oder split) werden. Cracks zwischen aneinanderliegenden Knoten
(siehe auch Kapitel 4.2.4) werden über einen Binärbaum entfernt, der die Abhängigkeiten zwischen
den Vertices erhält. Um auch Cracks zwischen den einzelnen Blöcken zu vermeiden, teilen sich alle
benachbarten Blöcke in ihren Grenzregionen die gleichen Vertices. [LOD_3D]
Das Vereinfachungsschema von Lindstrom et al. schlägt eine Vertex-Entfernung vor, bei der jeweils
ein Paar von Dreiecken zu einem einzelnen reduziert wird. Dies beinhaltet, dass das gemeinsame
Vertex zwischen den Dreiecken identifiziert und entfernt werden muss. Die Entscheidung, wann
diese merge-Operation durchgeführt werden muss, wird über die Größe des Screen-Space Fehlers
zwischen den beiden Oberflächen getroffen. In diesem Fall ist das die vertikale Distanz zwischen
dem zu entfernenden Vertex und dem Mittelpunkt der neu zu entstehenden Kante. Anschließend
wird dieses Segment in den Screen-Space projiziert, um den maximal erreichbaren Fehler
berechnen zu können. Wenn dieser Fehler kleiner als ein vorgegebener Pixel-Schwellwert liegt,
wird die Dreiecks-Vereinfachung weiter durchgeführt. [LOD_3D]
Mittlerweile wurde dieser Algorithmus modifiziert und es entstand daraus die SOAR-Terrain-
Engine (siehe [SOAR]).
3.4 Der ROAM Algorithmus
Ein Jahr nach Lindstrom et al.s Algorithmus publiziert wurde, wurde von Duchaineu et al. aus den
Los Alamos und Lawrence Livermore National Laboratories der ROAM-Algorithmus veröffentlicht
[ROAM]. Dieser Algorithmus ist vor allem unter Spieleentwicklern sehr populär geworden. ROAM
(real-time optimally adapting meshes) benutzt einen inkrementellen prioritätsbasierten Ansatz, mit
einer zugrunde liegenden Binärbaumstruktur. Über diese Struktur wird ein kontinuierliches Mesh
erstellt, indem eine Reihe von split- und merge-Operationen auf Dreieckspaare angewandt wird, die
sich ihre Hypotenusen teilen, sogenannte ,,Diamanten".
Der ROAM-Algorithmus benutzt zwei Prioritäts-Warteschlangen, um über die merge- und split-
Operationen zu entscheiden. Die erste Warteschlange enthält eine nach Priorität geordnete Liste von
split-Operationen zwischen den Dreiecken, so dass eine Verfeinerung des Terrains erzielt wird,
wenn man in jedem Schritt das Dreieck mit der höchsten Priorität unterteilt. Die zweite
Warteschlange enthält eine nach Priorität geordnete Liste von merge-Operationen der Dreiecke, um
das Mesh zu vereinfachen. Dies ermöglicht ROAM den Vorteil von Frame-Kohärenz zu nutzen,
d.h. dass er auf vorherige Frames der Triangulierung zurückgreifen kann und dort inkrementell
Dreiecke hinzufügen oder entfernen kann. Die Priorität der split- und merge-Operationen beider
Warte-schlangen wird durch verschiedene Fehler-Metriken bestimmt und kann bei Interesse in dem
zugehörigen Paper [ROAM] nachgelesen werden.
13