Moving rects - find the moment of intersection

Game Mechanics
#1

I have two rectangles that are both moving (or could be moving) that cannot be rotated (will always be AABB). I have their last position and current positions stored, they are colliding at their current position but not at their last position. I also have the velocity used to get from last to current positions.

The question is, I’m wondering the best way to move them both to the point at which they collided to avoid overlap. The only thing I can really think of is to do line intersections using their vertices, but this definitely seems overly expensive. Because they are AABB, I can dissolve the situation to one where they are either colliding along the side of the squares (thereby reflecting only over the X velocity), or the top/bottom of the squares (a Y reflection). Pretty simple situations.

Still, I’m not sure the best way to get the point of intersection. Where in between last and current positions would they collide? I can think of lots of different ways but they all seem too slow. There’s got to be really cheap way of doing this given that I have two AABB.

#2

Can the rectangles move in any direction or only orthogonally (on the x and y planes)?

#3

And how would you handle the situation where they do not overlap in their last positions and not in their current positions, but there was a collision between them? Then you’d have to use swept rectangles.

To be honest, the collision check of 2 rectangle is so cheap, that any advanced algorithm to figure out the exact time of collision will be extremely slow. So it’s probably fastest to use a binary search to converge to the solution, despite that there might be more correct algorithms.

#4

I’m pretty sure that the exact solution won’t be too expensive, but for now here’s code to test for rectangle intersection that doesn’t involve computing line intersections


/**
 * Tests if two axis-aligned rectangles intersect
 * 
 * @param minA
 * @param maxA
 * @param minB
 * @param maxB
 * @return <code>true</code> if intersection
 */
public static boolean axisAlignedRectIntersection( Point2f minA,
		Point2f maxA, Point2f minB, Point2f maxB )
{
	boolean xOverlap = !( minA.x > maxB.x || maxA.x < minB.x );
	boolean yOverlap = !( minA.y > maxB.y || maxA.y < minB.y );
	return xOverlap && yOverlap;
}

I’ll have a think, might have more later…

#5

Read up on Separating Axis Theorem.

Google gives this: http://supertux.lethargik.org/wiki/Sweep_collision_algorithms
which leads to this tutorial: http://www.metanetsoftware.com/technique/tutorialA.html
which cites this article in it’s references: http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php
Page 3 of the article is An Axis-Aligned Bounding Box (AABB) Sweep Test

Some time ago I believe I used that article to implement the Sphere-Sphere sweep test(actually, I was interested in just circle-circle), and can confirm the algorithm works.

If you want to have nightmares tonight, just think about how you’d go about computing the sweep test for an arbitrary n-dimensional polygonal shape that is moving and rotating.

#6

I reckon I’ve got the solution. Code attached (you want the axisAlignedIntersectionTime() method), but the gist is:

  • Subtract the velocities so you’re testing a mobile rectangle against a static rectangle
  • Split the problem: for each axis find the time period over which the rectangles intersect on that axis: the time period between the high edge of rectangle A meeting the low edge of B, and low edge of A meeting high edge of B
  • If these time periods both exist (catch zero velocity case) and intersect, the rectangles first intersect at the start of the later time period

… and Robert is thy mother’s brother.

#7

This is (somewhat) what I had in mind, still I’m pretty sure a binary search is (much) faster, as each check is so cheap.

#8

I’d be really surprised if that were so
The above method is 6 subtractions, 4 divisions, a handful of comparisons and you’ve got the exact time of intersection - whenever that occurs on the unbounded timeline. You can do this once whenever the rectangles or velocities change, rather than per-frame, and it catches the case where small or fast rectangles skip through each other.
I really can’t see any way that stepping through time to find an intersection and then recursing to approximate the moment of impact will be faster in the general case.

#9

Thanks for all the responses. I was pretty close to all these in my current implementation, I just didn’t consider the time periods. That’s very cool that you can just compare the ranges of time at which they will collide and use that on both axes. Cheers!