2001:16B8:8144:3B00:D172:9519:9BFA:4C11: Typo.

2024-06-17T03:39:22Z

Typo.

Neue Seite

Der '''Diamond-square Algorithmus''' ist ein Verfahren, das in der [[Computergrafik]] eingesetzt wird, um [[Höhenfeld]]er zu erzeugen. Er stellt eine [[zweidimensional|2-dimensionale]] Verallgemeinerung der [[Mittelpunktverschiebung]] dar. Der Algorithmus wurde erstmals 1982 von [[Alain Fournier (Informatiker)|Fournier]], Fussell und Carpenter auf der [[SIGGRAPH]] 1982 vorgestellt<ref name="fournier1982computer">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</ref>. Der Name geht zurück auf Gavin S. P. Miller<ref name="miller1986definition">Gavin S. P. Miller: ''The definition and rendering of terrain maps'' In: ACM SIGGRAPH Computer Graphics, Band 20, Nr. 4, 1986, S. 39–48</ref>.

== Funktionsweise ==
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 [[Seitenhalbierende]]n eines Quadrats als Mittelwert der vier horizontal umgebenden Punkte, plus einer zufälligen Verschiebung, definiert. Die Verschiebung ist [[Normalverteilung|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<ref name="fournier1982computer" />.

Für den Diamond-square Algorithmus kommt ein 3x3-Raster, ein 5x5-Raster, ein 9x9-Raster, ein 17x17-Raster oder allgemein ein [[Quadratisch|quadratisches]] Raster infrage, wo die Breite und Höhe gleich <math>2^n + 1</math> mit einer positiven [[Ganze Zahl|ganzen Zahl]] <math>n</math> ist. Jede [[Iteration]] unterteilt jedes Quadrat in 4 gleich große Quadrate mit halber Seitenlänge und besteht aus 2 Schritten:

* ''Karoschritt'': Für jedes Quadrat des Rasters wird ein zufälliger Wert im Mittelpunkt erzeugt, wo sich die beiden Diagonalen des Quadrats schneiden. Der Wert für den Mittelpunkt wird berechnet, indem der Durchschnitt der Werte der 4 Ecken des Quadrats gebildet und ein zufälliger Betrag addiert wird. Dadurch entstehen Quadrate, die auf der Ecke stehen (''Karos'').
* ''Quadratschritt'': Für jedes quadratische Karo wird ein zufälliger Wert im Mittelpunkt erzeugt, wo sich die beiden Diagonalen des Karos schneiden. Der Wert für den Mittelpunkt wird berechnet, indem der Durchschnitt der Werte der 4 Ecken des Karos gebildet und ein zufälliger Betrag addiert wird, der im gleichen Bereich liegt wie im Karoschritt. Dadurch entstehen wieder Quadrate, die parallel zum Raster sind.

Jede [[Iteration]] unterteilt jedes Quadrat also in 4 gleich große Quadrate mit halber Seitenlänge. Wenn die Prozedur 2-mal ausgeführt wird, entstehen aus jedem Quadrat <math>4^2 = 16</math> kleinere Quadrate mit gleicher Seitenlänge. Wenn die Prozedur <math>k</math>-mal ausgeführt wird, entstehen aus jedem Quadrat <math>4^k</math> kleinere Quadrate mit gleicher Seitenlänge.<ref>Robert C. Pendleton: [https://web.archive.org/web/20060420054134/http://www.gameprogrammer.com/fractal.html#diamond Generating Random Fractal Terrain]</ref>

Folgende Abbildung zeigt die ersten zwei Iterationen des Algorithmus für ein 5x5-Raster:

[[Datei:Diamond Square.svg|rahmenlos|800x800px]]

Dabei werden vier Schritte in der Reihenfolge ''Karoschritt, Quadratschritt, Karoschritt, Quadratschritt'' ausgeführt. Schon vorhandene Punkte sind schwarz, neu erzeugte Punkte sind gelb dargestellt.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung des Diamond-square Algorithmus. Das Höhenfeld wird als [[Zweidimensional|zweidimensionales]] Hintergrundbild des Hauptfensters dargestellt. Die berechneten Werte entsprechen den Farbwerten der [[Pixel]] einer ''Bitmap''.<ref>GitHub: [https://gist.github.com/awilki01/83b65ad852a0ab30192af07cda3d7c0b Diamond-Square Algorithm for Generating Terrain (C#)]</ref>
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Code-Schnipsel'''  
|-
|
<syntaxhighlight lang="c#">
using System;
using System.Drawing;
using System.Windows.Forms;

namespace DiamondSquare
{
public class DiamondSquare
{
// Diese Methode berechnet die Werte mit dem Diamond-square Algorithmus
// Gegen ist die Seitenlänge des Quadrats, der Bereich für die zufälligen Werte und der Wert für die 4 Ecken des Quadrats
public double[,] CalculateValues(int length, double roughness, double seed)
{
// Initialisiert den Wert der 4 Ecken des Quadrats
double[,] values = new double[length, length]; // Initialisiert das zweidimensionale Array für die Werte des quadratischen Rasters
values[0, 0] = seed; // Wert der Ecke links oben
values[0, length - 1] = seed; // Wert der Ecke links unten
values[length - 1, 0] = seed; // Wert der Ecke rechts oben
values[length - 1, length - 1] = seed; // Wert der Ecke rechts unten
Random random = new Random(); // Initialisiert den Zufallsgenerator
// Diese for-Schleife definiert die Iterationsschritte des Algorithmus
// In jedem Iterationsschritt wird die Seitenlänge der Teilquadrate und der Bereich für die zufälligen Werte halbiert, bis die Seitenlänge kleiner als 2 ist
for (int sideLength = length - 1; sideLength >= 2; sideLength /= 2, roughness /= 2.0)
{
int halfLength = sideLength / 2;
// In diesen zwei for-Schleifen werden die Werte für den Karoschritt berechnet
for (int x = 0; x < length - 1; x += sideLength)
{
for (int y = 0; y < length - 1; y += sideLength)
{
// Berechnet den Mittelwert der 4 Ecken des Teilquadrats
double average = (values[x, y] // Wert der Ecke links oben
+ values[x, y + sideLength] // Wert der Ecke links unten
+ values[x + sideLength, y] // Wert der Ecke rechts oben
+ values[x + sideLength, y + sideLength]) / 4.0; // Wert der Ecke rechts unten
average += (2 * roughness * random.NextDouble()) - roughness; // Addiert einen zufälligen Wert im Bereich von -roughness bis +roughness zum Mittelwert
values[x + halfLength, y + halfLength] = average; // Setzt den Wert für den Mittelpunkt des Teilquadrats
}
}
// In diesen zwei for-Schleifen werden die Werte für den Quadratschritt berechnet
for (int x = 0; x < length - 1; x += halfLength)
{
for (int y = (x + halfLength) % sideLength; y < length - 1; y += sideLength)
{
// Berechnet den Mittelwert der 4 Ecken des Karos
double average = (values[(x - halfLength + length) % length, y] // Wert der linken Ecke
+ values[(x + halfLength) % length, y] // Wert der rechten Ecke
+ values[x, (y - halfLength + length) % length] // Wert der oberen Ecke
+ values[x, (y + halfLength) % length]) / 4.0; // Wert der unteren Ecke
average += (2 * roughness * random.NextDouble()) - roughness; // Addiert einen zufälligen Wert im Bereich von -roughness bis +roughness zum Mittelwert
values[x, y] = average; // Setzt den Wert für den Mittelpunkt des Karos
if (x == 0) // Sonderfall für die linke Kante des Quadrats
{
values[length - 1, y] = average; // Setzt den entsprechenden Punkt auf der rechten Kante auf denselben Wert
}
if (y == 0) // Sonderfall für die obere Kante des Quadrats
{
values[x, length - 1] = average; // Setzt den entsprechenden Punkt auf der unteren Kante auf denselben Wert
}
}
}
}
return values;
}
}

// Klasse für das Hauptfenster
public partial class MainForm : Form
{
private Bitmap bitmap;

private int length;
private double[,] values; // Zweidimensionales Array für die Werte des quadratischen Rasters

public MainForm()
{
Random random = new Random(); // Initialisiert den Zufallsgenerator
length = 257; // Seitenlänge des Quadrats, es ist 2^8 + 1 = 257
int roughness = 64; // Bereich für die zufälligen Werte
int seed = 128; // Wert für die 4 Ecken des Quadrats

DiamondSquare diamondSquare = new DiamondSquare(); // Erzeugt ein Objekt der Klasse DiamondSquare
values = diamondSquare.CalculateValues(length, roughness, seed); // Aufruf der Methode, die die Werte für das quadratische Raster berechnet und zurückgibt
bitmap = new Bitmap(length, length); // Erzeugt ein quadratisches Bitmap mit der gegebenen Seitenlänge
BackgroundImage = bitmap; // Setzt die Bitmap als Hintergrundbild des Hauptfensters.

InitializeComponent();
Text = "Diamond-square Algorithmus";
Width = 800;
Height = 800;
Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters.
}

// Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird und setzt die Pixel des Bitmaps
private void OnPaint(object sender, PaintEventArgs e)
{
// Diese for-Schleifen durchlaufen die Pixel des Bitmaps
for (int x = 0; x < length; x++)
{
for (int y = 0; y < length; y++)
{
bitmap.SetPixel(x, y, Color.FromArgb(0, (int) values[x, y], 0)); // Setzt den Farbwert des Pixels
}
}
}
}
}
</syntaxhighlight>
|}

== Mögliche Implementierung in unterschiedlichen Dimensionen ==
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 Implementierung namensgebend.
;Beispiele:
Bei einer dreidimensionalen Implementierung kann man sich zum Beispiel eine Karte für die Dichte von Nebel vorstellen. Hierbei werden unterschiedliche Areale unterschiedlich viel Licht absorbieren.

== Kritik ==
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<ref name="miller1986definition" />.

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<ref>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</ref>. 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 [[Erosion (Geologie)|Erosion]]<nowiki />seffekten eine Weiterentwicklung fraktaler Landschaften entwickelt, die in der Lage ist, Landschaften zu erzeugen, die wesentlich realitätsnäher sind.

== Weblinks ==
* Async Drink: [https://asyncdrink.com/blog/diamond-square-algorithm Generating landscapes with the Diamond Square algorithm]
* Robert C. Martin, The Clean Code Blog [https://blog.cleancoder.com/uncle-bob/2017/01/09/DiamondSquare.html TDD Lesson - Terrain Generation]
* [https://gist.github.com/awilki01/83b65ad852a0ab30192af07cda3d7c0b Diamond-square Implementierung in C#]
* [https://github.com/A1essandro/Diamond-And-Square Diamond-square Implementierung in PHP]
* Fractal terrain generator: [https://spbooth.github.io/xmountains/ Xmountains]

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus (Computergrafik)]]

Diamond-square Algorithmus - Versionsgeschichte

2001:16B8:8144:3B00:D172:9519:9BFA:4C11: Typo.