Sledování cest

Sledování cest, anglicky Path tracing, je algoritmus používaný v počítačové 3D grafice k syntéze (renderování) obrazu virtuální trojrozměrné scény, v níž věrně simuluje globální osvětlení. Řeší zobrazovací rovnici za pomoci Monte Carlo integrování, kdy pro každý pixel výsledného obrázku opakovaně simuluje tok světla ve scéně formou náhodné procházky, neboli sleduje možné cesty paprsků světla, které vycházejí ze světelných zdrojů a po interakci se scénou dopadají do daného pixelu virtuální kamery (odtud název).

Sledování cest přirozeně a fyzikálně přesně simuluje mnoho efektů nepřímého osvětlení, které musí být při užití jiných metod (např. sledování paprsku) komplikovaně imitovány. Patří mezi ně zejména ideální odraz a lom světla, „půjčování barev“ (anglicky color bleeding), kaustiky, měkké stíny, zachycuje rovněž hloubku ostrosti či rozmazání pohybem. Při kombinaci s dostatečně přesnými modely povrchů objektů, světelných zdrojů a kamery pak produkuje obrázky nerozeznatelné od reálných fotografií. Pro získání takto kvalitních výstupů však musí být odsimulováno velké množství paprsků, jinak jsou výsledky zatíženy viditelným šumem.

Časová náročnost této metody dosud komplikuje nasazení v interaktivních aplikacích, díky své přesnosti a nestrannosti ale našla uplatnění například ve filmovém průmyslu a designu či je používána ke generování referenčních obrázků při testování kvality jiných renderovacích algoritmů.

Historie

Když v roce 1986 James Kajiya publikoval zobrazovací rovnici a její využití v počítačové grafice, představil rovněž algoritmus pro nalezení jejího numerického řešení, jenž nazval sledováním cest.^[1] O deset let později na něj navázal Lafortune a navrhl mnohá zlepšení včetně tzv. obousměrného sledování cest.^[2]

V roce 1997 přispěli svou modifikací obousměrného sledování cest Eric Veach a Leonidas J. Guibas.^[3] Nesla název Metropolis light transport a byla založena na znovu využívání již nalezených cest z kamery do světelných zdrojů za účelem zvýšení výkonu v náročných scénách.

Na počátku nového tisíciletí bylo směřování dalšího vývoje ovlivněno nástupem programovatelných GPU. V roce 2002 prezentoval Timothy Purcell první algoritmus globálního osvětlení běžící na GPU.^[4] Následné zdokonalení technologií pro programování GPU (OpenCL, CUDA, ATI Stream) pak spolu s nárůstem výpočetní síly znovu podnítilo zájem o algoritmy založené na sledování cest. První komerční GPU implementaci sledování cest demonstroval Austin Robison ze společnosti NVIDIA v únoru 2009^[5] a další následovaly. V současnosti jsou již některé schopny vykreslovat fotorealistické scény v reálném čase.

Existující implementace

• Čistě CPU:
  • Corona (volně dostupný, ve vývoji, český autor)
  • Arnold Archivováno 8. 2. 2018 na Wayback Machine. (komerční)
• Čistě GPU:
  • Octane Render (komerční)
• Hybridní (CPU s GPU akcelerací):
  • Arion (komerční)
  • LuxRender (open-source)
  • Maxwell Render (komerční)
  • Indigo (komerční)

Základní verze algoritmu

Teoretické pozadí

Algoritmus chápe světlo jako spojitou nekonečně dělitelnou energii, která vychází ze světelných zdrojů a šíří se prostředím, kde interaguje s povrchy objektů, až se ustálí v rovnovážném stavu. Přitom předpokládá, že se světlo vzájemně neovlivňuje, tj. že energie přicházející do jednoho místa z více směrů se jednoduše sčítá. Tento model je zjednodušením reality, nepostihuje vlnový ani částicový charakter světla, odpovídá spíše geometrické optice. Sledování cest tudíž v této podobě nesimuluje jevy jako je difrakce, disperze, interference či polarizace.

