Axis-Aligned Bounding-Box/AABB collision detection is trivially easy and can be determined with a few well placed tests - in case you don't want to look on the Internet, here's a copy-paste from MotorJ source:

[code]

short col_aabb_aabb(vector3 & a_min, vector3 & a_max,

vector3 & b_min, vector3 & b_max){

return !((a_min.x > b_max.x) || (b_min.x > a_max.x) ||

(a_min.y > b_max.y) || (b_min.y > a_max.y) ||

(a_min.z > b_max.z) || (b_min.z > a_max.z)) ;

}

[/code]

Now, determining what to do with that is another thing. Specifically, when you wish to have "physical" axis-aligned boxes instead of using them only for bounding box tests.

Suppose we would like to be able to give them such a use. For ease, let's start by thinking one of them is fixed and the other one is capable of moving. I plan to consider when both boxes can move and have mass in a further post.

So, for a movable and a fixed box here's the steps we need to take, the way I see it:

- Determine the direction in which the box needs to travel to reach a non-collision state

- Move the box

Moving the box once the correct direction has been found is easy. Only one of the coordinate needs to be altered, and it needs to be set to center of the fixed box + half fixed box's size + half movable box's size. The coordinate that needs to be modified matches the direction the box needs to be moved in to reach a non-collision spot (there can be cases where the box could be moved in more than one direction the same amount to reach a non-collision spot, however those cases are very uncommon, and usually moving it in either direction is satisfactory from the user's point of view).

However, determining this direction can be tricky - especially because though an AABB cannot be rotated, it can still have pretty different measures in different axes. So finding out the distance between box centers and choosing an axis won't work, for example.

So, to answer this question, after a long time I found out this possibility: find out how much both boxes overlap on each axis. Then the axis with the least overlap will point to the direction in which the box should be moved.

How do we find the overlapping region? Well, the plan goes like this:

- Find the right coordinates

- Do subtraction

- ???

- PROFIT!!!

To make things simpler, let's for a moment imagine that we want to find out the overlap between two lines, in only one dimension. Let's keep it nice and simple:

The overlap would then be represented by the red line in the following figure:

So how do we determine this "overlap" line? well, we need to find out whether L1.end or L2.end is smaller, and whether L1.beginning or L2.beginning is greater. then,

Overlap.end = min(L1.end, L2.end);

and

Overlap.beginning = max(L1.beginning, L2.beginning);

Then, this is what we need to do on each axis - find out the overlap as we did with as simple line -- each axis being a line, and afterwards compare them to know which axis has the least overlap, and move the box in that direction.

But, before I give you the code, one last observation: What happens if the movable box is on one of the negative sides of a fixed box?

Well, this can be solved by subracting the fixed box's center to the movable box's center, and paying attention to the sign of each coordinate.

So finally, here's some (pseudo)code:

[code]

// First choose a box and find out the directions it should be moved along

// (I choose box0; subtracting the center of box1 to box0 will give me

// the directions I need)

// (supposing vector math notation is allowed)

directions = box0.center - box1.center;

// Find out closest measures of the "greatest" corners of the boxes

endp[1].x = min(box0.corners[1].x, box1.corners[1].x);

endp[1].y = min(box0.corners[1].y, box1.corners[1].y);

endp[1].z = min(box0.corners[1].z, box1.corners[1].z);

// Repeat same procedure for Y

// and Z coordinates

// Do opposite procedure for lowest corners

endp[0].x = max(box0.corners[0].x, box1.corners[0].x);

endp[0].y = max(box0.corners[0].y, box1.corners[0].y);

endp[0].z = max(box0.corners[0].z, box1.corners[0].z);

// The overlap will be

overlap = endp[1] - endp[0];

// Once the overlap is found,the closest way to a non-collision state will be

// to move box0 along the direction with the minimum overlap.

// suppose in this case it is "y":

If ((overlap.y < overlap.x) && (overlap.y < overlap.z))

MoveAxis = AXIS_Y;

if (moveAxis == AXIS_Y)

box0.center.y = box1.center.y + (sign(directions.y) * ((box0.size.y + box1.size.y)/2));

[/code]

< Back to blog