Hey! Its been a while since I updated but I was busy with finals. Now on break, and excited to be learning about collision detection in my game physics book.
The first thing they discuss is broad phase vs. narrow phase collision detection. Which is an idea I have anticipated (and even implemented in some form) before.
Suppose we have N objects in a given scene. Then there are “N choose 2” possible ways we can pair up the objects to check for a collision. Or N(N-1)/2 or roughly half the square of N. So if we have 100 objects, we have about 5,000 possible collisions to check. If the objects have complicated geometries, this could take way longer than one frame duration!
The solution to this is “Broad Phase” collision detection. A crude but fast method of eliminating large numbers of collision checks. Its purpose is primarily to determine if objects do NOT collide so that they need not be considered further, and return a list of pairs of objects that potentially collide.
The one requirement of a broad phase collision detection algorithm is it must return all pairs of objects that do intersect. This does not mean it will not return pairs of objects that do not actually intersect.
In other words, the broad phase algorithm determines what objects need “further inspection”
This is carried out by the “narrow phase” collision detection algorithm. This will then determine precisely which objects interesect and which do not, and additional details about the collision itself.
This allows much more efficient collision checking that can be completed in the time-span of a single frame.
In my next post, I’m going to discuss a specific broad-phase algorithm, that uses a special data structure called a “bounding volume hierarchy”.
TheGeneralSolution's Game Development Blog 