Game Development Reference
In-Depth Information
A - B
A - B
w 1
w 1
w 3
V 3
O
O
w 2
w 2
(a)
(b)
A - B
A - B
w 1
w 3
w 3
V 4
V 5
O
O
w 4
w 4
w 2
w 2
(c)
(d)
Figure 17.2 GJK Algorithm
for collision calculation. Intersection of safety zones makes it possible to launch the
processes avoiding the overlap of objects per se. However, there are other contexts
that tolerate interpenetration between objects and simply try to restrict them. These
approaches require a certain measurement of overlap, in the form of volume or mostly
in the form of interpenetration distance (amplitude of the smallest translation that can
separate the objects). Even though several algorithms were suggested, unfortunately,
very few of them are actually stable. Most of them are based on the techniques of
calculation of separation distance: GJK (Cameron, 1997; Joukhadar et al., 1999) and
Expanded polytope algorithm (EPA) (Bergen, 2001) or Voronoi marching (Gregory
et al., 2000). We can also mention the DEEP method which works in the space of
the perpendiculars of two objects (Kim et al., 2002a). Finally, if the intersection is
really necessary for the application, the standard structures can be used in geometric
modelling: the BSP (Binary Space Partitions) (Naylor et al., 1990).
17.1.3 Spatial detection between any polyhedrons
The algorithms mentioned in the previous part are restricted to polytopes. When a
polyhedron is concave, we can apply these algorithms on its convex envelop, but only
non-collision cases can be detected. There are several methods to construct the convex
envelop of a set of vertices, such as the Qhull 2 algorithm. It is also possible to divide the
2 See http://www.geom.umn.edu/software/qhull/