How do I test for collision of two moving 2d oriented bounding boxes?

Question

The OBBs have a position(x,y), a velocity(x,y) and an orientation(Matrix). Given periodic updates, the OBBs must collide with each other, returning the fraction of the move that was deemed successful.

I have looked at the Polygon test on the GPWiki - http://gpwiki.org/index.php/Polygon_Collision - but it does not account for moving objects or an object that is completely within an OBB.

The book Real Time Collision Detection covers 3D OBBs in Chapter 4: Bounding Volumes, but the method for testing in 3 dimensions is notably more complex than in 2D.

Answer 1

To test collision detections between 2 oriented bounding boxes, I'd use separating axis theorem (SAT). In fact SAT can be used for collision detection between any 2 convex shapes. This technique is not overly complex to understand and has a reasonable performance. The theorem can easily be extended to 3D.

EDIT:

The algorithm tries to determine is it is possible to fit a plane between two objects. If such a plane exists, then the object are separated, and cannot intersect.

To determine if the objects are separated, it is simply a matter of projecting the objects onto the normal of the plane, and comparing the intervals and see if they overlap.

So, there is obviously an infinite number of planes that can fit between two separated objects. But it has been proved you only have to test a handful of planes.

It can be shown that for boxes, the separation planes to be tested are the planes with normal equal to the axes of both boxes. So for 2 boxes, you only need to test 4 separation planes in total. Out of the 4 planes, once you found a separation plane that separates the boxes, then you know the box cannot intersect, and you return a no collision flag.

If the 4 planes cannot separate the boxes, then the box must be intersection, and there you have a collision.

Answer 2

Another suggestion (which covers containment, and I think is cheaper):

Check if any of the 4 vertices of #1 are inside #2, then check if any of the 4 vertices of #2 are inside #1. Here's how i'd suggest to go about that:

Assume the vertex of #1 you're checking is v, and the 4 vertices of #2 are v1 ... v4. Inverse-rotate all 5 vertices by #2's orientation. (to inverse-rotate a vector u by an orientation matrix M, multiply u by M-transposed: M^T u , assuming that in your convention orientation works by left-multiplication.) The resulting 2nd box, call it #2', is now axis aligned - you can immediately check whether v' is contained in it.

If you found any #1-vertex inside of #2 - stop, you have intersection. Otherwise - continue.

A few optimizations immediately pop to mind (maybe you can store unrotated copies of the vertices in each box? if the sizes are fixed, maybe you can compare them to immediately eliminate one of the possible containments, and save 3 potential tests?) but unless you're applying it on gazillions of box pairs, this test should be cheap enough as is.

Regarding the motion, you can get as deep as you want there - look up 'continuous collision', and see for yourself. (I specifically remember some nice works by Stephane Redon). I whole heartedly believe that no game does any of this fancy stuff: if you are indeed moving extremely fast, you can subdivide your time step and perform collision checks on each position/orientation sub-iteration.

(edit:) There was another discussion right here about that, with nice references.