Garland-Heckbert-Algorithmus
Der Garland-Heckbert-Algorithmus ist ein Verfahren der Computergrafik, mit dem der Detailgrad eines als Dreiecksnetz modellierten 3D-Körpers kontrolliert reduziert werden kann, ohne dabei das grundsätzliche Aussehen des Körpers zu verändern. Dies geschieht inkrementell, wobei immer eine Kante des Dreiecksnetzes gelöscht und die beiden adjazenten Knoten zu einem einzelnen Knoten zusammengefasst werden. Es wird immer diejenige Kante gelöscht, deren Entfernen die geringste optische Veränderung des Körpers bewirkt.
Der Algorithmus wurde 1997 in einer Veröffentlichung von Michael Garland und Paul Heckbert vorgestellt[1].
Algorithmus
[Bearbeiten | Quelltext bearbeiten]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/b/b1/Edge_contraction.svg/280px-Edge_contraction.svg.png)
In einem Dreiecksnetz wird das Löschen einer Kante und Zusammenfassen der übrig gebliebenen Knoten als Kantenkontraktion oder -kollaps bezeichnet. Der Algorithmus gibt Auskunft darüber, welche Kante gelöscht werden muss, und an welcher Stelle der neu entstandene Knoten platziert wird.
Dazu wird eine Fehlerquadrik verwendet, die jedem Knoten und jeder Kante zugeordnet wird. Diese gibt Auskunft darüber, wie groß der entstehende optische Fehler wäre, wenn die entsprechende Kante kontrahiert werden würde. Gleichzeitig kann mit ihr berechnet werden, wo der neu entstehende Knoten platziert werden muss, damit genau dieser Fehler (und kein größerer) entsteht.
Pseudocode
[Bearbeiten | Quelltext bearbeiten]Berechne zunächst für jeden Knoten bi die zugehörige initiale Fehlerquadrik Qbi. Siehe dazu weiter unten.
Danach iteriere solange, bis der gewünschte Detailgrad erreicht ist:
- Jede Kante erhält als Quadrik QEj die Summe der Quadriken ihrer beiden Endpunkte.
- Berechne anhand der Quadrik für jede Kante, an welcher Stelle der zusammengezogene Knoten erstellt werden müsste, um minimalen Fehler beim Kollabieren der Kante zu verursachen.
- Ordne alle Kanten anhand ihrer Fehler. Kollabiere die Kante mit dem kleinsten Fehler.
- Ordne dem neuen Knoten als Quadrik die Summer der Quadriken der beiden Endpunkte der Kante zu.
- Update die Quadriken aller Kanten, die durch den Kollaps der Kante verändert wurden.
Detaillierte Beschreibung
[Bearbeiten | Quelltext bearbeiten]Initiale Fehlerquadriken
[Bearbeiten | Quelltext bearbeiten]Den Fehler, der beim Zusammenfassen zweier Knoten v1 und v2 zu einem neuen vneu entsteht, definiert man als: Quadrat der Summe der Abstände, die vneu zu allen Flächen hat, die durch irgendeins der Dreiecke definiert werden, welche an v1 oder v2 grenzen.
Um zunächst den Abstand eines Punktes vneu zu einer Fläche F zu berechnen, kann folgende Formel verwendet werden:
Dabei ist b ein beliebiger Punkt in der Fläche (z. B. einer der Eckpunkte des Dreiecks, das in der Fläche liegt), und nT ist der Normalenvektor der Fläche (zum Zeilenvektor transponiert).
Bildet man nun wie vorgesehen das Quadrat dieses Abstands, erhält man:
Verwendet man homogene Koordinaten, so ist diese Rechnung gleichbedeutend mit:
Die Matrix wird als Fehlerquadrik der Fläche F bezeichnet.
Betrachtet man nun einen Knoten b des Dreiecksnetzes, so kann ihm als Fehlerquadrik Qb die Summe der Quadriken seiner angrenzenden Dreiecksflächen Fi zugewiesen werden.
Die Quadrik Qb wird zur Initialisierung des Algorithmus für jeden Knoten des Dreiecksnetzes berechnet.
Iterationsschritt
[Bearbeiten | Quelltext bearbeiten]Berechnung der zu kontrahierenden Kante
[Bearbeiten | Quelltext bearbeiten]Jede Kante ej des Dreiecksnetzes erhält als Quadrik Qej die Summe der Quadriken ihrer Endpunkte b1 und b2:
Falls der Kante ej vorher noch keine Quadrik zugeordnet war (nur im ersten Iterationsschritt), oder falls sich die Quadrik im Vergleich zum letzten Iterationsschritt verändert hat (weil einer der Endpunkte durch Kantenkontraktion verschoben wurde), muss nun berechnet werden:
- Welcher Punkt vneu beim Kontrahieren von ej einen möglichst kleinen Fehler verursachen würde
- Wie groß der verursachte Fehler wäre.
Um den optimalen Punkt vneu zu bestimmen, muss also der Minimalwert der Fehlerfunktion gefunden werden, d. h. alle partiellen Ableitungen von müssen gleich 0 sein.
Berechnet man diese Ableitungen, erhält man folgendes zu lösende Gleichungssystem:
Dabei können sich mehrere Fälle ergeben:
- Die Matrix ist invertierbar: Der Punkt vneu kann einfach durch das Gleichungssystem berechnet werden.
- Die Matrix ist nicht invertierbar: Der optimale Wert für vneu kann auf der Verbindungsstrecke der beiden Kantenendpunkte b1 und b2 gefunden werden. Man beschreibt dann vneu als Linearkombination der beiden Endpunkte: und sucht stattdessen das Minimum von bezüglich λ. Dies geschieht durch einfache Ableitung der Funktion nach λ und setzen dieser Ableitung = 0.
- Sollte auch die zweite Methode kein Ergebnis liefern, so wird einfach der Mittelpunkt zwischen b1 und b2 verwendet, oder b1 oder b2 selbst.
Nachdem nun vneu bekannt ist, wird der entstandene Fehler berechnet. Dieser Fehler wird in eine Prioritätswarteschlange eingetragen, wobei der niedrigste Fehler das Top-Element der Warteschlange ist.
Kontrahieren der Kante
[Bearbeiten | Quelltext bearbeiten]Aus der Warteschlange wird das Top-Element entfernt. Dieses Element entspricht derjenigen Kante, deren Kontraktion den geringsten Fehler verursacht. Die Kante wird nun kontrahiert, und dem dabei neu entstehenden Punkt vneu wird die Fehlerquadrik der dabei zerstörten Kante zugewiesen. Dies bewirkt, dass der Fehler in den folgenden Iterationsschritten nicht nur von dem jeweils aktuellen Dreiecksnetz abhängt, sondern auch die vorherigen Veränderungen mit einbezogen werden.