Terrain 101

Dieser Artikel wird gerade geschrieben bzw. bearbeitet und erfüllt noch nicht die Qualitätsstandards von indiedev. Bitte bearbeite diesen Artikel nur, wenn du kleine Fehler korrigieren möchtest oder der Autor bist.

Terrain 101
Eine Einführung in dreidimensionale Landschaften in Echtzeit
Autor	Roland "Glatzemann" Rosenkranz
Programmier­sprache	C#
Kategorie	XNA
Diskussion	Thread im Forum
Lizenz	indiedev article license
Terrain 101 auf MitOhneHaare.de

Eine Einführung in dreidimensionale Landschaften in Echtzeit

Besonders Anfänger in der Spieleentwicklung sind immer wieder fasziniert von dreidimensionalen Landschaften, die in Echtzeit berechnet und dargestellt werden. So interessant dieses Themengebiet auch sein mag, so wenig geeignet ist es eigentlich für den Einsteiger. Für ein realistisches Terrain muss man bereits einiges an Arbeit investieren und eine ganze Menge von Techniken beherrschen, damit man zum Ziel kommt. Auf den ersten Blick - und das suggerieren die meisten anderen Tutorials - ist es sehr einfach, so eine Landschaft zu generieren. Schnell hat man ein ansehnliches Ergebnis erzielt, daß aber für den Real-Life-Einsatz in einem Spiel wenig geeignet ist und auch größere Terrains sind mit diesen meist sehr einfachen Techniken nicht möglich. Schnell fangen dann die Probleme an und der Einsteiger fühlt sich überfordert und verliert sein Ziel aus den Augen. Dies ist zum lernen natürlich nicht hilfreich und frustriert.

Ich möchte mit dieser Artikelreihe dagegen vorgehen und daher über das übliche Ziel anderer Tutorials weit hinausgehen. Ich möchte sowohl dem Einsteiger, als auch dem Fortgeschrittenen eine Menge Informationen an die Hand geben, die es ihm ermöglichen wird, sein eigenes Terrain zu entwickeln und versuche dies so einfach wie möglich, aber auch so effektiv wie möglich zu gestalten.

Ich möchte an dieser Stelle direkt anmerken, daß diese Artikelreihe noch nicht zuende geschrieben ist. Wer morgen oder übermorgen ein Terrain benötigt, der sollte nicht auf mich warten, denn ich kann jetzt weder sagen, wieviele Artikel ich zu diesem Thema schreiben werde, noch wielange dies dauern wird. Wer jedoch nebenher Entwickeln möchte, oder einfach nur etwas lernen möchte, wenn es etwas Neues gibt, der ist hier an der richtigen Stelle.

Ich werde in diesem Artikel eine Art Inhaltsverzeichnis pflegen, die auf die Folgeartikel verweisen wird. Dieses Inhaltsverzeichnis ermöglicht die schnelle und einfache Navigation zwischen den Artikeln und man kann leicht einzelne Themengebiete wiederfinden und auch Dinge, die man bereits beherrscht überspringen.

Das Inhaltsverzeichnis

• Die Entwicklungsumgebung und das XNA 4.0 Projekt
• Das erste Dreieck
• Transformationen
• Vertex- und Index-Buffer
• Land in Sicht
• Technische Rafinessen
• Neue Sichtweisen
• Kamera ab und Action
• Bessere Struktur durch Refactoring

Los gehts...

In diesem ersten Artikel möchte ich noch keinen Code vorstellen und auch noch nicht wirklich auf technische Themen detailliert eingehen. Ich möchte ein paar Worte zum Thema im Allgemeinen verlieren und ich möchte ein paar grundlegende Entscheidungen anreißen, die für ein Terrain wichtig sind. Auch möchte ich ein paar Begrifflichkeiten erklären bzw. nennen, die vorab interessant sind und es mir ermöglichen, daß ich in späteren Artikel keine langwierigen Erklärungen mehr vornehmen muss. Die Folgeartikel werden dadurch viel flüssiger zu lesen sein.

Die Grundlagen

Um eine "vollständige" 3D-Tutorial-Reihe zu haben, werde ich mich anfangs ein wenig über die absoluten Grundlagen auslassen. Ich werde Fragen wie

