Aktuelle Version vom 21. März 2012, 15:28 Uhr

Hinweis: Dieser Artikel wurde von den Benutzern des Wikis zum exzellenten Artikel berufen! (weitere exzellente Artikel)

Perlin Noise ist ein Fraktal-Algorithmus welcher mit sehr einfachen Formeln komplexe und theoretisch endlose Gebilde berechnen kann. Da Perlin Noise darauf basiert, scheinbar zufällige Funktionen mit weichen Übergängen (die Steigung kann einen gewissen Wert nicht überschreiten) zu benutzen, 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.

Zufallswerte aber wie?

Es wird eine Funktion benötigt die für jede Dimension einen Parameter hat und für die gleichen Parameter auch die gleichen Zahlen liefert.

// 1. Dimension
function Werte1D(X:Integer):ErgebnisTyp
// 2.Dimension
function Werte2D(X,Y:Integer):ErgebnisTyp

mit einen Array

Diese Aufgabe kann ein Array erfüllen welches man zuvor mit Zufallswerten gefüllt hat. also:

Werte1D:array [0..X_Werte_Max] of ErgebnisTyp;
Werte2D:array [0..X_Werte_Max,0..Y_Werte_Max] of ErgebnisTyp;

eigene Zufallsfunktion

Ein gängiger Algorithmus sieht beispielsweise so aus:

x := x + Seed;
x := ( x shl 13 ) xor x;
rand := 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 := 1 - ( (n * (n * n * 15731 + 789221) + 1376312589) and $7fffffff) / 1073741824;

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

Interpolation

Zwischen den Werten aus dem Array versucht man nun mit einer Interpolation schöne Übergänge zu schaffen. Am schnellsten ist die lineare Interpolation, jedoch kann durch einen Trick auch eine Sinus artige Interpolation sehr schnell ablaufen. Auf den folgenden Bildern sieht man links linear interpolierte Höhenwerte und auf der rechten seite eine Sinus/Cosinus artige Interpolation. Die größern Punkte entsprechen den im Array abgespeicherten Zufallswerten.

Die Interpolations funktion muss zunächst einmal die beiden zu interpolierenden Werte entgegen nehmen. Zusätzlich muss noch durch mindestens einen weiteren Parameter klar werden, welche Position (im obrigen Bild X) den gesuchte Wert haben soll.

Wäre einem die Ausführgeschwindigkeit egal, könnten die beiden Interpolations Funktionen folgerndermaßen aussehen:

//Hinweis: nicht getestet

function InterpoliereLinear(Wert1, Wert2, FaktorWert1: Real): Real;
// Lineare Interpolation von zwei Werten 
// FaktorWert1 muss zwischen 0 und 1 liegen
begin
  result := Wert1*FaktorWert1 + Wert2*(1-FaktorWert1);
end;

function InterpoliereCos(Wert1, Wert2, FaktorWert1: Real): Real;
// Cosinus/Sinus artige Interpolation von zwei werten; 
// FaktorWert muss zwischen 0 und 1 liegen
begin
  result := Wert1*((cos(pi/2*FaktorWert1)+1)/2) + Wert2*(1-(cos(pi/2*FaktorWert1)+1)/2)
end;

Jedoch möchte man meistens möglichst schnelle Berechnungen haben. Besonders die Sinus und Cosinus Funktionen können unter Umständen zum Problem werden. Um trotzdem Sinuns- und Cosinus-Interpolation zu erzeugen kann man im Voraus sich ein Array mit Interpolationswerten anlegen. Da Rechner schneller mit Integerwerten als mit Gleitkommerwerten rechnen werden wir im folgenden Beispiel erstere verwenden.

var
  Interpolation:array [0..Interpolation_Bereich-1]of Integer;
  //Interpoaltions_Bereich ist legt die Maximale Anzahl an Punkten fest,
  // die für zwei Interpolationswerte ermittelt werden können(inklusive Randpunkte).

const
  Interpolation_Max = 1000 // * entspricht dem Wert 1.000; 
                           // * je höher dieser Wert deso genauer das Ergebnis.
                           // * je höher dieser Wert ist deso niedriger  müssen
                           //   die Interpolationswerte sein

procedure BeimStart;
begin
{..}
  // Im Interpolations Array werden mit den Werten die von Interpolation_Max bis 0 gehen gefüllt.
  // wobei Interpolation[0] = Interpolation_Max ist
  // und Interploation[high(Interpolation)] = 0 ist
  for i := 0 to high(Interpolation) do Interpolation[I] := round((cos(pi/(Interpolation_Bereich-1)*i)+1)/2*Interpolation_Max);
{..}
end;


function Interpoliere(Wert1, Wert2: Integer; Nr, Von: Integer): Integer;
// Interpoliert zwischen 2 Werten
// Nr ist gibt den Punkt an den man ermitteln möchte. Von die Anzahl der Interpolations schrite
var
  Wert1_Faktor:Integer;
