CPU-basierte Terrain Render Optimierung

Submitted by Stefan on 27. April 2009 - 21:05
in

Die Anbindung von unterschiedlichen DetailstufenDie Anbindung von unterschiedlichen DetailstufenTerrains 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.

Eine typische HeightmapEine typische Heightmap

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:

$\displaystyle x = s_{terrain} \frac{x_{pixel}}{s_{heightmap}} – 0.5 $
$\displaystyle y = h_{terrain} \frac{h_{pixel}}{255}} – 0.5 $
$\displaystyle z = s_{terrain} \frac{y_{pixel}}{s_{heightmap}} – 0.5 $

$ x_{pixel} $ X Wert des Pixels
$ y_{pixel} $ Y Wert des Pixels
$ h_{pixel} $ Die Höhe des Terrains an der Position ($ x_{pixel} $, $ y_{pixel} $)
$ s_{heightmap} $ Breite und Höhe des Heightmap-Image in Pixel
$ s_{terrain} $ Die gewünschte Breite und Tiefe des Terrains in Welt-Koordinaten
$ h_{terrain} $ 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;x<=heightMap.getWidth();x++) {
        for ( int y=0;y<=heightMap.getWidth();y++) {
                heightMapVectors[x][y] = new Vector();
                getVertexFromHeightmap(x, y, heightMapVectors[x][y]);
        }
}

/**
 * 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<0) h+=256;
        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).

Das Terrain mit allen DetailsDas Terrain mit allen Details

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!

OpenGLBlenderDrupal poweredSpieleentwicklertreff NRW