• Wie funktioniert 3D-Grafik?
• Was ist ein Shader?
• Wie stelle ich ein Dreieck dar?
• Wozu sind World-, View- und Projection-Matrix da?
• Was ist Vertex- und Index-Buffer?

aufarbeiten und erklären.

Ein wenig habe ich dazu schon im ein oder anderen Artikel in meinem Blog geschrieben, aber ich werde das noch etwas ausführlicher beschreiben bzw. chronologisch sinnvoll verlinken, damit dieser Abschnitt vollständiger wird und es auch dem absoluten Einsteiger ermöglicht, sich auf ein Level zu arbeiten, daß ihm das notwendige Verständnis zur Entwicklung eines 3D-Terrains gibt.

Wer an eine 3D-Landschaft denkt, der denkt oft an wunderschöne Hügel mit interessanten Tälern und schneebedeckte Bergspitzen. Schier endlose Weiten, die flüssig dargestellt werden und eine fast fotorealistische Qualität haben. Echtzeit-Beleuchtungseffekte werfen wohl definierte, aber weiche Schatten in die Täler und die Sonne wander über den Horizont und geht langsam hinter einer Bergspitze unter. Bäume und Berge spiegeln sich in Wellen, die ein See in einem der Täler sanft durch seine Wellen verzerrt.

Sowas werden wir machen :-)

Die Geometrie

Man merkt schon, daß dies ziemlich hoch gesteckte Anforderungen sind und daß wir vermutlich eine Menge von Dreiecken benötigen, um ein Gitternetz zu erzeugen, daß so eine Landschaft darstellen kann. Dies ist auch richtig und dies ist auch unsere erste Herausforderung. Ein Gitternetz oder Mesh zu erzeugen, daß den notwendigen Detailgrad aufweist ist ziemlich einfach z.B. mit einer Heightmap zu realiseren. Das Problem dabei ist, daß auch aktuelle Grafikkarten damit an die Leistungsgrenze stoßen. Dies bedeutet, daß es nicht möglich ist, ein perfektes Mesh für eine Landschaft mit hohem Detailgrad zu erzeugen und dies einfach so darzustellen. Bei gutem Wetter hat man eine Sichtweite von durchaus 10.000m und wenn man ein realtiv detailliertes Mesh mit einer Kantenlänge von 10cm hat, dann müsste man bereits 100.000 x 100.000 Rechtecke haben, die jeweils aus zwei Dreiecken bestehen. Wer schnell nachrechnet, der kommt dabei auf ca. 20 Milliarden Dreiecke. Auch wenn Grafikkarten durchaus in der Lage sind 200.000.000 (200 Millionen) Dreiecke zu rendern (wobei dies eher ein theoretischer als ein Real-Life-Wert ist), hätten wir noch 100x soviele Dreiecke, wie überhaupt möglich sind. Auch wenn man nur den sichtbaren Ausschnitt dieser Landschaft nehmen würde, dann hätten wir noch immer ca. 7-8 Milliarden Dreiecke zu rendern und in diesem Fall dürfte man sich dann nicht mehr bewegen, da sonst die Ränder sichtbar würden.

Um diese Anzahl der Dreiecke zu senken gibt es zwei Strategien, die wir beide anwenden müssen und auch werden.

Das Culling

Die erste Möglichkeit zur Senkung der Anzahl der Dreiecke, die gerendert werden müssen ist das sogenannte Culling. Beim Culling stellen wir sicher, daß möglichst wenig Dreiecke zum Rendern vorgemerkt werden. Dabei muss eine möglichst gute Balance zwischen dem Aufwand für das Culling und der Genauigkeit erreicht werden. Das Culling wird - bis auf wenige Ausnahmen - von der CPU vorgenommen, kostet also Rechenzeit. Algorithmen zum Culling können ziemlich aufwendig sein und CPU-Zeit ist kostbar. Wenn wir zuviel cullen, dann hat zwar die Grafikkarte wenig zu tun und könnte schnell rendern, aber die CPU ist eventuell überlastet und hat keine Zeit mehr, Render-Befehle an die Grafikkarte zu senden. Dies ist unterm Strich genauso wenig zielführend, als einfach zu viele Dreiecke an die Grafikkarte zu schicken.

