Path Tracing

História

V roku 1986 James Kajiya predstavil zobrazovaciu rovnicu, popri ktorej zároveň publikoval aj algoritmus, ktorý odhaduje jej numerickú aproximáciu. O desať rokov neskôr Eric P. Lafortune priniesol niekoľko vylepšení, medzi ktoré patril aj algoritmus bidirectional path tracing.
V roku 2009 Austin Robinson z Nvidia prezentoval prvú komerčnú implementáciu algoritmu path tracing, ktorý beží na grafickej karte. Tá vo veľkej miere ovplyvnila ďalšie implementácie, ktorým pomohlo aj vyzretie technológií pre programovanie na GPU ako sú CUDA alebo OpenCL.

Opis

Zobrazovacia rovnica, ktorú publikoval Kajiya sa zdží troch zásad optiky: Princíp globálneho osvetlenia, Princíp ekvivalencie (odrazené svetlo je ekvivalentné vyžarovanému svetlu) a Princíp smerov (odrazené aj refraktované svetlo majú svoj smer).
V svete okolo nás, objekty sú viditeľné pre ich odrazivosť svetla. Z tohto hľadiska možno pozorovať, že sa objekty (aj odrazeným) svetlom osvetľujú navzájom. Z tohto jednoduchého pozorovania vychádzajú ďalšie dva princípy:
I. Pre danú uzavretú scénu, každý objekt na scéne musí vyžarovať svetlo na každý objekt.
II. Nie je žiadny rozdiel v správaní svetla, ktoré prichádza priamo od svetelného zdroja a svetla, ktoré je odrazené.

Teoretické pozadie

Algoritmus aproximuje radianciu, ktorá zo scény prichádza do kamery zo scény, teda tú ktorá je vyžarovaná priamo, aj tú, ktorú odrážajú osvetlené objekty v scéne. Pri odrazenom svetle z objektov na scéne do kamery je nutné uvažovať nielen svetlo, ktoré dopadá na ne priamo zo svetelného zdroja, ale aj to, ktoré ich osvetľuje po odraze zo scény. Preto je nutné najprv poznať zobrazovaciu rovnicu:
L(\mathbf x,\omega_o) = L_e(\mathbf x,\omega_o) + \int_H L(r(\mathbf x, \omega_i), -\omega_i) \cdot f_r(\mathbf x, \omega_i \rightarrow \omega_o) \cdot cos(\theta_i)\mathrm d \omega_i.
Ktorá hovorí o tom, že pre daný bod x na scéne v smere \omega_o je súčet radiance, ktorá je z bodu x vyžarovaná priamo (v prípade svetelného) zdroja a integrálu prichádzajúcej radiancie z celej hemisféry funkcie BRDF doplnenú o faktor frac{cos(\theta_i)}{\pi}. Výraz r(x,\omega_i) vyjadruje presečník z bodu x v smere \omega_i so scénou a L(r(x,\omega_i), -\omega_i) je prichádzajúca radiancia z bodu r(x,\omega_i) do bodu x.
V komplikovanejších scénach však nie je možné v krátkom čase vypočítať priestorový integrál analyticky. V tomto prípade je nutné použiť numerickú metódu pre výpočet integrálu. V prípade algoritmu path tracing sa využíva metóda Monte Carlo, pre ktorý príslušný estimátor bude mať tvar:
\hat{L}(\mathbf x,\omega_o) = L_e(\mathbf x,\omega_o) + \frac{L(r(\mathbf x, \omega_i), -\omega_i) \cdot f_r(\mathbf x, \omega_i \rightarrow \omega_o) \cdot cos(\theta_i)}{p(\omega_i)},
Kde \omega_i je náhodne vygenerovaný smer a p(\omega_i) je pravdepodobnosť, s akou bol smer \omega_i vygenerovaný.

Pseudokód

function renderImage() 
{
   for all pixels
   {
      Color pixelCol = (0,0,0);
      for k = 1 to N
      {
         wk := náhodný smer cez k-tý pixel
         pixelCol += getLi(camPos,wk)
      }
   }}
getLi(x, w){
   Color thrput = (1,1,1)
   Color accum  = (0,0,0)
   while(1)
   {
      hit = NearestIntersect(x, w)
      if no intersection
         return accum + thrput * bgRadiance(x, w)
      if isOnLightSource(hit)
         accum += thrput * Le(hit.pos, -w)
      ρ = reflectance(hit.pos, -w)
      if rand() < ρ // ruská ruleta - pravdepodobnosť prežitia
      {
         wi := SampleDir(hit)
         thrput *= fr(hit.pos, wi, -w) * dot(hit.n, wi) / (ρ*pdf(wi))
         x := hit.pos
         w := wi
      }
      else // absorb
         break;
   }return accum;}

Výber náhodného smeru

Algoritmus ako je uvedený vyššie používa metódu SampleDir() o ktorej vieme len to, že vygeneruje nejaký smer \omega_i s nejakou pravdepodobnosťou p(\omega_i). Jedno z možných riešení je, že metóda bude vyberať smery uniformne z celej hemisféry, ktorá sa však ukazuje ako korektná, ale z výsledných obrázkov šum mizne veľmi pomaly. V praxi je výhodnejšie vyberať prednostne tie smery, kde očakávame vyšší príspevok svetla.

Vzorkovanie podľa BRDF

V závislosti na charakteristike materiálu a vstupnom smere, vygenerujeme nový smer s hustotou podľa funkcie odrazivosti. Napríklad v prípade zrkadlovehó povrchu bude výsledný smer zakaždým odrazený v smere od kolmice, v prípade ideálne Lambertovského povrchu, bude vzorkovanie prebiehať s hustotou \frac{cos(\theta)}{\pi}(tzv. cosínové vzorkovanie), kde \theta je uhol medzi vygenerovaným smerom a normálou plochy v bode x.

Vzorkovanie svetla

Ak sú svetelné zdroje príliš malé, alebo dokonca sú v scéne vyjadrené ako matematický bod (nemajú nikdy priesečník s náhodne vygenerovaným smerom), môže trvať veľmi dlho, kým algoritmus vygeneruje taký smer, že bude mať s nimi priesečník. V tomto prípade je výhodné odhadovať zvlášť priame a zvlášť nepriame osvetlenie. Kým stratégia pre odhad nepriameho osvetlenia môže ostať napr. vzorkovaním podľa BRDF, priame osvetlenie algoritmus odhadne zvlášť vygenerovaným smerom zo svetelného zdroja.

Kombinované vzorkovanie

Predstavme si prípad, kde materiál je „takmer zrkadlový“ a svetlo s veľmi veľkou plochou. Ak budeme vzorkovať z plochy svetla, je veľmi nízka pravepodobnosť, že sa trafíme práve do úzkeho intervalu smerov U(\omega_i), ktorý je materiál schopný odraziť v smere \omega_o s nejakou nezanedbateľnou radian- ciou. Ak budeme mať ešte silnejší predpoklad, a to že materiál je „dokonale zrkadlový“, budeme mať len jeden prípustný smer \omega_o. Ten však nami zvolená technika nikdy nevygeneruje. V týchto prípadoch bude lepšie použiť vzorkovanie podľa BRDF.
Naopak, predpokladajme, že materiál je „dokonale difúzny“ a svetlo s veľmi malou plochou. Ak budeme vzorkovať náhodne smery z celej hemisféry, opäť dostávame veľmi nízku pravdepodobnosť, že trafíme zdroj svetla. Aj v tomto prípade môžeme mať silnejší predpoklad, a to keď svetelný zdroj bude zanedbateľne malý – môžeme ho zjednodušit’ až na bodový svetelný zdroj. V tomto prípade technika vzorkovania nikdy nevygeneruje smer, kde sa trafí práve do bodu, kde je umiestnené svetlo, preto bude lepšie použiť techniku z prvého prípadu.
Oba prípady môžu nastať dokonca v rámci jednej scény. Metóda vyrovnanej heuristiky využíva obe metódy vzorkovania naraz a do výsledku dáva ich súčet upravený o váhu s akou pravdepodobnosťou by boli vygenerované tou druhou metódou.
Majme smer \omega_l ktorý bol vygenerovaný metódou vzorkovania svetla, smer \omega_f, ktorý bol vygenerovaný metódou vzorkovania podľa BRDF. Pravdepodobnosť p_l(\omega_l) bude príslušná pravdepodobnosť z prvej metódy, p_f(\omega_f) príslušná pravdepodobnosť pre metódu vzorkovania podľa BRDF. Pri tejto metóde vzorkovania potrebujeme ďalšie dve hodnoty a to, aká by bola pravdepodobnosť, keby sme smery \omega_l a \omega_f vygenerovali v druhej stratégií. Formálne p_f(\omega_l) a p_l(\omega_f).
Estimátor za použitia takejto stratégie vzorkovania bude mať tvar
\hat{L}(\mathbf x,\omega_o) = L_e(\mathbf x,\omega_o) + \frac{L_i(r(\mathbf x, \omega_l), -\omega_l) \cdot f_r(\mathbf x, \omega_l \rightarrow \omega_o) \cdot cos(\theta_l)}{p_l(\omega_l) + p_f(\omega_l)} + \frac{L_i(r(\mathbf x, \omega_f), -\omega_f) \cdot f_r(\mathbf x, \omega_f \rightarrow \omega_o) \cdot cos(\theta_f)}{p_l(\omega_f) + p_f(\omega_f)}

Ukončenie rekurzie

V realite, svetlo, ktoré prekoná konečný počet odrazov z materiálu s nenulovou odrazivosťou, má stále nejakú (aj keď len zanedbateľne malú) hodnotu. V implementácií by to znamenalo pre každú cestu nekonečný cyklus, ktorý je v praxi vylúčený. Pre tento problém boli vyvinuté algoritmy, ktoré danú hodnotu, pre ktorú je nutný nekonečný cyklus odhadnú.

Ruská ruleta

Ruská ruleta je nestranný algoritmus, ktorý pokračuje s pravdeposťou q a váhu upraví faktorom \frac{1}{q} ktorá nám zaručuje nestrannosť. Za pravdepodobnosť prežitia cesty q môžeme použit’ čokoľvek, algoritmus bude vždy nestranný. V praxi za q dosadzujeme práve odrazivosť, ako je uvedené v pseudokóde. Ak plocha odrazí napr. 30 %, rekurzia skončí s pravdepodobnosťou 70 % a s pravdepodobnosťou 30 % bude pokračovat’.