Diamond-square algorithm - Revision history

Bearcat: /* top */ dabfix

2025-04-13T18:16:52Z

top: dabfix

← Previous revision		Revision as of 18:16, 13 April 2025
Line 5:		Line 5:
	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 '''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\|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 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.		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.

Tamfang: /* Description */ an attempt to deflect likely misunderstandings

2023-10-20T15:06:58Z

Description: an attempt to deflect likely misunderstandings

← Previous revision		Revision as of 15:06, 20 October 2023
Line 16:		Line 16:
	* '''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.		* '''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<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>		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.		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.

ZippeyKeys12: Typo, 0.1 -> 1.0

2023-06-23T18:09:10Z

Typo, 0.1 -> 1.0

← Previous revision		Revision as of 18:09, 23 June 2023
Line 16:		Line 16:
	* '''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.		* '''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<sup>−h</sup>, where h is a value between 0.0 and 0.1 (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>		At each iteration, the magnitude of the random value should be multiplied by 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.		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.

Citation bot: Alter: url. URLs might have been anonymized. Add: s2cid, archive-date, archive-url, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Josve05a | Linked from User:Josve05a/cite/wayback | #UCB_webform_linked 258/1365

2023-06-18T20:52:14Z

Alter: url. URLs might have been anonymized. Add: s2cid, archive-date, archive-url, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Josve05a | Linked from User:Josve05a/cite/wayback | #UCB_webform_linked 258/1365

← Previous revision		Revision as of 20:52, 18 June 2023
Line 5:		Line 5:
	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 '''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\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{Cite journal \|~~last~~=Fournier \|~~first~~=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=June 1982 \|title=Computer rendering of stochastic models ~~\|url=http://dx.doi.org/10.1145/358523.358553~~ \|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 idea was first introduced by [[Alain Fournier\|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.		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.
Line 16:		Line 16:
	* '''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.		* '''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<sup>−h</sup>, where h is a value between 0.0 and 0.1 (lower values produce rougher terrain).<ref>{{Cite web \|date=2006-04-20 \|title=Generating Random Fractal Terrain \|url=https://web.archive.org/web/20060420054134/http://www.gameprogrammer.com/fractal.html#diamond \|~~access~~-date=~~2022~~-12-13 ~~\|website=web.archive.org~~}}</ref>		At each iteration, the magnitude of the random value should be multiplied by 2<sup>−h</sup>, where h is a value between 0.0 and 0.1 (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.		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.
Line 31:		Line 31:
	==Artifacts and extensions==		==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}}<!--\|accessdate=3 November 2011--></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}}</ref> In this variant the weights on the neighboring points are obtained by solving		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}}<!--\|accessdate=3 November 2011--></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.		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 />		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 />

Selinger: Citations: eliminated duplicate, better citation of book.

2023-05-23T00:48:59Z

Citations: eliminated duplicate, better citation of book.

