Terrains werden benutzt um größere Gelände abzubilden. Vor allem in Spielen nehmen die Terrains einen immer größer werdenden Stellenwert ein, denn sie ermöglichen es mit überschaubarem Aufwand große Spielwelten zu erzeugen die zudem sehr realistisch wirken. Dekorative Elemente wie Bäume, Häuser und Felsen werden auf dieser Landschaft platziert so dass eine dicht bestückte Welt entsteht in der der Spieler sich dann frei bewegen kann.

In diesem Artikel möchte ich einen möglichen Ansatz zur Erzeugung und dem Rendering von Terrains vorstellen. Dieser Ansatz nutzt die Leistungsfähigkeit moderner Grafikkarten nicht gut aus. Dies liegt daran, dass die CPU viel Arbeit für die Echtzeitoptimierung des Terrains investieren muss. Ein Vorteil des Algorithmus ist allerdings der, dass die Qualität der Darstellung stufenlos eingestellt und zur Laufzeit verändert werden kann.

Definieren der Geländeform

Ein Terrain wird über eine Heightmap definiert. Eine Heightmap ist eine Bilddatei deren Bildpunkte als Höhenangaben interpretiert werden. Es ist eine Art Abbild des Geländes bei einem Blick von oben. Durch diese Art der Definition können große Datenmengen kompakt und zudem für Menschen anschaulich bereitgestellt werden.

Heightmaps können manuell mit einem Malprogramm erstellt werden, doch es gibt auch sehr pfiffige Algorithmen die Heightmaps erzeugen können indem sie unter anderem eine Erosion mit Bildverarbeitungsfiltern simulieren.

Wenn die GPL-Lizenz kein Hindernis ist, dann findet man den Terrain texture generation code von Oddlabs dazu vielleicht sehr hilfreich.

Sehr empfehlen kann ich auch L3DT das auch in der kostenlosen Version ausreichende Features bietet und derzeit mein Tool der Wahl ist für die Erstellung von Heightmaps mitsamt den dazu notwendigen Texturen.

Die dunklen Stellen sind diejenigen mit dem niedrigsten Höhenwert und die weißen entsprechend die mit dem höchsten. Eine Heightmap sollte immer quadratisch sein und eine genaue Zweierpotenz breit sein – dies macht ihre Verarbeitung sehr viel einfacher. Üblich sind zwischen 512 und 4096 Pixel. Sollen noch größere Heightmaps zum Einsatz kommen, muss man sich mit zunehmender Terraingröße über Caching und das Unterteilen der Heightmap in mehrere Teilbereiche Gedanken machen. Auch wenn die Rechner inzwischen sehr große Hauptspeicher haben ist der Bereich den der Spieler sehen kann stets beschränkt und warum sollte man unnötig Ressourcen vergeuden?

Umwandeln der Heightmap in ein 3D-Modell des Terrains

Da die Heightmap ein Bild ist, besteht diese aus Pixeln und jeder Pixel hat eine x und eine y-Koordinate im Bereich der Bildbreite bzw. -höhe. Wenn die Heightmap die Ausmaße einer glatten Zweierpotenz besitzt, dann ist ihre Breite und Höhe $2^n$.

Die X-Achse der Heightmap wird auf die X-Achse in der 3D-Welt abgebildet, die Y-Achse allerdings auf die Z-Achse. Die Y-Werte werden aus den Höhenwerten der Heightmap ermittelt. Da die Pixelkoordinaten nicht den Weltkoordinaten entsprechen, müssen diese noch transformiert werden:

	X Wert des Pixels
	Y Wert des Pixels
	Die Höhe des Terrains an der Position (, )
	Breite und Höhe des Heightmap-Image in Pixel
	Die gewünschte Breite und Tiefe des Terrains in Welt-Koordinaten
	Gewünschte Höhe des Terrains in Welt-Koordinaten

Die Y-Achse wird anhand des Grauwertes in einen Bereich von 0 bis 1 konvertiert. Auch diese wird dann noch in den richtigen Bereich hochmultipliziert: Mit der gewünschten maximalen Höhe.

