Terrain 101: Technische Rafinessen

Und hier ist nun endlich der lang ersehnte nächste Teil des Terrain 101. Wie ich bereits im letzten Teil angekündigt habe, möchte ich in diesem Teil auf ein paar Grundlagen eingehen, die ich im letzten und den anderen Teilen etwas geschludert habe. Aus diesem Grund habe ich den Titel „Technische Rafinessen“ gewählt, da dies eine zutreffende Beschreibung ist. Wichtig sind diese Grundlagen aus diesem Artikel aber in jedem Fall, denn sie liefern die Begründungen für einige Dinge, die wir bisher gemacht haben und auch noch machen werden. Teilweise werde ich aber bestimmte Dinge nochmal wiederholen, denn durch Wiederholung lernt man besonders gut.

Legen wir also sofort los und zwar mit dem sogenannten Backface-Culling. Zunächst kommt aber, wie es bisher immer war, dass aktualisierte Inhaltsverzeichnis. Dieses soll die Übersicht wahren und es ermöglichen, dass ihr schnell und einfach auf die vorherigen Artikel Zugriff habt.

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

Backface-Culling

Moderne Grafikkarten sind zwar verdammt schnell in dem was sie tun, aber trotzdem ist oft eine sehr gute Optimierung, dass man schlicht und einfach bestimmte Aufgaben weglässt. In diesem Fall ist diese Aufgabe: Rendere Dreiecke. Das Problem bei Optimierungen dieser Art ist, dass diese nur dann Sinn machen, wenn diese so einfach und schnell durchzuführen sind, dass der Geschwindigkeitsgewinn, den man durch das weglassen erreicht, größer ist, als die Zeit, die man für die Optimierung aufwendet. Wir werden insbesondere in dieser Reihe von Artikeln noch damit in Berührung kommen, da wir später mit einer so großen Anzahl von Dreiecken arbeiten, dass diese von aktuellen Grafikkarten nicht dargestellt werden könnte.

Eine schnelle und einfache, und vor allem automatische Optimierung dieser Art ist das Backface-Culling. Der Begriff „cull“ bedeutet dabei Ausschuss oder auch Auswahl. Und Backface bedeutet soviel wie „hintere Fläche“. Es werden also alle hinteren Flächen als Ausschuss angesehen. Dies macht auch absolut Sinn, wenn wir uns unseren altbekannten Würfel vor Augen führen. Wenn wir exakt von vorne auf den Würfel schauen und der Betrachter exakt auf der gleichen Höhe ist, wie der Würfel, dann ist eine Seite des Würfels auf keinen Fall zu sehen: die hintere Seite, also ein Backface.

Was ist nun die einfachste Möglichkeit die Flächen, oder Dreiecke zu erkennen? Dazu muss ich ein klein wenig ausholen: Jedes Dreieck das dargestellt wird besteht aus drei Vertices. Und diese Vertices müssen innerhalb eines Objektes oder besser noch innerhalb der gesamten Szene oder noch besser einfach immer gleich angeordnet sein. Dazu gibt es zwei Möglichkeiten und zwar gegen den Uhrzeigersinn oder mit dem Uhrzeigersinn. Dies sieht wie folgt aus:

Die Vertices des linken Dreiecks sind gegen den Uhrzeigersinn angeordnet. Bei welchem Vertex man anfängt ist dabei unerheblich, es geht aber in jedem Fall links herum. Das rechte Dreieck ist mit den Uhrzeigersinn angeordnet, es geht also immer rechts herum.

