Diamond-square algorithm

from Wikipedia, the free encyclopedia

The diamond-square algorithm is a method in computer graphics , is used to height fields to be generated. It represents a 2-dimensional generalization of the center shift. The algorithm was first presented in 1982 by Fournier, Fussell and Carpenter at the SIGGRAPH 1982. The name goes back to Gavin SP Miller.

Basic idea

The starting point for generating a fractal landscape based on the Diamond-square algorithm is a square. A height value is assigned to each corner of the square. The algorithm recursively breaks the square down into smaller squares, with the height value of the center point being defined as the mean value of the four corner points plus a random displacement. Similarly, the height value of the bisector of a square is defined as the mean value of the four horizontally surrounding points plus a random shift. The shift is normally distributed with a mean value of 0 and decreases with the size of the rectangles. The center points and side bisectors form the corner points of the new rectangles. Exceptions to the rule for generating the new points are the four outer sides of the original rectangle, which are each generated after the one-dimensional center shift.

Possible implementation in different dimensions

It is possible to transfer the algorithm into different dimensions and thus achieve different results. Here, an n-dimensional unit is provided with depth. This means that for every calculated n-dimensional coordinate there is a value, usually from 0 to 1. The visual representation can be realized either with a shift in the next dimension axis or a color or transparency. Here, the two-dimensional implementation is named.

Examples

For example, in a three-dimensional implementation, imagine a map of the density of fog. Different areas will absorb different amounts of light.

criticism

Gavin SP Miller has criticized the diamond-square algorithm because, in contrast to the square-square algorithm presented by him , it leads to conspicuous artifacts in the generated landscape.

Fractal landscapes in general have been criticized because, although they provide a good approximation for mountain ranges, the landscapes - if you turn them upside down - are statistically identical . In reality, however, sediments, for example, are deposited in valley depressions, causing them to flatten. Among other things, Musgrave, Kolb and Mace have developed a further development of fractal landscapes, taking into account the effects of erosion , which is able to create landscapes that are much closer to reality.

Individual evidence

  1. ↑ a b A. Fournier, D. Fussell and L. Carpenter: Computer rendering of stochastic models In: Communications of the ACM, Volume 25, No. 6, 1982, pp. 371-384
  2. ↑ a b Gavin SP Miller: The definition and rendering of terrain maps In: ACM SIGGRAPH Computer Graphics, Vol. 20, No. 4, 1986, pp. 39-48
  3. ↑ FK Musgrave, CE Kolb and RS Mace: The synthesis and rendering of eroded fractal terrains In: ACM SIGGRAPH Computer Graphics, Vol. 23, No. 3, 1989, pp. 41-50