Graphics Reference
In-Depth Information
coordinates of
R
. It is now straightforward to derive the code for testing a line
PQ
against a counterclockwise triangle
ABC
and computing the barycentric coordinates
of the intersection point, if any.
//Given line pq and ccw triangle abc, return whether line pierces triangle. If
//so, also return the barycentric coordinates (u,v,w) of the intersection point
int IntersectLineTriangle(Point p, Point q, Point a, Point b, Point c,
float &u, float &v, float &w)
{
Vector pq=q-p;
Vector pa=a-p;
Vector pb=b-p;
Vector pc=c-p;
// Test if pq is inside the edges bc, ca and ab. Done by testing
// that the signed tetrahedral volumes, computed using scalar triple
// products, are all positive
u = ScalarTriple(pq, pc, pb);
if (u < 0.0f) return 0;
v = ScalarTriple(pq, pa, pc);
if (v < 0.0f) return 0;
w = ScalarTriple(pq, pb, pa);
if (w < 0.0f) return 0;
// Compute the barycentric coordinates (u, v, w) determining the
// intersection point r,r=u*a+v*b+w*c
float denom = 1.0f / (u+v+w);
u *= denom;
v *= denom;
w *= denom;
//w=1.0f-u-v;
return 1;
}
For robustness, the case in which
PQ
lies in the plane of
ABC
must be handled
separately.
PQ
is in the plane of
ABC
when
u
=
v
=
w
=
0, which would result in a
division-by-zero error if left unhandled.
The code can be optimized further by rearranging the terms in the triple scalar
products'expressions so that a cross product is shared between two of them, turning
the middle section of code into:
Vector m = Cross(pq, pc);
u = Dot(pb, m);
// ScalarTriple(pq, pc, pb);
if (u < 0.0f) return 0;
