Broad Phase and Narrow Phase Collision Detection

We still don't know how to check for collisions between our objects and their bounding shapes. There are two phases of collision detection:

Broad phase: In this phase we try to figure out which objects can potentially collide. Imagine having 100 objects that could each collide with each other. We'd need to perform 100 x 100 / 2 overlap tests if we chose to naively test each object against each other object. This naïve overlap testing approach is of O(n2) asymptotic complexity, meaning it would take n2 steps to complete (it actually finished in half that many steps, but the asymptotic complexity leaves out any constants). In a good, non-brute-force broad phase, we try to figure out which pairs of objects are actually in danger of colliding. Other pairs (e.g., two objects that are too far apart for a collision to happen) will not be checked. We can reduce the computational load this way, as narrow-phase testing is usually pretty expensive.

Narrow phase: Once we know which pairs of objects can potentially collide, we test whether they really collide or not by doing an overlap test of their bounding shapes.

Let's focus on the narrow phase first and leave the broad phase for later.

0 0

Post a comment