7
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You may also consider GJK \$\endgroup\$ – Anonymous Anonymous Sep 25 '16 at 8:22
  • 1
    \$\begingroup\$ @AnonymousAnonymous I avoid TLA whenever possible. \$\endgroup\$ – 3Dave Sep 26 '16 at 1:31
  • 1
    \$\begingroup\$ Ok... Gilbert-Johnson-Keerthi distance algorithm... :-) \$\endgroup\$ – Anonymous Anonymous Sep 26 '16 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.