VIPMs - Versionsgeschichte

Openglerf: Detailiert -> Detailliert

2012-03-21T14:06:16Z

Detailiert -> Detailliert

DGLBot: Der Ausdruck ''(.*?)'' wurde ersetzt mit ''$1''.

2009-03-10T18:16:20Z

Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.

Flo: Der Kategorie Anleitung zugeordnet

2005-09-23T08:25:42Z

Der Kategorie Anleitung zugeordnet

Flo am 23. September 2005 um 08:25 Uhr

2005-09-23T08:25:15Z

Lyr: /* Verberechnen der Daten */ in Vorberechnen

2005-05-30T14:31:33Z

‎Verberechnen der Daten: in Vorberechnen

Robert S: Rechtschreibung und Interpunktion

2005-05-30T12:05:09Z

Rechtschreibung und Interpunktion

Änderungen zeigen

134.109.4.78: /* Vertex Merge */

2005-05-30T11:43:59Z

‎Vertex Merge

134.109.4.78: /* Vertex Split */ C->Delphi

2005-05-30T11:42:24Z

‎Vertex Split: C->Delphi

2005-05-30T05:20:15Z

Neue Seite

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 [[LOD|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 [[LOD|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 [[LOD|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 [[LOD|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 [[LOD|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 [[LOD|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:
{|
|'''Datentyp'''
|'''Bezeichnung'''
|'''Beschreibung'''
|-
|Integer
|SplitVertex
|Der Index des Vertex von dem aus geteilt wird. In der 3ecksliste kann ausschließlich dieser Wert durch den Index des neuen 3ecks ersetzt werden (siehe Funktionsweise letzter Absatz).
|-
|Byte
|NeueDreieckeAnzahl
|Anzahl der 3ecke um die die 3ecksliste 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 3eck nicht 2 gleiche Werte beinhaltet, ist dies gleichbedeutend mit der Anzahl der 3ecke die geändert werden müssen.
|-
|Float
|Error
|Fehlerwert ab dem dieser Vertex hinzu kommen, oder wieder entfernt werden soll.
|-
|Integer[ÄnderungsAnzahl]
|ÄnderungsIndizes
|Dieser array beinhaltet die indizes auf die Positionen der 3ecksliste 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ä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 [[LOD|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 [[LOD|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 f < VSplit.ÄnderungsAnzahl
{
Integer TriangleEntry = VSplit.ÄnderungsIndizes[ f ];
VertexBuffer[ TriangleEntry ] = VertexBufferLänge;
}
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:
#Man berechnet sich für alle umliegenden Punkte eines Punktes die "durchschnittliche" Ebene (beispielsweise nach der Methode der kleinsten Quadrate nach Gauß).
#Man prüft für den jeweiligen Punkt die Entfernung zu dieser Ebene und nimmt diesen als Fehlerwert.
#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 3ecke 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 3ecke 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 3ecke auf die ein Änderungsindex zeigt sind noch nicht in der berechneten 3ecks-Liste vorhanden, müssen also zwischengespeichert werden. Erst wenn die 3ecke die bei "ÄnderungsAnzahl" beachtet wurden in die 3ecks-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 3ecks-Liste werden nun die 3ecke 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 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 [[LOD|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: [http://research.microsoft.com/~hoppe/ Hugues Hoppe]
*Ursprüngliche Publikation: [http://research.microsoft.com/~hoppe/pm.pdf]
*Wichtige Erweiterungen: [http://graphics.cs.uiuc.edu/~garland/papers/quadrics.pdf]

@@ Zeile 2: / Zeile 2: @@
 =Funktionsweise=
-VIPMs benötigen einge vorberechnete Daten. Anhand dieser Daten ist es sehr effizient möglich, den [[LOD|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.
+VIPMs benötigen einge vorberechnete Daten. Anhand dieser Daten ist es sehr effizient möglich, den [[LOD|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 [[LOD|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 [[LOD|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.

@@ Zeile 58: / Zeile 58: @@
 VSplit ist hier der Eintrag "Nächster_Split" der VertexSplit-Liste.
-<pascal> DreiecksListeLänge := DreiecksListeLänge + (VSplit.NeueDreieckeAnzahl * 3);
+<source lang="pascal"> DreiecksListeLänge := DreiecksListeLänge + (VSplit.NeueDreieckeAnzahl * 3);
   for f := 0 to VSplit.ÄnderungsAnzahl-1 do
   begin
@@ Zeile 65: / Zeile 65: @@
   end;
   VertexBufferLänge := VertexBufferLänge + 1;
-  Nächster_Split := Nächster_Split + 1;</pascal>
+  Nächster_Split := Nächster_Split + 1;</source>
 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.
@@ Zeile 77: / Zeile 77: @@
 VSplit ist hier der Eintrag "Nächster_Split - 1" der VertexSplit-Liste.
-<pascal> DreiecksListeLänge := DreiecksListeLänge - (VSplit.NeueDreieckeAnzahl * 3);
+<source lang="pascal"> DreiecksListeLänge := DreiecksListeLänge - (VSplit.NeueDreieckeAnzahl * 3);
   for f := 0 to VSplit.ÄnderungsAnzahl-1 do
   begin
@@ Zeile 84: / Zeile 84: @@
   end;
   VertexBufferLänge := VertexBufferLänge - 1;
-  Nächster_Split := Nächster_Split - 1;</pascal>
+  Nächster_Split := Nächster_Split - 1;</source>
 Die erste und die letzten beiden Zeilen machen nur den letzten Split rückgängig.

← Nächstältere Version		Version vom 23. September 2005, 08:25 Uhr
Zeile 143:		Zeile 143:
	*Wichtige Erweiterungen: [http://graphics.cs.uiuc.edu/~garland/papers/quadrics.pdf]		*Wichtige Erweiterungen: [http://graphics.cs.uiuc.edu/~garland/papers/quadrics.pdf]

−	[[Kategorie:Technik_oder_Algorithmus]]	+	[[Kategorie:Anleitung]] [[Kategorie:Technik_oder_Algorithmus]]

← Nächstältere Version		Version vom 23. September 2005, 08:25 Uhr
Zeile 142:		Zeile 142:
	*Ursprüngliche Publikation: [http://research.microsoft.com/~hoppe/pm.pdf]		*Ursprüngliche Publikation: [http://research.microsoft.com/~hoppe/pm.pdf]
	*Wichtige Erweiterungen: [http://graphics.cs.uiuc.edu/~garland/papers/quadrics.pdf]		*Wichtige Erweiterungen: [http://graphics.cs.uiuc.edu/~garland/papers/quadrics.pdf]
		+
		+	[[Kategorie:Technik_oder_Algorithmus]]

@@ Zeile 91: / Zeile 91: @@
 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.
-=Verberechnen der Daten=
+=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:
 #Man berechnet sich für alle umliegenden Punkte eines Punktes die "durchschnittliche" Ebene (beispielsweise nach der Methode der kleinsten Quadrate nach Gauß).

@@ Zeile 77: / Zeile 77: @@
 VSplit ist hier der Eintrag "Nächster_Split - 1" der VertexSplit-Liste.
- DreiecksListeLänge = DreiecksListeLänge - VSplit.NeueDreieckeAnzahl * 3;
+<pascal> DreiecksListeLänge := DreiecksListeLänge - (VSplit.NeueDreieckeAnzahl * 3);
-  for f = 0 to f < VSplit.ÄnderungsAnzahl
+  for f := 0 to VSplit.ÄnderungsAnzahl-1 do
+  begin
-   Integer TriangleEntry = VSplit.ÄnderungsIndizes[ f ];
+   TriangleEntry := VSplit.ÄnderungsIndizes[ f ];
-   VertexBuffer[ TriangleEntry ] = VSplit.SplitVertex;
+   VertexBuffer[ TriangleEntry ] := VSplit.SplitVertex;
+  end;
-  VertexBufferLänge = VertexBufferLänge - 1;
+  VertexBufferLänge := VertexBufferLänge - 1;
-  Nächster_Split = Nächster_Split - 1;
+  Nächster_Split := Nächster_Split - 1;</pascal>
 Die erste und die letzten beiden Zeilen machen nur den letzten Split rückgängig.