🔒 Locked

OBBOX / OBBOX collision accuracy

Started by Marmakoide Aug 11, 2005 at 12:38 AM 7 replies 1.5k views

Original Post

Aug 11, 2005 at 12:38 AM

Hi everybody I'am using an OBBOX vs OBBOX collision function, taken from the Wild Magic library by David Eberly. It seems to doesn't work for some minor boxes configurations. If I perform the test isColliding(boxA, boxB) sometimes, the answer will be different from isColliding(boxB, boxA) with *exactly* the same boxes. Is anybody here who meet the same problem ?

intrest86

Aug 11, 2005 at 1:15 AM

I don't know what the function is in the book, but OBB vs OBB should not be a troublesome collision function, and unless I am missing something is just a handful of comparisons with no data manipulation.

Marmakoide

Aug 11, 2005 at 1:20 AM

The code of this function is available here :
http://www.geometrictools.com/Intersection.html

And I found some cases where collisions are simply missed. The fact that
isColliding(boxA, boxB) != isColliding(boxB, boxA)
could be due to numerical precision, float numbers are evil. I search for a more bullet-proof intersection detection algorithm.

ajas95

Aug 11, 2005 at 1:28 AM

Well I guess that the implementation uses SAT, which involves cross products of the axes. This could be unstable except that he seems to check for the unstable case, and then handle the boxes as 2D, removing the parallel axis.

Other than that, there could be some minor instability between transforming one box into the other's space, and vice-versa... but that should be small compared to boxes whose axes are nearly aligned. Have you checked what relative orientations lead to instability?

Marmakoide

Aug 11, 2005 at 1:38 AM

Yes, it's a nice SAT implementation.

You're right, the problem comes when the boxes had nearly aligned axis. Even if I work in double precision, the problem is still here. I checked the compiler option , no -ffast-math or such precision killers.

oliii

Aug 11, 2005 at 5:15 AM

in the case of OBBs, if the separation axes are degenerate (cross product of directions), they can be ignored totally. Then you should not get spurious results, and it should be consistent (with slight loss of precision).

Well, that's the theory anyway.

Marmakoide

Aug 11, 2005 at 6:23 AM

Ok, I will add a special case in the test : if the boxes axes are nearly perpendicular, then it just an ABBox test. If it works, I will add a reply here. Thanks a lot !

oliii

Aug 11, 2005 at 8:56 AM

you don't even need that.

When you reached the stage of cehcking edge cross products, if the sep axis

Sep = A0.Cross(B0);if (Sep.Dot(Sep) > 1.0E0-8f){    // the normal sep test on the axis    if (IsSeparationAxis(Sep, BoxA, BoxB))    {         return false;    }}Sep = A0.Cross(B1);if (Sep.Dot(Sep) > 1.0E0-8f){    // the normal sep test on the axis    if (IsSeparationAxis(Sep, BoxA, BoxB))    {         return false;    }}Sep = A0.Cross(B2);if (Sep.Dot(Sep) > 1.0E0-8f){    // the normal sep test on the axis    if (IsSeparationAxis(Sep, BoxA, BoxB))    {         return false;    }}// ect.....

thing is, you can have two boxes resting on a table. One axis will be parallel, but the other two wont. So doing a special case of AABB or whatever isn't gonna solve your problems.

the only special case in case of degenerate axes, is when you want to do triangle / triangle collision (or polygons, something which doesn not have a 3rd dimension), and the triangles are parallel.

Then you need to change the procedure and do something more like a 2D test.

For solid shapes, no special case should be necessary.

Marmakoide

Aug 11, 2005 at 10:29 AM

... That's I already did ... But you give some ideas, I will test it.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.