Terrain 101: 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

Terrain 101: Eine Einführung in dreidimensionale Landschaften in Echtzeit
Terrain 101: Die Entwicklungsumgebung und das XNA 4.0 Projekt
Terrain 101: Das erste Dreieck
Terrain 101: Transformationen
Terrain 101: Vertex- und Index-Buffer
Terrain 101: Land in Sicht
Terrain 101: Technische Rafinessen
Terrain 101: Neue Sichtweisen
Terrain 101: Kamera ab und Action

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.

Advertisements

Veröffentlicht am 14.06.2011 in 3D Terrain, Tutorial, XNA, XNA 4.0 und mit , , , , getaggt. Setze ein Lesezeichen auf den Permalink. 28 Kommentare.

  1. Du solltest dir echt mal ein Team aus guten Programmierern vom Fach suchen und ein Art Magazin machen 😀

    Muss ein Lob aussprechen für die verdammt vielen und doch so genauen und informativen Artikel. Schau inzwischen immer wieder gern hier rein 🙂

    Ich hoffe dass diese Serie so flott wie möglich kommt. Bis dahin werd ich zwar schon das meiste gelöst haben vermute ich, aber man kann nie genug lernen.

    Ich warte mal gespannt auf den ersten Artikel 🙂
    MfG
    R

  2. Hört sich net an ^^
    gut das ich Terrain’s gerade in der Schule habe da kann ich bestimmt hier den ein oder anderen Schlaumeierspruch abstauben ^^

  3. Respekt für die Arbeit die du hier reinsteckst. Vielen dank, sehr informativ!

  4. Super, habe die ganze Zeit gehofft, dass du alles was du im Forum dazu gesagt hast noch einmal zusammenfasst und hier veröffentlichst 🙂
    Weil da war das nur in Bruchstücken und das war nicht so toll :/

    Freue mich auf folgende Artikeln.

    • Gerne, mich hat es auch schon länger unter den Fingernägeln gejuckt… Ich hatte vor ein paar Jahren schon mal mit so einem Tutorial angefangen, aber das immer wieder verworfen bzw. nicht daran weitergearbeitet… Aber jetzt geht’s rund 🙂

  5. Mit dem Wissen solltest du endlich mal ein Spielestudio gründen… die Glatzemann GmbH ^^

  6. Hellriegel

    Also erstmal vielen Dank, dass Du Dir die Mühe machst. Du versprichst im ersten Artikel ja ziemlich viel. Ich bin sehr gespannt und hoffe nur Du ziehst das durch und läßt Dir nicht zu viel Zeit, dass man Spaß dran hat am Ball zu bleiben. Gute Tutorials (und dann noch in Deutsch) sind leider sehr selten auf dem Gebiet. Ich freue mich darauf 🙂

    • Danke sehr 🙂

      Durchziehen werde ich das auf jeden Fall, da sehe ich kein Problem… Die Zeit ist allerdings eine andere Geschichte, da kann ich nix versprechen 😦

      • Hellriegel

        Dann bleib ich einfach mal dran dran. Glücklicherweise kann man den Blog ohne Harre ja als RSS Feed verfolgen. Ich freue mich drauf wenn es über Riemers TErrain Tutorial hinausgeht, so dass man das auch sinnvoll nutzen kann. Bisher ist es ja noch nicht so spannend^^ Aber ich finde es gut dass Du C# Kenntisse vorrausetzt und bei der 3D Programmierung wikrlich von vorne anfängst, so dass jeder eine Chance hat wirklich zu verstehen was da passiert. Btw sei an der Stelle gleich mal gesagt, dass ich finde, dass Du eine sehr angenehme und verständliche Art hast Dinge zu erklären und auf den Punkt zu bringen, ohne zu viel und ohne zu wenig Fachchinesisch und vor allem ohne zu viel bla bla drum rum. Schade dass es nicht mehr Tutorials von Dir gibt. Also gib gas 😉

      • Wow, soviel Lob in einem Post 🙂 Vielen, vielen Dank. Ich geb mein Bestes 😉

      • Hellriegel

        Naja, ich lese viel auf xnamag mit und poste sehr wenig. Sieh das einfach als gesammeltes Lob für Deine gesamte gute Arbeit die Du die ganze über Zeit leistest. Und natürlich als Motivation nachzulegen 😉

        Aber wie ein Vorredner auch schon meinte, meisten schmeißt Du im Forum immer so kleine Wissenhäppchen hin. So ein strukturiertes Tutorial wurde mal fällig und finde ich sehr gut. Ach und die Aufgaben am Ende des 3. Teils finde ich auch eine gute Sache, behalte das ruhig bei.

        So jetzt mal Feierabend genießen, schönen Abend, Prost 😉

      • Gut, daß das mit den Aufgaben gefällt, ist zwar nicht meine Idee, aber ich fand das in anderen Tutorials schon immer ganz gut. Und ich habe früher mal Schulungen für Visual Basic bei der Bundeswehr gegeben, da kam das auch immer ganz gut an.

        Motivation sind solche Kommentare definitiv… Und… Immer schön weiterempfehlen 😉

        Dir auch nen schönen Feierabend, ich mach jedenfalls heut nix mehr, war eben beim Zahnarzt und hab jetzt ne dicke Backe.

  7. Netter Blog, gefaellt mir sehr. Auch interessante Themen.

  8. super artikel hilft mir gut weiter 🙂

  9. Da ich ja dem größenwahn verfallen bin ein Spiel in 3D zu erstellen, kommt bei mir zwangsläufig die „Terrain“ frage auf.

    Da mein Spiel allerdings im Weltraum stattfindet, stehe ich vor Problemen die ich nicht einordnen kann.

    Die größte „Einheit“ wird ein Sonnensystem sein. Sonne(n), Planeten, Monde und Asteroidenfelder.
    Will ich mich halbwegs an realistische größen halten habe ich eine Map von Schlicht gigantischen Abmessungen mit 99,9% gar nichts 😀

    Mein Gedanke war Folgender: Ich speicher die Map ab und defeniere die Position der Untereinheiten. Also eben Sonne, Planeten etc. Fliege ich mit meinem Raumschiffe einen Ort an, soll der Computer aus einer anderen Datei diesen Ort laden.

    Soweit zumindest die Theorie. Bei nem Ordinären Planeten wird das kein Problem sein, nur wenn ich den Spieler in ein Asteroidenfeld schicken will wirds lustig … viele Objekte unterschiedlicher größe … Ich muss mir bei solchen sachen auch noch echt gedanken machen wie ich das überhaupt sinnvoll erstelle. Jedes mal die relativ Position einzeln in ne Datei zu schreiben wird ein enormer aufwand.

    Ich less mal die Reihe weiter durch, vieleicht kommt mir dann ne Idee zu dem Thema.

  10. Prozedu … WAS ?

    Okay das klingt nach Kopfschmerzen ^_^ aber danke für den Wegweiser 😀

  1. Pingback: Terrain 101: Die Entwicklungsumgebung und das XNA 4.0 Projekt « "Mit ohne Haare"

  2. Pingback: Terrain 101: Das erste Dreieck « "Mit ohne Haare"

  3. Pingback: Terrain 101: Transformationen « "Mit ohne Haare"

  4. Pingback: Terrain 101: Land in Sicht « "Mit ohne Haare"

  5. Pingback: Terrain 101: Vertex- und Index-Buffer « "Mit ohne Haare"

  6. Pingback: Terrain 101: Technische Rafinessen « "Mit ohne Haare"

  7. Pingback: Terrain 101: Neue Sichtweisen « "Mit ohne Haare"

  8. Pingback: Terrain 101: Kamera ab und Action « "Mit ohne Haare"

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: