Zobrazenie zdroja stránky Path Tracing

{{Bez zdroja}}
'''Path tracing''' je fotorealistický 3D vykresľovací [[algoritmus]], ktorý využíva integrovanie metódou Monte Carlo na výpočet intenzity svetla, ktoré sa odrazí od jednotlivých bodov na povrchu objektu scény a dopadá do virtuálnej kamery. Algoritmus jednotlivo simuluje tok svetla na scéne, ktoré sa pohybujú smerom od svetla do kamery. Medzi jeho hlavné výhody patrí jeho fyzikálna vernosť,
ktorá umožňuje zachytávať javy ako nepriame osvetlenie, mäkké tiene alebo [[kaustika|kaustiky]] pod vodnou hladinou.

Práve pre jeho presnosť a nestrannosť sa dnes využíva ako referenčný algoritmus pri testovaní iných, rýchlejších algoritmov. Vykresľovanie kvalitných obrázkov pomocou path tracingu môže trvať niekoľko desiatok až stoviek hodín.

== História ==

V roku 1986 James Kajiya{{Ref|kajiya1986rendering}} predstavil zobrazovaciu rovnicu, popri ktorej zároveň publikoval aj algoritmus, ktorý odhaduje jej numerickú
aproximáciu. O desať rokov neskôr Eric P. Lafortune{{Ref|lafortune1996mathematical}} priniesol niekoľko vylepšení, medzi ktoré patril aj algoritmus bidirectional path tracing.

V roku 2009 Austin Robinson{{Ref|robisonNVIRT}} 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 [[Grafická karta|GPU]] ako sú [[CUDA]] alebo [[OpenCL]].

== Opis ==

Zobrazovacia rovnica, ktorú publikoval Kajiya{{Ref|kajiya1986rendering}} 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ť [[zobrazovacia rovnica|zobrazovaciu rovnicu]]:

<math>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.</math>

Ktorá hovorí o tom, že pre daný bod ''x'' na scéne v smere <math>\omega_o</math> 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 <math>frac{cos(\theta_i)}{\pi}</math>. Výraz <math>r(x,\omega_i)</math> vyjadruje presečník z bodu x v smere <math>\omega_i</math> so scénou a <math>L(r(x,\omega_i), -\omega_i)</math> je prichádzajúca radiancia z bodu <math>r(x,\omega_i)</math> 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: 

<math>\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)},</math>

Kde <math>\omega_i</math> je náhodne vygenerovaný smer a <math>p(\omega_i)</math> je pravdepodobnosť, s akou bol smer <math>\omega_i</math> vygenerovaný.  

=== Popis algoritmu ===
Pre jednoduchosť algoritmus počíta s kamerou ako s bodom. Odtiaľ cez jednotlivé [[pixel]]y vedie lúče a skúša, či sa od scény neodrazí do svetla. Ak áno, vypočíta príspevok v danom bode a vráti sa naspäť cez odrazené miesta postupne až ku kamere, pričom v odrazených miestach eliminuje intenzitu svetla v závislosti na odrazivosti konkrétneho bodu na scéne. 

[[File:Ray trace diagram.svg|right|thumb|300px|Prvý krok algoritmu, pri ktorom vedie lúč smerom od kamery na scénu]]

# Na začiatku nech ''x'' je pozícia kamery
# Zvolí sa smer ω cez pixel na obrazovke smerom od kamery do scény
# Nájde sa priesečník ''y'' smeru ω so scénou
::Ak je ''y'' súčasť svetla, k medzivýsledku pripočíta intenzitu svetla, ktoré je z bodu ''y'' vyžarované v smere -ω (z bodu ''y'' do ''x'')
::Ak ''y'' neexistuje (nenájde priesečník), vráti sa a pripočíta sa farba okolia
::Ak ''y'' je bod na scéne s nenulovou odrazivosťou, pokračuje s bodom ''y'' ako s bodom ''x'', odtiaľ sa vygeneruje nový smer ω (na základe distribučnej funkcie) a pokračuje sa v bode 3 (rekurzívne), kde sa hľadá nový priesečník. Vypočítaný príspevok po odraze pripočíta k medzivýsledku.

Uvedený úsek algoritmu je pre 1 pixel. Výsledná scéna vznikne, ak sa spustí niekoľkokrát pre každý pixel a v rámci jedného pixelu sa hodnoty spriemerujú. Kvalita obrázku priamo závisí na počte opakovaní algoritmu na jednom pixeli.

== Pseudokód ==

<source lang="cpp">
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)
      }
   }
}
</source>

<source lang="cpp">
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;
}
</source>

== 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 <math>\omega_i</math> s nejakou pravdepodobnosťou <math>p(\omega_i)</math>. 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 <math>\frac{cos(\theta)}{\pi}</math>(tzv. cosínové vzorkovanie), kde <math>\theta</math> 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 <math>U(\omega_i)</math>, ktorý je materiál schopný odraziť v smere <math>\omega_o</math> 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 <math>\omega_o</math>. 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 <math>\omega_l</math> ktorý bol vygenerovaný metódou vzorkovania svetla, smer <math>\omega_f</math>, ktorý bol vygenerovaný metódou vzorkovania podľa BRDF.
Pravdepodobnosť <math>p_l(\omega_l)</math> bude príslušná pravdepodobnosť z prvej metódy, <math>p_f(\omega_f)</math> 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 <math>\omega_l</math> a <math>\omega_f</math> vygenerovali v druhej stratégií. Formálne <math>p_f(\omega_l)</math> a <math>p_l(\omega_f)</math>.

Estimátor za použitia takejto stratégie vzorkovania bude mať tvar

<math>\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)}</math>

== 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 <math>\frac{1}{q}</math> 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’.

== Referencie ==

{{Reflist}}
# {{note |kajiya1986rendering}} James T. Kajiya [http://cg.informatik.uni-freiburg.de/intern/seminar/86kajiyaRenderingEquation.pdf Rendering equation] 1986
# {{note |lafortune1996mathematical}} Lafortune, E, [http://www.graphics.cornell.edu/~eric/thesis/index.html Mathematical Models and Monte Carlo Algorithms for Physically Based Rendering], (PhD thesis), 1996.
# {{note |robisonNVIRT}} Robison, Austin, [http://realtimerendering.com/downloads/NVIRT-Overview.pdf "Interactive Ray Tracing on the GPU and NVIRT Overview"], slide 37, I3D 2009.

[[Kategória:Algoritmy]]
[[Kategória:Počítačová grafika]]