schließlich liefert diese Methode die besten Resultate. An den Stellen eines Cracks können
die zwei kleineren Dreiecke (von höherer Stufe) entweder zu einem großen Dreieck einer
Stufe niedriger zusammengefügt werden (merge-Operation) oder das große Dreieck in zwei
kleinere unterteilt werden (split-Operation) und falls nötig auch die daran angrenzenden
Dreiecke. [LOD_3D] Im Folgenden wird eine Kombination dieser beiden Lösungen
vorgestellt.
Die Funktion
void mesh_optimization::update_neighbors( unsigned int level )
löst dieses Problem folgendermaßen:
In jeder ungeraden Rekursionsstufe:
1. Bestimmte und speichere für jedes Dreieck das Nachbardreieck mit gemeinsamer
Hypotenuse. Dann gilt, dass dieses Dreieck jeweils Punkt 2 mit Punkt 3 des
Nachbardreiecks und Punkt 3 mit Punkt 2 teilt. Die Dreiecke am Rand des Höhenfelds
werden von dieser Suche ausgeschlossen, da sie grundsätzlich keine Nachbardreiecke mit
gemeinsamer Hypotenuse besitzen.
2. Wenn das Dreieck ein Nachbardreieck mit gemeinsamer Hypotenuse besitzt und es zwar
selbst gezeichnet wird (draw-Flag = true), das Nachbardreieck aber nicht (draw-Flag =
false), so unterteile das Dreieck in zwei neue, setze sie auf die nächsthöhere Rekursionsstufe
und kennzeichne sie mittels eines Flags, das in der Implementierung deptri (,,dependency
triangle") genannt wurde.
3. Stelle diejenigen Dreiecke der niedrigeren Stufe wieder her (draw-Flag = true), die eines der
durch deptri gekennzeichneten Dreiecke als Nachbarn besitzen und kennzeichne diese
ebenfalls über das deptri-Flag.
4. Lösche in diesem Fall die darüber liegenden Dreiecke der höheren Stufe.
Für den Ausschluss der Dreiecke am Rand des Höhenfelds wird über die Funktion bool
testEdge(triangle3 &tri) während des Unterteilungsprozesses ermittelt, ob ein Dreieck mit einer
seiner Kanten am Rand des Höhenfelds grenzt. Dazu werden alle drei Punkte mit den Randwerten
des Höhenfelds verglichen. Liegen mindestens zwei der Punkte im Bereich des Randes, so wird ein
isEdge-Flag für das Dreieck auf true gesetzt, um damit das Dreieck entsprechend zu kennzeichnen.
22
Abbildung 17: Rekursives Splitting: Die Unterteilung des durch die gepunktete Linie
gekennzeichneten Dreiecks in (a) würde eine ,,T-Junction" an dem markierten Punkt einführen. Das
Mesh in (b) zeigt das Resultat des rekursiven Splittings, um diese Situation zu umgehen. [LOD_3D]