Graphics Reference
In-Depth Information
involves detecting intersection between the objects, at discrete points in time, dur-
ing their motion. At each such point in time the objects are treated as if they were
stationary at their current positions with zero velocities. In contrast,
dynamic colli-
sion detection
considers the full continuous motion of the objects over the given time
interval. Dynamic collision tests can usually report the exact time of collision and
the point(s) of first contact. Static tests are (much) cheaper than dynamic tests, but
the time steps between tests must be short so that the movement of the objects is
less than the spatial extents of the objects. Otherwise, the objects may simply pass
each other from one time step to the next without a collision being detected. This
phenomenon is referred to as
tunneling
.
The volume covered by an object in continuous motion over a given time interval is
called the
swept volume
. If the swept volumes of two moving objects do not intersect,
there is no intersection between the objects. Even if the swept volumes intersect,
the objects still may not intersect during movement. Thus, intersection of the swept
volumes is a sufficient, but not necessary, condition for object collision. For complex
motions, the swept volume is both difficult to compute and to work with. Fortunately,
perfect accuracy is rarely necessary. Dynamic collision testing of complex tumbling
motions can usually be simplified by assuming a piecewise linear motion; that is,
a linear translation over the range of movement, with an instantaneous rotation
at the end (or start) of the motion. Somewhere between these two alternatives is
replacement of the unrestricted motion with a screw motion (that is, a fixed rotational
and translational motion).
When working with moving objects it is virtually always preferable to consider
the relative motion of the objects by subtracting the motion of the one object off the
other object, thus effectively leaving one object static. Assuming linear translational
motion for the objects makes this operation a simple vector subtraction. A key benefit
of considering only the relative motion is that for testing one moving object against
a stationary object a swept volume test is now an exact intersection test. In games,
the entire swept volume is sometimes just replaced by a
speedbox
: an elongated box
covering the object for its full range of motion (or some similarly simple proxy object,
not necessarily a box).
2.5
Performance
Taking game consoles as an example, for the best possible visuals games must run
at 60 fps (in countries with NTSC TV format; 50 fps in PAL territory). This frame
rate leaves 16.7 ms to prepare each game frame. Depending on the type of game,
collision detection may account for, say, 10 to 30% of a frame, in turn leaving 2 to
5 ms for collision detection. For an action platform game that may have dozens of
collision-dependent objects active at a given time there may be only about 50 to
250
s available to handle the collision for each object — not a lot of time. Clearly, it
is very important to reduce the average running time of collision queries. However,
as large sudden drops in frame rate are very noticeable in games (in a bad way) it is
μ
