Game Development Reference
tell you how to build a physics engine collision system. In fact, most commercial or
open source collision detection systems aren't suitable for physics applications.
Collision detection determines whether two objects are touching or interpene-
trated, and normally provides data on the largest interpenetration point. Contact
generation produces the set of points on each object that are in contact (or pene-
The difference is crucial. In figure 13.2 one box is lying across another: in the left
part of the figure the result of a typical collision detection system is shown: the box is
slightly (microscopically) twisted, so one edge generates the contact. In the right part
of the figure the correct contact patch is generated.
The contact patch can be of any shape. This can make a challenging programming
task when it comes to resolving contacts. To make things easier we would like to deal
only with point contacts. The naive collision detection shown in figure 13.2 does this,
but doesn't provide enough contacts to generate realistic physics. We need a reliable
way to simplify a contact patch into a set of point contacts.
To do that we deal with a set of contact situations as shown in figure 13.3. Al-
though the contact patch can be any shape, the simplifications in the figure generate
reasonable physical behavior. While there are many situations in which they aren't
optimal, there are few in which the problem is noticeable when the physics is run-
ning. In figure 13.3 these cases are arranged in order of how useful they are. If we can
generate useful contacts higher in the list, we can ignore those lower down.
Of the illustrated cases, we ignore point-point contacts and point-edge contacts
altogether. These can be handled relatively easily, but they are rare and are normally
associated with other contact cases that can take the load. In the small number of
cases where the contact can only be represented in one of these two forms, we will
miss the contact. Experience shows that this isn't significant enough to be noticed.
The only occasion that we need to deal with face-face collisions is when one or
the other face is curved. In all other cases the edge-edge and edge-face contacts will
give the correct physics. Similarly edge-face contacts can often be replaced by a pair of
edge-edge contacts (except when the edge is curved), and we will prefer to use these.
F IGURE 13.2
Collision detection and contact generation.