keretezett|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. 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:Az eredeti forráskódja a Ken Perlin-féle 'koherens zajfunkciónak'
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.Ken Perlin 2001-es simplex zaj szabadalma
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.Kerman, Phillip. Macromedia Flash 8 @work: Projects and Techniques to Get the Job Done. Sams Publishing. 2006. .
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 komplexitásának skálázódásához vezet.
Interpoláció 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.
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];
// 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] + dy*Gradient[iy][ix]); }
// 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 -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.
Jegyzetek
Fordítás
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)
Kategória:Számítógépes grafika Kategória:Fraktálok