Graphics Reference
In-Depth Information
As det
abc
c
), the algebraic identities for scalar triple products
allow these expressions to be simplified to
=
a
·
(
b
×
=
−
·
t
(
P
A
)
n
/
d
v
=
(
C
−
A
)
·
e
/
d
w
=−
(
B
−
A
)
·
e
/
d
,
where
n
=
(
B
−
A
)
×
(
C
−
A
)
d
=
(
P
−
Q
)
·
n
=
−
×
−
e
(
P
Q
)
(
P
A
).
Note that if
d
<
0 the segment points away from the triangle, and if
d
=
0 the
segment runs parallel to the plane of the triangle.
The following code implements this variant of segment-triangle intersection.
// Given segment pq and triangle abc, returns whether segment intersects
// triangle and if so, also returns the barycentric coordinates (u,v,w)
// of the intersection point
int IntersectSegmentTriangle(Point p, Point q, Point a, Point b, Point c,
float &u, float &v, float &w, float &t)
{
Vector ab=b-a;
Vector ac=c-a;
Vector qp=p-q;
// Compute triangle normal. Can be precalculated or cached if
// intersecting multiple segments against the same triangle
Vector n = Cross(ab, ac);
// Compute denominator d. If d <= 0, segment is parallel to or points
// away from triangle, so exit early
float d = Dot(qp, n);
if (d <= 0.0f) return 0;
// Compute intersection t value of pq with plane of triangle. A ray
// intersects iff 0 <= t. Segment intersects iff 0 <= t <= 1. Delay
// dividing by d until intersection has been found to pierce triangle