Diamond-square algorithm

From Wikipedia, the free encyclopedia

$Plasma fractal$

Plasma fractal

The diamond-square algorithm is a method for generating highly realistic heightmaps for computer graphics. It is a three-dimensional implementation of the midpoint displacement algorithm which produces two-dimensional landscapes.

It is also known as the random midpoint displacement fractal, the cloud fractal or the plasma fractal, because the Plasma effect gives a nice "plasma-like" effect when applied to this fractal.

[edit] Algorithm

First assign a height value to each corner of the rectangle (image).

Divide the rectangle into 4 subrectangles, and let their height values be the mean values of the corners of the parent rectangle.

Example on first iteration

For example, the upper left sub-rectangle in $\begin{bmatrix} 0 & 2 \\ 4 & 8\\ \end{bmatrix}$ will have the height values $\begin{bmatrix} 0 & (0+2)/2 \\ (0+4)/2 & (0+2+4+8)/4 \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 2 & 3.5\\ \end{bmatrix}$ , see image to the right.

But when computing the middle height, one should add a small error, that depends on the size of the rectangle. (Standard is to let the error be propotional to the size of the rectangle and some constant. The constant controls the "roughness" of the fractal; a bigger constant results in more valleys and mountains.)

Iterating and subdividing each rectange into smaller ones, sooner or later they will be smaller than one pixel. When this occurs, break the iteration, and paint that pixel with the mean of the height values.