Graphics Reference
In-Depth Information
// If c and d are on different sides of ab, areas have different signs
if (a1 * a2 < 0.0f) {
// Compute signs for a and b with respect to segment cd
float a3 = Signed2DTriArea(c, d, a);
// Compute winding of cda (+ or -)
// Since area is constant a1 - a2 = a3 - a4, or a4 = a3 + a2 - a1
//
float a4 = Signed2DTriArea(c, d, b); // Must have opposite sign of a3
float a4 = a3 + a2 - a1;
// Points a and b on different sides of cd if areas have different signs
if (a3 * a4 < 0.0f) {
// Segments intersect. Find intersection point along L(t)=a+t*(b-a).
// Given height h1 of an over cd and height h2 of b over cd,
//t=h1/(h1-h2)=(b*h1/2) / (b*h1/2 - b*h2/2) = a3 / (a3 - a4),
// where b (the base of the triangles cda and cdb, i.e., the length
// of cd) cancels out.
t = a3 / (a3 - a4);
p=a+t*(b-a);
return 1;
}
}
// Segments not intersecting (or collinear)
return 0;
}
Here, the expression
a1 * a2 < 0.0f
is used to test if
a1
and
a2
have different signs
(and similarly for
a3
and
a4
). When working with signed integers, a better alternative
is to use exclusive-or instead of multiplication,
a1
∧
a2<0
, thereby avoiding potential
problems with overflow. In the presence of collinear points, either or both of
a1
and
a2
may be zero. To detect proper intersections in these cases, the test would have to
be written along the lines of:
if (a1 != 0.0f && a2 != 0.0f && a1*a2 < 0.0f) ...
// for floating-point variables
if ((a1 | a2) != 0 && a1
∧
a2<0)...
// for integer variables
Finally, note that for some applications it is worthwhile to test if the bounding
boxes of
AB
and
CD
overlap before proceeding with one of these segment intersec-
tion tests. This is especially true for determining intersection of line segments in 3D,
for which the involved computations are more expensive.
5.1.10
Closest Points of a Line Segment and a Triangle
The closest pair of points between a line segment
PQ
and a triangle
ABC
is not
necessarily unique. When the segment is parallel to the plane of the triangle, there