Vyzařování a přenos světla jsou charakterizovány radiometrickými veličinami, zejména září ${\displaystyle L(\mathbf {x} ,\omega )}$ vyjadřující směrovou hustotu toku světla v bodě ${\displaystyle \mathbf {x} }$ ve směru ${\displaystyle \omega }$. Zář daným bodem emitovaná je typicky značena ${\displaystyle L_{e}}$ a nabývá nenulových hodnot pro body na povrchu světelných zdrojů. Nelze ji však použít pro popis bodových zdrojů, k tomu slouží veličina zářivost.

Interakce světla s hmotou je vyjádřena pomocí BRDF, tj. funkce ${\displaystyle f_{r}(\mathbf {x} ,\omega _{i}\rightarrow \omega _{o})}$ udávající v zásadě hustotu pravděpodobnosti, s jakou se světlo dopadající ze směru ${\displaystyle \omega _{i}}$ do bodu ${\displaystyle \mathbf {x} }$ odrazí do směru ${\displaystyle \omega _{o}}$. Tato funkce zachycuje odrazivé vlastnosti materiálů ve scéně, modeluje mikrostrukturu jejich povrchů.

Podmínku na rovnovážné rozložení světla ve scéně formuluje zobrazovací rovnice:

${\displaystyle 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}.}$

Ta říká, že odchozí zář v bodě ${\displaystyle \mathbf {x} }$ ve směru ${\displaystyle \omega _{o}}$ je dána součtem záře tímto bodem do tohoto směru emitované a integrálu záře příchozí do ${\displaystyle \mathbf {x} }$ z libovolného směru hemisféry, která se s pravděpodobností danou BRDF do směru ${\displaystyle \omega _{o}}$ odrazila.

Cílem algoritmu pak je pro daný popis světelných zdrojů pomocí emitované radiance a povrchů pomocí BRDF nalézt takové rozložení světla ve scéně, které splňuje zobrazovací rovnici, tzn. nalézt její řešení. Zobrazovací rovnici je však typicky nemožné vyřešit analyticky (scény mají složitou geometrii, integrand je tudíž nespojitý a nabývá takřka libovolných hodnot), sledování cest je proto řešením numerickým. Integrál v rovnici algoritmus odhadne metodou Monte Carlo pomocí jednoho náhodně vygenerovaného směru, neboli spočítá

