Echtzeitdarstellung von Volumendaten mit einem Level of Detail System

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 Textu­rierung
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 vo­lumenbasierter 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 Re­lief 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 Operatio­nen 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 Squa­res Skirts werden Polygonnetze aus den Volumendaten generiert und mittels triplanarer Texturierung mit einem passenden Material versehen.

Zur Darstellung des Volumens werden viele separate Polygonnetzen meh­rerer Detailstufen erzeugt und in einer Baumstruktur organisiert. Je nach Ent­fernung zum Betrachter werden aus diesen „Chunks" die passenden aus­gewählt. Dieser Level of Detail Algorithmus sorgt dafür, dass auch große Vo­lumendaten 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 over­hangs, 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 geome­try 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 le­vels 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 Inter­polation und Funktion, nach [ZBS05, S. 16]

5.5. der Octree einer Kugel mit Zentrum im Ursprung des abgetas­teten Volumens

5.6. uberschneidende Dreiecke mit geanderter Eckpunktreihenfol­ge 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 ge­bildet 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 Textur­koordinaten, 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 Kame­raabstand 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 Squa­res Fall Dreiecke gebildet werden

16. Bildung der Uberblendungsfaktoren bei der triplanaren Textu­rierung

17. Normalisierung der Uberblendungsfaktoren bei der triplana- ren Texturierung

18. Bildung der Fragmentfarbe durch Überblendung dreier plana­rer Projektionen

19. Bildung der drei Texturkoordinaten der planaren Projektionen .

20. Umrechnung einer RGB-Texturfarbe in eine Normale

