Game Development Reference
Smooth Mesh Contacts with GJK
Gino van den Bergen
Contacts are without doubt the toughest constraints that a game physics engine
needs to deal with. Contacts constrain the relative motions of two bodies in one
direction only, often act for a short period of time, and involve sliding and rolling.
But most importantly, contacts require a detailed representation of a body's ge-
ometry, since a contact between two bodies can occur anywhere on their surfaces.
This chapter discusses how to obtain proper contact points and normals for
convex shapes that collide with each other or with possibly concave shapes
represented by polygon meshes. The case of a convex shape hitting a mesh is
very common in games. Meshes are typically used for representing the static en-
vironment, such as buildings and terrain, whereas the moving objects, like player
and nonplayer characters, (parts of) vehicles, projectiles, debris, and third-person
cameras, are represented by convex shapes. The trouble with polygon meshes is
that they, having zero thickness, actually only represent the surface but need to
physically represent solid objects.
One immediate problem we see is that not only is the position on the surface
important but also the time of impact. Physics engines compute body positions
at discrete time steps. Collisions usually happen in between these time steps.
Problems occur when performing collision detection for fast-moving bodies at
these discrete time steps, since collisions may be detected too late or not at all.
This effect, called tunneling , can be reduced by taking smaller time steps. If we
had the computational budget to reduce the time step to a millisecond or less,
then we would rid ourselves of the grossest tunneling mishaps for the average
game scene. However, in game development we usually do not have that kind of
This suggests that for fast-moving objects we need to detect collisions in con-
tinuous four-dimensional space-time in order to catch colliding bodies before they
interpenetrate. This also seems to suggest that we need to take substeps in our
physics integration, since velocities may radically change in between time steps.