1. coursebook
  2. poznámky k pg

Průsečík trojúhelníku s paprskem

Algoritmů na hledání průsečíku paprsku a trojúhelníku existuje řada, lze je vyhledat pod heslem ray-triangle intersection.

Test incidenční operace by měl být implementován co nejefektivněji, je doporučeno použít např. Möller-Trumbornův algoritmus [1].

Je skutečně nutné se zabývat rychlým výpočtem průsečíku? Odpověď by mohl rychle nabídnout následující příklad:

Cílem je vyrobit obraz o rozlišení $1000 \times 1000$ pixelů, což v té nejjednodušší variantě vyžaduje vrhnutí $10^6$ primárních paprsků. Během generování obrazu je nutné provádět také jiné operace než jen výpočet průsečíků, dobu strávenou těmito výpočty označme $\varepsilon$. Dále mějme $n$ objektů ve scéně. Pokud bude nejbližší objekt vyhledáván zcela naivně (otestuje se průsečík paprsku a každého objektu), bude třeba provádět $n \times 10^6$ testů. Dobrou otázkou je, kolik je $n$. Pro malé scény lze uvažovat $n$ do tisíců, pro složitější scény milióny a více. To ve výsledku může vést např. na $\thicksim 10^{9}$ testů na snímek. Kdyby bylo cílem dosáhnout snímkovací frekvence $30\; \text{fps}$, je třeba jeden test provést za \begin{equation} \frac{\frac{1}{30} - \varepsilon}{10^{9}} \approx_{\varepsilon \rightarrow 0} 0.03\; \text{[ns]}, \end{equation} což je prakticky těžko proveditelné. Pro srovnání - procesor s taktem 3 GHz provede jeden takt za 0.3 ns. Tento odhad navíc vyžaduje zanedbání jakéhokoliv času potřebného na ostatní výpočty ($\varepsilon \rightarrow 0$). Předchozí odhad nám dává motivaci optimalizovat testovací proceduru a strategii testování.

Barycentrické souřadnice

Je vhodné zabývat se tím, jakým způsobem je možné vyjádřit souřadnice bodu vůči trojúhelníku. Každý trojúhelník je možné plně definovat třemi body $\mathbf{a},\mathbf{b},\mathbf{c}$. Všechny body ležící v rovině tohoto trojúhelníku je pak možné zapsat pomocí barycentrických souřadnic $x, y, z$ jako \begin{equation} \label{eq:plane} \mathbf{p} = x\mathbf{a} + y\mathbf{b} + z\mathbf{c}. \end{equation} tak, že $x + y + z = 1$. Nabízí se následující odvození:

Začněme se dvěma body $\mathbf{a}, \mathbf{b}$. Chceme-li proložit přímku těmito body, je možné ji zapsat například jako: \begin{align} \mathbf{p} &= \mathbf{a} + u(\mathbf{b} - \mathbf{a}),\\ \mathbf{p} &= (1 - u)\mathbf{a} + u\mathbf{b}. \end{align}

Nyní přidejme bod $\mathbf{c}$ tak, aby neležel na přímce s body $\mathbf{a},\mathbf{b}$ ($\mathbf{a}, \mathbf{b}, \mathbf{c}$ nejsou kolineární). Z bodů $\mathbf{a},\mathbf{b},\mathbf{c}$ je možné sestrojit rovinu: \begin{align} \mathbf{p} &= \mathbf{a} + u(\mathbf{b} - \mathbf{a}) + v(\mathbf{c} - \mathbf{a}),\label{eq:triangle}\\ \mathbf{p} &= (1 - u - v)\mathbf{a} + u\mathbf{b} + v\mathbf{c}. \end{align}

Z rovnic výše by mělo být patrné následující:

barycentrické souřadnice

Ilustrace algoritmu pro výpočet průsečíku paprsku a trojúhelníku

Möller-Trumbornův algoritmus

