Broad And Narrow Phase Collision Detection Systems

If you don’t know about the big O notation, I recommend you read about it here first. This post gives you an idea of what broad and narrow phase algorithms are and how they are used in physics engines.

Broad Phase Collision Detection

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions using a O(n^2) algorithm, but when you add more and more objects to the simulator It becomes quite expensive (CPU wise). Not very good for performance.

We can reduce the amount of tests by implementing a broad phase into our collision system. It is responsible of eliminating tests and thus reducing the number of tests needed (We obviously don't need to test objects far away from the player). We could for example have an algorithm that tests the distance using the X and Y axis of the screen, if the objects are too far away from each other, we can eliminate them as potential collisions. There are many algorithms that can eliminate tests, a few of them are:

SAP (Sweep and Prune) - More info - O(n log(n)) algorithm

Spatial Hash - More info - O(n log(n)) algorithm

If I remember correctly they can be O(1) in best case and O(n^2) in worst case.

It is important to remember that the broad phase only keeps track of the distance between objects. If they are close enough to create a potential collision, the objects are paired. To determine if two objects are close enough to create a collision, we use something called a AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that encapsulates the whole object. It is cheaper to test box vs. box instead of a lot of polygons vs. polygon.

Too far from each other to be tested for collisions:

Close and needs to be further tested for collision:

Narrow Phase Collision Detection

Once the broad phase collider has done its job, we are left with a couple of pairs that needs further testing. A physics engine needs to know exactly how deep polygon shapes have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygon shapes and finds out where those two polygons intersect and how deep.

We need the depth of penetration, the normal and the position of the collision to calculate a proper physics response.

Collision where the red dot is the point of collision.

There are also a few different narrow phase algorithms. Two examples of such algorithms are listed here:

SAT (Separate Axis Theorem) - More info
Distance Grid - More info