What's the fastest way checking if two moving AABBs intersect?

Question

I have two AABBs that are moving, what's the fastest way to check if they will intersect under a frame?

By moving I mean not just to check with the usual rectangle intersection method, I mean some kind of simple easy swept test that only returns a boolean, no hit time or anything else.

What I think is to simply do it like this:

But that Hexagon is quite complex and I don't know how to calculate an AABB - Polygon intersection, is there maybe an easier way?

Any programming language that you like the most, I can easily port it.

Thanks.

Answer 1

Use the Minkowski sum

A good way to solve this problem is to consider the intersection between a line of motion (v) translated to the origin (v') and the Minkowski sum of A rotated 180 degrees at the origin (A') and its obstacles (just B in this case): A' ⊕ B.

In the following picture I place A smack-dab in the origin of an arbitrary coordinate system. This simplifies understanding as rotating A by 180 degrees results in A', and v translated to the origin equals v'.

The Minkowski sum is the green rectangle, and the intersection points of a moving A and a stationary B can be found by doing line-AABB intersection. These points are marked with the blue circles.

In the following picture a different origin was used and the same intersection points are found.

Multiple moving AABBs

To make this work for two AABBs that move in a linear fashion during a specific period of time you would subtract B's velocity vector from A's velocity vector and use that as the line segment for the line-AABB intersection.

Pseudo code

def normalize(aabb):
    return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2),
            y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2),

def rotate_about_origin(aabb):
    return normalize({x1: -aabb.x1, x2: -aabb.x2
                      y1: -aabb.y1, y2: -aabb.y2})

# given normalized aabb's
def minkowski_sum(aabb1, aabb2):
    return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2,
            y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2}

def get_line_segment_from_origin(v):
    return {x1: 0, y1: 0, x2: v.x, y2: v.y}

def moving_objects_with_aabb_intersection(object1, object2):
    A = object1.get_aabb()
    B = object2.get_aabb()

    # get A'⊕B
    rotated_A = rotate_about_origin(A)
    sum_aabb = minkowski_sum(rotated_A, B)

    # get v'
    total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity())
    line_segment = get_line_segment_from_origin(total_relative_velocity)

    # call your favorite line clipping algorithm
    return line_aabb_intersection(line_segment, sum_aabb)

Collision response

Depending on the gameplay you would either perform more fine-grained collision detection (maybe the AABB's contain meshes), or move forward to the next phase: collision response.

When there is a collision the line-AABB-intersection algorithm will return either 1 or 2 intersection points depending on whether A ends its movement inside B or passes through it, respectively. (This is discounting the degenerate cases where A grazes B along their sides or along one of their respective corners.)

Either way, the first intersection point along the line segment is the collision point, you'd translate this back to the correct position in the world coordinate system (the first light-blue circle in the second picture along the original v, call it p) and then decide (e.g., for elastic collisions by reflecting v along the collision normal at p) what the actual position for A at the end of the frame will be (At+1).

If there are more than just 2 colliders this will get a little more complex, as you'd want to do collision detection for the second, reflected, part of v as well.

Answer 2

OBB - Oriented bounding box. Here's a tutorial

Effectively, a bounding box aligned with the Velocity vector of object A as the y-axis (up). It's width and height can be calculated by the starting and ending points of object A. You then compare this with the AABB of object B (treating it as an OOBB), and your golden.

If you're just looking for a quick intersection test to see IF they COULD possibly intersect, you could create an AABB that surrounds object A's AABB in both the starting and ending positions. If an AABB does-not intersect with this all encompassing AABB, then there is no intersection; However, this could lead to false positives, so you should only use it as a preliminary test.

Answer 3

You don't need OOBs and you don't need to use time-stepping collision detection. Just use the normal AABB swept test, see this link. In essense it does exactly what you have in your diagram: the moving AABB is "swept" from start point to end point and then that is used for collision detection against other, static AABBs.

If you are worried that this swept test is more expensive because it returns an "impact time", I think you prematurely optimizing.

More in-depth information about swept tests can be found in the excellent book: Real-Time Collision Detection by Christer Ericson.

Answer 4

You will need to first decompose the movement into smaller steps and use that information to calculate a high-level AABB. If the large AABB's intersect, you can then check the smaller steps to be more accurate.

Estimating whether or not there may have been a collision by checking AABB (or OOBB) using just the starting and ending positions can miss collisions if either object is rotating quickly and is longer in one dimension than another.

To calculate a more accurate estimate AABB, decompose the movement into smaller steps, and using only the initial AABB (not the object mesh), rotate the AABB (now just a box, not axis aligned) as the object would rotate and move at each step. The max and min points for each axis will give you the AABB that encloses the entire movement of the object.

If there is an intersection with the larger AABB, you can then use the smaller AABBs that were already calculated to determine where the collision may have been. For each of the smaller AABBs that intersect with the other object, you can then do the more expensive mesh intersection detection.

Answer 5

You will have to decompose the movement into smaller steps of movement. For example:

You want to decompose the movement using the greater componen (in this case, X-axis), and then check for collision in each step.

This might look too expensive, but take into account that an object moving faster than it's own width each cycle will be EXTREMELLY fast, so this scenario is not as common as you first might think.

Answer 6

You should also use relative speeds for the collision check so one AABB is "static" and the other move at a speed of its own speed minus the speed of the "static" one.

The fastest way to see if they may intersect is to just expand the moving AABB with the speed.

for example the AABB is moving right with 0.1 x/frame, then you extend it so the left edge remains the same and the right edge is 0.1 further. Then you can check with the new AABB. If false then there is no collision. (early return and accurate for small speeds).

Then you can check if the end and start AABB of the moving object intersects. if true then return true.

Otherwise you need to check whether the diagonal intersects the static ABB.

This involves getting the coordinates of the diagonal where x= left edge of the static and the right edge see if the y is inside the bottom and top. (repeat the other way around)