Box collision

Your first idea is on track. Only you have to do it for both boxes, and the logic is reversed in that you're trying to find a way the boxes don't intersect, and if that fails then you're left with an intersection. Some psuedo-code (assuming outward-facing planes):

for each plane on box 1  if all points on box 2 are in front of plane[0]    return no_intersectionfor each plane on box 2  if all points on box 1 are in front of plane[1]    return no_intersectionreturn intersection

In other words, if you can't find a separating plane, then they must be intersecting (or one inside the other). We chose the planes that define the boxes because they're the most tight-fitting.

Ah, the topic du jour. The solution for this (the separating axis theorem) has been discussed a great deal here as of late, so a search through the last few pages of posts will turn up a lot of information on it (try the 'adding a vector' thread, among others).

The first step is to take the dimensions (width, height, depth), and turn them into the often more useful form 'extents'. The extents are simply half of the dimension along each axis. So you would have:

float extents[3];extents[0] = width/2;       // Extent along x axis in local spaceextents[1] = height/2;      // Extent along y axis in local spaceextents[2] = depth/2;       // Extent along z axis in local space

If your width, height and depth are mapped to different axes, just adjust accordingly.

The next thing you need is a local coordinate frame for each box. For this you'll need an 'axis-angle to matrix' function. The basis vectors (local box axes) will then be the rows or columns of this matrix. The origin of the coordinate system is obviously the box position.

The other threads (and the many resources available on the subject) will explain the basic idea behind the SAT, but I'll go ahead with the box-specific details. The first thing you need to be able to do is find the projected radius of an oriented box onto an axis:

float radius =    box_extents[0]*fabs(axis.Dot(box_axis[0]))+    box_extents[1]*fabs(axis.Dot(box_axis[1]))+    box_extents[2]*fabs(axis.Dot(box_axis[2]));

Next, we need to be able to find the projected interval of a box onto an axis:

float center = box_position.Dot(axis);float radius = GetProjectedRadius(box, axis);float min = center - radius;float max = center + radius;

And a function to determine whether two intervals overlap:

if (max0 < min1)    return false;if (max1 < min0)    return false;return true;

You're now set to perform the separating axis test. For boxes there are 15 axes to test - the basis vectors for each box (6 total), plus the cross product of each combination of basis vectors for each box (9 total). You can bail as soon as you find a separating axis. Together you get something like:

float min0, max0, min1, max1;Vector3 axis;for (int i = 0; i < 3; ++i) {    axis = box0.axis;    ProjectBox(box0,axis,min0,max0);    ProjectBox(box1,axis,min1,max1);    if (!TestIntervals(min0,max0,min1,max1)) {        return false;    }    axis = box1.axis;    ProjectBox(box0,axis,min0,max0);    ProjectBox(box1,axis,min1,max1);    if (!TestIntervals(min0,max0,min1,max1)) {        return false;    }}for (int i = 0; i < 3; ++i) {    for (int j = 0; j < 3; ++j) {        axis = box0.axis.Cross(box1.axis[j]);        ProjectBox(box0,axis,min0,max0);        ProjectBox(box1,axis,min1,max1);        if (!TestIntervals(min0,max0,min1,max1)) {            return false;        }    }}return true;

That's the simplest possible implementation. It doesn't check for degenerate cross products, and skips a bunch of optimizations. Also, it's off the top of my head, so is untested and not guaranteed to be error-free.

But, that's the general idea for boolean intersection between oriented boxes. The test can be expanded to incorporate linear velocity, and to return contact information.

'Hope that helps.

Quote:

Original post by jyk That's the simplest possible implementation.

Is that the simplest possible way to implement SAT, or the simpliest way to see if two boxes intersect? I'm not trying to be a smartass I'm really curious to know if the way I suggested works or if there are a few cases I've overlooked that don't work. Because if so my intuition has been failing me all these years!

Quote:

Is that the simplest possible way to implement SAT, or the simpliest way to see if two boxes intersect? I'm not trying to be a smartass I'm really curious to know if the way I suggested works or if there are a few cases I've overlooked that don't work.

