Perlin-zaj

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
Két-dimenziós részlet 3D Perlin-zajból, ahol a z=0

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.[1] Hivatalosan leírta megállapításait egy SIGGRAPH-os papírra 1985-ben.[2] 1997-ben Perlin elnyerte az Oscar Műszaki-díjat az algoritmus létrehozásáért:[3]

„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épen á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.[4]

Használata[szerkesztés]

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 az 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, amikor 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 által létrehozott valós idejű grafikáknál számítógépes játékokban.

Fejlesztés[szerkeszté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.[5]

Algoritmus részletei[szerkesztés]

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ó[szerkesztés]

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.[6] 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[szerkesztés]

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 komplexitásának skálázódásához vezet.

Interpoláció[szerkesztés]

Az utolsó lépés az interpoláció a 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 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 , akkor például a függvény, amely interpolálja értékét a 0. csomópont és értékét az 1. csomópont között, az

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.[6]

Pszeudokód[szerkesztés]

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[szerkeszté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 -vel skálázódik dimenziónként. Alternatíva Perlin-zaj létrehozására hasonló végeredménnyel a továbbfejlesztett simplex zaj és az OpenSimplex zaj.

Források[szerkeszté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.

  1. Perlin, Ken: Making Noise. noisemachine.com . Ken Perlin. [2016. március 3-i dátummal az eredetiből archiválva].
  2. (1985. július 1.) „An Image Synthesizer”. SIGGRAPH Comput. Graph. 19 (0097-8930), 287–296. o. DOI:10.1145/325165.325247. (Hozzáférés ideje: 2016. február 9.)  
  3. Az eredeti forráskódja a Ken Perlin-féle 'koherens zajfunkciónak'
  4. Ken Perlin 2001-es simplex zaj szabadalma
  5. Kerman, Phillip. Macromedia Flash 8 @work: Projects and Techniques to Get the Job Done. Sams Publishing. 2006. ISBN 9780672328282.
  6. a b libnoise

Hivatkozások[szerkesztés]