Stellen wir uns nun vor, dass wir das linke Dreieck, welches nun als sichtbar „definiert“ ist, um die vertikale Achse drehen. Sobald das Dreieck um 180° gedreht wurde, schauen wir exakt von hinten auf dieses Dreieck. Wenn wir nun die Vertices, die bisher gegen den Uhrzeigersinn angeordnet waren, durchgehen, dann merken wir, dass sich die Reihenfolge nun praktisch umgedreht hat. Aus unserer aktuellen Positon betrachtet, sind die Vertices nun im Uhrzeigersinn angeordnet. Und exakt dies ist der Schlüssel zum Backface-Culling. Schauen wir von vorne auf das Dreieck, dann ist die Anordnung der Vertices exakt anders herum, als würden wir von hinten darauf schauen. Wir stellen also nur eine der beiden Gruppen dar.

In XNA wird dies durch den RasterizerState festgelegt. Und dies ist eine tolle Überleitung zum nächsten Themengebiet in diesem Artikel, den Render-States.

Render-States

Die Render-States sind Schalter mit denen festgelegt wird, wie sich die Grafikkarte verhalten soll. Das wichtigste ist, dass man weis, wie sich diese Schalter verhalten. Ist so ein Schalter eingeschaltet worden, dann bleibt dieser solange eingeschaltet, bis dieser wieder abgeschaltet wird. Der Grafikkarte ist dabei egal, wie diese Schalter eingestellt sind. Sie rendert schlicht und einfach so, wie dies festgelegt ist.

Diese Aussage klingt logisch, wenn man nun aber bedenkt, dass unterschiedliche Programmteile jederzeit diese Render-States verändern können, dann kann man bereits erahnen, dass dies etwas komplizierter werden könnte und auch wird. Der SpriteBatch legt z.B. seine eigenen Render-States fest und zwar exakt die, die benötigt werden. Wir können uns also nicht darauf verlassen, dass die gleichen Render-States vor und nach dem SpriteBatch gesetzt sind. Wir müssen also die gleiche Strategie fahren, wie der SpriteBatch. Wir legen exakt die Render-States fest, die wir benötigen.

Daraus können wir ein paar wichtige Grundregeln ableiten:

  • Render-States bleiben solange bestehen, bis sie wieder abgeschaltet werden
  • Render-States müssen unmittelbar vor der Verwendung so eingestellt werden, wie man sie benötigt
  • Render-States können von anderen Programmteilen verändert werden

Die Render-States sind eine wichtige Geschichte, da sie halt das komplette Verhalten der Grafikkarte beeinflussen. Zum einen kann durch die Render-States das Performance-Verhalten massiv beeinflusst werden, zum anderen kostet das Setzen der Render-States an sich auch etwas Zeit. Es sollte also immer sorgfältig bestimmt werden, wann welche States gesetzt werden.

Seit XNA 4.0 ist dies ein wenig einfacher geworden, da XNA uns hierbei etwas unterstützt. Einige der am häufigsten verwendeten Render-States wurden in den State-Klassen gekapselt und sind so einfach verwendbar. Dies sind

XNA erkennt bei diesen State-Objekten automatisch, welche States verändert werden müssen und optimiert dabei ein wenig um die Geschwindigkeit zu erhöhen.

Dies sind noch nicht alle Render-States die es gibt, nur ein paar wichtige. Zu den Render-States gehören aber auch noch Dinge wie der aktuell verwendete Shader/Effect, der oder die aktuellen Vertex-Buffer, der Index-Buffer, die verwendeten Texturen und einige weitere Dinge mehr.

Es ist sehr wichtig, dass ihr damit sehr vertraut seid. Und auch wenn es diesmal kein Stichwort für die Überleitung gibt, gehe ich an dieser Stelle zum nächsten Thema über und dies ist der Vertex-Cache.

Vertex-Cache