Pro průsečík paprsku a roviny ve které leží trojúhelník pak platí \begin{equation} \mathbf{o} + t\mathbf{s} = \mathbf{a} + u(\mathbf{b} - \mathbf{a}) + v(\mathbf{c} - \mathbf{a}). \end{equation} Pokud je cílem zjistit, zda průsečík leží uvnitř trojúhelníku, je nutné ověřit podmínky $u + v \leq 1$ a $u, v \geq 0$. Výraz výše je možné upravit do maticového zápisu: \begin{equation} \label{eq:matintersection} \begin{bmatrix} -\mathbf{s} & \left(\mathbf{b} - \mathbf{a}\right) & \left(\mathbf{c} - \mathbf{a}\right) \end{bmatrix} \begin{bmatrix} t \\ u \\ v \\ \end{bmatrix} = \mathbf{o} - \mathbf{a} \end{equation}

Takto lze dostat tři lineární rovnice o třech neznámých. Tuto soustavu je možné řešit různými způsoby, důležité je:

Möller-Trumbornův algoritmus [1] využívá pro řešení soustavy Cramerovo pravidlo: \begin{equation} \mathbf{A}\mathbf{x} = \mathbf{b},\;x_i = \frac{\text{det}\,\mathbf{A}_i}{\text{det}\,\mathbf{A}} \end{equation} kde $\mathbf{A}$ musí být regulární a $\mathbf{A}_i$ je matice kde v $i$-tém sloupci je vektor $\mathbf{b}$. Počítání determinantu může být opět drahou operací, dá se efektivně zrychlit pomocí následujících identit: \begin{align*} \begin{vmatrix} \mathbf{a} & \mathbf{b} & \mathbf{c} \end{vmatrix} &= \phantom{-}\mathbf{a} \cdot \left( \mathbf{b} \times \mathbf{c} \right)\\ &= -\mathbf{a} \cdot \left( \mathbf{c} \times \mathbf{b} \right)\\ &= -\mathbf{b} \cdot \left( \mathbf{a} \times \mathbf{c} \right) \end{align*} Naivní implementaci řešení rovnice v maticovém zápisu je možné optimalizovat tak, aby byl minimalizován počet prováděných vektorových součinů, dělení a zároveň aby bylo možné rychle výpočet ukončit, pokud se průsečík nachází mimo trojúhelník. Optimalizovaná verze je popsaná pseudokódem níže.

Vstup: paprsek: $\mathbf{o}$, $\mathbf{s}$, trojúhelník: $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$ Výstup: parametr $t$ $\varepsilon \gets \textit{epsilon, value really close to zero}$ $\mathbf{e}_1 \gets \mathbf{b} - \mathbf{a}$ $\mathbf{e}_2 \gets \mathbf{c} - \mathbf{a}$ $\mathbf{p} \gets \mathbf{s} \times \mathbf{e}_2$ $d \gets \mathbf{e}_1 \times \mathbf{p}$ If $\textit{cull_backfaces}$: If $d < \varepsilon$: return $\infty$ else: If $\lvert d\rvert < \varepsilon$: return $\infty$ $d_{inv} \gets \frac{1}{d}$ $\mathbf{q} \gets \mathbf{o} - \mathbf{a}$ $u \gets d_{inv}(\mathbf{q} \cdot \mathbf{p})$ If $u < 0 \vee u > 1$: return $\infty$ $\mathbf{r} \gets \mathbf{q} \times \mathbf{e}_1$ $v \gets d_{inv}(\mathbf{r} \cdot \mathbf{s})$ If $v < 0 \vee u + v > 1$: return $\infty$ $t \gets d_{inv}(\mathbf{e}_2 \cdot \mathbf{r})$ return $t$

Literatura

  1. T. Möller and B. Trumbore, “Fast, minimum storage ray-triangle intersection,”Journal of graphics tools, vol. 2, no. 1, pp. 21–28, 1997