Irradiance caching

Irradiance caching je algoritmus pro globální osvětlení v počítačové grafice. Algoritmus slouží k urychlení výpočtů, jako například Final Gathering ve Photon Mapping technikách, kde se pro každý bod vrhá mnoho (stovky až tisíce) sekundárních paprsků, což je výpočetně náročné.

Metoda Irradiance caching je nekonzistentní, tedy nekonverguje v čase ke správnému výsledku. Dává ovšem velmi uvěřitelné výsledky v mnohem rychlejším čase oproti jiným metodám.

Popis

Základní myšlenkou je výpočet neprovádět pro každý bod prostoru zvlášť, ale jenom na několika vybraných místech a ostatní body pouze interpolovat. Lze to dělat díky tomu, že ve scéně, která není modulovaná texturou a odrazem paprsků, pro každý bod zobrazujeme příchozí osvětlení přes celou hemisféru, což se v okolí bodu moc nemění. +more Pokud je v okolí bodu složitější geometrie, tak se mění rychleji, pokud ne, tak pomaleji. V místech se složitější geometrií tak budou body vybrány hustě, v místech s jednodušší geometrií řídce.

Algoritmus je navržen pro fungování s difuzní komponentou osvětlení, protože ta je pohledově nezávislá. Odražená radiance je dána jako irradiance * odrazivost povrchu, tedy bez směrových proměnných, takže je ve všech směrech konstantní. +more Pokud si budeme pamatovat hodnotu příchozí irradianci v nějakém místě, tak pro jakýkoli úhel pohledu získáme množství odražené radiance pouze pronásobením s texturou (odrazivostí). Když máme potom v cache irradianci pro některé body, tak z nich pro dotazovaný bod vyzvedneme irradianci a vynásobíme hodnotou textury v daném místě.

Algoritmus

Algoritmus má klasické cachovací schéma - líné vyhodnocování. Tedy hodnota osvětlení se počítá, až když je potřeba.

Podíváme se tedy do cache. Pokud jsou v okolí nějaké vhodné body, tak interpoluji, jinak počítám (draze) novou hodnotu a uložím ji do cache.

Pseudokód Irradiance caching

function GetIrradiance(p): Color E = InterpolateFromCache(p); if E == invalid E = SampleHemisphere(p); InsertIntoCache(E, p); return E;

Výpočet nepřímé irradiance

Když v cache nejsou záznamy, ze kterých bychom mohli interpolovat, musíme vytvořit nový záznam vrháním sekundárních paprsků pomocí funkce SampleHemisphere(p).

Vrháme řádově 500 až 5000 paprsků (záleží na uživateli).

Ze scény vyjmeme zdroje světla, jelikož děláme pouze nepřímé osvětlení.

Vrhneme paprsek někam na hemisféře a v průniku nějakým způsobem odhadneme radianci. Buď můžeme dát dotaz do fotonové mapy nebo rekurzivně opakovat irradiance caching (do jiných cache). +more Pak výsledky z různých paprsků zprůměrujeme.

Pro vrhání sekundárních paprsků typicky používáme metodu Monte Carlo se stratifikací podle \theta a \phi.

Irradianci v bodě p spočítáme podle :

E(p) = \int L_{i}(p,\omega _{i})\cos \theta_{i} d\omega _{i}

Obecná forma stratifikovaného estimátoru

E(p)\approx \frac{1}{MN}\sum_{j=0}^{M-1}\sum_{k=0}^{N-1}\frac{f(\theta_{j,k}, \phi_{j,k})}{p(\theta_{j,k}, \phi_{j,k})}

Pro výpočet irradiance je integrand:

L(\theta, \phi) cos \theta

Hustota pravděpodobnosti (PDF):

p(\theta, \phi)= \frac{cos\,\theta}{\pi}

Po dosazení je estimátor irradiance:

E(p)\approx \frac{\pi}{MN}\sum_{j=0}^{M-1}\sum_{k=0}^{N-1}L_{j,k}

Kde L_{j,k} je vzorek radiance ze směru (\theta_{j,k}, \phi_{j,k}) = (arccos\sqrt{1-\frac{j+\zeta_{j,k}^{1}}{M}}, 2\pi\frac{k+\zeta_{j,k}^{2}}{N})

M, N jsou počty dílů podél \theta, \phi

\zeta_{j,k}^{1}, \zeta_{j,k}^{2} jsou náhodná čísla z R(0,1)

Adaptivní odhad poloměru platnosti záznamu

Chceme, aby cachování bylo adaptivní. Tedy tam, kde by se osvětlení mohlo měnit rychle, tak tam chceme záznamů hodně. A naopak.

Osvětlení se bude měnit rychle tam, kde se nachází v okolí nějaká geometrie, na rovné ploše se nebude osvětlení rychle měnit. Jestli je v okolí bodu nějaká geometrie, zjistíme jednoduše - při vzorkování hemisféry u každého vrhnutého paprsku známe i jeho vzdálenost. +more Spočítáme pak průměrnou vzdálenost, kde se nacházejí objekty v okolí daného místa a to nám dá poloměr (radius), kde se záznam smí ještě použít.

Interpolace z cache

Irradianci v bodě p spočítáme jako vážený průměr irradiancí v bodech, co jsou v okolí bodu p.

Vážený průměr:

E(p)=\frac{\sum_{i\in S(p)}E_{i}(p)\omega_{i}(p)}{\sum_{i\in S(p)}\omega_{i}(p)}

Množina záznamů použitelných pro interpolaci:

S(p)=\left \{ i; \omega_{i}(p)>0 \right \}

Váhová funkce:

\omega_{i}(p)=1-\kappa \max \left \{ \frac{\left \| p-p_{i} \right \|}{\mathrm{clamp}(2R_{i}, R_{min},R_{max})}, \frac{\sqrt{1-n\cdot n_{i}}}{\sqrt{1-\cos 10 ^\circ}} \right \}

Zde p je bod, kde chceme interpolovat, p_{i} je bod v cache. Funkce clamp omezuje shora a zespoda. +more Zbytek jsou přidané heuristiky, kde n je normála v bodě, kde chceme interpolovat, n_{i} je normála bodu v cache.

Při implementaci se přidávají ještě další heuristické podmínky, které nejsou pokryty ve vzorci. Jedná se například o "behind test", který kontroluje, jestli neinterpolujeme bod, který je za bodem v cache.

Datová struktura - Octree

Musíme zvolit vhodnou datovou strukturu pro Irradiance cache.

Máme záznam - bod ve scéně, normála, irradiance, poloměr použitelnosti hodnoty irradiance, gradienty.

Do datové struktury budeme inkrementálně přidávat nové záznamy. Dále budeme chtít, aby nám datová struktura vrátila všechny koule (záznamy - bod a poloměr dává kouli), které obsahují dotazovaný bod v prostoru.

Pro tyto potřeby je nejvhodnější datovou strukturou Octree. Do každého uzlu stromu ukládáme všechny koule, které tento uzel pronikají. +more Máme tak vysokou redundanci záznamů, ale napomáhá to rychlejšímu vyhodnocení dotazu. Větší koule ukládáme ve vyšších patrech, menší v nižších. Při vyhledávání procházíme stromem od kořene do uzlu, kde se dotazovaný bod nachází, a po cestě sbíráme v každém uzlu, který navštívíme, informace o potenciálně proniknutých koulích. Průniky zadaného bodu s nalezenými koulemi vyhodnocujeme.

Pseudokód hledání záznamu v Octree

procedure LookUpRecordsMR(p,n): node := root; while node != NULL do for all records i stored in node do if w(i,p) > 0 and (p(i) not in front of p) then Include record in S(p) end if end for node := child containing p end while //w(i,p) je váhová funkce, p(i) je bod v zaznamu

Gradienty

Aby se zlepšila interpolace, tak použijeme gradienty. Použijeme tedy interpolace vyšších řádů. +more Celá interpolace funguje tak, že ve chvíli výpočtu osvětlení nějakého místa spočítáme nejen irradianci, ale spočítáme i jaký bude její gradient - tedy jak rychle se bude měnit hodnota irradiance při posouvání bodem. Uděláme tedy Taylorův rozvoj prvního řádu. Počítají se dva typy gradientů - jeden je vůči rotaci, druhý je vůči translaci.

Kategorie:Počítačová 3D grafika Kategorie:Algoritmy