box-box intersection?

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.

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!

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]

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.

Thanks MrRowl, I should have thought of that case.