Guten Abend
Vorwort
Da ich mich vor kurzem nach Perlin Noise umgesehen habe und kaum fündig wurde (auch nichts auf der
dp 
) habe ich mich entschlossen,
ein kleines Tutorial zu schreiben. Mehr oder weniger als Dankeschön an die
DP-Community!
Dank diversen Quellen bin ich mir
nicht sicher, ob das, was ich unter Perlin Noise verstehe nicht zufällig Value-Noise ist, da es bei sehr vielen Quellen, wo ich mein Wissen her habe, verwechselt wurde. Bitte um Korrektur, sofern notwendig.
Was ist Perlin Noise (Abk. P.N.)
Meines Wissens nach ist P.N. kurz und bündig eine pseudozufällige Rauschfunktion. Zum Einsatz kommt sie größtenteils in der Computergrafik.
Sie eignet sich u.A. für "die Bildsynthese, um natürliche Phänomene wie Wolken, Landschaftstopologien oder Wasser zu simulieren" (laut
Wikipedia).
Unser Algorithmus wird grundsätzlich ein zwei dimensionales Array vom Typ Byte zurücklieferen. Hierbei wird es sich dann um
solch ein Resultat handeln! Was man damit nun anstellt, ist einem selbst überlassen.
Damit man sich darunter evt. mehr vorstellen kann, hier eine
Landschaftsgenerierung Anhand dieser
Heightmap.
(Jeder Pixelwert (im Heightmap gibt die Höhe der Landschaft relativ zu der Position an, wobei 0 (schwarz) der niedrigste und 255 (weiß) der höchste Wert ist)
Notwendiges Vorwissen- Umgang mit Vektoren (Skalarprodukt, Normalisierung)
- Interpolation (nicht linear!)
Der Algorithmus- Einen Seed für den Zufallszahlen-Generator setzen. Dieser kann beliebig gewählt werden. Weiters ist dieser Schritt hauptsächlich zuständig für das Aussehen des Resultates!
- Ein beliebig großes, zwei dimensionales Array von Vektoren (x, y Tupel) erstellen und zufällig initialisieren und direkt normalisieren. Dieses Array nennen wir von nun an dispMap (displacement Map).
- Nun für jeden Punkt des Resultates:
- nach dispMap Dimensionen mappen -> diesen Punkt nennen wir nun pos.
- pos ist nun von vier Punkten im dispMap umzingelt. Man berechnet nun jeweils den Richtungsvektor von den vier Punkten zu pos. Diese vier Richtungsvektoren speichern wir
in einem Array ab und nennen es gradients[].
- Nun bildet man jeweils das Skalaprodukt zwischen den vier dispMap und gradient Vektoren. Diese speichern wir und nenn sie von nun an dotprods[] (dot products array).
- Letzendlich interpoliert man die dotprodts zweimal horizontal (um die beiden Punkte bei pos.x zu bestimmen) und einmal vertikal, um letzendlich den Wert für den Punkt pos zu bestimmen.
- Das Resultat (eine Fließkommazahl) anschließend normalisieren: durch die diagonale eines der Quadrate in der gridMap dividieren.
Der Algorithmus mag auf dem ersten Blick schlecht verdaubar aussehen, aber durch die folgenden Codesnippets sollte es deutlicher werden.
Implementierung
Bevors damit losgeht - die Snippets sind zum größten Teil aus der Demo (Anhang) und zum Teil schnell aus dem Gedächtnis hingeschrieben.
Könnte kleine Tippfehler enthalten.
Delphi-Quellcode:
// einfaches Setzen über eine Zahl
procedure setRandomSeed(const Seed: Integer); overload;
begin
RandSeed := Seed;
end;
// einfache Seed Berechnung durch (evt.) künstlich hergeführtes Integer-Overflow
procedure setRandomSeed(const Seed: AnsiString); overload;
var
idx, sd: Integer;
begin
sd := 0;
for idx := 1 to Length(Seed) do
sd := sd*256 + Byte(Seed[idx]);
RandSeed := sd;
end;
Delphi-Quellcode:
// Datenstruktur für ein Vektor:
type
PVector2 = ^TVector2;
TVector2 = record
X, Y: Single;
procedure assign(const AX, AY: Single);
procedure normalize();
class operator multiply(const A, B: TVector2): Single;
end;
// ...
procedure TVector2.assign(const AX, AY: Single);
begin
X := AX;
Y := AY;
end;
procedure TVector2.normalize();
var
size: Single;
begin
size := SQRT(X*X + Y*Y);
if size = 0 then Exit; // divison-by-zero vermeiden
X := X/size;
Y := Y/size;
end;
class operator TVector2.multiply(const A, B: TVector2): Single;
begin
Result := A.X*B.X + A.Y*B.Y;
end;
// ...
var
dispMap: Array of Array of TVector2;
// Punkt 2.
const
size = 8; // 8x8 dispMap!
var
i, j: Integer;
begin
SetLength(gridMap, size, size);
for i := 0 to size-1 do
for j := 0 to size-1 do
begin
dispMap[i][j].Assign(2*Random() - 1, 2*Random() - 1);
dispMap[i][j].normalize();
end;
end;
- Nun der Kern:
Delphi-Quellcode:
type
TByteArrayArray = Array of Array of Byte;
TInterpolationFunc = function(const x, y, t: Single): Single;
TVector2Map = Array of Array of TVector2;
// ...
function interpolator(const x, y, t: Single): Single;
var
f: Single;
begin
f := 3*t*t - 2*t*t*t;
Result := x * (1-f) + y * f;
end;
{
w und h geben die Breite und Höhe des Resultates an
interpolator ist eine Funktion (vorzugsweise nicht-linear)
}
function generateNoiseBitmap(const w, h: Integer; const dispGrid: TVector2Map;
const interpolator: TInterpolationFunc): TByteArrayArray;
var
vertices: Array[0..3] of PVector2;
gradients: Array[0..3] of TVector2;
dotprods: Array[0..3] of Single;
gridDelta, pos: TVector2;
leftBottomIdx: TPoint;
fac: TVector2;
y, x, i: Integer;
pValue: PByte;
diag, interpolation: Single;
begin
SetLength(Result, h, w);
if not Assigned(interpolator) then Exit;
// gridDelta gibt die breite und höhe eines Quadrates des dispMaps an (sie ist abhängig von der Breite und Höhe des Resultates):
gridDelta.Assign(w / High(dispGrid), h / High(dispGrid[0]));
// die Diagonale wird für die Normalisierung der Werte berechnet
diag := gridDelta.Size;
for y := 0 to h - 1 do
begin
pos.Y := y;
pValue := @Result[y,0];
for x := 0 to w - 1 do
begin
pos.X := x;
// leftBottomIdx ist die nach dispMap gemappte Position des Punktes "pos"
leftBottomIdx := Point(Floor(x/gridDelta.X), Floor(y/gridDelta.Y));
// hier werden die 4 umzingelnde Punkte bestimmt
vertices[0] := @dispGrid[leftBottomIdx.X+0, leftBottomIdx.Y+0];
vertices[1] := @dispGrid[leftBottomIdx.X+0, leftBottomIdx.Y+1];
vertices[2] := @dispGrid[leftBottomIdx.X+1, leftBottomIdx.Y+1];
vertices[3] := @dispGrid[leftBottomIdx.X+1, leftBottomIdx.Y+0];
// Gradienten Berechnung
gradients[0] := vector2(gridDelta.X*(leftBottomIdx.X+0), gridDelta.Y*(leftBottomIdx.Y+0)) - pos;
gradients[1] := vector2(gridDelta.X*(leftBottomIdx.X+0), gridDelta.Y*(leftBottomIdx.Y+1)) - pos;
gradients[2] := vector2(gridDelta.X*(leftBottomIdx.X+1), gridDelta.Y*(leftBottomIdx.Y+1)) - pos;
gradients[3] := vector2(gridDelta.X*(leftBottomIdx.X+1), gridDelta.Y*(leftBottomIdx.Y+0)) - pos;
// fac gibt an, wie weit die gemappte Position horizontal und vertikal in den umzingelnden 4 Vertices liegt (in %, also [0,1])
fac.Assign(
x/gridDelta.X - leftBottomIdx.X,
y/gridDelta.Y - leftBottomIdx.Y);
// Skalarproduktberechnung
for i := 0 to 3 do
dotprods[i] := gradients[i] * vertices[i]^;
interpolation :=
interpolator( // vertikale interpolation der..
interpolator(dotprods[0], dotprods[3], fac.X), // beiden horizontal interpolierten..
interpolator(dotprods[1], dotprods[2], fac.X), // Werte!
fac.Y) / diag; // die direkt normalisiert wird
// interpolation = -1..1
interpolation := (interpolation + 1)/2;
// interpolation = 0 .. 1
pValue^ := Max(0,Min(255, Floor(255*interpolation)));
inc(pValue);
end;
end;
end;
Überlagerung
Der Algorithmus generiert nun Graustufenbilder. Diese sehen je nach dispMap Dimensionen verschieden aus.
Das Rauschen ist umso stärker, je größer die Dimension des dispMaps ist.
In der Praxis berechnet berechnet man mehrere solcher NoiseMaps (mit 8x8, 16x16, 32x32) und überlagert (einfaches Blenden der Resultate!) diese!
Resultate
Im Anhang befindet sich eine kleine Demo Anwendung.
In der Memo befinden sich zwei Zeilen:
Bedeutung (Zeile 1):
- 8x8 gibt die Dimension des dispMaps an
- 0.5 gibt die Gewichtung für die Überlagerung später an
Es können beliebig viele Zeilen hinzugefügt werden! Achtet aber darauf, dass die Syntax stimmt und die Gewichtungen in Summe 1 ergeben!
Ich weiß nicht mehr genau warum, aber drüber befindet sich noch eine SpinEdit Komponente, bei der man einstellen muss, wie viele
dispMaps generiert werden sollen.
Exception-Handling ist nicht wirklich drinnen, hierbei handelt es sich nur um eine Demo!
Resultate sind übrigens im Anhang auch zu finden!
PS: Ich bin nicht allzu sehr ins Detail gegangen, das wird mir gerade bewusst. Sofern es Unklarheiten gibt, einfach Fragen, ich werde, so gut es geht, versuchen, diese zu beantworten.
Antwort
Linear-Darstellung
