Perlin Noise

Perlin Noise ist ein Fraktal-Algorithmus welcher mit sehr einfachen Formeln komplexe und theoretisch endlose Gebilde berechnen kann. Da Perlin Noise darauf ausgelegt ist scheinbar zufällige Funktionen, jedoch welche mit weichem Übergang (die Steigung kann einen gewissen Wert nicht überschreiten) eignet er sich sehr gut zur Simulation verschiedenster, natürlicher Phänomene wie beispielsweise:

• Wolken
• Landschaftshöhen- und auch Texturen
• eventuell auch Texturen wie Wasser, Feuer und ähnliches

Grundlagen

Perlin Noise basiert auf der Überlagerung von Frequenzen. Bei einer niedrigen Frequenz wird zwischen 2 eher weit voneinander entfernten angegebenen Werten interpoliert. Bei der höchsten (sinnvollen) Frequenz wird für jeden dargestellten Wert (zB jedes Pixel) ein anderer Wert berechnet. Die Werte werden aus Pseudozufallszahlen für eine Positionsangabe gebildet. Die Positionsangabe kann hier eine beliebige Dimension besitzen (beispielsweise 2D für eine Heightmap, 3D für eine Volumentrische Textur, ...). Die Ausgabe ist üblicherweise 1 Wert welcher beliebig interpretiert werden kann.

Pseudozufallszahlen

Da hier der Standard-Zufallsgenerator (ohne zusätzlichen Code) nicht die gewünchte Funktionalität aufweiset, müssen wir uns hier unseren eigenen Zufallsgenerator kreieren. Ein gängiger Algorithmus sieht beispielsweise so aus:

x := x + Seed;
x := ( x shl 13 ) xor x;
rand := Round(1 - ( (x * (x * x * 15731 + 789221) + 1376312589) and $7fffffff) / 1073741824);

Rand liefert hier einen Wert für eine 1 Dimensionale Positionsangabe (X - Ganzzahl) einen Wert zwischen -1 und 1. Für 2 Dimensionen könnte dieser Code folgendermaßen erweitert werden:

n := x + y * 57 + Seed;
n := ( n shl 13 ) xor n;
rand := Round(1 - ( (n * (n * n * 15731 + 789221) + 1376312589) and $7fffffff) / 1073741824);

im weiteren wird diese Funktionalität mit Random( Pos ) bzw. Random( PosX, PosY ) verwendet.

Frequenzen

Wir besitzen nun eine Funktion

x = Random( Position )

welcher eine Pseudozufallszahl für eine Position zurück gibt. Position soll hierbei eine Ganzzahl in einer beliebigen Dimension sein. Um nun eine beliebige Frequenz wählen zu können, muss einfach die Position entsprechend skaliert werden. Beispielsweise

x = Random( Ganzzahl( Position * 0.01 ) )

würde eine Frequenz von 0.01 liefern. Die Einheit kann hier nach belieben gewählt werden und ist auch vom Verwendungszweck abhängig.

Interpolation

Wir können nun in beliebigen Frequenzen Pseudozufallszahlen bilden. Um jedoch keine abrupten Wechsel von einem Wert auf den anderen zu erhalten müssen diese Werte noch interpoliert werden. Die Interpolationsmethode kann beliebige gewählt werden

Ergebnis  = Interpoliere( Random( Ganzzahl( Position ) ), Random( Ganzzahl( Position ) + 1 ), Nachkommateil( Position ) )

Dies wäre die Interpolation für eine 1 Dimensionale Positionsangabe. Natürlich müssen aber auch die anderen Dimensionen interpoliert werden. Dies kann aber (wenn gewünscht) ebenfalls mit mehreren Interpolationen von 2 Werten erfolgen

