Game Engine Architecture

613

A compound shape can oft en be a more-effi cient alternative to a poly
soup for modeling non-convex objects; two or more convex volumes can oft en
out-perform a single poly soup shape. What’s more, some collision systems
can take advantage of the convex bounding volume of the compound shape as
a whole when testing for collisions. In Havok, this is called midphase collision
detection. As the example in Figure 12.9 shows, the collision system fi rst tests
the convex bounding volumes of the two compound shapes. If they do not
intersect, the system needn’t test the subshapes for collisions at all.

12.3.5. Collision Testing and Analytical Geometry

A collision system makes use of analytical geometry —mathematical descrip-
tions of three-dimensional volumes and surfaces—in order to detect inter-
sections between shapes computationally. See htt p://en.wikipedia.org/wiki/
Analytic_geometry for more details on this profound and broad area of re-
search. In this section, we’ll briefl y introduce the concepts behind analytical
geometry, show a few common examples, and then discuss the generalized
GJK intersection testing algorithm for arbitrary convex polyhedra.

Figure 12.8. A chair can be modeled using a pair of interconnected box shapes.

B^2 B^3

B^1

B^4

A 1

A 2

Sphere A Sphere B

A1

A2

B1

B2

B3

B4

Bounding Volume

Hierarchies:

Sphere A

Sphere B

Figure 12.9. A collision system need only test the subshapes of a pair of compound shapes
when their convex bounding volumes (in this case, Sphere A and Sphere B) are found to be
intersecting.

12.3. The Collision Detection System