Version vom 30. Mai 2005, 12:42 Uhr

View Independent Progressive Meshes (VIPMs) sind für beliebige Objekte anwendbar, jedoch vor allem bei kleineren Objekten kaum weg zu denken. "View Independent" bedeutet, dass es nur einen Wert gibt welcher besagt wie detailliert ein Objekt gezeichnet werden soll. Dieser Wert hängt im Normalfall von der Entfernung zum Betrachter ab. Zusätzlich könnte jedoch beispielsweise auch beachtet werden, ob dieses Objekt innerhalb eines Nebels liegt oder der Bereich nur wenig beleuchtet wird. Für große Objekte wie bespielsweise ein großes Haus oder gar eine Insel bedeutet dies jedoch, dass es dem LOD-Algorithmus egal ist von welcher Seite ich mich dem Haus oder der Insel nähere, er wird immer an den gleichen Stellen den Level of Detail erhöhen. Dies macht VIPMs für größere Objekte nur begrenzt brauchbar.

Funktionsweise

VIPMs benötigen einge vorberechnete Daten. Anhand dieser Daten ist es sehr effizient möglich, den Level of Detail eines Objektes Punkt für Punkt zu erhöhen oder zu senken. Wie bereits erwähnt wird ein Fehlerwert benötigt, welcher angibt wie detailiert das Objekt gezeichnet werden soll. In welchem Wertebereich dieser Fehlerwert liegt und auch ob er kleiner oder größer werden soll wenn das Objekt detaillierter dargestellt werden soll ist beliebig, muss jedoch natürlich beim vorberechnen der Daten und bei der Anwendung gleich sein.

Wenn man eine Index-Liste besitzt um die 3ecke eines Objektes zu zeichnen, so muss man beim hinzufügen eines Vertex nur die vollständige Vertexliste (für den höchsten Level of Detail) bereit stellen und einige Indizes der Index-Liste ändern und da es ein paar neue 3ecke geben kann die Index Liste um einige, wenige 3ecke erweitern. Wenn man bereits den Speicher für das vollständige Objekt, also das Objekt mit höchstem Level of Detail, reserviert hat, so muss man zum erweitern der Index Liste nur die Anzahl der gezeichneten 3ecke ändern. Wenn gespeichert wird welche Indizes geändert werden müssen, so geht diese Änderung ebenfalls sehr schnell.

Es gibt eine Einschränkung bei VIPMs die die größe der vorberechneten Daten etwas verkleinert, jedoch kaum bis gar keine negativen Auswirkungen hat: beim Hinzufügen eines Punktes dürfen immer nur alle direkt angrenzenden 3ecke zu einem anderen Punkt verändert werden. Dies ist notwendig um beim wegnehmen des Punktes zu wissen welcher Punkt vorher zu dem entsprechenden 3eck gehörte.

Datenstrukturen

Die übliche Vorgehensweise bei VIPMs ist, einen Vertexbuffer zu verwenden, welcher durch eine 3ecksliste indiziert wird. Triangle-Strips oder -Fans können bei VIPMs leider nicht verwendet werden. Der Vertexbuffer beinhaltet die Vertices des Objektes in der Reihenfolge wie sie verwendet werden sollen. Der Punkt der hinzu kommt wenn das Objekt den höchsten Level of Detail erreicht ist demnach am Ende der Vertexliste. Gleich verhält es sich bei der 3ecksliste, also die 3ecke die erst durch den letzten Punkt beim höchsten Level of Detail hinzu kommen, stehen am Ende der 3ecksliste. Für jeden neuen Punkt benötigt man die Daten zum hinzufügen oder teilen (auch als Split bezeichnet) und natürlich auch zum wieder entfernen oder zusammenführen (auch als Merge bezeichnet). Die notwendigen Daten für jeden neuen Punkt sind:

Der Array oder die Liste die aus dieser Datenstruktur besteht wird im weiteren (siehe Vertex Split und Vertex Merge) als VertexSplit-Liste bezeichnet.

Häufig wird für die ÄnderungsIndizes ein eigener Array angelegt, wodurch die Datenstruktur für einen Vertexsplit eine fixe größe besitzt und somit ebenfalls als Array abgelegt werden kann. Da man natürlich keinen Vertexsplit auslassen darf, würde man dadurch nur eine Variable benötigen welche die letzte Position in diesem zusätzlichen Array abspeichert.

Errorwert

