Diamond-square Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Diamond-square Algorithmus ist ein Verfahren, das in der Computergrafik eingesetzt wird, um Höhenfelder zu erzeugen. Er stellt eine 2-dimensionale Verallgemeinerung der Mittelpunktverschiebung dar. Der Algorithmus wurde erstmals 1982 von Fournier, Fussell und Carpenter auf der SIGGRAPH 1982 vorgestellt[1]. Der Name geht zurück auf Gavin S. P. Miller[2].

Grundidee[Bearbeiten | Quelltext bearbeiten]

Ausgangspunkt für die Generierung einer fraktalen Landschaft auf Basis des Diamond-square Algorithmus ist ein Quadrat. Jeder Ecke des Quadrats wird ein Höhenwert zugeordnet. Der Algorithmus zerlegt das Quadrat rekursiv in kleinere Quadrate, wobei der Höhenwert des Mittelpunkts als Mittelwert der vier Eckpunkte, plus einer zufälligen Verschiebung, definiert wird. Analog wird der Höhenwert der Seitenhalbierenden eines Quadrats als Mittelwert der vier horizontal umgebenden Punkte, plus einer zufälligen Verschiebung, definiert. Die Verschiebung ist Normalverteilt mit einem Mittelwert von 0 und nimmt mit der Größe der Rechtecke ab. Die Mittelpunkte und Seitenhalbierende bilden die Eckpunkte der neuen Rechtecke. Ausnahme von der Regel zur Generierung der neuen Punkte bilden die vier Außenseiten des ursprünglichen Rechtecks, die jeweils nach der eindimensionalen Mittelpunktverschiebung generiert werden[1].

Mögliche Implementation in unterschiedlichen Dimensionen[Bearbeiten | Quelltext bearbeiten]

Es ist möglich, den Algorithmus in verschiedene Dimensionen zu übertragen und somit unterschiedliche Resultate zu erzielen. Hierbei wird eine n-dimensionale Einheit, mit Tiefe versehen. Das heißt, dass für jede berechnete n-dimensionale Koordinate ein Wert, meist von 0 bis 1, vorhanden ist. Die optische Darstellung kann man entweder mit einer Verschiebung in der nächsten Dimensionsachse oder eine Farbe bzw. Transparenz realisieren. Hierbei ist die zweidimensionale Implementation namensgebend.

Beispiele

Bei einer dreidimensionalen Implementation kann man sich zum Beispiel eine Karte für die Dichte von Nebel vorstellen. Hierbei werden unterschiedliche Areale unterschiedlich viel Licht absorbieren.

Kritik[Bearbeiten | Quelltext bearbeiten]

Gavin S. P. Miller hat den Diamond-square Algorithmus kritisiert, da er, im Gegensatz zu dem von ihm vorgestellten Square-square Algorithmus, zu auffälligen Artefakten in der generierten Landschaft führt[2].

Fraktale Landschaften im Allgemeinen stehen in der Kritik, da sie zwar eine gute Approximation für Bergzüge liefern, die Landschaften jedoch – stellt man sie auf den Kopf – statistisch identisch sind[3]. In der Realität lagern sich jedoch beispielsweise Sedimente in Talsenken ab, wodurch diese abflachen. Unter anderem haben Musgrave, Kolb und Mace unter Berücksichtigung von Erosionseffekten eine Weiterentwicklung fraktaler Landschaften entwickelt, die in der Lage ist, Landschaften zu erzeugen, die wesentlich realitätsnäher sind.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b A. Fournier,D. Fussell und L. Carpenter: Computer rendering of stochastic models In: Communications of the ACM, Band 25, Nr. 6, 1982, S. 371–384
  2. a b Gavin S. P. Miller: The definition and rendering of terrain maps In: ACM SIGGRAPH Computer Graphics, Band 20, Nr. 4, 1986, S. 39–48
  3. F.K. Musgrave, C.E. Kolb und R.S. Mace: The synthesis and rendering of eroded fractal terrains In: ACM SIGGRAPH Computer Graphics, Band 23, Nr. 3, 1989, S. 41–50