Algorithmus: Diamond-square

Lesezeit: 8 Minuten

Um schöne Wolken-Muster zu erzeugen, benutze ich den sogenannten Diamond-square Algorithmus. Manchmal ist er unter dem Namen „Cloud-Fractal“ oder „Plasma-Fractal“ bei Google zu finden.

Da ich den Algorithmus auf dem Server benötige, hier meine PHP-Implementierung.

Habe ich banal im Blog: Mission on Mars: UV-Map generieren erzählt, dass ich ein Wolkenmuster benutze, um Sandstrukturen zu erhalten, erkläre ich hier, wie ich diese Wolke erzeugt habe.

Vielfach wird dieser Algorithmus angewendet, um zufällige Höhenbilder zu erzeugen, welche dann bei Computerspielen als Grundlage benutzt wird, eine Landschaft darzustellen.

Nachteil dieses Algorithmus ist allerdings die „Gleichförmigkeit“ – daher benutze ich ihn lediglich als Ausgangspunkt für Texturen und für mehr oder weniger chaotischen Strukturen; halt für Sand und Steine, etc.

Die Definition des Algorithmus findet man hier: https://de.wikipedia.org/wiki/Diamond-square_Algorithmus

Allen Performance-Warnungen zum Trotz erfolgt meine Implementierung in PHP, weil ich diesen Algorithmus auf dem Server benötige.

Grundsätzliches

Der Algorithmus basiert auf Halbieren von Quadraten. Damit ist die Ausgabe fixiert auf eine Höhe bzw. Breite von 2^n + 1. Also z. B. 129 x 129.

Da ich nahtloses Aneinanderreihen von Wolkenstrukturen erzielen möchte, achte ich auf entsprechende Hilfsfunktionen.

Die Funktion soll Pseudo-Zufallszahlen generieren, bei gleicher Parameter-Wahl jeweils aber immer die selbe Wolke erzeugen (Seed mit Pseudo-Randoms).

Als Ausgabe erfolgt immer eine Graustufen-PNG ohne Transparenz.

Ablauf

Ich setze die vier Eckpunkte des Bildes auf einen zufälligen Grauwert abhängig vom eingegebenen Seed-Wert.

Dann setze ich den Mittelpunkt der vier Werte auf einen Mittelwert aus allen vier Graustufen plus/minus gewollter Abweichungen. Dazu benutze ich eine Abweichungsvariable $d (Dynamic). Aus den nun gewonnenen 4 neuen Quadraten ermittel ich wieder den Mittelpunkt und berechne mit diesem Verfahren wieder neue Werte. Bei diesen Schritten wird die Dynamic immer weiter durch eine Roughness-Variable abgemildert. Das erzeugt besagte Wolkenbilder.

Sehr anschaulich erklärt ist dieser Algorithmus z. B. hier: http://stevelosh.com/blog/2016/06/diamond-square/

Als Basis für meine Implementierung habe ich einige Stellen daraus portiert: https://github.com/Vesther/Cloud-Fractal/blob/master/PlasmaFractal.cpp

Implementierung

Ich fasse den Algorithmus in einer eigenen Klasse zusammen. Dabei trenne ich absichtlich den Konstruktor von einer Init-Funktion, da PHP overloading von Konstruktoren nicht so ohne weiteres unterstützt. Näheres dazu später.

Ich arbeite intern mit einem Punkte-Array und visualisiere abschließend die Werte des Punkte-Arrays als Graustufen in einem Bild.

Seamless

Damit die Wolke für sich alleine eine seamless texture wird, spiegel ich ggf. den linken und/oder oberen Rand nach rechts bzw. nach unten:

Möchte ich das eine neu generierte Wolke nahtlos an eine andere Wolke passt, muss ich die Werte vorheriger Wolken übernehmen können – auch hier reichen die jeweiligen Ränder:

Anwendung

Einfache Generierung – Seed = 6

Diese Textur in 2×2:

Seamless Generierung – Seed 6 und true:

Und als 2×2:

Königsdisziplin Seamless Generierung mit 4 Wolken jeweils einzeln nicht seamless und unterschiedlichen Seeds, aber mit Werten früherer Maps:

Seed 6 (oben links):

Seed 7 (oben rechts):

Seed 8 (unten links):

Seed 9 (unten rechts):

Zusammengesetzt als 2×2 Textur:

So ist dieser Algorithmus wirklich universell einsetzbar für die Generierung von Wolken.

Anwendung

Grundsätzlich kann die Klasse z. B. so eingesetzt werden:

Weiterführende Links

Diesen und  zukünftig erarbeitete Algorithmen möchte ich zusammenfassen in einer dynamischen Klasse, die mir Materialgenerierung ermöglicht. Dazu später mehr.

PHP-Code

Abschließend noch der Code der Klasse in Gänze:

 

 

 

 

 

 

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.