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
Inhaltsverzeichnis
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 Heighmap, 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 * Persitenz
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