Ray-triangle intersection

From DmWiki

A triangle is given by its three points. Since the triangle is the most fundamental element in rendering, it is always handy to have a slew of algorithms at hand to deal with them. To find an intersection between a ray and a triangle, various methods exist.

[edit]

Barycentric coordinate test

Each point on a triangle can be defined by its barycentric coordinates : $w A + u B + v C = P$ . As long as the barycentric coordinates u, v and w sum up to one, the point p is lying on the triangle. Since we know that u, v and w always have to sum up to one, we can immediately substitute one of the barycentric coordinates with the other two.

P = (1 - u - v) A + u B + v C

and more conveniently

u (B - A) + v (C - A) = P - A

where $u \ge 0, v \ge 0, u + v \le 1$

To find an intersection with a ray given by its origin O and its direction D we first want to find the intersection between the ray and the plane the triangle is lying in. This can be easily achieved using the triangle's normal given by :

$N = (B - A) \times (C - A)$

and a point on the triangle.

$distance = -\frac{(O - A) \cdot N}{D \cdot N}$

Notice that we can terminate the algorithm early at this point if the distance is smaller than 0 (point is behind ray origin and thus invisible). Inserting distance into the parametric ray equation gives us the point where the ray intersects the plane.

$P = O + distance \cdot D$

Given this point we can solve the barycentric coordinate equation for u and v. While it would be possible to do so in three dimensions there is a trick that applies to barycentric coordinates that is going to make our lives a whole lot easier. Projecting the triangle into any other plane, except one that is orthogonal to the triangles plane will not change the barycentric coordinates of the triangle. What at first sounds like a technicality now allows us to simplify our computations, since we can choose any of the coordinate system's three axis-aligned planes to project our triangle, thus throwing away one of the three coordinates and reducing the barycentric equations to R². For reasons of numerical stability we want to choose the dominant axis of the triangles normal for the projection.

Before we compute the actual barycentric coordinates of the ray-plane intersection point I'd like to do a few substitutions.

b = (B' - A'), c = (C' - A'), p = (P' - A')

, where $A', B', C', P' \in \mathbb{R}^2$ are

A, B, C

and

P

respectively with the dominant axis removed.

Solving for u this gives us :

$\begin{matrix} ub_{x} + vc_{x} & = & p_{x}\\ v & = & \frac{p_{x} - ub_{x}}{c_{x}}\\ ub_{y} + \frac{p_{x} - ub_{x}}{c_{x}} c_{y} & = & p_{y}\\ ub_{y} \cdot c_{x} + p_{x}c_{y} - ub_{x}c_{y} & = & p_{y} \cdot c_{x}\\ ub_{y}c_{x} - ub_{x}c_{y} & = & p_{y}c_{x} - p_{x}c_{y}\\ ub_{y}c_{x} - ub_{x}c_{y} & = & p_{y}c_{x} - p_{x}c_{y}\\ u(b_{y}c_{x} - b_{x}c_{y}) & = & p_{y}c_{x} - p_{x}c_{y}\\ u & = & \frac{p_{y}c_{x} - p_{x}c_{y}}{b_{y}c_{x} - b_{x}c_{y}}\\ \end{matrix}$

v can be computed analogously : $v = \frac{p_{y}b_{x} - p_{x}b_{y}}{c_{y}b_{x} - c_{x}b_{y}}$ .

All that is left to do now is check wether $u \ge 0, v \ge 0, u + v \le 1$

[edit]

Optimizations

Of course a lot of the computations involved can be computed once. For example the triangle's normal might not change for static geometry. Even if it does it will be beneficial to compute it once per frame since there might be many ray-triangle intersections per frame.

Another less obvious point of precomputation are the two computations for u and v. Seemingly all three triangle points are involved and need to be passed to the intersection algorithm, since the term in the u and v computations depends on them. If we carefully rearrange the terms :

$\begin{matrix} u & = & \frac{p_{y}c_{x} - p_{x}c_{y}}{b_{y}c_{x} - b_{x}c_{y}}\\ \ & = & \frac{1}{b_{y}c_{x} - b_{x}c_{y}} \cdot (p_{y}c_{x} - p_{x}c_{y})\\ \ & = & \frac{1}{b_{y}c_{x} - b_{x}c_{y}} \cdot (c_{x}P_{y} - c_{x}A_{y} - c_{y}P_{x} + c_{y}A_{x})\\ \ & = & \frac{c_{x}}{b_{y}c_{x} - b_{x}c_{y}} \cdot P_{y} + \frac{-c_{y}}{b_{y}c_{x} - b_{x}c_{y}} \cdot P_{x} + \frac{c_{y}A_{x} - c_{x}A_{y}}{b_{y}c_{x} - b_{x}c_{y}} \end{matrix}$

Now the term only depends on the point of intersection between the triangle's plane and the ray, which we compute from the triangle's normal only. Thus we have eliminated the need to store the triangle's actual geometry throughout the intersection test. To compute the intersection we now only need to store the following data : The triangle's projected normal, the $A \cdot N$ term that is in the distance to plane equation, the dominant axis of the normal and the 6 factors used in the equations to compute the barycentric coordinates of the ray hitpoint.