Ray Intersect with Triangle

文章最后更新时间为：2023 年 06 月 14 日 15:25:48

This note shows how to compute the intersection between ray and triangle.

Ray can be represented as $\vec{o} + t\vec{d}$.

Triangle composes with three vertices $\vec{v}_0, \vec{v}_1, \vec{v}_2$.

Any point in the same plane as this triangle can be represented as $a(\vec{v}_1-\vec{v}_0) + b(\vec{v}_2-\vec{v}_0) + \vec{v}_0$ where $a, b$ are scalars.

Combine the ray equation and above equation,

$$ \begin{aligned} \vec{o} + t\vec{d} &= a(\vec{v}_1 - \vec{v}_0) + b(\vec{v}_2 - \vec{v}_0) + \vec{v}_0\\ \vec{o} - \vec{v}_0 &= a(\vec{v}_1-\vec{v}_0) + b(\vec{v}_2-\vec{v}_0) - t\vec{d}\\ &= \begin{bmatrix} -t\\ b\\ a \end{bmatrix} \begin{bmatrix} \vec{d} & \vec{v}_2 - \vec{v}_0 & \vec{v}_1 - \vec{v}_0 \end{bmatrix} \end{aligned} $$

Let $\vec{e}_1 = \vec{v}_1 - \vec{v}_0, \vec{e}_2 = \vec{v}_2 - \vec{v}_0$. Then

$$ \begin{aligned} \vec{o}-\vec{v}_0 &= \begin{bmatrix} -t\\ b\\ a \end{bmatrix} \begin{bmatrix} \vec{d} & \vec{e}_2 & \vec{e}_1 \end{bmatrix}\\ \begin{bmatrix} -t\\ b\\ a \end{bmatrix} &= \begin{bmatrix} \vec{d} & \vec{e}_2 & \vec{e}_1 \end{bmatrix}^{-1}(\vec{o}-\vec{v}_0) \end{aligned} $$

For convenience, let $T = \begin{bmatrix}\vec{d} & \vec{e}_2 & \vec{e}_1\end{bmatrix}$. And we know that

$$ T^{-1} = \frac{1}{\det(T)}\operatorname{adj}(T) $$

where

$$ \begin{aligned} \det(T) &= \vec{e} \cdot(\vec{d}\times \vec{e}_2)\\ \operatorname{adj}(T) &= \begin{bmatrix} (\vec{e}_2\times \vec{e}_1)^\top\\ (\vec{e}_1\times \vec{d})^\top\\ (\vec{d}\times \vec{e}_2)^\top \end{bmatrix} \end{aligned} $$

Then

$$ \begin{aligned} t \cdot \det(T) &= -(\vec{o} - \vec{v}_0)\cdot (\vec{e}_2 \times \vec{e}_1)\\ &= (\vec{o} - \vec{v}_0)\cdot (\vec{e}_1 \times \vec{e}_2)\\ &= \vec{e}_2 \cdot [(\vec{o}-\vec{v}_0)\times \vec{e}_1]\\ b\cdot \det(T) &= (\vec{o}-\vec{v}_0) \cdot (\vec{e}_1\times \vec{d})\\ &= \vec{d} \cdot [(\vec{o}-\vec{v}_0)\times \vec{e}_1]\\ a \cdot \det(T) &= (\vec{o} - \vec{v}_0) \cdot (\vec{d}\times \vec{e}_2) \end{aligned} $$

We can finally obtain $a, b$ and $t$ through the above formula. If $0 \le a \le 1, 0 \le b \le 1$ and $a + b \le 1$, we can conclude that there is an intersection between the ray and this triangle.