up to Schedule & Notes

Ray/Triangle Intersection

We need to compute the intersection of a ray, $P+tD$, with a triangle $\bigtriangleup v_0 v_1 v_2$.

The triangle lies on a plane $\{ x \; | \; n \cdot x - d = 0 \}$.

At the point of intersection, $$n \cdot (P + tD) - d = 0$$

So we can solve for $t$: $$t = {d - n \cdot P \over n \cdot D}$$

Then let $x = P + tD$.

Point in Triangle

We need to determine whether $x$, the point on the triangle's plane, is actually inside the triangle.

We can write $x$ as a linear combination of $v_0$, $v_1$, and $v_2$, $$x = v_0 + \alpha \; (v_1-v_0) + \beta \; (v_2-v_0)$$

as shown below:

Then $x$ is in $\bigtriangleup v_0 v_1 v_2$ if and only if

$\alpha \geq 0$

$\beta \geq 0$

$\alpha + \beta \leq 1$

as shown below:

Barycentric Coordinates

The point $x$ can be written in the barycentric coordinate system of $v_0$, $v_1$, and $v_2$: $$\begin{array}{rcll} x & = & v_0 + \alpha \; (v_1-v_0) + \beta \; (v_2-v_0) \\ & = & (1 - \alpha - \beta) \; v_0 + \alpha \; v_1 + \beta \; v_2 \\ & = & \gamma \; v_0 + \alpha \; v_1 + \beta \; v_2 & \textrm{where } \gamma = 1 - \alpha - \beta \\ \end{array}$$

Then $x$ has barycentric coordinates $(\alpha,\beta,\gamma)$ and is in $\bigtriangleup v_0 v_1 v_2$ if and only if

$\alpha \geq 0$

$\beta \geq 0$

$\gamma \geq 0$

How do we compute $\alpha$, $\beta$, and $\gamma$ for $x$?

Since $\gamma = 1 - \alpha - \beta$, we only need to find $\alpha$ and $\beta$.

Computing the Barycentric coordinates

Let $\widehat{x} = x - v_0$, let $a = v_1 - v_0$, and let $b = v_2 - v_0$

Then $$\begin{array}{rcl} x &=& v_0 + \alpha (v_1-v_0) + \beta (v_2-v_0) \\ x - v_0 &=& \alpha (v_1-v_0) + \beta (v_2-v_0) \\ \widehat{x} &=& \alpha\ a + \beta\ b \end{array}$$

This can be written in matrix form: $$ \left[\begin{array}{cc} \vdots & \vdots \\ a & b \\ \vdots & \vdots \end{array}\right] \left[\begin{array}{c} \alpha \\ \beta \end{array}\right] = \left[\begin{array}{c} \vdots \\ \widehat{x} \\ \vdots \end{array}\right] $$

If $a$, $b$, and $\widehat{x}$ were 2D vectors, it would be easy to invert the $2 \times 2$ matrix, $\left[ a\ b \right]$, and solve for $\alpha$ and $\beta$.

However, these are 3D vectors and the matrix on the left has no inverse.

We can solve this matrix equation using the "normal form" in which each side of the original equation is projected onto the 2D $\langle a, b \rangle$ subspace: $$ \left[\begin{array}{c} \cdots a \cdots \\ \cdots b \cdots \\ \end{array}\right] \left[\begin{array}{cc} \vdots & \vdots \\ a & b \\ \vdots & \vdots \end{array}\right] \left[\begin{array}{c} \alpha \\ \beta \end{array}\right] = \left[\begin{array}{c} \cdots a \cdots \\ \cdots b \cdots \\ \end{array}\right] \left[\begin{array}{c} \vdots \\ \widehat{x} \\ \vdots \end{array}\right] $$

Then the problem becomes $$ \left[\begin{array}{cc} a \cdot a & a \cdot b \\ b \cdot a & b \cdot b \\ \end{array}\right] \left[\begin{array}{c} \alpha \\ \beta \end{array}\right] = \left[\begin{array}{cc} a \cdot \widehat{x} \\ b \cdot \widehat{x} \\ \end{array}\right] $$

Now we have a $2 \times 2$ matrix and can invert it to find $\alpha$ and $\beta$.

Summary

To find whether a point, $x$, is in a triangle $\bigtriangleup v_0 v_1 v_2$, compute $x$'s barycentric coordinates, $(\alpha, \beta, \gamma$) as above, and see whether they are all positive.

up to Schedule & Notes