4.2 Triangulierung über rekursive Unterteilung (recursive subdivision)
4.2.1 4-8 Mesh
Ein 4-8 Mesh ist, mathematisch beschrieben, eine reguläre trianguläre Unterteilung einer Teilfläche
des Körpers R². Es ist ein semi-reguläres Gitter, bei dem die Vertices (Knotenpunkte) eine
maximale Wertigkeit von vier oder acht haben, d.h. dass die Knoten im Inneren jeweils vier oder
acht und am Rand entweder drei oder fünf Nachbarn besitzen.
Ein solches Mesh eignet sich besonders gut für eine apdaptive Triangulierung, da es sich, im
Gegensatz zu anderen Methoden (face split / vertex split), durch einfache Bisektion verfeinern lässt
und dabei in jedem Schritt immer wieder ein feineres gültiges 4-8 Mesh entsteht. Dies hat zur
Folge, dass bei restriktiver Triangulierung die Topologie des Meshs erhalten bleibt. Das vereinfacht
die adaptive Verfeinerung enorm: Wenn ein Mesh nicht gleichförmig verfeinert wird, bleibt das
verfeinerte Mesh trotzdem noch gültig.
Ein weiterer Vorteil ist, dass sich die Anzahl der Dreiecke zur nächst höheren Stufe nur um den
Faktor zwei erhöht, womit eine feinere Detailabstufung möglich ist, als bei einigen anderen
bekannten Verfahren.
4.2.2 Nicht-restriktive Verfeinerung
Um ein 4-8 Mesh zu erzeugen, wird zu Beginn ein grobes Mesh aus zwei Dreiecken aufgebaut,
indem die vier Eckpunkte des Höhenfelds identifiziert und zu jeweils zwei Dreiecken verbunden
werden. Dieses initiale Mesh bildet also ein einzelnes trianguliertes Viereck (Quad).
In den folgenden Schritten wird von jedem Dreieck der Mittelpunkt der Hypotenuse bestimmt und
genau an dieser Stelle das Dreieck in zwei kleinere Dreiecke halbiert. Dabei hat man zwischen acht
möglichen Ausrichtungen der Dreiecke zu unterscheiden, die bei dieser Art der Unterteilung
entstehen können, wie es in Abbildung 13 dargestellt wird.
16