Introduction

Two physical objects cannot occupy the same space at the same time. Simulated physical objects do not naturally obey this constraint. Instead, we must detect when two objects have collided and rectify the situation.

For example, when using CAD/CAM to design a machine, we must ensure the simulated machine parts never pass though one another. If the simulated parts collide, we must correct the design.

In computer graphics and animation, we often want to ensure that objects behave in a physically plausible way. This means checking if the simulated objects penetrate one another- if they do, the modeling tool or animator will want to know.

In motion planning for robotics, we must check if a robot arm will collide with anything as it executes a proposed command. The command will have to be modified if a collision is possible.

In simulating a car crash or tearing metal, at each timestep we must check if any objects intersect. If they do, we must deform or displace the objects.

Figure: Collision detection for: (a) CAD/CAM (b) Computer animation (c) Robotics (d) Physical simulation

Collision detection, also known as contact or interference detection, is the problem of determining whether a given set of objects overlap. If the objects overlap, in some situations we need to find exactly which parts of the objects overlap and the depth of the overlap region. The problem can be formulated in 2D, 3D, or higher dimensions; can vary with time; and, as shown above and in Figure , is relevant to many domains.

In this work, we only consider collision detection. Determining the appropriate response to a collision is an interesting problem, but the solution completely depends on the particular domain.