Graphics Reference
In-Depth Information
the halfspaces. (To intersect a ray against the intersection volume,
t
last
would instead
initially be set to
+∞
. For a line, additionally
t
first
would be initially set to
−∞
.)
Now recall that for a segment
S
(
t
)
=
A
+
t
(
B
−
A
), 0
≤
t
≤
1, and a plane
n
·
X
=
d
A
)
(
n
the intersection of the segment and the plane is given by
t
=
(
d
−
n
·
·
(
B
−
A
)).
Thus, the plane faces the segment if the denominator
n
A
) is negative, and if the
denominator is positive the plane faces away from the segment. When the denomina-
tor is zero, the segment is parallel to the plane. When the plane faces the segment, the
computed
t
is the parameterized value corresponding to the point at which the seg-
ment is entering the halfspace. As a consequence, if
t
is
greater
than
t
first
the segment
must be clipped by setting
t
first
to the current value of
t
. When the plane faces away
from the segment,
t
corresponds to the parameterized value at the point the segment
is exiting the halfspace. Therefore, if
t
is less than
t
last
,
t
last
must be set to the current
value of
t
. If ever
t
last
·
(
B
−
t
first
, the segment has disappeared and there is no intersection.
The segment running parallel to the plane must be handled as a special case. If the
segment lies outside the halfspace, parallel to the defining plane, the segment cannot
be intersecting the polyhedron and the test can immediately return“no intersection.”If
the segment lies inside the halfspace, the plane can simply be ignored and processing
may continue with the next plane. To determine whether the segment lies inside or
outside the halfspace, either endpoint of the segment may be tested against the plane
by insertion into the plane equation, the sign of the result determining the sidedness
of the point.
Figure 5.27 gives a 2D illustration of how a ray is clipped against a number of half-
spaces and how the logical intersection of the ray being clipped against each halfspace
forms the part of the ray that overlaps the intersection volume. The following function
implements the test just described.
<
// Intersect segment S(t)=A+t(B-A), 0<=t<=1 against convex polyhedron specified
// by the n halfspaces defined by the planes p[]. On exit tfirst and tlast
// define the intersection, if any
int IntersectSegmentPolyhedron(Point a, Point b, Plane p[], int n,
float &tfirst, float &tlast)
{
// Compute direction vector for the segment
Vectord=b-a;
// Set initial interval to being the whole segment. For a ray, tlast should be
// set to +FLT_MAX. For a line, additionally tfirst should be set to -FLT_MAX
tfirst = 0.0f;
tlast = 1.0f;
// Intersect segment against each plane
for(inti=0;i
<
n; i++) {
float denom = Dot(p[i].n, d);
float dist = p[i].d - Dot(p[i].n, a);
// Test if segment runs parallel to the plane
