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.

In vielen Open-World-Spielen, z. B. Minecraft, 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 sogenanntes Gradientrauschen. Das bedeutet, dass an festgelegten äquidistanten Gitterpunkten jeweils ein pseudozufälliger Gradient definiert wird, dem die Rauschfunktion in der Nähe dieses Punktes folgt. Zwischen diesen Punkten wird interpoliert, um eine glatte Funktion zu erhalten.

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, und der Funktionswert an jeder ganzzahligen Koordinate wird auf Null gesetzt. In der Umgebung des Punkts $i$ , wenn also $x\approx i$ , folgt der Rauschfunktionswert damit 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. 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 verwendet, deren Ableitung an den Punkten $x=i$ und $x=j$ gleich Null ist. Ursprünglich verwendete Ken Perlin kubisch hermitesche Splines, aber weil es wünschenswert ist, eine stetige zweite Ableitung zu haben, schlug er später Polynome vom Grad 5 vor. Diese beiden Funktionen sind sehr ähnlich, aber mit einem Polynom vom Grad 5 kann auch die zweite Ableitung an den Endpunkten gleich Null gemacht werden, sodass die Rauschfunktion überall eine stetige zweite Ableitung hat.

In zwei Dimensionen bilden die ganzzahligen Koordinaten ein quadratisches Gitter, und jedem Gitterpunkt wird ein pseudozufälliger zweidimensionaler Gradientenvektor 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.

Funktionsweise

Im zweidimensionalen Fall wird auf die zu texturierende Oberfläche ein Quadratgitter gelegt. Jedem Gitterpunkt $q_{i,j}$ ist ein pseudozufälliger in der Regel normierter Gradientenvektor ${\vec {g}}_{i,j}$ in der Ebene zugeordnet. Diese Vektoren 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 Koordinatenwerten $i,j\in \mathbb {Z}$ des Gitterpunkts berechnet werden.

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

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.

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.

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 Implementierung des zweidimensionalen Perlin Noise.

#include <math.h>

// Diese Funktion interpoliert linear zwischen a0 und a1. Das Gewicht w sollte im Intervall [0.0, 1.0] liegen.
float interpolate(float a0, float a1, float x)
{
    if (x < 0.0) return a0;
    if (x > 1.0) return a1;
    return (a1 - a0) * x + a0;
    //return (a1 - a0) * (3.0 - x * 2.0) * x * x + a0; // Alternative: Kubische Interpolation mit dem Polynom 3 * x^2 - 2 * x^3
    //return (a1 - a0) * ((x * (x * 6.0 - 15.0) + 10.0) * x * x * x) + a0; // Alternative:  Interpolation mit dem Polynom 6 * x^5 - 15 * x^4 + 10 * x^3
}

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

// Diese Funktion erzeugt einen zufälligen Richtungsvektor
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 = sin(random);
    v.y = cos(random);
    return v;
}

// Diese Funktion berechnet das Skalarprodukt des Abstandsvektors und den Gradientenvektoren
float dotGridGradient(int ix, int iy, float x, float y)
{
    // Bestimmt den Gradienten der ganzzahligen Koordinaten
    vector2 gradient = randomGradient(ix, iy);
    // Berechnet den Abstandsvektor
    float dx = x - (float) ix;
    float dy = y - (float) iy;
    return dx * gradient.x + dy * gradient.y; // Skalarprodukt
}

// Diese Funktion berechnet das Perlin noise für die Koordinaten x, y
float perlin(float x, float y)
{
    // Bestimmt 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;
    // Bestimmt die Gewichte für die Interpolation
    float sx = x - (float)x0;
    float sy = y - (float)y0;
    // Interpoliert zwischen den Gradienten der vier Ecken
    float n0, n1, ix0, ix1, value;
    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); // Gibt den Wert der Funktion für das Perlin noise zurück
}

Weblinks

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

Einzelnachweise

↑ Stefan Gustavson, Linköping University: Simplex noise demystified

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Stefan Gustavson, Linköping University: Simplex noise demystified