Perlin-Noise

Perlin Noise ist eine Rauschfunktion auf der Basis von pseudozufälligen Gradientenwerten an Gitterpunkten. Diese Textursynthese geht auf Ken Perlin zurück, der sie 1982 für den Film Tron entwickelte, wofür er 1997 einen Oscar erhielt. Perlin Noise wird häufig in der Bildsynthese eingesetzt, um natürliche Phänomene wie Wolken, Landschaftstopologien oder Wasser zu simulieren.

Zweidimensionales Perlin Noise

Fraktales Rauschen durch Überlagern mehrerer Frequenzen

In vielen Open-World-Spielen, z. B. Minecraft oder Minetest, nutzt man Perlin Noise, um das Terrain zu erstellen.

Im einfachen Fall erhält man eine unregelmäßig wellenförmig verlaufende Funktion in beliebig vielen Dimensionen $n\geq 1$, deren Frequenz sich aus dem Abstand der Gitterpunkte ergibt. Perlin Noise kann als fraktale Funktion dargestellt werden, indem man mehrere einfache Rauschfunktionen verschiedener Frequenzen (typischerweise mit dem Faktor 2 zur vorhergehenden) definiert und durch Addition der Funktionswerte überlagert.

Die Größe der zufälligen Variationen, die bei natürlichen Phänomenen vorkommen, hängt vom Maßstab ab, in dem diese Phänomene betrachtet werden. Durch Ändern der Frequenz des Rauschens kann man unterschiedliche Texturen erhalten. Die Eigenschaft, dass sich wiederholende Muster in unterschiedlichen Maßstäben vorkommen, wird als Selbstähnlichkeit bezeichnet und ist für viele Phänomene in Wissenschaft und Natur grundlegend. Perlin Noise kann als eine Art von Zufallsrauschen angesehen werden, das auf verschiedenen Skalen selbstähnlich ist, und ist daher eine Möglichkeit, zufällige fraktale Objekte zu modellieren.

Definition

Perlin Noise ist ein prozedurales Gradientrauschen. Es werden äquidistante Gitterpunkte festgelegt, und für jeden wird ein pseudozufälliger Gradient definiert, dem die Rauschfunktion in der Nähe dieses Gitterpunktes folgt. Diese Gradienten müssen konstant sein, damit die Textur nicht bei jedem Zugriff anders aussieht. Sie können entweder vorab in einem Array gespeichert oder bei jedem Zugriff per Pseudozufallsfunktion aus den ganzzahligen Koordinatenwerten des Gitterpunkts berechnet werden.

Zwischen den Werten, die sich für die nächstgelegenen Gitterpunkte ergeben, wird interpoliert, wodurch man je nach Wahl der Interpolationsfunktion eine einmal oder sogar zweimal stetig differenzierbare Rauschfunktion erhalten kann.

Für fraktales Rauschen überlagert (addiert) man mehrere verschiedene Rauschfunktionen mit verschiedenen Frequenzen (Gitterteilungen). Bei der höchsten Frequenz sollte der Abstand der Gitterpunkte nicht kleiner als der zweifache Pixelabstand sein, da höhere Frequenzen nur noch zu Alias-Effekten führen würden. Je niedriger die Frequenz, desto größer ist der Bereich, über den interpoliert wird, was einen flacheren Gradienten der Rauschfunktion ergibt. Deshalb macht man meist die Amplitude des Rauschens (zumindest ungefähr) proportional zur Gittergröße, d. h. dem Abstand der Gitterpunkte.

Eine Dimension

Um Perlin Noise in einer Dimension zu generieren, ordnet man jedem ganzzahligen Koordinatenwert $i$ einen pseudozufälligen Gradienten $g_{i}$ (eine Steigung) der Funktion zu. In der Umgebung des Punkts $i$, wenn also $x\approx i$, folgt der Rauschfunktionswert näherungsweise der linearen Funktion $f_{i}(x)=(x-i)\cdot g_{i}$

Für einen Punkt $x\in \mathbb {R}$ zwischen zwei ganzzahligen Punkten $i<x<j=i+1$ wird zwischen den Funktionswerten $f_{i}(x)$ und $f_{j}(x)$ interpoliert:

$f(x)=f_{i}(x)h(j-x)+f_{j}(x)(1-h(j-x));\quad i\leq x<j,\;h(0)=0,\,h(1)=1$.

Diese Interpolation ist in der Regel nicht linear mit dem Abstand, weil sonst die Ableitung der Funktion an den ganzzahligen Punkten nicht stetig wäre. Stattdessen wird eine Interpolationsfunktion $h$ verwendet, deren Ableitung an den Punkten 0 und 1, also bei $x=i$ und $x=j$, gleich Null ist. Ursprünglich verwendete Ken Perlin kubisch hermitesche Splines wie etwa $h(x)=3x^{2}-2x^{3}$, aber weil es wünschenswert ist, eine stetige zweite Ableitung zu haben, schlug er später Polynome vom Grad 5 vor. Damit kann auch die zweite Ableitung an den Endpunkten gleich Null gemacht werden, sodass die Rauschfunktion überall eine stetige zweite Ableitung hat.

