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 editovat

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í. 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í. 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 editovat

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 editovat

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

Výpočet nepřímé irradiance editovat

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). 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 editovat

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. 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 editovat

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. 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 editovat

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í. 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 editovat

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 editovat

Aby se zlepšila interpolace, tak použijeme gradienty. Použijeme tedy interpolace vyšších řádů. 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.