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.
Plasma fractalAnimated plasma fractal with color cycling
The diamond-square algorithm starts with a two-dimensional 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 diamond-square algorithm begins with a two-dimensional square array of width and height 2n + 1. The four corner points of the array must first 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.
Each random value is multiplied by a scale constant, which decreases with each iteration by a factor of 2−h, where h is a value between 0.0 and 1.0 (lower values produce rougher terrain).[2]
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.
Visualizationedit
The image below shows the steps involved in running the diamond-square algorithm on a 5 × 5 array.
Applicationsedit
This algorithm can be used to generate realistic-looking landscapes, and different implementations are used in computer graphics software such as Terragen. It is also applicable as a common component in procedural textures.
Artifacts and extensionsedit
The diamond-square algorithm was analyzed by Gavin S. P. Miller in SIGGRAPH 1986[3] who described it as flawed because the algorithm produces noticeable vertical and horizontal "creases" due to the most significant perturbation taking place in a rectangular grid. The grid artifacts were addressed in a generalized algorithm introduced by J.P. Lewis.[4] In this variant the weights on the neighboring points are obtained by solving a small linear system motivated by estimation theory, rather than being fixed. The Lewis algorithm also allows the synthesis of non-fractal heightmaps such as rolling hills or ocean waves. Similar results can be efficiently obtained with Fourier synthesis,[5] although the possibility of adaptive refinement is lost. The diamond-square algorithm and its refinements are reviewed in Peitgen and Saupe's book "The Science of Fractal Images".[5]
Referencesedit
^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. ISSN 0001-0782.
^. 2006-04-20. Archived from the original on 2006-04-20. Retrieved 2022-12-13.
^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.
^Lewis, J. P. (1 July 1987). "Generalized stochastic subdivision". ACM Transactions on Graphics. 6 (3): 167–190. CiteSeerX10.1.1.21.3719. doi:10.1145/35068.35069. S2CID 14994949.
^ abPeitgen, Heinz-Otto, Dietmar Saupe (1988). The Science of Fractal Images. New York: Springer-Verlag. ISBN978-0-387-96608-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
External linksedit
Simple open source heightmap module for Lua using 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 Github (PHP)
An example of test-driving an implementation of the algorithm on Uncle Bob's Clean Coder blog
A Python implementation, short and straightforward. Handles both fixed and periodic boundary conditions.
January 01, 1970
diamond, square, algorithm, diamond, square, algorithm, method, generating, heightmaps, computer, graphics, slightly, better, algorithm, than, three, dimensional, implementation, midpoint, displacement, algorithm, which, produces, dimensional, landscapes, also. 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 Plasma fractal Animated plasma fractal with color cycling The idea was first introduced by Fournier Fussell and Carpenter at SIGGRAPH in 1982 1 The diamond square algorithm starts with a two dimensional 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 1 Description 2 Visualization 3 Applications 4 Artifacts and extensions 5 References 6 External linksDescription editThe diamond square algorithm begins with a two dimensional square array of width and height 2n 1 The four corner points of the array must first 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 Each random value is multiplied by a scale constant which decreases with each iteration by a factor of 2 h where h is a value between 0 0 and 1 0 lower values produce rougher terrain 2 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 editThe image below shows the steps involved in running the diamond square algorithm on a 5 5 array nbsp Applications editThis algorithm can be used to generate realistic looking landscapes and different implementations are used in computer graphics software such as Terragen It is also applicable as a common component in procedural textures Artifacts and extensions editThe diamond square algorithm was analyzed by Gavin S P Miller in SIGGRAPH 1986 3 who described it as flawed because the algorithm produces noticeable vertical and horizontal creases due to the most significant perturbation taking place in a rectangular grid The grid artifacts were addressed in a generalized algorithm introduced by J P Lewis 4 In this variant the weights on the neighboring points are obtained by solving a small linear system motivated by estimation theory rather than being fixed The Lewis algorithm also allows the synthesis of non fractal heightmaps such as rolling hills or ocean waves Similar results can be efficiently obtained with Fourier synthesis 5 although the possibility of adaptive refinement is lost The diamond square algorithm and its refinements are reviewed in Peitgen and Saupe s book The Science of Fractal Images 5 References edit 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 ISSN 0001 0782 Generating Random Fractal Terrain 2006 04 20 Archived from the original on 2006 04 20 Retrieved 2022 12 13 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 Lewis J P 1 July 1987 Generalized stochastic subdivision ACM Transactions on Graphics 6 3 167 190 CiteSeerX 10 1 1 21 3719 doi 10 1145 35068 35069 S2CID 14994949 a b Peitgen Heinz Otto Dietmar Saupe 1988 The Science of Fractal Images New York Springer Verlag ISBN 978 0 387 96608 3 a href Template Cite book html title Template Cite book cite book a CS1 maint multiple names authors list link External links editSimple 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 Github PHP An example of test driving an implementation of the algorithm on Uncle Bob s Clean Coder blog Xmountains classic sideways scrolling X11 implementation Algorithm details A Python implementation short and straightforward Handles both fixed and periodic boundary conditions Retrieved from https en wikipedia org w index php title Diamond square algorithm amp oldid 1181050351, wikipedia, wiki, book, books, library,
