Chapter 31: Triangles
For spheres and planes, we plugged the ray equation into the equation of the shape in question to solve for intersection. But what is the equation for a triangle? We have the plane equation, and we have line equations for each edge. We could find the plane intersection point, then check against each line. In fact, this is how you can support arbitrary polygons, but there are more convenient representations for triangles.
Review: Barycentric Coordinates
Barycentric coordinates of point in terms of , , and are the numbers , , and such that:
With the constraint:
This must be true if the three values are barycentric coordinates.
However, the values don’t have to be positive.
A point is inside the the triangle if and only if:
What does mean? Any point opposite the vertex , or rather along the line from to .
What about ? In this case we know must be , this is the vertex.
The center of the triangle is
One interesting thing to note is that we’re really defining a coordinate system with, e.g., origin and basis vectors and
Let’s plug in our standard ray equation:
Since this is a vector form it is really three different equations:
Here we have three equations and three unknowns - , , and . It’s a linear system we can solve using matrix algebra. First let’s move all the unknowns to one side:
Let’s rewrite in matrix form:
This is a linear system of the form:
This 3x3 linear system can be solved by finding the inverse of the matrix.
However, we don’t need to compute the inverse explicitly - there is a faster option.
Given a linear system of the form
where is the matrix formed by replacing the th column of by the column vector .
The denominator gives us an obvious way to test for intersection - if this is 0, there is no intersection. Cramer’s rule is also convenient because it permits solving for individual elements of the solution vector. So, we can solve for and check if it’s positive. Them, we can solve for and check , etc.
Recall, to compute the 2x2 determinant:
And for a 3x3 determinant:
Note the pattern of (+) (-) (+) for the three 2x2 determinants. We can compute this “expansion” of the determinant using any row or column, not just the first row (as in this example). However, if you use the middle row or middle column, you flip the signs to (-) (+) (-)
Below are the results of applying Cramer’s rule. Note the vertical bars around a matrix mean to compute the determinant.
3x3 matrices have common subterms that can be exploited by carefully naming variables. Lets look at generic form with dummy variables.
Solving for determinants expands to (here we expand the determinant on the third column purposefully):
The expression is found in two places - instead of computing this twice, you can create a variable for it, compute once, and use it twice. Of course, also save the denominator value - it is the same for all three variables.
Similarly, we can purposefully expand both and computations to share expressions.
Which we can then manipulate to create common terms with the solution.
Arguably, this also makes cleaner and easier to read/verify code.
hit_tri(ray r, vert a, vert b, vert c, t0, t1) compute t if (t < t0) || (t > t1) then return false compute gamma if (gamma < 0) || (gamma > 1) then return false compute beta if (beta < 0) || (beta > 1 - gamma) then return false return true