10
\$\begingroup\$

I have two object-aligned bounding boxes (i.e. not axis aligned, they rotate with the object). I'd like to know if two object-aligned boxes overlap. (Edit: note - I'm using an axis-aligned bounding box test to quickly discard distant objects, so it doesn't matter if the quad routine is a little slower.)

My boxes are stored as four x,y points. I've searched around for answers, but I can't make sense of the variable names and algorithms in examples to apply them to my particular case.

Can someone help show me how this would be done, in a clear and simple way? Thanks. (The particular language isn't important, C-style pseudo code is OK.)

\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

If you know where to look it is easy. You are looking for oobb. Go here: http://www.realtimerendering.com/intersections.html.
There you find link to this site http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html
and there find correct code. (ctrl+f "Intersection of boxes (2D)")

It uses SAT and contains source codes and article.

\$\endgroup\$
2
  • \$\begingroup\$ The algorithm described by the geometrictools is the one I would have pointed at. \$\endgroup\$ Jan 31, 2011 at 13:15
  • \$\begingroup\$ I get that this was 4 years ago, but always explain a downvote and all that. This is pretty "Your answer is in another castle", and now the answer doesn't even seem to be there in the second case. \$\endgroup\$
    – Yann
    Nov 26, 2015 at 21:54
2
\$\begingroup\$

The easier way is probably to test each vertex of box B against each side of box A (compute the signed distance). This way you can classify each vertex as "in front" or "behind" the segment.

If all of B's vertexes classify as "in front" of one of A's segments, B and A don't overlap; otherwise, they do.

This is somewhat involved, so you may get some performance gain by doing a circle-circle check first, using the bounding circles of the squares (trivial to compute)

\$\endgroup\$
2
  • \$\begingroup\$ I'm first doing an axis-aligned bounding box test to quickly discard distant objects... do you have any more details on the quad-quad test though? \$\endgroup\$ Jan 30, 2011 at 22:19
  • \$\begingroup\$ temporarily rotate both quads with the same transform such that one of them ends up axis aligned... then use the SAT test as notabebe mentioned. when result is found, inverse the rotation to get them back. \$\endgroup\$
    – Steve H
    Jan 31, 2011 at 2:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .