Graphics Reference
In-Depth Information
first (as the circular cross section of the sphere, as it moves through the plane, will be
centered at
P
).
To determine whether the sphere hits
Q
, instead of moving the sphere toward the
triangle a ray
Q
t
v
can be cast “in reverse” from
Q
toward the sphere. If this ray
does not hit the sphere or if
t
does not lie in the range of zero to one, then the sphere
does not hit
Q
and there is no intersection. If the ray hits the sphere at some point
R
,
with 0
−
1, then the point
R
on the sphere will first come into contact with point
Q
of the triangle, at time
t
(Figure 5.36b).
Unfortunately, this test is not robust. When the sphere is moving parallel to the
plane of the triangle, there is no intersection between the movement vector and the
plane and the algorithm breaks.
However, this is not always a problem as, for example, when all triangles inter-
sected against are part of a mesh such that all exposed triangle edges are always
shared with another triangle. A moving sphere will then always hit a neighboring
triangle before it has a chance to fail detecting intersection with a triangle it is moving
parallel to. Of course, collision response relating to sliding in the plane of the triangle
must also be adapted to handle this situation.
A more robust, but also more expensive, method is first to perform a sphere-
against-plane test (either as just described, or as per Section 5.5.3). If there is an
intersection, the point
P
of earliest contact is tested for containment in
T
, just as
in Nettle's approach. If
P
lies inside
T
, the earliest intersection has been found
and the test can exit. Otherwise, a test of the moving sphere against each trian-
gle edge is performed. This is equivalent to testing the directed segment
C
≤
t
≤
+
t
v
,
0
1, against the edges turned into cylinders of radius
r
(see Section 5.3.7).
If one or more intersections against the curved surface (only) of the cylinders
are detected, the closest one corresponds to the earliest intersection, which is
returned.
Assuming that no intersection has been detected up to this point, the ray is inter-
sected against the spheres of radius
r
centered on the vertices of the triangle. Again,
if there are one or more intersections the closest one is returned. If no sphere is inter-
sected, this corresponds to the original sphere not intersecting the triangle. Note that
for the ray-cylinder tests no intersection against the endcaps is necessary: if there is
an intersection between the sphere and the triangle, the ray will intersect the spheres
at the vertices before it can strike an endcap. The last bit of the test, as given in Section
5.3.7, can therefore be omitted.
Overall, this approach is perhaps best seen conceptually as a ray test against the
solid volume
V
resulting from sweeping
T
with
S
, forming the Minkowski sum
T
≤
t
≤
S
of
T
and
S
(as described in Section 3.11), but with the three individual component
tests performed either as ray tests or as sphere tests (depending on what is more
appropriate). The next section describes how to apply the Minkowski sum approach
to the problem of intersecting a moving sphere against an AABB.
This second, more robust, method is suggested in [Schroeder01], with corrections
in [Akenine-Möller02]. Both of the approaches described in this section generalize
to intersections against arbitrary polygons in a straightforward way.
⊕
