Sledování cest

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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

Ukázka scény zobrazené pomocí algoritmu sledování cest.

Historie[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Základní verze algoritmu[editovat | editovat zdroj]

Teoretické pozadí[editovat | editovat zdroj]

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áří L(\mathbf{x},\omega) vyjadřující směrovou hustotu toku světla v bodě \mathbf{x} ve směru \omega. Zář daným bodem emitovaná je typicky značena 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 f_r(\mathbf{x},\omega_i\rightarrow\omega_o) udávající pravděpodobnost, s jakou se světlo dopadající ze směru \omega_i do bodu \mathbf{x} odrazí do směru \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:

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ě \mathbf{x} ve směru \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 \mathbf{x} z libovolného směru hemisféry, která se s pravděpodobností danou BRDF do směru \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á

\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 směr náhodně vygenerovaný podle hustoty pravděpodobnosti p.

Algoritmus[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 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 \cos(\theta)/\pi, kde \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ů[editovat | editovat 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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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

  1. KAJIYA, James T. The rendering equation. In SIGGRAPH '86 Proceedings of the 13th annual conference on Computer graphics and interactive techniques. New York : ACM, 1986. Dostupné online. ISBN 0-89791-196-2. DOI:10.1145/15922.15902 S. 143-150. (anglicky)
  2. LAFORTUNE, Eric. Mathematical Models and Monte Carlo Algorithms for Physically Based Rendering. Ithaca, 1996. Disertační práce (PhD.). Cornell University, Program of Computer Graphics. Dostupné online. (anglicky)
  3. VEACH, Eric; GUIBAS, Leonidas J. Metropolis light transport. In SIGGRAPH '97 Proceedings of the 24th annual conference on Computer graphics and interactive techniques. New York : ACM, 1997. Dostupné online. ISBN 0-89791-896-7. DOI:10.1145/258734.258775 S. 65-76. (anglicky)
  4. PURCELL, Timothy J. Ray Tracing on Programmable Graphics Hardware. In SIGGRAPH '02 Proceedings of the 29th annual conference on Computer graphics and interactive techniques. New York : ACM, 2002. Dostupné online. ISBN 1-58113-521-1. DOI:10.1145/566570.566640 S. 703-712. (anglicky)
  5. ROBISON, Austin. Interactive Ray Tracing on the GPU and NVIRT Overview. Prezentace na I3D 2009. Dostupné online. (anglicky)

Literatura[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

  • 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)