Vertices sind in der Welt der Grafikkarte eine der wichtigsten „Datentypen“. Sie sind so wichtig, dass es sogar einen eigenen Shader-Typ gibt, der sie verarbeitet: den Vertex-Shader. Was mit den Vertices gemacht wird, kann aus Sicht der Rechenzeit relativ schnell verhältnismäßig teuer werden und aus diesem Grund gibt es den Vertex-Cache. Dieser ist dafür gedacht, dass kein Vertex während des Renders nach Möglichkeit zweimal berechnet werden muss. Aber warum müssen überhaupt Vertices mehrfach berechnet bzw. transformiert werden? Der Grund dafür ist, dass für bestimmte Polygone einige Vertices geteilt sind, um die gewünschte Form zu erreichen. Ein Beispiel ist ein simples Quad. Es besteht aus zwei Dreiecken und vier Vertices. Da jedes Dreieck 3 Vertices hat, kann man relativ einfach ausrechnen, dass zwei Vertices zweimal verwendet werden können bzw. müssen. Und genau hier greift der Vertex-Cache.

Eine wichtige Information ist noch, dass der Vertex-Cache nur dann funktioniert, wenn auch ein Index-Buffer vorhanden ist und verwendet wird. DrawIndexedPrimitives bzw. DrawUserIndexedPrimitives ist also Pflicht.

Die Größe des Vertex-Cache ist meistens ein gut gehütetes Geheimnis der Grafikkarten-Hersteller, da dieser extrem wichtig ist, aber auch einige Rückschlüsse auf das interne Design zulässt und so der Konkurrenz einen kleinen Wettbewerbsvorteil verschaffen könnte. Dies ist nicht so schlimm für uns, wir können einfach einen Vertex-Cache zwischen 4 und 64 Vertices annehmen.

Worauf müssen wir nun achten? Das ist klingt einfach, kann aber durchaus ziemlich schwierig werden. Wir müssen im Grunde genommen nur die wiederholten Zugriffe auf die einzelnen Vertices unserer Meshes möglichst nah beieinander halten, damit die Wahrscheinlichkeit, dass diese noch im Cache sind, möglichst groß ist. Bei unserem Quad-Beispiel sollten wir also auf die Vertices 0,1,2 und dann auf 1,2,3 zugreifen. Dies würde bei einer Vertex-Cache-Größe von 2 perfekt arbeiten, im Gegensatz zu 0,1,2 und 3,1,2. Da bei einer Cache-Größe von 2 immer nur die beiden letzten Vertices im Cache sind, würde in diesem Fall Vertex 2 zweimal berechnet werden müssen.

Um die Sache noch komplexer zu machen, gibt es sogar noch einen zweiten Vertex-Cache und zwar den sogenannten „Pre-Vertex-Shader-Cache“. Dies ist ein gewöhnlicher Cache, der den Zugriff auf den Speicher des Vertex-Buffers beschleunigt und dies ist einer der Gründe, warum Draw*Primitives in der Regel schneller ist als DrawUser*Primitives. Wir können für diesen Speicher sehr einfach optimieren indem wir den Zugriff auf unsere Vertices möglichst linear gestalten. Wir sollten also möglichst wenig in den Positionen im Buffer „springen“. Optimal ist, wenn wir diesen schlicht und einfach von vorne nach hinten durchlaufen, was durch einfaches Sortieren der Vertices und Dreiecke erreicht werden kann.

Der Vertex-Cache ist eine wichtige Sache, die die letzten Reserven aus der Grafikkarte herauskitzeln kann.

Sinn und Zweck von Chunks und Paging

Den Sinn und Zweck von Chunks zu erklären ist relativ einfach. Unsere Welt bzw. Landschaft, die gigantisch groß sein soll, ist in dieser Größe nicht wirklich gut zu handhaben. Weder für die Grafikkarte, noch für das Laden von Festplatte und auch nicht für das Erzeugen der einzelnen Vertices. Auch für eine Sichtbarkeitsprüfung (auf die ich in einem eigenen Artikel eingehen werde) ist es notwendig, dass wir kleinere Häppchen haben um die Sichtbarkeit in feineren Stufen kontrollieren zu können.

