4.2.4 Adaptive Verfeinerung
Durch die nicht-restriktive Verfeinerung wird das Mesh an allen Stellen gleichmäßig verfeinert. Das
Ziel soll aber sein, das Mesh nur an solchen Stellen weiter zu verfeinern, an denen die von den
Dreiecken eingeschlossenen Höhenwerte sich in ihrer Höhendifferenz zum zuvor approximierten
Dreieck merklich unterscheiden, d.h. nur innerhalb solcher Regionen, in denen das Höhenfeld noch
Unebenheiten aufweist.
Um dies zu erreichen, muss man eine effektive Begrenzung für die weitere Unterteilung eines
Dreiecks einrichten. Das heißt, es muss ermittelt werden, wie stark sich die aktuelle Triangulierung
von einer optimalen Triangulierung der Höhenpunkte unterscheidet. In dieser optimalen
Triangulierung würde jeder Höhenpunkt mit seinen vier unmittelbaren Nachbarpunkten verbunden
werden, wäre also im Inneren des Felds ein Eckpunkt für vier Dreiecke.
Es gibt verschiedene Möglichkeiten diese Abweichung (im Folgenden auch Fehler genannt) zu
berechnen. Eine sehr beliebte Variante in diesem Bereich ist die Hausdorff-Distanz.
4.2.5 Fehlerberechnung Die Hausdorff-Distanz
Die Hausdorff-Distanz ist ein bekanntes Konzept aus der Topologie und findet Anwendung in der
Bildverarbeitung, Oberflächenmodellierung und einer Vielzahl weiterer Anwendungsgebiete. Sie ist
nur auf Punktmengen definiert. Da man aber eine Oberfläche als eine kontinuierliche Punktmenge
beschreiben kann, kann man sie auch hierauf anwenden.
Zu zwei gegebenen Punktmengen A und B, ist die Hausdorff-Distanz H(A,B) das Maximum der
minimalen Abstände zwischen den Punkten beider Mengen. Mit anderen Worten: Wir suchen für
jeden Punkt der Menge A den nächstgelegenen Punkt in der Menge B und umgekehrt. Anschließend
berechnen wir die Distanzen zwischen all diesen Punktpaaren und nehmen davon das Maximum.
Algebraisch ausgedrückt:
H A , B=max h A , B ,h B , A
wobei
h A , B=max
aA minbBa b
19
Abbildung 15: Die Hausdorff-Distanz zwischen zwei Oberflächen. Die einseitigen Hausdorff-Distanzen
sind h(A,B) = ||v|| und h(B,A) = ||w||. Die beidseitige Hausdorff-Distanz ist H(A,B) = max(||v||,||w||)=||v||.
[LOD_3D]