Embed Size (px)
Citation preview
Fachbereich 4: Informatik
Seminar
Echtzeit-Rendering
SS 2008
Rendering von Landschaften
vorgelegt von
Paul Lemke, Helene Roht
Betreuer: Dipl.-Inform. Jakob Barz(Institut fur Computervisualistik, AG Computergrafik)
Koblenz, 04. Juni 2008
Inhaltsverzeichnis
1 Einfuhrung 3
2 Anwendungen 3
3 Technische Vorraussetzungen 43.1 Rendering Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . 53.2 Grafikhardware . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.3 Out-of-Core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Grundlagen 74.1 Reprasentation der Daten . . . . . . . . . . . . . . . . . . . . . . 7
4.1.1 Hohentextur . . . . . . . . . . . . . . . . . . . . . . . . . 74.1.2 Rastergelandemodell . . . . . . . . . . . . . . . . . . . . 74.1.3 Dreiecksvermaschung . . . . . . . . . . . . . . . . . . . 84.1.4 BinTree . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.1.5 Quadtrees . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Level of Detail . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.2.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . 104.2.2 Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 104.2.3 Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 View Frustum Culling . . . . . . . . . . . . . . . . . . . . . . . . 114.3.1 View Frustum . . . . . . . . . . . . . . . . . . . . . . . . 114.3.2 Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 124.3.3 Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4 Texturierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.4.1 Texturskalierung . . . . . . . . . . . . . . . . . . . . . . 124.4.2 Mip Mapping . . . . . . . . . . . . . . . . . . . . . . . . 124.4.3 Multitexturing . . . . . . . . . . . . . . . . . . . . . . . 13
5 Algorithmen 155.1 Chunked Level of Detail . . . . . . . . . . . . . . . . . . . . . . 15
5.1.1 Chunked Level of Detail Control . . . . . . . . . . . . . . 155.1.2 Vorverarbeitung . . . . . . . . . . . . . . . . . . . . . . . 155.1.3 Einsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.1.4 Selektionskriterium fur die Detailstufe . . . . . . . . . . . 175.1.5 Crack Filling . . . . . . . . . . . . . . . . . . . . . . . . 185.1.6 View Frustum Culling und Textur . . . . . . . . . . . . . 185.1.7 Bewertung . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Geometric Mipmapping . . . . . . . . . . . . . . . . . . . . . . . 195.2.1 Geometric Mipmapping . . . . . . . . . . . . . . . . . . 195.2.2 Vorverarbeitung . . . . . . . . . . . . . . . . . . . . . . . 195.2.3 Einsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1
5.2.4 Selektionskriterium fur die Detailstufe . . . . . . . . . . . 205.2.5 Geometry Gaps . . . . . . . . . . . . . . . . . . . . . . . 205.2.6 View Frustum Culling und Textur . . . . . . . . . . . . . 205.2.7 Morphing . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2.8 Bewertung . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3 Geometry Clipmap . . . . . . . . . . . . . . . . . . . . . . . . . 225.3.1 Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.3.2 Hohendaten . . . . . . . . . . . . . . . . . . . . . . . . . 225.3.3 Interaktion . . . . . . . . . . . . . . . . . . . . . . . . . 235.3.4 Ubergangszonen . . . . . . . . . . . . . . . . . . . . . . 235.3.5 View Frustum Culling . . . . . . . . . . . . . . . . . . . 24
2
1 Einfuhrung
Rendering von Landschaften wird zunehmend ein wichtiger Begriff in dem Ge-biet Computergrafik. Heutzutage greifen viele Bereiche auf das Rendern der Land-schaften. Einige Bereiche werden hier herangefuhrt und vorgestellt. Zudem spie-len technische Grundlagen eine enorme Rolle. Die aktuellen Grafikkarten erledi-gen viele Berechnungen selbstandig und rendern die Umgebung in annehmbarerQualitat. Fur die Verwaltung großer Datenmengen benotigt man geschickte Ver-fahren und deren Optimierungsmoglichkeiten, die hier naher erlautert werden. Furdie Implementierung der Algorithmen braucht man grundlegende Methoden, wiebeispielsweise Generierung der Netzstrukturen, Level of Detail und View FrustumCulling.
Eine Vielzahl von Algorithmen lassen sich zu Landschaftsrendering finden.Hier werden drei Konzepte prasentiert: Chunked LoD, Geometric Mipmapping undGeometry Clipmap.
2 Anwendungen
Die virtuellen Landschaften werden in vielen Gebieten eingesetzt. Eins der Gebie-te ist virtueller Tourismus und Reiseplanung. Ein eindrucksvolles Beispiel dazu ist”Virtuelles Bayern”, welches Abbildung 1 zeigt. Dieses privat finanzierte Projekthat sich zum Ziel gesetzt touristische und kulturhistorische Sehenswurdigkeitenphotorealistisch zu erstellen. Vordergrundig bei diesem Projekt ist ”digitales kul-turelle Erbe”. Daruber hinaus mochte man die Landschaften vor Massentourismusschutzen. [fRuMiO08] Unter virtuellen Tourismus fasst man auch unzuganglicheLandschaften zusammen, wie zum Beispiel fremde Planeten oder die Oberflachedes Tiefseebodens. Die zugehorigen Daten fur die Topografie wurden durch dieSatelliten oder Schallwellen beschafft.
Weitere Anwendungsgebiete von Visualisierung der realen Welten sind Pla-nungsprozesse der Stadt- und Landschaftsplanung. Rendering von Landschaftenkann eine wichtige Rolle bei der Entscheidungsfindung der Planung spielen. Da-mit lasst es sich leicht feststellen, ob finanziell aufwendige Projekte wie Teiche undHugel in die Umgebung hineinpassen.[Ape03, S. 793] Ebenso kann man die Visua-lisierung leicht nach den asthetischen Gesichtspunkten bewerten und entscheiden,ob die geplanten Projekte mit der gegebenen Umgebung harmonieren.
Klimatologie und Meteorologie ist ein anderer wichtiger Bereich. Mit Hilfevon simulierten Landschaften lasst sich feststellen, wie bestimmte Landschafts-formen wie Berge oder Gewasser auf einander wirken konnen und wie sie einebestimmte Umgebung beeinflussen. Besonders die Katastrophenforschung bedientsich zunehmend solcher Simulationen.[Ape03, S. 793] Man kann zum Beispiel die
3
Abbildung 1: Virtuelles Bayern1 Abbildung 2: Stadplannung2
Abbildung 3: Brandkatastrophe3 Abbildung 4: Oblivion4
Ursachen und Auswirkungen eines Erdbebens visualisieren und dadurch naher be-trachten. In Fallen von Waldbrandkatastrophen kann man Vorhersagen machen, dieanhand von Windrichtung und der Gebirgsgestaltung zusammenhangen. Die Ab-bildung 3 zeigt eine solche Visualisierung.
Das letzte Anwendungsbeispiel, das hier angefuhrt wird, ist auch der bedeu-tendste Vorantreiber fur die gesamte Entwicklung des Lanschafts-Rendering. Eshandelt sich um die Computerspiele. Die Computerspiele haben in den letzen Jah-ren eine rasante Entwicklung hingelegt. Es werden naturgetreue Landschaften ge-neriert, um das Spielerlebnis zu steigern. Fruher wurde die weit entferne Umge-bung durch eingeblendete Bilder vorgetauscht und heute lassen sich große ”be-gehbare”Landschaften als Trend verzeichnen, wie in Abbildung 4 das abgebildeteSpiel Oblivion.
3 Technische Vorraussetzungen
Die eigentliche Schwierigkeit des Rendering von Landschaften ist die Menge derzu verarbeitenden Daten. Hinzu kommt noch, dass in der Regel nicht nur die Land-
1DLR-Instituts fur Robotik und Mechatronik Oberpfaffenhofen, 2008,http://www.virtuellesbayern.de/
23D Geo GmbH, http://www.3dgeo.de/server products.aspx3Wetterzentrale, http://www.wzforum.de/forum2/read.php?7,11800614http://i9.photobucket.com/albums/a61/jesterspaz/FixedTiling.jpg
4
Abbildung 5: Rendering Pipeline5
schaft, sondern auch viele andere Dinge, wie zum Beispiel Baume und Texturengerendernt werden sollen. Die Herausforderung liegt darin, die Menge an Datenintelligent zu speichern und zu verwalten. Ein wichtiges Verfahren dazu ist LOD,auf welches spater eingegangen wird.
In den letzten Jahren hat die Grafikhardware rasante Entwicklung hinterlegt. Esist mittlerweile so weit, dass die Leistung der Grafikkarten schneller zunimmt alsdie der CPU. Diese Entwickelung ist vor allem den Computerspielen zu verdan-ken. Heute besitzt nahezu jeder Computer eine sehr leistungsfahige Grafikkarte.Zusatzlich zu der erhohten Performance, sind die Grafikkarten programmierbar.Das bietet einer Landschaftsumsetzung eine hohere Flexibilitat. Die komplexenAnforderungen lassen sich direkt auf dem Grafikprozessor umsetzten, welche vor-her auf der CPU gelost wurden.
3.1 Rendering Pipeline
Die Abbildung 5 zeigt eine stark vereinfachte Rendering-Pipeline. Sie beschreibtden Weg zwischen einer mathematischen Beschreibung einer Szene, bis zu einemgerasterten Bild auf den Bildschirm. Die moderne Rendering Pipeline hat zwei pro-grammierbare Einheiten den Vertex Shader und den Fragmen-/Pixel Shader. DieseShader sind kleine Programme, die auf der Grafikhardware umgesetzt werden. Sieersetzen Teile der statischen Standart-Grafikpipeline.
Beim Rendering werden als erstes die Szenendaten durch Koordinatentrans-formation in zweidimensionale Projektion umgewandelt und danach kommt dieBeleuchtung. Mit dem Vertex Shader Programm lassen sich diese Schritte frei pro-grammieren, d.h. man kann auf der Geometrie frei operieren und die Attribute derVertices andern. Als nachstes folgt das Clippen, bzw. Verdeckungsrechnung im Ob-jektraum. Nach der Rasterung folgt der Fragmet-/Pixel Shader. Er operiert auf denBildpunkten der Szene und andert die Farbe der Bildpunkte, die auch Fragmentegenannt werden. Die Fragmente bestehen aus Farbe, Tiefe und Textur-Koordinaten,die sich durch Fragmet-/Pixel Shader modellieren lassen.
5Entnommen aus: http://www.linux-magazin.de/heft abo/ausgaben/2004/02/glaenzende effekte
5
3.2 Grafikhardware
Die modernen Grafikkarten sind extra fur das Rendern der Dreiecke optimiert undkonnen mehrere Millionen Dreiecke pro Sekunde darstellen. Betrachtet man dieaktuelle Grafikhardware mit Textur-Fullraten von rund 40 Mrd. Pixel pro Sekun-de genauer, so schatzt man die modernen Grafikkarten sehr hoch ein. Man konntedavon ausgehen, dass sie leistungsfahig genug sind, um den Bildschirm mit vie-len Dreiecken zu fullen. Wenn man wirklich eindrucksvolle Ergebnisse haben will,das heißt alles selbstverstandlich in Echtzeit und unter Verwendung von aufwendi-gen Shadern, Mip-Map-Texturfilterung, hohe Bildschirmauflosung etc, dann ver-braucht mal viele Ressourcen und selbst die schnellste verfugbare Grafikhardwarewird zu langsam.
3.3 Out-of-Core
Neben der Grafikkarte spielt selbstverstandlich der Speicher eine wichtige Rolle.Der Arbeitsspeicher ist ein entscheidender Faktor fur die Große eines Terrains. Daman in der Regel große Daten hat, kann man sie nicht gleichzeitig in den Haupt-speicher laden. Die Losung des Problems ist Out-of-Core Rendering. Mit Out-of-Core, ist es moglich die Daten zur Laufzeit des Programms von der Festplatte zuladen.
Einige Algorithmen ermoglichen eine Aufspaltung der Daten in Blocke. Furdie Aufspaltung gibt es verschiedene Verfahren, besonders geeignet sind dafur dieBaume. Die Aufspaltung ermoglicht, dass nur die wichtigsten Teile in den Ar-beitsspeicher geladen werden, d.h. nur die Blocke, die sich im Sichtfeld befinden.[VM02]
6
Abbildung 6: Hohentextur6
4 Grundlagen
4.1 Reprasentation der Daten
4.1.1 Hohentextur
Hohentextur, auch Heightmap genannt, besteht aus einem 2D-Array, jeder Wertstellt einen Hohenwert dar. Diese Hohenwerte werden in Graustufen in einer Texturgespeichert. Die Werte sind in Zeilen und Spalten angeordnet, wobei jedem Werteine y- und x-Koordinate zugeordnet wird. Normalerweise steht der Hohenwert 0,also Schwarz fur die Tiefe und Weiß mit 255 fur den hochsten Punkt. Der Vorteilsolcher Heightmaps ist, dass sie besonders fur große Terrains gut geeignet und rela-tiv leicht zu implementieren sind. Nachteil ist, dass man keine Felsvorsprunge oderHohlen erstellen kann. [Ape03, 795ff] Die Abbildung 6 zeigt die ”rohen”Daten ei-ner Heightmap und in Abbildung 7 werden diese Daten in einer Netzstruktur um-gesetzt.
Fur die Erstellung der Hohentextur gibt es verschiedene Verfahren. Es gibtzahlreiche Programme oder Algorithmen, mit denen man sich Daten ”per Zu-fall”generieren kann. Oder die Daten werden Mithilfe von Hohenmessverfahrenwie Schallwellenabtastung beschafft.
4.1.2 Rastergelandemodell
Um die definierten Hohenwerte in 3D anzeigen zu konnen, benotigt man dafureine geeignete Geometrie, die diese Punkte verbindet. Die Landschaft lasst sichaus regelmaßigen Vertices generieren. Beim Aufbau des Terrains werden jedesHohenwert aus der Hohentextur einem Vertex zugeordnet. Dabei bilden die Hohenwerte
6Wikipedia, http://en.wikipedia.org/wiki/Heightmap7Wikipedia, http://en.wikipedia.org/wiki/Heightmap
7
Abbildung 7: Gerenderte Hohentextur7
die z-Koordinaten fur das Rastermodell. Je geringer der Abstand zwischen denWerten, desto hoher ist die Auflosung. Nachteil dieses Verfahrens ist, dass relativviele uberflussige Informationen entstehen konnen. Wenn man eine große, glatteFlache hat, wird sie durch viele Punkte dargestellt, was man sich theoretisch sparenkonnte. Eine weitere Schwache des Rastermodells ist der Aufwand fur die Verbes-serung der Details. Will man nur eine bestimmte Stelle verfeinern, muss man dieglobale Verfeinerung des Rasters erhohen.
4.1.3 Dreiecksvermaschung
Die Dreiecksverschmaschung, auch Triangulated Irregular Network (TIN)genannt,stellt eine Alternative zum Rastergelandemodel dar. Die Oberflache wird durch vie-le Punkte konstruiert, diese Punkte sind unregelmaßig angeordnet. Auf diese Weiseist es moglich eine beliebige Gelandeform zu modellieren. [UNI08] Anschließendwerden die Punkte zu einem Netz trianguliert. Abbildung 8 zeigt die Umsetzungdes Triangulated Irregular Networks. Man erhalt eine niedrigere Stutzpunktzahl,die Stutzpunkte lassen eine genauere Annahrung an das gewunschte Landschafts-modell. Nachteilig ist, dass fur die hohe Detailliertheit der Oberflache, eine rechen-intensive Speicherstruktur und komplizierte Verarbeitungsalgorithmen benotigt wer-den.
4.1.4 BinTree
Eine Netzstruktur kann man auch durch einen Binarbaum ermoglichen. Der Auf-bau ist folgender: Jeder Knoten hat zwei Kinder, die Knoten und Kinder bilden die
8Hoppe, Smooth view-dependent level-of-detail control and its application to terrain rendering,1998
8
Abbildung 8: Triangulated Irregular Network8
Abbildung 9: BinTree9
Abbildung 10: Mesh aus BinTree 10
Dreiecke der Netzstruktur. Jeder Knoten wird rekursiv einem Dreieck zugeordnet.Im ersten Schritt besteht die Struktur aus zwei Dreiecken, die die gesamte Land-schaft bedecken. Die beiden Dreiecke werden jeweils in zwei weitere aufgeteilt.Und so wird das Verfahren fortgesetzt, dabei teilt man nur die Knoten zu weiterenUnterknoten auf, die eine hohere Auflosung im Terrain erzeugen sollen. Abbildung9 stellt eine vereinfachte Darstellung des Aufbaus von dem BinTree und in der Ab-bildung 10 ist das mogliche Gesamtergebnis veranschaulicht.Bei der Umsetzung muss beachtet werden, dass die gemeinsamen Kanten der Un-terknoten im Verhaltnis zu den Nachbarknoten stehen.
9GISWIKI, http://en.giswiki.org/wiki/Bintree10Brunet und Fellner, Batched Dynamic Adaptive Meshes for High Performance Terrain Visuali-
zation, 2003
9
Abbildung 11: QuadTree 11
4.1.5 Quadtrees
Ein Quadtree folgt einem ahnlichen Prinzp wie beim BinTree. Um die Netzstrukturzu konstruieren, ordnet Quadtree vier Kinder einem Knoten zu. Auch hier stelltdie Wurzel eines Quadtrees die gesamte Flache eines Landschaftsmodells dar, dierekursiv in viele verschiedene Dreiecke zerlegt wird. Die Vorgehensweise bei derZerlegung eines solchen Netzes ist in Abbildung 11 Schritt fur Schritt dargestellt.
4.2 Level of Detail
4.2.1 Problemstellung
Bei der Reprasentation von Landschaften fallen große Datenmengen in Form vonDreiecken und Texturen an. Damit das Terrain in der Anwendung gut aussieht musses moglichst hoch aufgelost sein, die Meshstruktur soll vom Anwender nicht alssolche wahrgenommen werden und die Textur muss noch aus der Nahe scharf wir-ken.
Gleichzeitig fuhrt eine Erhohung der zu rendernden Dreiecke zu einer pro-portional dazu sinkenden Framerate. Es ist also, im Besonderen fur echtzeitfahigeAnwendungen, unumganglich die Anzahl der zu rendernden Dreiecke (und der zuladenden Texturen) moglichst gering zu halten.
4.2.2 Verfahren
Um diese Diskrepanz zwischen Qualitat und Performanz zu reduzieren gibt es ver-schiedene Ansatze. Einer der wichtigsten ist Level of Detail.
Hierbei macht man sich zu nutze, dass ein hoher Detailgrad von Geometrie undTextur lediglich im Nahbereich des Betrachters erforderlich ist. Im Fernbereich istdieser Detailgrad nicht notig. Hier werden sonst bei der Texturierung mehrere Texelauf ein Pixel abgebildet oder bei der Geometrie gar mehrere Dreiecke pro Pixelgerendert. Es werden also unnotig Dreiecke gerendert und unnotig große Texturengeladen.
Anstatt die selben Modelle zu verwenden mussen, abhangig von der Entfer-nung, Modelle mit angepasstem Detailgrad verwendet werden.
11http://groups.csail.mit.edu/graphics/classes/6.837/F98/talecture/
10
Abbildung 12: View Frustum [SWND04]
4.2.3 Probleme
Der Fehler zwischen den Modellen verschiedener Detailstufen muss moglichst ge-ring sein, da sonst ein Unterschied in der Wahnehmung entsteht.
Besonders bei zu wenigen Detailstufen lasst sich der so genannte Popping Ef-fect, ein wahrnehmbarer Unterschied zwischen den Detailstufen nicht verhindern.Erfolgt ein Wechsel des Modells, kann das plotzliche Verschwinden oder Erschei-nen von Details wahgenommen werden.
Ein weiteres Problem ergibt sich durch die große Ausdehnung der Geometrie.Wahrend Modelle in der Regel als Ganzes in einer Detailstufe dargestellt wer-den, liegen verschiedene Teile des Terrains immer im Nah- und Fernbereich desBetrachters. Level of Detail kann also nicht auf das ganze Terrain angewendet wer-den. Das Terrain muss vorher in mehrere Blocke unterteilt werden. Dabei entste-hen “Bruche“ zwischen benachbarten Blocken, die einer gesonderten Behandlungbedurfen.
4.3 View Frustum Culling
4.3.1 View Frustum
Das View Frustum(siehe Abbildung 12) ist der von der Kamera aufgespannte Py-ramidenstumpf, der den poteltiell sichtbaren Bereich in einer Szene definiert.
Er entsteht durch die vier Seitenflachen, gegeben durch den Offnungswinkelder Kamera und der Far- und Nearplane welche den sichbaren Bereich weiter ein-schranken. Fur Landschaften sollte die Farplane sehr weit von der Kamera posi-tioniert, bzw. auf Unendlich gestellt werden. Ansonsten passiert es, dass Teile derLandschaft plotzlich aus dem Nichts auftauchen.
11
4.3.2 Verfahren
Der vom View Frustum erfasste Bereich ist nur ein Ausschnitt aus der Szene. Ob-jekte, die außerhalb des Frustums liegen sind nicht sichtbar. Sie werden nicht ge-rendert und mussen daher nicht an die Grafikkarte ubermittelt werden. Man solltealso die Objekte einer Szene darauf testen, ob sie außerhalb des Frustums liegen.
Dabei ware es viel zu aufwendig ein Objekt Dreieck fur Dreieck zu testen.Stattdessen werden Naherungen des Objekts getestet, zum Beispiel Bounding Bo-xes.
4.3.3 Probleme
Wie bei Level of Detail kann auch bei View Frustum Culling im Falle eines zusam-menhangenden Terrains nicht das ganze Objekt getestet werden. Teile des Terrainssind immer sichtbar. Auch hier muss das Terrain in mehrere Blocke unterteilt wer-den.
Fur die Blocke bieten sich Bounding Boxes als Naherung an. Falls das Terrainnoch parallel zu den Achsen ausgerichtet ist, lasst sich der Test durch Axis AlignedBounding Boxes noch weiter vereinfachen.
Um den Test noch effizienter zu gestalten, sollten die Blocke in eine hierarchi-sche Struktur gebracht werden. So mussen nicht alle Blocke der untersten Ebenegetestet werden, ist ein Block einer hoheren Ebene außerhalb des Frustums, sindes auch alle enthaltenen Blocke niedrigerer Ebene.
4.4 Texturierung
4.4.1 Texturskalierung
Wird fur die Texturierung eine zu ungenaue Textur verwendet, wirkt diese un-scharf. Bei zu fein aufgelosten Texturen konnen Antialiasing Effekte auftreten undes wird eine unnotig große Textur geladen. Die richtige Skalierung von Texturenist daher sehr wichtig.
Als Grundregel fur die Genauigkeit gilt, mindestens ein Texel pro sichtbaremPixel darzustellen. Und nach Moglichkeit auch nicht mehr.
4.4.2 Mip Mapping
Eine hierfur geeignete Losung ist das Mip Mapping. Dabei werden verschiedeneDetailstufen einer Textur berechnet. Die Kantenlange einer Textur muss hierfur ei-ne 2er-Potenz sein. Zur Berechnung der nachstkleineren Textur kann zum Beispieljeweils der Mittelwert aus 4 benachbarten Pixeln gebildet werden.
Je nach Abstand und damit benotigter Detailstufe wird die passende Textur-große gewahlt. Dieses Verfahren wird bereits von der GPU unterstutzt und kannsomit leicht umgesetzt werden.
12
Abbildung 13: Mip Mapping [wik]
4.4.3 Multitexturing
Ein hafig verwendetes Verfahren bei der Texturierung ist das Multitexturing [Bar06].Dabei werden mehrere Texturen, statt einer verwendet. Das sind beim Terrain meis-tens eine grobe Untergrundtextur fur die allgemeine Farbverteilung des Gelandes.Dazu kommen Texturen fur feinere Strukturen wie Geroll, Sand, Dreck oder Ve-getation. Diese werden uberlagert und deren Gewichtung, je nach gewunschtemEffekt, angepasst.
So konnen mit relativ kleinen Texturen Zahlreiche Bereiche des Terrains abge-deckt werden. Es entstehen jedoch Probleme bei der Wiederholung der Texturen.Diese “Nahte“ mussen mit Uberblendung kaschiert oder durch nathlose Texturenvermieden werden.
Ein weiteres Problem bei der Wiederholung der Texturen ist, dass diese ein re-gelmaßiges und wahrnehmbares Muster hervorruft. Um diesen unnaturliche Effektzu minimieren sollten die Texturen verschiedene Großen aufweisen und versetztuberlagert werden. So ist der Abstand in denen sich alle Texturen wiederholen vielgroßer.
13
Abbildung 14: Multitexturing in UT2004 [Vot08]
Abbildung 15: Quadtree Level 0 [Ulr02]
5 Algorithmen
5.1 Chunked Level of Detail
5.1.1 Chunked Level of Detail Control
Das Verfahren Chunked Level of Detail wurde 2002 von Thatcher Ulrich in demPaper “Rendering Massive Terrain using Chunked Level of Detail Control“ [Ulr02]vorgestellt. Es handelt sich dabei um einen Algorithmus, der blickrichtungsabhangigDetailstufen auf eine Menge von Primitiven anwendet.
5.1.2 Vorverarbeitung
In einem Vorverarbeitungschritt wird ein Quadtree aufgebaut. Jeder Knoten enthaltein Mesh, dieses Dreiecksnetz wird auch Chunk genannt.
Der Wurzelknoten enthalt ein gering aufgelostes Mesh des ganzen Terrains.Jeder Kindknoten reprasentiert ein Viertel des Chunks des Elternknotens in einerhoheren Auflosung. Rekursiv wird so das Terrain bis zur festgelegten Rekursions-tiefe in steigenden Detailstufen vom Baum reprasentiert. Jeder Chunk ist ein un-abhangiger, statischer Verbund von Primitiven und kann uber einen einzigen Befehlan die GPU ubergeben werden.
15
Abbildung 16: Quadtree Level 1 [Ulr02]
Abbildung 17: Quadtree Level 2 [Ulr02]
16
Abbildung 18: Quadtree Level 3 [Ulr02]
5.1.3 Einsatz
Zum Rendern des Terrains wird der Quadtree traversiert. Es wird gestetet, ob dieDetailstufe des Knotens groß genug ist, er also fur die Darstellung geeignet ist.Dazu wird ein Fehlermaß berechnet welches unterhalb eines festgelegten Schwell-wert liegen muss. Liegt der Fehler unterhalb des Schwellwerts, wird der Chunk andie GPU Ubergeben. Liegt er oberhalb, werden die Kindknoten untersucht. Ist diehochste Detailstufe erreicht, wird diese verwendet.
Die Wahl des Schwellwerts ist entscheidend fur die Qualitat.
5.1.4 Selektionskriterium fur die Detailstufe
Als variable Großen fließen in die Berechnung des Fehlermaßes der Abstand zumbetrachteten Chunk und die Neigung der Kamera ein.
Errorpixel = Errormax ×DistFarplane
DistChunk︸ ︷︷ ︸Errorprojected
× HeightWindow
HeightFarplane×sin(vAngleCamera)
Errorpixel : Pixelfehler (Selektionskriterium)Errormax : Maximaler Fehler des betrachteten Chunks
17
Abbildung 19: Crack Filling [Ulr02]
DistFarplane : Abstand zur Farplane des View FrustumsDistChunk : Abstand zum betrachteten ChunkHeightWindow :Hohe des DarstellungsfenstersHeightFarplane :Hohe der Farplane des View FrustumsvAngleCamera : Neigung der Kamera
Der Abstand ergibt sich aus der perspektivischen Projektion als Kriterium furden benotigten Detailgrad. Je weiter etwas entfernt ist, desto kleiner erscheint esim Bildausschnitt.
Bei Terrain ist aber auch der Neigungswinkel fur ein noch effizienteres Levelof Detail zu berucksichtigen. Betrachtet man die Geometrie von der Seite, sinddie Hohenunterschiede deutlich zu sehen. Blickt man dagegen senkrecht von oben,lassen sich diese kaum noch ausmachen.
5.1.5 Crack Filling
Zwischen benachbarten Chunks mit unterschiedlichen Detailstufen konnen Locherentstehen, die als schwarze, oder je nach Hintergrundfarbe blaue Pixel sichtbar seinkonnen.
Um diese zu schließen wird der Chunk am Rand um einen vertikalen trian-gle strip erweitert (siehe Abbildung 19). Da die Locher in der Regel nur ein oderwenige Pixel groß sind, und Terrain relativ ungleichmaßig texturiert ist, ist dieseLosung ausreichend um die Fehler zu kaschieren.
5.1.6 View Frustum Culling und Textur
Der fur den Level of Detail verwendete Quadtree kann analog fur View FrustumCulling genutzt werden. Fur jeden Chunk wird im Baum eine Bounding Box ge-speichert. Der Baum wird schließlich rekursiv durchlaufen und die Chunks auf ihreLage bezuglich des View Frustums gepruft.
Die Auswahl der richtigen Detailstufe der Textur erfolgt ebenfalls analog uberden Quadtree, lediglich das Selektionskriterium muss angepasst werden. Die Re-kursion wird durchlaufen, bis mindestens ein Texel pro Pixel dargestellt wird.
18
5.1.7 Bewertung
Vorteile:
• Effizienter Einsatz von Dreiecken.
• Geringe Auslastung der CPU.
• LoD der Geometrie und der Textur erfolgt analog.
• Kann um Morphing erweitert werden um Popping Effect zu verhindern.
Nachteile:
• Aufwendige Vorverarbeitung notig.
• Daten mussen statisch sein.
• Nicht optimale Anzahl an Dreiecken.
5.2 Geometric Mipmapping
5.2.1 Geometric Mipmapping
Das Verfahren Geometric Mipmapping wurde 2000 von Willem H. de Boer in demPaper “Fast Terrain Rendering Using Geometric MipMapping“ [dB00] vorgestellt.
Es handelt sich dabei um einen Algorithmus, der blickrichtungsabhangig De-tailstufen auf eine Menge von Primitiven anwendet.
5.2.2 Vorverarbeitung
In einem Vorverarbeitungschritt werden die gegebenen Terraindaten in viele gleichgroße quadratische Blocke unterteilt.
Die Kantenlange l dieser Blocke muss die Form l = 2n +1 mit n ∈ N+ haben.Auf der untersten Ebene hat das Mesh die hochste Auflosung. Analog zum MipMapping bei Texturen wird schrittweise die Auflosung der Blocke reduziert indemin x- und y-Richtung jeder zweite Hohenwert weggelassen wird. So entstehen furjeden Terrainblock n Meshes mit jeweils geringer werdender Detailstufe.
5.2.3 Einsatz
Zum Rendern des Terrains wird fur jeden Terrainblock die passende Detailstufeermittelt. Es wird gestetet, ob die Detailstufe des Meshes der hochsten Ebene großgenug ist, er also fur die Darstellung geeignet ist. Dazu wird ein Fehlermaß be-rechnet welches unterhalb eines festgelegten Schwellwerts liegen muss. Liegt derFehler unterhalb des Schwellwerts, wird das Mesh an die GPU Ubergeben. Liegter oberhalb, wird das Mesh an der nachsten Detailebene betrachtet. Ist die hochsteDetailstufe erreicht, wird diese verwendet.
Die Wahl des Schwellwerts ist entscheidend fur die Qualitat.
19
Abbildung 20: Geo Map Level 0 und 1 [dB00]
5.2.4 Selektionskriterium fur die Detailstufe
Als Selektionskriterium kann die selbe Fehlerberechnung wie im Chunked Level ofDetail Algorithmus dienen.
Vereinfacht man jedoch die Formel, indem der Neigungswinkel der Kameraaußer Acht gelassen wird, so lasst sich die Berechnung in den Vorverarbeitungs-schritt verlagern. In einer LUT (Look-Up Table) wird gespeichert ab welchem Ab-stand welche Detailstufe zu verwenden ist. Wahrend des Rendern muss nur nochder Abstand ermittelt werden, die CPU wird weiter entlastet. Dies geht jedoch aufKosten der GPU, da das Fehlermaß weniger genau die gegebene Situation beurteiltund somit im Zweifelsfall mehr Dreiecke gerendert werden mussen.
5.2.5 Geometry Gaps
Auch bei diesem Verfahren konnen zwischen benachbarten Meshes mit unterschied-lichen Detailstufen Locher entstehen.
Um diese zu schließen, wird der Randstreifen des hoher aufgelosten Meshes soangepasst, dass er mit dem des niedriger aufgelosten ubereinstimmt (siehe Abbil-dung 21).
5.2.6 View Frustum Culling und Textur
Fur das View Frustum Culling werden fur die Blocke Bounding Boxes berechnet.Diese sollten fur eine Effizientsteigerung in einer hierarchischen Struktur, z.B. ei-nem Quadtree weiter zusammengefasst werden.
Die Texturauswahl erfolgt analog zum Geometric Mipmapping.
20
Abbildung 21: Crack Filling [dB00]
Abbildung 22: Morphing [dB00]
5.2.7 Morphing
Um beim Wechsel der Detailstufen einen Popping Effect zu verhindern kann dieVeranderung hin zur nachsten Detailstufe langsam erfolgen.
Dabei wird nicht abrupt zwischen den Detailstufen gewechselt, sondern inter-poliert (siehe Abbildung 22).
Die Eckpunkte der hoher aufgelosten Detaistufe nahern sich immer weiter derOberflache der nierigeren Detailstufe bis das Fehlermaß greift und auf die niedrigeDetailstufe umgestellt werden kann.
5.2.8 Bewertung
Vorteile:
• Sehr geringe Auslastung der CPU.
• Vorverarbeitung nicht sehr aufwendig.
• Kann auf dynamische Daten erweitert werden.
• Kann einfach um Morphing erweitert werden um Popping Effect zu verhin-dern.
Nachteile:
• Relativ hohe Anzahl an Dreiecken, hohere Belastung der GPU.
21
Abbildung 23: Aufbau der Geometry Clipmaps 12
5.3 Geometry Clipmap
Der Geometry Clipmap Algorithmus wurde von Frank Losasso und Hugeues Hop-pe im Jahr 2004 veroffentlicht.[LH04] Ein Jahr darauf hat Hoppe in Zusammenar-beit mit Arul Asirvatham ein GPU basiertes Geometry Clipmap veroffentlicht.[AH05]Dieser Abschnitt behandelt die Algorithmen aus diesen beiden Papers.
Geometry Clipmap ist ein einfacher Algorithmus, der bezogen auf die Drei-ecke weitgehend eine optimale Ausnutzung des Grafikprozessors hat. Dank desAufbaus der Netzstruktur erhalt man eine konstante Renderrate. Der Algorithmusbietet zahlreiche Einsatzgebiete wie Filme, Kartografie und Spiele.
5.3.1 Prinzip
Man hat eine Art Ringe aus verschachtelten Rechtecken um den Betrachter herum.Somit wird die weiter weg entfernte Netzstruktur grober. Es gibt m quadratischeLevel und jedes Level hat eine Große von 2m. Dabei ist 0-te die innerste und m−1die außerste Ebene. Die Große der Dreiecke verdoppelt sich von Level zu Level,so dass die grobere Netzstruktur mehr Flache abdeckt. Ein Clipmap-Level bestehtaus einem n ∗ n Array von Vertices. Je mehr Level man verwendet, desto mehrDetailstufen erreicht man. Die Kamera befindet sich im Zentrum aller Level unddie feineren Netze sind teilweise uberdeckend zu den groberen.[Kle05]
Der grundlegende Gedanke ist, dass die Dreiecke der Große eines Bildpunktesauf dem Bildschirm entsprechen, so dass bei der Rasterisierung alle Dreiecke etwadie gleiche Große haben.
5.3.2 Hohendaten
Die Hohendaten werden in einer 2D-Textur gespeichert, zudem werdenvdiese vondem Grafikprozessor auf die Netzstruktur ubertragen. Die Koordinaten aus der Tex-
12Hoppe, 2004
22
tur mussen fur den jeweiligen Level komprimiert werden. Diese Aufgabe ubernimmtder Vertex Shader. Dadurch, dass die Textur fur aktuellen und groberen Level dieHohenwerte enthalt, werden die Texturzugriffe erspart.
5.3.3 Interaktion
Das Drehen und Neigen der Kamera, sowie Verschiebung entlang der y-Achse ge-schieht einfach uber Modelview Matrix.[Kle05] Wenn man sich auf der y-Achsebewegt, kann die Detailstufe der Clipmaps abnehmen, außerdem je hoher die Ka-mera uber die Landschaft schwebt, desto grober kann die Netzstruktur gewahltwerden. Die Bewegung entlang der x-z-Achse ist etwas schwieriger, da die Ka-mera immer in der Mitte der Clipmaps bleiben muss. Wahrend sich die Kamerabewegt, mussen die Inhalte der Hohentextur aktualisiert werden. Mithilfe der Tran-sition wird die reibungslose Bewegung zwischen den Hohenpunkten erreicht. DieClipmaps haben eine Große von 2n − 1 Vertices, damit ist die Kamera nie genauin der Mitte und bewegt sich zwischen 2 Punkten. Die Bewegung innerhalb derClipmaps ist nach außen zu den groberen Clipmaps geringer, dadurch werden dieHohendaten fur grobere Levels seltener aktualisiert.
5.3.4 Ubergangszonen
Ein Problem von GeoClipping sind Artefakte, die bei den Levelubergangen ent-stehen. Diese außern sich durch Lucken und durch ein Ruckeln der Geometrie anden Ubergangen, was durch die unterschiedliche Auflosung an den Levelgrenzenerzeugt wird.
In Abbildung 11 ist die Problematik des Meshes an den Levelubergangs ver-deutlicht. Es sind zwei Netze zu sehen eins in grun und das andere in blau, da dasnachste Level (grun) doppelt so grob ist, verliert sich ein Vertex und es entsteht einLoch.
Das Problem lasst sich losen in dem man eine Uberblendung an den Randernerzeugt. An den Levelubergangen werden Ubergangszonen generiert, in denen zwi-schen den Levelstufen ubergeblendet wird. Die groberen Stufen werden von de-taillierteren Regionen uberlappt, die Uberlappung nimmt in dem Alphakanal nachaußen ab.
In Abbildung 12 zeigt das erste Bild die Problematik ohne Transition und dasBild in der Mitte zeigt dieselbe Landschaft mit der transitionierten Geometrie undschließlich das rechte Bild zeigt die Ausfuhrung mit der transitionierten Geometriemit zusatzlich transitionierten Textur, was eine Vermeidung des Ruckeln zur Folgehat.
13Hoppe, 2005
23
Abbildung 24: Ubergangszonen 12
Abbildung 25: Mesh
5.3.5 View Frustum Culling
Die Clipmaps lassen sich jeweils in 4 Vierecke unterteilen, abgesehen von dem0-ten Clipmap. Alle Blocke der Clipmaps werden als Vertex Array ausgegeben.Befindet sich ein Block außerhalb der nicht sichtbaren Region, wird es nicht ge-zeichnet. Der Anteil der geladenen Landschaft hat eine L-formige Form. Damitwerden die Ressourcen des Computers geschont, da die Arbeitsspeicherbelegunggeringer weniger wird.
24
Abbildung 26: Aufteilung der Clipmaps in Blocke
Literatur
[AH05] Arul Asirvatham and Hugues Hoppe. Terrain rendering using gpu-based geometry clipmaps, 2005.
[Ape03] Marius Apetri. 3D-Grafik Programmierung. mitp-Verlag, 2003.
[Bar06] Robert Barz. In Effizientes Rendering von Landschaften. UniversitatKoblenz-Landau, 2006.
[dB00] Willem H. de Boer. In Fast Terrain Rendering Using GeometricalMipMapping. E-mersion Project, 2000.
[fRuMiO08] DLR Instituts fur Robotik und Mechatronik in Oberpfaffenhofen.Virtuelles bayern. http://www.virtuellesbayern.de/,2008.
[Kle05] Michael Kleiber. Terrain terrain rendering using geometric clipmaps.http://isgwww.cs.uni-magdeburg.de/˜spindler/wiki/ShaderSeminar2005/index.php?n=Projects.TerrainRendering, 2005.
[LH04] Frank Losasso and Hugues Hoppe. Geometry clipmaps: Terrain ren-dering using nested regular grids, 2004.
[SWND04] Dave Shreiner, Mason Woo, Jackie Neider, and Tom Davis. Theofficial guide to learning opengl. In OpenGL Programming Guide.Addison Wesley, 2004.
[Ulr02] Thatcher Ulrich. In Rendering Massive Terrains using Chunked Le-vel of Detail Control. Odworld Inhabitants, 2002.
[UNI08] UNIGIS. Triangulated irregular network. http://www.unigis.ac.at/fernstudien/UNIGIS_professional/schnupper/schnuppermodul/html/lektion5/p1.htm,2008.
[VM02] Gokul Varadhan and Dinesh Manocha. Department of computerscience. Out-of-Core Rendering of Massive Geometric Environ-ments, 2002.
[Vot08] Raffael Votter. The most beautiful textures in games, 2008.
[wik] wikipedia. In http://en.wikipedia.org/wiki/Image:MipMap_Example_STS101.jpg.
26