Wie bereits erwähnt können in den Errorwert mehrere Faktoren einfließen. Der gängiste ist aber natürlich die Entfernung des Objektes zum Betrachter. Um für den Errorwert auch die Auflösung zu berücksichtigen, kann man einen fixen Wert als Multiplikator für die Entfernung verwenden. Wie dieser Multiplikator berechnet werden kann ist beim Screenspace Error etwas ausführlicher für den vertikalen Errorwert erklärt.

Der aus verschiedensten Parametern berechnete Errorwert dient nun dazu, zu entscheiden ob ein (oder vielleicht sogar mehrere) Vertex-Splits oder -Merges durchgeführt werden sollen. Wenn ein höherer Errorwert einen höheren Level of Detail bedeuten soll, so könnte dies bei jedem Renderdurchgang beispielsweise so aussehen:

while AktuellerErrorwert > VertexSplit[ Nächster_Split ].Error
 Führe Vertex Split durch
while AktuellerErrorwert < VertexSplit[ Letzter_Split ].Error
 Führe Vertex Merge durch

Die while schleife dient hier dazu mehrere Splits oder Merges je Frame zu zulassen. Da wir Punkt für Punkt zu einem Objekt hinzu fügen kann es durchaus passieren, dass mehrere Level of Detail Stufen innerhalb eines Frames überschritten werden, obwohl dies natürlich nicht der Normalfall sein sollte.

Vertex Split

Mit der unter Datenstrukturen erleuterten Datenstruktur für einen Vertexsplit und den zusätzlichen aktuellen Werten:

• VertexBufferLänge: Aktuelle Länge des Vertex Buffers.
• DreiecksListeLänge: Aktuelle Länge der 3ecksliste.
• Nächster_Split: Nächster Vertex-Split Eintrag.

könnte ein Vertex Split folgenermaßen aussehen:

VSplit ist hier der Eintrag "Nächster_Split" der VertexSplit-Liste.

 DreiecksListeLänge := DreiecksListeLänge + (VSplit.NeueDreieckeAnzahl * 3);
 for f := 0 to VSplit.ÄnderungsAnzahl-1 do
 begin
  TriangleEntry := VSplit.ÄnderungsIndizes[ f ];
  VertexBuffer[ TriangleEntry ] := VertexBufferLänge;
 end;
 VertexBufferLänge := VertexBufferLänge + 1;
 Nächster_Split := Nächster_Split + 1;

In der ersten Zeile wird hier die 3ecksliste um NeueDreieckeAnzahl erweitert (ein 3eck besitzt natürlich 3 neue Punkte deshalb * 3). Diese neuen 3ecke sind bereits in der vorberechneten, kompletten 3ecksliste vorhanden. Somit muss OpenGL nur mitgeteilt werden, dass auch diese 3ecke beachtet werden sollen.

In der Schleife wird jeder zu ändernde Index auf den neuen Vertexindex gesetzt. Der neue VertexIndex ist natürlich gleich der aktuellen VertexBufferLänge.

Am Ende wird noch bekannt gegeben, dass nun ein zusätzlicher Vertex verwendet wird.

Vertex Merge

Der Merge-Vorgang sieht sehr ähnlich aus wie der Split-Vorgang. Wie bereits erwähnt, wurde beim Split nur ein Wert der 3ecks-Liste geändert. Diesen Wert können wir uns aber einfach von unseren vorberechneten Daten holen:

VSplit ist hier der Eintrag "Nächster_Split - 1" der VertexSplit-Liste.

DreiecksListeLänge = DreiecksListeLänge - VSplit.NeueDreieckeAnzahl * 3;
for f = 0 to f < VSplit.ÄnderungsAnzahl
{
 Integer TriangleEntry = VSplit.ÄnderungsIndizes[ f ];
 VertexBuffer[ TriangleEntry ] = VSplit.SplitVertex;
}
VertexBufferLänge = VertexBufferLänge - 1;
Nächster_Split = Nächster_Split - 1;

Die erste und die letzten beiden Zeilen machen nur den letzten Split rückgängig.

In der For-Schleife werden natürlich ebenfalls die Änderungen des letzten Split rückgängig gemacht, jedoch benötigen wir hier zusätzliche Informationen. Die Zeile

VertexBuffer[ TriangleEntry ] = VSplit.SplitVertex;

ist der einzige Grund weshalb wir die Variable SplitVertex für jeden Vertex Split benötigen, und damit dies nicht noch komplizierter wird, bzw. noch mehr Datenoverhead erfordert kommt hier auch die unter "Funktionsweise" erwähnte Einschränkung zum tragen, dass immer nur ein bestimmter Wert der 3ecks-Liste verändert werden darf.

