Guide to Game Development/Theory/Collision detection
Collision detection is split up into two parts: broad-phase and narrow-phase. Broad-phase finds the objects that need to be checked, narrow-phase actually checks for a collision of objects.
Broad-phase
This is the method of checking which objects need to be checked. This basically means that if an object is too far away, then this test will say that the object doesn't need to be tested for collision detection. This is because the actual collision detect is resource heavy, so eliminating the amount of objects will mean that there are less calculations that need to be made.
Here are the different types:
- Sweep and Prune
- QuadTree partitioning
- BSPTrees
- SphereTrees
- Spatial partitioning
- Object partitioning
Narrow-phase
This is the accurate collision detection that is resource heavy (compared to broad-phase).
- Discrete vs. Continuous
- Demonstrating the differences between discrete and continuous collision detection.
Types
- Axis-aligned bounding box (only works for items aligned to axes, but you can translate them, perform the test and translate them back).
- OBB intersection
- Oriented bounding box.
- The idea of creating new virtual axes based upon your geometry and comparing them.
- Circular collision detection.
- Ray casting
- A linear vector equation with a limit that goes through the air to check for a collision of sorts.
- Mesh
- This is where you actually test for collisions of an object exactly, you build a mesh of polygons around the object and check for collisions around that.