Diamond-square Algorithmus

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. Der Name geht zurück auf Gavin S. P. Miller.

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

Für den Diamond-square Algorithmus kommt ein 3x3-Raster, ein 5x5-Raster, ein 9x9-Raster, ein 17x17-Raster oder allgemein ein quadratisches Raster infrage, wo die Breite und Höhe gleich $2^{n}+1$ mit einer positiven ganzen Zahl $n$ 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 $4^{2}=16$ kleinere Quadrate mit gleicher Seitenlänge. Wenn die Prozedur $k$-mal ausgeführt wird, entstehen aus jedem Quadrat $4^{k}$ kleinere Quadrate mit gleicher Seitenlänge.

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

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# zeigt die Implementierung des Diamond-square Algorithmus. Das Höhenfeld wird als zweidimensionales Hintergrundbild des Hauptfensters dargestellt. Die berechneten Werte entsprechen den Farbwerten der Pixel einer Bitmap.

Code-Schnipsel

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 } } } } }

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.

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

Weblinks

• Async Drink: Generating landscapes with the Diamond Square algorithm
• Robert C. Martin, The Clean Code Blog TDD Lesson - Terrain Generation
• Diamond-square Implementierung in C#
• Diamond-square Implementierung in PHP
• Fractal terrain generator: Xmountains