Value Noise(*) to najprostszy rodzaj szumu(**), który można wykorzystać jako podstawę do generowania różnego rodzaju zjawisk/obiektów (krajobrazy, tekstury, chmury, maski obrazów itp).
(*) - Nie znalazłem polskiego terminu, a nie wiem, jak to przetłumaczyć, żeby jakoś porządnie brzmiało (szum wartości? - nie za bardzo).
(**) - Chodzi o szum gładki - tj. taki, w którym wartości pomiędzy kolejnymi punktami zmieniają się w sposób ciągły.
Najprościej mówiąc - generowanie Value Noise polega na przypisaniu pewnym punktom w przestrzeni losowych wartości, a następnie na interpolacji tych wartości dla punktów znajdujących się pomiędzy nimi.
Losowanie wartości
[spis treści]Punkty owe są rozmieszczone w węzłach jakiejś regularnej siatki (najczęściej kartezjańskiej - w odstępach co 1). Wartości, które im się przypisuje nie mogą być całkiem losowe - muszą być pseudolosowe i zależne od danych współrzędnych (żeby zagwarantować powtarzalność algorytmu). Aby to zrealizować, trzeba użyć tzw. funkcji hashującej. Można to w bardzo prosty sposób zrealizować za pomocą zwykłego generatora liczb losowych, przykładowo dla dwóch wymiarów:
int hash(int x, int y) {
srand(x+OFFSET*y);
return rand();
}
lub
static Random rnd=new Random();
int hash(int x, int y) {
rnd.setSeed(x+OFFSET*y);
return rnd.nextInt();
}
OFFSET jest dowolną, w miarę dużą liczbą(*), która ma zagwarantować, że otrzymane wartości nie będą w jakiś oczywisty sposób symetryczne względem linii y=x.
(*) - Może być liczba pierwsza, chociaż nie sądzę, aby było to konieczne. Nie powinno się też przesadzać z jej wielkością - kilka tysięcy powinno wystarczyć.
Tablice permutacji[spis treści]
Można też skorzystać z tablic permutacji. Do tablicy 256-elementowej(*) wpisujemy losową permutację indeksów tej tablicy (liczb od 0 do 255). Tworzymy też tablicę wstępnie zainicjowanych pseudo-losowych wartości y (również o rozmiarze 256).
(*) - Najlepiej zrobić z tego tablicę 512-elementową i przepisać do drugiej połowy pierwszą połowę - zaoszczędzi to czas dzięki usunięciu konieczności obliczania indeksu modulo 256 minimalnym kosztem pamięci.
Losowanie wartości dla danego x polega teraz na wybraniu indeksu z tablicy permutacji, który to indeks wskaże nam wartość y w tablicy wartości:
//tablica z losową permutacją indeksów 0...255
//jest rozszerzona do 512 elementów
int p[512]={...};
i=(int)x; //indeks musi być liczbą całkowitą
/*
* Tu niestety musimy ograniczyć wartość i,
* ponieważ nie mamy nad jej zakresem żadnej kontroli
* (no chyba że mamy - ale lepiej nie ryzykować)
* jeśli chcemy obliczyć część ułamkową x (lub ograniczyć
* do niej samo x), powinniśmy to zrobić zanim dokonamy
* operacji modulo na zmiennej i: x-=(double)i;
*/
i%=256;
y=wartosci[ p[i] ];
/*
* Jeśli obliczamy wartości dla sąsiednich punktów,
* dodajemy do i odpowiednie liczby. Dla punktu poprzedniego
* (i-1, potrzebne dla interpolacji sześciennej, ale o tym dalej)
* dodajemy 255, które ma własność -1 dla operacji modulo 256.
* Zwróćcie uwagę, że dzięki rozszerzeniu tablicy p[] do 512
* elementów nie musimy obliczać indeksów modulo 256
*/
y_1=wartosci[ p[i+255] ];
y1=wartosci[ p[i+1] ];
Dla większej liczby wymiarów operacja wygląda nieco inaczej:
i=(int)x; j=(int)y; k=(int)z; y=wartosci[ p[p[p[i]+j]+k] ];
Dlatego najlepiej zrobić sobie z tego osobną funkcję:
int getIndex(int i, int j, int k) {
i%=256; //zabezpieczenie - nie wiem, czy słusznie
j%=256; //ale jak już powiedziałem, lepiej nie ryzykować
k%=256;
return p[p[p[i]+j]+k];
}
Wtedy kod staje się bardziej przejrzysty:
//przykładowo dla i-1, j, k+2 y=wartosci[ getIndex(i+255, j, k+2) ]; //zamiast y=wartosci[ p[p[p[i+255]+j]+k+2] ];
Interpolacja
[spis treści]Interpolacja pomiędzy tymi punktami może być dowolna. Z reguły interpolacja liniowa daje najgorsze efekty i nie poleca się jej, ale jest ona bardzo prosta i do niektórych zastosowań może być wystarczająca. Oto kilka możliwych rodzajów interpolacji(*).
(*) - Konkretnie przedstawione tu metody interpolacji są z rodzaju interpolacji funkcjami sklejanymi.
Interpolacja liniowa[spis treści]
Wartość y dla punktu x znajdującego się między dwoma punktami x0 i x1 dla interpolacji liniowej:
y = y0*(1-x) + y1*x = y0 + x*(y1-y0)
Dla uproszczenia przyjęto, że x jest obcięte do wartości ułamkowych (tj. x=x-floor(x) ).
Interpolacja cosinusami[spis treści]
Dla interpolacji cosinusami:
f = 0.5 * (1 - cos(π*x))
y = y0*(1-f) + y1*f = y0 + f*(y1-y0)
Interpolacja wielomianami(*)[spis treści]
(*) - Uwaga! Nie należy mylić tego typu interpolacji z interpolacjami wielomianowymi (patrz niżej).
Interpolować można funkcjami wielomianowymi wykorzystywanymi w szumie Perlina:
S = 3x2 - 2x3 lub S = 6x5 - 15x4 + 10x3
y = y0*(1-S) + y1*S = y0 + S*(y1-y0)
Porównując te interpolacje z liniową możemy zauważyć, że jest to zasadniczo to samo, tylko że w tym przypadku x jest zniekształcona tak, aby x-sy bliskie 0 lub 1 były jeszcze bardziej bliskie 0 lub 1 - nadaje to „gładkość” funkcji interpolującej.
Warto zwrócić uwagę, że w trakcie programowania odpowiednie zapisanie działania matematycznego może znacząco zmniejszyć ilość wykonywanych operacji, co daje zauważalne przyspieszenie. I tak, zamiast obliczać S=6x5-15x4+10x3 w naiwny sposób:
S=6*x*x*x*x*x+15*x*x*x*x+10*x*x*x;
co zabiera nam 14 działań, lepiej zapisać to w następujący sposób:
S=x*x*x*(x*(6*x-15)+10);
co zabiera nam tylko 7 działań, dając dwukrotne przyspieszenie.
Można też spróbować użyć zmiennych tymczasowych do przechowywania wyższych potęg. Tak czy siak - warto pokombinować, ale zawsze najlepiej zapisać w komentarzu orginalną formułę, żeby nie wpaść w pułapkę przedwczesnego optymalizowania.
Interpolacja cosinusami jest bardzo zbliżona do interpolacji x3.
Interpolacja sześcienna
[spis treści]
Przedstawione wyżej interpolacje (oprócz liniowej) mają tę cechę, że w punktach całkowitych (w węzłach siatki) funkcja będzie „płaska”. Generalnie rzecz biorąc nie powinniśmy tego nawet zauważyć, ale jeśli komuś się to nie podoba, może zastosować inną interpolację. Najprostszym wyborem jest interpolacja sześcienna:
Założenia:
x ∈ [0; 1] (x musimy „obciąć” do części ułamkowej)
x0 = -1, y0 = f(x0)
x1 = 0, y1 = f(x1)
x2 = 1, y2 = f(x2)
x3 = 2, y3 = f(x3)
y = a3 x3 + a2 x2 + a1 x + a0
Dla zwykłej interpolacji współczynniki są równe
Można jednak dobrać inne współczynniki, które zmieniają trochę wygląd interpolacji pomiędzy x=0 a x=1. Nowa funkcja nie będzie się zgadzać dla punktów x=-1 i x=2, ale nie ma to znaczenia, ponieważ wartości spoza zakresu [0; 1] nie są w ogóle obliczane:
lub
Jak można zauważyć, interpolacje te mają taką wadę, że wymagają znajomości wartości w więcej, niż bezpośrednio sąsiadujących z danym x-em punktach (w tym przypadku poprzednią y0, sąsiadujące y1 i y2, oraz następną y3). No i wymagają też więcej obliczeń, przez co są wolniejsze, ale jak bardzo - tego nie sprawdzałem. Ale interpolacje takie dają za to o wiele milsze dla oka efekty(*).
(*) - Szumy gradientowe są tak skonstruowane, że zwykłe interpolacje zapewniają dostateczną jakość, dlatego nie stosuje się w nich „szerszych” interpolacji.
Interpolacja w wielu wymiarach[spis treści]
Interpolację w więcej niż 1 wymiarze przeprowadza się stosując interpolację kolejno dla każdej osi. Przykładowo dla 2 wymiarów:
dane: z00, z01, z10, z11 (zji w odpowiednich punktach [xi, yj] ); punkt [x, y], w którym obliczamy wartość z
interpolujemy wartości np. najpierw wzdłuż osi X - pomiędzy z00 i z01, oraz pomiędzy z10 i z11 w punkcie x:
z0=Interpolacja(z00, z01, x)
z1=Interpolacja(z10, z11, x)
a następnie wzdłuż osi Y - pomiędzy otrzymanymi uprzednio wartościami w punkcie y:
z=Interpolacja(z0, z1, y)
Sumowanie szumu
[spis treści]Otrzymany w ten sposób szum jest mało ciekawy (jest gładki, o co notabene nam chodziło). Dlatego sumuje się go ze sobą samym, po uprzednim przeskalowaniu (pomniejszeniu). Nadaje mu to miłą dla oka ziarnistość, oraz właściwości fraktalne. Dzięki temu zabiegowi (oraz dzięki zapewnionej przez pseudolosowość powtarzalności), możemy dokonywać w zasadzie nieograniczonego powiększania takiego szumu (zbliżenia) bez ryzyka, że w pewnym momencie skończymy z gładkimi płaszczyznami (co jest nudne).
Sumuje się z reguły serię szumów o coraz większej częstotliwości i coraz mniejszej amplitudzie. Są to tzw. oktawy.
Dla każdej oktawy częstotliwość zwiększamy dwukrotnie (czyli jak w muzyce) - tak jest łatwiej, ale można poeksperymentować z innymi sposobami. Amplitudę wymnażamy natomiast o stały współczynnik o wartości pomiędzy 0 (wyłącznie) a 1 (włącznie) - im większy współczynnik, tym bardziej poszarpany będzie szum. Ogólny wzór wygląda tak (x może być wektorem współrzędnych, jeśli obliczamy szum dla więcej niż jednego wymiaru):
v = ValueNoise(x) + a*ValueNoise(2*x) + a2*ValueNoise(4*x) + ... + an*ValueNoise(2n*x)
Wartość a jest nazywana persystencją (ang. persistence) i jak już wspomniałem, jest to wartość z zakresu (0, 1]. Jest ona stała, ale jeśli ktoś chce, może poeksperymentować z różnymi wartościami dla różnych częstotliwości (czy nawet w zależności od innych zmiennych - współrzędnych, wartości podstawowego szumu...).
|
+ |
|
+ |
|
= |
|
|
Ilustracja sumowania szumów w jednym wymiarze. Trzy pierwsze obrazki pokazują kolejne „poziomy” szumu. Ostatni obrazek przedstawia zsumowanie trzech oktaw.
|
||||||
|
|
|
Porównanie szumu w 2 wymiarach. Z lewej gładki szum, z prawej szum zsumowany z czterech oktaw.
|
|
Lektura uzupełniająca
- Fractal terrain generation - lista artykułów traktujących o fraktalnym generowaniu krajobrazów. W szczególności teksty związane z tym artykułem to: Value Noise oraz Fractional Brownian Motion.
- Perlin Noise - wbrew tytułowi, tekst traktuje o Value Noise. Wyjaśnia w bardzo prosty sposób to wszystko, o czym mówiłem we własnym artykule.
- Value noise - artykuł na wikipedii. W bardzo krótki ale jasny sposób wyjaśnia ideę Value Noise.
Wszystkie ilustracje wykonane przeze mnie przy pomocy programów OpenOffice Calc, GIMP, Java (NetBeans).
Brak komentarzy:
Prześlij komentarz