Narrow-phase collision detection algorithms

Question

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.

Answer 1

Two that you're missing which immediately stand out to me are GJK and MPR.

GJK is an algorithm for finding the closest point of two convex polygons. With a little bit of extra work you can use it to find incident points for intersecting objects, and hence calculate a collision manifold. This is done via polygon clipping, same as if using SAT, but GJK saves you some steps (since you'll already have the closest points).

MPR (Minkowski Portal Refinement) is another algorithm, similar to GJK (they both use Minkowski spaces). It can't find the closest point between non- intersecting objects like GJK, but it does have a lot of other nice properties for games, and is way to use to get a contact manifold.

MPR is one of the more popular for games. It is very efficient, numerically stable, and easy to implement.

Other narrow phases are used more in specialized games. Racing games usually use ray casting as modeling actual tires and getting realistic (or even just fun) behavior is not yet possible using traditional collision shape and resolution modeling. Platformers also typically use highly customized collision and physics, as the preferred "Mario-like" physics are not modeled with traditional physics algorithms. You'll also often see different collision and physics methods for fluids and such, though I know less about those.

See:

• https://dyn4j.org/tags#gjk
• http://xenocollide.snethen.com/

Answer 2

I wanted to say, its Separating Axis Test, not Theorem.

You'd use SAT on non moving polygons (2D), although you can extend it to cope with relative linear motion.

2D polygon-based collision detection and response: Tutorial 3 - Extending further for fast moving objects

Don't use GJK in 2D, I found its actually slower than simply brute forcing SAT.

Another technique you can use is Minkowski Difference, which shrinks one object down to a point and 'grows' the other by the shape of the first. Then you test the combined object against the point which is a lot easier - this gives you penetration distance and normal. I find this tool is conceptually very useful for approaching new collision detection problems; easier to visualise than SAT.

For moving and rotating polygons (and polyhedrons) you can use Conservative Advancement to find the exact time and point of contact.

Continuous Collision Detection and Physics

You can read more about these techniques in this blog post which I wrote a while back:

Collision detection for dummies

Hope that helps!

Cheers, Paul.

Answer 3

This is really depends on the type of game you have. Each method above have its own trade-offs.

However, SAT is pretty standard in my experience for generic physics libaries, Ex. Box2D uses it extensively (Angry Birds, and many other games use Box2D).

Variations of color intersection mixed with SAT or Hitbox intersection is used in games like Sonic, Megaman with good results.

I don't know much about #4 and #5 though.