• Advertisement
Sign in to follow this  

AABB vs. AABB sweep test (collision)

This topic is 4404 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have been looking around for an efficient AABB vs. AABB sweep test, and the best that I've been able to find is just what I came up with myself: finding the overlap times for each dimension separately and then finding the overlap between those for the final time range. This seems to be something of a complex process, and I am wondering whether or not anyone has a more efficient solution. Thanks, Sean Purser-Haskell

Share this post


Link to post
Share on other sites
Advertisement
I'm not sure whether this is what you're looking for, but I have some code that works with 2d rects. It should be fairly straitforward to extend it in the 3rd dimension:


def non_collision_vector(
rect1,
rect2,
velocity1,
velocity2
):
"""Return the vector which, when added to rect1, puts it at the very
point in time before it intersects with rect2.

NOTE:
This should not be used to determine a collision; this does not check if
the collision will happen this frame or not.

"""


# Find the relative movement of the first rect to the second
relative_velocity = vector2d.sub(velocity1, velocity2)

# Use this to find the "base corner" used in the other calculations.
# The base corner is the corner between the two possible collision sides
# of rect1. The relative velocity points towards the base corner.
#
# The horizontal and vertical boundaries are the x and y values,
# respectively, of the horizontal and vertical sides on rect2. One of
# these two sides is the one that should fit snug against rect1.
base_corner = [0, 0]
horizontal_boundary = 0
vertical_boundary = 0
if relative_velocity[0] >= 0:
base_corner[0] = rect1.x + rect1.width
horizontal_boundary = rect2.x
else:
base_corner[0] = rect1.x
horizontal_boundary = rect2.x + rect2.width

if relative_velocity[1] >= 0:
base_corner[1] = rect1.y + rect1.height
vertical_boundary = rect2.y
else:
base_corner[1] = rect1.y
vertical_boundary = rect2.y + rect2.height

if relative_velocity[0] == 0 and relative_velocity[1] == 0:
return None

if relative_velocity[0] == 0:
# Guaranteed vertical collision. X value stays the same due to the
# vertical velocity vector, so it doesn't need to be calculated.
return [0, vertical_boundary-base_corner[1]]
elif relative_velocity[1] == 0:
# Guaranteed horizontal collision
return [horizontal_boundary-base_corner[0], 0]

# Test for horizontal collision first. The following formula is used:
#
# By - y = Vy/Vx * (Bx - boundary)
#
# where B is the base corner, V is the velocity, and y is what
# we're solving for. The final formula looks like this:
#
# y = By - Vy/Vx * (Bx - boundary)
slope = relative_velocity[1]/float(relative_velocity[0])
y = base_corner[1] - slope * (base_corner[0] - horizontal_boundary)

# Check if the two rects would be touching at all
velocity = vector2d.sub([horizontal_boundary, y], base_corner)
temp = move(rect1, velocity)
if temp.y < rect2.y + rect2.height and temp.y + temp.height > rect2.y:
return velocity

# Test for vertical collision. This uses the same basic formula
# as the horizontal collision code:
#
# By - boundary = Vy/Vx * (Bx - x)
#
# x = Bx - Vx/Vy * (By - boundary)
x = base_corner[0] - 1/slope * (base_corner[1] - vertical_boundary)

# Again, check if they would be touching
velocity = vector2d.sub([x, vertical_boundary], base_corner)
temp = move(rect1, velocity)
if temp.x < rect2.x + rect2.width and temp.x + temp.width > rect2.x:
return velocity

# Rects can't collide
return None


def non_collision_factor(rect1, rect2, velocity1, velocity2):
"""Return the non-collision factor for rect1.

The non-collision factor is the exact point in time in which rect1
and rect2 are touching but not intersecting.

"""

vector = non_collision_vector(
rect1,
rect2,
velocity1,
velocity2
)

if vector == None:
return

# Find the non collision factor using the following formula:
# x1*x - x2*x = Vx
#
# x = Vx/(x1 - x2)
#
# Where x1 = velocity1[0], x2 = velocity2[0], and V = vector
if velocity1[0] - velocity2[0] != 0:
return vector[0]/float(velocity1[0] - velocity2[0])
elif velocity1[1] - velocity2[1] != 0:
# Use the same formula except with y components
return vector[1]/float(velocity1[1] - velocity2[1])