← Previous revision		Revision as of 00:48, 23 May 2023
Line 5:		Line 5:
	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 '''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\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{cite journal\|last=Fournier\|first=Alain\|last2=Fussell\|first2=Don\|last3=Carpenter\|first3=Loren\|title=Computer rendering of stochastic models\|journal=Communications of the ACM\|date=June 1982\|volume=25\|issue=6\|pages=371–384\|doi=10.1145/358523.358553\|doi-access=free}}<!--\|accessdate=3 November 2011--></ref><ref>{{Cite journal \|last=Fournier \|first=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=June 1982 \|title=Computer rendering of stochastic models \|url=http://dx.doi.org/10.1145/358523.358553 \|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 idea was first introduced by [[Alain Fournier\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{Cite journal \|last=Fournier \|first=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=June 1982 \|title=Computer rendering of stochastic models \|url=http://dx.doi.org/10.1145/358523.358553 \|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.		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.
Line 33:		Line 33:
	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}}<!--\|accessdate=3 November 2011--></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}}</ref> In this variant the weights on the neighboring points are obtained by solving		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}}<!--\|accessdate=3 November 2011--></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}}</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.		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 ~~the~~ book.<ref name=PeitgenSaupe />		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==

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-29T21:43:23Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 21:43, 29 January 2023
Line 5:		Line 5:
	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 '''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\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{cite journal\|last=Fournier\|first=Alain\|last2=Fussell\|first2=Don\|last3=Carpenter\|first3=Loren\|title=Computer rendering of stochastic models\|journal=Communications of the ACM\|date=June 1982\|volume=25\|issue=6\|pages=371–384\|doi=10.1145/358523.358553}}<!--\|accessdate=3 November 2011--></ref><ref>{{Cite journal \|last=Fournier \|first=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=June 1982 \|title=Computer rendering of stochastic models \|url=http://dx.doi.org/10.1145/358523.358553 \|journal=Communications of the ACM \|volume=25 \|issue=6 \|pages=371–384 \|doi=10.1145/358523.358553 \|issn=0001-0782}}</ref>		The idea was first introduced by [[Alain Fournier\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{cite journal\|last=Fournier\|first=Alain\|last2=Fussell\|first2=Don\|last3=Carpenter\|first3=Loren\|title=Computer rendering of stochastic models\|journal=Communications of the ACM\|date=June 1982\|volume=25\|issue=6\|pages=371–384\|doi=10.1145/358523.358553\|doi-access=free}}<!--\|accessdate=3 November 2011--></ref><ref>{{Cite journal \|last=Fournier \|first=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=June 1982 \|title=Computer rendering of stochastic models \|url=http://dx.doi.org/10.1145/358523.358553 \|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.		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.

Trav Kint: /* Description */

2022-12-13T11:38:28Z

Description

← Previous revision		Revision as of 11:38, 13 December 2022
Line 16:		Line 16:
	* '''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.		* '''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<sup>−h</sup>, where h is a value between 0.0 and 0.1 (lower values produce rougher terrain).		At each iteration, the magnitude of the random value should be multiplied by 2<sup>−h</sup>, where h is a value between 0.0 and 0.1 (lower values produce rougher terrain).<ref>{{Cite web \|date=2006-04-20 \|title=Generating Random Fractal Terrain \|url=https://web.archive.org/web/20060420054134/http://www.gameprogrammer.com/fractal.html#diamond \|access-date=2022-12-13 \|website=web.archive.org}}</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.		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==		==Visualization==

Keith D: /* top */Fix cite date error

2022-12-09T12:32:32Z

top: Fix cite date error

← Previous revision		Revision as of 12:32, 9 December 2022
Line 5:		Line 5:
	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 '''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\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{cite journal\|last=Fournier\|first=Alain\|last2=Fussell\|first2=Don\|last3=Carpenter\|first3=Loren\|title=Computer rendering of stochastic models\|journal=Communications of the ACM\|date=June 1982\|volume=25\|issue=6\|pages=371–384\|doi=10.1145/358523.358553}}<!--\|accessdate=3 November 2011--></ref><ref>{{Cite journal \|last=Fournier \|first=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=1982~~-06~~ \|title=Computer rendering of stochastic models \|url=http://dx.doi.org/10.1145/358523.358553 \|journal=Communications of the ACM \|volume=25 \|issue=6 \|pages=371–384 \|doi=10.1145/358523.358553 \|issn=0001-0782}}</ref>		The idea was first introduced by [[Alain Fournier\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{cite journal\|last=Fournier\|first=Alain\|last2=Fussell\|first2=Don\|last3=Carpenter\|first3=Loren\|title=Computer rendering of stochastic models\|journal=Communications of the ACM\|date=June 1982\|volume=25\|issue=6\|pages=371–384\|doi=10.1145/358523.358553}}<!--\|accessdate=3 November 2011--></ref><ref>{{Cite journal \|last=Fournier \|first=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=June 1982 \|title=Computer rendering of stochastic models \|url=http://dx.doi.org/10.1145/358523.358553 \|journal=Communications of the ACM \|volume=25 \|issue=6 \|pages=371–384 \|doi=10.1145/358523.358553 \|issn=0001-0782}}</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.		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.

Trav Kint at 10:19, 9 December 2022

2022-12-09T10:19:15Z

← Previous revision		Revision as of 10:19, 9 December 2022
Line 3:		Line 3:
	[[File:-PLASMA-ColorCycling.Gif\|200px\|thumb\|right\|Animated plasma fractal with [[color cycling]]]]		[[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 '''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\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] 1982.<ref name=fournier>{{cite journal\|last=Fournier\|first=Alain\|last2=Fussell\|first2=Don\|last3=Carpenter\|first3=Loren\|title=Computer rendering of stochastic models\|journal=Communications of the ACM\|date=June 1982\|volume=25\|issue=6\|pages=371–384\|doi=10.1145/358523.358553}}<!--\|accessdate=3 November 2011--></ref>		The idea was first introduced by [[Alain Fournier\|Fournier]], [[Don Fussell\|Fussell]] and [[Loren Carpenter\|Carpenter]] at [[SIGGRAPH]] in 1982.<ref name=fournier>{{cite journal\|last=Fournier\|first=Alain\|last2=Fussell\|first2=Don\|last3=Carpenter\|first3=Loren\|title=Computer rendering of stochastic models\|journal=Communications of the ACM\|date=June 1982\|volume=25\|issue=6\|pages=371–384\|doi=10.1145/358523.358553}}<!--\|accessdate=3 November 2011--></ref><ref>{{Cite journal \|last=Fournier \|first=Alain \|last2=Fussell \|first2=Don \|last3=Carpenter \|first3=Loren \|date=1982-06 \|title=Computer rendering of stochastic models \|url=http://dx.doi.org/10.1145/358523.358553 \|journal=Communications of the ACM \|volume=25 \|issue=6 \|pages=371–384 \|doi=10.1145/358523.358553 \|issn=0001-0782}}</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.		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==		==Description==

Pjanert: /* External links */

2022-06-14T00:59:13Z

External links

← Previous revision		Revision as of 00:59, 14 June 2022
Line 49:		Line 49:
	* [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]		* [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://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:Fractals]]