Game Development Reference
In-Depth Information
Sort as per axis X
Y
Sort as per axis Y
X
(a)
(b)
Result of the algorithm:
6 pairs selected
4 pairs in collision
(c)
Figure 17.11 Sweep and Prune Algorithm
(Cohen et al., 1995). It involves including the objects in isothetic parallelepiped boxes
i.e. all directed towards the same reference point. Figure 17.11 represents the steps of
the algorithm. In (a), we consider the projections on the axes of each of these boxes.
In (b), the projections are classified on each axis, as per the value of their minimum
abscissa. Their minimum abscissa helps defining an overlapping zone (shown under
the objects in the diagram). This list is then passed through. For a box B i , we consider
the next boxes in the sorted list. If the minimum abscissas of the boxes after B j ( j < i )
are less than the maximum abscissa of box B i , the projections of boxes overlap on the
axis. Once the minimum abscissa of a box B k is more than the maximum abscissa of
B i , all B j boxes where j > k have a track different than that of B i . Once all the boxes are
examined, we obtain a set of boxes whose tracks overlap on an axis. This technique
is carried out for each axis. Only the boxes that overlap on all the three axes are
retained. In (c), for 10 objects, we have 10
45 possible pairs. The algorithm
shows us that only 6 of the 45 pairs are in potential collision. The algorithms for
detailed detection later show that only 4 pairs actually collide. The sorting on the axes
is incremental, on the basis of the sorting of the previous detection (spatial coherence
of objects). The algorithm thus has an average linear complexity.
Other approaches prefer calculating the distances between each pair of objects. If
the distance is close to zero, the objects collide. For this purpose, and if necessary, we
approximate all the objects by convex polyhedrons (bounding box or convex envelop)
and modify the methods mentioned in section 17.1.2 so that they can use temporal
coherence: GJK, Voronoi Marching or DK. Finally, the last group of approaches uses
the relative speeds of the objects. If the objects do not intersect each other and they
move away, they cannot collide. It is called the backtracking test (Vanecek, 1994). If,
in addition to the relative speeds, the approximate inter-object distances can be known,
it is possible to estimate the impact time (Culley & Kempf, 1986; Lin & Canny, 1992;
Dworkin &Zelter, 1993; Kim et al., 1998) by t approx =
×
9/2
=
d min /v max . The corresponding
pair of objects is not inspected until this period does not end.