non_collision_factor is what you'd use to determine if a collision happens, and doesn't need to be changed at all to work with AABBs. If it returns a number in the range -1..0, it means the collision happened after you moved the two objects. If it's in the range 0..1, it means they'll collide the next time you move them. If it's anything outside of that range, or None, it means the collision didn't happen after you moved them last frame nor will it happen when you move them again.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well I'm just not sure how this test is useful, because what if you're objects are spinning? IMO, a sphere sweep would probably be better in all cases (unless your objects are poles that are guaranteed to not be spinning around!).

Share this post


Link to post
Share on other sites
That's right, AABBs can't spin, but the AABB can be adjusted to match the extrema of the object as it spins.

I've tested a simplistic implementation of both the sphere/sphere sweep and the AABB/AABB sweep, and to my surprise the AABB sweep is faster with randomized input (with idealized input the sphere/sphere sweep is faster).

Here are the results of sequences of 100000 randomized collision checks (not including the time to generate the input, which is significantly larger for the AABBs):


AABB 63 ms
AABB 31 ms
AABB 47 ms
AABB 47 ms
AABB 62 ms
AABB 32 ms
AABB 47 ms
AABB 47 ms
AABB 47 ms
AABB 31 ms
Sphere 78 ms
Sphere 94 ms
Sphere 94 ms
Sphere 93 ms
Sphere 78 ms
Sphere 110 ms
Sphere 94 ms
Sphere 78 ms
Sphere 93 ms
Sphere 94 ms




AABB 47 ms
AABB 47 ms
AABB 47 ms
AABB 46 ms
AABB 47 ms
AABB 31 ms
AABB 31 ms
AABB 47 ms
AABB 47 ms
AABB 47 ms
Sphere 94 ms
Sphere 94 ms
Sphere 109 ms
Sphere 94 ms
Sphere 109 ms
Sphere 78 ms
Sphere 110 ms
Sphere 94 ms
Sphere 78 ms
Sphere 93 ms



Since AABBs can represent less isotropic shapes properly, and seem to be faster for randomized input, it seems like I should use them for everything.

My implementations are simplistic though, so perhaps they are swaying my results improperly:

Sphere:

float cParticle::ts(cParticle &o,bool &real)
{
float rs = rad+o.rad;
// a = v0^2 + v1^2 - 2v0v1
float a = v.dot(v) + o.v.dot(o.v) - 2 * v.dot(o.v);
if(a==0.0f)
{
real=false;
return -1.0f;
}

// b = 2v0p0 - 2v1p0 - 2v0p1 + 2v1p1
float b = 2 * v.dot(p) - 2 * o.v.dot(p) - 2 * v.dot(o.p) + 2 * o.v.dot(o.p);
// c = p0^2 + p1^2 + (r0+r1)^2 - 2p0p1
float c = p.dot(p) + o.p.dot(o.p) - (rs*rs) - 2 * p.dot(o.p);
// Descriminant = b^2 - 4ac
float desc = (b*b) - (4*a*c);

if(desc<0.0f)
{
real=false;
return -1.0f;
}

float sqrtd = sqrt(desc);

float ans[2] = {
(-b + sqrtd)/(2*a),// (-b + sqrt(desc))/2a
(-b - sqrtd)/(2*a) // (-b - sqrt(desc))/2a
};

float ret;

if(ans[0]<ans[1])
ret = ans[0];
else
ret = ans[1];

real=true;
if(ret>=0.0f)
return ret;
// Only accept a negative result when they are currently colliding
if(p.dist(o.p)<rs)
return ret;
real=false;
return -1.0f;
}



AABB:

