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

You say 2d, but also mention 3d as being more complex. For collision detection, you basically want to test if two shapes intersect each other. In 2D, with bounding boxes, these are rectangles. You'll need to use an algorithm to see if the rectangles intersect and also check if one is completely contained within another (3 tests for the simple algorithm). For 3d, these are cubes. Same thing. Look at this matrix of object-object intersections and find the ones you want. Check for intersection of the objects themselves, and also wither one is completely contained within the other.

This procedure can extend to not just bounding boxes, but also bounding speheres or to actual objects themselves in convex bounding hulls, polygons, or complete 3d objects. The end result is, as the objects progress through space and time, whether their surfaces collide or whether they are inside each other. In the case where your granularity is too coarse and, in the situation you are modelling, they should collide, but they end up moving past each other, you should do an additional ray bound's intersection test to see if some central, weighted point in an object intersects the bounds of the other.

Answer 2

If you have two bounding boxes (i.e. rectangles) with some arbitrary orientation (which I assume means some "rotation"), then I would do the following:

• Starting at an initial position (where I assume the bounding boxes are not intersecting), translate each box forward based on its velocity (however you're applying movements over time).
• Find the coordinates of the corners of each translated bounding box. These 4 coordinates define the endpoints of the 4 line segments that make up the edges of the bounding box.
• For bounding box #1, test for an intersection between each of its line segments and the 4 line segments of bounding box #2. You can do this using standard equations for computing the intersection point of two lines, as discussed here, for example.
• If there was an intersection, figure out the fraction of a move that was successful using the coordinates of the intersection points and the known translation you applied.
• Repeat the above steps for each update.

EDIT: A rough pseudocode (incorporating what was discussed in the comments) would look as follows:

...test for intersections between the OBB edges...
if any intersections are found{
    ...run code for when OBBs are partially overlapping...
}else{
    P = line segment whose endpoints are the OBB centers;
    ...test for intersections between P and OBB edges...
    if P intersects edges of both OBBs{
        ...run code for when OBBs are not touching...
    }else{
        ...run code for when one OBB is completely inside the other...
    }
}

Answer 3

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 4

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.

Answer 5

You probably should implement a quadtree (see wikipedia) to keep track of all the objects on the plane. I unfortunately have never implemented one for collision detection, but it seems that other people have been able to create similar scenarios to yours using quad trees.