Sign in to follow this  
hylke2

Boxed collision detection

Recommended Posts

hylke2    122
Hello. For my current collision detection, I use boxes. I've managed to calculate the boxes, but now I have to check wheter they overlap each other. This can be a problem, because you can't simply do like this:
if((BoxPt1.x > point.x && BoxPt2.x < point.x) && (BoxPt1.y > point.y && BoxPt2.y < point.y) &&  (BoxPt1.z > point.z && BoxPt2.z < point.z))
{
...
}
Because if your box is rotated, say 20 degrees around the z axis, it would be a much larger area. Ofcourse I know how to fix it, but it would involve some thinking of me, and some weird calculations. So I figured, I ask it here, because y'all most probably have an easy solution for this kinda things. So any idea how to get a right collision detection for boxed based collision detection? Thanx in advance, Hylke

Share this post


Link to post
Share on other sites
illadel4life    127
CD systems must be a hot topic.

Heres the rule of thumb I use that can be used on all axis.

a.low <= b.high && a.high >= b.low

Or a more if friendly'er

a.low > b.high || a.high < b.low

good luck

Share this post


Link to post
Share on other sites
Tom    352
I have an identical problem myself and would greatly appreciate an explanation of the solution or an algorithm (preferably C or psuedocode). In a shocking turn of events, Paul Bourke's geometry site does not contain an algorithm for determining collision between two arbitrarily rotated rectangles on a plane. ;) However, I do recall seeing a similar example that calculated the visible region between a camera frustrum and quadtree . . . if only I could remember where.

Share this post


Link to post
Share on other sites
jyk    2094
A short at-work answer. For AABBs in 2d or 3d, separating axis theorem. Simplifies greatly due to axis alignment; easy to implement. For 2d oriented rectangles/boxes, SAT again. Same principle, but in generic form to handle arbitrary axes. Robust and fairly straightforward in 2d. For 3d, same thing, but demands more care due to possible degenerate cross products. For all cases, boolean test = easy, penetration info = a little more complicated, swept test = a little more complicated than that, but all fairly manageable.

Share this post


Link to post
Share on other sites
hylke2    122
Thank y'all for the replies.
But what exactly means:
Quote:
The separating axis theorem tells us that, given two convex shapes, if we can find an axis along which the projection of the two shapes does not overlap, then the shapes don't overlap

Because I still don't quite understand what it's saying.

Share this post


Link to post
Share on other sites
Airo    197
also lookup oliii's tutorial here on gamedev.net.

for example take two axis aligned rectangles sitting on a plane(the x-axis). The projection of the rectangles on this plane are then the x-coordinates of the corners of the rectangles. This forms two intervals. If these intervals don't overlap, the rectangles can't possibly intersect.

Share this post


Link to post
Share on other sites
illadel4life    127
hylke2 to add what the guy above me just said, thats what I was trying to say. lol I look back and I see I might have been more confusing. You see, my example was for one axis. the "low" would be the lowest interval for an object. the "high" would be the highest Interval.

So apply the test to the X axis u have



*****|******|*******|******|

*****^******^*******^******^

a's low*****b's low
*********************a's high****b's high

sorry about the stars, they don't show spaces well.

if u perform the test I gave, you will see the first test would be true, the second would be false, both indecating that the x-axis of the objects overlap. Now thats just one axis. for a OBB I believe u have 2 more axis togo, and thats on the Y, and on the Z. Imagine doing a 14-dop, you would have 6 more axis togo.

Share this post


Link to post
Share on other sites
jyk    2094
This is somewhat a repeat of what the previous posters said, but I'll try to supply some more fun ascii art to illustrate the point. Here are two AABBs in 2d, and their projections onto the x axis:
    ------
A | |
| |
------

------
B | |
| |
------

1----2
----*--*-*--*
3----4
The projection of box A onto the x axis is labeled 1-2, and box B's projection is labeled 3-4. It should be clear from the diagram that if these two projected intervals didn't overlap, we could be certain that A and B didn't intersect. This is the idea behind the separating axis - it is an axis such that if the projected intervals of the objects onto that axis don't overlap, we can be certain the objects don't intersect.

In the above example, the intervals intersect but the boxes do not, so that can't be the whole story. The rest of the story is that we have to perform the same test using the y axis. You can see that in this case the projected intervals on the y axis would not intersect, therefore it's a separating axis and we know the boxes don't intersect. If the intervals were to overlap on both axes, we would know for certain that the objects intersect.

But how do we know which, and how many, separating axes to test? The first thing to note is that a vector and its negative are equivalent as far as the SAT is concerned. It can be shown that for convex objects in 2d, the potential separating axes are the normals to the edges. In the case of AABBs this leads trivially to only two potential axes, cardinal x and y. For oriented boxes in 2d it would be 4 axes, the 2 basis vectors for each box. There are still a few details left, such as how to find the projections of various objects onto an axis, but if you're only interested in 2d, that's about all you need to know to get SAT working.

For convex objects in 3d it's not as simple as testing the normals to all the faces, because the objects could also be separated along an axis that is the cross product of an edge from each object. This leads to a high number of tests which can quickly become impractical for arbitrary polytopes. For OBBs, though, it's manageable. You end up with 15 potential separating axes: the 3 basis vectors from each box, and the cross products of all possible pairs of basis vectors. Note that this works because every face normal and every edge of a box is parallel to one of its basis vectors, and we need not consider multiple separating axes which are parallel to each other.

Ok, well that turned out to be kind of lengthy. But perhaps that will help clear some things up.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this