Die Herausforderung bei den Chunks ist jedoch die Bestimmung der Größe eines einzelnen Chunks. Je mehr Chunks wir haben, desto mehr Vorteile haben wir, gleichzeitig aber auch Nachteile. Kleine Chunks haben weniger Vertices und können daher schneller gerendert, geladen und erzeugt werden. Die Sichtbarkeitsprüfung kann sehr fein arbeiten. Der Nachteil ist jedoch, dass jeder Chunk einen eigenen Draw-Call benötigt. Draw-Calls kosten Zeit, zum einen Setup-Kosten (laden der Effekte, Texturen, Umschalten der Render-States etc.), die eigentlichen Kosten für das Rendern, sowie den Overhead, der durch den Grafikkartentreiber erzeugt wird. Je weniger Draw-Calls wir haben, desto besser. Ein Durchschnitts-PC schafft ca. 2500 Draw-Calls und die XBox vielleicht um die 500-1000. Die genaue Anzahl kann jedoch nur für eine spezielle Maschine mit einem konkreten Beispiel festgelegt werden, da dies von vielen Faktoren abhängt: CPU-Leistung, Art und Leistung der Grafikkarte, eingesetzter Treiber, welche Effekte, Anzahl und Art der Buffer und einige Punkte mehr spielen eine wichtige Rolle. Für unseren Fall hier erkennen wir also, dass die Größe der Chunks weise gewählt werden muss. Als Faustregel könnte man also festlegen:

Wir benötigen so viele Chunks wie möglich, aber höchstens soviele wie nötig.

Wir werden uns im weiteren Verlauf an eine gute Größe und Balance herantasten und ich werde euch das notwendige Wissen vermitteln, wie ihr dies in Zukunft handhaben könnt.

Das Paging hängt eng mit den Chunks zusammen, da dieses mit den Chunks arbeitet. Das Paging ist schlicht und einfach dafür zuständig, dass zur rechten Zeit Chunks geladen bzw. erzeugt werden, damit diese dargestellt werden können, aber auch dafür, dass diese wieder aus dem Speicher entfernt werden, wenn sie nicht mehr benötigt werden.

Ein einfaches Beispiel ist eine endlose Welt. Wir möchten endlos lange in eine Richtung laufen können, ohne jemals das Ende der Welt zu erreichen. Da eine endlose Welt auch endlos viel Speicher benötigt, brauchen wir eine Strategie um diese Unmöglichkeit aufzulösen. Ein einfacher Weg ist in Blick- bzw. Marschrichtung soviele Chunks vorzuhalten, wie wir sehen können. Hinter uns können die Chunks wieder entfernt werden, über die wir bereits hinweggelaufen sind. Dies ist problemlos möglich, da wir ja nur in eine Richtung blicken. Auf diese Art und Weise sind immer nur ein paar Chunks aktiv und diese sind einfach zu handhaben. Das ist Paging.

Sicherlich ist echtes Paging noch ein wenig komplizierter. Wir benötigen eine komplexere Heuristik um bestimmte Fälle abzufangen. Wenn der Spieler zum Beispiel plötzlich stehenbleibt und sich umdreht, dann haben wir die Chunks hinter ihm bereits entladen und müssen diese neu Laden. Da dies aber Zeit kostet, kann es passieren, dass dies solange dauert, dass dieser Vorgang sichtbar wird. Eine Möglichkeit dies zu verhindern ist, dass wir soviele Chunks in alle Richtungen um den Spieler herum vorhalten, wie benötigt werden um an den Rand der Sichtweite zu gelangen.

Es gibt jedenfalls viele, viele Möglichkeiten, wie wir mit Paging umgehen können. Vieles hängt schlicht und einfach davon ab, wie lange es dauert Chunks zu erzeugen. Manchmal müssen Chunks auf der Festplatte gespeichert werden, damit diese später wieder schnell geladen werden können und manchmal macht dies keinen Sinn (oder ist nicht möglich). Fakt ist jedoch, dass solche Entscheidungen massiv vom tatsächlichen Anwendungsfall also der Spielmechanik abhängen. Wir werden in dieser Artikelreihe sicherlich nur den einfachsten, im vorherigen Abschnitt beschriebenen, Fall implementieren. Was wir aber in jedem Fall besprechen werden ist eine weitere, wichtige Möglichkeit zur Reduzierung der Dreiecke, dass „Level of Detail“.