Glücklicherweise gibt es eine ganze Menge von Algorithmen, wie man dieses Problem angehen kann. Ein paar Schlagworte sind Hardware Occlusion Culling, QuadTree, Octree, Tiling, Horizon Culling, PVS und viele mehr. Einige Terrain-Algorithmen unterstützen das Culling, andere enthalten es sogar implizit und bei anderen ist man vollkommen auf sich selbst gestellt. Ich werde jedenfalls mindestens einen Artikel dem Culling widmen, so daß wir danach in der Lage sind, dies effektiv anzuwenden.

Der LOD - Level of Detail

Eine Landschaft hat eine Charakteristik, die sehr gut für LOD geeignet ist. Wir sehen gleichzeitig Bereiche, die sehr nah an der virtuellen Kamera sind und Bereiche, die viele hundert oder gar tausend Meter entfernt sind. Bereiche die der Kamera nah sind benötigen einen höheren Detailgrad als entferntere Bereiche. Einzelne Steine oder Grashalme und jede kleine Felsspalte sieht man auf hundert Meter Entfernung nicht mehr. Und auf 2500 Meter Entfernung sieht man nur noch Silhouetten. Dies können wir uns zunutze machen und so ganz massiv Dreiecke sparen. Wir können dies nicht verwenden, wir müssen es sogar verwenden. Ohne LOD werden wir nur in der Lage sein, sehr kleine Terrains zu realisieren und das wollen wir ja schliesslich nicht.

Bei den LOD-Algorithmen - die das wichtigste und durchaus auch das Schwerste des 3D-Terrains sind - gibt es eine ganze Reihe von Algorithmen, die seit den späten 70ern bzw. den frühen 80ern entwickelt wurden. Mit der Entwicklung der Grafikkarten haben sich diese Algorithmen ganz massiv geändert und weiterentwickelt.

Es gibt grundsätzlich zwei Bereiche von Algorithmen. Einmal die Algorithmen, die eine Pre-Processing-Step benötigen und diese vorberechneten Daten auf die Festplatte speichern und zum anderen die Algorithmen, die alles in Echtzeit berechnen können. Erstere haben einen entscheidenden Vorteil: Es können deutlich komplexere Methoden zur Erkennung von Details angewendet werden und das Mesh kann deutlich besser an die Landschatsstruktur angepasst werden. Bei gleicher Anzahl Dreiecke erhält man ein deutlich besseres Ergebnis bei i.d.R. deutlich weniger Belastung für CPU und GPU. Der Nachteil ist jedoch, daß der Pre-Processing-Step oft sehr lange dauert (bei sehr großen Terrains können dies viele Stunden sein) und die vorberechneten Daten viel Speicherplatz belegen können. Auch ist es mit dieser Methode oft nicht möglich, daß dynamisches Terrain (also z.B. die klassischen Bombenkrater) realisiert werden kann. Bei der zweiteren Gruppe verhält es sich genau umgekehrt. Die Vorteile der ersten Gruppe sind mehr oder weniger ihre Nachteile und die Nachteile sind die Vorteile der anderen Gruppe.

Bei den LOD-Algorithmen ist ebenfalls die Balance zwischen CPU und GPU Last sehr wichtig. Wenn wir einen LOD-Algorithmus verwenden, der zu viel CPU-Last erzeugt, kann es passieren, daß die GPU nichts zu tun hat. Umgekehrt können wir auch die CPU wenig belasten, aber dafür die GPU überlasten.

Ich werde in dieser Artikelreihe den sogenannten Geomipmapping-Algorithmus von Willem H. de Boer aus dem Jahr 2000 vorstellen, zumindest weitestgehend. Evtl. werde ich zum besseren Verständnis oder aus Performancegründen bestimmte Bereiche abwandeln oder vorerst auslassen.

Der Geomipmapping-Algorithmus hat ein paar entscheidende Vorteile:

• leicht verständlich
• leicht zu implementieren
• relativ geringe CPU-Last
• relativ geringe GPU-Last
• nur wenige Mathekenntnisse notwendig
• verträgt sich gut mit Culling-Algorithmen
• moderate Anzahl von Dreiecken
• keine Vorberechnung notwendig
• Streaming für endlose Welten möglich
• unterliegt keinem Patentschutz
• und ist immer noch State-Of-The-Art

Sicherlich gibt es mittlerweile Algorithmen, die moderner und vielleicht auch besser sind, wie z.B. Geometric Clipmaps, aber diese sind deutlich komplizierter zu implementieren oder haben den ein oder anderen Vorteil von Geomipmapping nicht (in diesem Fall ein ganz entscheidender: Clipmaps sind Patentgeschützt).

