Graphics Reference
In-Depth Information
Vector f0 = v1 - v0,
f1 = v2 - v1, f2 = v0 - v2;
// Test axes a00..a22 (category 3)
// Test axis a00
p0 = v0.z*v1.y - v0.y*v1.z;
p2 = v2.z*(v1.y - v0.y) - v2.z*(v1.z - v0.z);
r = e1 * Abs(f0.z) + e2 * Abs(f0.y);
if (Max(-Max(p0, p2), Min(p0, p2)) > r) return 0;
// Axis is a separating axis
// Repeat similar tests for remaining axes a01..a22
...
// Test the three axes corresponding to the face normals of AABB b (category 1).
// Exit if...
// ... [-e0, e0] and [min(v0.x,v1.x,v2.x), max(v0.x,v1.x,v2.x)] do not overlap
if (Max(v0.x, v1.x, v2.x) < -e0 || Min(v0.x, v1.x, v2.x) > e0) return 0;
// ... [-e1, e1] and [min(v0.y,v1.y,v2.y), max(v0.y,v1.y,v2.y)] do not overlap
if (Max(v0.y, v1.y, v2.y) < -e1 || Min(v0.y, v1.y, v2.y) > e1) return 0;
// ... [-e2, e2] and [min(v0.z,v1.z,v2.z), max(v0.z,v1.z,v2.z)] do not overlap
if (Max(v0.z, v1.z, v2.z) < -e2 || Min(v0.z, v1.z, v2.z) > e2) return 0;
// Test separating axis corresponding to triangle face normal (category 2)
Plane p;
p.n = Cross(f0, f1);
p.d = Dot(p.n, v0);
return TestAABBPlane(b, p);
}
Note that there are robustness issues related to the tests of categories 2 (in com-
puting the face normal for a degenerate or oversized triangle) and 3 (the cross product
of two parallel edges giving a zero vector). See Section 5.2.1.1 for a discussion of what
has to be done to cover these cases in a fully robust implementation.
The topic of triangle-AABB overlap testing is discussed in [Voorhies92]. A test of
arbitrary polygons against an AABB is given in [Green95].
5.2.10
Testing Triangle Against Triangle
Many algorithms have been suggested for detecting the intersection of two triangles
ABC
and
DEF
. The most straightforward test is based on the fact that in general when
two triangles intersect either two edges of one triangle pierce the interior of the other
or one edge from each triangle pierces the interior of the other triangle (Figure 5.19).
