Narrow-phase collision detection algorithms
- by Marian Ivanov
There are three phases of collision detection.
Broadphase: It loops between all objecs that can interact, false positives are allowed, if it would speed up the loop.
Narrowphase: Determines whether they collide, and sometimes, how, no false positives
Resolution: Resolves the collision.
The question I'm asking is about the narrowphase. There are multiple algorithms, differing in complexity and accuracy.
Hitbox intersection: This is an a-posteriori algorithm, that has the lowest complexity, but also isn't too accurate,
Color intersection: Hitbox intersection for each pixel, a-posteriori, pixel-perfect, not accuratee in regards to time, higher complexity
Separating axis theorem: This is used more often, accurate for triangles, however, a-posteriori, as it can't find the edge, when taking last frame in account, it's more stable
Linear raycasting: A-priori algorithm, useful for semi-realistic-looking physics, finds the intersection point, even more accurate than SAT, but with more complexity
Spline interpolation: A-priori, even more accurate than linear rays, even more coplexity.
There are probably many more that I've forgot about. The question is, in when is it better to use SAT, when rays, when splines, and whether there is anything better.
