What is the fastest algorithm to check if two cubes intersect (where the cubes are not axis aligned)?

Question

I am looking for an algorithm to check if two cubes intersect. One can check if each of the 6 faces of cube A are intersected by each of 12 edges of cube B, but that is 72 checks. I've heard there is a paper from 1997 or so, describing a method that uses just 15 intersection checks, but I can't find it. Can you please share the name of the paper, describing it or describe it in your words.

This question deals with axis aligned cubes which is not really useful. https://stackoverflow.com/questions/5009526/overlapping-cubes

Answer 1

Separating axis test. (Also called separating axis theorem, separating axis theorem test, yada yada.)

If you can find an axis (ANY axis), not just regular XYZ basis vectors) where the projections of your two cubes don't overlap, then they don't intersect.

There are a ton of tutorials and implementations available via Google, but this one has pretty graphs:

https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169

This is what we teach our game dev grad students and they all get jobs. :)

Also, checking intersections of vertices and faces or edges doesn't cover the case where cubes are nested, so it's not a real solution. SAT looks complicated in 3D, but it's just a lot of repetition. Cut, paste, trace and try some edge cases and you'll get it.

A dirt-simple method that's good enough for broad-phase collision detection is to treat the cubes as spheres. (If they're really regular cubes, the error is marginal, though proportional to the scale of the cubes relative to each other.)

Get the distance between the center of the cubes, and see if it is greater than the sum of the half diagonals of the two cubes. (Basically, you're checking bounding spheres instead of worrying about hyperplanes.)