.heightMap I

Grundlagen und Gedanken zu HeightMaps
zurück .weiter zu heightMap II
Auf dieser Seite möchte ich ein paar Gedanken und Informationen zu Heightmaps unterbringen mit denen ich mich ein paar Tage lang beschäftigt habe und hoffe auch das eine mehr oder weniger verständnisfördernde gerenderte Bilder aus meinem in C++ geschriebenen Heightmapgenerator zu zeigen.
Nach und nach, wenn die Quelltexte getestet und stabil (und mit den nötigsten Kommentaren versehen) sind, werde ich sie auf meiner Seite veröffentlichen.


Eine Heightmap ist ein 2 dimensionales Zahlenfeld. So könnte man zum Beispiel eine Tabelle als Heightmap verwenden. Als Beispiel soll folgende Tabelle dienen:
  Spalte 1 Spalte 2 Spalte 3 Spalte 4
Reihe 1 4 6 5 6
Reihe 2 6 8 7 7
Reihe 3 5 6 5 6
Reihe 4 2 3 4 6

Der Zelleninhalt könnte als Höhenangaben eines rechteckigen Untergrundes interpretiert werden. Legt man sich auf eine Skalierung für X, Y und Z fest, ist es also möglich in Form einer solchen Tabelle eine Oberfläche in diskreten Punkten zu beschreiben.

Im folgenden verwende ich - im Gegensatz zu den gängigen 3D API's - ein Koordinatensystem, bei dem die x Achse nach rechts und die y Achse in die Tiefe zeigt. Der z Wert beschreibt also die Höhe ("Rechte Hand System" um -90 Grad um den Daumen gedreht).
Ist eine Fläche von 3x3 Metern gemeint und wird der Ursprung (x = 0 Meter und y = 0 Meter) festgelegt als Tabelleneintrag Reihe 1 / Spalte 1, kann das Gelände für eine Reihe von Punkten bestimmt werden.
Bei (0/0) ist das Gelände 4 Meter hoch, bei (3/1) ist es 7 Meter hoch und bei (3/3) ist es 6 Meter hoch.


Durch bidirektionale Interpolation können nun auch die Werte für Stellen zwischen den bekannten Punkten berechnet werden. (Ich verwende im folgenden "Heightmap" als eine Funktion, die als Parameter x und y erhält und den z Wert liefert...)

Beispiel: Bei (1,6/1,1) ist uns kein Eintrag bekannt, wir kennen nur
h1 = Heightmap(x1, y1) = Heightmap(1, 0) = 6
h2 = Heightmap(x2, y2) = Heightmap(2, 0) = 5
h3 = Heightmap(x3, y3) = Heightmap(1, 1) = 8
h4 = Heightmap(x4, y4) = Heightmap(2, 1) = 7

Wir interpolieren zunächst in x Richtung:
dx1 = (x2 - x1)       p1 = (x - x1) / dx1       m1 = h1 * (1-p) + h2 * p
dx2 = (x4 - x3)       p2 = (x - x3) / dx3       m2 = h3 * (1-p) + h4 * p

In unserem Fall ergibt das dx1 = dx2 = 1, p1 = p2 = 0,6
m1 = 6 * 0,6 + 5 * 0,4 = 5,6
m2 = 8 * 0,6 + 7 * 0,4 = 7,6 Ebenso können wir die beiden ermittelten y Werte natürlich wieder in y Richtung interpolieren und erhalten so in unserem Fall:
h = 5,6 * 0,1 + 7,6 * 0,9 = 7,4


Fazit: Ein zweidimensionales Zahlenfeld kann eine Oberfläche beschreiben. Die einfachste Variante ein solches Zahlenfeld zu erhalten oder zu speichern ist ein Bitmap - also eine Bilddatei. In der Regel ist eine Heightmap ein Bitmap in dem nur Grauwerte gespeichert sind. Breite und Höhe entsprechen x und y Richtung der Oberfläche und je heller ein Punkt ist, desto höher ist das Terrain an dieser Stelle.
Eine normalisierte Heightmap beinhaltet nur Zahlen im Intervall [0..1]. Durch eine Skalierung kann jeder Punkt vor der Nutzung auf die richtige Höhe gebracht werden, nach dem Normalisieren und Strecken auf 255 (und Runden auf Integerwerte) kann dann wiederum das Zahlenfeld mit Header versehen als Bitmap gespeichert werden (0 = Schwarz, 255 = Weiss).
Eine einfache, leere Heightmap wäre zum Beispiel visuell dargestellt:
Zu Heightmaps an sich gibt es im Netz für das Grundverständnis eine ganze Menge an Informationen und ich möchste ja auch kein Tutorial schreiben, sondern einfach Anregungen für 3D Programmierer geben die schon ein wenig "auf eigenen Füssen stehen".
Der erste Schritt für mich war nun ein "Displaylist Generator" für OpenGL, der eine solche Heightmap ausliest und in ein polygonales Netz transformiert. Die Vertices (Eckpunkte der Geometrie) werden also im voraus berechnet und texturiert und sind im Rendervorgang über einen Quadtree (den ich noch aus dem LOD-Projekt hatte) in Form von Displaylisten abrufbar - also ohne die Daten wieder und wieder an die Grafikhardware zu senden.
Sobald man aus einem schwarzen Bitmap ein glattes, flaches Netz erzeugt hat, kann man sich dann den eigentlichen Algorithmen zuwenden. Ich habe mich mit den verschiedenen Algorithmen zur Heightmapgeneration auseinandergesetzt und blieb vor allem auch an der Theorie von Perlin Noise hängen. Dennoch habe ich über kurz oder lang gemerkt, dass ich eine ganz spezielle "runde, >smoothe<" Landschaftstruktur erzeugen will und mir daher eine eigenen Generator für diesen Zweck geschrieben. Die Idee kam mir als ich eine Testmap schnell im PaintShop gemalt hatte und mit dieser per Hand gezeichneten Heightmap arbeitete:


 

 
HeightMap durch weitere Iteration generieren
Die Idee war einfach die folgende: Statt aus einer Datei die Heightmapdaten auszulesen, generiere ich mir die Heightmaps "on the fly" - also prozedural - und zwar nach exakt dem Muster wie die eben genannte PaintShop Datei: Ich erstelle an beliebiger Stelle der Heightmap mit einen zufällig gewählten Radius und einer zufällig gewählten Höhe einen solchen idealen "Hügel". Das ganze iteriere ich ein paar mal durch und am Ende normalisiere und skaliere ich die Map. Das Ergebnis sieht wie folgt aus:

1, 5, 20, 50, 100 und 200 Iterationen:

Das Aussehen der Landschaft ist stark davon abhängig, wie die Beschränkungen der Zufallswerte gewählt werden - also z.B. minRadius, maxRadius eines Hügels oder die Skalierung. Eine kontrastreichere Landschaft (ab jetzt texturiert mit einem Gitternetz) folgt im nächsten Beispiel.

Neben der Normalisierungsroutine habe ich auch ein normalise_and_invert() eingebaut, was in etwa folgende Ergebnisse liefert:

 

 
Täler/Flattening per exp(), isle() u.a. Berechnungen
Auf jeden Fall sind für eine Landschaft schon mal genügend Hügel und Berge vorhanden. Das Problem ist der - nicht vorhandene - Zwischenraum, sprich Täler zwischen den Bergen. Nach ein wenig Recherche im Netz kam ich zum "flattening" oder "washing" der Landschaft. Ohne aufwändiges Zusammenmischen verschiedener Landschaftsstrukturen kann man ganz einfach die normalisierte Heightmap, die ja nur Werte zwischen 0 und 1 besitzt quadrieren. Die Höhe 1 bleibt dabei unverändert, niedriger liegende Gebiete werden weiter abgeflacht... Die zugehörige Routine ist denkbar einfach zu implementieren und statt eines einfachen Quadrates habe ich die pow() Funktion bemüht und so folgende - auch bei Exponenten < 1, wie zum Beispiel der Quadratwurzel - interessante Ergebnisse erhalten:

Zunächst die Heightmaps des Testhügels samt Ausgabe für die Exponenten 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 2.0, 3.0, 4.0, und 5.0:

Im folgenden kann man das Ergebnis verschiedener Exponenten angewand auf die weiter oben gezeigte Landschaft sehen:

Um aus einer solchen Landschaft jetzt zum Beispiel eine Insel zu erstellen habe ich den Algorithmus erweitert: Die Heightmap wird mit einem vom Mittelpunkt bei 1 liegenden und zum Rand hin abfallenden Wert multipliziert. Dieser Wert wird allerdings ebenfalls mit einer pow() Funktion kombiniert um keinen linearen abfall zum Rand hin zu erzeugen, sondern ähnlich der oben beschriebenen Hügelformen zu funktionieren:

heightmap->island(0.25)
heightmap->island(0.5)
heightmap->island(0.75)
heightmap->island(1.0)
heightmap->island(1.5)
heightmap->island(2.0)


Die nächste Operation, die sich für Heightmaps anbietet, ist die Addition und die Multiplikation zweier Heightmaps.
Sind die Quellen normalisiert, so entsteht bei der Addition eine Heightmap im Intervall [0..2] bzw. bei der Multiplikation wieder eine normalisierte Map [0..1].
Ausserdem sind 2 prozedurale Generatoren mit "statischen" Funktionen dazugekommen:
Generatorfunktion A1 erstellt den bereits oft gesehen "standard Hügel" mit beliebigem Radius in der Mitte der Karte, Funktion A2 legt Sinuskurven mit unterschiedlicher x und y Frequenz übereinander. Die Erzeugung solch statischer Karten kann nach deren Bearbeitung mit flat() oder anderen Kombinationen sinnvoll sein um sie mit "random"-Karten zu mischen (add oder mul-Funktionen).
Ausserdem habe ich eine clipping Methode eingeführt. Nachfolgend eine auf diese Weise erzeugte Sinusüberlagerung mit x und y Frequenz 3.0 sowie das darauf angewandte Clipping (hier: heightMap->clip(0.35, 0.75)):


.weiter zu heightMap II zurück