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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * setMap * * Sets internal values of point: * - but only, if this point was not set before * - if seamless: mirrors left and upper values to right and/or bottom * * @param int $x x-coordinate * @param int $y y-coordinate * @param float $value greyscale of this point */ private function setMap( $x, $y, $value ) { if( !isset( $this->_map[ $x ][ $y ] ) ) { $this->_map[ $x ][ $y ] = $value; if( $this->_seamless == true ) { // mirrors values from left and/or from top if( $x == 0 ) { $this->_map[ $this->_size - 1 ][ $y ] = $value; } if( $y == 0 ) { $this->_map[ $x ][ $this->_size - 1 ] = $value; } } } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/** * copyMapValues * * Copies existing values from given maps from left or upper cloud images */ private function copyMapValues() { // copy left values if( count( $this->_map_left ) > 0 ) { for( $y = 0; $y < $this->_size - 1; $y++ ) { $this->setMap( 0, $y, $this->_map_left[ $this->_size-1 ][ $y ] ); } } // copy top values if( count( $this->_map_top ) > 0 ) { for( $x = 0; $x < $this->_size - 1; $x++ ) { $this->setMap( $x, 0, $this->_map_top[ $x ][ $this->_size-1 ] ); } } } |
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:
1 2 3 4 |
$img = imagecreatetruecolor( 256, 256 ); $generator = new Cloud( $img ); $generator->init( 6 ); imagepng( $img, $filename ); |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 |
<?php /** * Generator: Cloud - Generates a procedural cloud texture * * Implements Diamond-square algorithm. * Ported and corrected from * https://github.com/Vesther/Cloud-Fractal/blob/master/PlasmaFractal.cpp * * Enhanced for Mission on Mars - UVMap-Generator * * @copyright 2018 Michael Scheffler * @license https://de.wikipedia.org/wiki/Beerware Beerware License Rev.42 * @version Release: 1.0 * @link http://www.grafiction.de */ namespace App\Lib\Substance\Generator; class Cloud { private $_size; // x & y size private $_d; // dynamic private $_r; // roughness private $_seamless; // wether to be seamless or not private $_map; // internal values - must be rendered if computed /** * Constructor * * Fills the given image with a fractal cloud image based on Diamond-square. * All existing information of the image will be lost. * * @param resource &$img the image must be quad sized and of size n^2 */ public function __construct( &$img ) { $this->_img = $img; $this->_size = imagesx( $this->_img ); // check if size is n^2 if( ( $this->_size & ( $this->_size - 1 ) ) != 0 ) { throw new \Exception( 'Generator Cloud: imagesize must be n^2!' ); } // check if quad size if( $this->_size != imagesy( $this->_img ) ) { throw new \Exception( 'Generator Cloud: imagesize must be quad!' ); } // enhance size by 1 $this->_size++; } /** * Init * * Sets internal parameters and calculates the cloud image * * @param int $seed seed for random generator * @param bool $seamless true if the cloud should be seamless * @param int $d dynamic of changing grey values * @param float $r roughness of changing dynamic in further steps * @param array $map_left map of points of existing cloud on left side * @param array $map_top map of points of existing cloud on upper side * * @return array two-dimensional array of points with grey values [x][y] */ public function init( int $seed = 0, bool $seamless = false, int $d = 200, float $r = 1.0, array $map_left = [], array $map_top = [] ) { // Init random generator srand( $seed ); // internal values $this->_d = $d; $this->_r = $r; $this->_seamless = $seamless; $this->_map = []; $this->_map_left = $map_left; $this->_map_top = $map_top; // algorithm $this->copyMapValues(); $this->generateCloudValues(); $this->renderMapToImage(); return $this->_map; } /** * averageAndOffset * * Calculates average of max. four values and added a random value * * @param float $v1 first value * @param float $v2 second value * @param float $v3 third value * @param float $v4 fourth value * @param int $d offset for random generation from -d/2 to d/2 * @param int $c divisor (should be number of given values) * * @return float average + offset in a range of 0 to 255 */ private function averageAndOffset( float $v1, float $v2, float $v3, float $v4, int $d, int $c = 4 ) { $offset = ( -$d / 2 ) + rand( 0, $d ); $avg = ( $v1 + $v2 + $v3 + $v4 ) / $c + $offset; // limit values if( $avg < 0 ) { $avg = 0; } if( $avg > 255 ) { $avg = 255; } return $avg; } /** * edgeHelper * * Calculates average of suares containing maybe less than 4 points. * Used in the stepSquare pass. * * @param int $x x-coordinate * @param int $y y-coordinate * @param int $sideLength actual processing side length * * @return float average + offset in a range of 0 to 255 */ private function edgeHelper( int $x, int $y, int $sideLength ) { $counter = $accumulator = 0; $halfSide = $sideLength / 2; if( $x != 0 ) { $counter++; $accumulator += $this->_map[ $y ][ $x - $halfSide ]; } if( $y != 0 ) { $counter++; $accumulator += $this->_map[ $y - $halfSide ][ $x ]; } if( $x != $this->_size - 1 ) { $counter++; $accumulator += $this->_map[ $y ][ $x + $halfSide ]; } if( $y != $this->_size - 1 ) { $counter++; $accumulator += $this->_map[ $y + $halfSide ][ $x ]; } $avg = $this->averageAndOffset( $accumulator, 0, 0, 0, $this->_d, $counter ); $this->setMap( $y, $x, $avg ); } /** * copyMapValues * * Copies existing values from given maps from left or upper cloud images */ private function copyMapValues() { // copy left values if( count( $this->_map_left ) > 0 ) { for( $y = 0; $y < $this->_size - 1; $y++ ) { $this->setMap( 0, $y, $this->_map_left[ $this->_size-1 ][ $y ] ); } } // copy top values if( count( $this->_map_top ) > 0 ) { for( $x = 0; $x < $this->_size - 1; $x++ ) { $this->setMap( $x, 0, $this->_map_top[ $x ][ $this->_size-1 ] ); } } } /** * generateCloudValues * * Main loop of algorithm */ private function generateCloudValues() { // init four corners $this->setMap( 0, 0, rand( 0, 255 ) ); $this->setMap( 0, $this->_size - 1, rand( 0, 255 ) ); $this->setMap( $this->_size - 1, 0, rand( 0, 255 ) ); $this->setMap( $this->_size - 1, $this->_size - 1, rand( 0, 255 ) ); // calculate first pass $sideLength = $this->_size - 1; $this->stepDiamond( $sideLength ); $this->stepSquare( $sideLength ); // reduce sidelength by half and interate $sideLength /= 2; while( $sideLength >= 2 ) { $this->stepDiamond( $sideLength ); $this->stepSquare( $sideLength ); $sideLength /= 2; // reduce dynamic by given roughness $this->_d *= pow( 2, -$this->_r ); } } /** * renderMapToImage * * Renders the values of intern _map to the image */ private function renderMapToImage() { for( $x = 0; $x < $this->_size - 1; $x++ ) { for( $y = 0; $y < $this->_size - 1; $y++ ) { $grey = $this->_map[$x][$y]; $color = imagecolorallocate( $this->_img, $grey, $grey, $grey ); imagesetpixel( $this->_img, $x, $y, $color ); } } } /** * setMap * * Sets internal values of point: * - but only, if this point was not set before * - if seamless: mirrors left and upper values to right and/or bottom * * @param int $x x-coordinate * @param int $y y-coordinate * @param float $value greyscale of this point */ private function setMap( $x, $y, $value ) { if( !isset( $this->_map[ $x ][ $y ] ) ) { $this->_map[ $x ][ $y ] = $value; if( $this->_seamless == true ) { // mirrors values from left and/or from top if( $x == 0 ) { $this->_map[ $this->_size - 1 ][ $y ] = $value; } if( $y == 0 ) { $this->_map[ $x ][ $this->_size - 1 ] = $value; } } } } /** * stepDiamond * * First step of the algorithm: * Calculates the greyscale in the center of four points * * @param int $sideLength the actual side length of the pass */ private function stepDiamond( $sideLength ) { $halfSide = $sideLength / 2; for( $y = 0; $y < ( $this->_size - 1 ) / $sideLength; $y++ ) { for( $x = 0; $x < ( $this->_size - 1 ) / $sideLength; $x++ ) { $center_x = $x * $sideLength + $halfSide; $center_y = $y * $sideLength + $halfSide; $v1 = $this->_map[ $x*$sideLength ][ $y*$sideLength ]; $v2 = $this->_map[ $x*$sideLength ][ ($y+1)*$sideLength ]; $v3 = $this->_map[ ($x+1)*$sideLength ][ $y*$sideLength ]; $v4 = $this->_map[ ($x+1)*$sideLength ][ ($y+1)*$sideLength ]; $avg = $this->averageAndOffset( $v1, $v2, $v3, $v4, $this->_d ); $this->setMap( $center_x, $center_y, $avg ); } } } /** * stepSquare * * Second step of the algorithm: * Calculates the greyscale of the new four points from a diamond * * @param int $sideLength the actual side length of the pass */ private function stepSquare( $sideLength ) { $halfLength = $sideLength / 2; for( $y = 0; $y < ( $this->_size - 1 ) / $sideLength; $y++ ) { for( $x = 0; $x < ( $this->_size - 1 ) / $sideLength; $x++ ) { // Top $this->edgeHelper( $x * $sideLength + $halfLength, $y * $sideLength, $sideLength ); // Right $this->edgeHelper( ($x+1) * $sideLength, $y*$sideLength + $halfLength, $sideLength ); // Bottom $this->edgeHelper( $x*$sideLength + $halfLength, ($y+1)*$sideLength, $sideLength ); // Left $this->edgeHelper( $x*$sideLength, $y*$sideLength + $halfLength, $sideLength ); } } } } |