Square-square Algorithmus

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

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

$SD=k\cdot 2^{-i\cdot H}$

addiert, wobei $k$ der Skalierungsfaktor des Höhenfeldes ist $i$ die Iteration und $H$ 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 $9$ gewichtet, der am entferntesten liegende wird mit $1$ gewichtet, die übrigen mit $3$ (siehe Bild). Auf den interpolierten Vertex wird ein Zufallswert entsprechend der obigen Formel addiert. Für den unten dargestellten Vertex ergibt sich der Wert

$h_{0,0}^{2}={\frac {9\cdot h_{0,0}^{1}+3\cdot h_{0,1}^{1}+3\cdot h_{1,0}^{1}+h_{1,1}^{1}}{9+3+3+1}}+rand(0,k\cdot 2^{-2\cdot H})$

Hierbei steht $h_{x,y}^{i}$ für den Höhenwert des Gitters des $i$ -ten Iteration bei dem Vertex an der Position $(x,y)$ im Gitter. $rand(M,SD)$ ist ein Pseudocode für eine Zufallsfunktion mit dem Mittelwert $M$ und der Standardabweichung $SD$

Gitter der zweiten Iteration

Gewichte für die Interpolation

Beispielimplementierung

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

Kritik

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

↑ ^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
↑ 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
↑ 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

[miller1986definition-1] Gavin S. P. Miller: The definition and rendering of terrain maps In: ACM SIGGRAPH Computer Graphics, Band 20, Nr. 4, 1986, S. 39–48

[fournier1982computer-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

[1]

[2]

[3]