Get collision time between two moving, non uniform Axis Aligned bounding boxes

Question

I have a problem finding the exact time of collision of two possibly moving or static objects. Both objects have AABB data (HalfExtents, Min, Max, Center vector and stuff) and a velocity vector. The objects, as I wrote, can move, but must not to. How can I get the exact collision time from now? Could you give me please a pseudo code, or at least some directions how can be this solved?

Answer 1

It's been a while since I've had to write code to do this, but here's how I used to do it, so I'm not going to write any code for this post, but I'm going to describe the theory in a way that hopefully sets you down the right path. You didn't mention whether their rotations changes at all during a single collision test, so I am going to assume they are not. The math gets much more complex rather quickly if you have an angular velocity as well.

Each box is made up of 8 points, and 6 planes. Both boxes can be moving, but since we only need to find the time during the frame where they collided, we can transform 2 moving boxes into 1 moving box by adding the velocity of one of the moving boxes (box A) to the other (box B) before setting the velocity of box A to 0. So you know have 2 boxes, one which is not moving, and one which is moving. For the purposes of the algorithm we're about do, this will work, since we only care about the movement of the boxes relative to each other, and not their velocities relative to the rest of the world.

You can now take each of the corners of Box B (the moving one), and convert each of it's corners into a line that extends along this frame's velocity. You can then do a simple check of an intersection with each of these lines from Box B against each of the planes that make up Box A. If any lines cross any plane, then by doing a plane vs. line collision, you can find out where on the plane the line crosses. The planes that make up the box are infinite length, so we need to check if the point is within the bounds of the box's plane. You can then do a dot product with that point of intersection against the normal coming out of each of the other 5 planes and make sure that the dot product is negative, which means you are "behind" the direction the plane is facing. If you are behind all 5 of the other planes on your point of intersection, then you have a collision. Save the time value for where on that velocity vector you had a collision. Repeat the same steps for each of the 6 planes, and save the smallest t value that is between 0 and 1.

At the request of the original asker, I'm expanding this section. If you run the algorithm above, you'll get all of the collisions for where a corner in Box B intersected Box A. You will not have the collisions for where Box A's corner intersects Box B, so repeat the algorithm above, but reverse the boxes. To help visualize it, in the case of our boxes, think about the types of collisions that can occur here. Since the planes of the boxes are flat, and they are convex. The fact that they are convex means we don't have any interior points, every vertex in the shape is a point. So there are only a few ways that these boxes can collide. One of the points on Box A can pass through one of the flat planes in Box B. One of the points in Box B can pass through one of the flat planes in Box A. A flat plane of Box A can hit a flat plane on Box B (for example, if they both have the same rotation). Finally, a point on Box A can hit a point on Box B (the corners are touching). The first test we did will detect whether a corner from Box B penetrated Box A, but a corner from Box A penetrating one of the sides of Box B wouldn't be detected. To detect that case, we can do the same tests we did in the first step, but reverse Box A and Box B. This will allow us to catch that collision.

In my example, I listed 4 possible collision types, so I'll briefly go over the last 2. If the 2 boxes have co-planar sides, then our collision should still catch it, since if the 2 boxes have coplanar sides, then a corner still needs to pass through one of the planes we detected earlier, and we should still catch it. A similar case is also true for the corners penetrating each other. You can potentially miss some collisions due to floating point error. You may not run into this case, but if you do, the standard way of handling it is to put in a tolerance/fudge factor for each of these tests, so that very close "near misses" still collide.

This is a relatively simple example that illustrates how most of these collision tests are run. What they are all doing, at a fundamental level, is breaking the collision down into the simplest possible checks we can do, and then doing the checks using algorithms that can determine the exact intersection time. If you want your boxes to be rotating during the collision, then you'll have to figure out how to take the rotation account. For example, you could do the same thing but instead of straight lines, you would have to use a curved line instead, which gets more expensive (algorithmically). If you wanted to not have a constant rotational velocity, then you'll have to break it down further. At some point of complexity, you won't be able to break your primitives down enough, and you will have to look at other ways of determining whether you had a collision.

For speed purposes, you'll also want to do some quick checks that you can use to discard the possibility of a collision. For example, if the start and end points of each corner on one of the boxes are all on the same side of any edge planes that make up the other box, then for sure no collision has occurred (since you didn't cross any planes). This check will be much simpler and faster to execute before you process any further, so you can use those sorts of checks to optimize your code if needed.