Game Development Reference
The Final Contact
Now we have a winner from the point-face calculations and a winner from the edge-
edge calculations. The contact that gets returned will be the deeper of these two op-
tions. This can then be fed into the caching algorithm described previously to gener-
ate a complete set of contacts over successive frames.
E FFICIENCY AND G ENERAL P OLYHEDRA
Obviously the naive contact generation algorithm described earlier is considerably
less efficient than V-Clip, GJK, or the handful of other variations used in comprehen-
sive collision detection libraries.
You'll find this algorithm on the CD, along with a more efficient general-purpose
contact generation routine that you can simply copy and paste into your own code.
Neither the naive algorithm nor its more efficient cousins are limited to contact
generation between boxes. They are general-purpose algorithms that can generate
contacts between any convex 3D objects made up of flat surfaces. This is convenient
are becoming increasingly common).
As the number of faces increases, however, the algorithms slow down by an in-
creasingly large amount. The naive algorithm shows this particularly acutely; for any-
thing more than a simple box it performs very badly. But both V-Clip and GJK also
suffer from the same problem.
For this reason, even when using a very efficient collision detection algorithm
with a comprehensive coarse collision detection layer, it is not advisable to use the
same set of geometry for collision detection as you do for rendering. Even complex
3D assets can normally be represented to the collision detector as either an assembly
of primitives or an assembly of simply convex polyhedra. A general polyhedra contact
generator, combined with the caching system we've built, can then generate a set of
contacts that will lead to realistic physics in a reasonable amount of time.
These collision detection cases only scratch the surface of what is possible (and what
may be needed) in a full game engine. Collision detection, and particularly contact
generation, is a large field in its own right, and although the physics engine relies on
it, it is a quite separate piece of software engineering.
You can use the collision detection system we've built in the last two chapters in
its own right, and extend it with the additional tests you need (the other topics in this
series contain lots of collision detection tests). Or you can elect to bring in a third-
party collision detection system.
There are good open source collision detection and contact generation algorithms
available (such as SOLID and RAPID). You can use these alongside the physics you're