Cube-Cube collision detection

Started by
4 comments, last by wildbunny 12 years, 7 months ago
Hi.

Im currently writing an FPS. I allready have a working level and collisions between the player and the floor/walls work fine. I Test the players collision box with the floors/walls collision boxes using this simple logic.


boolean valueInRange(float value, float min, float max)
{ return (value >= min) && (value <= max); }

boolean rectOverlap(Rect A, Rect B)
{
boolean xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);

boolean yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height);

boolean zOverlap = valueInRange(A.z, B.z, B.z + B.depth) ||
valueInRange(B.z, A.z, A.z + A.depth);

return xOverlap && yOverlap && zOverlap;
}


But that obviously doesnt work if i need to test the players collision box against a rotated collision box like for example a ramp.

I can calculate the coordinates of the 8 corners of the rotated colision box in world space but how would i determine if it intersects with the players colision box. Its a givin that the players collision box will never be rotated for incase that helps.

Any help appreciated. Thnx in Advance!
Advertisement
Hi,


Hi.

Im currently writing an FPS. I allready have a working level and collisions between the player and the floor/walls work fine. I Test the players collision box with the floors/walls collision boxes using this simple logic.


boolean valueInRange(float value, float min, float max)
{ return (value >= min) && (value <= max); }

boolean rectOverlap(Rect A, Rect B)
{
boolean xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);

boolean yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height);

boolean zOverlap = valueInRange(A.z, B.z, B.z + B.depth) ||
valueInRange(B.z, A.z, A.z + A.depth);

return xOverlap && yOverlap && zOverlap;
}


But that obviously doesnt work if i need to test the players collision box against a rotated collision box like for example a ramp.

I can calculate the coordinates of the 8 corners of the rotated colision box in world space but how would i determine if it intersects with the players colision box. Its a givin that the players collision box will never be rotated for incase that helps.

Any help appreciated. Thnx in Advance!


I'm not sure why it matters if the players box would be rotated?

I use code similar to this code

boolean rectCol(Rect A, Rect B) //rectangle collision because overlap is such a long word ;)
{
bool xCol = (A.bbMin.x <= B.bbMax.x) && (A.bbMax.x >= B.bbMin.x);
bool yCol = (A.bbMin.y <= B.bbMax.y) && (A.bbMax.y >= B.bbMin.y);
bool zCol = (A.bbMin.z <= B.bbMax.z) && (A.bbMax.z >= B.bbMin.z);
return xCol && yCol && zCol;
}


Of course this is not live code, it was whipped up just to demonstrate the simplicity of such code. Also if the language supports it pass addresses around as they are obviously smaller than passing whole complex objects! hope this helps there!

Ramp collision should be implemented with the same bounding box collision, but then you would need to find the collision point within the box to test if the "player" is colliding with the ramp
Hi!

Ok, so, the rotated box you're talking about is called "OBB" (oriented bounding box). I don't have an AABB to OBB function handy at the moment, since I've never used it, but that's the keyword you're looking for anyway.

Now, a small comment regarding your code... You could put all those checks in one line. Basically, something like:



return (valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width)) &&
(valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height)) &&
(valueInRange(A.z, B.z, B.z + B.depth) ||
valueInRange(B.z, A.z, A.z + A.depth));


It will be faster, since there will be lots of early outs, instead of having to create 3 bools, calculate all of them and then check them.
If you could, however, try using Lewis's version, it has less checks than the whole valueInRange thing.
And it could be done even faster by doing:


return (A.bbMin.x <= B.bbMax.x) &&
(A.bbMax.x >= B.bbMin.x) &&
(A.bbMin.y <= B.bbMax.y) &&
(A.bbMax.y >= B.bbMin.y) &&
(A.bbMin.z <= B.bbMax.z) &&
(A.bbMax.z >= B.bbMin.z);

Hello

Maybe there's a more specific algorithm for arbitrary boxes (oriented bounding boxes, OBB), but I know that the SAT (separating axis theorem) method could solve this problem, it works on arbitrary convex polytopes (2D and 3D) so it works for simple boxes too.
Hi, I'm sure if the compiler did not optimize code for us we would have to inline the code like that but can anyone confirm or deny that the compiler does this? I'm sure C++ is smart enough to do basic var stacking and loop unrolling where needed... Hopefully anyway :rolleyes:(this is my hopeful face)


Now, a small comment regarding your code... You could put all those checks in one line. Basically, something like:



return (valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width)) &&
(valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height)) &&
(valueInRange(A.z, B.z, B.z + B.depth) ||
valueInRange(B.z, A.z, A.z + A.depth));


It will be faster, since there will be lots of early outs, instead of having to create 3 bools, calculate all of them and then check them.
If you could, however, try using Lewis's version, it has less checks than the whole valueInRange thing.
And it could be done even faster by doing:


return (A.bbMin.x <= B.bbMax.x) &&
(A.bbMax.x >= B.bbMin.x) &&
(A.bbMin.y <= B.bbMax.y) &&
(A.bbMax.y >= B.bbMin.y) &&
(A.bbMin.z <= B.bbMax.z) &&
(A.bbMax.z >= B.bbMin.z);



I am also quite sure you need extra brackets and to change some of the && to || ala

return ((A.bbMin.x <= B.bbMax.x) || (A.bbMax.x >= B.bbMin.x)) && ((A.bbMin.y <= B.bbMax.y) || (A.bbMax.y >= B.bbMin.y)) && ((A.bbMin.z <= B.bbMax.z) || (A.bbMax.z >= B.bbMin.z));

voilla this now works as expected when I test it :P(oh the cheek of me)
by the way i'm not poking fun I'm just in a very good mood :D
There is a much neater way to tell if two AABBs overlap.

Firstly, start using a vector library to help with adding, subtracting and so forth; it will lead to less bugs and make your code more readable.

If you define an AABB by two vectors, one being its centre and the other its half-extents (half the length, width and height), then you can tell if two AABBs overlap by doing this:

D = |centreB-centreA| – (halfExtentsA+halfExtentsB)

binary overlap = D.x < 0 && D.y < 0;



Where |a| = abs(a).

However, if you want OBB vs OBB, its a much more difficult test. I would use a sphere or a capsule to represent the player instead of a box - the tests for those primitive are much easier :)

Cheers, Paul.

This topic is closed to new replies.

Advertisement