v2 cAABB::ts_range(range *r0,range *r1,int &real)
{
// Check intersection first
if(UM_WITHIN(r0->x0,r1->x0,r1->x1) || UM_WITHIN(r0->x1,r1->x0,r1->x1))
{
real = intersection;
return v2(0.0f,0.0f);
}

// If velocities are the same then they will never collide and there will be a divide by zero error
if(r0->v == r1->v)
{
real=unreal;
return v2(-1.0f,-1.0f);
}

// Find left/right
range *left,*right;
if(r0->x1 < r1->x0)
{
left=r0;
right=r1;
}
else
{
left=r1;
right=r0;
}

// Find t0 and t1
float t0 = (left->x1-right->x0)/(right->v-left->v);
if(t0<0.0f)
{
real=unreal;
return v2(-1.0f,-1.0f);
}

real=collision;
return v2(t0, // t0
(left->x0-right->x1)/(right->v-left->v) // t1
);
}

v2 cAABB::ts_union(v2 a,v2 b,bool &intersection)
{
v2 ret=v2(UM_MAX(a.x,b.x), // The maximum of the minimums
UM_MIN(a.y,b.y)); // The minimum of the maximums

// No overlap
if(ret.x>ret.y)
{
intersection=false;
return v2(0.0f,0.0f);
}

intersection=true;
return ret;
}

v2 cAABB::ts(cAABB &o,int &real)
{
/*
We must treat each axis separately, getting t0 (when the ranges begin to overlap) and t1 (when the ranges cease to overlap)
for each, checking that t0 >= 0. The overlap between all of these time ranges is then found, and its minimum returned.
*/

bool ranged=false;
v2 trange;

for(int i=0;i<3;i++)
{
int reality;
v2 thisrange = ts_range(axes+i,o.axes+i,reality);
if(reality==unreal)
{
real=unreal;
return v2(-1.0f,-1.0f);
}
else if(reality==collision)
{
if(!ranged)
{
trange=thisrange;
ranged=true;
}
else
{
bool intersection;
trange=ts_union(trange,thisrange,intersection);
if(!intersection)
{
real=unreal;
return v2(-1.0f,-1.0f);
}
}
}
}

if(!ranged)
{
real=intersection;
return v2(-1.0f,-1.0f);
}

real=collision;
return trange;
}



Thanks, ~SPH

Share this post


Link to post
Share on other sites
For large numbers of moving AABB's you might want to look into a method called 'Sweep and Prune'. I cant find a link to a good tutorial right now but its a well documented method so a bit of googling should see you right. It requires that you can store data between tests but the pay off is that is makes good use of temporal coherence meaning that for small time steps (compared to the velocity of the boxes) only very minimal processing needs to be done each pass making it very efficient.

Share this post


Link to post
Share on other sites
Quote:
Original post by Motorherp
For large numbers of moving AABB's you might want to look into a method called 'Sweep and Prune'. I cant find a link to a good tutorial right now but its a well documented method so a bit of googling should see you right. It requires that you can store data between tests but the pay off is that is makes good use of temporal coherence meaning that for small time steps (compared to the velocity of the boxes) only very minimal processing needs to be done each pass making it very efficient.

Sweep and prune is generally something that can (and should) be done outside the actual collision detection algorithm.

edit:
Or, at least, that's how I do it, since my "collision detection" routine doesn't simply return true or false. I suppose it could make sense to stick that in there if it fits in with the purpose of the routine.

Also, if you plan on using a sweep and prune approach, make sure you extrude the AABBs by their velocities, otherwise it's likely you'll miss some collisions.

Share this post


Link to post
Share on other sites
Quote:
Original post by ShmeeBegek

I have been looking around for an efficient AABB vs. AABB sweep test, and the best that I've been able to find is just what I came up with myself: finding the overlap times for each dimension separately and then finding the overlap between those for the final time range. This seems to be something of a complex process, and I am wondering whether or not anyone has a more efficient solution.

Thanks, Sean Purser-Haskell


it's not that complicated. Since the code for each dimension is the same, you just run one single sub-routine for each dimensions. Basically, you find the time interval for each dimensions, as you mentioned, and reduce the interval and compare it to the original swept time interval (so, either between [0, 1] or [0, FrameTime]).

the advantage of doing it that way, is that it's then straight forward to extend the test to do OBBoxes, polygons, simple convex shapes (pyramids for examples).

If you want code and explainations, you can look at that thread.

As I also explained in there, the code is identical in its structure to a segment/ray-box collision. You can do that in an efficient way, then you can do AABB collision exactly the same way.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement