The diamond-square algorithm is a method for generating
heightmap
In computer graphics, a heightmap or heightfield is a raster image used mainly as Discrete Global Grid in secondary elevation modeling. Each pixel stores values, such as surface elevation data, for display in 3D computer graphics. A heigh ...
s for
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
. 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 in 1982.
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.
Description
The diamond-square algorithm begins with a two-dimensional square array of width and height 2
n + 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.
At each iteration, the magnitude of the random value should be multiplied by 2
−h, where h is a value between 0.0 and 0.1 (lower values produce rougher terrain).
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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
can be used to generate realistic-looking
landscapes
A landscape is the visible features of an area of land, its landforms, and how they integrate with natural or man-made features, often considered in terms of their aesthetic appeal.''New Oxford American Dictionary''. A landscape includes the p ...
, and different implementations are used in computer graphics software such as
Terragen
Terragen is a scenery generator program for Microsoft Windows and Mac OS X developed and published by Planetside Software. It can be used to create renderings and animations of landscapes.
History
Released in stages (tech preview and be ...
. 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
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.
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,
[{{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] although the possibility of adaptive refinement is lost. The diamond-square algorithm and its refinements are reviewed in the book.
References
External links
Simple open source heightmap module for Luausing diamond-square algorithm
from
ttp://www.gameprogrammer.com/ GameProgrammer.comPlasma Fractalfrom Justin Seyster's web page
from Patrick Hahn's home page
Terrain Tutorialfrom Lighthouse3d.com
Random Midpoint Displacement with CanvasDiamond And Squarealgorithm o
Github(PHP)
of
test-driving an implementation of the algorithm on
Uncle Bob'
Clean Coder blogXmountainsclassic sideways scrolling X11 implementation
A Python implementation short and straightforward. Handles both fixed and periodic boundary conditions.
Fractals
Computer graphics algorithms
Procedural generation