Ray Casting and Rasterization - Computer Graphics: Principles and Practice - page 410

Listing 15.16: Ray-triangle intersection (derived from [MT97])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

float intersect( const Ray &R, const Triangle &T, float weight[3]) {
const Vector3 & e1 = T.vertex(1) - T.vertex(0);
const Vector3 & e2 = T.vertex(2) - T.vertex(0);
const Vector3 & q = R.direction().cross(e2);

const float a = e1.dot(q);

const Vector3 & s = R.origin() - T.vertex(0);
const Vector3 & r = s.cross(e1);

// Barycentric vertex weights
weight[1] = s.dot(q) / a;
weight[2] = R.direction().dot(r) / a;
weight[0] = 1.0f - (weight[1] + weight[2]);

const float dist = e2.dot(r) / a;

static const float epsilon = 1e-7f;
static const float epsilon2 = 1e-10;

if ((a <= epsilon) || (weight[0] < -epsilon2) ||
(weight[1] < -epsilon2) || (weight[2] < -epsilon2) ||
(dist <= 0.0f)) {
// The ray is nearly parallel to the triangle, or the
// intersection lies outside the triangle or behind
// the ray origin: "infinite" distance until intersection.
return INFINITY;
} else {
return dist;

}

}

will be missed at glancing angles, and this missed intersection behavior will be
more likely to occur at triangles with large areas than at those with small areas.
Note that if we changed the test to fabs(a)<= epsilon , then triangles would
have two sides. This is not necessary for correct models of real, opaque objects;
however, for rendering mathematical models or models with errors in them it can
be convenient. Later we will depend on optimizations that allow us to quickly cull
the (approximately half) of the scene representing back faces, so we choose to
render single-sided triangles here for consistency.
The epsilon2 constant allows a ray to intersect a triangle slightly outside the
bounds of the triangle. This ensures that triangles that share an edge completely
cover pixels along that edge despite numerical precision limits. If epsilon2 is
too small, then single-pixel holes will very occasionally appear on that edge. If it
is too large, then all triangles will visibly appear to be too large.
Depending on your processor architecture, it may be faster to perform an early
test and potential return rather than allowing not-a-number and infinity propaga-
tion in the ill-conditioned case where a ≈ 0 . Many values can also be precom-
puted, for example, the edge lengths of the triangle, or at least be reused within
a single intersection, for example, 1.0f / a . There's a cottage industry of opti-
mizing this intersection code for various architectures, compilers, and scene types
(e.g., [MT97] for scalar processors versus [WBB08] for vector processors). Let's
forgo those low-level optimizations and stick to high-level algorithmic decisions.
In practice, most ray casters spend very little time in the ray intersection code
anyway. The fastest way to determine if a ray intersects a triangle is to never ask