Basic Primitive Tests - Real-Time Collision Detection - page 187

v = -Dot(pa, m); // ScalarTriple(pq, pa, pc);
if (v < 0.0f) return 0;
w = ScalarTriple(pq, pb, pa);
if (w < 0.0f) return 0;

For a double-sided test the same code would instead read:

Vector m = Cross(pq, pc);
u = Dot(pb, m); // ScalarTriple(pq, pc, pb);
v = -Dot(pa, m); // ScalarTriple(pq, pa, pc);
if (!SameSign(u, v)) return 0;
w = ScalarTriple(pq, pb, pa);
if (!SameSign(u, w)) return 0;

It is also possible to recast the arithmetic of this test as

Vector m = Cross(pq, p);
u = Dot(pq, Cross(c, b)) + Dot(m,c-b);
v = Dot(pq, Cross(a, c)) + Dot(m,a-c);
w = Dot(pq, Cross(b, a)) + Dot(m,b-a);

or equivalently as

Vector m = Cross(pq, q);
float s = Dot(m,c-b);
float t = Dot(m,a-c);
u = Dot(pq, Cross(c, b)) + s;
v = Dot(pq, Cross(a, c)) + t;
w = Dot(pq, Cross(b, a))-s-t;

The three cross products C × B , A × C , and B × A are constant for a given tri-

angle, as are the vectors e 0 c . If these are stored with the

triangle, at runtime only one cross product and five dot products need to be evalu-
ated. Because the remaining cross product only depends on values from the line, it
only has to be evaluated once even if the line is tested against many triangles. This
last formulation is equivalent to performing the intersection test with the line PQ
and the triangle edges expressed as lines using Plücker coordinates [Amanatides97].
Brief but good introductions to Plücker coordinates are given in [Erickson97] and
[Shoemake98]. Although a Plücker coordinate formulation results in slightly fewer
floating-point operations (assuming no special dot or cross-product instructions are

= c − b and e 1 = a −