Graphics Reference
In-Depth Information
Chapter
1
Introduction
This topic is concerned with the subject of collision detection, a broad topic dealing
with a seemingly simple problem: detecting if two (or more) objects are intersect-
ing. More specifically, collision detection concerns the problems of determining
if
,
when
, and
where
two objects come into contact. “If”involves establishing a Boolean
result, answering the question whether or not the objects intersect. “When” must
additionally determine at what time during a movement collision occurred. “Where”
establishes how the objects are coming into contact. Roughly, these three types of
queries become increasingly more complex to answer in the order given.
Gathering information about when and where (in addition to the Boolean collision
detection result) is sometimes labeled
collision determination
. The terms
intersection
detection
and
interference detection
are sometimes used synonymously with collision
detection.
Collision detection is fundamental to many varied applications, including com-
puter games, physically based simulations (such as computer animation), robotics,
virtual prototyping, and engineering simulations (to name a few).
In computer games, collision detection ensures that the illusion of a solid world is
maintained. It keeps player characters from walking through walls or falling through
floors; it provides for line-of-sight queries, telling enemies if they can see the player
and therefore can attack; and it keeps a skateboarder attached to an invisible guide
surface, ensuring that the player safely makes it back down into a halfpipe after having
gone airborne up it.
In computer animation, collision detection is used, for example, to constrain the
physical simulation of cloth, ensuring clothing behaves in a lifelike manner and
does not slide off a character as the character moves. Collision detection is used
for path planning in robotics applications, helping robots steer away from obstacles.
In virtual prototyping, collision detection assists in computing clearances, and overall
allows prototypes to be refined without the production of physical models. Collision
detection is used in crash tests and other engineering simulations.
1
