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.

Search Nedrilad ::

Custom Search