PosX = Ganzzahl( Position.x )
PosY = Ganzzahl( Position.y )
X1 = Interpoliere( Random( PosX, PosY ), Random( PosX, PosY + 1 ), Nachkommateil( Position.y ) )
X2 = Interpoliere( Random( PosX + 1, PosY), Random( PosX + 1, PosY + 1, Nachkommateil( Position.y ) )
Ergebnis = Interpoliere( X1, X2, Nachkommateil( Position.x ) )

Für die Interpolation können natürlich alle beliebigen Interpolationsmethoden verwendet werden. Hier noch kurz der einfachste Fall (die lineare Interpolation) welche jedoch für 2D Positionsangaben schon recht brauchbare Ergebnisse liefert:

Interpoliere( Wert1, Wert2, Faktor )
Ergebnis = Wert1 * Faktor + Wert2 * (1 - Faktor);

Algorithmus

Mit den oben beschriebenen Funktionen ist der Algorithmus recht schnell zu machen.

Die Parameter

Der Perlin Noise Algorithmus erhält üblicherweise folgende Parameter:

• Double: Position (Die Position wird bereits entsprechend skaliert)
• Double: Persistenz (wie stark ist der Einfluss der höheren Frequenzen)
• Wertebereich: Double: Min, Double: Max
• Integer: Rechentiefe (Detailgrad)
• Gegebenenfalls Double: Frequenzfaktor (oder Standard auf 2)

Die Laufzeit für einen berechneten Wert beträgt O( n ) wobei n die Rechentiefe angibt.

Überlagerung der Frequenzen

Es wird für jeden Detailgrad ein Wert berechnet. Da Perlin Noise für einen einzelnen Wert kaum Sinn macht und im Normalfall für mehrere nebeneinander liegende Positionen ein Wert berechnet wird, kann man auch von Frequenzbändern sprechen. Der Code könnte beispielsweise so aussehen:

Wert = 0
Für jeden Detailgrad
 Wert = Wert + InterpolierterWert( Position * Frequenz )
 Frequenz = Frequenz * Frequenzfaktor

Wie hier unschwer zu erkennen ist werden die Werte addiert (also überlagert).

Abb.1: Frequenzbänder für 200 Werte (Pixel).
Frequenzfaktor = 2; Persitenz = 0.5;
Links oben: Frequenz 0.01 (Einheit = Pixel)
Rechts oben: Frequenz 0.02
Links unten: Frequenz 0.04
Rechts unten: überlagerte (addierte) Frequenzbänder (für die ersten 3 Detailgrade)

Rechentiefe

Die Rechentiefe gibt an wie hoch der Detailgrad sein soll. In Abbildung 1 (siehe Frequenzen) wurde beispielsweise eine Rechentiefe von 3 verwendet. Bei einem 2 Dimensionalen Perlin Noise dürfte dies jedoch deutlichere Unterschiede zeigen (siehe Abbildung 2).

Abb. 2: Unterschiedliche Rechentiefen.
Frequenzfaktor = 2; Persitenz = 0.5;
Links oben: Rechentiefe 1
Rechts oben: Rechentiefe 2
Links unten: Rechentiefe 3
Rechts unten: Rechentiefe 4

Persistenz

Die Persistenz gibt an wie stark die höheren Frequenzbänder Einfluss auf das Ergebnis haben sollen. Hierfür erweitern wir den unter Überlagerung der Frequenzen angegebenen Code:

Wert = 0
Faktor = 1
Für Detailgrad = 1 bis Rechentiefe
 Wert = Wert + InterpolierterWert( Position * Frequenz ) * Faktor
 Frequenz = Frequenz * Frequenzfaktor
 Faktor = Faktor * Persistenz

Abb. 3: Unterschiedliche Persitenzen.
Frequenzfaktor = 2; Rechentiefe = 5
Links oben: Persitenz 0.2
Rechts oben: Persitenz 0.4
Links unten: Persitenz 0.6
Rechts unten: Persitenz 0.8

Der Wertebereich

Bisher wurden zwar in den Bildern die Werte korrekt dargestellt, jedoch wurde noch nicht erklärt wie man zu diesen Werten kommt. Wir möchten nun den Code welcher unter Persitenz angegeben wurde so modifizieren, das er Werte für den Wertebereich [Min|Max] liefert. Betrachten wir vorerst was wir alles verwenden:

• InterpolierterWert( Position * Frequenz ): liefert einen Wert im Bereich [-1|1]
• Faktor: zu Beginn 1, wird bei jeden Durchlauf mit Persitenz multipliziert
• Frequenz und Frequenzfaktor: spielen für die Amplitude keine Rolle

Der gesamtfaktor lässt sich recht einfach berechnen:

Faktor = 1
GesFaktor = 0
Für Deteilgrad = 1 bis Rechentiefe
 GesFaktor = GesFaktor + Faktor
 Faktor = Faktor * Persistenz

Mit dem errechneten Gesamtfaktor wissen wir nun, das die Funktion einen Wert im Bereich

[-GesFaktor|+GesFaktor] liefert. Nun brauchen wir nur noch die Amplitude skalieren und einen entsprechenden Offset für das Minimum addieren. Dies sieht im Endeffekt so aus:

Initialisierung:

Bereich = Max - Min;   
Offset = Min + Bereich * 0.5;
GesFaktor = 0;
Faktor = 2;

für 1 bis Rechentiefe
  GesFaktor += Faktor
  Faktor = Faktor * Persistenz

Tiefe_1_Amplitude =   Bereich / GesFaktor

Berechnung eines Wertes:

Wert = 0
Faktor = Tiefe_1_Amplitude
Frequenz = 1
Für Detailgrad = 1 bis Rechentiefe
  Wert = Wert + InterpolierterWert( Position * Frequenz ) * Faktor
  Frequenz = Frequenz * Frequenzfaktor
  Faktor = Faktor * Persitenz

Wert = Wert + Offset