Verberechnen der Daten

Ausgehend vom vollständigen Modell wird der Punkt berechnet, an dem der Errorwert am geringsten ist. Eine einfache Methode wäre hier folgende:

1. Man berechnet sich für alle umliegenden Punkte eines Punktes die "durchschnittliche" Ebene (beispielsweise nach der Methode der kleinsten Quadrate nach Gauß).
2. Man prüft für den jeweiligen Punkt die Entfernung zu dieser Ebene und nimmt diesen als Fehlerwert.
3. Man führt dies für alle Punkt durch und nimmt den Punkt mit dem kleinsten Fehlerwert als ersten zu entfernenden Punkt.

Dies kann man rekursiv für alle folgenden Punkte fortsetzen bis ein bestimmtes Abbruchkriterium erreicht ist (beispielsweise ein zu hoher Fehlerwert). Natürlich kann die Wahl des Punktes nach belieben verbessert werden, im Extremfall sogar so weit, dass man sich den Fehlerwert von mehreren Betrachtungswinkeln berechnet und Kompromisse schließt wenn ein Punkt nur sehr selten auffällt.

Wenn man nun einen zu entfernenden Punkt ausgewählt hat und zusätzlich noch einen Punkt mit dem dieser "gemerged" werden soll, so sieht die Vertex-Split-Struktur dafür folgendermaßen aussehen:

Am Ende dieses Durchlaufes werden alle noch vorhandenen Punkte vor den bereits vorhandenen Punkten in den Vertex Buffer eingefügt und auch die vorhandenen 3ecke vor die berechnete 3ecks-Liste gestellt.

Morphing

Da man bei jedem Split bzw. jedem Merge den Vertex der hinzugefügt bzw. entfernt wird kennt und zusätzlich noch den Vertex von dem gesplittet bzw. mit dem der entfernte Vertex zusammen geführt wird kennt, ist die (lineare) Interpolation der Vertexposition, Texturkoordinaten und des Farbwertes kein Problem. Der Normalvektor sollte zwar spherisch interpoliert werden, da dies jedoch etwas aufwändig ist, die Normalisierung der Normalvektoren über Hardware mittlerweile nicht mehr so viel Performance schluckt und der Unterschied zwischen spherisch und linear interpolierten Normalvektoren bei kleineren Änderungen kaum bemerkbar ist, reicht hier üblicherweise ebenfalls eine einfache lineare Interpolation aus.

Anwendungsgebiete

Natürlich ist das Hauptanwendungsgebiet für VIPMs ein eher kleines jedoch eher detailreiches, nicht animiertes (statisches) Objekt. Obwohl der Datenoverhead von durchschnittlich etwa 20 Byte/Vertex nicht zu missachten ist, sind VIPMs für derartige Objekte zur Zeit der beste Level of Detail-Algorithmus.

Landschaften

Bei Landschaften werden VIPMs üblicherweise je Patch (kleinerer quadratischer Bereich der Landschaft) verwendet und die Zwischenräume der Patches können auf verschiedenste Arten gefüllt werden. Da Landschaften jedoch mit <= 3 Byte je Höhenpunkt (auf der Festplatte) auskommen würden, stellen die ~20 Byte Overhead von VIPMs doch einen beachtlichen Prozentteil des Speicherbedarfs dar.

Bone animierte Modelle / Skinned Characters

Natürlich ist es für Bone animierte Modelle von Vorteil wenn weniger Vertices (eventuell sogar in Software) berechnet werden müssen. Der Nachteil daran ist jedoch, dass Bone animierte Modelle nicht in jedem Animationsschritt den gleichen Errorwert für jeden Vertex besitzen. Somit müssen bereits beim Vorberechnen der Daten Kompromisse eingegangen werden, beispielsweise ob wenige Animationsschritte in denen der Errorwert für einen Punkt niedrig wäre ausschlaggebend sein sollen oder nicht. Diese Kompromisse können sich natürlich bei der Darstellung in einigen Fällen stark negativ auswirken. Bei sehr detaillierten Modellen sollte es jedoch genug Punkte geben die in allen möglich Animationsschritten ungefähr den selben Errorwert besitzen und somit früher entfernt werden können.

Ressourcen

• Der Erfinder: Hugues Hoppe
• Ursprüngliche Publikation: [1]
• Wichtige Erweiterungen: [2]