Graphics Reference
In-Depth Information
t = (-b - Sqrt(discr)) / a;
if (t < 0.0f || t > 1.0f) return 0;
// Intersection lies outside segment
if(md+t*nd<0.0f) {
// Intersection outside cylinder on 'p' side
if (nd <= 0.0f) return 0;
// Segment pointing away from endcap
t = -md / nd;
// Keep intersection if Dot(S(t) - p, S(t) - p) <= r
∧
2
returnk+2*t*(mn+t*nn)<=0.0f;
} else if (md+t*nd>dd){
// Intersection outside cylinder on 'q' side
if (nd >= 0.0f) return 0; //
Segment pointing away from endcap
t = (dd - md) / nd;
// Keep intersection if Dot(S(t) - q, S(t) - q) <= r
∧
2
returnk+dd-2*md+t*(2*(mn-nd)+t*nn)<=0.0f;
}
// Segment intersects cylinder between the endcaps; t is correct
return 1;
}
With minor adjustments, the same approach can be used to intersect a ray (not a
segment) against the finite cylinder. The intersection against a capsule, rather than a
cylinder, is performed in a comparable manner by replacing the intersection with the
endcap planes with intersection against hemispherical endcaps. Tests for intersecting
lines, rays, and segments with a cylinder have previously been described in [Shene94],
[Cychosz94], and [Held97].
5.3.8
Intersecting Ray or Segment Against Convex Polyhedron
To intersect a segment
S
(
t
)
1, against a convex polyhedron
it turns out that a convenient representation for the polyhedron is to describe it as
the intersection of a set of halfspaces [Haines91b]. For such a format, the segment
intersects the polyhedron if there exists some value for
t
,0
=
A
+
t
(
B
−
A
), 0
≤
t
≤
1, for which
S
(
t
) lies
inside all halfspaces. An efficient way of determining if this is the case is simply to
clip the segment against each halfspace, trimming away the portion of the segment
that lies outside the halfspace. If during this clipping process the segment becomes
zero length, the segment cannot intersect the polyhedron and the process can stop
with a result of “no intersection.”After the segment has been intersected against all
halfspaces, what remains of the segment must be the intersection of the segment and
the polyhedron.
The clipping process can be implemented as keeping track of the segment defined
over the interval
t
first
≤
t
≤
≤
≤
t
last
, where
t
first
and
t
last
are initially set to 0 and 1,
respectively, but are adjusted as the segment is intersected against the planes defining
t
