h(A, B) bestimmt für jeden Punkt in A den nächstgelegenen Punkt in B und nimmt davon das
Maximum. Diese Funktion, auch einseitige Hausdorff-Distanz genannt, ist nicht symmetrisch. Jeder
Punkt in A wird einem einzigen Punkt in B zugeordnet, aber dabei können nicht zugeordnete (und
mehrfach zugeordnete) Punkte in B verbleiben. Deshalb ist h(A, B) h(B, A). Jedoch wird die
Hausdorff-Distanz (oder beidseitige Hausdorff-Distanz) so konstruiert, dass sie symmetrisch ist,
indem beide einseitigen Hausdorff-Distanzen betrachtet werden und nur das Maximum
zurückgegeben wird. Dies sei hier in Abbildung 15 veranschaulicht.
4.2.5.1 Die Implementierung der Fehlerberechung
In PointMesh wird aus Gründen der Geschwindigkeit für die Fehlerabschätzung nur eine Näherung
der Hausdorff-Distanz berechnet und die Berechnung nur für Dreiecke der Ausrichtungen 0 bis 3
durchgeführt, was bedeutet, dass diese Berechnung nur für Dreiecke in ungeraden
Rekursionsschritten der subdivide(...)-Funktion durchgeführt wird.
In der Funktion
calc_error(triangle3 input, char orientation)
wurde dies folgendermaßen implementiert:
1. Wähle den linken unteren Punkt des Dreiecks und suche den entsprechenden Gitterpunkt-
Index.
2. Berechne die Größe der vom Dreieck eingeschlossenen rechteckigen Region in Form der
Anzahl an Gitterpunkten in x- und z-Richtung.
3. Speichere Indizes aller Punkte, die von dieser Region eingeschlossen werden in einem STL-
Vektor.
4. Bestimme die minimale Höhe der Dreieckspunkte (Vertices) und speichere sie nach min_y.
5. Bestimme die maximale Höhe aller Gitterpunkte innerhalb der rechteckigen Region und
speichere sie nach max_height.
6. Berechne den Fehler: error = max_height min_y
Dieser Fehler ist ausschlaggebend dafür, ob eine weitere Unterteilung durchgeführt wird oder nicht.
Als Entscheidungsgrenze wurde als Voreinstellung die Hälfte des Gitterpunktabstands (entspricht
der zuvor gewählten Maschenweite) gewählt, damit die Dreiecke nicht zu sehr entarten. Der Nutzer
kann den Schwellwert nach eigenem Ermessen ändern. Liegt der Fehler über dem Schwellwert,
wird das betreffende Dreieck weiter unterteilt, d.h. die Rekursion wird fortgesetzt. Liegt er darunter,
wird die Unterteilung gestoppt und für die aktuellen Dreiecke das draw-Flag gesetzt.
Es gibt einen Fall, in dem der Fehler nie klein genug wird, um unter diesen Schwellwert zu
gelangen. Dies passiert an solchen Stellen, an denen sehr große Höhendifferenzen zwischen den
Gitterpunkten auftreten. Die Region der eingeschlossenen Punkte wird hier durch die Unterteilung
immer kleiner und der Fehler bleibt trotzdem über dem Schwellwert. Bei weniger als zwei
eingeschlossenen Gitterpunkten ist keine sinnvolle Fehlerberechnung mehr möglich. Hier wird die
Rekursion gestoppt, sobald eine Seite des zu unterteilenden Dreiecks kleiner als der zweifache
Gitterpunktabstand ist. Anschließend wird das draw-Flag für die beiden Eingabe-Dreiecke der
Funktion auf true gesetzt.
20