Zwei Dimensionen

Gitter mit Gradientenvektoren und resultierender Rauschfunktion

Auf die zu texturierende Oberfläche wird ein Quadratgitter gelegt. Jedem Gitterpunkt $q_{i,j}$ ist ein zweidimensionaler, pseudozufälliger, in der Regel normierter Gradientenvektor ${\vec {g}}_{i,j}$ zugeordnet. Nahe einem Gitterpunkt folgt der Funktionswert wie im eindimensionalen Fall einer linearen Funktion (Schiefe Ebene), deren Steigung vom Gradientenvektor gegeben ist, wobei auch hier der Wert am Gitterpunkt Null ist.

Um für einen Punkt $p$ den Wert $f(p)$ der Rauschfunktion zu ermitteln, wird zunächst die Zelle des Quadratgitters bestimmt, in die er fällt. $q_{i,j}$ sei die linke untere Ecke. Für jeden Eckpunkt $q_{m,n}$ dieser Zelle berechnet man das Skalarprodukt des Gradientenvektors mit dem Vektor von $q_{m,n}$ zu $p$:

$s_{m,n}={\vec {g}}_{m,n}\cdot (p-q_{m,n});\quad m=i,i+1,\;n=j,j+1$.

Diese vier Werte werden nun interpoliert mittels einer Überblendfunktion $h$, die von $h(0)=0$ bis $h(1)=1$ ansteigt:

$f_{0}(p)=s_{i,j}\cdot h(1-x)+s_{i+1,j}\cdot h(x)$,

$f_{1}(p)=s_{i,j+1}\cdot h(1-x)+s_{i+1,j+1}\cdot h(x)$,

$f(p)=f_{0}(p)\cdot h(1-y)+f_{1}(p)\cdot h(y)$.

Dabei sind $x$ und $y$ die Koordinaten von $p$ bezüglich des linken unteren Gitterpunkts $q_{i,j}$, normiert auf $x,y\in [0,1]$. In der Regel wird das Gitter zur Vereinfachung der Rechnung normiert und an den Koordinatenachsen ausgerichtet, so dass $q_{i,j}=(i,j)$, und der Punkt, an dem die Rauschfunktion auszuwerten ist, wird vor der Berechnung zu $p$ transformiert (durch multiplizieren seiner Komponenten mit der Frequenz). Dann sind $x$ und $y$ einfach die Komponenten von $p-q_{i,j}$. Allgemeiner gilt:

$x={\frac {(q_{i+1,j}-q_{i,j})\cdot (p-q_{i,j})}{(q_{i+1,j}-q_{i,j})^{2}}},\;y={\frac {(q_{i,j+1}-q_{i,j})\cdot (p-q_{i,j})}{(q_{i,j+1}-q_{i,j})^{2}}}$.

Als Überblendfunktion kann die smoothstep-Funktion $h(x)=x^{2}(3-2x)$ dienen, mit der die erste Ableitung der Rauschfunktion an den Grenzen der Zellen stetig ist. Weil je nach Anwendungsfall der Übergang noch ungleichmäßig aussehen kann, wird oft die Funktion 5. Grades $h(x)=x^{3}(6x^{2}-15x+10)$ verwendet, mit der auch die zweite Ableitung stetig ist, d. h., wenn man die Rauschfunktion $f(p)$ als Fläche über der $x,y$-Ebene darstellt, ändert sich ihre Krümmung nirgends sprunghaft. Für beide gilt $h(1-x)=1-h(x)$, so dass man die Funktion nur zweimal ($n$ mal in $n$ Dimensionen) auswerten muss.

Mehr Dimensionen

Das Verfahren kann auf beliebig viele Dimensionen verallgemeinert werden. In $n$ Dimensionen muss man entsprechend die Skalarprodukte an den $2^{n}$ Ecken eines Hyperwürfels berechnen und interpolieren. Der Rechenaufwand wächst also exponentiell mit der Zahl der Dimensionen. Um dem abzuhelfen, stellte Perlin im Jahr 2001 den Nachfolger Simplex Noise vor, welcher in $n$ Dimensionen nur $n+1$ Gitterpunkte an den Ecken eines Simplex auswertet.

Bestimmung der Gradienten

Um den Gradientenvektor an einem Gitterpunkt zu erhalten, werden zunächst die Koordinaten des Gitterpunkts gehasht. Entweder berechnet man die Komponenten des Gradientenvektors direkt aus dem Hash, oder der Hash dient als Index, um einen Gradientenvektor aus einer vorberechneten Tabelle auszulesen.

Die originale Implementierung von Ken Perlin nutzt als Hashfunktion ein Feld $P$ mit 512 Elementen, das eine Zufallspermutation der Zahlen 0 bis 255 zweimal nacheinander enthält; es ist $P_{i}=P_{i+256}$. Die Koordinaten $i,j,k,\cdots$ des Gitterpunkts werden modulo 256 als Indizes genommen (durch bitweises UND mit der Konstante 255, das schneller ist als eine Division):

