Szum Perlina

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Szum Perlinaalgorytm 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

 1  //Interpolacja liniowa
 2  function lerp(float a0, float a1, float w) 
 3  {
 4      return (1.0 - w)*a0 + w*a1;
 5  }
 6  
 7  // Wylicza iloczyn skalarny wektora odległości z odpowiednim wektorem gradientu
 8  function dotGridGradient(int ix, int iy, float x, float y) 
 9  {
10  
11      // Wcześniej wyliczone wektory gradientu
12      extern float Gradient[IYMAX][IXMAX][2];
13  
14      // Oblicz wektor odległości
15      float dx = x - (float)ix;
16      float dy = y - (float)iy;
17  
18      // Oblicz iloczyn skalarny
19      return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]);
20  }
21  
22  // Oblicz szum na pozycji x, y
23  function perlin(float x, float y) 
24  {
25      int x0 = floor(x);
26      int x1 = x0 + 1;
27      int y0 = floor(y);
28      int y1 = y0 + 1;
29  
30      float sx = x - (float)x0;
31      float sy = y - (float)y0;
32  
33      float n0, n1, ix0, ix1, value;
34      n0 = dotGridGradient(x0, y0, x, y);
35      n1 = dotGridGradient(x1, y0, x, y);
36      ix0 = lerp(n0, n1, sx);
37      n0 = dotGridGradient(x0, y1, x, y);
38      n1 = dotGridGradient(x1, y1, x, y);
39      ix1 = lerp(n0, n1, sx);
40      value = lerp(ix0, ix1, sy);
41  
42      return value;
43  }

Złożoność algorytmiczna[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  1. Szum Perlina, Khan Academy [dostęp 2017-08-10].
  2. Publikacja w płatnym dostępie – wymagana płatna rejestracja lub wykupienie subskrypcji Perlin, Ken, An Image Synthesizer, „SIGGRAPH Comput. Graph.”, 19 (3), 1985, s. 287–296, DOI10.1145/325165.325247 (ang.).
  3. Ken’s Academy Award, mrl.nyu.edu [dostęp 2017-08-10] (ang.).
  4. Ken Perlin, Noise Hardware, csee.umbc.edu (ang.).