LOD – Level of Detail

Level of Detail, kurz LOD, ist eine Technik zur Reduzierung der Komplexität von Objekten. Niedrigere Komplexität bedeutet in der Regel weniger Geometrie, also weniger Dreiecke, ist aber nicht darauf beschränkt. Auch Texturgrößen können optimiert werden, wobei dies einen eigenen Namen hat: Mipmapping. Aber es gibt noch weitere Anwendungsgebiete: Die Effekte sind für LOD oft ausgezeichnet geeignet.

Warum wollen wir nun LOD einsetzen? Der Grund dafür ist schlicht: Mit zunehmender Entfernung sehen wir immer weniger Details eines Objektes. Auf 1000m Entfernung kann man nicht mehr jede Falte in einem Gesicht erkennen, da diese Details einfach zu klein sind. Wir können also auf solche Details verzichten und das Objekt so schneller Rendern. Wir können dies leicht in unsere virtuelle Welt überführen: Der Monitor hat eine feste Auflösung mit einer begrenzten Anzahl von Pixeln. Je weiter ein Objekt in einer 3D-Szene entfernt ist, desto kleiner wird es. Die Anzahl der Pixel die das Objekt auf dem Bildschirm einnimmt, nimmt also mit zunehmender Entfernung ab. Wenn die Anzahl der Pixel abnimmt, dann können wir auch weniger Details darstellen und wenn wir weniger Details darstellen können, dann macht es auch keinen Sinn, diese Details zu berechnen. Das ist LOD.

Bei einer Landschaft können wir dies sehr gut einsetzen: Je weiter ein Chunk vom Betrachter entfernt ist, desto weniger Details müssen wir darstellen. Wir stellen einfach weniger Dreiecke dar, wie dies im Detail umgesetzt wird, dazu werden wir in einem der nächsten Teile kommen. Aber auch die Effekte sind eine wichtige Optimierung: Im Nahbereich zur Kamera können wir bestimmte Textureffekte anwenden (sogenannte Detailmaps) und diese mit der eigentlichen Textur überblenden. Dies führt direkt vor dem Betrachter, also auf dem Chunk, auf dem sich der Spieler befindet, zu einer sehr hohen Detaildichte. Die Berechnung dafür ist etwas teurer und kostet Rechenzeit. Auf den weiter entfernten Chunks ist dies nicht notwendig, da der Effekt nicht oder nur kaum sichtbar wäre. Daher können wir in diesem Bereich einen anderen, einfacheren Effekt einsetzen. Auch Licht- und Schatten sind im entfernten Bereich weniger wichtig. Da kleine Details nicht sichtbar sind, reicht es vielleicht, wenn man in 5 Chunks Entfernung nicht mehr mit mehrfach projizierten, perspektivisch korrigierten und gefilterten Schatten arbeitet, sondern mit einer schlichten, niedrig aufgelösten Shadowmap.

LOD ist ein sehr, sehr komplexes, aber extrem interessantes Gebiet der Grafikprogrammierung. Man kann viel erreichen und wird viele Erfolge erzielen, aber es gibt auch eine Schattenseite. Die Problematik ist der Übergang zwischen unterschiedlichen LOD-Stufen. Wenn wir im einen Moment einen Chunk mit 100.000 Dreiecken darstellen und diesen plötzlich nur noch mit 50.000 Dreiecken, dann ist dies sichtbar. Diesen Effekt beim Umschalten zwischen den LOD-Stufen nennt man Popping. Es gibt bestimmte Tricks, wie man diesen Effekt weniger sichtbar machen kann und damit werden wir uns auch beschäftigen. Wir werden Morphing anwenden, also langsam zwischen zwei Meshes überblenden bzw. wechseln.

