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

for unprocessed triangles in Section 3.4 (on barycentric coordinates) and one for
preprocessed triangles in Section 5.3.6.
A third solution is to take the triangle ABC and the query point P in the plane
of the triangle and translate both so that P lies at the origin. The test now becomes
that of checking if the origin is contained in the translated triangle (which will still
be referred to as ABC throughout).
P lies inside ABC if and only if the triangles PAB , PBC , and PCA are all either
clockwise or counterclockwise. Because P is at the origin, this is now equivalent to
testing if the cross products u

= B × C , v = C × A , and w = A × B all point

in the same direction; that is, if u · v ≥ 0 and u · w ≥ 0. Implemented, this test

becomes:

// Test if point P lies inside the counterclockwise triangle ABC
int PointInTriangle(Point p, Point a, Point b, Point c)
{

// Translate point and triangle so that point lies at origin
a-=p;b-=p;c-=p;
// Compute normal vectors for triangles pab and pbc
Vector u = Cross(b, c);
Vector v = Cross(c, a);
// Make sure they are both pointing in the same direction
if (Dot(u, v) < 0.0f) return 0;
// Compute normal vector for triangle pca
Vector w = Cross(a, b);
// Make sure it points in the same direction as the first two
if (Dot(u, w) < 0.0f) return 0;
// Otherwise P must be in (or on) the triangle
return 1;

}

If cross products are more expensive than dot products, Lagrange's identity allows
this test to be written in terms of just five dot products.

// Test if point P lies inside the counterclockwise 3D triangle ABC
int PointInTriangle(Point p, Point a, Point b, Point c)
{

// Translate point and triangle so that point lies at origin
a-=p;b-=p;c-=p;
float ab = Dot(a, b);
float ac = Dot(a, c);
float bc = Dot(b, c);
float cc = Dot(c, c);