GPU-basiertes Zeichnen von 3D-Terrains
Stitching eines groben an einen feinen LOD
In diesem Artikel möchte ich beschreiben wie die derzeitige Implementierung des Terrain-Moduls in der Parrot-Engine funktioniert. Meine alte Terrain-Implementierung war mir einfach viel zu langsam. Dieses neue Verfahren unterteilt das Terrain in Blöcke die nahtlos aneinandergefügt werden. Da dieses Verfahren deutlich weniger Geometrie prüfen und berücksichtigen muss, ist es deutlich schneller.
Ich gehe davon aus, dass das Terrain bereits in ein 3D-Modell konvertiert wurde. Wie das gemacht werden kann steht im oben verlinkten Artikel. Für diesen neuen Ansatz hier ist auch kein Quadtree notwendig - zumindest nicht für das Frustum Culling und das Zeichnen des Terrains.
Vorbereitungen
Die Heightmap wird in Blöcke aufgeteilt. Jeder Block hat die gleiche Breite und Höhe - und zwar 
. Dadurch können wir ein großes Terrain in einige wenige kleinere Bereiche unterteilen: Aus einem 1024x1024 Terrain wird zum Beispiel eines mit 16x16 Blöcken wenn ein Block 64 Segmente breit und hoch ist.
Für jeden dieser Blöcke wird eine BoundingBox ermittelt indem der niedrigste und der höchste Punkt innerhalb des Blocks ermittelt wird und daraus dann die Box erstellt wird. Diese Box wird später beim Zeichnen verwendet um das Frustum Culling durchzuführen.
Level-of-Detail (LOD) der Blöcke
Jeder dieser Blöcke kann einen bestimmten Detaillevel (LOD) haben. Dieser bestimmt wie genau der Block sich an der Heightmap orientiert. Ein Block mit dem LOD 0 verwendet jeden Punkt der Heightmap. Der LOD 1 nur jeden zweiten, der LOD 2 nur jeden vierten und so weiter.
Welcher LOD für einen Block verwendet wird orientiert sich an der Entfernung des Blocks zum Beobachter. Je weiter weg der Beobachter ist, umso gröber kann ein Block gezeichnet werden und einen umso höheren LOD darf er benutzen. Ein Terrain, unterteilt in Blöcke und mit LODs in Abhängigkeit von der Entfernung zum Beobachter könnte sich dann wie folgt darstellen:
Ein Terrain das die Verteilung von LODs zeigt
Vermeiden der Lücken im Terrain
Die Pfeile zeigen auf die Stellen die bei dieser Technik die Probleme bereiten: Die Übergänge zwischen den LODs. An den markierten Stellen befindet sich auf der Seite der gröberen LODs eine gerade Linie, auf der direkt angrenzenden Seite des feineren LODs jedoch noch ein weiterer Stützpunkt. Sollte dieser nicht zufällig exakt auf der Linie zwischen seinen Nachbarn liegen entstehen beim Rendern sogenannte Cracks (Lücken) die sehr unschön und alles andere als professionell aussehen.
Um diese Lücken zu vermeiden muss die Seite mit dem feineren LOD sich an die gröbere angleichen. Dies bedeutet, dass der Rand zum Nachbarn hin anders gerendert werden muss. Zunächst nochmal das Problem - hier allerdings schon in einer Darstellung die dem echten Renderprozess ähnlicher sieht indem Dreiecke verwendet werden:
Fehlende Nahtstelle
Diese beiden Blöcke werden nun so verbunden, dass keine Lücken mehr entstehen können:
Stitching eines groben an einen feinen LOD
Der hervorgehobene Bereich ist der, der den Levelunterschied zur linken Seite berücksichtigen muss - die anderen Bereiche des Blocks bleiben davon jedoch unberührt. Da es nur der Rand ist der sich an den Nachbarn anpasst, nennt man diese Technik auch "Stitching" - man näht quasi beide Blöcke passend zusammen.
Durch das zusammennähen der Blöcke ist es nun möglich lückenlos die LODs Block für Block zu reduzieren:
Sukzessive Detailreduzierung durch schrittweise LODs
Diese Technik funktioniert natürlich nur, wenn der LOD-Unterschied angrenzender Blöcke maximal 1 beträgt. Dies kann man sicherzustellen über die Formel die für die Festlegung des LODs eines Blocks verwendet wird:
Wenn pro einer Entfernung q der nächstgröbere LOD verwendet werden soll, dann muss für die Entfernung d der LOD Level d/q verwendet werden. Um nun sicherzustellen, dass der dahinter liegende Block maximal einen Level Differenz aufweist, muss gelten: (d+w)/q - d/q <= 1. (w sei die Breite eines Blocks).
Daraus folgt: q >= w. Sobald für q ein Wert der größer ist als die Blockbreite verwendet wird, unterscheiden sich aneinander grenzende Blöcke maximal um einen Level.
Der feinste verwendbare LOD ist der, der alle Heightmap-Punkte verwendet. Der gröbste ist der, der einen gesamten Block durch lediglich zwei Dreiecke darstellt. Haben die Blöcke 64x64 Segmente, so gibt es LODs von 0 bis 6 (64, 32, 16, 8, 4, 2, 1 Segmente breit und hoch). Weiter vereinfacht kann das Terrain nicht werden.
Das Annähen der Blöcke aneinander funktioniert in jede Richtung und jede Seite ist unabhängig von dem Detaillevel der anderen Seiten: An einem Block mit LOD 3 können LODs der Level 2, 3 und 4 in beliebiger Kombination angebracht werden:
Viele verschiedene LODs an einem Block
Ein Block besitzt genau vier Nahtstellen. Auf dem folgenden Bild ist ein Block dargestellt und rechts daneben der gleiche, jedoch mit farblich hervorgehobenen Nahtstellen:
Nahtstellen hervorgehobem
Zeichnen des Terrains
Um das Terrain effizient zeichnen zu können werden Vertex Buffer Objekte verwendet. Für jeden Block wird ein Vertex Buffer Objekt erzeugt dass die Koordinaten der Punkte Zeile pro Zeile enthält. Ausserdem werden für jeden Block mehrere Index Buffer Objekte erzeugt: Und zwar so viele wie es LODs gibt. Ein Index Buffer mit einem LOD n > 0 verwendet einfach nur jeden 2
Blöcke ohne Nahtstellen
Die Nahtstücke werden ebenfalls mit dem Index Buffer erstellt: Für jede Seite werden zwei Buffer benötigt. Einen, der zwei identische LODs aneinanderbindet und einen der einen Block mit gröberer Struktur anbindet.
Durch diese Vorgehensweise gestaltet sich das Zeichnen auch sehr einfach: In einer geschachtelten Schleife werden alle Blöcke nacheinander betrachtet. Der Inhalt jedes Blocks kann direkt gezeichnet werden. Anschließend werden alle vier Nachbarseiten überprüft: Ist der jeweilige Nachbar von feinerer Struktur, so wird er sich um die Anbindung kümmern und es wird die Naht für einen Nachbarn mit identischem Level gezeichnet. Hat der Nachbar jedoch eine gröbere Struktur, so binden wir ihn mit der Naht an die die LOD-Differenz ausgleichen kann. Das Schöne hier ist: Dies alles können wir mit dem identischen Vertex Buffer tun und müssen keinen Wechsel vornehmen. Da die Reihenfolge der Punkte für jeden Vertex Buffer für jeden Block identisch ist, und stets mit dem Index 0 beginnt, können wir die Index Buffer für alle Blöcke wiederverwenden.
Auf dem folgenden Bild wird der rechte Block an den linken angebunden. Der linke Block verwendet für seine rechte Seite die Naht als käme rechts neben ihm ein identischer LOD. Der rechte Block allerdings verwendet die Naht für einen gröberen LOD und bindet damit den anderen Level korrekt an.
Zwei angrenzende Nahtstellen
Vor- und Nachteile
Der Nachteil dieser Methode ist der, dass keine Berücksichtigung der Geländestruktur stattfindet: Eine flache Ebene wird ebenso mit sehr vielen Dreiecken gezeichnet wie ein rauher Gebirgszug.
Ein Vorteil ist, dass beim Laden der Map anhand der Konfiguration zwischen Grafiklast / CPU-Last gewählt werden kann indem die Blockgröße verändert wird: Größere Blocks bedeuten weniger Arbeit für die CPU, aber mehr für die GPU. Ebenso ist von Vorteil, dass generell der größte Teil der Arbeit an die Grafikkarte übergeben wird und ich dadurch eine enorme Performance erreichen konnte.
Ideen für Verbesserungen
Eine mögliche Verbesserung ist die, dass beim Zeichnen nicht alle Blöcke auf Sichtbarkeit getestet werden, sondern ausgehend von einem definitiv sichtbaren Block nach aussen wandernd getestet wird. Auf diese Weise kann das Terrain gigantisch sein, getestet und geprüft wird aber immer der gleiche Teil und damit hängt die Performance nicht mehr an der Größe des Terrains. Den definitiv sichtbaren Block kann man einfach ermitteln indem ein Strahl von der Kamera mit der Ebene unter dem Terrain geschnitten wird. Durch die Koordinaten des Schnittpunkts kann man direkt den Block ermitteln der sich dort befindet. Von diesem aus muss dann nach aussen wandernd die Sichtbarkeit geprüft werden.
