Der Square-square Algorithmus wurde von Gavin S. P. Miller auf der Siggraph 1986 als Verbesserung der Generierung von Höhenfeldern in der Computergrafik vorgestellt[1]. Insbesondere nimmt er dabei Bezug auf den Diamond-square Algorithmus von Fournier, Fussell und Carpenter [2], der unter bestimmten Bedingungen Artefakte erzeugen kann, die mit dem Square-square Algorithmus nicht vorkommen (siehe S. 45 f. in [1]).

Funktionsweise

Bearbeiten

Das Höhenfeld ist ein Raster von Vertizes, die jeweils einen Höhenwert besitzen, welcher sich aus dem Höhenfeld der vorhergehenden Iteration berechnet (siehe unten). Auf diese Vertizes wird jeweils ein zufallsgenerierter Wert mit der Standardabweichung

 

addiert, wobei   der Skalierungsfaktor des Höhenfeldes ist   die Iteration und   die Dimension des Fraktals.

Der Algorithmus beginnt in der ersten Iteration mit einem Raster von 3 × 3 Vertizes und addiert auf diese Vertizes die zufallsgenerierten Höhenwerte nach o. g. Formel.

 
Gitter für die erste Iteration


Mit jeder weiteren Iteration wird ein neues Gitter mit den halben Abständen zwischen den Vertizes gebildet, so dass innerhalb jedes Rechtecks des vorherigen Gitters ein Rechteck der halben Größe liegt.

Die Vertizes dieses neuen Rechtecks werden wie folgt über die umliegenden Vertizes interpoliert: Der nächstliegende Vertex wird mit   gewichtet, der am entferntesten liegende wird mit   gewichtet, die übrigen mit   (siehe Bild). Auf den interpolierten Vertex wird ein Zufallswert entsprechend der obigen Formel addiert. Für den unten dargestellten Vertex ergibt sich der Wert

 

Hierbei steht   für den Höhenwert des Gitters des  -ten Iteration bei dem Vertex an der Position   im Gitter.   ist ein Pseudocode für eine Zufallsfunktion mit dem Mittelwert   und der Standardabweichung  

 
Gitter der zweiten Iteration
 
Gewichte für die Interpolation

Beispielimplementierung

Bearbeiten

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung des Square-square Algorithmus.

Implementierung  
namespace SquareSquareExample;

public class SquareSquareGenerator
{
    private readonly int _iterations;
    private readonly double _k;
    private readonly double _h;

    public SquareSquareGenerator(int iterations, double k, double h)
    {
        _iterations = iterations;
        _k = k;
        _h = h;
    }

    public double[,] Generate()
    {
        var initialLattice = GetInitialLattice();

        double[,] currentLattice = initialLattice;

        for (int iteration = 2; iteration <= _iterations; iteration++)
        {
            var nextLattice = CreateInterpolatedLattice(currentLattice);
            AddRandomNumbers(nextLattice, iteration);
            currentLattice = nextLattice;
        }

        return currentLattice;
    }

    private double[,] GetInitialLattice()
    {
        double[,] initialLattice = new double[3, 3];
        AddRandomNumbers(initialLattice, iteration: 1);
        return initialLattice;
    }

    private void AddRandomNumbers(double[,] lattice, int iteration)
    {
        for (int i = 0; i < lattice.GetLength(0); i++)
        {
            for (int j = 0; j < lattice.GetLength(1); j++)
            {
                lattice[i, j] += CreateRandomNumber(0, GetStandardDeviation(iteration));
            }
        }
    }

    /// <summary>
    /// Create a normal distributed random number with the Box-Muller method.
    /// </summary>
    private double CreateRandomNumber(double mean, double standardDeviation)
    {
        double u1 = 1.0-Random.Shared.NextDouble(); 
        double u2 = 1.0-Random.Shared.NextDouble();
        double standardNormalRandomNumber = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Sin(2.0 * Math.PI * u2);
        return mean + standardDeviation * standardNormalRandomNumber; 
    }

    private double GetStandardDeviation(int iteration)
    {
        return _k * Math.Pow(2, -iteration * _h);
    }

    private double[,] CreateInterpolatedLattice(double[,] currentLattice)
    {
        int nextLatticeSize = (currentLattice.GetLength(0) - 1) * 2;
        double[,] nextLattice = new double[nextLatticeSize, nextLatticeSize];

        for (int i = 0; i < nextLatticeSize; i++)
        {
            for (int j = 0; j < nextLatticeSize; j++)
            {
                var weights = GetWeights(i, j);

                var upperLeft = (X: i / 2, Y: j / 2);
                var upperRight = (X: i / 2 + 1, Y: j / 2);
                var lowerLeft = (X: i / 2, Y: j / 2 + 1);
                var lowerRight = (X: i / 2 + 1, Y: j / 2 + 1);

                nextLattice[i, j] = (currentLattice[upperLeft.X, upperLeft.Y] * weights.UpperLeft 
                                     + currentLattice[upperRight.X, upperRight.Y] * weights.UpperRight 
                                     + currentLattice[lowerLeft.X, lowerLeft.Y] * weights.LowerLeft
                                     + currentLattice[lowerRight.X, lowerRight.Y] * weights.LowerRight) / 16.0;
            }
        }

        return nextLattice;
    }

    private (double UpperLeft, double UpperRight, double LowerLeft, double LowerRight) GetWeights(int i, int j)
    {
        return (i % 2, j % 2) switch
        {
            (0, 0) => ( 9, 3, 3, 1 ),
            (0, 1) => ( 3, 1, 9, 3 ),
            (1, 0) => ( 3, 9, 1, 3 ),
            (1, 1) => ( 1, 3, 3, 9 ),
            _ => throw new Exception()
        };
    }
}
Beispielausgabe
Ausgabe des Square-square Algorithmus mit 11 Iterationen, k=.7 und H=.6
Ausgabe des Square-square Algorithmus mit 11 Iterationen, k=1.7 und H=1

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