Der Perlin-Noise-Algorithmus

Einfache Zufallszahlen sind die falsche Art von Zufall für die meisten Grafik- und Simulationsaufgaben. Ein Raster, in dem jede Zelle ein unabhängiges rand() % 256 ist, sieht aus wie Fernsehrauschen — zu nichts zu gebrauchen. Wolken, Terrain, Marmor, Feuer und unzählige prozedurale Texturen brauchen stattdessen Zufall, der glatt ist: benachbarte Punkte sollten ähnliche Werte haben, während weit entfernte Punkte sich völlig unterscheiden dürfen. Ken Perlin entwickelte genau das 1983 (ursprünglich für den Film Tron) und erhielt dafür 1997 einen Technical Achievement Award der Academy of Motion Picture Arts and Sciences.

Die Idee

Man legt ein unsichtbares Raster über die Ebene und gibt jeder Rasterecke einen festen pseudozufälligen Gradientenvektor — eine Richtung, keinen Wert. Um den Noise-Wert an einem beliebigen Punkt zu finden, bestimmt man zuerst, in welche Rasterzelle er fällt, und berechnet dann das Skalarprodukt zwischen jedem der vier Eck-Gradienten dieser Zelle und dem Vektor von dieser Ecke zum Abfragepunkt. Das liefert vier Zahlen, eine pro Ecke, die jeweils beschreiben, wie sehr der Gradient dieser Ecke "zum Abfragepunkt hin" oder "von ihm weg" zeigt.

Diese vier Zahlen werden dann mit einem gewichteten Mittel kombiniert, basierend darauf, wie nahe der Abfragepunkt an jeder Ecke liegt — glatt, nicht linear, mithilfe einer Kurve (die Fade-Funktion unten), die sanft ein- und ausschwingt statt sich mit konstanter Rate zu ändern. Genau diese Glättung hält das Ergebnis über Zellgrenzen hinweg kontinuierlich: Zwei Punkte auf beiden Seiten einer Rasterlinie erhalten fast dieselbe Mischung benachbarter Gradienten, sodass das Rauschen nie springt.

Die Gradienten selbst stammen aus einer festen Permutationstabelle: einer gemischten Liste der Zahlen 0–255, indiziert über die Rasterkoordinaten, um pro Ecke eine von wenigen Gradientenrichtungen auszuwählen. Da die Tabelle einmal fest steht und überall wiederverwendet wird, liefern dieselben Eingabekoordinaten immer denselben Noise-Wert — Perlin Noise ist eine deterministische Funktion von (x, y), sobald die Tabelle aufgebaut ist, eigentlich also gar nicht zufällig.

Implementierung

#include "plot.hpp"
#include <math.h>
#include <stdlib.h>

int perm[512];

void init_permutation() {
    int p[256];
    for (int i = 0; i < 256; i++) p[i] = i;

    srand(1);
    for (int i = 255; i > 0; i--) {
        int j = rand() % (i + 1);
        int tmp = p[i];
        p[i] = p[j];
        p[j] = tmp;
    }
    for (int i = 0; i < 512; i++) perm[i] = p[i & 255];
}

double fade(double t) {
    return t * t * t * (t * (t * 6 - 15) + 10);
}

double lerp(double t, double a, double b) {
    return a + t * (b - a);
}

double grad(int hash, double x, double y) {
    switch (hash & 7) {
        case 0: return  x + y;
        case 1: return  x - y;
        case 2: return -x + y;
        case 3: return -x - y;
        case 4: return  x;
        case 5: return -x;
        case 6: return  y;
        default: return -y;
    }
}

double perlin(double x, double y) {
    int xi = (int)floor(x) & 255;
    int yi = (int)floor(y) & 255;
    double xf = x - floor(x);
    double yf = y - floor(y);

    double u = fade(xf);
    double v = fade(yf);

    int aa = perm[perm[xi] + yi];
    int ab = perm[perm[xi] + yi + 1];
    int ba = perm[perm[xi + 1] + yi];
    int bb = perm[perm[xi + 1] + yi + 1];

    double x1 = lerp(u, grad(aa, xf, yf), grad(ba, xf - 1, yf));
    double x2 = lerp(u, grad(ab, xf, yf - 1), grad(bb, xf - 1, yf - 1));

    return lerp(v, x1, x2);
}

// Fractal Brownian motion: several octaves of Perlin noise at increasing
// frequency and decreasing amplitude, summed together.
double fbm(double x, double y, int octaves) {
    double total = 0;
    double amplitude = 1.0;
    double frequency = 1.0;
    double maxValue = 0;

    for (int i = 0; i < octaves; i++) {
        total += perlin(x * frequency, y * frequency) * amplitude;
        maxValue += amplitude;
        amplitude *= 0.5;
        frequency *= 2.0;
    }

    return total / maxValue;
}

