12
\$\begingroup\$

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:

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ I'm confused. You specifically mention "swept test", have you tried the typical AABB swept test? It does exactly what you want. \$\endgroup\$ – SomeWritesReserved Jan 28 '15 at 21:30
  • 1
    \$\begingroup\$ I agree with comment above - what is wrong with "classic" test? Moreover, most of proposed solutions here are clearly slower than that...plus some of them can give wrong results(not robust). \$\endgroup\$ – wondra Jan 28 '15 at 21:39
  • \$\begingroup\$ You could try the Separating Axis Test gamedevelopment.tutsplus.com/tutorials/… \$\endgroup\$ – Pharap Jan 29 '15 at 3:22
8
\$\begingroup\$

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.

Minkowski sum - degenerate case

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

Minkowski sum - more general case

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).

Collision response

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, most interesting. Could you please explain how do you handle the case when A and B intersect during the move, but end the move without intersection ? \$\endgroup\$ – GameAlchemist Jan 30 '15 at 7:04
  • \$\begingroup\$ @GameAlchemist That would be collision response, and not so much collision detection (the question's original subject). But I like Paint, so check out the edit. :-) \$\endgroup\$ – Eric Jan 30 '15 at 10:30
  • \$\begingroup\$ Thanks for the update (and hurra for the schemes :-)), this was not my question but helped me understand that your algorithm already handles the case when A completely passes through B. \$\endgroup\$ – GameAlchemist Jan 30 '15 at 11:26
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

AABB approximation edge case weakness

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ or precalculate the max width the BB can for any rotation and use that \$\endgroup\$ – ratchet freak Jan 28 '15 at 22:32
2
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ This method is bad, because it will not catch some cases (for example a box being close to first and the second you drew) and increasing sampling would be overkill. Simple Polygon test using SAT should be fast enough and reliable. \$\endgroup\$ – Sopel Jan 28 '15 at 21:14
  • 1
    \$\begingroup\$ Yeah, this is an OK solution but not too great. Accuracy rapidly decreases when the collision nears the corners of the objects, performance decreases as speed increases (or accuracy, depending on the implementation), and it's just unnecessarily hacky. \$\endgroup\$ – BWG Jan 29 '15 at 0:37
2
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.