21. Berechnung der Normal Mapping Normale durch Uberblen­dung 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 Fragment­farbe

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 Normalen­Textur Normalen-Vektoren beinhaltet, die Normale fiir jedes Pixel mo­difiziert [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 verein­fachten 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 al­len Computerspielen mit Außenszenarien benötigt, sei es ein Flugsimulator, ein Rennspiel oder ein Ego-Shooter. Dabei ist es essentiell wichtig, ein effizi­entes Verfahren zu verwenden, um eine flüssige Bildrate zu ermoglichen.

Ein klassischer Ansatz ist die Verwendung von Hohenfeldern. Hierffir wer­den 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 Po­lygonnetz 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 De­tail (LOD) Mechanismus notig. Dieser sorgt dafiir, dass weiter vom Betrach­ter 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 be­liebige 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 volumenbasier­ten 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 Volumen­daten nötig, die mittels eines Polygonnetzes die Informationen approximiert. Eine direkte Darstellung wurde auf die Umwandlung in Dreiecke verzich­ten 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 Strate­gie 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 meh­rere 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 ge­bildet 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 entspre­chendes Material erforderlich. Es bestimmt, ob das Polygonnetz wie Ra­sen oder wie Wüstensand aussieht. Dabei kann je nach Steigung über­blendet 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 Compu­ter 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 prakti­sches 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. Eini­ge 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 Volumendarstel­lung. Anhand der Dichtefunktion werden mittels DMC Polygonnetze gebil­det. 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 Biblio­thek Object-Oriented Graphics Rendering Engine (OGRE)^[1]. Das Projekt wur­de im Google Summer of Code (GSoC) entwickelt und ist mittlerweile Be­standteil von OGRE.

Anschließend werden die Softwarearchitektur und die Implementierungs­details 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 be­zeichnet. Die Oberflache wird extrahiert, indem die Funktion fUr eine gegebe­ne 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 For­mel 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 Funk­tion gleich 0, ein mittleres Grau in der Darstellung. Alle Orte mit einem Iso­wert von 0 sind außerdem grün eingezeichnet, womit ein Kreis entsteht. Das Abbilden dieses Isosurfaces mittels eines Polygonnetzes wird als „Konturie­rung" bezeichnet [Hom10, S. 6]. Zuletzt ist die Dichtefunktion bei der blauen Markierung gleich — r.

Neben dem Dichtewert ist noch der Gradient an der gegebenen Koordi­nate wichtig. Er wird für die Bildung eines Octrees und für die Beleuchtung benotigt. Beim Gradienten handelt es sich um einen Vektor, dessen Kompo­nenten aus den partiellen Ableitungen der Dichtefunktion bestehen. Somit steht der Vektor senkrecht auf Oberflache der Dichtefunktion. Die Lange be­schreibt 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ängen­de Entwicklung. Zuerst werden die drei Teilaspekte der Generierung des Isos­urfaces und des Materials betrachtet. Danach werden auf Hohenfeld basieren­de 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 Algorith­mus 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 befin­den, 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 Konfi­gurationen der Eckpunkte mehrere, gültige Triangulationsmöglichkeiten, die bei aneinanderliegenden Kuben zu Lochern führen. Diese lassen sich behe­ben, indem die Symmetrie des Negierens der Eckpunktkonfiguration wegge­lassen wird [Nie03, S. 9].

Ein weiteres Problem ist die innere Mehrdeutigkeit, bei der zwar keine Locher entstehen, aber unterschiedliche Geometrien moglich sind. In man­chen 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" ent­stehen oder eine Art Schlauch quer durch den Kubus. Die Dichtefunktion ei­ner 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 er­weiterten Tabelle die korrekte Triangulation nachgeschlagen werden [Che95]. LEWINER et al stellten hierfür eine effiziente Implementierung vom Algorith­mus Marching Cubes 33 mit Tabellen ffir alle Konfigurationen zur Verffigung [LLVT03].

Marching Tetrahedra funktioniert wie Marching Cubes, mit dem Unter­schied, 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 Kan­ten von Marching Cubes. Dabei wird die Geometrie nicht aus vorgefertig­ten Schablonen einer Tabelle erstellt. Stattdessen wird ffir jede das Volumen schneidende Kubuskante aus einer Reihe von Testpunkten mit ihren Norma­len mittels des Verfahrens der kleinsten Quadrate ein repräsentativer Punkt berechnet. Nach der Iteration uber die Kuben werden mit der erstellten Punk­teliste 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 Dreie­cke kontrolliert. Diese Metrik ist der Berechnung der repräsentativen Punkte ahnlich [JLSW02].

SCHAEFER stellte spater fest, dass immer noch unnotig viele Dreiecke ge­neriert werden, weil der Detailgrad von der Dicke des Volumens abhangt. Je dfinner das Volumen an der betreffenden Stelle ist, je feiner wird auch der Oc­tree unterteilt [SW04, S. 2]. MANSON beschrieb Situationen, bei Dual Contou­ring, 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 al­lerdings nicht erlaubt. Wenn das möglich ist, sind die Formen topologisch aquivalent. Als Konsequenz darf der Schnitt zweier Dreiecke eines Polygon­netzes nur leer, ein Eckpunkt, eine Kante oder die Dreiecksflache sein. Über­lappende 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 ent­warf 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" ab­zuleiten. Diese Datenstruktur bewirkt, dass Lücken in der Triangulierung be­nachbarter Zellen durch die Auswahl der Kanten der hoher aufgelosten Seite geschlossen werden. Damit ist das Ziel einer adaptiven Triangulierung er­reicht, 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 extra­hierte 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 Mar­ching Squares ausfuhrt und aus diesen Daten eine dreidimensionale Triangu­lierung produziert. Auch hier wird ein Octree verwendet, um eine dem De­tailgrad entsprechende Dreiecksanzahl zu erreichen. Zuerst werden Segmen­te 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 exak­ten Punkte der scharfen Features werden durch Probepunkte und ihre Nor­malen 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 Pro­grammierung verbunden und erst dann trianguliert [HWC+05]. Diese Me­thode 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 Volu­menmodellen nicht aus, weil sie zu großen Verzerrungen führt. GEISS er­weiterte die planare Projektion auf drei von den Hauptachsen des Koordi­natensystems kommende und wahlt diejenige aus, die die geringste Verzer­rung bietet. In den Zwischenbereichen der Geometrie werden die Projektio­nen überblendet. Mit der gleichen Technik wird auch Normal Mapping umge­setzt [Gei07]. Diese triplanare Texturierung wurde von LENGYEL um einige Kontrollparameter erweitert. Außerdem entfernt er eine ungewollte Spiege­lung [Len10, S. 46 - 51].

Eine Alternative ist das „Indirection Mapping" von MCGUIRE und WHIT­SON. Ein komplizierter Praprozess erstellt mittels einer Federsimulation eine „Indirection Map". Eine einzelne planare Projektion bildet Texturkoordina­ten. 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 haupt­sachlich 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 verein­facht. Damit wird auch gleichzeitig ein Nachteil deutlich. Bei jederÄnderung der Kamera müssen die Dreiecke neu berechnet und an die Grafikkarte ge­schickt 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 Auf­tauchen von Details mindert [DWS+97].

ULRICH hat bei „Chunked Level of Detail Control" einen Quadtree aufge­baut, dessen Wurzel das ganze Terrain in der niedrigsten Detailstufe bein­haltet. Die vier Kinder enthalten jeweils ein Viertel des Terrains ihres Vaters in höherem Detailgrad. Jede Ebene des Baumes umfasst somit das komplet­te 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 bezeich­net 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 Tri­angulierung 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 simp­leren Schema das Polygonnetz auf. In der höchsten LOD-Stufe erzeugt je­der 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 Rand­Eckpunkte 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 berech­net 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 Er­zeugung des Polygonnetzes. Ein Unterschied ist die Verwendung von Skirts zur Vermeidung von Lücken zwischen angrenzenden, unterschiedlichen De­tailstufen. Das reduziert dieÄnderung von Indizes der Polygonnetze beim Wechsel der LOD-Stufen. Die Verwendung von Skirts ermöglicht es, weit ent­fernte Bereiche nicht im Speicher zu halten und erst beim Naherkommen zu laden. Bereiche, die wieder weit genug entfernt sind, werden aus dem Spei­cher entfernt. Durch die Skirts müssen die einzelnen Teilbereiche keine Kennt­nisse über ihre Nachbarn mitbringen [OT12].

3.4. Volumenbasiertes Terrain

David Williams und Matt Williams haben die Bibliothek „Polyvox" un­ter 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 LOD­Mechanismus ist nicht in der Bibliothek implementiert. Strahlenschnitte und Wegfindung uber den a*-Algorithmus werden angeboten, außerdem die Be­rechnung 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 aufge­baut und traversiert, bis der gewünschte Detailgrad abhangig von der Ka­meraposition erreicht ist. Nur ist der Baum hier ein Octree. Zum Beheben der Lucken zwischen Bereichen unterschiedlicher Auflösung wird das Kon­zept der Ubergangszellen beim Marching Cubes eingeführt. Dabei beinhalten die Zellen Dreiecke, die beide aneinanderliegenden Auflosungen miteinan­der verbinden. Insgesamt beinhaltet die Triangulationstabelle nun 73 Falle, ohne dass die inneren Mehrdeutigkeiten gelost werden. Würden sie berück­sichtigt, würde die Anzahl der Triangulierungsmöglichkeiten enorm wachsen [Len10].

Ein zum Zeitpunkt dieser Arbeit noch nicht veröffentlichtes, experimen­telles 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 an­gewandt. 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 Abschnit­ten 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 um­gesetzt, 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 dreidimensio­nalen Gitter gespeichert und abgefragt.

VOXELOGlCs Editor „Acropora" bietet prozedurale Generierung von Volu­menmodellen 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 Pin­sel und vieles mehr. Das Ergebnis kann als 3D Textur im DDS-Format expor­tiert 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 Dimen­sionen 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 ganz­zahligen Koordinate (x, y, z), liefert. Somit ergibt sich der gewünschte Dich­tewert 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 Eck­punkten 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 in­terpoliert werden. [Abbildung in dieser Leseprobe nicht enthalten] bis [Abbildung in dieser Leseprobe nicht enthalten] sind in diesem Falle die entsprechenden Gra­dienten 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 Gra­dienten 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 For­mel 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, Ebe­nen usw. zu komplexeren Modellen verstanden. Dabei werden Operatoren aus der Mengenlehre verwendet wie Vereinigung, Schnitt, Differenz und Ne­gation. Die Kombination erfolgt über einen Baum, dessen Knoten die Opera­toren 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

x_c, y_c und z_c 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, un­terer, 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 Ver­einigung und Schnitt zweier Kugeln gezeigt. Der ausgefranste Rand der Dif­ferenz 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 bes­seren Visualisierung sind hier die Kanten des Polygonnetzes eingezeichnet.

WANG, und KAUFMAN zeigen die Operatoren Vereinigung, Schnitt, Diffe­renz 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 () aus­gewä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 Dich­tefunktion (wieder ggf. ein kompletter CSG-Baum) in ihrer Größe mit einem Faktor. Formel 13 bringt die übergebenen Koordinaten mittels einer Divisi­on 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 meh­reren, separat auszuführenden Schritten: Die Bildung des Octrees, die Isolie­rung von Features, das Ableiten des Dualgitters und letztendlich die Kontu­rierung des Dualgitters mittels Marching Cubes.

DMC basiert auf einen an den Detailgrad der Dichtefunktion angepassten Octree. Somit werden bei ebenformigeren Teilen des Volumens weniger Drei­ecke als bei stark gekrümmten verwendet. Außerdem konnen die separier­ten 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 unterteilen­de 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 Heu­ristik 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 dar­gestellte Nummerierung.

In diesem Projekt beschreibt die Heuristik einen geometrischen Fehlerwert und stoppt die Unterteilung, wenn die aktuelle Zelle einen definierten, akzep­tierten Fehler unterschreitet. Dieser akzeptierte Fehler ist die Ursache, dass komplexere Regionen ein detaillierteres Polygonnetz erhalten. Außerdem be­stimmt 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 verwen­det. Dafür wird der Fehler mit Hilfe des Unterschiedes einer trilinearen Inter­polation und den korrekten Daten approximiert. Die Dichtewerte der acht Eckpunkte der aktuellen Octree-Zelle dienen als Ausgangsdaten für die trili­neare 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 eindi­mensionale 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 aufsum­miert, wobei fl+[1] der interpolierte und fl der tatsachliche Wert der Dichte­funktion ist. Die roten Eckpunkte, die sich die aktuelle Zelle und die Kinder teilen, sind Ausgangsbasis der Interpolation und haben somit auch einen Feh­lerwert 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 ak­tuellen Zelle kleiner oder gleich dem Minimum, stoppt die Unterteilung, ohne die Heuristik zu berechnen. Die zweite Optimierung ist das Stoppen der Un­terteilung, wenn die aktuelle Zelle hinreichend vom Isosurface entfernt ist. Dafür wird der absolute Dichtewert ihres Zentrums gegen die 1,5-fache Dia­gonalenlange getestet. Dieser Faktor ist aus Erfahrungswerten entstanden. Ist der Dichtewert größer oder gleich, stoppt auch hier die Unterteilung vorzei­tig. Als letztes wird beim Aufsummieren der Fehlerwerte der einzelnen Kin­dereckpunkte ständig gegen das tolerierte Minimum gepruft. Sobald es uber­schritten 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 abge­tasteten 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 Kan­ten. 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 Eckpunktreihen­folge bei Dual Marching Cubes nach [MS10, S. 2]

SCHAEFER schlägt als Alternative vor, die Zentren der Octreeblätter zu ver­wenden [SW04, S. 6]. Da die Hauptanwendung dieses Projektes organisch ge­formtes 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 ver­wenden.

5.1.3. Bilden des Dualgitters

Anhand des Octrees kann nun das Dualgitter gebildet werden. Dualität be­deutet, 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 Eckpunk­te können aufeinander liegen, so dass die Dualzellen dann nicht mehr ausse­hen 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 Oc­tree 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 ange­passt. 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) gebil­det.

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 Zentren­vektoren der Octree-Zellen verwendet. Dies geschieht nach einem Test, ob alle diese Zentren „nah genug" am Isosurfaces sind. Nah genug bedeutet in die­sem 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 Tra­versierung elegant Dualzellen zwischen benachbarten Knoten gebildet wer­den, 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 Rand­zellen 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 Zen­trum 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 auf­gefü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, reduzie­ren 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 vor­deren, linken und rechten Außenflachen mit den entsprechenden Außenkan­ten 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 gebil­det wird, wenn es zu weit vom Isosurface entfernt ist.

