Path Tracing

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 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 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:
formula_1
Ktorá hovorí o tom, že pre daný bod "x" na scéne v smere formula_2 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 formula_3. Výraz formula_4 vyjadruje presečník z bodu x v smere formula_5 so scénou a formula_6 je prichádzajúca radiancia z bodu formula_4 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: 
formula_8
Kde formula_5 je náhodne vygenerovaný smer a formula_10 je pravdepodobnosť, s akou bol smer formula_5 vygenerovaný. 
Popis algoritmu.
Pre jednoduchosť algoritmus počíta s kamerou ako s bodom. Odtiaľ cez jednotlivé pixely 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. 
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.
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 formula_5 s nejakou pravdepodobnosťou formula_10. 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 formula_14(tzv. cosínové vzorkovanie), kde formula_15 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 formula_16, ktorý je materiál schopný odraziť v smere formula_2 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 formula_2. 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 formula_19 ktorý bol vygenerovaný metódou vzorkovania svetla, smer formula_20, ktorý bol vygenerovaný metódou vzorkovania podľa BRDF.
Pravdepodobnosť formula_21 bude príslušná pravdepodobnosť z prvej metódy, formula_22 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 formula_19 a formula_20 vygenerovali v druhej stratégií. Formálne formula_25 a formula_26.
Estimátor za použitia takejto stratégie vzorkovania bude mať tvar
formula_27
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 formula_28 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’.