Die Texturierung

Texturen sind ebenfalls wichtig bei einem Terrain. Zum einen sind dabei die Höhenunterschiede bzw. Variationen eine Herausforderung. Wir wollen ja schliesslich nicht, daß die gesamte Landschaft mit schlichtem Gras überzogen ist. Die Wipfel sollen mit Schnee bedeckt sein, die Täler von saftigem Gras bedeckt sein, aber auch schroffe Felswände sollen sichtbar werden. Zum anderen ist aber auch die große Sichtweite wieder ein Problem. Eine Textur für die gesamte Welt ist aus Speicherplatzgründen nicht möglich, diese würde schnell etliche hundert Gigabyte benötigen. Wir müssen also Texturen kacheln. Dies führt allerdings dazu, daß wir hässliche Muster erkennen können. Die Wiederholung wird aus der Ferne betrachtet sehr schnell sichtbar. Aus der Nähe betrachtet werden die Texturen aber wieder zu matschig, wenn diese nicht detailliert genug sind.

Bei der Texturierung werden wir mit Multitexturing arbeiten, aber auch mit Detail- und Noise-Texturen um praktisch endlose Variationen zu schaffen. Zur Vermeidung von starken Verzerrungen werde ich erklären, wie Triplanare Texturierung funktioniert.

Die Artikel über die Texturierung sind sicherlich auch der Richtige Platz für ein paar Informationen über Mipmapping, Füllraten, Shader und Texture-Sampler. Ein oft unterschätzter Punkt, der später einen großen Teil der Qualität ausmacht.

Licht und Schatten

Sind ebenfalls extrem wichtig. Durch Licht und Schatten kann man Größenverhältnisse abschätzen und die Welt bekommt eine Tiefe und zusätzliche Details. Oft sind Licht und Schatten der entscheidende Punkt im Vergleich eines mittelmäßigem zu einem guten Terrain.

Dieser Bereich wird Dinge wie Normal- und Bumpmapping, aber auch Themen wie Self-Shadowing, Shadowmaps und diverse Beleuchtungsmodelle abdecken.

Die prozedurale Erzeugung der Welt

Ein letzter Punkt, der nicht unbedingt an das Ende dieser Artikelreihe gehört ist die Erzeugung der notwendigen Höhendaten für die Landschaft. Dies erfolgt oft mit einer Heightmap, die mittels einer Noise-Funktion erzeugt wird. Hier werde ich unterschiedliche Ansätze beschreiben, wie man an solch eine Heightmap kommt und wie man ein realistisches Ergebnis erarbeiten kann.

Vielleicht werde ich noch einen Artikel schreiben, wie man Planeten generieren kann, auf die man stufenlos zoomen kann. Da dies aber eigentlich ein ganz eigener Themenkomplex ist, bin ich mir nicht ganz sicher, ob dies nicht vielleicht irgendwann mal eine eigene Artikelreihe werden wird.

Weitere Interessante Themen in diesem Zusammenhang wären auch Vegetation und die realistische Bestimmung von Flußläufen, sowie die Besiedelung. Das sind aber sehr spezielle Themen, bei denen ich auch nicht garantieren möchte, daß ich darüber etwas schreiben werde. Interessant fände ich das aber in jedem Fall.

Fazit und Ausblick

In diesem sehr theoretischen und mittlerweile auch nicht mehr ganz kurzen Artikel habe ich einen kurzen Ausblick gegeben, worüber ich in dieser Artikelreihe schreiben möchte und was ich dem interessierten Leser beibringen möchte. Der Umfang dieser gesamten Artikelreihe wird ziemlich groß werden und es wird auch einige Artikel zu diesem Thema geben. Kurz überschlagen komme ich auf vermutlich 15-20 Artikel, die jeweils den bekannten Umfang haben werden.

Wie schon zu Beginn geschrieben, habe ich noch keinen Zeitplan für die Artikelreihe. Sicherlich wird sich dies einige Zeit hinziehen, da ich auch noch andere interessante Themen habe, über die ich schreibe, und auch noch eine Menge Artikel habe, die auf ihre Veröffentlichung nach dem notwendigen Feinschliff warten.