Schlusswort und Ausblick

In diesem Artikel bin ich ein wenig abgeschweift und habe ein paar Begriffe erklärt, damit einige technische Details etwas klarer werden. Dies war auch notwendig, da ich das Gefühl hatte, das ich im letzten Teil etwas zu schnell über ein paar Dinge hinweggesprungen bin. Wie schon mehrfach gesagt, sind diese Grundlagen sehr, sehr wichtig, auch wenn sie teilweise etwas trocken sind.

Kommen wir zum Ausblick für den nächsten und den übernächsten Teil. Ich habe für beide Teile bereits die Themen grob festgelegt, aber ich habe noch nicht entschieden, in welcher Reihenfolge ich diese veröffentlichen werde. Ein Teil wird sich mit der Kamera beschäftigen, damit wir uns auf unserer Landschaft bewegen können, aber auch um bestimmte Details betrachten zu können. Im anderen geplanten Teil werde ich beschreiben, wie zunächst 9 Chunks angezeigt werden und ich werde näher auf den Geomipmapping-Algorithmus eingehen.

Sobald diese beiden Teile abgeschlossen sind, werde ich in den Folgeartikeln noch auf das Laden und Entladen von Chunks eingehen und die Landschaftgrößer machen. Morphing der LOD-Stufen, Stitching zwischen Chunks mit unterschiedlichen LOD-Stufen und die Ermittlung der LOD-Stufen-Verteilung werden ebenfalls noch Themengebiete sein, die ich behandeln werde. Sobald diese Themen besprochen sind und ihr sie verinnerlicht habt, werden wir uns in Richtung Texturierung, Beleuchtung, Schatten, Physik etc. begeben, aber dies ist tatsächlich noch Zukunftsmusik und bestimmt noch 4-5 Artikel entfernt.

Advertisements

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

  1. Ein super Artikel, der irgendwie lange auf sich warten lassen hat 🙂
    Ich bin jetzt um ein paar Sachen schlauer geworden und freue mich natürlich auf die nächsten Teile dieser Reihe! 🙂

    • Ich hatte auch schon ein schlechtes Gewissen, dass es so lange gedauert hat und ich hoffe, dass ich den nächsten Teil etwas schneller hinbekomme.

  2. Als ich gestern von dir den Link zu deinem Blog bekommen habe (http://www.xnamag.de/forum/viewtopic.php?t=5729 ) , habe ich mich sehr gefreut, dass ich eine so gute Blog Seite über XNA gefunden habe. Die Tutorials funktionieren ohne Probleme und sind super erklärt, mit vielen Details aber auch wieder nicht zu viele.
    Außerdem habe ich noch kein einziges Tutorial gefunden (in XNA), das die Landschafts Erstellung so genau erklärt (erklären wird 😀 ).

    Ich freue mich schon sehr auf die weiteren Teile der Tutorial Reihe (vor allem auf den mit der Texturierung.

    Mach weiter so!!

    Gruß christof

  3. Xwin7userX

    Einen tollen Blog hast Du hier ! Und vorallem arbeitet er meiner Meinung nach perfekt mit Riemers Tutorials zusammen. Während man hier viele Informationen und anschauliche Erklärungen findet, sieht man bei Riemers Tutorials sehr schnell Ergebnisse, das Verständnis bleibt dabei aber manchmal auf der Strecke (unter anderem, weil ich das Englische nicht immer 100%tig verstehe).
    Auch die Terrain 101 Serie kommt mir gerade recht, da ich mich eh mal ein wenig an 3D herantasten wollte. Hoffentlich kommt bald der nächste Artikel ;D

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

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

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

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

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

  6. Pingback: Terrain 101: Eine Einführung in dreidimensionale Landschaften in Echtzeit « "Mit ohne Haare"

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

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

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

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

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

  12. Pingback: Terrain 101: Transformationen « "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: