Quelltext der Seite Benutzer:Ambur/Garland-Heckbert-Algorithmus

Der '''Garland-Heckbert-Algorithmus''' ist in der [[Computergraphik]] ein Verfahren, um den Detailgrad eines als [[Dreiecksnetz]] modellierten 3D-Körpers kontrolliert zu reduzieren, 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 zusammengefaßt werden. Es wird immer diejenige Kante gelöscht, deren Entfernen die geringste optische Veränderung des Körpers bewirkt.

== Geschichte ==
Der Algorithmus wurde 1997 in einem Paper von Michael Garland und Paul Heckbert vorgestellt<ref> 	
M. Garland and P. Heckbert. Surface Simplification Using Quadric Error Metrics. In Proceedings of SIGGRAPH 97. [http://mgarland.org/papers/quadrics.pdf]</ref>.

== Algorithmus ==
[[Datei:Edge contraction.svg|miniatur|280px|right|Kantenkontraktion]]
Im 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 enstandene Knoten plaziert wird. 

Dazu wird eine [[Quadrik|Fehlerquadrik]] verwendet, die jedem Knoten und jeder Kante zugeordnet wird. Diese gibt Auskunft darüber, wie groß der enstehende optische Fehler wäre, wenn die entsprechende Kante kontrahiert werden würde. Gleichzeitig kann mit ihr berechnet werden, wo der neu entstehende Knoten plaziert werden muss, damit genau dieser Fehler (und kein größerer) entsteht.

=== Pseudocode ===
Berechne zunächst für jeden Knoten b<sub>i</sub> die zugehörige initale Fehlerquadrik Q<sub>b<sub>i</sub></sub>. Siehe dazu weiter unten.

Danach iteriere solange, bis der gewünschte Detailgrad erreicht ist:
#Jede Kante erhält als Quadrik Q<sub>E<sub>j</sub></sub> 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.
#Finde unter allen Kanten diejenige, deren Fehler beim Kollabieren am kleinsten werden würde. Kollabiere diese Kante.
#Der beim Kollaps neu entstehende Punkt bekommt als Quadrik diejenige zugewiesen, die der kollabierten Kante gehörte.

=== Detaillierte Beschreibung ===

==== Initale Fehlerquadriken ====

Den Fehler, der beim Zusammenfassen zweier Knoten v<sub>1</sub> und v<sub>2</sub> zu einem neuen v<sub>neu</sub> entsteht, definiert man als: Quadrat der Summe der Abstände, die v<sub>neu</sub> zu allen [[Ebene|Flächen]] hat, die durch irgendeins der Dreiecke definiert werden, welche an v<sub>1</sub> oder v<sub>2</sub> grenzen.

Um zunächst den Abstand eines Punktes v<sub>neu</sub> zu einer Fläche F zu berechnen, kann folgende Formel verwendet werden:

<math>dist(v_{neu}, F) = n^T \cdot (v_{neu}-b)</math>

Dabei ist b ein beliebiger Punkt in der Fläche (z.B. einer der Eckpunkte des Dreiecks, das in der Fläche liegt), und n<sup>T</sup> ist der Normalenvektor der Fläche (zum Zeilenvektor [[Matrix_(Mathematik)#Die_transponierte_Matrix|transponiert]]).

Bildet man nun wie vorgesehen das Quadrat dieses Abstands, erhält man:

<math>\begin{align}
dist(v_{neu}, F)^2 &= (n^T \cdot (v_{neu}-b))^2\\
&= (n^T \cdot (v_{neu}-b)) \cdot (n^T \cdot (v_{neu}-b))\\
&= (n^Tv_{neu} - n^Tb) \cdot (n^Tv_{neu} - n^Tb)\\
&= (n^Tv_{neu})^2 - n^Tv_{neu} \cdot n^Tb - n^Tb \cdot n^Tv_{neu} + (n^Tb)^2\\
&= {v_{neu}}^Tn\cdot n^Tv_{neu} - b^Tn\cdot n^Tv_{neu} - {v_{neu}}^Tn\cdot n^Tb + b^Tn\cdot n^Tb
\end{align}</math>

Verwendet man [[homogene Koordinaten]], so ist diese Rechnung gleichbedeutend mit:

<math>
dist(v_{neu}, F)^2 = ( v_{{neu}_x} v_{{neu}_y} v_{{neu}_z} 1) \cdot 
\begin{pmatrix} nn^T & -nn^Tb \\ -b^Tnn^T & b^Tnn^Tb\end{pmatrix} \cdot
\begin{pmatrix} v_{{neu}_x} \\ v_{{neu}_y} \\ v_{{neu}_z} \\ 1 \end{pmatrix}
</math>

Die Matrix <math> Q_F = \begin{pmatrix} nn^T & -nn^Tb \\ -b^Tnn^T & b^Tnn^Tb\end{pmatrix} </math> wird als Fehlerquadrik der Fläche F bezeichnet.

Betrachtet man nun einen Knoten b des Dreiecksnetzes, so kann ihm als Fehlerquadrik Q<sub>b</sub> die Summe der Quadriken seiner angrenzenden Dreiecksflächen F<sub>i</sub> zugewiesen werden. 

<math> Q_b = \sum_i {v_{neu}}^T \cdot Q_{F_i} \cdot v_{neu} </math>

Die Quadrik Q<sub>b</sub> wird zur Initialisierung des Algorithmus für jeden Knoten des Dreiecksnetzes berechnet.

==== Iterationsschritt ====

===== Berechnung der zu kontrahierenden Kante =====

Jede Kante e<sub>j</sub> des Dreiecksnetzes erhält als Quadrik Q<sub>e<sub>j</sub></sub> die Summe der Quadriken ihrer Endpunkte b<sub>1</sub> und b<sub>2</sub>:

<math> Q_{e_j} = Q_{b_1} + Q_{b_2} </math>

Falls der Kante e<sub>j</sub> 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 v<sub>neu</sub> beim Kontrahieren von e<sub>j</sub> einen möglichst kleinen Fehler verursachen würde
* Wie groß der verursachte Fehler wäre.
Um den optimalen Punkt v<sub>neu</sub> zu bestimmen, muss also der [[Extremwert|Minimalwert]] der Fehlerfunktion gefunden werden, d.h. alle [[partielle Ableitung|partiellen Ableitungen]] von <math>( {v_{neu}}^T \quad 1) \cdot Q_{e_j} \cdot \begin{pmatrix} v_{neu} \\ 1 \end{pmatrix}</math> müssen gleich 0 sein. 

Berechnet man diese Ableitungen, erhält man folgendes zu lösende Gleichungssystem:

<math>
\begin{pmatrix} & nn^T   & & -nn^Tb \\ 0 & 0 & 0 & 1\end{pmatrix} \cdot
\begin{pmatrix} v_{{neu}_x} \\ v_{{neu}_y} \\ v_{{neu}_z} \\ 1 \end{pmatrix} =
\begin{pmatrix}0 \\ 0 \\ 0 \\ 1 \end{pmatrix}
</math>

Dabei können sich mehrere Fälle ergeben:
* Die Matrix <math> \begin{pmatrix} & nn^T   & & -nn^Tb \\ 0 & 0 & 0 & 1\end{pmatrix} </math> ist [[inverse Matrix|invertierbar]]: Der Punkt v<sub>neu</sub> kann einfach durch das Gleichungssystem berechnet werden.
* Die Matrix <math> \begin{pmatrix} & nn^T   & & -nn^Tb \\ 0 & 0 & 0 & 1\end{pmatrix} </math> ist nicht invertierbar: Der optimale Wert für v<sub>neu</sub> kann auf der Verbindungsstrecke der beiden Kantenendpunkte b<sub>1</sub> und b<sub>2</sub> gefunden werden. Man beschreibt dann v<sub>neu</sub> als [[Linearkombination]] der beiden Endpunkte: <math> {v_{neu}}^*(\lambda) = (1-\lambda)\cdot b_1 + \lambda \cdot b_2 </math> und sucht stattdessen das Minimum von <math>dist(v_{neu}, F)^2 = ( ({v_{neu}}^*)^T \quad 1) \cdot Q_{e_j} \cdot \begin{pmatrix} {v_{neu}}^* \\ 1 \end{pmatrix}</math> 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 b<sub>1</sub> und b<sub>2</sub> verwendet, oder b<sub>1</sub> oder b<sub>2</sub> selbst.

Nachdem nun v<sub>neu</sub> bekannt ist, wird der enstandene Fehler <math>( {v_{neu}}^T \quad 1) \cdot Q_{e_j} \cdot \begin{pmatrix} v_{neu} \\ 1 \end{pmatrix}</math> berechnet. Dieser Fehler wird in eine [[Prioritätswarteschlange]] eingetragen, wobei der niedrigste Fehler das Top-Element der Warteschlange ist.

===== Kontrahieren der Kante =====

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 v<sub>neu</sub> wird die Fehlerquadrik der dabei zerstörten Kante zugewiesen. Dies bewirkt, daß der Fehler in den folgenden Iterationsschritten nicht nur von dem jeweils aktuellen Dreiecksnetz abhängt, sondern auch die vorherigen Veränderungen mit einbezogen werden.

== Referenzen ==

<references />