heightMapVectors = new vector[heightMap.getWidth()+1][heightMap.getWidth()+1];
for ( int x=0;xfor ( int y=0;y
1 /**  * Gets the position of a point on the heightmap.  *  * The values for x and y are clamped to the valid range.  *  * @param x x coordinate of the pixel  * @param y y coordinate of the pixel  * @param pos the vector to receive the coordinates  */ private void getVertexFromHeightmap(int x, int y, final Vector pos) {   final double heightMapObjectFactor = terrainExtend / heightMap.getWidth();   final double xx = 2.0*x*heightMapObjectFactor - terrainExtend;   final double zz = 2.0*y*heightMapObjectFactor - terrainExtend;   if ( x>=heightMapWidth-1 ) x=heightMapWidth-1;
  if ( y>=heightMapWidth-1 ) y=heightMapWidth-1;

  int h = heightMap.getRedColorAt(x, y);
  if ( h  final double yy = terrainHeight * (double)h / 255.0;

  pos.x=xx;
  pos.y=yy;
  pos.z=zz;
}

Eine interessante Idee findet man auf der Seite von Shamus Young. Dort schlägt er vor die drei Farbkomponenten für verschiedene Detailgrade zu verwenden um die volle Genauigkeit von 24Bit breiten Pixeln ausnutzen zu können. Sein Tutorial zu seiner Terrain Engine ist zudem insgesamt ausserordentlich lesenswert!

Da die Vertexkoordinaten des Terrains sehr oft benötigt werden und die Umrechnung in Weltkoordinaten Zeit kostet, speichere ich alle Vertices in dem zweidimensionalen Array heightMapVectors.

Die Heightmap wird eine Spalte und Zeile größer

Die Methode getVertexFromHeightmap schneidet die Koordinaten der Heightmappixel auf den gültigen Bereich zurecht weil diese den erlaubten Bereich verlassen werden. Dies hat einen einfachen Grund: Ich arbeite später nur mit den Flächen des Terrains und eine Fläche braucht mehr als einen Punkt um aufgespannt zu werden. 1024 Pixel in der Breite ergeben 1023 Flächen in der Breite. Da ich einen Quadtree einsetzen möchte, benötige ich eine exakte Zweierpotenz an Flächen. Um dies zu erreichen könnte man die Heightmap auf 1025 Pixel ausdehnen – ich dupliziere aber einfach die letzte Spalte und Zeile der Heightmap. Da alle Texturen glatte Zweierpotenzen sein sollen gelten dann auch für die Heightmaps keine besonderen anderen Regeln an die man immer denken muss (und die man gerne vergisst und sich anschließend über Fehlermeldungen wundert).

So sieht das Terrain aus wenn ich es mit allen Details zeichne. Das heißt, dass jeder Pixel der Heightmap berücksichtigt wird. Das Programm zeichnet so pro Frame 1024x1024x2 = 2.097.152 Dreiecke. Trotz der Verwendung von VBOs zur Beschleunigung erreicht mein Rechner maximal 1,1 Bilder pro Sekunde. Hier muss noch kräftig optimiert werden!

Frustum Culling mit dem Quadtree

Die erste Optimierung die ich beschreiben werde ist das Frustum Culling. Es sorgt dafür, dass nur das gezeichnet wird was auch für den Beobachter sichtbar ist. Warum sich das lohnt sieht man auf dem folgendem Bild.

Hier sieht man das gesamte Terraingebiet mit dem sichtbaren Bereich in weiß hervorgehoben. Es ist offensichtlich, dass viel Rechenzeit vergeudet wird für die Bereiche die der Beobachter gar nicht sehen kann.

Frustum

Der Frustum ist exakt der Bereich den die Kamera sehen kann – alles was außerhalb des Frustums liegt wird, sollte es doch gerendert werden, nicht auf dem Bildschirm zu sehen sein. Der Frustum hat die Form einer abgeschnittenen Pyramide.

Verwendung eines Quadtrees

Um die sichtbaren Bereiche von den unsichtbaren zu unterscheiden setze ich einen QuadTree ein. Dies ist eine hierarchische Datenstruktur die das Gelände, angefangen mit einem großen Quadrat in immer feinere Quadrate unterteilt. Die unterschiedlichen Grade der Unterteilung werden Levels (Ebenen) genannt. Während der erste Level nur ein Quadrat enthält, sind es beim zweiten schon vier und beim drittten 16 Stück:

Das Bild zeigt ein Terrain mit 8×8 Heightmap Pixeln (die auf 9×9 wie oben beschrieben erweitert wurden) und deren resultierenden 8×8 Flächen dann mit einem Quadtree überlagert wurden. Der Übersichtlichkeit wegen habe ich pro Level nur eine einzige Node des Trees eingezeichnet. Man sieht, dass Level 1 das gesamte Feld umfasst und Level 2 nur noch ein viertel davon. Die Folge ist, dass die Breite und Höhe eines Quadrats eines Levels jeweils die Hälfte des darüber liegenden Levels ist.

Der Level 1 des Quadtrees ist die Wurzel, der oberste Knotenpunkt (Root-Node). Dieser enthält den gesamten Bereich. Unterhalb dieser Node befindet sich der Level 2 – dieser enthält nun 4 Nodes, Level 4 schließlich besteht aus 64 (8×8) Quadraten die jeweils nicht weiter unterteilt werden können da sie nur noch Quadrate der Fläche 1×1 sind.

Diese Unterteilung erfolgt jedoch nur organisatorisch: Das bedeutet, dass lediglich immer kleinere Teile des Geländes betrachtet werden – die Heightmap wird nicht wirklich in so viele kleine Teile zerteilt.

Frustum Culling

Um nun das Frustum Culling durchzuführen wird das Terrain anhand dieses Quadtrees gezeichnet: Es wird mit dem Level 1 begonnen.

Für das aktuellen Level und das aktuelle Quadrat dieses Levels wird überprüft ob der Bereich teilweise innerhalb des Frustums liegt.

• Falls dem nicht so ist und der Bereich komplett ausserhalb des Frustum ist wird er nicht gezeichnet.
• Falls der Bereich komplett innerhalb des Frustum liegt, wird der gesamte Inhalt direkt gezeichnet.
• Falls nur ein Teil den Frustum schneidet, werden die Kinder untersucht und dieser Algorithmus rekursiv wieder aufgerufen bis entweder einer der vorgenannten Kriterien eintritt oder die unterste Ebene erreicht ist. Diese wird dann direkt gezeichnet.

Um zu überprüfen ob eine Node innerhalb des Frustums liegt oder nicht wird um diese eine “axis aligned Bounding Box” gelegt und diese dann auf Schnittpunkte mit dem Frustum geprüft. Aus jedem zu prüfenden Quadrat wird eine Box erzeugt die den Grundriss des Quadrats hat und dessen Höhe das gesamte Terraingebiet in ihrem Bereich enthält.

Das folgende Bild zeigt von der Seite gesehen ein paar Quadrate einer Quadtree Ebene und darüber die BoundingBoxes die so gewählt wurden, dass die die Punkte des Terrains enthalten:

Hier sieht man in weiß wieder den sichtbaren Frustum hervorgehoben und das Terrain, welches nun auf den sichtbaren Bereich zugeschnitten ist. Diese Version kommt bereits mit 362.670 Dreiecken aus und wird schon mit 4,2 Bildern pro Sekunde gerendert.

Betrachtet man das Terrain aber im Wireframe Modus so sieht man, dass immer noch enorm viele Dreiecke verwendet werden. Vor allem im hinteren Bereich bilden die Dreiecke einen einzigen “weißen Brei”. Hier kann man einzelne Dreiecke gar nicht mehr ausmachen und daher würde es auch nichts ausmachen hier einige einfach wegzulassen…

Laufzeitoptimierung des Terrain-Meshes

Da aufgrund der Perspektive die Dreiecke weiter hinten sehr viel kleiner werden, tragen diese auch zur Qualität des gerenderten Bildes weniger bei. Dies umso weniger je weiter sie entfernt sind. Es bietet sich also an je nach dem wie „wichtig“ (im Sinne von: Das Weglassen wäre sehr deutlich sichtbar und störend für den Betrachter) ein Dreieck ist, dieses einfach wegzulassen und durch ein größeres zu ersetzen.

Die Fehlerformel

Um feststellen zu können welche Dreiecke weggelassen werden können ohne die Qualität zu stark einzuschränken wird eine Formel benötigt die einen Wert für den Fehler liefert. Der Fehler bei einer Vereinfachung resultiert daraus, dass Stützstellen aus der Heightmap weggelassen werden – dies ist klar da größere und damit gröbere Dreiecke verwendet werden.

/**
 * Visits the drawFlags-Tree and marks the nodes so they can be drawn later.
 *
 * @param frustum the frustum to use for frustum culling and LOD
 * @param level the level of the current node to process
 * @param x the x coordinate of the node
 * @param y the y coordinate of the node
 */
private void setDrawFlags(final Frustum frustum,final int level,final int x, final int y) {
  final int[][] flags = drawFlags.get(level-1);

  final double err = getErrorFor(frustum,level,x,y,tmpBBox);
  if ( err < Terrain1ConsoleVars.maxError || level>=maxDepth ) {
    // The error is small enough - draw this node
    flags[x][y]=nodeInfoDraw;
  } else {
    // Error is too high: subdivide further
    flags[x][y]=nodeInfoDontDraw;
    if ( level < maxDepth ) {
      setDrawFlags(frustum, level+1, 2*x, 2*y);
      setDrawFlags(frustum, level+1, 2*x+1, 2*y);
      setDrawFlags(frustum, level+1, 2*x, 2*y+1);
      setDrawFlags(frustum, level+1, 2*x+1, 2*y+1);
    }
  }
}

Das folgende Schaubild zeigt das Prinzip der Fehlerberechnung. Die roten Punkte fallen weg bei einem Vereinfachungsschritt:

Der Fehlerwert ist das Maximum aller Höhendifferenzen die entfallen. Es werden stets die Absolutwerte der Höhendifferenzen verwendet da eine Veränderung nach unten wie nach oben als Fehler gewertet wird. Dieser Fehlerwert wird nun für jede Node des Quadtrees errechnet und das Maximum des Fehlers wird in die darüber liegenden Ebenen durchgereicht – das bedeutet dass die Fehler hin zur Wurzel des Quadtrees nur steigen können.

Dieser Fehlerwert geht derzeit noch davon aus, dass die Höhe des Terrains für den Beobachter konstant ist – die Perspektive ist somit noch gar nicht berücksichtigt worden. Derzeit besagt der Fehlerwert nur unabhängig von der Beobachterposition was für eine Abweichung zum Original-Terrain zu erwarten ist. Wie sich der Fehler auf den Betrachter auswirkt lässt sich aber über den Strahlensatz berechnen:

	der Maximalfehler der aktuellen Node
	das vertikale Ausmaß des Fehlers auf der Near-Plane des Frustums
	die Höhe des Frustums
	der Near-Wert des Frustums
	der Abstand des Nodemittelpunkts zum Frustum Ursprung (der Beobachter)

Anhand der Daten des Frustums können wir berechnen wie groß der Anteil des Fehlers zur Höhe der Bildschirmdarstellung ist:

errorScreenAbsolut = * / distance
errorScreenPercent = 100 * errorScreenAbsolut /

Mit dieser Formel kann nun ausgerechnet werden wie groß ein Fehler bezogen auf die Höhe des Bildschirm-Bildes ist. Dadurch kann man nun das Berechnen des Terrains so optimieren, dass der Fehler unter einem vorher vergebenen Grenzwert bezüglich dessen Auswirkung auf den erkennbaren Fehler bleibt. Je größer der Grenzwert, desto stärker wird das Gelände optimiert und umso mehr Dreiecke können eingespart werden. Es ist wichtig die Bildschirmauflösung in die Berechung einfliessen zu lassen, denn auf einem 320×200 Pixel Fenster sieht man weniger Details -und damit auch weniger Fehler – als auf einer 1280×1024 Darstellung.

Wenn wir den Fehler als echten Vector darstellen und nicht nur als Zahl die die Höhendifferenz angibt, dann ergibt sich sogar eine weitere Verbesserungsmöglichkeit. Wird dieser Fehlervektor auf die Y-Achse der Kamera projiziert so erhält man den wirklich für die Kamera sichtbaren Fehler. Wenn die Kamera in einem steilen Winkel nach unten auf das Terrain schaut, dann ist der Fehler viel kleiner. Entsprechend auch wenn die Kamera gerade von vorne schaut, der Fehlervektor aber schräg nach vorn zeigt.

Das Prinzip ist wie bei einem Stab der im Boden steckt: Wenn man ihn von oben betrachtet sieht ist er (bezogen auf die Menge des Sichtfeldes den er einnimmt) kleiner aus als wenn man ihn von der Seite betrachtet.

Die Länge dieses auf die Kamera-Ansicht projizierten Vektors ist der echte Fehler. Dieser wird mit dem Grenzwert verglichen.

Der Grenzwert kann auch zur Laufzeit automatisch verändert werden. Wenn das Programm zum Beispiel feststellt, dass es zuviel Zeit für die Berechnung des Terrains verbraucht. Man könnte sich vorstellen, dass es einen Einstellungsdialog gibt der drei Qualitätsstufen für das Terrain vorsieht: high, medium und low.

Die high-Einstellung begrenzt den erlaubten Fehlerwert auf den Bereich von 0,1 bis 1, medium von 1 bis 3 und low auf den Bereich von 3 bis 8. Das Programm kann dann innerhalb dieser Grenzen die Optimierung frei verändern um eine optimale Zielframerate zu erreichen.

Der Fehlerwert muss für jede Node des Quadtree auf jedem Level eingetragen werden. Als Datenformat habe ich ein ArrayList Containerobjekt gewählt das double[][] Arrays beinhaltet- pro Eintrag im ArrayList-Objekt ist das ein zweidimensionales Array mit den Fehlerwerten. Der Level 1 (der Index 0 des ArrayList Objekts) enthält ein double[1][1] Array. Der Level 2 (Index 1) ein double[2][2]. Die beiden Dimensionen verdoppeln sich mit jedem weiteren Level.

Das Bild zeigt wie der Quadtree aufgebaut ist. Für jeden Level ist das zweidimensionale Array rechts daneben eingezeichnet. Die roten und blauen Elemente zeigen wie das Verhältnis von Vater zu Kind-Nodes aussieht und welche Nodes von den jeweiligen Vätern eingeschlossen werden. Beispielhaft zeigt das Bild für einen Übergang von Level 3 zu Level 4 wie die Koordinaten im Array umgerechnet werden müssen um für eine Vaternode die 4 Kindnodes zu erhalten. Die umgekehrte Rechnung ist sehr viel einfacher: Um die Vaterkoordinaten zu einem Kind zu erhalten sind einfach die X und Y Koordinate durch 2 zu dividieren und die Nachkommastellen abzuschneiden.
Nun sind die Fehlerwerte ermittelt. Der nächste Schritt ist herauszufinden welche Nodes des Quadtrees gezeichnet werden sollen.

Der Zeichenalgorithmus

Es sollten am besten genau die Nodes gezeichnet werden deren Fehlerwert gerade unter den vorgegebenen Grenzwert fällt. Um diese herauszufinden wird der Quadtree rekursiv von oben an durchlaufen und für jede besuchte Node der perspektivkorrigierte Fehlerwert berechnet (errorScreenPercent). Ist dieser Wert kleiner als der Grenzwert, so wird die Node als zu zeichnen markiert und die Rekursion an dieser Stelle beendet und mit der nächsten Node fortgefahren. Solange der Grenzwert jedoch kleiner als der effektive Fehler ist und die Node nicht vollständig unsichtbar ist (das Frustum Culling habe ich kurzerhand hier mit integriert) werden die jeweiligen Kindernodes einen Level tiefer weiter untersucht. Spätestens wenn die maximale Quadtreetiefe erreicht wurde werden die Nodes allerdings zum Zeichnen markiert. Nodes die nicht gezeichnet werden sollen werden ebenfalls entsprechend markiert.

Nach diesem Durchlauf ist bekannt welche Nodes gezeichnet werden sollen und welche nicht (Fehler zu gross oder unsichtbar).

Zur Speicherung dieser Daten wird ein weiterer Quadtree verwendet der den Typ Integer aufnimmt. Diese Integer werden mit den Infos zu der entsprechenden Node des Terrains gefüllt. Es gibt somit vier verschiedene Zustände:

nodeInfoUninitialized	noch nicht analysiert, daher undefiniert
nodeInfoDontDraw	nicht zu zeichnen, Fehler wäre zu groß
nodeInfoDraw	zeichnen
nodeInfoInvisible	Node ausserhalb des sichtbaren Frustums

Das Zeichnen des Terrains erfolgt über die Benutzung von VBOs mit indizierten Vertexdaten. Alle Punkte des Terrains (1025×1025 Stück) werden in einem VBO an die Grafikkarte übergeben. Die Punkte sind zudem mit den korrekten Texturkoordinaten bereits fertig ausgestattet. Das Zeichnen der Dreiecke wird dann über die Indizes in diese Liste vorgenommen.

Das Zeichnen erfolgt ebenfalls wieder rekursiv: Jede Node die als zum zeichnen markiert wurde wird dann gezeichnet.

Ausgehend von der Mitte als Zentrum werden nacheinander die obere Kante, die rechte, die untere und dann die linke Kante mit Dreiecken gezeichnet. Dies ist in jedem Fall so. Es kann allerdings passieren, dass deutlich mehr Dreiecke nötig sind – und genau dann, wenn eine Node mit einem groben Level an viele mit feineren Leveln angrenzt:

Um die angrenzenden Nodes so zu verbinden müssen die gröberen Nodes auf die angrenzenden feineren Rücksicht nehmen. Dies bedeutet, jede der zu zeichnende Node muss ihre Nachbarn prüfen ob diese feiner sind oder nicht. Dies ist einfach festzustellen, denn eine Nachbarnode ist genau dann feiner wenn die Nachbarnode den Status nodeInfoDontDraw hat. Denn dann war der Fehler der Nachbarnode zu gross und sie wurde weiter unterteilt.

Ist dies der Fall, so muss die Liste der Unternodes des Nachbarn ermittelt werden und die Punkte auf der angrenzenden Seite zur aktuellen Node gesammelt werden. In einer Schleife können dann alle Dreiecke der Seite gezeichnet werden.

Hier sieht man einen Screenshot eines optimierten Terrains. Die hervorgehobene hat zur rechten und unteren Seite die feineren Nodes korrekt angebunden.

Die Dreiecke die zu zeichnen sind werden in einem intBuffer gesammelt und anschließend mit einem Mal per glBufferDataARB an die Grafikkarte gesendet. Diese zeichnet anschließend mit dem Aufruf von glDrawElements alle Dreiecke in einem Durchgang.

	/**
	 * Recursively visits the nodes and adds the triangle indices to the intBuffer which
	 * need to be rendered.
	 *
	 * @param frustum the frustum to cull with
	 * @param testCull flag whether to test culling for this node
	 * @param level the level to render from
	 * @param x the x coordinate of the node
	 * @param y the y coordinate of the node
	 */
	private void renderTerrain(final Frustum frustum, final boolean testCull, final int level, final int x, finalint y) {
		final int levelExtend = 1 << (level-1);
		final int terrainW = heightMap.getWidth() / levelExtend;
		final int terrainX = x * terrainW;
		final int terrainY = y * terrainW;
		boolean testchildren = false;

		// These are the draw flags for this level
		final int[][] flags = drawFlags.get(level-1);

		// Should we perform a culling test?
		if ( testCull && level < Terrain1ConsoleVars.maxLevelCullTest ) { 			fillBoxFor(level,x,y,tmpBBox); 			if ( !frustum.touches(tmpBBox)) { 				// if the bounding box is outside the frustum - leave now 				return; 			} else { 				if ( frustum.contains(tmpBBox)) { 					// If the box is completely in the frustum we can draw everything beyound us 					testchildren = false; 				} else { 					// we must test further 					testchildren = true; 				} 			} 		} 		// Is the current node to be drawn? 		if ( flags[x][y] == nodeInfoDraw ) { 			// Yes - go for it! 			int drawFlagLeft = nodeInfoDraw; 			int drawFlagRight = nodeInfoDraw; 			int drawFlagTop = nodeInfoDraw; 			int drawFlagBottom = nodeInfoDraw; 			// Check the neighbouring nodes 			if ( x>0 ) {
				// the maximum depth that will be rendered in the node left of us
				drawFlagLeft = flags[x-1][y];
			}
			if ( x0 ) {
				drawFlagTop = flags[x][y-1];
			}
			if ( y				drawFlagBottom = flags[x][y+1];
			}

			//   0--1--2
			//   |\ | /|
			//   | \|/ |
			//   3--4--5
			//   | /|\ |
			//   |/ | \|
			//   6--7--8
			nodeVertexIndices[0]=indexOf(terrainX,terrainY); // 0
			nodeVertexIndices[1]=indexOf(terrainX+terrainW/2,terrainY); // 1
			nodeVertexIndices[2]=indexOf(terrainX+terrainW,terrainY); // 2
			nodeVertexIndices[3]=indexOf(terrainX,terrainY+terrainW/2); // 3
			nodeVertexIndices[4]=indexOf(terrainX+terrainW/2,terrainY+terrainW/2); // 4
			nodeVertexIndices[5]=indexOf(terrainX+terrainW,terrainY+terrainW/2); // 5
			nodeVertexIndices[6]=indexOf(terrainX,terrainY+terrainW); // 6
			nodeVertexIndices[7]=indexOf(terrainX+terrainW/2,terrainY+terrainW); // 7
			nodeVertexIndices[8]=indexOf(terrainX+terrainW,terrainY+terrainW); // 8

			// If this is the max depth level we dont need to investigate anything further
			if ( level==maxDepth ) {
				intBuffer.put( nodeVertexIndices[0]);
				intBuffer.put( nodeVertexIndices[8]);
				intBuffer.put( nodeVertexIndices[6]);
				intBuffer.put( nodeVertexIndices[0]);
				intBuffer.put( nodeVertexIndices[2]);
				intBuffer.put( nodeVertexIndices[8]);

				// leave early
				return;
			}

			// For every neighbor we determine the list of vertex indices that are on the
			// specific border to the neighbor. These vertices are then used to draw the
			// triangles. This way wo don't need to assume any static level difference.

			if ( drawFlagTop == nodeInfoDontDraw ) {
				findTopIndices(level, x, y);
			} else {
				intBuffer.put( nodeVertexIndices[0]); // 0
				intBuffer.put( nodeVertexIndices[2]); // 2
				intBuffer.put( nodeVertexIndices[4]); // 4
			}

			if ( drawFlagRight == nodeInfoDontDraw ) {
				findRightIndices(level, x, y);
			} else {
				intBuffer.put( nodeVertexIndices[2]); // 2
				intBuffer.put( nodeVertexIndices[8]); // 8
				intBuffer.put( nodeVertexIndices[4]); // 4
			}

			if ( drawFlagBottom == nodeInfoDontDraw ) {
				findBottomIndices(level, x, y);
			} else {
				intBuffer.put( nodeVertexIndices[4]); // 4
				intBuffer.put( nodeVertexIndices[8]); // 8
				intBuffer.put( nodeVertexIndices[6]); // 6
			}

			if ( drawFlagLeft == nodeInfoDontDraw ) {
				findLeftIndices(level, x, y);
			} else {
				intBuffer.put( nodeVertexIndices[4]); // 4
				intBuffer.put( nodeVertexIndices[6]); // 6
				intBuffer.put( nodeVertexIndices[0]); // 0
			}
		} else if ( flags[x][y] == nodeInfoDontDraw ) {
			if ( level < maxDepth ) {
				renderTerrain(frustum, testchildren, level+1, x*2, y*2);
				renderTerrain(frustum, testchildren, level+1, x*2+1, y*2);
				renderTerrain(frustum, testchildren, level+1, x*2+1, y*2+1);
				renderTerrain(frustum, testchildren, level+1, x*2, y*2+1);
			}
		}
	}

Hier folgen nun ein paar Beispiele wie und dasselbe Terrain aus identischer Kameraposition bei verschiedenen Fehlergrenzwerten aussieht.

Weitere Optimierungen

Der Quadtree der die Zustände der Nodes speichert muss eigentlich bei jedem Frame neu initialisiert werden. Um diesen Aufwand zu sparen ändere ich bei jedem Frame die Werte der Status-Konstanten so dass das Programm erkennt ob ein Node-Status in diesem Frame gesetzt wurde oder nicht.

Im ersten Frame haben die Konstanten die Werte 0 bis 3, im zweiten Frame 10 bis 13 und so weiter. Wird beim Zeichen des zweiten Frames ein Status mit dem Wert 2 gefunden so weiß das Programm dass diese Node als nicht initialisiert gelten muss.