$a_{1}=P_{i{\bmod {2}}56}$,

$a_{2}=P_{a_{1}+(j{\bmod {2}}56)}$,

$a_{3}=P_{a_{2}+(k{\bmod {2}}56)}$.

Der Hashwert ist dann $a_{n}$ im $n$-dimensionalen Fall. Statt der Addition kann man auch das bitweise XOR nutzen, dann muss $P$ nur 256 Elemente haben ($a_{2}=P_{a_{1}\oplus (j{\bmod {2}}56)}$), oder die Modulodivision wird erst nach der Addition gemacht ($a_{2}=P_{(a_{1}+j){\bmod {2}}56}$). Man kann außerdem einen Schritt des Hashverfahrens einsparen, indem man bereits mit $a_{2}\oplus (k{\bmod {2}}56)$ (im dreidimensionalen Fall) das Feld mit den Gradientenvektoren indiziert, welches dann entsprechend 256 Vektoren enthält, die zufällig permutiert sind.

Dieses Hashverfahren durch Feldzugriff ergibt allerdings eine periodische Textur, die sich alle 256 Gitterpunkte wiederholt. In der Regel fällt das aber nicht auf, denn wenn der Bildausschnitt so groß ist, dass mehr als eine Periode zu sehen ist, dann ist das Rauschen bereits so feinkörnig, dass der Betrachter es kaum noch im Einzelnen auflösen kann. Auch werden meist mehrere Rauschfunktionen mit unterschiedlicher Frequenz überlagert, was die Periode noch besser unkenntlich macht.

Programmierung

Das folgende Computerprogramm in der Programmiersprache C++ zeigt eine einfache, nicht auf Effizienz ausgelegte Implementierung des zweidimensionalen Perlin Noise.

#include <math.h>

// Diese Funktion interpoliert zwischen a0 bei x=0 und a1 bei x=1. x muss im Intervall [0, 1] liegen.
float interpolate(float a0, float a1, float x)
{
    float g; // Gewicht für die Interpolation
    //g = x; // lineare Interpolation; ergibt stetiges, aber nicht differenzierbares Rauschen
    g = (3.0 - x * 2.0) * x * x; // kubische Interpolation mit dem Polynom 3 * x^2 - 2 * x^3
    //g = ((x * (x * 6.0 - 15.0) + 10.0) * x * x * x); // Interpolation mit dem Polynom 6 * x^5 - 15 * x^4 + 10 * x^3
    return (a1 - a0) * g + a0;
}

// Datentyp für zweidimensionale Vektoren
typedef struct
{
    float x, y;
} vector2;

// Diese Funktion erzeugt den pseudozufälligen Gradientenvektor für den Gitterpunkt (ix,iy)
vector2 randomGradient(int ix, int iy)
{
    const unsigned w = 8 * sizeof(unsigned);
    const unsigned s = w / 2;
    unsigned a = ix, b = iy;
    a *= 3284157443;
    b ^= a << s | a >> w-s;
    b *= 1911520717;
    a ^= b << s | b >> w-s;
    a *= 2048419325;
    float random = a * (3.14159265 / ~(~0u >> 1)); // Erzeugt eine Zufallszahl im Intervall [0, 2 * Pi]
    vector2 v;
    v.x = cos(random);
    v.y = sin(random);
    return v; // v hat den Betrag 1
}

// Diese Funktion berechnet das Skalarprodukt von Abstandsvektor und Gradientenvektor
float dotGridGradient(int ix, int iy, float x, float y)
{
    vector2 grad = randomGradient(ix, iy);
    // Berechne den Abstandsvektor:
    float dx = x - (float) ix;
    float dy = y - (float) iy;
    return dx * grad.x + dy * grad.y; // Skalarprodukt
}

// Diese Funktion berechnet den Wert des Perlin noise für den Punkt (x, y)
// Das Ergebnis liegt im Intervall [-1/sqrt(2), 1/sqrt(2)]
float perlin(float x, float y)
{
    // Bestimme die Koordinaten der vier Ecken der Gitterzelle:
    int x0 = (int) floor(x);
    int x1 = x0 + 1;
    int y0 = (int) floor(y);
    int y1 = y0 + 1;

    // Bestimme die Abstände von den Gitterpunkten für die Interpolation:
    float sx = x - (float)x0;
    float sy = y - (float)y0;

    // Interpoliere zwischen den Skalarprodukten an den vier Ecken:
    float n0, n1, ix0, ix1;
    n0 = dotGridGradient(x0, y0, x, y);
    n1 = dotGridGradient(x1, y0, x, y);
    ix0 = interpolate(n0, n1, sx);
    n0 = dotGridGradient(x0, y1, x, y);
    n1 = dotGridGradient(x1, y1, x, y);
    ix1 = interpolate(n0, n1, sx);

    return interpolate(ix0, ix1, sy);
}

Weblinks

• Ken Perlin: Noise and Turbulence
• Dave Mount, University of Maryland: Procedural Generation: Perlin Noise
• Scratchapixel: Perlin Noise: Part 2