Perlin-zaj

A Perlin-zaj egy típusa a gradiens zajoknak, Ken Perlin fejlesztette ki 1983-ban abból a célból, hogy a számítógép által generált grafika kevésbé tűnjön mesterségesnek. Hivatalosan leírta megállapításait egy SIGGRAPH-os papírra 1985-ben. 1997-ben Perlin elnyerte az Oscar Műszaki-díjat az algoritmus létrehozásáért:

Két-dimenziós részlet 3D Perlin-zajból, ahol a z=0

„Ken Perlin számára a Perlin-zaj kifejlesztéséért, mely technika arra használható, hogy természetesnek tűnő mintázatok legyenek gyárthatóak vele számítógép által a filmes vizuális effektekhez. A Perlin-zaj kifejlesztése lehetővé tette a számítógépes grafikus művészek számára, hogy átfogóbban ábrázolhassák a bonyolult természeti jelenségeket vizuális hatásokban a filmiparban.”

Perlin nem nyújtott be kérést az algoritmus szabadalmára, viszont 2001-ben feljogosították a szabadalomra a 3D és afölött implementálható simplex zajhoz a textúra szintézisért. A simplex zajnak ugyanaz a célja, de egyszerűbb térkitöltő rácsot használ. A simplex zaj enyhíti Perlin "klasszikus zajának" néhány problémáját, köztük a számítási komplexitást és vizuális jelentőségét tekintve az irányvonalak felfedezhetőségét.

Használata

A Perlin-zaj egy procedurális textúra primitív, egyfajta gradiens zaj, amit vizuális hatásokkal foglalkozó művészek használnak, hogy a számítógépes grafika valóságosságát növeljék. A funkció álvéletlen megjelenéssel rendelkezik, de az összes vizuális részlete ugyanolyan méretű. Ez a tulajdonság lehetővé teszi, hogy könnyen szabályozható legyen; többszörösen méretezett példánya a Perlin-zajnak beilleszthető matematikai kifejezésekbe, hogy ezáltal létrehozzon változatos procedurális textúrákat. Olyan szintetikus textúrákat, amik Perlin-zaj alapján készülnek, gyakran használnak CGI-ben, hogy a számítógép által generált vizuális elemek – mint például tárgyak felülete, tűz, füst, vagy felhők – természetesebbnek hassanak, imitálva a természetben fellelhető szabályos, ugyanakkor véletlenszerű textúrákat.

Abban az esetben is gyakran van használva textúrák generálásához, ha a rendelkezésre álló memória rendkívül korlátozott, mint demók esetében, és egyre inkább keresik a lehetőségét a grafikus feldolgozó egység (GPU) által létrehozott valós idejű grafikáknál a számítógépes játékokban.

Fejlesztés

Ken Perlin munkájának eredménye a Perlin-zaj, aki a Matematikai Alkalmazások Csoportjánál (MAGI) fejlesztette a Disney CGI sci-fi filmjéhez, a Tronhoz (1982). 1997-ben elnyerte az Oscar Műszaki-díjat a Filmművészeti és Filmtudományi Akadémiától a CGI-technológiához való hozzájárulásáért.

Algoritmus részletei

A Perlin-zaj a leggyakrabban két-, három- vagy négydimenziós függvényként van implementálva, de definiálható bármely számú dimenzióra. A leimplementálása tipikusan magába foglal három lépést: rácsdefiníció véletlenszerű gradiensvektorokkal, a skaláris szorzat számítása a távolság-gradiensvektorok között és interpoláció ezen értékeken.

Rács definíció

Definiálj egy n dimenziós rácsot, ahol minden rácspont tartalmaz egy véletlenszerű, n dimenziós egységhosszúságú gradiensvektort, kivéve egydimenziós esetén, ahol az átmenetek (gradiensek) véletlenszerű skaláris mennyiségek -1 és 1 közt.

A véletlenszerű gradienseket hozzárendelni egy- és két dimenzióhoz célszerű egy véletlenszám generátorral. Magasabb dimenzióknál a Monte-Carlo-módszer a megszokott, aminek lényege, hogy egy koordináta-rendszeren egy egység méretű kockában véletlenszerű pontok kerülnek kiválasztásra, és amely pontok kívül esnek a kockát kitöltő gömb területén, azokat szelektáljuk. A megmaradó pontokat normalizáljuk, hogy illeszkedjenek az egységnyi gömb felületéhez. A folyamat addig zajlik, amíg a szükséges mennyiségű véletlenszerű gradienst megkapjuk.

