XI. ERDÉLYI TUDOMÁNYOS DIÁKKÖRI KONFERENCIA KOLOZSVÁR, 2008. MÁJUS 23-24
Virtuális valóság
Vezető tanár
Szerző
Dr. Soós Anna, docens
Sipos Tamás
Babeş-Bolyai Tudományegyetem
Babeş-Bolyai Tudományegyetem
Matematika és Informatika kar
Matematika és Informatika kar
Numerikus Analízis és Statisztika Tanszék
Matematika és Informatika szak IV. Évfolyam
Kolozsvár 2008
1
Fraktál interpoláció Az euklideszi geometria, trigonometria és számítások arra tanítottak minket, hogy a körülvevő világ formáinak modellezését egyenesek, körök, parabolák és egyéb egyszerű mértani görbék segítségével képzeljük el. Körülnézve a mindennapi életben, hamar észrevehetjük ezt több helyen is, egy egyszerű példa mondjuk a háztartásbeli tárgyak alakja, jellemző rájuk a egyenesség, szabályosság, ugyanakkor egy másik, meggyőző példa, a programozási nyelvek által biztosított rajzolási lehetőségek, általában rajzunkat pontokból, egyenesekből, körökből, háromszögekből állíthatjuk össze. A technika fejlődésével a videokártyák is ezekre az úgymond primitívekre specializálódtak, és hardveresen támogatták minél gyorsabb megjelenítésüket. Az euklideszi geometria és az elemi függvények, mint a szinusz, koszinusz, polinomok az alapját képezik a kisérleti adatok vizsgálatának. Tegyük fel, adva van nekünk egy valós változójú F(x) függvényünk és feltételezzük, hogy egy kísérletet ír le, mondjuk az idő függvényében. Folyamatos mérésre általában képtelen az ember, így különböző mérési pillanatokban bizonyos értékeket kapunk amit matematikailag egy halmazzal ábrázolhatunk: { (xi , Fi): i = 0, 1, 2, …, N } , ahol az N az adatok száma, Fi = F(xi) és az xi –k valós számok, rendezve x0 < x1 < x2 < x3 < …< xN A hagyományos módszer az adatok feldolgozására, az az, hogy először ábrázoljuk a pontjainkat grafikusan az
2
síkban, majd mértanilag feldolgozzuk. Ez a feldolgozás
többféleképpen is történhet, az adatok milyenségétől függően, összeköthetjük őket szakaszokkal, vagy szerkezthetünk hozzájuk illeszkedő polinomokat, vagy akár elemi függvények kombinacióira is gondolhatunk. Bármelyik módszer mellett is döntünk, a cél ugyanaz: az adatokat egy klasszikus mértani mennyiséggel reprezentáljuk, egy egyszerű formulával, amely már többet mond számunkra, és amellyel már könyebben dolgozhatunk. Elemi függvényeink, mint például a trigonometrikus fuggvények vagy a racionális függvények magukban hordoznak egy közös tulajdonságot: ha “elég” nagyra felnagyítjuk őket, lokálisan egyenessé “válnak”. Ezért az érintő módszer elég hatásosan alkalmazható
2 pontok megközelítésére, ha a ponthoz közel alkalmazzuk. Az elemi “euklideszi” függvények nem csak a mértani tartalmukért nagyon hasznosak, hanem azért is, mert kifejezhetőek egyszerű formulákban, könnyen adhatóak át információként., és gyorsan számíthatóak számítógép segítségével. A
grafikus
rendszerek
segítséget
nyújtanak
az
embercsinálta
tárgyak
megformázására. Ez nem meglepő, hiszem ezek a tágyak euklideszi geometria szellemében voltak tervezve. Sokszor azt szeretnénk, hogy a graikus rendszerünk bonyolultabb feladatokat is megoldjon. Ezért bevezetjűk a fraktál interpolációs függvény fogalmát. Ezek függvények grafikonjával közelíthetünk olyan képeket, amiknek a körvonala hasonlít egy hegyhez, felhőhöz vagy akár a falról lelógó sztalaktitokhoz, melyek alakja elég véletlenszerű, így nem igazán lehet közelíteni őket euklideszi függvényekkel. A fraktál interpolációs függvény hasonlít az elemi függvényhez, annyiban, hogy neki is mértani jellege van, felírható egyszerű “formulákkal” és hamar kiszámítható. Viszont a nagy különbség kettőjük között, a fraktál jelleg. Lehet például nemegész fraktál dimenziója. 1. Definíció: Egy adathalmaz az egy olyan ponthalmaz, melynek alakja: { (xi,Fi) ∈
2
: i = 0, 1, 2, ..., N }, ahol
x0 < x1 < x2 < x3 < ... < xN . Egy ezenek
az adatoknak megfelelő interpolációs függvény, egy olyan folytonos
f:[x0,xN]→
, amelyre teljesül, hogy: f(xi) = Fi minden i = 0, 1, 2, ..., N –re.
Az (xi,Fi)
2
-beli pontokat interpolációs pontoknak nevezzük, és azt mondjuk, hogy az f
függvény interpolálja az adatokat; ugyanakkor f (grafikonja) átmegy az interpolációs pontokon. 2. Definíció: Metrikus térnek nevezzük az (X,d) párost, ahol X egy halmaz, és a d : X× X →
egy valós értékű függvény, amely méri a “távolságot” két pont között úgy,
hogy teljesíti az alábbi feltételeket:
3 i.
d(x,y) = d(y,x) ∀ x,y ∈ X
ii.
0 < d(x,y)<∞ ∀x,y ∈ X, x ≠ y
iii.
d(x,x)=0, ∀x ∈ X
iv.
d(x,y) ≤ d(x,z)+d(z,y), ∀x,y,z ∈ X
3. Definíció: Az X tér fölötti d1 és d 2 metrikákról azt mondjuk, hogy ekvivalensek, ha ∃c1 , c 2 ∈
konstansok, 0 < c1 < c 2 < ∞ , úgy, hogy: c1d1 (x,y) ≤ d 2 (x,y) ≤ c 2 d1 (x,y), ∀(x,y) ∈ (X × X)
4. Definíció: Az f : X1 → X 2 függvény, ahol (X1 , d1 ), ( X 2 , d 2 ) metrikus terek, folytonos,
ha ∀ε > 0 és ∀x ∈ X1 ∃δ >0 , úgy hogy: d1 (x,y)<δ ⇒ d 2 (f (x),f (y))<ε 5. Definíció: Egy (X,d) metrikus térben levő {xn }∞n =1 sorozatról azt mondjuk, hogy Cauchy-
sorozat, ha ∀ε > 0-ra, ∃N > 0 úgy, hogy: d(xn , xm ) < ε , ∀n,m>N 6. Definício: Egy (X,d) metrikus térben levő {xn }∞n =1 sorozat konvergál egy x ∈ X ponthoz,
ha ∀ε > 0 -ra ∃N > 0 úgy, hogy: d(xn , x) < ε , ∀n>N 7. Definíció: Az (X,d) metrikus tér teljes, ha ∀ {xn }∞n =1 ⊂ X Cauchy-sorozat konvergál egy
x ∈ X ponthoz 8. Definíció: Legyen S ⊂ X részhalmaza az (X,d) metrikus térnek. Ekkor S-ről azt mondjuk, hogy kompakt, ha ∀ {xn }∞n =1 ⊂ S sorozatnak létezik S-ben konvergens részsorozata
4 Az
előbbi
fogalmak
ismeretében
bevezethetjük
az
ideális
teret
a
fraktálok
tanulmányozására. Az (X,d) teljes metrikus tér fölött definiáljuk a H(X) teret melyről a későbbiekben belátjuk, hogy metrikus tér “h” metrikával. Lássuk, hogy mi is az a H(X) tér:
9. Definíció: Legyen (X,d) egy teljes metrikus tér. Ekkor jelölje H(X) az X összes nemüres kompakt részhalmazainak halmazát.
10. Definíció: Legyen (X,d) egy teljes metrikus tér, x∈X és B∈ H(X). Definiáljuk a d(x,B) = Min{ d(x,y): y∈B } távolságot, melyet az x pont távolságának nevezzük a B halmaztól.
11. Definíció: Legyen (X,d) egy teljes metrikus tér és legyen A, B ∈ H(X). Definiáljuk a d(A,B) = Max{ d(x,B): x∈A }, amelyet az A∈ H(X) halmaz távolságának nevezzük a B∈ H(X) halmaztól
12. Definíció: : Legyen (X,d) egy teljes metrikus tér és legyen A, B∈ H(X). Ekkor a h(A,B) = max{ d(A,B), d(B,A) } az A ∈ H(X) és a B ∈ H(X) halmazok közötti Hausdorff távolságnak nevezzük.
1. Tétel: A “h” távolságfüggvény egy metrika a H(X) felett. Bizonyítás: Legyen A, B, C ∈ H(X). Könnyen belátható, hogy h(A,A) = Max{ d(A,A), d(A,A) } = d(A,A) = Max{ d(x,A): x∈A} = 0. Ugyancsak könnyen belátható, hogy az A és B kompaktsága miatt ∃a ∈ A, ∃b ∈ B úgy, hogy h(A,B) = d(A,B). Ugyanakkor 0 ≤ h(A,B) < ∞ . Ha A ≠ B akkor ∃a ∈ A úgy, hogy a ∉ B . Ekkor h(A,B) ≥ d(a,B) > 0. Tudjuk, hogy h(A,B) = Max{ d(A,B), d(B,A) } = Max{ d(B,A), d(A,B) } = h(B,A) ⇒ h(A,B) = h(B,A). Most mutassuk ki, hogy h(A,B) ≤ h(A,C) + h(C,B). Látható, hogy ∀a ∈ A :
d(a,B) = Min{ d(a,b), b∈ B } ≤ Min{ d(a,c)+d(c,b): b∈B } ∀c ∈ C } = = d(a,c) + Min{ d(c,b): b ∈ B } ∀c ∈ C , így d(a,B) ≤ Min{ d(a,c), c ∈ C } + Max{ Min{ d(c,b): b ∈ B }: ∀c ∈ C } = = d(a,C) + d(C,B) ⇒ (mivel ∀a ∈ A-ra igaz az egyenlőtlenség)
5 ⇒ d(A,B) ≤ d(A,C) + d(C,B) Hasonlóan: d(B,A) ≤ d(B,C) + d(C,A), és így h(A,B) = Max{ d(A,B), d(B,A) } ≤ Max{ d(B,C), d(C,B) } + + Max{ d(A,C), d(C,A) } = h(B,C) + h(A,C) ⇒ h(A,B) ≤ h(B,C) + h(A,C) ⇒ (H(X), h) metrikus tér.
2. Tétel: Legyen (X,d) teljes metrikus tér. Ekkor (H(X),h) szintén teljes metrikus tér, mitöbb, ha { A n ∈ H(X) }∞n =1 Cauchy-sorozat, akkor A= Lim A n ∈ H(X) n →∞
jellemezhető a következő formában is: A={x∈ X: ∃ {x n ∈ A n }∞n=1 Cauchy-sorozat, úgy, hogy x n konvergál az x-hez} Most bevezetjük a metrikus terek közötti transzformaciókat, a kontrakciós leképezéseket, hogy bebizonyíthassuk a kontrakciós leképezés tételét, melyet alkalmazhatunk a “fraktálok terére”, ezzel eljutva az attraktor fogalmáig.
13. Definíció: Legyen (X,d) metrikus tér. Egy transzformáció az X tér fölött egy olyan f:X → X függvény, amely megfeleltet pontosan egy f(x) ∈ X pontot minden x ∈ X pontnak.
Ha S ⊂ X akkor f(S) = {f(x): x ∈ S}. f injektív, ha ∀x,y ∈ X úgy, hogy f(x) = f(y) ⇒ x = y. f szürjektív, ha f(X) = X. f invertálható, ha injektív és szürjektív, és ebben az esetben definiálható egy, az f inverzének nevezett, transzormáció f −1 : X → X úgy, hogy f −1 (y) = x , ahol x ∈ X az egyetlen olyan pont, amelyre y = f(x).
14. Definíció: Egy w:
2
→
2
transzformációt affin transzformációnak nevezünk, ha
w(x1 ,x 2 ) = (ax1 + bx 2 +e, cx1 + dx 2 + f) alakú, ahol a, b, c, d, e és f valós számok. 15. Definíció: Legyen (X,d) egy metrikus tér. Ekkor egy f:X → X transzformációt kontrakciónak vagy kontrakciós leképezésnek nevezünk, ha ∃ s ∈
, 0 ≤ s < 1 úgy, hogy
6 d(f(x),f(y)) ≤ s ⋅ d(x,y), ∀x,y ∈ X
16. Definíció: Legyen f:X → X transzformáció az (X,d) metrikus tér felett. Ekkor az x f ∈ X elemet, ahol f( x f )= x f , fixpontnak nevezzük.
3. Tétel (A kontrakciós leképezés tétele): Legyen f:X → X kontrakció az (X,d) teljes metrikus tér felett. Ekkor f-nek pontosan egy x f ∈ X fixpontja létezik, mitöbb ∀x ∈ X kezdőelemet választva Lim f o n (x)=x f n →∞
Bizonyítás: Legyen x ∈ X és 0 ≤ s<1 az f függvény kontrakciós eleme. Ekkor d(f o n (x), f o m (x))
∀m,n = 0,1,2,... -re,
kontrakció
ahol
≤
s ⋅ d(f o(n-1) (x),f o(m-1) (x)) ≤ ... ≤ s Min{m,n} ⋅ d(x,f
x∈ X
pillanatnyilag
rögzített.
egyenlőtlenségünk jobboldalán kapott kifejezést. Legyen k ∈
Most
o n-m
)
vizsgáljuk
az
, k= n-m . Ekkor
d(x,f o k (x)) ≤ d(x,f(x))+d(f(x),f o2 (x))+...+d(f o(k-1) , f o k ) ≤
≤ (1 + s+s 2 +...+s k-1 ) ⋅ d(x,f(x)) ≤ ≤ (1 − s) −1 ⋅ d(x,f(x)) és az így kapott egyenlőtlenséget visszahelyezve az előzőbe, kapjuk, hogy d(f o n (x),f o m (x)) ≤ s Min{m,n} ⋅ (1-s) −1 ⋅ d(x,f(x)) , mely összefüggésből, mivel 0 ≤ s<1 , könnyen észrevehető, hogy {f o n (x)}∞n=0 Cauchysorozat. Mivel X teljes metrikus tér ⇒ ∃ x f ∈ X úgy, hogy Lim f o n (x) = x f . n →∞
Most igazoljuk, hogy x f fixpontja az f függvényünknek. Mivel f kontrakció, ezért f folytonos is és így f(x f ) = f( Lim f o n (x)) = Lim f o(n+1) (x) = x f n →∞
n →∞
Bizonyításunkból még hátramaradt igazolni azt, hogy ez a fixpont egyedi. Tegyük fel, hogy fixpontunk nem egyedi, így ∃x f , yf ∈ X , x f ≠ yf x f = f(x f ), y f = f(y f ) és
két különböző fixpont. Ekkor
7 d(x f , y f ) = d(f(x f ), f(yf )) ≤ s ⋅ d(x f ,yf ) amely összefüggés csak akkor teljesülhet, ha d(x f ,y f ) = 0 ⇔ x f = yf . Viszont ez ellentmondás ⇒ az x f ∈ X fixpont egyedi. Ezzel bebizonyítottuk a tételünket.
1. Lemma: ∀ B,C,D,E ∈ H(X) : h(B ∪ C,D ∪ E) ≤ Max{h(B,D),h(C,E)}, ahol h a H(X)-en értelmezett Hausdorff távolság.
2. Lemma: Legyen (X,d) egy metrikus tér és legyen {wn : n = 1,2,…,N} egy {H(X),h} feletti kontrakciókból alló halmaz. Legyen minden wn függvénynek a kontrakciós eleme sn. Definiáljuk a W : H(X)→ H(X) függvényt úgy, hogy N
W(B) = w1 (B) ∪ w2 (B) ∪ ... ∪ wN (B) = U wn (B), ∀B ∈ H(X). n=1
Ekkor W egy kontrakció és kontrakciós eleme s = Max{sn : n=1,2,…,N}. Bizonyítás : Állításunkat bebizonyítjuk N=2 –re és ezután indukcióval egyszerű az általánosítás. Legyen B,C ∈ H(X). Ekkor h(W(B),W(C)) = h(w1 (B) ∪ w2 (B), w1 (C) ∪ w2 (C))
1. Lemma
≤
≤ Max{h(w1 (B),w1 (C)),h(w2 (B),w2 (C))} ≤ ≤ Max{s1h(B,C),s 2 h(B,C)} ≤ s ⋅ h(B,C)
Ezzel igazoltuk az állításunkat N=2 –re. 17. Definíció: Egy (hiperbolikus) iterált függvény rendszer taralmaz egy teljes metrikus teret (X,d) és véges számú kontrakciót wn:X→X, a neki megfelelő sn kontrakciós elemmel, n = 1,2,…,N. Általában IFS -el rövidítjük. Az IFS -nek megfelelő jelölés : {X ; wn, n = 1,2,…,N} és s=Max{sn : n = 1,2,…,N} a hozzátartozó kontrakciós elem. A következő tételünk összesíti a hiperbolikus iterált függvény rendszerek legfőbb tulajdonságait : 4. Tétel: Legyen {X ; wn, n = 1,2,…,N} egy hiperbolikus iterált függvény rendszer s kontrakciós elemmel. Ekkor a W : H(X) → H(X) transzformáció,
8 N
W(B) = U wn (B) , ∀ B∈ H(X) n=1
egy kontrakciós leképezés a (H(X),h(d)) teljes metrikus tér felett, s kontrakciós elemmel. Így h(W(B),W(C)) ≤ s ⋅ h(B,C), ∀ B,C ∈ H(X). Ugyanakkor W-nek létezik egy és csakis egy A∈ H(X) fixpontja, másszóval N
A=W(A)= U wn (A) , n=1
és meghatározható A = Lim W o n (B), ∀B ∈ H(X) módon. n →∞
18. Definició: A 4. tételben szereplő A ∈ H(X) fixpontot az IFS attraktorának nevezzük. Most az előző tételek és értelmezések birtokában térjünk vissza a fraktál interpolációra, és írjuk le a menetét 2 dimenzióban, majd utána két tétel segítségével, mutassuk meg, hogy az elképzelésünk helyes. Ezek után már egyszerű lesz áttérni 3 dimenzióra. Legyen {(xi,Fi) : i = 0,1,2,…,N} egy adott adathalmaz. Feladatunk, hogy szerkesszünk egy IFS -t
2
fölött, melynek attraktora megegyezik egy f :[x 0 , x N ] →
folytonos függvény grafikus képével, amely interpolálja az adatokat. Ennek érdekében figyelmünket leszűkítjük az affin transzformációkra. Értelmezzünk egy {
2
; wn, n = 1,2,…,N } iterált függvény rendszert, amelyben a
leképezések affin transzformációk a következő speciális alakkal : ⎛ x ⎞ ⎛ a n 0 ⎞ ⎛ x ⎞ ⎛ en ⎞ wn ⎜ ⎟ = ⎜ ⎟⎜ ⎟ + ⎜ ⎟ ⎝ y ⎠ ⎝ cn d n ⎠ ⎝ y ⎠ ⎝ f n ⎠
A transzformációt, az adatokra vonatkozóan, a következő kikötésekkel szeretnénk végrehajtani : ⎛ x 0 ⎞ ⎛ x n-1 ⎞ ⎛ xN ⎞ ⎛ xn ⎞ wN ⎜ ⎟ = ⎜ ⎟ és wn ⎜ ⎟ = ⎜ ⎟ , ∀n = 1, 2,..., N , ⎝ F0 ⎠ ⎝ Fn-1 ⎠ ⎝ FN ⎠ ⎝ Fn ⎠
vagyis, azt szeretnénk, hogy az interpolációs adathalmazunk két végpontját, (x0,F0) és (xN,FN), minden affin transzformációs függvényünk a neki megfelelő "intervallum" végpontjaira vigye át. Ezzel biztosítjuk az interpolációs kikötést, jobban mondva azt, hogy
9 a keletkezett grafikon át fog menni az interpolációs pontokon és megfigyelhetjük, hogy a továbblépést - finomítást - is biztosítottuk, mert két "egymás mellett elhelyezkedő" interpolációs pont közötti "területet" újabb részekre bonthatjuk, és az előző algoritmust használhatjuk, végpontoknak tekintve a megfelelő intervallum végpontjait, és interpolációs pontoknak tekintve a részekre bontás után kapott osztópontokat. Legyen n ∈ {1,2,3,…,N}. A wn transzformációt meghatározza az an, cn, dn, en és fn öt valós szám, amelyeknek teljesíteniük kell az alábbi egyenletrenszert : ⎧a n x 0 + e n = x n −1 ⎪a x + e = x ⎪ n N n n ⎨ ⎪c n x 0 + d n F0 + f n = Fn-1 ⎪⎩c n x N + d n FN + f n = Fn
0 ≤ d n < 1, n = 1, 2,..., N
Mivel öt ismeretlenünk van, és csak 4 egyenletünk, így látható, hogy minden transzformációnknál van egy szabad paraméterünk. Válasszuk szabad paraméternek a dn-t, a következő ok miatt: Minden wn transzformáció az y tengellyel párhuzamos egyeneseket y-tengellyel páhuzamos egyenesekbe visz át. Tehát ha L egy y-tengellyel párhuzamos egyenest jelöl, akkor wn( L) ugyancsak egy y-tengellyel párhuzamos egyenes lesz, viszont a wn(L) és L hosszának aránya d n lesz. Ezért az dn paramétert a wn transzformáció vertikális skálázásának is nevezhetjük. Most legyen dn egy tetszőleges valós szám. Ekkor az an, cn, en, fn valós együtthatók mindig kiszámolhatók a dn függvényében:
Jelölje {
2
an =
x n − x n −1 x N − x0
en =
x N x n −1 − x 0 x n x N − x0
cn =
F −F Fn − Fn −1 − dn ⋅ N 0 x N − x0 x N − x0
fn =
x N Fn-1 − x 0 Fn x F − x 0 FN − dn ⋅ N 0 , ∀n = 1, 2,..., N x N − x0 x N − x0
; wn, n = 1,2,…,N } a fennebb definiált iterált függvény rendszerünket. Ha a dn
vertikális skálázóra igaz, hogy 0 ≤ d n < 1, n = 1, 2,..., N még akkor is az IFS általában nem
10 lesz hiperbolikus az (
2
,Euklidész) metrikus tér fölött. Eltekintve ettől, nézzük meg az
algoritmus menetét és vizsgaljuk meg a generált grafikont. 1. Az interpolációs adatok betöltése 2. A di, i = 1,2,…,N , valós értékek megválasztása 3. Az ai, ci, ei, fi, i = 1,2,…,N , értékek kiszámítása a fennebb leírt képlet alapján 4. A kezdő (x,y) páros megválasztása, általában (0,0) 5. A kívánt iterációszám megválasztása 6. Egy véletlenszerű K szám generálása az {1, 2,...., N} halmazból ⎛ újx ⎞ ⎛x⎞ 7. Az ⎜ ⎟ = wK ⎜ ⎟ értékek kiszámítása ⎝ újy ⎠ ⎝ y⎠ ⎛ x ⎞ ⎛ újx ⎞ 8. ⎜ ⎟ = ⎜ ⎟ ⎝ y ⎠ ⎝ újy ⎠ 9. Egy pont kirajzolása az (x,y) pozícióba 10. Ha még nem érte el a kívánt iteráció számot, ugorjon vissza a 6. Lépésre Az algoritmust lefuttatva d1 = 0.5, d2 = -0.5, d3 = 0.23 skálázási értékekre, a fenti ábrán látható
rajzot
kapunk.
Az
algoritmus
többszöri
lefuttatásakor
0 ≤ d n < 1, n = 1, 2,..., N értékekre megfigyelhető, hogy annak ellenére, hogy az 2
különböző {
; wn, n = 1,2,…,N } iterált függvény rendszerünk nem hiperbolikus az euklidészi
metrikával, a függvény rendszernek létezik egy attraktora. Most próbáljuk meg bebizonyítani az előbbi észrevételünket: 5. Tétel: Legyen N egy pozitív, egynél nagyobb egész szám. Jelölje {
2
; wn,
n
= 1,2,…,N } a fennebb említett iterált függvény rendszerünket, összekapcsolva az {(xi,Fi) : i = 0,1,2,…,N} adathalmazzal. Legyen a vertikális skálázó elem dn úgy, hogy 0 ≤ d n < 1, n = 1, 2,..., N . Ekkor ∃d metrika
2
felett, mely ekvivalens az euklidészi
11 metrikával, úgy, hogy az IFS hiperbolikus legyen ezzel a d metrikával. Partikuláris esetben létezik egy és csakis egy nemüres, kompakt G ⊂
2
halmaz, úgy, hogy:
N
G = U wn (G) n =1
Bizonyítás: Szerkesszünk egy d metrikát
2
felett a következő alakkal :
d((x1 , y1 ), (x 2 , y 2 )) = x1 − x 2 + θ y1 − y 2 ,
ahol θ egy pozitív valós szám, melyet a későbbiekben fogunk definiálni. Könnyen igazolható, hogy az általunk így megszerkeztett metrika ekvivalens az euklidészi metrikával
2
-t fölött. Pillanatnyilag rögzítsünk egy n ∈ {1, 2,..., N} egész számot. Az an,
cn, en, fn valós együtthatókat számítsuk ki a fennebb leírt képletek szerint. Ekkor : d(wn (x1 , y1 ), wn (x 2 , y 2 )) = d((a n x1 + en , c n x1 + d n y1 + f n ), (a n x 2 + e n , c n x 2 + d n y 2 + f n )) = = a n x1 − x 2 + θ c n (x1 − x 2 ) + d n (y1 − y 2 ) ≤ ≤ a n x1 − x 2 + θ ( c n (x1 − x 2 ) + d n (y1 − y 2 ) ) ≤ ≤ ( a n + θ c n ) ⋅ x1 − x 2 + θ d n y1 − y 2 Mivel x0 < x1 < x2 < x3 < ... < xN és N ≥ 2, észrevehetjük, hogy a n =
x n − x n-1 < 1 . Ha x N − x0
c1 = c2 = ... = c n = 0 akkor legyen θ = 1 . Máskülönben:
θ=
Min{1 − a n : n = 1, 2,..., N} Max{2 c n : n = 1, 2,..., N}
.
Ekkor d(wn (x1 , y1 ), wn (x 2 , y 2 )) ≤ ( a n + θ c n ) ⋅ x1 − x 2 + θ d n y1 − y 2 ≤ ≤ a x1 − x 2 + θδ y1 − y 2 ≤ ≤ Max{a,δ } ⋅ d((x1 ,y1 ),(x 2 ,y 2 )),
ahol a = (1 + 2
Max{ a n : n = 1, 2,..., N} ) < 1 és 2
δ = Max{ d n : n = 1, 2,..., N}<1 ⇒ ∀n ∈ {1, 2,..., N} wn kontrakció a "d" metrikával
2
fölött ⇒ az IFS hiperbolikus.
12
6. Tétel: Legyen N egy pozitív egynél nagyobb egész szám. Jelölje {
2
; wn,
n
= 1,2,…,N } a fennebb említett iterált függvény rendszerünket, összekapcsolva az {(xi,Fi) : i = 0,1,2,…,N} adathalmazzal. Legyen a vertikális skálázó elem dn úgy, hogy 0 ≤ d n < 1, n = 1, 2,..., N , így az IFS hiperbolikus lesz (5. tétel alapján). Jelölje G az IFS attraktorát. Ekkor G egy f :[x 0 , x N ] →
folytonos függvény grafikus képe lesz, amely
interpolálja {(xi,Fi) : i = 0,1,2,…,N} adathalmazunkat. Másképp: G = {(x, f(x)) : x ∈ [x 0 , x N ]}, ahol f(x i ) = Fi , ∀i = 0,1, 2,3,..., N
Bizonyítás: Jelölje F azt a halmazt, amely tartalmazza az összes folytonos, f :[x 0 , x N ] → alakú függvényt, amely rendelkezik az f(x 0 ) = F0 és f(x N ) = FN tulajdonságokkal. Definiáljunk egy d metrikát az F fölött: d(f,g) = Max{ f(x) − g(x) : x ∈ [x 0 , x N ]}, ∀f,g ∈ Y
Ekkor az (F,d) egy teljes metrikus tér lesz. Most legyenek az an, cn, en, fn valós paraméterek a fennebb említett képlet szerint definiálva és ugyanakkor definiáljunk egy T :F → F leképezést a következőképpen: (Tf)(x) = c n I −n1 (x) + d n f(I −n1 (x)) + f n , ∀x ∈ [x n −1 , x n ], ∀n = 1, 2,..., N , ahol I n :[x 0 , x N ] → [x n −1 , x n ] egy invertálható transzformáció I n (x) = a n x + e n alakkal. Ellenőrizzük le, hogy a T leképezésünk F-et önmagába viszi át. Legyen f ∈ F-nek. Ekkor (Tf)(x 0 ) = c1I1−1 (x 0 ) + d1f(I1−1 (x 0 )) + f1 = c1x 0 + d1f(x 0 ) + f1 = c1x 0 + d1F0 + f1 = F0 és (Tf)(x N ) = c N I−N1 (x N ) + d N f(I −N1 (x N )) + f N = c N x N + d N f(x N ) + f N = c N x N + d N FN + f N = FN
⇒ a T leképezés az f függvényt, egy olyan függvénybe viszi át, amely teljesíti a végpontokra kiszabott feltételt: (Tf)(x0) = F0, (Tf)(xn) = FN. Hátramaradt, hogy igazoljuk, hogy a (Tf)(x) folytonos az [x 0 , x N ] intervallumon. Mivel a Tf függvény szerkesztésében egy adott [x n −1 , x n ] intervallumon folytonos függvények szerepelnek, és ezekkel a folytonosságot megőrző műveleteket végzünk, így
13 könnyen belatható, hogy a (Tf)(x) is olytonos az [x n −1 , x n ] intervallumon, ∀n = 1, 2,..., N re. Még bebizonyításra vár a (Tf)(x) folytonossága az x1 , x 2 , x 3 ,..., x N −1 osztópontokban. Ehhez kiszámítjuk a (Tf)(xn) értékét kétéleképpen ∀n = 1, 2,..., N : (Tf)(x n ) = c n +1I −n1+1 (x n ) + d n +1f(I −n1+1 (x n )) + f n +1 = c n +1x 0 + d n +1f(x 0 ) + f n +1 = Fn (Tf)(x n ) = c n I n−1 (x n ) + d n f(I −n1 (x n )) + f n = cn x N + d n f(x N ) + f n = Fn Látható, hogy mind a két oldalról a függvény értéke megegyező, így a (Tf) függvényünk folytonos ezekben a pontokban is. Így kimutattuk, hogy a T leképezés az F teret az F térre képezi le. Most mutassuk ki, hogy a T egy kontrakció (F,d) metrikus tér felett. Legyen f,g ∈ F és pillanatnyilag rögzítsünk egy n ∈ {1, 2,..., N} számot. Legyen x ∈ [x n −1 , x n ] . Ekkor −1 n
−1 n
(Tf)(x)-(Tg)(x) = d n ⋅ f(I (x)) − g(I (x))
In−1 szürjektív
≤
d n ⋅ d(f,g)
és így d(Tf,Tg) ≤ δ d(f,g) ahol δ = Max{ d n : n = 1, 2,..., N} < 1
Innen már látható, hogy a T:F → F egy kontrakció. A kontrakciós leképezés tétele
(3.
tétel) alapján T-nek létezik egy és csakis egy fixpontja F-ben. Másszóval létezik egy f ∈ F úgy, hogy (Tf)(x) = f(x), ∀x ∈ [x 0 , x N ] . Az függvényünk átmegy az interpolációs pontokon. Legyen G az f függvény grafikonja. Észrevehető, hogy a T definíciójában szereplő kiejezés átírható az alábbi formába: (Tf)(a n x + en ) = cn x + d n f(x) + f n , ∀x ∈ [x 0 , x N ], ∀n = 1, 2,..., N amiből következik, hogy N
G = U wn (G) n =1
De a G egy nemüres, kompakt részhalmaza
2
-nek. Az előző tétel (5. tétel) alapján egy és
csakis egy kompakt, nemüres G halmaz létezik, az IFS attraktora, amely teljesíti a fenti egyenletet. Ezért G = G . Ezzel bebizonyítottuk a tételünket.
14
19. Definíció: Azt a függvényt, amelynek grafikus képe az IFS attraktora (mint ahogy az 5. és 6. tétel mutajta), az {(x i , Fi ) : i = 1, 2,..., N} adatokhoz tartozó, fraktál interpolációs függvénynek nevezzük. A tételeink után, melyek bizonyítják azon észrevételünket, hogy létezik egy attraktor és ugyanakkor létezik egy f fraktál interpolációs függvény, térjünk át a három dimenziós esetre. Legyenek N, M ∈
természetes számok, és legyenek x 0 < x1 < ... < x N , y 0 < y1 < ... < y M ,
valós értékű osztópontok. Legyen {(x n , y m , z n,m ) ∈
3
, n = 0,1, 2,..., N, m = 0,1, 2,..., M}
ponthalmaz az interpolációs adathalmazunk. Feladatunk ismét egy olyan folytonos f:[x 0 , x N ] × [y0 , y M ] →
függvény meghatározása, melyre teljesül az interplációs feltétel,
vagyis f(x n , y m ) = z n,m , n = 0,1, 2,..., N, m = 0,1, 2,..., M . Most értelmezzünk φn :[x 0 , x N ] → [x n −1 , x n ] , ψ m :[y0 , y N ] → [y n −1 , y n ] , n ∈ {1,2,...,N} , m ∈ {1,2,...,M} kontrakciókat, melyek teljesítik az alábbi követelményeket:
⎧φn (x 0 ) = x n −1 , φn (x N ) = x n ⎪ψ (y ) = y , ψ (y ) = y n −1 n N n ⎪ n 0 , ⎨ ⎪ φn (c1 ) − φn (c 2 ) < k1 c1 − c 2 ⎪ ⎩ψ n (d1 ) −ψ n (d 2 ) < k 2 d1 − d 2 ahol c1 , c 2 ∈ [x 0 , x N ] , d1 , d 2 ∈ [y0 , y M ] és 0 ≤ k1 < 1, 0 ≤ k 2 ≤ 1 . Legyen ezen kontrakciók alakja φn (x) = a n x + b n és ψ m (x) = c m x + d m . Mivel függvényeinket úgy definiáltuk, hogy teljesítsék a fennebbi követelményeket, kiszámíthatók az együtthatók, így kapjuk, hogy x n − x n −1 ⎧ ⎪a n = x − x ⎪ N 0 , ⎨ ⎪b = x n −1x N − x n x 0 ⎪⎩ n x N − x0 illetve
15 y m − y m −1 ⎧ ⎪c m = y − y ⎪ M 0 . ⎨ − y y y y m 1 M m 0 − ⎪d = ⎪⎩ m yM − y0 Legyen Fn,m :[x 0 , x N ] × [y0 , y M ] ×
→
folytonos függvény, mely teljesíti az alábbi négy
tulajdonságot:
⎧Fn,m (x 0 , y 0 , z 0,0 ) = z n −1,m −1 ⎪ ⎪Fn,m (x N , y0 , z N,0 ) = z n,m −1 , ⎨ F (x , y , z ) z = n,m 0 M 0,M n 1,m − ⎪ ⎪F (x , y , z ) = z n,m ⎩ n,m N M N,M és ∀(x1, y1 ), (x 2 , y 2 ) ∈ [x 0 , x N ] × [y0 , y M ] , ∀z1 , z 2 ∈
:
Fn,m (x1 , y1 , z1 ) − Fn,m (x 2 , y 2 , z 2 ) ≤ k 3 z1 − z 2 , n ∈ {1, 2,..., N},m ∈ {1,2,...,M},0 ≤ k 3 < 1. Legyen az Fn,m függvény alakja Fn,m (x,y,z) = en,m x + f n,m y + g n,m xy + α n,m z + k n,m . Így definiálva függvényünket, a tulajdonságaival összevetve, felírhatunk négy egyenletet:
⎧z n −1,m −1 = en,m x 0 + f n,m y0 + g n,m x 0 y 0 + α n,m z 0,0 + k n,m ⎪ ⎪z n,m −1 = en,m x N + f n,m y 0 + g n,m x N y0 + α n,m z N,0 + k n,m . ⎨ ⎪z n −1,m = en,m x 0 + f n,m y M + g n,m x 0 y M + α n,m z 0,M + k n,m ⎪z = e x + f y + g x y + α z + k n,m N n,m M n,m N M n,m N,M n,m ⎩ n,m Látható, hogy négy egyenletünk van minden Fn,m függvényre és öt együtthatónk, így az egyiket megválasszuk szabad paraméternek. Legyen ez a szabad paraméter az α n,m , mégpedig úgy, hogy 0 ≤ α n,m < 1, n ∈ {1,2,...,N},m ∈ {1,2,...,M} . Ezt a paramétert vertikális skálázónak nevezzük, akárcsak két dimenziós esetben. Rögzítve szabad paraméterünket, ki tudjuk számolni a függvények együtthatóit, amelyek a következők lesznek:
16 z n −1,m −1 − z n −1,m − z n,m −1 + z n,m − α n,m (z 0,0 − z N,0 − z 0,M + z N,M ) ⎧ ⎪g n,m = x 0 y0 − x N y0 − x 0 y M + x N yM ⎪ ⎪ z n −1,m −1 − z n,m −1 − α n,m (z 0,0 − z N,0 ) − g n,m (x 0 y 0 − x N y 0 ) ⎪e n,m = x0 − x N ⎨ ⎪ z −z − α n,m (z 0,0 − z 0,M ) − g n,m (x 0 y 0 − x 0 y M ) ⎪f n,m = n −1,m −1 n −1,m y0 − yM ⎪ ⎪ ⎩k n,m = z n,m − e n,m x N − f n,m y M − α n,m z N,M − g n,m x N y M Most szerkesszünk egy új G n,m (x,y,z) függvényt, a következő alakkal: ⎧1 ⎪ 2 (Fn,m (x,y,z) + Fn +1,m (x 0 ,y,z)), ha x = x n ; n = 1, 2,..., N − 1; m = 1, 2,..., M ⎪ ⎪1 G n,m (x,y,z) = ⎨ (Fn,m (x,y,z) + Fn,m+1 (x,y 0 , z)), ha y = yM ; n = 1, 2,..., N;m = 1, 2,..., M − 1 . ⎪2 ⎪Fn,m (x,y,z), máskülönben ⎪ ⎩
Definiáljunk egy {
3
; Wn,m , n = 1, 2,..., N, m = 1, 2,..., M} alakú iterált függvény rendszert,
ahol Wn,m :[x 0 , x N ] × [y 0 , y M ] ×
→
3
,
Wn,m (x,y,z) = {φn (x),ψ m (y),G n,m (x,y,z)}, n = 1, 2,..., N; m = 1, 2,..., M. Az így keletkezett iterált függvényrendszerről, a két dimeneziós esethez hasonlóan bebizonyítható, hogy létezik egyetlen G attraktora, amely egy folytonos f függvény grafikus képe úgy, hogy
G = {(x,y,f(x,y)) : (x,y) ∈ D} továbbá f(x n , y m ) = z n,m ; n = 0,1,..., N, m = 0,1,..., M . Megjegyzésként megemlíteném, hogy ha csak G n,m (x,y,z) = Fn,m (x,y,z) egyenlőséget vennénk, akkor a keletkezett felület több, egymáshoz nem illeszkedő felületdarabkából állna (minden darab az [x n −1 , x n ] × [y m −1 , y m ], n = 1, 2,..., N; m = 1, 2,..., M térség fölött elhelyezkedő felület lenne). Illetve pontosítva az előző kijelentésem, a felületek a megadott interpolációs pontokban találkoznának, viszont az ezeken kívül eső felület oldalain nem lennének folytonosak. Ezért minden pontot a felület széléről átlagolok a vele összekapcsolandó másik felület megfelelő pontjával.
17 Egy másik módszer három dimenziós fraktálinterpolációra, ha az interpolációs adathalmazunk {(x i , y j , z i,j ) ∈
3
; i = 1,..., N, j = 1,...,i} alakú, melyen látható, hogy egy
háromszög alakú síkrészt osztottunk fel és ezekhez csatolunk egy harmadik értéket, ami az osztópontoknak
meg-
felelő térbeli magasság lesz. Ezúttal definiálni fogunk egy affin transzformációt úgy, hogy a nagyháromszög csúcspontjait rendre
az
osztópontok
által létrehozott háromszögek
csúcspontjaira
transzformálja (ahogy az ábrán is látható). Vigyázni kell, hogy megfelelő csúcsot megfelelő csúcsba transzformáljunk, mivel látható, hogy vannak fordított háromszögek is. Tehát akkor szerkesszük meg affin transzformációnkat a következő képpen: ⎛ x ⎞ ⎛ a n b n 0 ⎞ ⎛ x ⎞ ⎛ t1n ⎞ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ wn ⎜ y ⎟ = ⎜ d n e n 0 ⎟ ⎜ y ⎟ + ⎜ t2n ⎟ , ⎜ z ⎟ ⎜ g h i ⎟ ⎜ z ⎟ ⎜ t3 ⎟ ⎝ ⎠ ⎝ n n n ⎠⎝ ⎠ ⎝ n ⎠
ahol 0 ≤ i n < 1 . Ezekből az affin transzformációkból képezhető az {
3
; wn , n = 1, 2,..., N}
iterált függvény rendszer. Az együtthatók kiszámolhátóak a megfeleltetési szabályokból, és a két dimenziós esethez hasonlóan itt is igazolható, hogy létezik egy attraktor, és egy neki megfelelő folytonos függvény, melynek grafikus képe az attraktor és amely átmegy az interpolációs pontokon. Itt már nincs szükség átlagolásra a háromszögek csatlakozásánál, mert a transzformációm affin, és háromszögű tartomanyokkal dolgozunk.
18
Perlin zaj A perlin zaj egy procedurális minta és textúra generátor, melyet vizuális effektek generálására használnak, ezzel növelve a megjelenítések valósághűségét a számítógépes grafikákban. Fennebb már említettem, hogy a valóság ábrázolásához, eszközeinket nem szűkíthetjük le csupán az elemi függvények használatára, szükségünk van valamire, amely képes végtelen részletekig hatolni, és ugyanakkor magában hordozza természetünk “véletlenszerűségét”. A Perlin zaj fraktálokon alapszik, mely tartalmazza az előbb említett tulajdonságokat. Felhasználhatjuk domborzatok generálására, a víz mozgásának, az ég változásának szimulálására, és számos más területen. Programomban, miután a fraktál interpolációval domborzatot hoztam létre, Perlin zajt használtam az ég generálására. Ehhez f:
n
először
is,
szükségünk
van,
egy
úgynevezett
zajfüggvényre,
→ [−1, +1] , amely egy egész számokban csomópontokat képző rácshoz igazított
pseudo-random interplációs függvény, ami a véletlenszerűség hatását kelti, de ugyanakkor rendelkezik azzal a tulajdonsággal, hogy azonos bemeneti értékekre, azonos függvény értékeket térít vissza. N-dimenziós térben definiáltuk a zajfüggvényünket, de az egyszerűség kedvéért a továbbiakban két dimenzióban dolgozom (egy dimenzió-animáció, két dimenzió-egyszerű textúrák, három dimenzió-bonyolultabb textúrák). Most lássuk, hogyan is viselkedik a zajfüggvényünk egy (x,y) ∈
2
bemeneti adatra. Kiszámítjuk a
pontot körülvevő rácspontok koordinátáit (a rácspontok egész számok lesznek), és minden így kapott pontnak kiválasztunk egy neki megfelelő pseudo-random értéket egy előre definiált halmazból. Ezek után az (x,y) pontnak megfelelő pontos értéket úgy kaphatjuk meg, hogy interpolálunk az így megkapott rácspontokhoz rendelt értékek között. Azt, hogy milyen interpolációt használjunk, azt a kívánt eredmény símasága, finomsága dönti el. Lineáris interpoláció esetén a leggyorsabb a generálás, viszont a textúra símaságának elromlásába kerül, ezért ezt elvetettem. Amit választottam az a koszinusz interpoláció, sokkal jobb eredményt ad mint a lineáris és sebességét tekinteve is elfogadható , melyet a következő képpen valósíthatunk meg:
19
Koszinusz_Interpolació(a, b, t) f = (1 − cos(t ⋅ π )) ⋅ 0.5 visszatérés = a ⋅ (1 − f ) + b ⋅ f vége
Nagyon jó símasághoz vezet, ha köbös interpolációt használunk, de a program gyorsaságával fizetünk érte, és nem vagyok biztos benne, hogy az emberi szemnek említésre méltó különbséget okozna. Egy nagyon jó finomítás, ha az előre definiált pseudo-random számokból alló halmazunkat úgy építjük fel, hogy minden elemnél figyelembe vesszük a szomszédait (beleértve átlósan is), így az árnyalati különbség elem és szomszédja között csökken. Ezzel már láttuk, hogy hogyan is működik a zajfüggvényünk, ezek segítségével generálhatjuk a Perlin alapú fraktál függvényeket. Jellemző rájuk az amplitudó (a fraktálfüggvény maximuma és minimuma közötti különbség), frekvencia. Kiválasztva egy iterációszámot,
folyamatosan
generálhatunk
fraktálfüggvényeket,
különböző
paraméterekkel (különböző amplitúdó illetve frekvencia). Ezeket fraktálösszegbe írva minden iterációban új adatot vihetünk be, melyek befolyásolják a végső értéket. Az egyszerűség kedvéért, az az i-edik iterációban ( 0 ≤ i < max_ iterációszám) szereplő fraktálfüggvényünk jellemzőit egyetlen értékkel fogjuk meghatározni - jelöljük ezt
p -vel - a következő módon : frekvencia = 2i amplitudó = p i ,
ami azt jelenti, hogy a frekvencia minden iterációval nő (a fraktálfüggvényünk "rezgései" egyre sűrűsödnek) és
p < 1 esetén az amplitudó (vagyis a rezgések "nagysága")
folyamatosan csökken, tart a nullába. Ezeket összevetve észrevehetjük, hogy ha p → 0 , akkor a fraktál összeg nagyon síma lesz, viszont ha p → 1 akkor a fraktálösszeg nagyon szabálytalan. Még hátramaradt, hogy megnézzük, hogyan alakítottam át a kapott [−1, +1] intervallumban szereplő értéket színné (felhőhöz fehér és kék közötti árnyalatra volt szükségem). Szükségünk van egy g :[−1, +1] → {0,1,..., 255} egész értéket visszatérítő
20 függvényre, amely szabályozza a kék szín erősségét. Ezért definiáljuk a g függvényünket a következőképpen: , ha x ≤ 0 ⎧⎪0 g(x) = ⎨ x ⎢ ⎥ ⎩⎪ ⎣ (1 − sharpness ) ⋅ 255⎦ , máskülönben. Bevezettem egy sharpness ∈ (0,1) értéket, mely segítségével eponenciálisan tudom kezelni a fehér és kék közötti átmenetet (felhőknél megfigyelhető, hogy a fehérség nem lineárisan tünik el, hanem exponenciálisan) és ugyanakkor egy paraméterként szolgáll, amellyel állíthatom az átmenet gyorsaságát. Minden színt meghatároz egy piros, egy zöld és egy kék színkomponens. Ha mind a három színkomponens értéke magas akkor kapunk fehér színt, viszont ha az első kettő alacsony, és csak a kék magas, akkor kapunk kék színt. Ezt kihasználva, ha a komponenseket piros = g(f(x,y)) zöld = g(f(x,y)) kék = 255
módon állítjuk be, akkor f(x,y) negatív vagy nullához közeli értékére kéket fogunk kapni, f(x,y) egyhez közeli értékére fehéret kapunk (itt feltételeztem, hogy a sharpness elég kicsi). Legvégül nézzük meg, hogyan "mozgattam" a felhőket, vagy hogyan keltettem azt az érzést, hogy mozognak. Eleinte hozzunk létre az előzőekben említett módszerrel több pszeudó-random elemekből felépített halmazt úgy, hogy a halmazok elemei eltérőek legyenek. Ezutan generáljuk a fraktálösszegünket különböző p ∈ (0,1] paraméterekre, majd számoljuk ki a színeket és építsük fel a szükséges textúrákat. Ekkor vezessük be az idő fogalmát egy t ∈ [0,1] paraméterrel, amely kezdetben legyen 0. A t paraméter egy lineáris interpolációban fog segédkezni, két véletlenszerűen kiválasztott textúra között. A t -t növeljük az idő függvényében és (1 − t ) ⋅ textura1 + t ⋅ textura2 képlettel folyamatosan összemossuk, így mozgáshoz hasonló animációt kapunk. Mikor a t változónk eléri az 1 maximális értéket, akkor a textura1 felveszi a textura2
értékét, véletlenszerűen
kiválasztunk egy új textura2 -t, és a t változónk értékét nullává tesszük, és minden kezdődhet előlről.
Könyvészet
21
1. Michael Barnsley – Fractals everywhere 2. Heping Xie and Hongquan Sun – The study on bivariate fractal interpolation functions and creations of fractal interpolated surfaces (received July 1, 1997; Accepted August 21, 1997 3. Jacques Levy Vehel, André Gagalowicz – Fractal approximation of 2-D object 4. Craig M. Wittenbrink – IFS Fractal Interpolation for 2D and 3D Visualization 5. Perlin noise: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm 6. Valós idejű procedurális domborzatmodellezés Perlin zajjal – Dr. Soós Anna, Dr. Szenkovits Ferenc, Osváth-Boros Róbert (Május 17, 2005)
