i
i
i
i
i
i
i
i
790 16. Intersection Test Methods
Figure 16.31. In the left figure, a sphere moves towards a polygon. In the right figure,
a ray shoots at an “inflated” version of the polygon. The two intersection tests are
equivalent.
ray against this volume’s parts: First, the polygon facing the ray is tested,
then the edge cylinders are tested against the ray, and finally, the vertex
spheres are tested.
Thinking about this puffy object gives insight as to why a polygon is
most efficiently tested by using the order of area, then edges, then vertices.
The polygon in this puffy object that faces the sphere is not covered by the
object’s cylinders and spheres, so testing it first will give the closest possible
intersection point without further testing. Similarly, the cylinders formed
by the edges cover the spheres, but the spheres cover only the insides of
the cylinders. Hitting the inside of the cylinder with a ray is equivalent to
finding the point where the moving sphere last hits the corresponding edge,
a point we do not care about. The closest cylinder exterior intersection (if
one exists) will always be closer than the closest sphere intersection. So,
finding a closest intersection with a cylinder is sufficient to end testing
without needing to check the vertex spheres. It is much easier (at least for
us) to think about testing order when dealing with a ray and this puffy
object than the original sphere and polygon.
Another insight from this puffy object model is that, for polygons with
concavities, a vertex at any concave location does not have to be tested
against the moving sphere, as the sphere formed at such a vertex is not
i
i
i
i
i
i
i
i
16.18. Dynamic Intersection Testing 791
visible from the outside. Efficient dynamic sphere/object intersection tests
can be derived by using relative motion and the transformation of a moving
sphere into a ray by using Minkowski sums.
16.18.4 Dynamic Separating Axis Method
The separating axis test (SAT) on page 731 is very useful in testing convex
polyhedrons, e.g., boxes and triangles, against each other. This can be
extended quite easily to dynamic queries as well [124, 292, 315, 1131].
Remember that the SAT method tests a set of axes to see whether the
projections of the two objects onto these axes overlap. If all projections
on all axes overlap, then the objects overlap as well. The key to solving
the problem dynamically is to move the projected interval of the moving
object with a speed of (v · a)/(a · a) (see Equation A.17) on the axis,
a [124]. Again, if there is overlap on all tested axes, then the dynamic
objects overlap, otherwise they do not. See Figure 16.32 for an illustration
of the difference between the stationary SAT and the dynamic SAT.
Eberly [292], using an idea by Ron Levine, also computes the actual time
of intersection between A and B. This is done by computing times when
they just start to overlap, t
s
, and when they stop overlapping (because the
intervals have moved “through” each other), t
e
. The hit between A and
B occurs at the largest of all the t
s
s for all the axes. Likewise, the end
of overlapping occurs at the smallest of all the t
e
s. Optimizations include
detecting when the intervals are nonoverlapping at t = 0 and also moving
apart. Also, if at any time the largest t
s
is greater than the smallest t
e
,
then the objects do not overlap, and so the test is terminated. This is
similar to the ray/box intersection test in Section 16.7.1. Eberly has code
for a wide range of tests between convex polyhedra, including box/box,
triangle/box, and triangle/triangle.
Figure 16.32. Left: the stationary SAT illustrated for an axis a. A and B do not overlap
on this axis. Right: the dynamic SAT illustrated. A moves and the projection of its
interval on a is tracked during the movement. Here, the two objects overlap on axis a.
i
i
i
i
i
i
i
i
792 16. Intersection Test Methods
Figure 16.33. A line swept sphere (LSS) and rectangle swept sphere (RSS).
Further Reading and Resources
Ericson’s Real-Time Collision Detection [315] and Eberly’s 3D Game En-
gine Design [294] cover a wide variety of object/object intersection tests,
hierarchy traversal methods, and much else, and also include source code.
Schneider and Eberly’s Geometric Tools for Computer Graphics [1131] pro-
vides many practical algorithms for two- and three-dimensional geometric
intersection testing. Practical Linear Algebra [333] is a good source for
two-dimensional intersection routines and many other geometric manipu-
lations useful in computer graphics. The Graphics Gems series [36, 405,
522, 667, 982] includes many different kinds of intersection routines, and
reusable code is available on the web. The free Maxima [829] software is
good for manipulating equations and deriving formulae. This book’s web-
site includes a page, http://www.realtimerendering.com/int, summarizing
resources available for many object/object intersection tests.
Other bounding volumes of possible interest are line swept spheres
(LSS) and rectangle swept spheres (RSS). These are also called capsules
and lozenges, respectively, and are shown in Figure 16.33. For these BVs it
is a relatively quick operation to compute the minimum distance. There-
fore, they are often used in tolerance verification applications, where one
wants to verify that two (or more) objects are at least a certain distance
apart. Eberly [294] and Larsen et al. [730] derive formulae and efficient
algorithms for these types of bounding volumes.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.