Diamond-square algorithm

The diamond-square algorithm is a method for generating heightmaps for computer graphics. It is a slightly better algorithm than the 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 of the plasma effect produced when applied.

The idea was first introduced by Fournier, Fussell and Carpenter at SIGGRAPH 1982.^[1] It was later analyzed by Gavin S. P. Miller in SIGGRAPH 1986^[2] who described it as flawed — the algorithm produces noticeable vertical and horizontal "creases" due to the most significant perturbation taking place in a rectangular grid.

The algorithm starts with a 2D grid then randomly generates terrain height from four seed values arranged in a grid of points so that the entire plane is covered in squares.

Midpoint displacement algorithm

File:Plasmafrac2.gif

Example on first iteration

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.

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}}

But when computing the middle height, one should add a small error that depends on the size of the rectangle (the standard is to let the error be proportional 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).

Iterate and subdivide each rectangle into smaller ones. Eventually, they will be too small to produce a noticeable difference. When this occurs, stop the iteration, and render the pixel with the mean of the height values.

The difference from the above algorithm is an intermediate step that regards diamond-shaped squares as well. This reduces the squared-shaped artifacts in the landscape, since the diamonds are rotated 45 degrees relative to the squares.

Applications

This algorithm can be used to generate realistic-looking landscapes, and different implementations are used in computer graphics software such as Terragen.

References

^ Fournier, Alain; Fussell, Don; Carpenter, Loren (June 1982). "Computer rendering of stochastic models". Communications of the ACM. 25 (6): 371–384. doi:10.1145/358523.358553. {{cite journal}}: |access-date= requires |url= (help)
^ Miller, Gavin S. P. (August 1986). "The definition and rendering of terrain maps". ACM SIGGRAPH Computer Graphics. 20 (4): 39–48. doi:10.1145/15886.15890. {{cite journal}}: |access-date= requires |url= (help)

External links

Simple open source heightmap module for Lua using diamond-square algorithm
Generating Random Fractal Terrain: The Diamond-Square Algorithm from GameProgrammer.com
Plasma Fractal from Justin Seyster's web page
Plasma fractals from Patrick Hahn's home page
Terrain Tutorial from Lighthouse3d.com
Random Midpoint Displacement with Canvas
Random midpoint displacement method

[fournier-1] Fournier, Alain; Fussell, Don; Carpenter, Loren (June 1982). "Computer rendering of stochastic models". Communications of the ACM. 25 (6): 371–384. doi:10.1145/358523.358553. {{cite journal}}: |access-date= requires |url= (help)

[miller-2] Miller, Gavin S. P. (August 1986). "The definition and rendering of terrain maps". ACM SIGGRAPH Computer Graphics. 20 (4): 39–48. doi:10.1145/15886.15890. {{cite journal}}: |access-date= requires |url= (help)

[1]

[2]