Game Development Reference
Figure 17.3 Problem of detection in case of a division into convex parts
objects into convex parts, but in that case, the results obtained can have some lacunas.
For example, in figure 17.3, we obtain several overlap measurements, depending on
the decomposition we select. In an application that is looking for a global character-
isation of the collision (for example by a translation separating the two objects), the
object division proves to be inadequate. Finding a separator plane requires determin-
ing parameters a , b , c and d of the equation of the plane so that ax
d > 0
for all the vertices of one polyhedron and ax
d < 0 for the vertices of the
other polyhedron. This problem is generally settled by linear programming. Using the
simulated annealing method can also be effective (Zachmann, 2001).
If the distance between polyhedrons is to be found, the methods consist of con-
verging on the surfaces closest to the two polyhedrons. For this purpose, each object is
approximated by a hierarchy of bounding volumes (Quinlan, 1994; Johnson&Cohen,
1998; Ehmann & Lin, 2001).
The root volume includes the entire object. The volumes of intermediate nodes
include parts of the object; the parts become smaller as we move down the hierarchy.
At the level of leaves, the volume includes only one surface of the object. Methods for
constructing such a hierarchy are studied in section 22.214.171.124. Let d be an estimation
of the minimum distance (measured between any two polygons of the object or up to
infinity). Going through the two hierarchies makes it possible to delete all the pairs of
polygons not involved in the calculation of the minimum distance at the same time,
by ignoring the volume pairs separated by a distance more than d . When two volumes
are at a distance less than d and they are the leaves of the tree, then we calculate the
distance between the corresponding surfaces. If this distance is less than d , we modify
d and continue the algorithm until the distance between the last two pairs of primitives
that modified d is found. When the distance between objects is nil, a different algorithm
should be used to characterise the intersection. Intersection of two polyhedrons is not
empty if and only if one of the following two conditions is verified:
One vertex of one polyhedron belongs to the other;
One edge of one of them cuts one surface of the other.
These conditions are often, but not necessarily, checked simultaneously. In figure 17.4,
the intersections of polyhedrons are characterised by a vertex of a polyhedron located
in the other and/or an edge of this polyhedron passing through a surface of the other