Graphics Reference
In-Depth Information
// Given line pq and ccw quadrilateral abcd, return whether the line
// pierces the triangle. If so, also return the point r of intersection
int IntersectLineQuad(Point p, Point q, Point a, Point b, Point c, Point d, Point &r)
{
Vector pq=q-p;
Vector pa=a-p;
Vector pb=b-p;
Vector pc=c-p;
// Determine which triangle to test against by testing against diagonal first
Vector m = Cross(pc, pq);
float v = Dot(pa, m);
// ScalarTriple(pq, pa, pc);
if (v >= 0.0f) {
// Test intersection against triangle abc
float u = -Dot(pb, m);
// ScalarTriple(pq, pc, pb);
if (u < 0.0f) return 0;
float w = ScalarTriple(pq, pb, pa);
if (w < 0.0f) return 0;
// Compute r, r = u*a + v*b + w*c, from barycentric coordinates (u, v, w)
float denom = 1.0f / (u+v+w);
u *= denom;
v *= denom;
w *= denom;
//w=1.0f-u-v;
r = u*a + v*b + w*c;
} else {
// Test intersection against triangle dac
Vector pd=d-p;
float u = Dot(pd, m);
// ScalarTriple(pq, pd, pc);
if (u < 0.0f) return 0;
float w = ScalarTriple(pq, pa, pd);
if (w < 0.0f) return 0;
v = -v;
// Compute r, r = u*a + v*d + w*c, from barycentric coordinates (u, v, w)
float denom = 1.0f / (u+v+w);
u *= denom;
v *= denom;
w *= denom;
//w=1.0f-u-v;
r = u*a + v*d + w*c;
}
return 1;
}
This particular intersection method can also be used for testing against a concave
quadrilateral, assuming the diagonal fully interior to the quadrilateral is used for the
