Szum Perlina
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/88/Perlin_noise_example.png/220px-Perlin_noise_example.png)
Szum Perlina – algorytm generowania szumu gradientowego, nazwany na cześć swojego twórcy, Kena Perlina. Jest to pierwsza implementacja szumu gradientowego, a jego opis został upubliczniony w 1985 roku. Szum ten nie został opatentowany.
Historia
Szum został stworzony w roku 1983 przez Perlina jako rezultat frustracji spowodowanej „maszyno-podobnym” wyglądem ówczesnej grafiki komputerowej oraz w czasie jego prac nad filmem Tron[1]. Wyniki swojej pracy Perlin opublikował w 1985 roku[2]. W 1997 roku autor algorytmu otrzymał za swoją pracę Oscara w kategorii technicznej[3].
Pseudokod
Podany pseudokod jest dwuwymiarową implementacją klasycznego szumu Perlina[potrzebny przypis]. Jest to zmodyfikowana wersja, inna pod względem semantyki, ale o tym samym działaniu co oryginalny szum z 1985 roku.
//Interpolacja liniowa function lerp(float a0, float a1, float w) { return (1.0 - w)*a0 + w*a1; } // Wylicza iloczyn skalarny wektora odległości z odpowiednim wektorem gradientu function dotGridGradient(int ix, int iy, float x, float y) { // Wcześniej wyliczone wektory gradientu extern float Gradient[IYMAX][IXMAX][2]; // Oblicz wektor odległości float dx = x - (float)ix; float dy = y - (float)iy; // Oblicz iloczyn skalarny return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]); } // Oblicz szum na pozycji x, y function perlin(float x, float y) { int x0 = floor(x); int x1 = x0 + 1; int y0 = floor(y); int y1 = y0 + 1; float sx = x - (float)x0; float sy = y - (float)y0; float n0, n1, ix0, ix1, value; n0 = dotGridGradient(x0, y0, x, y); n1 = dotGridGradient(x1, y0, x, y); ix0 = lerp(n0, n1, sx); n0 = dotGridGradient(x0, y1, x, y); n1 = dotGridGradient(x1, y1, x, y); ix1 = lerp(n0, n1, sx); value = lerp(ix0, ix1, sy); return value; }
Złożoność algorytmiczna
Dla wymiarów, dla których generowany jest szum, złożoność obliczeniowa ewaluuje do [4]. Istnieją alternatywy dla szumu Perlina, które generują podobne wyniki, z tą różnicą, że ich złożoność obliczeniowa jest mniejsza. Zaliczają się do nich m.in. szumy simplex czy OpenSimplex.
Przypisy
- ↑ Szum Perlina [online], Khan Academy [dostęp 2017-08-10] .
- ↑ KenK. Perlin KenK., An Image Synthesizer, „SIGGRAPH Comput. Graph.”, 19 (3), 1985, s. 287–296, DOI: 10.1145/325165.325247 (ang.).
- ↑ Ken’s Academy Award [online], mrl.nyu.edu [dostęp 2017-08-10] (ang.).
- ↑ KenK. Perlin KenK., Noise Hardware [online], csee.umbc.edu (ang.).