Graphics Reference
In-Depth Information
A
A
+
v
(a)
A
(b)
1
n
A
+ —
v
A
(c)
Figure 5.32
Dynamic collision tests. (a) Testing only at the start point and endpoint of an
object's movement suffers from tunneling. (b) A swept test finds the exact point of collision,
but may not be possible to compute for all objects and movements. (c) Sampled motion
may require a lot of tests and still exhibit tunneling in the region indicated by the black
triangle.
or end of a movement. Thus, for two objects
A
and
B
, the movement of object
B
can be subtracted from object
A
. Now object
B
is stationary and any intersection
test needs to consider only a moving object (
A
) against a stationary object (
B
). That
is, the test is effectively considering the objects' movement relative to each other. If
an intersection point is computed, the movement of
B
must be added back into the
computed intersection point to obtain actual world coordinates rather than object-
relative coordinates. In the following sections, first two generic methods to dynamic
tests are explored, followed by a number of specific methods addressing common
intersection problems.
5.5.1
Interval Halving for Intersecting Moving Objects
Somewhere halfway between the sampling method and performing a continuous
swept test lies a method based on performing a recursive binary search over the
object movement to find the time of collision, if any. Consider again the problem
of a sphere
S
moving at high speed past a stationary object. Let
S
be at position
A
,
its movement described by the vector
v
. Start by forming a bounding sphere that
fully encloses the sphere at
A
and at
A
+
v
and test this sphere for collision against
