views:

1616

answers:

5

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.

A: 

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.

John Ellinwood
The question is specifically about ORIENTED bounding boxes that can be rotated, not axially aligned boxes.
sludge
+1  A: 

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...
    }
}
gnovice
I don't think that will cover the case where one OBB is completely inside the other since the segments won't intersect, yet the OBB would.
Erich Mirabal
Yes, that would be a special case you would need additional testing for. But if the OBBs are moved in small enough increments, an intersection is likely to happen first before one OBB enters the other.
gnovice
I know this may not be in his use case, but what if the initial condition is that one is already inside the other? I think he could draw a line from center point to center point. If the line only intersects the lines from one of the OBBs, then one is inside the other. This would have to be done after running your test to rule out partial overlap. Is there an easier check than that?
Erich Mirabal
(btw, I ignore the case where one of the OBB is smaller than the delta movement since you already mentioned 'small enough increments' which should take into account the sizes of the OBBs).
Erich Mirabal
I would have to double check this, but I believe one way to test for an OBB being inside another would be to create a vector from center point to center point and test if it either a) intersects edge lines for only one OBB or b) does not intersect any edge lines for OBBs and has a total length less than half the length of a diagonal of an OBB.
gnovice
Someone want to explain the downvote?
gnovice
+4  A: 

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.

Mez
I think it would help to explain this a bit more, don't you? If I'm reading the theorem correctly, he would have to generate an axis perpendicular to each rotated side, project the OBBs to that axis, and test for overlap. Right?
Erich Mirabal
Sounds like an interesting algorithm. More detail would be nice. =)
gnovice
Erich, you just have to check that all the vertices of the box are on the same side of the separating axis. I know there is already a question on here that explains this more fully.http://stackoverflow.com/questions/115426/algorithm-to-detect-intersection-of-two-rectangles
BigSandwich
Also, if you want to be completely accurate, you should sweep the non-fixed rectangle before testing for intersection. Then you compare the swept volume to the fixed rectangle. Other wise you will miss collisions if the rectangles can jump past each other in a single frame.
BigSandwich
Adding a 'Sweep and prune' is indeed necessary if you want to test the collision detection between (fast) moving objects, otherwise you'll likely miss collisions, especially when using long time steps.
Mez
+2  A: 

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.

Ofek Shilon
+1 for the edit. I was actually thinking about -1 for the initial answer, but I think the edit saved you :). I guess somebody should close this question as a duplicate.
Erich Mirabal
i still stand behind my suggestion. why -1?
Ofek Shilon
Just to be clear, I didn't downvote you. The answer was very hard to follow (even though I see what you are saying and after reading it a couple of times it makes sense), it didn't explain or link to how you would inverse-rotate the vertices. Also, did you mean "if any of the 4 vertices" and not 3?
Erich Mirabal
Thanks for the comment. I edited it accordingly.
Ofek Shilon
A: 

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.

Darwyn