void frame() {
    static bool ready = false;
    if (!ready) {
        init_permutation();
        ready = true;
    }

    int cell = 4;
    for (int py = 0; py < plot_height; py += cell) {
        for (int px = 0; px < plot_width; px += cell) {
            double n = fbm(px / 80.0, py / 80.0, 4);

            int gray = (int)((n + 1.0) * 0.5 * 255.0);
            if (gray < 0) gray = 0;
            if (gray > 255) gray = 255;

            PlotColor(gray, gray, gray);
            PlotFilledRectangle(px, py, px + cell, py + cell);
        }
    }
}

init_permutation baut die gemischte Tabelle einmal auf (abgesichert über das ready-Flag in frame(), da dieses Sample kein eigenes setup() hat — siehe unten). grad wählt anhand eines Hash-Werts eine von acht festen Richtungen aus und gibt direkt das Skalarprodukt mit (x, y) zurück, eine gängige Vereinfachung von Perlins ursprünglichem 3D-Gradientensatz für zwei Dimensionen. perlin macht das oben beschriebene Vier-Ecken-Nachschlagen-und-Mischen; fade ist die Glättungskurve, lerp die gewichtete Mischung.

fbm (Fractal Brownian Motion) ist das, was das Ergebnis tatsächlich wie Wolken aussehen lässt statt wie einen verwaschenen Fleck: Es tastet perlin mehrfach ab, mit sich verdoppelnder Frequenz und halbierender Amplitude, und addiert die Ergebnisse. Die erste Oktave liefert die grobe Form, jede folgende Oktave fügt feinere Details obenauf — dieselbe Idee wie beim Hinzufügen von Obertönen zu einer Grundfrequenz bei Klang.

Dieses Sample definiert kein setup(), weshalb das Standard- PlotCanvas(640, 480) automatisch greift — dasselbe Muster wie bei den Samples zu Bresenham-Linien und Midpoint Circle. frame() zeichnet das Rauschen als Raster von 4×4-Pixel-Blöcken statt mit einem Zeichenaufruf pro Pixel und bildet den fbm-Wert jedes Blocks aus seinem nativen Bereich von etwa [-1, 1] auf einen Graustufenwert ab.

Schritt für Schritt durchgerechnet

Betrachte den Noise-Wert bei x = 0.5, y = 0.5 — genau in der Mitte der Rasterzelle zwischen den Ecken (0,0), (1,0), (0,1), (1,1). Der Beitrag jeder Ecke ist das Skalarprodukt ihres Gradienten mit dem Vektor zu (0.5, 0.5) relativ zu dieser Ecke:

Genau am Mittelpunkt ist fade(0.5) = 0.5 für beide Achsen, sodass jede Ecke gleich gewichtet wird. Der Durchschnitt der vier Skalarprodukte oben ergibt 0 — genau das, was an einem Punkt mit gleichem Abstand zu allen vier Ecken bei diesen (illustrativen) Gradienten passieren sollte: Keine einzelne Eckrichtung dominiert. Punkte außerhalb der Mitte gewichten die näheren Ecken stärker, und genau daraus ergibt sich die eigentliche Form des Rauschens.

Warum die Glättung wichtig ist

Zwei Designentscheidungen in diesem Algorithmus lassen sich leicht falsch treffen, und beide sind sichtbar, wenn man es tut:

• Lineare Interpolation statt fade. t direkt statt t³(6t² − 15t + 10) zu verwenden liefert immer noch kontinuierliches Rauschen, aber mit sichtbaren Knicken entlang der Rasterlinien — die Änderungsrate ist an Zellgrenzen diskontinuierlich, auch wenn der Wert es nicht ist. Die erste und zweite Ableitung von fade sind bei t = 0 und t = 1 beide null, und genau das macht das Raster im Ergebnis unsichtbar.
• Zu wenige Oktaven. Eine einzelne Oktave Perlin Noise sieht weich und blobartig aus — als Rauschen erkennbar, aber nicht als Wolken oder Terrain. Echte prozedurale Texturen summieren fast immer mehrere Oktaven; das Sample oben verwendet vier, mit jeweils verdoppelter Frequenz, was reicht, um von "verwaschen" zu "überzeugend organisch" zu kommen.

Fazit

Perlin Noise verwandelt eine feste Tabelle pseudozufälliger Richtungen in eine kontinuierliche Funktion, die auf jeder Zoomstufe und an jedem Punkt organisch aussieht, dabei aber vollständig deterministisch bleibt — dieselben (x, y) liefern immer denselben Wert, ohne dass mehr Zustand gespeichert werden müsste als die Permutationstabelle selbst. Diese Kombination — natürlich aussehend, unendlich dicht und günstig neu zu berechnen statt zu speichern — ist der Grund, warum es vier Jahrzehnte nach seiner Entwicklung für einen einzigen Film immer noch so viel prozeduralen Inhalten zugrunde liegt.