Game Development Reference
In-Depth Information
3.3 Optimization of the Broad Phase
A role of the broad phase in rigid-body simulation is to find a pair of bodies that
could possibly collide. Because a fast algorithm is required rather than an accurate
one in the broad phase, a bounding volume (AABB) that surrounds a real shape
of a rigid body along each x -, y -, and z -axis is used. Then, if the AABBs of two
rigid bodies cross one another, broad phase outputs this as a pair with a possibility
of colliding. The collision-detection sequel to the broad phase can be done only
for these colliding pairs, using real shapes of rigid bodies that belong to a pair.
Therefore, useless operations will be largely avoided.
3.3.1
“Sweep and Prune” Algorithm
The mechanism of the “sweep and prune” (SAP) algorithm is very simple yet ef-
fective [Ericson 05]. In this algorithm, minimum and maximum values of AABB
are stored in a node of the list along the x -, y -, and z -axes. All nodes in the
lists are maintained as sorted along each axis. Then, select one axis and find
nodes crossing one another. When the intersection is found, also check the in-
tersection of nodes along the other axis. If nodes of two AABBs are crossing all
axes, two AABBs are output as an overlapped pair. If the state of a rigid body is
changed (moved, added, or removed), the algorithm's operation is to just change
the pointer to the nodes, so the update of nodes is completed fast when there are
not so many moving objects in the world.
Figure 3.4. The mechanism of double buffering.