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.
The Algorithm
The diamond-square algorithm begins with a 2D array of size 2n + 1. The four corner points of the array must firstly be set to initial values. The diamond and square steps are then performed alternately until all array values have been set.
The diamond step. For each square in the array, set the midpoint of that square to be the average of the four corner points plus a random value.
The square step. For each diamond in the array, set the midpoint of that diamond to be the average of the four corner points plus a random value.
At each iteration, the magnitude of the random value should be reduced.
During the square steps, points located on the edges of the array will have only three adjacent values set rather than four. There are a number of ways to handle this complication - the simplest being to take the average of just the three adjacent values. Another option is to 'wrap around', taking the fourth value from the other side of the array. When used with consistent initial corner values this method also allows generated fractals to be stitched together without discontinuities.
Visualization
The image below shows the steps involved in running the diamond-square algorithm on a 5 × 5 array.
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
- Diamond And Square algorithm on PHP Github