5.1.4. Konturierung des Dualgitters

Bei der Konturierung des Dualgitters wird letztendlich das Polygonnetz er­stellt. 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 Isosur­face. Damit werden kleine Dreiecke vermieden und die Qualitat des Polygon­netzes 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 ak­tuellen Kubus, ob sie kleiner (außerhalb des Volumens) oder großer (inner­halb des Volumens) des Isowerts sind und bildet aus diesen boolschen Wer­ten 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 Konfigura­tionen. Es existiert eine Tabelle anhand derer fur jede Konfiguration die Trian­gulierung des Kubus nachgeschlagen wird. Der original Marching Cubes re­duziert diese Tabelle durch Ausnutzung von Symmetrie. Erstens können die Werte der Eckpunkte (außerhalb oder innerhalb des Volumens) negiert wer­den, ohne dass sich die Triangulierung andert. Über bleiben 128 Konfigura­tionen. Zweitens können die Kuben rotiert werden. Z.B. gibt es acht Möglich­keiten, dass ein Eckpunkt innerhalb des Volumens liegt, deren Triangulierung sich nur durch Rotation unterscheidet. Damit verbleiben 15 mögliche Konfi­gurationen.

[...]

---

^[1] http://www.ogre3d.org

^[1] http://www.gzip.org/zlib/zlib_license.html