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

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[1].

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 mit einer positiven ganzen Zahl 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 kleinere Quadrate mit gleicher Seitenlänge. Wenn die Prozedur -mal ausgeführt wird, entstehen aus jedem Quadrat kleinere Quadrate mit gleicher Seitenlänge.[3]

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. Den berechneten Werte entsprechen den Farbwerten der Pixel einer Bitmap.[4]

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

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[5]. 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

Einzelnachweise

  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. Robert C. Pendleton: Generating Random Fractal Terrain
  4. GitHub: Diamond-Square Algorithm for Generating Terrain (C#)
  5. 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

Auf dieser Seite verwendete Medien

Diamond Square.svg
Autor/Urheber: Christopher Ewin, Lizenz: CC BY-SA 4.0
Visualization of the Diamond Square Algorithm