Tartalom
Sz´am´ıt´og´epes Grafika Valasek G´abor
[email protected] E¨ otv¨ os Lor´ and Tudom´ anyegyetem Informatikai Kar
2015/2016. ˝ oszi f´el´ev
Rekurz´ıv sug´ark¨ovet´es
Rekurz´ıv sug´ark¨ovet´es Megjegyz´esek
Sug´ark¨ ovet´es gyors´ıt´asa Befoglal´o keretek
T´erfeloszt´o elj´ar´asok Feloszt´asok
Rekurz´ıv sug´ark¨ovet´es
Rekurz´ıv sug´ark¨ovet´es - ´arny´ek sug´ar
Rekurz´ıv sug´ark¨ovet´es
Rekurz´ıv sug´ark¨ovet´es - ide´alis visszaver˝od´es
Rekurz´ıv sug´ark¨ovet´es - ide´alis t¨or´es
Rekurz´ıv sug´ark¨ovet´es - rekurzi´o
Rekurz´ıv sug´ark¨ovet´es Minden pixelre egym´ast´ol f¨ uggetlen¨ ul hat´arozzuk meg azok sz´ın´et – oldjuk meg az ´arnyal´asi ´es takar´asi feladatokat.
Turner Whitted, 1980
Koherens komponens
I
A f´eny u ´tj´at k´etf´ele komponensre bontjuk: I
Koherens komponens: I
I I
Az optik´ anak megfelel˝ o ide´ alis visszaver˝ od´es (”t¨ ukr¨ oz˝ od´es”) ´es t¨ or´es Tov´ abb k¨ ovetj¨ uk a f´eny u ´tj´ at
Inkoherens komponens: I I
Minden egy´eb Csak az absztrakt f´enyforr´ as direkt megvil´ ag´ıt´ as´ at vessz¨ uk figyelembe
Inkoherens komponens
Jel¨ol´es
Egyszer˝us´ıtett illumin´aci´os egyenlet
A k¨ovetkez˝o, egyszer˝ us´ıtett megvil´ag´ıt´asi egyenletet oldjuk meg: L(x, ω) = Le (x, ω) + ka · La +
X
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
l∈Lights
+ kr · L(xr , ωr ) + kt · L(xt , ωt )
I
K´et vektor skal´ar szorzat´at az egyszer˝ us´eg kedv´e´ert most a · b-vel fogjuk jel¨olni
I
Az ir´anyok jel¨ol´es´ere ω, ω 0 stb. bet˝ uket haszn´aljuk, de ezek tov´abbra is egys´eghossz´ u vektorok, azaz ω ∈ R3 : |ω| = 1
Sug´ark¨ovet´es
L(x, ω) = Le (x, ω) + ka · La +
Emisszi´o
X
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
l∈Lights
+ kr · L(xr , ωr ) + kt · L(xt , ωt )
L(x, ω) = Le (x, ω) + ka · La +
X
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
l∈Lights
Az x fel¨ uleti pontb´ ol az ω ir´anyban kibocs´atott radiancia I
A szempoz´ıci´ ob´ ol sugarakat ind´ıtunk minden pixelen kereszt¨ ul (p´eld´aul a pixel k¨ oz´eppontj´an ´at)
I
A sugarak ir´any´at −ω-val jel¨ olj¨ uk (minusz omega!)
I
A sug´ar ´es a sz´ınt´er objektumainak szemhez legk¨ozelebbi metsz´espontja adja meg x-et
Ambiens f´eny
L(x, ω) = Le (x, ω) + ka · La +
+ kr · L(xr , ωr ) + kt · L(xt , ωt ) Ez a tag a fel¨ ulet saj´at sug´arz´as´at – emisszi´oj´at – ´ırja le az x fel¨ uleti pontb´ol az ω ir´anyba
F´enyforr´asok
X
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
L(x, ω) = Le (x, ω) + ka · La +
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
l∈Lights
l∈Lights
+ kr · L(xr , ωr ) + kt · L(xt , ωt )
+ kr · L(xr , ωr ) + kt · L(xt , ωt ) ka a fel¨ ulet, La a k¨ ornyezet ambiens egy¨ utthat´oja. Az egyenlet ambiens tagja k¨ ozel´ıti azt a f´enymennyis´eget, ami ´altal´anosan jelen van, minden fel¨ uletet ´er, azok helyzet´et˝ol ´es az absztrakt f´enyforr´asokt´ ol f¨ uggetlen¨ ul.
X
I
A figyelembe vett inkoherens visszaver˝od´eseket foglalja ¨ossze a szumm´as tag
I
Csak a f´enyforr´asok direkt hat´as´at vessz¨ uk figyelembe ´ csak akkor, ha az az x fel¨ Es uleti pontb´ol l´atszik
I
F´enyforr´asok
F´enyforr´asok
L(x, ω) = Le (x, ω) + ka · La +
X
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
L(x, ω) = Le (x, ω) + ka · La +
+ kr · L(xr , ωr ) + kt · L(xt , ωt )
+ kr · L(xr , ωr ) + kt · L(xt , ωt )
ωl a f´enyforr´asb´ ol a fel¨ uleti pontba mutat´o egys´egvektor.
I
fr (x, ωl , ω) most csak a diff´ uz ´es spekul´aris visszaver˝od´est jellemz˝o BRDF.
I
−ωl · n a fel¨ uleti norm´alis ´es a f´enyforr´as fele mutat´o vektor ´altal bez´art sz¨ og koszinusza.
F´enyforr´asok - n´egyzetes elhal´as Mi´ert a metsz´espont ´es a f´enyforr´as t´avols´ag´anak n´egyzet´evel osztunk?
I
Tekints¨ unk egy pontszer˝ u f´enyforr´ast, ami minden ir´anyban egyenletesen sug´aroz L radianci´at Egyre t´avolodva t˝ ole, a pontszer˝ u f´enyforr´as k¨or´e ´ırt g¨omb¨on n´egyzetcentim´eterenk´ent mennyi f´enyt m´ern´enk? radiancia osztva a t´avols´aghoz tartoz´ o g¨ omb fel¨ ulet´evel, azaz Lr =
I
L 4πr 2
Teh´at k´et k¨ ul¨ onb¨ oz˝ o t´avols´agban m´ert f´enymennyis´eg ar´anya Lr1 = Lr2
I
Ha az l f´enyforr´as teljes´ıtm´enye Φl ´es pozici´oja xl akkor Li (x, ωl ) = v (x, xl ) ·
I
Φl . kx − xl k2
v (x, xl ) ∈ [0, 1] f¨ uggv´eny: Mi van a fel¨ uleti pont ´es a f´enyforr´as k¨oz¨ott?
F´enyforr´asok
I
I
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
l∈Lights
l∈Lights
I
X
r12 r22
L(x, ω) = Le (x, ω) + ka · La +
X
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
l∈Lights
+ kr · L(xr , ωr ) + kt · L(xt , ωt ) v (x, xl ) ∈ [0, 1] f¨ uggv´eny I
= 0, ha a f´enyforr´as nem l´athat´o x-b˝ol,
I
= 1, ha igen,
I
∈ (0, 1), ha ´atlatsz´o objektumok vannak a kett˝o k¨oz¨ott.
I
v kisz´am´ıt´as´ahoz u ´gynevezett ´arny´eksugarat ind´ıtunk x-b˝ol xl -fele, ´es az objektumokkal val´o metsz´es´et n´ezz¨ uk.
T¨ukr¨oz˝od´es
L(x, ω) = Le (x, ω) + ka · La +
F´enyt¨or´es
X
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
L(x, ω) = Le (x, ω) + ka · La +
+ kr · L(xr , ωr ) + kt · L(xt , ωt )
+ kr · L(xr , ωr ) + kt · L(xt , ωt )
A t¨ uk¨orir´anyb´ ol ´erkez˝ o f´enyt kr ar´anyban vessz¨ uk figyelembe.
I
ωr az ide´alis t¨ uk¨ orir´anynak megfelel˝ o bees˝o vektor.
I
Az xr az x-b˝ ol indul´ o, −ωr ir´anyvektor´ u sug´ar legk¨ozelebbi metsz´espontja sz´ınt´erbeli elemmel.
I
L(xr , ωr ) kisz´am´ıt´asa azonos L(x, ω) kisz´am´ıt´as´aval (rekurzi´o!). ´ sug´ar: szempoz´ıci´ Uj o helyett x-b˝ ol indul, ir´anya −ωr .
I
fr (x, ωl , ω)Li (x, ωl )(−ωl · n)
l∈Lights
l∈Lights
I
X
I
A t¨or´esi-ir´anyb´ol ´erkez˝o f´enyt kt ar´anyban vessz¨ uk figyelembe.
I
ωt a t¨or´esir´anynak megfelel˝o bees˝o vektor.
I
Az xt az x-b˝ol indul´o, −ωt ir´anyvektor´ u sug´ar legk¨ozelebbi metsz´espontja sz´ınt´erbeli elemmel.
I
L(x, ωt ) kisz´am´ıt´asa megint azonos L(x, ω) kisz´am´ıt´as´aval (rekurzi´o!). ´ sug´ar: szempozici´o helyett x-b˝ol indul, az ir´anya pedig Uj −ωt .
I
Megjegyz´es
Megjegyz´es - ¨on´arny´ekol´as
I
A numerikus pontatlans´agok miatt el˝ ofordulhat, hogy a metsz´espont val´ oj´aban kiss´e a testen bel¨ ul van
I
Ilyenkor a f´enyforr´asok fel´e l˝ ott sugarak bele¨ utk¨ozhetnek a kiindul´asi fel¨ uletbe!
I
Vagy hagyjuk ki a metsz´essz´am´ıt´asokb´ ol a legut´obb metszett objektumot (ahonnan indulunk), vagy toljuk el a sug´ar kezd˝opontj´at norm´alis ir´any´aban
I
Figyelj¨ unk arra is, hogy mi is kell pontosan: a metsz´espont helye(i) vagy el´eg-e maga a metsz´es t´enye?
Megjegyz´es - aliasing
Megjegyz´es - aliasing
I
Egyenk¨oz˝ u pontonk´enti mintav´etelez´est csin´alunk l´enyeg´eben → a mintav´etelez´esi frekvenci´an´al gyorsabb v´altoz´asok alias-olnak, azaz nem l´etez˝o, alacsonyabb frekvenci´as jelkomponensk´ent regisztr´aljuk ˝oket
Megjegyz´es - aliasing
Megjegyz´es - aliasing
Mintav´etelez´es grafik´aban
Mintav´etelez´es grafik´aban - alias
Mintav´etelez´es grafik´aban - alias
I
Eddig csak pixelenk´ent (”ablakonk´ent”) egyetlen sugarat ind´ıtottunk csak
I
Ha t¨obbet ind´ıtunk, akkor a Nyquist frekvencia n˝o
I
Pixelenk´ent egy sz´ın kell csak → a sugarak ´altal behozott k¨ ul¨onb¨oz˝o sz´ıneket ¨osszegezni kell valahogy (pl. ´atlagolni)
I
De a t¨obb sug´ar eredm´eny´et is t¨obbf´elek´eppen ¨osszegezhetj¨ uk (vagyis: sz˝ urhetj¨ uk)
Mintav´etelez´es grafik´aban - alias
I
I
Egyenletes mintav´etelez´essel az alias nem sz¨ untethet˝o meg (csak ha a bej¨ ov˝ o jel garant´altan nem tartalmaz t´ ul magas frekvenci´as komponenseket) Azonban ha nem egyenletes a mintav´etelez´es, hanem megfelel˝o eloszl´as szerint t¨ ort´enik, akkor az alias helyett v´eletlenszer˝ u, nagyfrekvenci´as zaj lesz a k´epen
Megjegyz´es
I
Vegy¨ uk ´eszre: a f´enyt fent v´egig r´eszecskek´ent kezelt¨ uk
I
Emiatt a f´eny hull´am term´eszet´eb˝ol ad´od´o jelens´egeket (interferencia, diffrakci´o stb.) nem tudjuk visszaadni Ezek sz´am´ıtanak:
I
I
I
I
Ehhez a szem¨ unk m´ar alkalmazkadott!
Metsz´esvizsg´alat gyors´ıt´asa - motiv´aci´o
I
Az algoritmus sebess´ege legink´abb a metsz´esvizsg´alat sebess´eg´et˝ol f¨ ugg.
Az interferencia miatt l´atjuk olyan sz´ınben a p´ava tollait vagy a szappanbubor´ek felsz´ın´et amilyenben l´atjuk A diffrakci´o pedig a finom ´arny´ekjelens´egek egy r´esz´eben j´atszik szerepet
Befoglal´o keretek
I
Minden objektumot vegy¨ unk k¨orbe valamilyen kerettel amivel gyorsan lehet metsz´est sz´amolni.
I
Ha egy sug´ar metszi az objektumot, akkor biztosan metszi a keretet is!
I
Hogyan gyors´ıthatn´ank ezt?
I
Ne vizsg´aljunk metsz´est olyan objektumokra, amiket biztosan nem metsz a sug´ar!
I
Ford´ıtva is legyen min´el nagyobb a val´osz´ın˝ us´ege! (Min´el jobban k¨ozel´ıtse a befoglal´o test az igazit)
I
Ne vizsg´aljunk metsz´est olyan objektumokra, amik biztosan t´avolabbi metsz´espontot adnak, mint a m´ar megtal´alt!
I
Befoglal´o g¨omb: m´asodfok´ u egyenlet megold´as.
I
Befoglal´o doboz: ´elei a tengelyekkel p´arhuzamosak, Cohen-Sutherland szakaszv´ag´o algoritmussal gyorsan sz´am´ıthat´o, l´asd el˝oz˝o el˝oad´as!
Tov´abbi befoglal´ok - konvex poli´ederek
Tov´abbi befoglal´ok - konvex poli´ederek
I
Egy n-oldal´ u konvex poli´ederek fel´ırhat´o n f´elt´er metszetek´ent (f´elt´er: ax + by + cz + d ≤ 0)
I
Azaz az oldallapok s´ıkjait kifel´e mutat´o norm´alisokkal fel´ırhatjuk ai x + bi y + ci z + di = 0 , i = 1.., n alakban
Sug´ar metsz´ese konvex poli´ederrel
1. Legyen tnear := −∞, tfar := ∞ 2. Minden i ∈ {1, 2, .., n} oldallapra: legyen a lap ai x + bi y + ci z + di = 0, egyenlete olyan, hogy az ni = [ai , bi , ci ]T lapnorm´alis a poli´ederb˝ol kifel´e fel´e mutat 2.1 Sz´am´ıtsuk ki a sug´ar ´es az oldallap s´ıkj´anak ti metsz´espontj´at 2.2 Ha v · ni < 0, akkor tnear := max{tnear , ti } 2.3 K¨ ul¨ onben tfar := min{tfar , ti }
3. Ha tnear > tfar , akkor nincs metsz´espont 4. K¨ ul¨ onben a sug´ar egyenese tnear -n´el l´ep be ´es tfar -n´al hagyja el a konvex poli´edert (azaz metszi a sug´ar a konvex poli´edert, ha [tnear , tfar ] ∩ R+ 6= ∅)
I
A kor´abban l´atott sug´ar-AAB metsz´es k¨onnyen ´altal´anos´ıthat´o erre az esetre!
I
Legyen a sug´ar p(t) = p0 + tv
Befoglal´o dobozok haszn´alata
Befoglal´o dobozok haszn´alata
Hierachikus befoglal´o keretek
Hierachikus befoglal´o keretek
I
A kisebb kereteket nagyobb keretekbe fogjuk ¨ossze.
I
Fa strukt´ ur´at kapunk.
I
Egy r´eszf´at csak akkor kell ki´ert´ekelni, ha a gy¨ok´errel van metsz´es.
Hierachikus befoglal´o keretek
Hierachikus befoglal´o keretek
Szab´alyos feloszt´as
Szab´alyos feloszt´as
I
Egy szab´alyos 3D r´accsal lefedj¨ uk az eg´esz sz´ınteret.
I
El˝ofeldolgoz´as: minden cell´ahoz feljegyezz¨ uk a beletartoz´o objektumokat.
I
Haszn´alat: csak azokkal az objektumokkal v´egz¨ unk sug´ar metsz´est, amiknek a cell´aj´an a sug´ar ´athalad
I
El˝onye: A vizsg´aland´o cell´ak gyorsan sz´am´ıthat´ok szakaszrajzol´o algoritmussal! (L´asd k´es˝obb a raszteriz´aci´on´al)
I
H´atr´anya: Feleslegesen sok cella – nagyr´esz¨ uk u ¨res teret fed le.
Okt´alis fa
I
Fa gy¨okere: a teljes sz´ınteret mag´aban foglal´o tengelyekkel p´arhuzamos ´el˝ u befoglal´o doboz (AABB)
I
V´agjuk ezt nyolc egyenl˝o r´eszre!
I
Minden u ´j dobozra: ha el´eg sok objektum van benne, akkor tov´abb osztjuk, k¨ ul¨onben meg´allunk.
I
El˝ony: az u ¨res r´eszeket nem osztjuk tov´abb feleslegesen.
I
H´atr´any: bonyolultabb bej´ar´as.
I
H´atr´any: a fa m´elys´ege elsz´allhat → a gyakorlatban egy el˝ ore´ırt m´elys´eg is adott, amit el´erve m´ar nem osztjuk tov´abb a cell´akat (m´eg ha t¨obb objektum is jutna oda, mint a minimum)
Okt´alis fa
Okt´alis fa
Okt´alis fa
Quadtree
I
Az okt´alis fa s´ıkbeli v´altozata
I
Az aktu´alis cell´at mindig n´egy egyenl˝o r´eszre osztjuk, a tengelyekkel p´arhuzamosan
Okt´alis fa
kd-fa
I
Probl´ema az okt´alis f´aval: mindig k¨oz´epen ´es minden s´ık ment´en v´ag – nem veszi figyelembe az objektumokat.
I
Okt´alis fa: keres´esi id˝o ≈ fa magas´aga. DE! az okt´alis fa kiegyens´ ulyozatlan.
I
kd-fa: minden l´ep´esben egyetlen s´ıkkal v´agunk, ami egy tengelyre mer˝oleges.
I
Sorrend: X , Y , Z , X , Y , Z , .... Felez˝o s´ık elhelyez´ese:
I
I I I
kd-fa
t´erbeli k¨oz´epvonal m´odszer test k¨oz´epvonal m´odszer k¨olts´eg modell alap´ u m´odszer
