imported>Ugnil: Minetest heißt jetzt anders

2026-04-02T11:23:52Z

Minetest heißt jetzt anders

Neue Seite

[[Datei:Perlin noise.jpg|mini|Zweidimensionales Perlin Noise]]
[[Datei:2D sample of Perlin noise.png|mini|Fraktales Rauschen durch Überlagern mehrerer Frequenzen]]
'''Perlin Noise''' ist eine [[Rauschen (Physik)|Rauschfunktion]] auf der Basis von pseudozufälligen [[Gradient]]enwerten an Gitterpunkten. Diese [[Textursynthese]] geht auf [[Ken Perlin]] zurück, der sie 1982 für den Film [[Tron (Film)|Tron]] entwickelte, wofür er 1997 einen [[Oscar/Technische Verdienste#1990 bis 1999|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-Spiel]]en, z. B. [[Minecraft]] oder [[Luanti]], wird Perlin-Noise verwendet, um Landschaften zu generieren.

Im einfachen Fall erhält man eine unregelmäßig wellenförmig verlaufende [[Funktion (Mathematik)|Funktion]] in einer oder mehreren Dimensionen, deren [[Frequenz]] sich aus dem [[Abstand]] der Gitterpunkte ergibt. Perlin Noise kann als [[Fraktal|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 [[Textur (Oberflächenattribut)|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. Mittels Perlin Noise kann man Zufallsrauschen erzeugen, das auf verschiedenen Skalen selbstähnlich ist, und somit zufällige [[Fraktal|fraktale]] Objekte modellieren.

== Definition ==
Perlin Noise ist ein [[Textursynthese#Prozedurale Verfahren|prozedurales]] Gradientrauschen. Es werden regelmäßig angeordnete ([[Äquidistanz (Geometrie)|äquidistante]]) Gitterpunkte festgelegt, und jedem wird ein [[Pseudozufällig|pseudozufälliger]] [[Gradient (Mathematik)|Gradient]] zugeordnet, 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 werden entweder vorab in einem [[Feld (Datentyp)|Array]] gespeichert oder bei jedem Zugriff per [[Pseudozufällige Funktion|Pseudozufallsfunktion]] aus den ganzzahligen Koordinatenwerten des Gitterpunkts berechnet.

Zwischen den Werten, die sich für die nächstgelegenen Gitterpunkte ergeben, wird [[Interpolation (Mathematik)|interpoliert]], wodurch man je nach Wahl der Interpolationsfunktion eine einmal oder sogar zweimal [[Differenzierbarkeit#Stetige Differenzierbarkeit und höhere Ableitungen|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 [[Pixel]]abstand sein, da höhere Frequenzen nur noch zu [[Alias-Effekt]]en 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 von der Gittergröße, d. h. dem Abstand der Gitterpunkte, abhängig.

== Eine Dimension ==
Um Perlin Noise in einer Dimension zu generieren, ordnet man jedem [[Ganze Zahl|ganzzahligen]] [[Koordinatensystem|Koordinatenwert]] <math>i</math> einen pseudozufälligen [[Gradient]]en <math>g_i</math> (eine [[Steigung]]) der Funktion zu. In der Umgebung des Punkts <math>i</math>, wenn also <math>x \approx i</math>, folgt der Rausch[[funktionswert]] näherungsweise der [[Lineare Funktion|linearen Funktion]] <math>f_i(x) = (x-i)\cdot g_i</math>

Für einen Punkt <math>x \in \R</math> zwischen zwei ganzzahligen Punkten <math>i < x < j = i+1</math> wird zwischen den Funktionswerten <math>f_i(x)</math> und <math>f_j(x)</math> interpoliert:
:<math>f(x) = f_i(x) h(j-x) + f_j(x) (1-h(j-x)); \quad i \le x < j, \; h(0) = 0, \, h(1) = 1</math>.

Diese Interpolation ist in der Regel nicht linear über dem [[Abstand]] <math>j-x</math>, weil sonst die [[Ableitung (Mathematik)|Ableitung]] der Funktion an den ganzzahligen Punkten nicht [[Stetige Funktion|stetig]] wäre. Stattdessen wird eine Interpolationsfunktion <math>h</math> verwendet, deren Ableitung an den Punkten ''0'' und ''1'', also bei <math>x=i</math> und <math>x=j</math>, gleich Null ist. Ursprünglich verwendete Ken Perlin [[Kubisch Hermitescher Spline|kubisch hermitesche Splines]] wie etwa <math>h(x) = 3x^2-2x^3</math>, aber weil es oft wünschenswert ist, dass <math>f(x)</math> überall eine stetige zweite [[Ableitung (Mathematik)|Ableitung]] hat, schlug er später [[Polynom]]e vom Grad 5 vor, die das ermöglichen.

== Zwei Dimensionen ==
[[Datei:PerlinNoiseInterpolated.png|mini|Gitter mit Gradientenvektoren und resultierender Rauschfunktion]]

Auf die zu texturierende Oberfläche wird ein [[Gitter (Geometrie)|Quadratgitter]] gelegt. Jedem Gitterpunkt <math>q_{i,j}</math> ist ein [[2D|zweidimensionaler]], [[Pseudozufall|pseudozufälliger]], in der Regel normierter Gradientenvektor <math> \vec g_{i,j}</math> 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.<ref>Stefan Gustavson, Linköping University: [https://weber.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf Simplex noise demystified]</ref>

Um für einen Punkt <math>p</math> den Wert <math>f(p)</math> der Rauschfunktion zu ermitteln, wird zunächst die Zelle des Quadratgitters bestimmt, in die er fällt. <math>q_{i,j}</math> sei die linke untere Ecke. Für jeden Eckpunkt <math>q_{m,n}</math> dieser Zelle berechnet man das [[Skalarprodukt]] des Gradientenvektors mit dem Vektor von <math>q_{m,n}</math> zu <math>p</math>:
:<math>s_{m,n}=\vec g_{m,n}\cdot(p-q_{m,n}); \quad m = i,i+1, \; n = j,j+1</math>.
Diese vier Werte werden nun [[Interpolation (Mathematik)|interpoliert]] mittels einer Überblendfunktion <math>h</math>, die von <math>h(0) = 0</math> bis <math>h(1) = 1</math> ansteigt:
:<math>f_0(p) = s_{i,j} \cdot h(1-x) + s_{i+1,j} \cdot h(x)</math>,
:<math>f_1(p) = s_{i,j+1} \cdot h(1-x) + s_{i+1,j+1} \cdot h(x)</math>,
:<math>f(p) = f_0(p) \cdot h(1-y) + f_1(p) \cdot h(y)</math>.
Dabei sind <math>x</math> und <math>y</math> die Koordinaten von <math>p</math> bezüglich des linken unteren Gitterpunkts <math>q_{i,j}</math>, normiert auf <math>x,y \in [0,1]</math>. In der Regel wird das Gitter zur Vereinfachung der Rechnung normiert und an den Koordinatenachsen ausgerichtet, so dass <math>q_{i,j} = (i,j)</math>, und der Punkt, an dem die Rauschfunktion auszuwerten ist, wird vor der Berechnung zu <math>p</math> transformiert (durch multiplizieren seiner Komponenten mit der Frequenz). Dann sind <math>x</math> und <math>y</math> einfach die Komponenten von <math>p-q_{i,j}</math>. Allgemeiner gilt:
:<math>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}</math>.

Als Überblendfunktion kann die smoothstep-Funktion <math>h(x) = x^2(3-2x)</math> 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 <math>h(x) = x^3(6x^2-15x+10)</math> verwendet, mit der auch die zweite Ableitung stetig ist, d. h., wenn man die Rauschfunktion <math>f(p)</math> als Fläche über der <math>x,y</math>-Ebene darstellt, ändert sich ihre Krümmung nirgends sprunghaft. Für beide gilt <math>h(1-x) = 1-h(x)</math>, so dass man die Funktion nur zweimal (<math>n</math> mal in <math>n</math> Dimensionen) auswerten muss.

== Mehr Dimensionen ==
Das Verfahren kann auf beliebig viele Dimensionen verallgemeinert werden. In <math>n</math> Dimensionen muss man entsprechend die Skalarprodukte an den <math>2^n</math> 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 <math>n</math> Dimensionen nur <math>n+1</math> Gitterpunkte an den Ecken eines [[Simplex (Mathematik)|Simplex]] auswertet.

== Bestimmung der Gradienten ==
Um den Gradientenvektor an einem Gitterpunkt zu erhalten, werden zunächst die Koordinaten des Gitterpunkts [[Hashfunktion|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 <math>P</math> mit 512 Elementen, das eine Zufallspermutation der Zahlen 0 bis 255 zweimal nacheinander enthält; es ist <math>P_i = P_{i+256}</math>. Die Koordinaten <math>i,j,k,\cdots</math> des Gitterpunkts werden modulo 256 als Indizes genommen (durch [[Bitweiser Operator#UND|bitweises UND]] mit der Konstante 255, das schneller ist als eine Division):
:<math>a_1 = P_{i \bmod 256}</math>,
:<math>a_2 = P_{a_1 + (j \bmod 256)}</math>,
:<math>a_3 = P_{a_2 + (k \bmod 256)}</math>.
Der Hashwert ist dann <math>a_n</math> im <math>n</math>-dimensionalen Fall. Statt der Addition kann man auch das [[Bitweiser Operator#XOR|bitweise XOR]] nutzen, dann muss <math>P</math> nur 256 Elemente haben (<math>a_2 = P_{a_1 \oplus (j \bmod 256)}</math>), oder die Modulodivision wird erst nach der Addition gemacht (<math>a_2 = P_{(a_1 + j) \bmod 256}</math>). Man kann außerdem einen Schritt des Hashverfahrens einsparen, indem man bereits mit <math>a_2 \oplus (k \bmod 256)</math> (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.
<syntaxhighlight lang="c++">
#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);
}
</syntaxhighlight>

== Weblinks ==
* Ken Perlin: [https://mrl.cs.nyu.edu/~perlin/doc/oscar.html Noise and Turbulence]
* Dave Mount, University of Maryland: [https://www.cs.umd.edu/class/fall2019/cmsc425/handouts/lect14-perlin.pdf Procedural Generation: Perlin Noise]
* Scratchapixel: [https://www.scratchapixel.com/lessons/procedural-generation-virtual-worlds/perlin-noise-part-2 Perlin Noise: Part 2]
== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus (Computergrafik)]]

Perlin-Noise - Versionsgeschichte

imported>Ugnil: Minetest heißt jetzt anders