Physics Initialization - Learning Game Physics with Bullet Physics and OpenGL - page 39

Note
This class doesn't define how to detect collisions, or how objects respond to col-
lisions. It only defines how they move in response to stepping the simulation
through time.
The broad phase
A physics simulation runs in real time, but it does so in discrete steps of time. Each
step, there would be some number of objects which may have moved a small dis-
tance based on their motion and how much time has passed. After this movement
has completed, a verification process checks whether a collision has occurred, and
if so, then it must generate the appropriate response.
Generating an accurate collision response alone can be highly computationally ex-
pensive, but we also have to worry about how much time we spend checking for
collisions in the first place. The brute force method is to make sure that no collisions
have been missed by comparing every object against every other object, and finding
any overlaps in space, and doing this every step.
This would be all well and good for simple simulations with few objects, but not when
we potentially have hundreds of objects moving simultaneously, such as in a video-
game. If we brute force our way through the collision checks, then we need to check
all the N objects against the other N-1 objects. In Big O notation this is an O(N 2 )
situation. This design scales badly for increasing values of N , generating an enorm-
ous performance bottleneck as the CPU buckles under the strain of having so much
work to do every step. For example, if we have 100 objects in our world, then we
have 100*99 = 9,900 pairs of objects to check!
Tip
Brute forcing one's way through physics collision detection is typically the first
performance bottleneck an inexperienced game programmer comes across.