Diese Arbeit stellt ein neues Verfahren zur Darstellung von volumenbasierten Daten mit LOD-Mechanismus vor. Das angedachte Einsatzgebiet ist Terrain. Da die anvisieren Frameworks und Anwendungen Dreiecke verarbeiten (mittels OpenGL oder Direct3D), ist eine indirekte Darstellung der Volumendaten nötig, die mittels eines Polygonnetzes die Informationen approximiert. Eine direkte Darstellung würde auf die Umwandlung in Dreiecke verzichten und z.B. mit einem Raytracer ohne Umweg zeichnen. Dabei werden verschiedene, vorhandene Algorithmen wie Dual Marching Cubes (DMC) und triplanare Texturierung eingesetzt. Das LOD-Verfahren ist von "Chunked Level of Detail Control" inspiriert und überträgt dessen Strategie von auf Höhenfeld basierten auf volumenbasierte Terrains. Die dort zur Schließung von Lücken verwendeten "Skirts2 werden hier mittels Marching Squares adaptiert.
Inhaltsverzeichnis
Abbildungsverzeichnis
Formelverzeichnis
Abkürzungsverzeichnis
Glossar
Quellcodeverzeichnis
1. Einleitung
1.1. Problemstellung
1.2. Vorgehensweise
2. Volumenmodell
3. Zusammenhüngende Entwicklung
3.1. Isosurface Generierung
3.2. Material
3.3. Hohenfeld basiertes Terrain
3.4. Volumenbasiertes Terrain
4. Dichtefunktion
4.1. 3D Texturen
4.2. Constructive Solid Geometry
4.2.1. Grundformen
4.2.2. Operatoren
4.2.3. Ein Constructive Solid Geometry Baum
5. Verfahren der Volumendarstellung
5.1. Dual Marching Cubes
5.1.1. Generierung des Octrees
5.1.2. Isolierung von Features
5.1.3. Bilden des Dualgitters
5.1.4. Konturierung des Dualgitters
5.2. Marching Squares Skirts
5.3. Material
5.3.1. Triplanare Texturierung
5.3.2. Normal Mapping
5.3.3. Beleuchtung
5.3.4. Nebel
5.4. Level of Detail
5.4.1. Aufbau des Chunkbaums
5.4.2. Chunkauswahl beim Zeichnen
6. OGRE
6.1. Google Summer of Code 2012
6.2. Wichtige Klassen fur das Projekt
7. Softwarearchitektur
7.1. Aufbau des Chunkbaums
7.2. Auswahl der Chunks beim Zeichnen
7.3. Weitere Funktionen
8. Implementierung
8.1. Dichtefunktion
8.2. Chunkbaum
8.3. Material
8.4. Chunkauswahl beim Zeichnen
9. Abschlussbetrachtung
9.1. Leistungsfahigkeit
9.1.1. Ladezeit
9.1.2. Laufzeit
9.2. Ergebnis des Google Summer of Code 2012
9.3. Zukiinftige Entwicklung
9.3.1. Entwicklung eines grafischen Editors
9.3.2. Paging
9.3.3. Constructive Solid Geometry
9.3.3.1. CSGXML
9.3.3.2. Rauschfunktion
9.3.3.3. Verbesserte CSG Operatoren
9.3.3.4. Matrix CSG
9.3.3.5. Weitere Grundformen
9.3.4. Schnitt mit Strahlen und den generierten Dreiecken . . .
9.3.5. Material
9.3.5.1. Mehrere Textursets bei der triplanaren Texturierung
9.3.5.2. Ambient Occlusion
9.3.5.3. Parallax Occlusion Mapping
9.3.6. Verbesserung des Polygonnetzes
9.3.6.1. Implementierung von Marching Cubes 33 ...
9.3.6.2. Extraktion von scharfen Kanten
9.3.6.3. Verbesserung der LOD-Wechsel
9.3.6.4. Reduzierung der Anzahl kleiner Dreiecke ...
9.4. Fazit
Literaturverzeichnis
Einsatz der Volumen-Komponente
Zusammenfassung und Abstract
Zusammenfassung
Außenszenarien in der Computergrafik beinhalten oft die Darstellung von weitflächigem Terrain. Volumenbasiertes Terrain ist eine flexible Methode, die Überhange, Kliffe oder Hohlen ermöglicht. Die Echtzeitdarstellung benötigt dabei hochste Effizienz.
Die vorliegende Arbeit beschreibt ein neues Verfahren zur Darstellung volumenbasierter Daten mit einem Level of Detail Mechanismus und Terrain als Hauptanwendung. Dabei wird dargestellt, woher die Daten stammen, wie aus ihnen ein Polygonnetz gebildet wird, wie die Dreiecke eine Textur und Relief erhalten und wie mittels des Level of Detail Algorithmus der Detailgrad der Darstellung je nach Entfernung zum Betrachter variiert.
Die Quelle der Daten sind zwei Verfahren. Constructive Solid Geometry baut einen Baum aus Grundformen wie Kugeln und Ebenen sowie Operationen wie Vereinigung und Schnitt auf. 3D Texturen, die aus einem externen Editor stammen, konnen verarbeitet werden.
Durch eine Kombination aus Dual Marching Cubes und Marching Squares Skirts werden Polygonnetze aus den Volumendaten generiert und mittels triplanarer Texturierung mit einem passenden Material versehen.
Zur Darstellung des Volumens werden viele separate Polygonnetzen mehrerer Detailstufen erzeugt und in einer Baumstruktur organisiert. Je nach Entfernung zum Betrachter werden aus diesen „Chunks" die passenden ausgewählt. Dieser Level of Detail Algorithmus sorgt dafür, dass auch große Volumendaten mit flussiger Bildrate darstellbar sind.
Abstract
Outdoor scenes in the field of computer graphics often contain the rendering of large terrains. Volume based terrain is a flexible solution allowing overhangs, cliffs or caves. It is important for real-time rendering, that this solution is as efficient as possible.
This work describes a novel method for rendering volume based data with a level of detail mechanism with terrain as the main application. Areas covered will include: where the data comes from, how a mesh is generated, how the triangles get their texture and relief, and finally how the amount of detail varies over the distance with the level of detail algorithm.
The source of the data consists of two methods. Constructive solid geometry builds up a tree made of basic shapes like spheres or planes as well as operators like union and intersection. 3D textures coming from an external editor can be processed.
With the use of Dual Marching Cubes and Marching Squares Skirts, meshes from the volume data are generated and with triplanar texturing, they get a fitting material.
For the rendering of the volume, many separate meshes with different levels of detail are created and organized in a tree structure. Depending on the distance to the viewer, the matching „chunks" amongst them are chosen. This level of detail algorithm takes care of displaying huge volumes within a fluent frame-rate.
Abbildungsverzeichnis
2.1. Visualisierung eines 2D Kreisvolumens
4.1. die Eckpunkte eines Kubus zur trilinearen Interpolation
4.2. die CSG Grundformen dieses Projektes
4.3. die CSG Operatoren dieses Projektes außer der Skalierung ...
4.4. ein CSG-Baum
5.1. Visualisierung eines Octrees mit Baumstruktur
5.2. die Nummerierung der Kinder eines Octree-Knotens
5.3. ein Octree-Knoten mit seinen Kindern und allen Eckpunkten . .
5.4. der eindimensionale Fall der Fehlerberechnung zwischen Interpolation und Funktion, nach [ZBS05, S. 16]
5.5. der Octree einer Kugel mit Zentrum im Ursprung des abgetasteten Volumens
5.6. uberschneidende Dreiecke mit geanderter Eckpunktreihenfolge bei Dual Marching Cubes nach [MS10, S. 2]
5.7. das grüne Dualgitter gebildet aus dem schwarzen Quadtrees nach SCHAEFER[SW04, S. 3]
5.8. die Aufrufe der Unterfunktionen von nodeProc(n)
5.9. die Aufrufe der Unterfunktionen von faceProcXY(n0, n1)
5.10. die Aufrufe der Unterfunktionen von edgeProcX(n0, n1, n2, n3) .
5.11. der Aufruf von vertProc(n0, n1, n2, n3, n4, n5, n6, n7) von sich selbst
5.12. ein Dualgitter zu einem Octree ohne Randzellen
5.13. ein Dualgitter zu einem Octree mit Randzellen
5.14. das adaptive Dualgitter zu einem Octree
5.15. links: zwei triangulierte Kuben mit Löchern, rechts: zwei trian- gulierte Kuben ohne Löcher nach [Hom10, S. 15]
5.16. links: Lücken, die durch aneinanderliegende Polygonnetze gebildet durch Octrees unterschiedlicher Auflösung, entstehen, rechts: die Lücken sind gefüllt mit Marching Squares Skirts ...
5.17. Marching Squares Skirts am Rand einer Viertelkugel
5.18. die 16 möglichen Marching Squares Falle
5.19. Texturierung mittels planarer Projektion
5.20. links: Marching Squares Skirts mit regulärer triplanare Texturkoordinaten, rechts: mit aufaddierter Länge der Normale
5.21. Triplanare Texturierung
5.22. links: triplanare Texturierung, rechts: triplanare Texturierung mit Normal Mapping
5.23. Beleuchtung durch eine gerichtete, weiße Lichtquelle und ein rotes Spotlight
5.24. eine Schlucht im quadratisch exponentiellen Nebel
5.25. der Chunkbaum einer Kugel mit drei LOD-Stufen
5.26. Kameraoffnungswinkel a und Bildbereichshohe h beim Kameraabstand D
6.1. OGREs Logo
6.2. GSoC Logo
7.1. Klassendiagramm von der OGRE Volumen Komponente
9.1. Schluchtlandschaft
9.2. die Kamerapositionen zur Laufzeitmessungen
Formelverzeichnis
1. Dichtefunktion eines 2D Kreisvolumens
2. Gradientenfunktion eines 2D Kreisvolumens
3. Umrechnung der Koordinate vom Weltraum in den Texturraum
4. Nearest Neighbor Interpolation der Texturkoordinate nach [To05,
S. 112 - 113]
5. trilineare Interpolation eines Punktes mit den acht gegebenen Eckpunkten nach [Bou99]
6. Berechnung des Gradienten an einer Koordinate nach [LC87, S. 3]
7. Berechnung des Gradienten an einer Koordinate mit Sobel-Filter
8. Dichtefunktion der Kugel
9. Gradientenfunktion der Kugel
10. Dichtefunktion der Ebene
11. CSG-Operatoren auf den Dichtewerten
12. angepasste CSG-Operatoren auf den Dichtewerten
13. Skalierungsoperation in einem CSG-Baum
14. der approximierte geometrische Fehler einer Octree-Zelle nach [ZBS05, S. 17]
15. die Mindestdistanz, innerhalb der beim letzten Marching Squares Fall Dreiecke gebildet werden
16. Bildung der Uberblendungsfaktoren bei der triplanaren Texturierung
17. Normalisierung der Uberblendungsfaktoren bei der triplana- ren Texturierung
18. Bildung der Fragmentfarbe durch Überblendung dreier planarer Projektionen
19. Bildung der drei Texturkoordinaten der planaren Projektionen .
20. Umrechnung einer RGB-Texturfarbe in eine Normale
21. Berechnung der Normal Mapping Normale durch Uberblendung dreier planarer Projektionen
22. Transformation vom Objektraum in den Texturraum
23. Bildung der Bitangente
24. Berechnung der Tangente
25. die Verechnung der Beleuchtungsanteile zur totalen Fragmentfarbe
26. der diffuse Lichtanteil
27. der Halbvektor
28. der spekulare Lichtanteil
29. die Abschwachung der Beleuchtung mit steigender Entfernung zur Lichtquelle
30. der Spotlight-Faktor
31. das Einbeziehen von Nebel in die Pixelfarbe
32. linearer Nebelfaktor
33. exponentieller Nebelfaktor
34. quadratisch exponentieller Nebelfaktor
35. Berechnung des geometrischen Fehlers eines LOD-Levels
36. Berechnung des Screen-Space-Fehlers eines Chunks
37. Verhaltnis vom geometrischen Fehler und Bildbereichshohe bei einem bestimmten Kameraabstand zu Screen-Space-Fehler und Höhe des Zeichenfensters
38. Berechnung der Bildbereichshöhe bei gegebenen Abstand D und Kameraöffnungswinkel a
Abkurzungsverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
Glossar
Isosurface Gegeben sei ein skalares Feld F(P) mit F als Funktion in R[3]. Die Oberfläche, die F(P) = c erfüllt, wird als Isosurface mit dem Isowert c bezeichnet [NY06, S. 1].
Normal Mapping Eine Technik zur Relief-Bildung, bei der eine NormalenTextur Normalen-Vektoren beinhaltet, die Normale fiir jedes Pixel modifiziert [NFHS11, S. 339].
Octree Ein Baum, dessen Wurzelknoten einen weltumschließenden Kubus bildet und dessen acht Kinder den Vaterknoten in Oktanten unterteilt. Die Unterteilung endet jeweils in einem Zweig nach einer bestimmten Heuristik [DeL00, S. 439].
Polygonnetz Ein Polygonnetz ist „eine Menge verbundener konvexer und planarer Polygone (Dreiecke, Vierecke)" [OM04, S. 128].
Screen-Space-Fehler Der Screen-Space-Fehler ist die (geschatzte) Differenz in Pixeln zwischen dem gezeichneten Original-Modell und dem vereinfachten des LOD-Mechanismus [Lue02, S. 54].
Quellcodeverzeichnis
5.1. Pseudocode von nodeProc(n)
5.2. Pseudocode von faceProcXY(n0, n1)
5.3. Pseudocode von edgeProcX(n0, n1, n2, n3)
5.4. Pseudocode von vertProc(n0, n1, n2, n3, n4, n5, n6, n7)
5.5. Pseudocode der Behandlung der Randzellen der hinteren Außenebene in createBorderCells(n0, n1, n2, n3, n4, n5, n6, n7)
5.6. Pseudocode der Behandlung der Randzellen der oberen Außenebene in createBorderCells(n0, n1, n2, n3, n4, n5, n6, n7)
5.7. Pseudocode der rekursiven Generierung des Chunkbaums ...
5.8. Pseudocode der Chunkauswahl abhangig von der Kamera ...
9.1. ein CSGXML-Baum
B.1. inkludieren der benötigten Header-Dateien
B.2. Laden eines Volumens anhand einer Konfigurationsdatei
B.3. Laden eines kleinen CSG-Baumes als Volumen
1. Einleitung
Die Darstellung von Terrain hat viele Anwendungen. Sie wird von nahezu allen Computerspielen mit Außenszenarien benötigt, sei es ein Flugsimulator, ein Rennspiel oder ein Ego-Shooter. Dabei ist es essentiell wichtig, ein effizientes Verfahren zu verwenden, um eine flüssige Bildrate zu ermoglichen.
Ein klassischer Ansatz ist die Verwendung von Hohenfeldern. Hierffir werden Graustufenbilder genommen, deren Breite und Hohe die skalierte Breite und Tiefe des Terrains darstellen. Der Grauwert der einzelnen Pixel bestimmt die Hohe an ihren Koordinaten. Mit Hilfe dieser Informationen wird ein Polygonnetz generiert. Ein Polygonnetz ist „eine Menge verbundener konvexer und planarer Polygone (Dreiecke, Vierecke)" [OM04, S. 128]. Da das benotigte Terrain mit unzahligen Dreiecken sehr großwerden kann, ist ein Level of Detail (LOD) Mechanismus notig. Dieser sorgt dafiir, dass weiter vom Betrachter entfernte Ausschnitte des Terrains weniger detailliert sind, d.h. weniger Dreiecke verwenden. Ein Algorithmus, der mit Hohenfeldern arbeitet ist z.B. „Chunked Level of Detail Control" von ULRICH [Ulr02].
Auf Hohenfeldern basierte Terrains haben einen gravierenden Nachteil. Die Daten variieren nur in Y-Richtung. Somit sind keine Uberhange, Kliffe oder Hohlen moglich.
Hier kommen volumenbasierte Modelle ins Spiel. Mit ihnen sind fast beliebige Strukturen moglich. Sollen mit ihnen Terrains dargestellt werden, ist auch hier ein LOD Mechanismus notig. Volumenbasiertes Terrain ist zum Zeitpunkt dieser Arbeit noch eine junge Disziplin. Aus diesem Grunde gibt es vergleichsweise wenig komplette Methoden. Einer ist z.B. der Transvoxel Algorithmus von LENGYEL [Len10].
Diese Arbeit stellt ein neues Verfahren zur Darstellung von volumenbasierten Daten mit LOD-Mechanismus vor. Das angedachte Einsatzgebiet ist Ter- rain. Da die anvisieren Frameworks und Anwendungen Dreiecke verarbeiten (mittels OpenGL oder Direct3D), ist eine indirekte Darstellung der Volumendaten nötig, die mittels eines Polygonnetzes die Informationen approximiert. Eine direkte Darstellung wurde auf die Umwandlung in Dreiecke verzichten und z.B. mit einem Raytracer ohne Umweg zeichnen [NY06, S. 1]. Dabei werden verschiedene, vorhandene Algorithmen wie Dual Marching Cubes (DMC) und triplanare Texturierung eingesetzt. Das LOD-Verfahren ist von „Chunked Level of Detail Control" inspiriert und übertragt dessen Strategie von auf Hohenfeld basierten auf volumenbasierte Terrains. Die dort zur Schließung von Lücken verwendeten „Skirts" werden hier mittels Marching Squares adaptiert.
1.1. Problemstellung
Bei einem Verfahren zur Darstellung von Volumendaten mit LOD sind mehrere Unterprobleme zu losen, die hier kurz beschrieben werden.
Dichtefunktion: Diese Funktion modelliert die Szene. Sie kann zur Laufzeit generiert oder vorher in einem Editor erstellt werden. Eine Mischung aus beidem ist auch denkbar.
Erstellung des Polygonnetzes: Aus den Volumendaten müssen Dreiecke gebildet werden. Einerseits sollen sie das Volumen möglichst gut abbilden, andererseits soll ihre Anzahl in Grenzen gehalten werden.
Material: Zur realistischen Darstellung des Polygonnetzes ist ein entsprechendes Material erforderlich. Es bestimmt, ob das Polygonnetz wie Rasen oder wie Wüstensand aussieht. Dabei kann je nach Steigung überblendet werden, so dass z.B. oben auf dem steinigen Kliff Gras wachst. Das Material beinhaltet die Textur, Normal Mapping und weiteres.
LOD: Vom Betrachter weit entfernte Gebiete sind detailarmer darzustellen als die direkter Umgebung. Das ist deshalb notig, da heutige Computer und Verfahren zur Darstellung von Polygonnetzen noch nicht leis- tungsfahig genug sind, um darauf verzichten zu können.
Jedes dieser Probleme ist separat zu betrachten und kann unterschiedlich gelöst werden, ohne dass es ein anderes beeinflusst.
1.2. Vorgehensweise
Zuerst wird das Kernkonzept der volumetrischen Modellierung beschrieben und dann ein Blick auf die zusammenhängende Entwicklung geworfen. Sie besteht aus den Themengebieten der Isosurface Generierung, des Materials, des Hohenfeld basierten und volumetrischen Terrain.
Bei der Dichtefunktion werden die zwei implementierten Möglichkeiten gezeigt, sie zu definieren. Um Daten „von Außen" (z.B. aus einem Editor) darstellen zu konnen, sind 3D Texturen wegen ihrer Einfachheit ein praktisches Format, da sie zu jeder diskreten Koordinate einen Wert definieren. In diesem Fall stellt er die Dichte dar. Constructive Solid Geometry (CSG) ist mit Volumendaten einfach umzusetzen und hat viele Anwendungen. Einige Grundformen wie Kugeln, Ebenen und Kuben konnen mittels CSG mit Mengenoperationen (Vereinigung, Schnitt, Differenz,...) in einem Binarbaum kombiniert werden [OM04, S. 157-158].
Das nachste Kapitel zeigt das entwickelte Verfahren zur Volumendarstellung. Anhand der Dichtefunktion werden mittels DMC Polygonnetze gebildet. Auftretende Lucken zwischen den Polygonnetzen schließen sich durch einer Variante von Marching Squares. Die Dreiecke bekommen anschließend ein Material zugewiesen. Aus einzelnen Polygonnetzen wird nun ein Baum beim LOD Verfahren gebildet, aus dem abhangig von der Kameraposition die zu zeichnenden Teile ausgewahlt werden.
Es folgt eine Betrachtung der zur Implementierung ausgewahlten Bibliothek Object-Oriented Graphics Rendering Engine (OGRE)[1]. Das Projekt wurde im Google Summer of Code (GSoC) entwickelt und ist mittlerweile Bestandteil von OGRE.
Anschließend werden die Softwarearchitektur und die Implementierungsdetails erörtert.
Mit der Abschlussbetrachtung wird die Arbeit vollendet. Sie evaluiert die Leistung des Systems und geht auf das Ergebnis des GSoCs ein. Das Kapitel endet mit der zukünftigen Entwicklung und dem Fazit.
2. Volumenmodell
SCHAEFER beschreibt das Volumenmodell als eine Dichtefunktion f (x, y, z), deren Ergebnis die Dichte bzw. die Distanz zur Oberflache des Modells bezeichnet. Die Oberflache wird extrahiert, indem die Funktion fUr eine gegebene Dichte c ausgewertet wird, f (x, y, z) = c.
Durch diese Form der Modellierung wird z.B. CSG einfach, da nur die Funktion f (x, y, z) modifiziert werden muss [SW04, S. 1].
c wird auch als Isowert bezeichnet. Die Oberflache der Funktion bei c heißt Isosurface [NY06, S. 1]. Üblicherweise wird ein Isowert von 0 gewahlt. Somit sind negative Dichten außerhalb und positive innerhalb des Modells.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.1.: Visualisierung eines 2D Kreisvolumens
Abbildung 2.1 zeigt ein zweidimensionales Volumen eines Kreises der Formel 1 mit Mittelpunkt (xc, yc) und Radius r.
Abbildung in dieser Leseprobe nicht enthalten
Formel 1: Dichtefunktion eines 2D Kreisvolumens
Weißkennzeichnet den höchst möglichen Dichtewert von r an der Position der roten Markierung. Bei der grünen Markierung ist der Isowert der Funktion gleich 0, ein mittleres Grau in der Darstellung. Alle Orte mit einem Isowert von 0 sind außerdem grün eingezeichnet, womit ein Kreis entsteht. Das Abbilden dieses Isosurfaces mittels eines Polygonnetzes wird als „Konturierung" bezeichnet [Hom10, S. 6]. Zuletzt ist die Dichtefunktion bei der blauen Markierung gleich — r.
Neben dem Dichtewert ist noch der Gradient an der gegebenen Koordinate wichtig. Er wird für die Bildung eines Octrees und für die Beleuchtung benotigt. Beim Gradienten handelt es sich um einen Vektor, dessen Komponenten aus den partiellen Ableitungen der Dichtefunktion bestehen. Somit steht der Vektor senkrecht auf Oberflache der Dichtefunktion. Die Lange beschreibt die Starke der Veränderung der Funktion an der gegebenen Stelle [Wei]. Die Gradientenfunktion des 2D Kreisvolumens ist in Formel 2 gezeigt.
Abbildung in dieser Leseprobe nicht enthalten
Formel 2: Gradientenfunktion eines 2D Kreisvolumens
3. Zusammenhängende Entwicklung
Dieser Abschnitt beschreibt die bisherige, mit dem Projekt zusammenhängende Entwicklung. Zuerst werden die drei Teilaspekte der Generierung des Isosurfaces und des Materials betrachtet. Danach werden auf Hohenfeld basierende Terrains beschrieben sowie die kompletten, vergleichbaren Lösungen der volumenbasierten Terrains. Auch werden beim ersten Auftreten noch einige grundlegende Begriffe erlautert.
3.1. Isosurface Generierung
LORENSEN und CLINE haben 1987 Marching Cubes eingeführt, ein Algorithmus zur Generierung des Isosurfaces, der das Volumen in Kuben unterteilt und jeden für sich verarbeitet. Dabei werden die Eckpunkte analysiert und mit der Information, ob sie sich innerhalb oder außerhalb des Volumens befinden, wird aus einer Tabelle die Triangulation ausgewahlt und die endgültige Position der Eckpunkte linear interpoliert. Durch Ausnutzen von Symmetrien hat diese Tabelle 15 Eintrage [LC87].
Marching Cubes hat jedoch einige Schwachen. Es gibt bei einigen Konfigurationen der Eckpunkte mehrere, gültige Triangulationsmöglichkeiten, die bei aneinanderliegenden Kuben zu Lochern führen. Diese lassen sich beheben, indem die Symmetrie des Negierens der Eckpunktkonfiguration weggelassen wird [Nie03, S. 9].
Ein weiteres Problem ist die innere Mehrdeutigkeit, bei der zwar keine Locher entstehen, aber unterschiedliche Geometrien moglich sind. In manchen Fallen kann nicht entschieden werden, ob sich in einem Kubus separierte oder vereinte Geometrie befindet. Sind z.B. nur zwei Eckpunkte im Volumen, die Diagonal Uber den Kubus gehen, können entweder zwei „Kappen" entstehen oder eine Art Schlauch quer durch den Kubus. Die Dichtefunktion einer Konfiguration mit internen Mehrdeutigkeiten stellt in der Ebene der sich im Volumen befindlichen Eckpunkte eine Hyperbel dar. Je nachdem, wie sie liegt, kann auf die Topologie der Dichtefunktion geschlossen und in einer erweiterten Tabelle die korrekte Triangulation nachgeschlagen werden [Che95]. LEWINER et al stellten hierfür eine effiziente Implementierung vom Algorithmus Marching Cubes 33 mit Tabellen ffir alle Konfigurationen zur Verffigung [LLVT03].
Marching Tetrahedra funktioniert wie Marching Cubes, mit dem Unterschied, dass die Kuben in sechs Tetraheden unterteilt und jede ffir sich kon- turiert werden. Dadurch, dass ein Tetrahedra nur vier Ecken hat, reduziert sich die Falltabelle durch Ausnutzen der Symmetrien auf drei Eintrage. Diese Methode ist vorteilhaft, weil keine Mehrdeutigkeiten wie bei Marching Cubes entstehen. Allerdings werden weitaus mehr Dreiecke generiert [CSK96].
„Dual Contouring" von TAO et al loste das Problem der abgerundeten Kanten von Marching Cubes. Dabei wird die Geometrie nicht aus vorgefertigten Schablonen einer Tabelle erstellt. Stattdessen wird ffir jede das Volumen schneidende Kubuskante aus einer Reihe von Testpunkten mit ihren Normalen mittels des Verfahrens der kleinsten Quadrate ein repräsentativer Punkt berechnet. Nach der Iteration uber die Kuben werden mit der erstellten Punkteliste direkt die Dreiecke erzeugt. Es ist auch moglich, vorher mittels einer Metrik einen Octree zu erstellen, der sich in einem gewissen Rahmen dem Detailgrad des Volumens anpasst und somit die Anzahl der erstellten Dreiecke kontrolliert. Diese Metrik ist der Berechnung der repräsentativen Punkte ahnlich [JLSW02].
SCHAEFER stellte spater fest, dass immer noch unnotig viele Dreiecke generiert werden, weil der Detailgrad von der Dicke des Volumens abhangt. Je dfinner das Volumen an der betreffenden Stelle ist, je feiner wird auch der Octree unterteilt [SW04, S. 2]. MANSON beschrieb Situationen, bei Dual Contouring, in denen das Polygonnetz nicht mannigfaltig ist. Es konnen Eckpunkte entstehen, die sich mehr als einen Abschnitt des Polygonnetzes teilen. Ein bildliches Beispiel sind zwei Pyramiden, deren zwei Spitzen auf nur einem Punkt liegen [MS10, S. 2].
HOMLID erklärt Mannigfaltigkeit als mathematisches Konzept. In diesem Fall handelt es sich um eine 2-Mannigfaltigkeit, da der Raum dreidimensional ist. Bei ihr ist die Nachbarschaft jedes Punktes der Oberflache homoomorph zu einer Scheibe. Mit Nachbarschaft ist die direkte Umgebung des Punktes gemeint. Homoomorph zwischen zwei Formen heißt, dass eine Form durch dehnen und biegen in die andere uberfuhrt werden kann. Zerreißen ist allerdings nicht erlaubt. Wenn das möglich ist, sind die Formen topologisch aquivalent. Als Konsequenz darf der Schnitt zweier Dreiecke eines Polygonnetzes nur leer, ein Eckpunkt, eine Kante oder die Dreiecksflache sein. Überlappende Dreiecke sind demzufolge nicht erlaubt, genauso wie Locher in der Oberflache [Hom10, S. 11].
Marching Cubes produziert durch das uniforme Gitter, über das die Kuben laufen, sehr viele Dreiecke. Dabei wird nicht beachtet, dass ebene Bereiche des Volumens mit weniger Dreiecken auskommen würden. Aneinanderliegende Kuben unterschiedlicher Auflosung produzieren Lücken. Eine hierarchische Struktur wie ein Octree lasst sich also nicht direkt anwenden. SCHAEFER entwarf eine vom Octree abgeleitete Datenstruktur namens Dualgitter, die das moglich macht. Durch die Isolierung von Features, die die Dualgitterpunkte definieren, werden scharfe Kanten abgebildet [SW04].
KAZHDAN et al benutzten einen Octree, um von ihm einen „Edgetree" abzuleiten. Diese Datenstruktur bewirkt, dass Lücken in der Triangulierung benachbarter Zellen durch die Auswahl der Kanten der hoher aufgelosten Seite geschlossen werden. Damit ist das Ziel einer adaptiven Triangulierung erreicht, die sich dem Detailgrad des Volumens anpasst [KKDH07]. MANSON und SCHAEFER haben erkannt, dass sich die Eckpunkte des resultierenden Polygonnetzes nur auf den Kanten des Octrees bewegen konnen. Dadurch konnen scharfe Rander und dünne Details nicht abgebildet werden [MS10, S. 3].
MANSON und SCHAEFER entwickelten eine Methode, vom Octree extrahierte Simplexe mit Marching Tetrahedra zu konturieren und scharfe Kanten zu erhalten. Im Paper selbst ist dabei schon ersichtlich, dass diese Methode vergleichsweise langsam ist [MS10].
HO et al haben mit Cubical Marching Squares eine Methode entwickelt, die auf den einzelnen Flachen des Kubus jeweils das zweidimensionale Marching Squares ausfuhrt und aus diesen Daten eine dreidimensionale Triangulierung produziert. Auch hier wird ein Octree verwendet, um eine dem Detailgrad entsprechende Dreiecksanzahl zu erreichen. Zuerst werden Segmente aller Flachen der Octree-Blatter mittels Marching Squares extrahiert. Die Mehrdeutigkeiten losen sich über Probenormalen. Scharfe Features werden in diesem Abschnitt auch anhand dieser Normalen markiert. Die gesammelten, zusammenhangenden Segmente verbinden sich zu Komponenten. Die exakten Punkte der scharfen Features werden durch Probepunkte und ihre Normalen gefunden, anhand derer ein Gleichungssystem aufgestellt und gelost wird. Anschließend werden die Punkte der Komponenten trianguliert. Durch interne Mehrdeutigkeiten können Komponenten überlappen. Diese werden über einen nicht naher spezifizierten Algorithmus aus der dynamischen Programmierung verbunden und erst dann trianguliert [HWC+05]. Diese Methode unterscheidet sich erheblich von den vorhergegangenen und beinhaltet komplizierte Schritte, z.B. die Vereinigung überlappender Komponenten.
3.2. Material
Eine einfache planare Texturprojektion reicht bei Polygonnetzen von Volumenmodellen nicht aus, weil sie zu großen Verzerrungen führt. GEISS erweiterte die planare Projektion auf drei von den Hauptachsen des Koordinatensystems kommende und wahlt diejenige aus, die die geringste Verzerrung bietet. In den Zwischenbereichen der Geometrie werden die Projektionen überblendet. Mit der gleichen Technik wird auch Normal Mapping umgesetzt [Gei07]. Diese triplanare Texturierung wurde von LENGYEL um einige Kontrollparameter erweitert. Außerdem entfernt er eine ungewollte Spiegelung [Len10, S. 46 - 51].
Eine Alternative ist das „Indirection Mapping" von MCGUIRE und WHITSON. Ein komplizierter Praprozess erstellt mittels einer Federsimulation eine „Indirection Map". Eine einzelne planare Projektion bildet Texturkoordinaten. Mit ihnen wird ein Vektor in der Indirection Map nachgeschlagen und auf die Texturkoordinaten aufaddiert [MW08].
3.3. Höhenfeld basiertes Terrain
Beim auf Hohenfeld basierten Terrain wird x und z vorgegeben. y ergibt sich aus dem Hohenfeld selbst. Somit variiert nur y, was Überhange, Hohlen und ahnliches verhindert. Weil sich die in dieser Arbeit entwickelte Technik hauptsachlich auf Terrains bezieht, wird dieser klassische Ansatz kurz prasentiert.
Eine altere Methode zur Triangulierung von Hohenfeld basiertem Terrain ist ROAMing von DUCHAINE AU et al. Dabei wird das Polygonnetz abhangig von der Kameraposition, Blickrichtung und einem akzeptierten Fehler vereinfacht. Damit wird auch gleichzeitig ein Nachteil deutlich. Bei jederÄnderung der Kamera müssen die Dreiecke neu berechnet und an die Grafikkarte geschickt werden. Ein großer Vorteil vom ROAMing besteht darin, dass bei der Reduzierung der Dreiecke auf die Topologie geachtet wird. Dadurch werden große Detailunterschiede im Hohenfeld beibehalten, was das plötzliche Auftauchen von Details mindert [DWS+97].
ULRICH hat bei „Chunked Level of Detail Control" einen Quadtree aufgebaut, dessen Wurzel das ganze Terrain in der niedrigsten Detailstufe beinhaltet. Die vier Kinder enthalten jeweils ein Viertel des Terrains ihres Vaters in höherem Detailgrad. Jede Ebene des Baumes umfasst somit das komplette Terrain. Abhangig von der Kameraposition wird der Baum traversiert und der Screen-Space-Fehler pro aktuellem Kind berechnet [Ulr02].
Als Screen-Space-Fehler wird die (geschatzte) Differenz in Pixeln bezeichnet zwischen dem gezeichneten Original-Modell und dem vereinfachten des LOD-Mechanismus [Lue02, S. 54].
Ist der Screen-Space-Fehler bei „Chunked Level of Detail Control" dieser kleiner oder gleich eines akzeptierten Screen-Space-Fehlers, wird der aktuelle Knoten gezeichnet und die Traversierung stoppt an dieser Stelle. Bei der Triangulierung verwendet ULRICH eine dem ROAMing sehr ahnliche Technik, die aber naturgemaßkeine Abhangigkeit zur Kamera beinhaltet. Da Knoten unterschiedlicher Auflösung nebeneinander liegen können, entstehen Lücken im Polygonnetz. „Skirts" verbergen diese. Dafür wird an den Knotengrenzen senkrecht nach unten das Polygonnetz weitergeführt [Ulr02].
„Geometry Clipmaps" von LOSASSO und HOPPE bauen mit einem simpleren Schema das Polygonnetz auf. In der höchsten LOD-Stufe erzeugt jeder Punkt des Höhenfeldes einen Eckpunkt, bei der nachsten LOD-Stufe nur noch jeder zweite und so weiter. Da dieses Schema sehr einfach ist, kann die Geometrie zur Laufzeit erzeugt werden. Damit keine Lücken zwischen den Bereichen der unterschiedlichen LOD-Stufen entstehen, werden die RandEckpunkte der höher aufgelosten Detailstufe auf die Hohe der Kanten der angrenzenden, niedriger aufgelösten Detailstufe platziert [LH04].
Spater haben ASIRVATHAM und HOPPE im Kapitel „Terrain Rendering Using GPU-Based Geometry Clipmaps" des Buches „GPU Gems 2" gezeigt, dass Geometry Clipmaps auch fast vollstandig auf der Grafikkarte berechnet werden können, was den teuren Transport von Daten vom Hauptspeicher zum Grafikspeicher minimiert [PFS05, S. 27 - 45].
OGREs Höhenfeld-Terrainsystem benutzt ein ahnliches Verfahren zur Erzeugung des Polygonnetzes. Ein Unterschied ist die Verwendung von Skirts zur Vermeidung von Lücken zwischen angrenzenden, unterschiedlichen Detailstufen. Das reduziert dieÄnderung von Indizes der Polygonnetze beim Wechsel der LOD-Stufen. Die Verwendung von Skirts ermöglicht es, weit entfernte Bereiche nicht im Speicher zu halten und erst beim Naherkommen zu laden. Bereiche, die wieder weit genug entfernt sind, werden aus dem Speicher entfernt. Durch die Skirts müssen die einzelnen Teilbereiche keine Kenntnisse über ihre Nachbarn mitbringen [OT12].
3.4. Volumenbasiertes Terrain
David Williams und Matt Williams haben die Bibliothek „Polyvox" unter der zlib-Lizenz [1] veröffentlicht. Bei der Darstellung der Volumendaten werden zwei Optionen angeboten. Zum einen kann die Oberflache mit ein- zelnen Kuben gezeichnet werden und bekommt so ein blockhaftes Aussehen, zum anderen kann Marching Cubes angewendet werden. Ein richtiger LODMechanismus ist nicht in der Bibliothek implementiert. Strahlenschnitte und Wegfindung uber den a*-Algorithmus werden angeboten, außerdem die Berechnung von „Ambient Occlusion". Die Bibliothek ist in C++ geschrieben und bietet Anbindungen an andere Sprachen [WW].
Transvoxel von LENGYEL ist ein komplettes System zur Darstellung von volumetrischem Terrain mit LOD-Mechanismus und Material. Hinzu kommt ein leistungsfahiger Editor. Transvoxel wird mit der C4-Engine ausgeliefert. Die dahintersteckende Technik ist eine Variante von Marching Cubes. Ahn- lich wie bei Chunked Level of Detail Control" wird auch ein Baum aufgebaut und traversiert, bis der gewünschte Detailgrad abhangig von der Kameraposition erreicht ist. Nur ist der Baum hier ein Octree. Zum Beheben der Lucken zwischen Bereichen unterschiedlicher Auflösung wird das Konzept der Ubergangszellen beim Marching Cubes eingeführt. Dabei beinhalten die Zellen Dreiecke, die beide aneinanderliegenden Auflosungen miteinander verbinden. Insgesamt beinhaltet die Triangulationstabelle nun 73 Falle, ohne dass die inneren Mehrdeutigkeiten gelost werden. Würden sie berücksichtigt, würde die Anzahl der Triangulierungsmöglichkeiten enorm wachsen [Len10].
Ein zum Zeitpunkt dieser Arbeit noch nicht veröffentlichtes, experimentelles Projekt ist die „Procedural World" von CEPERO. Es will eine komplette Welt prozedural generieren und enthalt Terrain, Vegetation und Gebaude. Für weitere Objekte besteht die Möglichkeit, Polygonobjekte zu importieren und zu Voxeldaten umzuwandeln. Zur Konturierung wird Dual Contouring angewandt. Die einzelnen Detailabschnitte werden auch hier wie bei Transvoxel über einen Octree gehandhabt. CEPERO nennt diese Methode in Anlehnung an die Geometry Clipmaps Octree Clipmaps". Dabei generiert ein Server die einzelnen Bereiche und schickt sie per HTTP zur Anwendung. So müssen sie nur einmal berechnet werden. Die Lücken zwischen den einzelnen Abschnitten schließen sich durch Überlappung [Cep12].
4. Dichtefunktion
Die Dichtefunktion bezeichnet die zu verarbeitenden Ausgangsdaten, für die es eine Quelle geben muss. In diesem Projekt wurden zwei Möglichkeiten umgesetzt, die im folgenden im Detail vorgestellt werden. Es sind 3D Texturen sowie Constructive Solid Geometry.
4.1. 3D Texturen
Bei 3D Texturen werden die Werte der Dichtefunktion in einem dreidimensionalen Gitter gespeichert und abgefragt.
VOXELOGlCs Editor „Acropora" bietet prozedurale Generierung von Volumenmodellen mit einigen Grundformen wie Kugeln und Ebenen, Hohenfel- dern, das Umwandeln von Polygonnetzen aus verschiedenen Dateiformaten wie 3DS, FBX oder Collada in Volumendaten, Terrain Generierung, Noise- Funktionen, direkte Bearbeitung des Volumens durch den Benutzer über Pinsel und vieles mehr. Das Ergebnis kann als 3D Textur im DDS-Format exportiert werden [Vox11].
Jeder Pixel dieser Textur ist ein 32 Bit Fließkommawert, der die Dichte des Volumens an dieser Stelle darstellt. Neben der Dichte ist in der Anwendung noch die Information notig, welche Große in Weltkoordinaten das exportierte Volumen hat. Aus diesen Daten gilt es, den Dichtewert und den Gradienten einer gegebenen Koordinate auszurechnen. Vorbereitend wird die Koordinate in den Texturraum umgerechnet.
Abbildung in dieser Leseprobe nicht enthalten
Formel 3: Umrechnung der Koordinate vom Weltraum in den Texturraum
Bei td handelt es sich um die Dimensionen der Textur, wd sind die Dimensionen des Volumens.
Um dem Benutzer Optionen zu bieten, sich zwischen Ladezeit und Qualitat zu entscheiden, gibt es zwei Methoden, den Dichtewert und vier Verfahren, den Gradienten zu berechnen.
Der Dichtewert kann über die „Nearest Neighbor" Interpolation oder trili- niar interpoliert werden.
Bei der Nearest Neighbor Interpolation wird einfach die Texturkoordinate genommen, die c' am nachsten ist [To05, S. 112 - 113].
Abbildung in dieser Leseprobe nicht enthalten
Formel 4: Nearest Neighbor Interpolation der Texturkoordinate nach [To05, S. 112-113]
T(x, y, z) stellt eine Funktion dar, die den Wert der 3D Textur an der ganzzahligen Koordinate (x, y, z), liefert. Somit ergibt sich der gewünschte Dichtewert mittels [Abbildung in dieser Leseprobe nicht enthalten].
Durch trilineare Interpolation lasst sich mit Formel 5 eine höhere Qualitat erreichen [Bou99].
Abbildung in dieser Leseprobe nicht enthalten
Formel 5: trilineare Interpolation eines Punktes mit den acht gegebenen Eckpunkten nach [Bou99]
Der Bereich von x, y und z geht von 0 bis 1, wobei (0,0,0) den Eckpunkt f000 beschreibt und (1,1,1) den Eckpunkt fm im Kubus der Abbildung 4.1. Also muss die Koordinate bei Übergabe an die Funktion auf den Bereich 0 bis 1 normalisiert und in den Ursprung verschoben werden. Im Falle der 3D Textur muss sie nur verschoben werden, weil die Pixel einen Abstand von eins haben.
Der Wert f000 ist der Texturwert [Abbildung in dieser Leseprobe nicht enthalten]. Entsprechend ist fm der Texturwert [Abbildung in dieser Leseprobe nicht enthalten].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4.1.: die Eckpunkte eines Kubus zur trilinearen Interpolation
Entweder kann der Gradient durch Nearest Neighbor Interpolation durch Auswerten von [Abbildung in dieser Leseprobe nicht enthalten] ermittelt oder trilinear interpoliert werden. [Abbildung in dieser Leseprobe nicht enthalten] bis [Abbildung in dieser Leseprobe nicht enthalten] sind in diesem Falle die entsprechenden Gradienten an den Kubus-Eckpunkten und nicht die Texturwerte.
[Abbildung in dieser Leseprobe nicht enthalten] ist in Formel 6 bzw. 7 gezeigt und stellt die Berechnung des Gradienten an einer ganzzahligen Koordinate dar. Dabei gibt es entweder die
Möglichkeit, ihn wie LORENSEN und CLINE zu berechnen [LC87, S. 3] oder ihn mit einem Sobel-Filter zu ermitteln.
Abbildung in dieser Leseprobe nicht enthalten
Formel 6: Berechnung des Gradienten an einer Koordinate nach [LC87, S. 3]
Die Division durch die Kubuslange aus der Originalversion wird hierbei weggelassen, da sie 1 ist.
Die zweite Möglichkeit ist die Ermittlung über einen Sobel-Filter der Formel 7, der weniger anfallig fiir Rauschen ist [To05, S. 176 - 178].
Abbildung in dieser Leseprobe nicht enthalten
Formel 7: Berechnung des Gradienten an einer Koordinate mit Sobel-Filter
4.2. Constructive Solid Geometry
Unter CSG wird die Kombination von Grundformen wie Kugeln, Kuben, Ebenen usw. zu komplexeren Modellen verstanden. Dabei werden Operatoren aus der Mengenlehre verwendet wie Vereinigung, Schnitt, Differenz und Negation. Die Kombination erfolgt über einen Baum, dessen Knoten die Operatoren und die Blatter die Grundformen sind [OM04, S. 157-158].
Im folgenden werden erst die umgesetzten Grundformen und danach die Operatoren vorgestellt. Den Abschluss bildet ein komplexeres Beispiel eines CSG-Baumes.
4.2.1. Grundformen
In diesem Projekt wurden Kugel, Kubus und Ebene als CSG-Grundformen umgesetzt. Abbildung 4.2 zeigt sie von links nach rechts. Die abgerundeten Kanten vom Kubus sind genau der Effekt von Marching Cubes. Er resultiert aus dem Verzicht der genauen Berechnung der Features bei der Umsetzung von DMC, siehe Kapitel 5.1.2.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4.2.: die CSG Grundformen dieses Projektes
Das Volumenmodell der Kugel wird über Formel 8 und 9 berechnet.
Abbildung in dieser Leseprobe nicht enthalten
Formel 8: Dichtefunktion der Kugel
Abbildung in dieser Leseprobe nicht enthalten
Formel 9: Gradientenfunktion der Kugel
xc, yc und zc sind dabei das Zentrum der Kugel, r ihr Radius.
Der Kubus wird über seine linke, untere, hintere und rechte, obere, vordere Ecke beschrieben. Somit können Position und Maße bestimmt werden, nicht jedoch seine Rotation. Bei der Ermittlung der Dichte wird zuerst überprüft, ob die gegebene Koordinate sich innerhalb des Kubus befindet. Das ist über sechs Vergleiche mit den Seiten des Kubus einfach getan. Ist sie innerhalb des Kubus, wird die geringste Distanz der Koordinate zu den Seitenwanden ermittelt. Bei der linken Seite ware das z.B. x — minx mit min als linker, unterer, hinterer Eckpunkt des Kubus. Ist die Koordinate außerhalb, wird auf eine Distanzfunktion der verwendeten Grafikbibliothek zurückgegriffen, die die Falle berücksichtigt, in denen auch eine Kubuskante oder -eckpunkt das nachste Element zur Koordinate sein kann. Zur Ermittlung des Gradienten wird auf die Methode von Marching Cubes in Formel 6 zurückgegriffen.
Die Ebene wird über den Abstand d zum Ursprung und einer Normalen n definiert. Die Dichtefunktion der Formel 10 ist abgeleitet von FARIN und HANSFORD durch die Ermittlung des Abstandes der Koordinate zur Ebene [FH03, S. 180 - 181].
Abbildung in dieser Leseprobe nicht enthalten
Formel 10: Dichtefunktion der Ebene
Der Gradient der Ebene ist ihre Normale n.
4.2.2. Operatoren
Bei den Operatoren wurden Vereinigung, Schnitt, Differenz, Negation und Skalierung umgesetzt. Sie sind in Abbildung 4.3 zu sehen. Oben werden Vereinigung und Schnitt zweier Kugeln gezeigt. Der ausgefranste Rand der Differenz zweier Kugeln unten links ist durch die Mangel der CSG-Operationen zu erklaren, siehe Kapitel 9.3.3.3. Unten rechts ist die Negation einer Kugel zu sehen. Die Kamera befindet sich also in einem kugelförmigen Raum. Zur besseren Visualisierung sind hier die Kanten des Polygonnetzes eingezeichnet.
WANG, und KAUFMAN zeigen die Operatoren Vereinigung, Schnitt, Differenz und Negation auf den Dichtewerten von Formel 11 [WK94, S. 4 - 5].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4.3.: die CSG Operatoren dieses Projektes außer der Skalierung
Abbildung in dieser Leseprobe nicht enthalten
Formel 11: CSG-Operatoren auf den Dichtewerten
Es erscheint unlogisch, dass bei der Differenz 1 — fb (x, y, z) und bei der Negation 1 — f (x, y, z) gewählt wurde, da der Betrag des Dichtewertes sich um 1 verandert. Deswegen wurden diese Formeln zu 12 leicht abgewandelt.
Abbildung in dieser Leseprobe nicht enthalten
Formel 12: angepasste CSG-Operatoren auf den Dichtewerten
Der Gradient ist der der Dichtefunktion, die durch min () bzw. max () ausgewählt wurde. Ist z.B. bei faUb(x,y, z) der Wert von fa(x,y, z) der größere, wird auch sein Gradient genommen. Wenn bei der Differenz — fb (x, y, z) den kleineren Wert liefert, wird der Gradient von fb (x, y, z) mit —1 multipliziert.
Der letzte unäre Operator ist eine Skalierungsfunktion der gegebenen Dichtefunktion (wieder ggf. ein kompletter CSG-Baum) in ihrer Größe mit einem Faktor. Formel 13 bringt die übergebenen Koordinaten mittels einer Division durch den Skalierungsfaktor sf in das Koordinatensystem der urspmng- lichen Dichtefunktion. Eine Multiplikation des Ergebnisses mit sf bringt den gewiinschten Dichtewert. Analog wird der Gradient skaliert.
Abbildung in dieser Leseprobe nicht enthalten
Formel 13: Skalierungsoperation in einem CSG-Baum
4.2.3. Ein Constructive Solid Geometry Baum
Die folgende Abbildung zeigt zur Verdeutlichung einen CSG-Baum.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4.4.: ein CSG-Baum
5. Verfahren der Volumendarstellung
Zunächst werden Teilausschnitte des Volumens mittels DMC konturiert. Da die Ausschnitte mit unterschiedlicher Auflösung aneinanderliegen und das komplette Volumen bilden, können Lucken an ihren Schnittflachen entstehen. Diese werden durch Marching Squares Skirts geschlossen. Damit die fertigen Polygonnetze realistisch aussehen, müssen sie ein Material haben, das die Texturierung, das Relief, die Beleuchtung und den Nebel umsetzt. Aus den einzelnen Ausschnitten wird ein hierarchischer Baum gebildet, der Chunk- baum. Aus ihm werden wahrend der Laufzeit reprasentative Teilausschnitte ausgewahlt, abhangig von der Betrachterkamera.
5.1. Dual Marching Cubes
Das Polygonnetz zur Darstellung des Isosurfaces wird über den Algorithmus DMC von SCHAEFER und WARREN gebildet [SW04]. Er besteht aus mehreren, separat auszuführenden Schritten: Die Bildung des Octrees, die Isolierung von Features, das Ableiten des Dualgitters und letztendlich die Konturierung des Dualgitters mittels Marching Cubes.
DMC basiert auf einen an den Detailgrad der Dichtefunktion angepassten Octree. Somit werden bei ebenformigeren Teilen des Volumens weniger Dreiecke als bei stark gekrümmten verwendet. Außerdem konnen die separierten Schritte für sich ausgearbeitet, implementiert und angepasst werden. Das Polygonnetz erfüllt die Kriterien der 2-Mannigfaltigkeit. Insgesamt ist es ein eleganter, gradliniger Algorithmus mit einigen Schwachen, die noch erlautert werden und in diesem Projekt von kleiner Bedeutung sind.
5.1.1. Generierung des Octrees
DeLoura beschreibt einen Octree als eine Geometrie räumlich unterteilende Datenstruktur. Sie besteht aus einem Baum mit acht Kindern pro Knoten. Der Wurzelknoten beschreibt einen Kubus, der die Geometrie der kompletten Welt einschließt. Seine Kindknoten sind die acht Kuben, die den Vaterknoten in Oktanten unterteilen. Die Unterteilung endet, wenn eine bestimmte Heuristik erfullt ist [DeLOO, S. 439].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.1.: Visualisierung eines Octrees mit Baumstruktur
Abbildung 5.1 zeigt einen kleinen Octree mit zugehöriger Baumstruktur.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.2.: die Nummerierung der Kinder eines Octree-Knotens.
Die Kinder eines Knotens haben in dieser Arbeit die in Abbildung 5.2 dargestellte Nummerierung.
In diesem Projekt beschreibt die Heuristik einen geometrischen Fehlerwert und stoppt die Unterteilung, wenn die aktuelle Zelle einen definierten, akzeptierten Fehler unterschreitet. Dieser akzeptierte Fehler ist die Ursache, dass komplexere Regionen ein detaillierteres Polygonnetz erhalten. Außerdem bestimmt er die Auflösung des Polygonnetzes der einzelnen LOD-Stufen.
Schaefer entwickelte eine Heuristik, die auf Quadratic Error Functions (QEF) basiert. Auf den Punkten eines uniformen Gitters wird mit lokalen Ebenen eine QEF gebildet und minimiert. Wenn der damit ermittelte Fehler großer ist, als ein akzeptierter, wird die aktuelle Octree-Zelle unterteilt [SW04, S. 2]. Die Bildung der QEFs beinhaltet das Abtasten des Gitters, das Bilden von Ebenen an den Punkten und die Minimierung einer daraus gebildeten quadratischen Funktion [SW04, S. 3]. Somit ist die Konstruktion eines Octrees mit dieser Methode sehr teuer und sie scheidet für dieses Projekt aus, da sie Ladezeit zu stark erhöhen wurde.
Stattdessen wird die Fehlermetrik von Zhang, Bajaj und Sohn verwendet. Dafür wird der Fehler mit Hilfe des Unterschiedes einer trilinearen Interpolation und den korrekten Daten approximiert. Die Dichtewerte der acht Eckpunkte der aktuellen Octree-Zelle dienen als Ausgangsdaten für die trilineare Interpolation.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.3.: ein Octree-Knoten mit seinen Kindern und allen Eckpunkten
In Abbildung 5.3 sind diese rot mit den dazugehörigen Indizes dargestellt. Die zusätzlichen Eckpunkte der potentiellen Kinder sind grün eingefarbt. An diesen grünen Punkten werden die Daten einmal abgetastet und einmal trili- near interpoliert.
Die trilineare Interpolation ist in Formel 5 gezeigt.
Für den Fehler zwischen Interpolation und Funktion wird nun der eindimensionale Fall erlautert. v in Abbildung 5.4 ist die Differenz zwischen In-
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.4.: der eindimensionale Fall der Fehlerberechnung zwischen In¬terpolation und Funktion, nach [ZBS05, S. 16]
terpolation und Funktion. Der Fehler ist [Abbildung in dieser Leseprobe nicht enthalten] als Steigung der grün eingezeichneten Tangente. Bei höheren Dimensionen wird aus k die Lange des entsprechenden Gradientenvektors.
Abbildung in dieser Leseprobe nicht enthalten
Formel 14: der approximierte geometrische Fehler einer Octree-Zelle nach [ZBS05, S. 17]
Im aufsummierten Fehler in Formel 14 wird über alle in Abbildung 5.3 grün eingezeichneten Eckpunkte der potentiellen Kinder iteriert, die nicht in der aktuellen Zelle enthalten sind. Die geometrischen Fehler werden aufsummiert, wobei fl+[1] der interpolierte und fl der tatsachliche Wert der Dichtefunktion ist. Die roten Eckpunkte, die sich die aktuelle Zelle und die Kinder teilen, sind Ausgangsbasis der Interpolation und haben somit auch einen Fehlerwert von 0 [ZBS05, S. 16-17].
Diese Heuristik wurde noch um einige Optimierungen erweitert. So wird am Anfang eine minimale Zellengröße festgelegt. Ist die Kantenlange der aktuellen Zelle kleiner oder gleich dem Minimum, stoppt die Unterteilung, ohne die Heuristik zu berechnen. Die zweite Optimierung ist das Stoppen der Unterteilung, wenn die aktuelle Zelle hinreichend vom Isosurface entfernt ist. Dafür wird der absolute Dichtewert ihres Zentrums gegen die 1,5-fache Diagonalenlange getestet. Dieser Faktor ist aus Erfahrungswerten entstanden. Ist der Dichtewert größer oder gleich, stoppt auch hier die Unterteilung vorzeitig. Als letztes wird beim Aufsummieren der Fehlerwerte der einzelnen Kindereckpunkte ständig gegen das tolerierte Minimum gepruft. Sobald es uberschritten oder gleich ist, bricht die Summierung ab und die Octree-Zelle wird unterteilt.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.5.: der Octree einer Kugel mit Zentrum im Ursprung des abgetasteten Volumens
Abbildung 5.5 zeigt den Octree einer Kugel, die ihr Zentrum im Ursprung des abgetasteten Volumens hat. Effektiv wird in der Szene eine Viertelkugel zu sehen sein. Sie hat einen Radius von 2 und das Volumen eine Kantenlange von 10. Es ist gut zu erkennen, dass die Zellen des Octrees in der Nahe der Kugel feiner sind.
5.1.2. Isolierung von Features
Pro Blatt des Octrees muss nun ein Featurepunkt isoliert werden, aus dem sich spater das Dualgitter ableitet. SCHAEFER bildet hier erneut eine QEF, die er zur Ermittlung des Punktes minimiert [SW04, S. 3]. Auch hier ergeben sich die gleichen Probleme, wie bei QEFs bei der Generierung des Octrees. Für ein Volumenmodell eines Drachens benotigte SCHAEFERs 3 GHz Pentium zur Generierung des Octrees und zur Isolierung der Featurepunkte mehrere Minuten [SW04, S. 6].
Die Isolierung der Featurepunkte dient der Erhaltung von scharfen Kanten. MANSON und SCHAEFER haben spater entdeckt, dass deren Position uberschneidende Dreiecke bilden können, die fehlerhaft beleuchtet werden, da die Reihenfolge der Eckpunkte sich bei ihnen geandert hat [MS10, S. 3]. In Abbildung 5.6 ist eine solche Situation zu sehen [MS10, S. 2].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.6.: überschneidende Dreiecke mit geänderter Eckpunktreihenfolge bei Dual Marching Cubes nach [MS10, S. 2]
SCHAEFER schlägt als Alternative vor, die Zentren der Octreeblätter zu verwenden [SW04, S. 6]. Da die Hauptanwendung dieses Projektes organisch geformtes Terrain ist, wurde diese Methode der Featureisolierung zugunsten der Ladezeit anstelle der scharfen Kanten gewahlt.
Die Zentren der Octree-Zellen stellen im nachsten Schritt die Eckpunkte der Dualzellen dar. Da die Dualzellen spater mittels Marching Cubes konturiert werden, wird beim Erstellen des Octrees an dieser Stelle schon der Isowert und der Gradient ermittelt, um sie beim Konturieren bis zu acht mal zu verwenden.
5.1.3. Bilden des Dualgitters
Anhand des Octrees kann nun das Dualgitter gebildet werden. Dualität bedeutet, dass es zu einem Objekt A ein duales Objekt B gibt, dessen duales Objekt wiederum A mindestens ahnlich ist [DLT]. Abbildung 5.7 zeigt frei nach SCHAEFER ein solches Dualgitter. Zur besseren Veranschaulichung ist das Dualgitter eines Quadtrees gewahlt [SW04, S. 3].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.7.: das grüne Dualgitter gebildet aus dem schwarzen Quadtrees nach SCHAEFER [SW04, S. 3]
Der Octree wird von oben nach unten traversiert. Dabei werden aus den Features des Octrees die Eckpunkte der einzelnen Zellen des Dualgitters, die für sich genommen jeweils einen topologischen Kubus ergeben. Die Eckpunkte können aufeinander liegen, so dass die Dualzellen dann nicht mehr aussehen wie Kuben. Dies stellt bei der spateren Konturierung mittels Marching Cubes kein Problem dar [SW04, S. 5 - 6].
Leider beschreibt SCHAEFER nur die Bildung eines Dualgitters zu einem Quadtree und merkt an, dass sich der Algorithmus „natürlich" auf einen Octree erweitert [SW04, S. 4].
HOLMLID erlautert in seiner Masterthesis die genaue Konstruktion im Falle eines Octrees. Die Traversierung beinhaltet vier rekursive Funktionen, node- Proc(n), faceProc(n0, n1), edgeProc(n0, n1, n2, n3) und vertProc(n0, n1, n2, n3, n4, n5, n6, n7). Alle Parameter sind Octree-Knoten. Wie bei HOLMLID ist auch in dieser Variante die Funktion edgeProc(n0, n1, n2, n3) unterteilt in edgeProcX(n0, n1, n2, n3), edgeProcY(n0, n1, n2, n3) und edgeProcZ(n0, n1, n2, n3) sowie face- Proc(n0, n1) in faceProcXY(n0, n1), faceProcZY(n0, n1) und faceProcXZ(n0, n1). Der Grund hierfür ist die Bewahrung der räumlichen Relation der Knoten, ohne in der jeweiligen Funktion viele Fallunterscheidungen zu benotigen.
Wenn ein an einer Funktion übergebene Knoten keine Kinder hat, wird er an die aufgerufenen Funktionen einfach durchgereicht. Aus diesem Grunde entstehen nicht nur Kuben, sondern auch andere Formen und es verbinden sich Octree-Nachbarn unterschiedlicher Tiefen miteinander [Hom10, S.21 - 25].
Der folgende Pseudocode und die Visualierungen sind an [Hom10, S.23 - 25] angelehnt und wurde an die Implementierung in diesem Projekt angepasst. Die Rekursion beginnt mit dem Aufruf von nodeProc(n) mit der Wurzel des Octrees.
Abbildung in dieser Leseprobe nicht enthalten
Quellcode 5.1: Pseudocode von nodeProc(n)
Eine Visualisierung der Aufrufe von nodeProc(n), faceProcXY(n0, nl), face- ProcZY(n0, nl), faceProcXZ(n0, nl), edgeProcX(n0, nl, n2, n3), edgeProcY(n0, nl, n2, n3), edgeProcZ(n0, nl, n2, n3) und vertProc(n0, nl, n2, n3, n4, n5, n6, n7) ist in Abbildung 5.8 gezeigt. Die roten Kinder sind dabei die Parameter der rekursiven Aufrufe von nodeProc(n). Grün sind die Parameter für faceProc(n0, n1), blau sind die für edgeProc<XY/ZY/ZX>(n0, n1, n2, n3). Der Aufruf von vertProc(n0, n1, n2, n3, n4, n5, n6, n7) hat gelbe Parameter.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.8.: die Aufrufe der Unterfunktionen von nodeProc(n)
Exemplarisch folgt nun faceProcXZ(n0, n1), die anderen beiden Funktionen sind analog.
Abbildung in dieser Leseprobe nicht enthalten
Quellcode 5.2: Pseudocode von faceProcXY(n0, n1)
In Abbildung 5.9 sind die Unteraufrufe von faceProcXY(n0, n1) dargestellt.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.9.: die Aufrufe der Unterfunktionen von faceProcXY(n0, n1) Es folgt edgeProcX(n0, n1, n2, n3).
Abbildung in dieser Leseprobe nicht enthalten
Quellcode 5.3: Pseudocode von edgeProcX(n0, n1, n2, n3)
edgeProcX(n0, n1, n2, n3)s Unteraufrufe sind in Abbildung 5.10 gezeigt. Die eigentlichen Dualzellen werden in vertProc(n0, n1, n2, n3, n4, n5, n6, n7) gebildet.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.10.: die Aufrufe der Unterfunktionen von edgeProcX(n0, n1, n2, n3)
Abbildung in dieser Leseprobe nicht enthalten
Quellcode 5.4: Pseudocode von vertProc(n0, n1, n2, n3, n4, n5, n6, n7)
vertProc(n0, n1, n2, n3, n4, n5, n6, n7) ruft nur sich selbst auf, wenn einer der ubergebenen Knoten kein Kind ist und wird in Abbildung 5.11 visuali- siert. Ansonsten wird mittels createDualCell(v0, v1, v2, v3, v4, v5, v6, v7) die Dualzelle mit v0 - v7 als Eckpunkte gebildet. Für v0 - v7 werden die Zentrenvektoren der Octree-Zellen verwendet. Dies geschieht nach einem Test, ob alle diese Zentren „nah genug" am Isosurfaces sind. Nah genug bedeutet in diesem Falle, dass der Isowert des Zentrums der jeweiligen Octree-Zelle kleiner sein muss als k · Zellendiagonale mit k als benutzerdefinierte Konstante. Ist k zu klein gewahlt, können Lucken im Polygonnetz entstehen, da Zellen des Dualgitters, die das Isosurface schneiden, sonst evtl. nicht erstellt werden. In dieser Implementierung ist k = 2. Dieser Test sorgt dafür, dass das Dualgitter sich adaptiv dem Isosurface anpasst und es werden viele Zellen ausgelassen, die nichts zum Polygonnetz beitragen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.11.: der Aufruf von vertProc(n0, n1, n2, n3, n4, n5, n6, n7) von sich selbst
Die Abbildungen 5.8,5.9,5.10 und 5.11 zeigen, wie durch diese Art der Traversierung elegant Dualzellen zwischen benachbarten Knoten gebildet werden, ohne dass die sich kennen mdssen.
Es fehlen noch die Dualzellen vom bisherigen Dualgitter zum Rand des Octrees. Abbildung 5.12 zeigt diesen Status der Kugel im Volumenursprung mit dem Dualgitter in grün.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.12.: ein Dualgitter zu einem Octree ohne Randzellen
SCHAEFER schlagt degenerierte Octree-Zellen zur Generierung der Randzellen vor und mit ihnen edgeProc(n0, n1, n2, n3) und vertProc(n0, n1, n2, n3, n4, n5, n6, n7) aufzurufen. Damit ist gemeint, dass der Octree wie das Zentrum eines 3 x 3 x 3 großen Gitters zu behandeln ist, wobei die außeren Zel- len zu Flächen bzw. Punkten (im Falle der Eckzellen) degenerieren [SW04, S. 4]. Damit ergibt sich das Problem, dass der Octree nochmal komplett tra- versiert wird, was die Ladezeit erhöhen wUrde. Deswegen wurde in diesem Projekt ein anderer Ansatz gewahlt. createBorderCells(n0, n1, n2, n3, n4, n5, n6, n7) prUft die Zellen, ob sie am Rand liegen und welche der nachfolgend aufgeführten Falle sich daraus ergeben.
- Die Zelle liegt an einer Außenebene (6 Moglichkeiten).
- Die Zelle liegt an einer Außenkante (12 Moglichkeiten).
- Die Zelle liegt in einer Außenecke (8 Moglichkeiten).
Somit gibt es 26 mogliche Randfalle. Die Tests, ob ein Fall vorliegt, reduzieren sich untereinander. So muss die Außenecke hinten links oben auch an der Außenebene oben und an der Außenkante hinten liegen.
Der folgende Pseudocode zeigt einen Teil der Erstellung der Randzellen. Den Kommentaren ist die Abhandlung der Falle zu entnehmen, wobei wie immer die Indizierung von Abbildung 5.2 gilt.
Abbildung in dieser Leseprobe nicht enthalten
Quellcode 5.5: Pseudocode der Behandlung der Randzellen der hinteren Außenebene in createBorderCells(n0, n1, n2, n3, n4, n5, n6, n7)
Analog zu diesem Code funktionieren auch die Bedingungsstufen der vorderen, linken und rechten Außenflachen mit den entsprechenden Außenkanten und Außenecken. Die Behandlung der oberen und unteren Außenflachen fällt kürzer aus, da die angrenzenden Außenkanten und -ecken schon erledigt sind. Beispielhaft folgt die Behandlung der oberen Außenebene:
Abbildung in dieser Leseprobe nicht enthalten
Quellcode 5.6: Pseudocode der Behandlung der Randzellen der oberen Außenebene in createBorderCells(n0, n1, n2, n3, n4, n5, n6, n7)
Somit ist das Dualgitter fertig und hat die Form von Abbildung 5.13.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.13.: ein Dualgitter zu einem Octree mit Randzellen
Abbildung 5.14 zeigt, dass das Dualgitter der bekannten Szene nicht gebildet wird, wenn es zu weit vom Isosurface entfernt ist.
5.1.4. Konturierung des Dualgitters
Bei der Konturierung des Dualgitters wird letztendlich das Polygonnetz erstellt. Hierzu wird Marching Cubes verwendet [SW04, S. 5 - 6].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5.14.: das adaptive Dualgitter zu einem Octree
SCHAEFER platziert die Eckpunkte des Dualgitters exakt auf dem Isosurface. Damit werden kleine Dreiecke vermieden und die Qualitat des Polygonnetzes erhöht [SW04, S. 5]. Dafür werden jedoch wieder QEFs benutzt, die in diesem Projekt aus genannten Griinden nicht implementiert wurden.
Der urspriingliche Marching Cubes von LORENSEN und Cline wandert mit Kuben definierter Größe das Volumen ab, testet die Eckpunkte des aktuellen Kubus, ob sie kleiner (außerhalb des Volumens) oder großer (innerhalb des Volumens) des Isowerts sind und bildet aus diesen boolschen Werten einen Index. Ein Kubus hat acht Eckpunkte, die jeweils großer oder kleiner des Isowerts sein können, somit ergeben sich 2[8] = 256 mögliche Konfigurationen. Es existiert eine Tabelle anhand derer fur jede Konfiguration die Triangulierung des Kubus nachgeschlagen wird. Der original Marching Cubes reduziert diese Tabelle durch Ausnutzung von Symmetrie. Erstens können die Werte der Eckpunkte (außerhalb oder innerhalb des Volumens) negiert werden, ohne dass sich die Triangulierung andert. Über bleiben 128 Konfigurationen. Zweitens können die Kuben rotiert werden. Z.B. gibt es acht Möglichkeiten, dass ein Eckpunkt innerhalb des Volumens liegt, deren Triangulierung sich nur durch Rotation unterscheidet. Damit verbleiben 15 mögliche Konfigurationen.
[...]
[1] http://www.ogre3d.org
[1] http://www.gzip.org/zlib/zlib_license.html
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X.