Diamond-square algorithm
From Wikipedia, the free encyclopedia
 |
This article's factual accuracy is disputed. Please see the relevant discussion on the talk page. (May 2008) |
The diamond-square algorithm is a method for generating highly realistic 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 Gavin S. P. Miller who described it as flawed.
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.
Contents |
[edit] Midpoint displacement algorithm
- 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
will have the height values 
- 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 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).
- 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.
[edit] Diamond-Square algorithm
The diffirence from the above algorithm is an intermediate step that regards diamond-shaped squares as well. This reduces the squared-shaped artefacts in the landscape, since the diamonds are rotated 45 degrees relative to the squares.
[edit] Applications
This algorithm can be used to generate realistic-looking landscapes, and different implementations are used in computer graphics software such as Bryce.
[edit] Papers
[Random Midpoint Displacement Method] Fournier,A., Fussel,D., and Carpenter, L. 1982. Computer Rendering of Stochastic Models. Communications of the ACM, 25: 371-384.
[edit] External links
- Generating Random Fractal Terrain: The Diamond-Square Algorithm from GameProgrammer.com
- Plasma Fractal from Justin Seyster's web page
- Processing.js Plasma Fractal Demo Justin Seyster's code converted for Processing.js
- Plasma fractals from Patrick Hahn's home page
- Terrain Tutorial from Lighthouse3d.com
- Random midpoint displacement method [1]
