Game Development Reference
details on tradeoffs, architecture, and optimization that are invaluable for a robust
C OLLISION D ETECTION P IPELINE
Collision detection can be a very time-consuming process. Each object, in the game
may be colliding with any other object, and each such pair has to be checked. If there
are hundreds of objects in the game, hundreds of thousands of checks may be needed.
And to make things worse, each check has to understand the geometry of the two ob-
jects involved, which might consist of thousands of polygons. So to perform a com-
plete collision detection, we may need a huge number of time-consuming checks.
This is not possible in the fraction of time we have between frames.
Fortunately there is plenty of room for improvement. The two key problems—
having too many possible collisions and having expensive checks—have independent
solutions. To reduce the number of checks needed, we can use a two-step process.
but without being too concerned about whether they actually are. This is typically
quite a fast process that uses rules of thumb and specialized data structures to
eliminate the vast majority of possible collision checks. It is called “coarse collision
2. Then a second chunk of code looks at the candidate collisions and does the check
to determine whether they actually are in contact. This is “fine collision detec-
tion.” Objects that are in contact are examined to determine exactly where the
contact is on each object (needed for rigid bodies), and the normal of collision
(which we saw in chapter 7). This is sometimes called “contact generation,” and
the results can form the input to the physics engine.
The first element is covered in this chapter; the second element will be covered in
To reduce the time taken for each check the geometry is typically simplified.
A special geometry just for collision detection is often created, making contact tests
far simpler. Collision geometry is discussed in section 13.1.
C OARSE C OLLISION D ETECTION
The first phase of collision detection is tasked with generating a list of full-detail
checks that need to be performed. 1
It needs to have the following key features.
1. In fact, we will not create an explicit list as a data structure to pass between the two phases. It is more
convenient to have the coarse collision detector simply call the fine collision detector each time it comes
across a likely collision. The fine collision detector can then accumulate a real list of actual collisions to
pass through to the physics engine.