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 liniowafunctionlerp(floata0,floata1,floatw){return(1.0-w)*a0+w*a1;}// Wylicza iloczyn skalarny wektora odległości z odpowiednim wektorem gradientufunctiondotGridGradient(intix,intiy,floatx,floaty){// Wcześniej wyliczone wektory gradientuexternfloatGradient[IYMAX][IXMAX][2];// Oblicz wektor odległościfloatdx=x-(float)ix;floatdy=y-(float)iy;// Oblicz iloczyn skalarnyreturn(dx*Gradient[iy][ix][0]+dy*Gradient[iy][ix][1]);}// Oblicz szum na pozycji x, yfunctionperlin(floatx,floaty){intx0=floor(x);intx1=x0+1;inty0=floor(y);inty1=y0+1;floatsx=x-(float)x0;floatsy=y-(float)y0;floatn0,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);returnvalue;}
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.PerlinKenK., An Image Synthesizer, „SIGGRAPH Comput. Graph.”, 19 (3), 1985, s. 287–296, DOI: 10.1145/325165.325247(ang.).