imported>Bearcat: /* top */ dabfix

2025-04-13T18:16:52Z

top: dabfix

New page

{{short description|Method for generating heightmaps for computer graphics}}
[[Image:Plasmafractal.gif|200px|right|thumb|Plasma fractal]]
[[File:-PLASMA-ColorCycling.Gif|200px|thumb|right|Animated plasma fractal with [[color cycling]]]]

The '''diamond-square algorithm''' is a method for generating [[heightmap]]s 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 [[Alain Fournier (academic)|Fournier]], [[Don Fussell|Fussell]] and [[Loren Carpenter|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{Cite journal |last1=Fournier |first1=Alain |last2=Fussell |first2=Don |last3=Carpenter |first3=Loren |date=June 1982 |title=Computer rendering of stochastic models |journal=Communications of the ACM |volume=25 |issue=6 |pages=371–384 |doi=10.1145/358523.358553 |issn=0001-0782|doi-access=free }}</ref>

The diamond-square algorithm starts with a two-dimensional grid, then [[terrain generation|randomly generates terrain height]] from four seed values arranged in a grid of points so that the entire plane is covered in squares.

==Description==
The diamond-square algorithm begins with a two-dimensional square array of width and height 2<sup>n</sup> + 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<sup>−h</sup>, where h is a value between 0.0 and 1.0 (lower values produce rougher terrain).<ref>{{Cite web |date=2006-04-20 |title=Generating Random Fractal Terrain |url=http://www.gameprogrammer.com/fractal.html#diamond |access-date=2022-12-13 |archive-url=https://web.archive.org/web/20060420054134/http://www.gameprogrammer.com/fractal.html#diamond |archive-date=2006-04-20 }}</ref>

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.

[[File:Diamond Square.svg|800px|Visualization of the Diamond Square Algorithm]]

==Applications==

This [[algorithm]] can be used to generate realistic-looking [[Fractal landscape|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==

The diamond-square algorithm was analyzed by [[Gavin S. P. Miller]] in SIGGRAPH 1986<ref name=miller>{{cite journal|last=Miller|first=Gavin S. P.|title=The definition and rendering of terrain maps|journal=ACM SIGGRAPH Computer Graphics|date=August 1986|volume=20|issue=4|pages=39–48|doi=10.1145/15886.15890}}</ref> 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.<ref>{{cite journal|last1=Lewis|first1=J. P.|title=Generalized stochastic subdivision|journal=ACM Transactions on Graphics|date=1 July 1987|volume=6|issue=3|pages=167–190|doi=10.1145/35068.35069|citeseerx=10.1.1.21.3719|s2cid=14994949 }}</ref> 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,<ref name=PeitgenSaupe>{{cite book|last1=Peitgen|first1=Heinz-Otto, Dietmar Saupe|title=The Science of Fractal Images|date=1988|publisher=Springer-Verlag|location=New York|isbn=978-0-387-96608-3|url-access=registration|url=https://archive.org/details/scienceoffractal0000unse}}</ref> 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".<ref name=PeitgenSaupe />

==References==
<references />

==External links==
* [https://github.com/mlepage/heightmap Simple open source heightmap module for Lua] using diamond-square algorithm
* [https://web.archive.org/web/20060420054134/http://www.gameprogrammer.com/fractal.html#diamond Generating Random Fractal Terrain: The Diamond-Square Algorithm] from [http://www.gameprogrammer.com/ GameProgrammer.com]
* [http://www.ic.sunysb.edu/Stu/jseyster/plasma/ Plasma Fractal] from Justin Seyster's web page
* [http://www2.vo.lu/homepages/phahn/fractals/plasma.htm Plasma fractals] from Patrick Hahn's home page
* [http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2 Terrain Tutorial] from Lighthouse3d.com
* [http://www.somethinghitme.com/2009/12/06/terrain-generation-with-canvas-and-javascript/ Random Midpoint Displacement with Canvas]
* [http://www.cescg.org/CESCG97/marak/node3.html Random midpoint displacement method]
* [https://github.com/A1essandro/Diamond-And-Square Diamond And Square] algorithm on [https://github.com/ Github] (PHP)
* [http://blog.cleancoder.com/uncle-bob/2017/01/09/DiamondSquare.html An example] of [[Test-driven development|test-driving]] an implementation of the algorithm on [[Robert Cecil Martin|Uncle Bob]]'s [http://blog.cleancoder.com/ Clean Coder blog]
* [https://spbooth.github.io/xmountains/ Xmountains] classic sideways scrolling X11 implementation. [https://spbooth.github.io/xmountains/about_xmountains.html Algorithm details].
* [https://janert.me/blog/2022/the-diamond-square-algorithm-for-terrain-generation/ A Python implementation], short and straightforward. Handles both fixed and periodic boundary conditions.

[[Category:Fractals]]
[[Category:Computer graphics algorithms]]
[[Category:Procedural generation]]

Diamond-square algorithm - Revision history

imported>Bearcat: /* top */ dabfix