The diamond-square algorithm is a method for generating highly realistic heightmap

Heightmap

In computer graphics, a heightmap or heightfield is a raster image used to store values, such as surface elevation data, for display in 3D computer graphics...

s for computer graphics

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

. 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

Plasma effect

The plasma effect is a computer-based visual effect animated in real-time. It uses cycles of changing colours warped in various ways to give an illusion of liquid, organic movement....

 produced when applied.

The idea was first introduced by Fournier

Alain Fournier

Alain Fournier was a computer graphics researcher.- Biography :Alain Fournier was born on November 5, 1943 in Lyon, France. He was married twice, first to Beverly Bickle and later to Adrienne Drobnies, with whom he had one daughter, Ariel.Fournier's early training was in chemistry, culminating in...

, Fussell and Carpenter

Loren Carpenter

Loren C. Carpenter is a computer graphics researcher and developer. He is co-founder and chief scientist of Pixar Animation Studios. He is the co-inventor of the Reyes rendering algorithm and is one of the authors of the PhotoRealistic RenderMan software which implements Reyes and which renders...

 at SIGGRAPH

SIGGRAPH

SIGGRAPH is the name of the annual conference on computer graphics convened by the ACM SIGGRAPH organization. The first SIGGRAPH conference was in 1974. The conference is attended by tens of thousands of computer professionals...

 1982. It was later analyzed by Gavin S. P. Miller in SIGGRAPH 1986 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.

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 proportional 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.

Diamond-square algorithm

The difference from the above algorithm is an intermediate step that regards diamond-shaped squares as well.
This reduces the squared-shaped artifacts in the landscape, since the diamonds are rotated 45 degrees relative to the squares.

Applications

This algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 can be used to generate realistic-looking landscapes

Fractal landscape

A fractal landscape is a surface generated using a stochastic algorithm designed to produce fractal behaviour that mimics the appearance of natural terrain...

, and different implementations are used in computer graphics software such as Terragen

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:...

.

External links

• Simple open source heightmap module for Lua using diamond-square algorithm
• Generating Random Fractal Terrain: The Diamond-Square Algorithm from GameProgrammer.com
• Implementing a plasma fractal in C#
• 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 with Canvas
• Random midpoint displacement method