Geometrical Mipmapping: Unterschied zwischen den Versionen

Version vom 7. Oktober 2004, 15:14 Uhr

Geometrical Mipmapping ist einer der effizientesten und noch dazu einer der einfachsten Level of Detail Algorithmen für Landschaften auf heutiger Hardware.

Patches

Der Algorithmus erfordert (wie auch einige andere LOD-Algorithmen für Landschaften) eine Einteilung der Landschaft in Patches. Ein Patch ist ein quadratischer Block aus N*N Höhenpunkten der Landschaft. In Abbildung 1 besteht ein Patch beispielsweise aus 9x9 Höhenpunkten bzw. 8x8 Feldern.

Abbildung 1: Von links oben nach rechts unten sind hier die Level of Detail Stufen 3, 2, 1 und 0 zu sehen. Die rot markierten Punkte sind Problempunkte die zu Löchern in der Landschaft führen können.

Wie in Abbildung 1 unschwer zu erkennen erfolgt die Wahl der Level of Detail-Stufe immer pro Patch. Somit muss auch der Error Wert je Patch berechnet werden. Anhand dieses Error Wertes kann beispielsweise mittels des maximalen Screenspace Errors die Wahl der Level of Detail-Stufe durchgeführt werden. Da jedoch Löcher entstehen können wenn 2 Patches mit unterschiedlichem Level of Detail nebeneinander liegen, müssen zwischen den Patches noch Verbindungen eingebaut werden.

Verbindung der Patches

Wenn 2 Patches mit unterschiedlichen Level of Detail-Stufen nebeneinander liegen, so hat man mehrere Möglichkeiten wie dies zu behandeln ist:

1. Passe die entsprechenden Punkte (rot markierte Punkte in Abbildung 1) der Höhe des Patches mit dem niedrigeren Level of Detail an. Dies wäre eine schöne Lösung, kann jedoch durch Rundungsfehler ebenfalls zu schmalen Löchern führen.
2. Passe den Patch mit der niedrigeren Level of Detail-Stufe dem Patch mit dem höheren Level of Detail an. Dies bringt ebenfalls sehr hochwertige Ergebnisse, führt jedoch zu viel mehr 3ecken die nur sehr selten wirklich notwendig wären.
3. Passe den Patch mit der höheren Level of Detail-Stufe dem Patch mit dem niedrigeren Level of Detail an. Dies führt ab und zu zu recht unschönenen Ergebnissen, ist jedoch (meines erachtens) die brauchbarste und auch am häufigsten verwendete Methode für Echtzeitanwendungen.

Abbildung 2: Die Verbindungen bei Anwendung der 3. Methode. Hier können keine Löcher in der Landschaft entstehen.

Wie in Abbildung 2 zu sehen werden sowohl bei der 2., also auch bei der 3. Methode an den Patch Rändern Triangle Fans eingeführt. Da nun keine losen Punkte mehr vorhanden sind, können keine Löcher mehr entstehen.

Morphing

Auch das Morphing ist bei Geometrical Mipmaps verhältnismäßig einfach. Da die Wahl der Level of Detail-Stufe je Patch erfolgt, muss natürlich auch der gesamte Patch morphen. Dafür werden die neu eingefügten, bzw. die zu entfernenden Höhenpunkte von der ursprünglichen Position bis zur gewünschten Position linear interpoliert. Da die Landschaft aus 3ecken besteht ist die Position bei einem niedrigeren Level of Detail bei jedem entfernten Punkt die Mitte von 2 anderen Punkten. Bei den Übergängen zwischen 2 Patches muss natürlich darauf geachtet werden, das beide Patches die Vertices gleich berechnen.

Verwaltung der Patches

Üblicherweise werden die Patches in einem Quadtree verwaltet wodurch Sichtbarkeitsberechnungen sehr einfach und effizient durchgeführt werden können. Bei kleineren Landschaften die kein Streaming erfordern werden die Patches auch häufig als 2 dimensionaler Array abgelegt.

Ressourcen

• Ursprüngliche Publikation zu Geometrical Mipmapping
• Kleinere Erweiterungen zum ursprünglichen Algorithmus
• DGL-Tutorial zum Geometrical Mipmapping