Terrain FAQ

[life]

Da in letzter Zeit desöfteren Fragen zur Terraindarstellung kommen, hab ich mir mal die Mühe gemacht und eine kleine Terrainfaq geschrieben. :xmas1:

Terraindarstellung? Wie funktioniert das?
Es gibt viele Möglichkeiten ein Terrain darzustellen. Zunächst muss man sich überlegen, wie man ein Terrain beschreiben will. Eine einfache und häufig genutzte Möglichkeit hierzu, ist es das darzustellende Terrain in ein regelmäßiges n x n – Grid einzuteilen und die Höhe eines jeden Punktes in diesem Grid zu speichern (Heightmap). In C++ könnte man dies beispielsweise einfach mit einem 2-dimensionalen Array, das jeweils die Höhendaten abspeichert, umsetzen. Um die eigentlichen Höhendaten einzulesen, kann man Graustufenbilder nutzen, wobei dann die Höhe des jeweiligen Pixels durch seine Farbe bestimmt ist (z.B. an Position / Pixel (5,6) ist die Farbe (255,255,255) und somit die Höhe 255).

Als nächstes stellt sich die Frage, wie man nun die Höhendaten graphisch darstellen kann. Als naiven Ansatz, kann man einfach die jeweiligen Quadrate, die durch jeweils 4 Höhenpunkte definiert sind, in 2 Dreiecke unterteilen und diese mit Hilfe einer beliebigen 3D-API zeichnen. Somit erhält man die komplette Landschaft, aber natürlich ohne Texturierung und Belichtung. Allerdings ist dieses Verfahren nur bei kleinen Heightmaps sinnvoll. Bei größeren Terrains werden die LOD-Algorithmen immer attraktiver.

LOD-Algorithmen? Was ist das?
Level of Detail (LOD) – Algorithmen teilen, wie der Name vermuten lässt, das Terrain in bestimmte Stufen (Levels) des Detailreichtums ein. So wird beispielsweise den Landschaftsabschnitten, die der Kamera nah sind, häufig in einem höheren Detailgrad dargestellt, als solche, die in weiter Ferne liegen. D.h., dass z.B. bei den Gebirgen im Hintergrund, wird nicht mehr jeder einzelne Höhenpunkt in der Heightmap wirklich dargestellt wird, sondern vielleicht nur noch jeder 5. Somit gehen natürlich wahrscheinlich jede Menge Informationen verloren, jedoch sagt nun der LOD-Algorithmus, dass auf diese große Entfernung hin, diese Informationen eh nicht mehr wahrgenommen werden würden und deshalb weggelassen werden können. Ein weiteres Kriterium für den Detailgrad kann auch die „Rauheit“ des Terrains sein. So ist natürlich nicht sehr sinnvoll bei einer vollkommen flachen Landschaft zig Höhenpunkte zu zeichnen, obwohl alle die gleiche Höhe haben und somit gar nicht sichtbar sind. D.h. bei dem entfernern dieser Höhenpunkte würde in diesem Extremfall gar keine Information verloren gehen.

Wo finde ich LOD-Algorithmen?
LOD-Algorithmen gibt wie Sand am Meer. Eine kleine Übersicht bietet folgende Seite: http://www.vterrain.org/LOD/Papers/index.html

Was versteht man unter Geomorphing?
Bei LOD-Algorithmen könnt es häufig zu dem Problem des „poppings“. Hier erscheinen durch Veränderung der Kameraposition plötzlich neue Höhendaten, die vorher durch den LOD-Algorithmus als unwichtig eingestuft werden, auf dem Bildschirm. Dies kann im dazu führen, dass eine kleine Hügel aus dem Nichts erscheinen und so auf den Bildschirm „poppen“. Dies will man natürlich vermeiden. Daher hat man sich überlegt, dass diese neuen Höhenpunkte zwar einfügt, allerdings die Höhe zunächst auf der alten belässt und die Höhe dann langsam der echten Höhe anpasst. Dies kann z.B. über eine bestimmten Zeitraum geschehen oder auch abhängig von der Kameraposition.

Da der Geomorphing-algorithmus stark abhängig vom gewählten LOD-Algorithmus ist, wird ein solcher meist zusammen mit dem LOD-Algorithmus beschrieben.

Terrain texturieren? Wie wird das gemacht?
Auch hier gibt es natürlich viele Möglichkeiten. Eine einfache Möglichkeit, ist es einfach eine Textur, die so groß ist wie das Terrain, über das ganze Terrain zu legen. Natürlich würde diese Textur bei großen Terrains entsprechend auch gigantische Ausmaße annehmen. Daher kann man auch in Betracht ziehen, das Terrain dynamisch zu texturieren. So kann man beispielsweise abhängig von der absoluten Höhe eines jeden Terrainpunktes von bestimmten Grundtexturen wählen. So könnte man z.B. Sand, Grass, Gestein und Schnee als Grundtextur wählen und dann abhängig der Höhe diese zusammenmischen. Also erhält eine hohe Gebirgsfront eine Mischung aus Gestein und Schnee, und das Tal darunter eine Grasstextur. Natürlich kann man sich auch ganz andere Kriterien für das mischen vorstellen (z.B. ist der jeweilige Höhenpunkt an einem Steilhang oder auf einer flachen Landschaft?). Das Verfahren des dynamischen texturieren mit Hilfe von Grundtexturen wird auch „texture splatting“ genannt.

Terrainbelichtung? Welche Möglichkeiten gibt es?
Eine einfache Möglichkeit der Belichtung des Terrains, ist es für jedes Quadrat im Grid die Ebenennormale zu berechnen und dann abhängig vom Winkel des Vektors zum Sonneneinstrahlungsvektors die Helligkeit des Quadrates zu berechnen. Dies ist natürlich ein sehr einfacher Algorithmus, der aber recht gute Ergebnisse liefern kann.

Bessere Ergebnisse erhält man z.B. durch per-pixel lighting (für jeden Pixel einzeln die Schattierung ausrechnen) oder z.B. auch indem man den Schattenwurf mit einberechnet. Da ich aber auf diesem Gebiet nicht sehr viel Erfahrung habe, verweise ich an dieser Stelle einfach auf folgende Seiten:
http://www.vterrain.org/Performance/lighting.html
http://www.gamedev.net/reference/list.asp?categoryid=40#135

Wie stell ich große Heightmaps dar ohne sie komplett ins RAM laden zu müssen?
Ein übliches Verfahren hierzu ist es, die Heightmap immer nur Blockweise einzulesen. Da mit einem LOD-Algorithmus nicht alle Höhendaten genutzt werden, müssen natürlich auch nicht alle Höhendaten im RAM sein.

Es gibt wiederum viele Möglichkeiten, wie man am besten die Datei mit den Höhendaten einlesen muss, damit man möglichst wenig Daten nachlesen muss, wenn die Kameraposition sich verändert. Wenn man sich allerdings einfach machen will, kann man auch einfach die von Windows bereitgestellte Funktion dafür nutzen (http://www.flipcode.com/articles/article_filemapping.shtml).
Natürlich muss hier darauf geachtet werden, dass Daten, die zusammen gebraucht werden, auch in der Datei möglichst nebeneinander gespeichert werden, um die benötigten Blockeinlesungen zu minimieren. Hierfür bietet es sich also an eine andere Datenstruktur als ein Graustufenbild zu verwenden. Allerdings hängt die benötigte Datenstruktur jeweils stark vom gewählten LOD-Algorithmus und vom der Art der Kamerabewegung ab.

Ergänzungen und Korrekturen sind natürlich erwünscht.