I wouldn't feel comfortable saying that the SAT is the absolute simplest way to test for intersection between two boxes unless I had implemented every possible method myself, which I haven't. But I'm pretty sure it's the simplest, at least in terms of minimal code and conceptual clarity.

Unless I overlooked something, my previous post included all the code necessary to perform the test using the SAT. So at least by the 'minimal code' metric, a competing algorithm would have to amount to less code than that, and I don't know of any alternate method (GJK, LP, DK hierarchy, feature-tracking, brute-force, etc.) that would do that.

As for the point-plane method:

Quote:

for each plane on box 1 if all points on box 2 are in front of plane[0] return no_intersectionfor each plane on box 2 if all points on box 1 are in front of plane[1] return no_intersectionreturn intersection

The first observation I'll make is that the box symmetry makes testing every corner against the plane unnecessary. The corners-plane test requires storing the corners explicitly and updating them whenever the box orientation changes. (Or, I suppose you could transform the plane into box space.) Then, the box-plane test requires 8 dot products. You can do the min-max-corner trick, which is only two dot products, but you still have to store the corners and then index based on the signs of the plane normal. So no matter how you approach it, it seems to me this approach requires more work and/or more memory than the center-radius test. The latter comes out ahead, I think, because it only requires the minimum representation for the box (coordinate frame and extents), 4 dots, and a few arithmetic operations. So the first modification I'd make to the above algorithm is to replace the corners test with the center-radius test.

The next problem is geometric. In 2d, the above method works fine. But in 3d, two non-intersecting boxes can be positioned in such a way that none of the face planes separates them. This leads to the 'rule' for testing 3d polytopes for intersection using the SAT: the potential separating axes are the normals to the faces, and the cross products of every edge from polytope A with every edge from polytope B. Only by testing all of these axes can you confirm that the objects are intersecting.

With boxes, every face normal and every edge is parallel to a box axis. Therefore, the axes to test are the box axes and the cross products of the box axis combinations, for a total of 15.

So, I don't know of a simpler method for performing this particular test. But that doesn't mean there isn't one :) Also, let my clarify that by 'simple' I don't necessarily mean 'most efficient' (although I think the oriented box SAT test would be efficient enough for most purposes).

Quote:

Original post by jyk The first observation I'll make is that the box symmetry makes testing every corner against the plane unnecessary. The corners-plane test requires storing the corners explicitly and updating them whenever the box orientation changes.

Not necessarily, you could generate the corners each time based on the box position, size, and orientation. But that still is a lot of work, so moot point I guess.

Quote:

But in 3d, two non-intersecting boxes can be positioned in such a way that none of the face planes separates them.

These are the special cases I was getting at that defy my intuition. While I'm also certain there are such cases, I've yet to come up with one. As in, I'm trying to position two 3D boxes in my head such that this is the case and I haven't been able to. But once I start getting into physics simulations I won't go with any more of my home-grown tests and use well-established ones.

Quote:

Not necessarily, you could generate the corners each time based on the box position, size, and orientation. But that still is a lot of work, so moot point I guess.

Ok, you can replace the 'and' in 'storing the corners explicitly and updating them' with 'and/or' :) As you note though, it's still a lot of work. Let's say you have 20 boxes, so that's, what, 190 box-box tests. So if you don't cache the corners, you have to compute them 380 times per frame! If you do cache them, you have to compute them 20 times per frame, and store them at the expense of 24 floats per box. The storage obviously isn't a big deal unless you have a lot of boxes or are tight on memory, but in any case it's just not a win.

Quote:

I'm trying to position two 3D boxes in my head such that this is the case and I haven't been able to.

It's easier to see if you can move around, but basically, none of the 12 face planes separates the two boxes. This is where the edge cross product tests are required to determine non-intersection.

[Edited by - jyk on October 30, 2005 2:23:24 AM]

Yeah, not five minutes after I posted I realized when the boxes have their edges facing each other like that then none of their plane faces will separate them. Live and learn!