begin
  if Nr > Von then raise ERangeError.CreateFmt('Nr Wert %d nicht in 0..%d',[Nr,Von-1]);
  if Von > Interpolations_Bereich raise ERangeError.CreateFmt('Von Wert %d nicht in 0..%d',[0,-1]);
  Wert1_Faktor := Interpolation[(Interpolation_Bereich*  Nr)div Von];
  result := (Wert1*Wert1_Faktor) div Interpolation_Max
   + (Wert2*(1000 - Wert1_Faktor)) div Interpolation_Max;
end;

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

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 Persistenzen.
Frequenzfaktor = 2; Rechentiefe = 5
Links oben: Persistenz 0.2
Rechts oben: Persistenz 0.4
Links unten: Persistenz 0.6
Rechts unten: Persistenz 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 Persistenz 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 Persistenz 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 * Persistenz

Wert = Wert + Offset

Weiterführendes

Einsatzgebiete

Neben der Generierung von Texturen und Heightmaps - welche von den Grafiken und Quellcodes in diesem Artikel bevorzugt behandelt wurden - gibt es natürlich noch andere Einsatzgebiete. Einige davon sind:

• Animation, also gehen, Mimik oder jede andere Form von Bewegung kann durch Perlin Noise abwechslungsreicher und somit etwas "menschlicher" gestaltet werden. Der Erfinder Ken Perlin hat hierfür auf seiner Homepage ein paar gute Beispiele.
• Modifikation von Meshes: was bei Heightmaps am offensichtlichesten ist kann man auch auf eine Kugel anwenden um einen wunderbar unregelmäßigen, aber dennoch realistisch wirkenden Stein, Planeten oder einen Kometen daraus zu machen.
• Denkbar wäre die Verwendung von Perlin Noise natürlich auch für verschiedenste Umwelteinflüsse wie Wind (was sich sowohl in Animationen als auch Geräuschlautstärke auswirken kann), aber natürlich auch für künstliche Einflüsse wie Börsenkurse in einem Strategiespiel.
• Prozedurale Texturen (u.a. Holz-, Stein-, oder Marmor-Oberflächen) können gut mit Perlin Noise und einigen Zusatzfunktionen erzeugt werden.

Erweiterungen

Perlin Noise kann (wie nahezu jeder andere Algorithmus auch) nach eigenen Wünschen modifiziert werden. Häufige Modifikationen sind:

• Tilebare Texturen erstellen, also Texturen welche links und rechts - und ggf. auch oben und unten - exakt gleich aussehen. Dieses Problem wird in diesem DGL-Forenthread (ab Seite 2) etwas näher behandelt.
• Nachbearbeitung der Ausgabewerte. Hier können wir das endgültige Resultat noch sehr stark verändern. Denkbar wäre hier beispielsweise, dass wir die Unterwasser und über Wasser - Landschaft ganz unterschiedlich skalieren. Das eindrucksvollste Beispiel hierfür dürfte jedoch ein Algorithmus für eine Himmelstextur sein, welcher hier zu finden ist. Dieser Algorithmus verwendet einfaches Perlin Noise, modifiziert jedoch die Ausgabewerte mit einer Exponentialfunktion, wodurch eine (meines Erachtens) eindrucksvolle Wolkendecke entsteht. Das endgültige Ergebnis des Algorithmus beinhaltet natürlich noch etwas mehr als diese einfache Exponentialfunktion, jedoch könnte man auch dies im weiteren Sinne als Modifikation der Ausgabewerte sehen.

Verwandte Themen

Die Dekomprimierung von JPEG-Bildern basiert auf der Überlagerungen von Cosinus-Schwingungen einer vorgegebenen Frequenz und einer (von Bild zu Bild) variierenden Amplitude. Diese Überlagerung ist sehr ähnlich der Frequenzüberlagerung beim Perlin Noise. Der Unterschied ist natürlich, dass bei JPEG Cosinus Schwingungen verwendet werden und beim Perlin Noise zufällige Werte welche interpoliert werden.

Die Komprimierung von JPEG-Bildern bildet nun das Gegenteil der Überlagerung von Cosinus-Schwingungen, also der Berechnung der Amplituden der einzelnen Frequenzen. Derartige Berechnungen basieren alle auf der Fourier Transformation.

Also wenn ihr nun verstanden habt wozu die Überlagerung von verschiedenen Frequenzbändern in der Lage ist (wofür dieser Artikel hoffentlich hilfreich war), euch diverse Themen der Mathematik wie integrieren, differenzieren und vor allem Regression nicht allzu sehr abschrecken und ihr immer schon mal wissen wolltet wie derartige Bildkompression oder die Frequenzbalken eurer Audiowidergabe entstehen, wäre wohl nun ein (neuer?) Anlauf vielversprechend.