${\displaystyle {\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 ${\displaystyle \omega _{i}}$ je směr náhodně vygenerovaný podle hustoty pravděpodobnosti ${\displaystyle p}$.

Algoritmus

Vlastní renderování probíhá následovně. Pro daný pixel výstupního obrázku je náhodným směrem skrze něj z kamery do scény vržen paprsek. Jestliže žádný objekt scény netrefí, použije se zář pozadí a cesta končí. Jinak se nalezne nejbližší průsečík se scénou a spočítá se zde odhad odchozí záře podle vztahu výše. Tj. leží-li průsečík na zdroji, přičte se emitovaná zář zdroje, a zář odražená se odhadne rekurzivně opětovným vržením paprsku do scény v náhodném směru hemisféry. Aby nevznikaly nekonečné cesty a algoritmus skončil, nevrhá se další paprsek vždy, nýbrž pouze s pravděpodobností rovnou odrazivosti povrchu v místě průsečíku. Tento postup se pro každý pixel zopakuje mnohokrát a příspěvky jednotlivých cest se zprůměrují.

V této podobě lze celý algoritmus zapsat následujícím pseudokódem:

renderImage()
{
  for each pixel p
  {
    Color pixelColor = (0, 0, 0);
    for k = 1 to N
    {
      w = randomDirThroughPixel(cameraPosition, p);
      pixelColor += getL(cameraPosition, w);
    }
    setOutputPixel(p, pixelColor / N);
  }
}

getL(x, wo)
{
  Color L = (0, 0, 0);
  hit = nearestIntersection(x, wo);
  if isEmpty(hit)
    return backgroundRadiance(x, wo);
  if isOnLightSource(hit)
    L += Le(hit.pos, -wo);
  ρ = reflectance(hit.pos, -wo);
  if rand() < ρ
  {
    wi = randomDirOnHemisphere(hit);
    L += getL(hit.pos, wi) * fr(hit.pos, wi, -wo) * dot(hit.n, wi) * 2 * Pi / ρ;
  }
  return L;
}

Vylepšení

Popsaná verze algoritmu je ryze základní, slouží především pro ilustraci. Ač je z teoretického hlediska korektní, v praxi velice špatně konverguje, pročež se typicky implementuje s celou řadou vylepšení. Mezi nejvýznamnější z nich patří:

Vzorkování podle BRDF

Místo uniformního generování směrů (vzorkování) hemisféry se použije technika vzorkování podle důležitosti a hemisféra se vzorkuje podle BRDF. Tedy místo konstantní hustoty ${\displaystyle 1/(2\pi )}$ jsou směry generovány podle hustoty co nejpodobnější BRDF. Například pro difúzní komponentu Phongovy BRDF se používá hustota ${\displaystyle \cos(\theta )/\pi }$, kde ${\displaystyle \theta }$ je úhel mezi vygenerovaným směrem a normálou plochy v místě průsečíku. Paprsky jsou tak vrhány ve směru pravděpodobnějšího odrazu.

Vzorkování světelných zdrojů

V některých situacích samotné vzorkování podle BRDF selhává (zejména pro malé či bodové světelné zdroje). Kombinuje se proto se vzorkováním světelných zdrojů, kdy se v místě dopadu paprsku vrhá, vedle paprsku sloužícího pro rekurzivní výpočet odražené záře, ještě jeden speciální paprsek k náhodně vygenerovanému bodu na zdroji (ten ve zdroji končí, cesty se tedy exponenciálně nevětví). Příspěvky obou paprsků se poté sečtou s vhodnými vahami.

Složitější interakce světla se scénou

BRDF popisuje pouze odraz světla, počítá se proto s komplikovanějšími distribucemi BTDF či BSDF modelujícími lom, resp. rozptyl světla, pro některé materiály se uvažují i odrazy pod povrchem (BSSRDF).

Osvětlení mapou prostředí

Místo bodových a plošných světelných zdrojů scénu osvětluje myšlená nekonečná koule kolem ní, na níž byl namapován obraz reálného prostředí. Implementace tohoto vylepšení významně ovlivňuje uvěřitelnost výstupu.

Obousměrné sledování cest

Sledování cest směrem z kamery do světelných zdrojů není v praxi pro vykreslení některých jevů použitelné, např. kaustiky konvergují jen velice pomalu. Obousměrné sledování cest proto tento směr kombinuje i se směrem opačným, tj. ze zdrojů do kamery.

Zkratky

• BSDF - Bidirectional scattering distribution function
• BRDF - Bidirectional reflectance distribution function
• BTDF - Bidirectional transmittance distribution function
• BTF - Bidirectional texture function
• BSSRDF - Bidirectional Surface Scattering Reflectance Distribution Function
• SVBRDF - Spatially Varying Bidirectional Reflectance Distribution Function

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Path tracing na anglické Wikipedii.

Literatura

KŘIVÁNEK, Jaroslav. Počítačová grafika III. Praha, 2012. Přednáška na Matematicko-fyzikální fakultě Univerzity Karlovy. Dostupné online.

PHARR, Matt; HUMPHREYS, Greg. Physically Based Rendering: From Theory to Implementation. 2. vyd. San Francisco: Morgan Kaufmann, 2010. Dostupné online. ISBN 0123750792. (anglicky) 

VEACH, Eric. Robust Monte Carlo Methods for Light Transport simulation. Stanford, 1998. Disertační práce (PhD.). Stanford University. Dostupné online. (anglicky)

DUTRÉ, Philip; BALA, Kavita; BEKAERT, Philippe. Advanced Global Illumination. 2. vyd. Natick: A. K. Peters, 2006. Dostupné online. ISBN 1568813074. (anglicky) 

Související články

• Obousměrné sledování cest
• Globální osvětlení
• Zobrazovací rovnice
• Radiometrické veličiny
• BRDF
• Monte Carlo integrování

Externí odkazy

• Global Illumination Compendium - Souhrn matematických vztahů souvisejících nejen se sledováním cest ale s globálním osvětlením obecně (anglicky)