Annak érdekében, hogy megakadályozzuk a túl költséges folyamatát az új gradiensek számításának a rácspontokra, néhány implementáció hash táblát használ a véges számú, előre kiszámított gradiensvektorokhoz. Hash használatával lehetőség nyílik a random seedelésre, miáltal több ugyanolyan példányban jöhet létre a Perlin-zaj.

Skaláris szorzat

Adott egy n dimenziós paraméter a zaj függvényhez, a következő lépés az algoritmusban, hogy meghatározzuk, mely rács celláiban kell megválni a véletlenszerű pontoktól. Az adott cella minden sarokpontján meghatározzuk a pont és a csomópont (node) közötti távolságvektort. A skaláris szorzat a csomópontnál lévő gradiensvektor és a távolságvektor között lesz számítva.

Egy pont számításához egy kétdimenziós rácsban szükség lesz 4 távolságvektorra és skaláris szorzatra, míg három dimenziónál 8 távolságvektor és 8 skaláris szorzat fog kelleni. Ez a $O(2^{n})$ komplexitásának skálázódásához vezet.

Interpoláció

Az utolsó lépés az interpoláció a $2^{n}$ skaláris szorzatok számítása közt azon cellák csomópontjainál, amelyek tartalmazzák a paraméter pontjait. Ennek következtében a zajfüggvény 0 értéket ad vissza, ha rács csomópontjai önmagukra értékelődnek ki.

Az interpoláció egy olyan függvény használatával történik, aminek nincs első deriváltja (és esetleg második deriváltja) a $2^{n}$ rács csomópontjában. Az ennek hatására a zajfüggvény gradiense minden ponton egybeesik az előre kiszámított véletlenszerű gradiensvektorral. Ha $n=1$, akkor például a függvény, amely interpolálja $a_{0}$ értékét a 0. csomópont és $a_{1}$ értékét az 1. csomópont között, az

$f(x)=a_{0}+\operatorname {smoothstep} (x)\cdot (a_{1}-a_{0})\ \ {\text{ahol }}0\leq x\leq 1$

ahol a smoothstep függvény volt használva.

Számítógépes grafikában a zajfüggvények használata tipikusan [-1.0,1.0] tartomány közti értékeket állít elő. Rendszerint az előbbi tartományon belüli Perlin-zaj produkálásához az interpolált értékeknek szükséges lehet, hogy skálázva legyenek néhány skálázódási faktor szerint.

Pszeudokód

A következő pszeudokód egy két-dimenziós implementációja a Klasszikus Perlin-zajnak.

// Funkció a lineáris átmenethez a0 és a1 között
// A w (weight) súlynak a [0.0, 1.0] tartományban kell lennie
float lerp(float a0, float a1, float w) {
    return (1.0 - w)*a0 + w*a1;
}

// Kiszámítja a skaláris szorzatát a távolság- és gradiensvektoroknak.
float dotGridGradient(int ix, int iy, float x, float y) {
    
    // Előre kiszámított (vagy egyéb) gradiens vektorokat minden rácsponthoz
    extern float Gradient[IYMAX][IXMAX][2];
    
    // Távolság vektor kiszámítása
    float dx = x - (float)ix;
    float dy = y - (float)iy;
    
    // Skaláris szorzat kiszámítása
    return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]);
}

// Perlin-zaj kiszámítása az x, y koordinátáknál
float perlin(float x, float y) {
    
    // A rács cellakoordinátájának kiszámítása
    int x0 = floor(x);
    int x1 = x0 + 1;
    int y0 = floor(y);
    int y1 = y0 + 1;
    
    // Interpoláció súlyának meghatározása
    // Használható magasabb rendű polinom/s-görbe is
    float sx = x - (float)x0;
    float sy = y - (float)y0;
    
    // Átmenetképzés a rácspontok és gradiensek között
    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;
}

Komplexitás

A zajfüggvény minden egyes kiértékeléséhez, a hely- és gradiensvektorok skaláris szorzatát muszáj kiértékelni az összes csomópontján a tartalmazó rács celláinak. A Perlin-zaj komplexitása ebből kifolyólag $O(2^{n})$-vel skálázódik $n$ dimenziónként. Alternatíva Perlin-zaj létrehozására hasonló végeredménnyel a továbbfejlesztett simplex zaj és az OpenSimplex zaj.

Fordítás

• Ez a szócikk részben vagy egészben a Perlin noise című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Matt Zucker-féle Perlin-zaj matematika GYIK
• Rob Farber tanbemutatója a Perlin-zaj generáláshoz
  
• Perlin-zaj részletes magyarázata (C++ forráskóddal)