Narrow-phase collision detection algorithms

Posted by Marian Ivanov on Game Development See other posts from Game Development or by Marian Ivanov
Published on 2012-12-05T18:19:08Z Indexed on 2012/12/05 23:21 UTC
Read the original article Hit count: 294

There are three phases of collision detection.

  1. Broadphase: It loops between all objecs that can interact, false positives are allowed, if it would speed up the loop.

  2. Narrowphase: Determines whether they collide, and sometimes, how, no false positives

  3. Resolution: Resolves the collision.

The question I'm asking is about the narrowphase. There are multiple algorithms, differing in complexity and accuracy.

  1. Hitbox intersection: This is an a-posteriori algorithm, that has the lowest complexity, but also isn't too accurate,

  2. Color intersection: Hitbox intersection for each pixel, a-posteriori, pixel-perfect, not accuratee in regards to time, higher complexity

  3. 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

  4. Linear raycasting: A-priori algorithm, useful for semi-realistic-looking physics, finds the intersection point, even more accurate than SAT, but with more complexity

  5. 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.

© Game Development or respective owner

Related posts about collision-detection

Related posts about ray-casting