Two-phase collision detection

Suppose that the robot is a collection of $m$ attached links, ${\cal A}_1$, ${\cal A}_2$, $\ldots$, ${\cal A}_m$, and that ${\cal O}$ has $k$ connected components. For this complicated situation, collision detection can be viewed as a two-phase process.

1. Broad Phase: In the broad phase, the task is to avoid performing expensive computations for bodies that are far away from each other. Simple bounding boxes can be placed around each of the bodies, and simple tests can be performed to avoid costly collision checking unless the boxes overlap. Hashing schemes can be employed in some cases to greatly reduce the number of pairs of boxes that have to be tested for overlap [703]. For a robot that consists of multiple bodies, the pairs of bodies that should be considered for collision must be specified in advance, as described in Section 4.3.1.
2. Narrow Phase: In the narrow phase, individual pairs of bodies are each checked carefully for collision. Approaches to this phase are described in Sections 5.3.2 and 5.3.3.