VIPMs

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 detailliert 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 Dreiecke 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 Dreiecke geben kann, die Index Liste um einige, wenige Dreiecke 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 Dreiecke ä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 Dreiecke zu einem anderen Punkt verändert werden. Dies ist notwendig, um beim Wegnehmen des Punktes zu wissen, welcher Punkt vorher zu dem entsprechenden Dreieck gehörte.

Datenstrukturen

Die übliche Vorgehensweise bei VIPMs ist, einen Vertexbuffer zu verwenden, welcher durch eine Dreiecksliste 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 Dreiecksliste, also die Dreiecke, die erst durch den letzten Punkt beim höchsten Level of Detail hinzu kommen, stehen am Ende der Dreiecksliste. 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:

Datentyp	Bezeichnung	Beschreibung
Integer	SplitVertex	Der Index des Vertex von dem aus geteilt wird. In der Dreiecksliste kann ausschließlich dieser Wert durch den Index des neuen Dreiecks ersetzt werden (siehe Funktionsweise letzter Absatz).
Byte	NeueDreieckeAnzahl	Anzahl der Dreiecke um die die Dreiecksliste erweitert werden muss.
Byte	ÄnderungsAnzahl	Anzahl der Änderungen, die vorgenommen werden müssen. Da ausschließlich ein Wert (SplitVertex) geändert werden darf und ein Dreieck nicht zwei gleiche Werte beinhaltet, ist dies gleichbedeutend mit der Anzahl der Dreiecke, die geändert werden müssen.
Float	Error	Fehlerwert, ab dem dieser Vertex hinzu kommt oder wieder entfernt werden soll.
Integer[ÄnderungsAnzahl]	ÄnderungsIndizes	Dieser Array beinhaltet die Indizes auf die Positionen der Dreiecksliste, auf der die Änderung vorgenommen werden muss.

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ängigste 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 zuzulassen. Da wir Punkt für Punkt zu einem Objekt hinzufü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 erläuterten 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 Dreiecksliste um NeueDreieckeAnzahl erweitert (ein Dreieck besitzt natürlich drei neue Punkte, deshalb * 3). Diese neuen Dreiecke sind bereits in der vorberechneten, kompletten Dreiecksliste vorhanden. Somit muss OpenGL nur mitgeteilt werden, dass auch diese Dreiecke 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 Dreiecks-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 VSplit.ÄnderungsAnzahl-1 do
 begin
  TriangleEntry := VSplit.ÄnderungsIndizes[ f ];
  VertexBuffer[ TriangleEntry ] := VSplit.SplitVertex;
 end;
 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 Dreiecks-Liste verändert werden darf.

Vorberechnen 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:

Bezeichnung	Wert(e)
SplitVertex	Der gewählte Punkt, mit dem der zu entfernende Punkt zusammengeführt werden soll
NeueDreieckeAnzahl	Die Anzahl der Dreiecke, in der sowohl der zu entfernende Punkt als auch der Punkt mit dem der zu entfernende Punkt zusammengeführt werden soll, enthalten ist.
ÄnderungsAnzahl	Die Anzahl der Dreiecke, in der der zu entfernende Punkt enthalten ist, jedoch nicht der Punkt mit dem der zu entfernende Punkt zusammengefürt werden soll.
Error	Der berrechnete Errorwert
ÄnderungsIndizes	Die Dreiecke, auf die ein Änderungsindex zeigt sind noch nicht in der berechneten Dreiecks-Liste vorhanden, müssen also zwischengespeichert werden. Erst wenn die Dreiecke, die bei "ÄnderungsAnzahl" beachtet wurden, in die Dreiecks-Liste kommen, wird der Index des Punktes, mit dem der zu entfernende Punkt zusammengeführt wird, in diese Liste eingetragen.
Neue Dreiecke	Vor die bereits bestehende Dreiecks-Liste werden nun die Dreiecke eingefügt, die bei "NeueDreieckeAnzahl" beachtet wurden.
Neuer Punkt	Der zu entfernende Punkt wird vor den bereits vorhandenen Punkten des Vertex Buffers eingefügt.

Am Ende dieses Durchlaufes werden alle noch vorhandenen Punkte vor den bereits vorhandenen Punkten in den Vertex Buffer eingefügt und auch die vorhandenen Dreiecke vor die berechnete Dreiecks-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 sphärisch 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 sphärisch 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]