Jump to content
  • Advertisement
Sign in to follow this  
Mach2

box-box intersection?

This topic is 4831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I just want to do a box-box intesection check. I thought it's simple, but it turned out that it's not. It is the box-box intersection check, not the box-box collision test. The box-box collision test (which return true or false that the boxes intesect each other and doesn't give out the intesection points) is simple, as the separating axis algorithm (for OBB/OBB) appears to be the best and most popular one out there. But I rarely find any "globally" similar algorithm that does the same thing and also return the intersection points? Even in the very good book "Real-time collision Detection" I still cannot find any bits about that (or I just missed it?) I thought of several approaches... The "blind-test" doing tri-tri works well, i'm currently using the "brute-force" method which ends up at doing all 144 tri-tri tests. It's too slow (for multiple detection) even using the fastest Muller tri-tri test. If I divide the box into several bits (faces) and do overlap tests for each set of bits before doing tri-tri tests then it will be faster... but is there any different ways? I even tried to do a full test, which consider all possible vertex-face, edge-edge tests but it's quite hacky and I felt confusing after a while doing the "if-if and if" things... Anybody who did that can you help me out of the box? I saw some demos from MrRowl and b34r that did the work quite well. I thought there's must be other ways than the "blind" way I'm doing.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Mach2
I just want to do a box-box intesection check. I thought it's simple, but it turned out that it's not.
It is the box-box intersection check, not the box-box collision test. The box-box collision test (which return true or false that the boxes intesect each other and doesn't give out the intesection points) is simple, as the separating axis algorithm (for OBB/OBB) appears to be the best and most popular one out there. But I rarely find any "globally" similar algorithm that does the same thing and also return the intersection points? Even in the very good book "Real-time collision Detection" I still cannot find any bits about that (or I just missed it?)

In short, consider switching to the continuous version of the separating-axis test that I describe in section 5.5.2. After you've found the time of collision, you can derive contact points from the features that are touching at the time of collision.

If you search the forums, I think you'll find that oliii has posted some code for this.

If for some reason you don't want to go down that route, for two statically intersecting OBBs, you can look at the separating axis with the least overlap and derive your penetration depth and contact points from that. It's not ideal though, because if e.g. the penetration is deep enough, you may be trying to separate the boxes in a completely bogus direction.

Share this post


Link to post
Share on other sites
The method I use involves:

1. Using a separating axis test to see if the boxes overlap - this gives a separation/collision direction/normal, and a penetration depth

2. If they do overlap then I intersect all the edges of one box against the faces of the other (I transform the second box into an axis-aligned box, so this isn't actually as slow as it sounds) - and then the other way around. This gives all the contact points. Then points are combined in order to reduce their number to a reasonable value (max 8 per box pair).

This works pretty well and is straighforward to implement. However, I'm sure it's slower than extracting features from the separating axis test, so I'm planning on changing this code.

Incidently, as you're writing geometry functions (and after a while you end up with a _lot_!) it's worth splitting them up - I use the following categories:

1. Distance - just returns distance between two primitives - would be 0 if they overlap, and (optionally) the closest features on each primitive. e.g. Function like:

tScalar PointBoxDistance(const tPoint&, const tBox&, tPoint* boxPoint = 0);

would return the distance from a point to a box, and (optionally) the closest point on the box's surface to the point.

2. Overlap - just returns whether two primitives overlap, and if so some (optional) info about the details of the overlap. e.g.

bool SegmentBoxOverlap(const tSegment&, const tBox&, tScalar* pt1 = 0, tScalar* pt2 = 0);

so this would tell you if a line segment overlaps a box, and if so (optionally) where the two "entry/exit" points are (paramters of the line segment).

3. Intersection - tells you if two "moving" primitives will intersect, and if so some (optional) info about how they intersect - e.g. contact points at the time of intersection. e.g.

bool SweptSphereIntersection(const tSegment& sphereSegment, tScalar sphereRadius, const tBox& box, tSweptSphereBoxIntersectionResult* details = 0);

would tell you if a sphere swept along a segment would intersect a static box. If it does then details (if non-zero) would be filled in to tell you when the intersection happens, the collision normal etc.

Or something like that... the details are probably less important than just being consistent. Actually reading your post again I think you're probably already doing this, but with different terminology... but I'll post this anyway!


Share this post


Link to post
Share on other sites
Thanks Christer Ericson and MrRowl for the replies.

Actually I read the part about doing intersection test between two moving OBB. Since I also want to do the test in the "static" case so I didn't use that algorithm. I did implement it and it works quite well, but we have to know additional data (previous time etc) and the algorithm only return one intersection point (I want more in case of edge-edge collision) so I didn't use that.

Thanks MrRowl for the idea of separating primitive tests. I found out that it should be done that way after a while. Good for me that Christer's book is a rich library about collision stuffs so I didn't have to sit down and do the math all over in pain.

Maybe I just stick with MrRowl's suggestion and look at the method of extracting features from the separating axis later. Just a quick question for that, through, since MrRowl already mentioned about it. Why do we need 8 contact points for box-box test? I though 4 is fine for rigid body simulation.

Edit: Oops, thought that I should read all the posts from MrRowl, b43r and oliii before asking any questions...

[Edited by - Mach2 on August 21, 2005 9:41:03 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Mach2
Why do we need 8 contact points for box-box test?


Draw a square. Then draw another square with its centre in the same place, but rotated through 45 degrees. There are 8 intersection points.

This is what you get if you have one box sitting on top of another, rotated through 45 degrees, viewed from above.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!