# AABB vs. AABB sweep test (collision)

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

## 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 on other sites
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 on other sites
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 on other sites
AABBs cant spin, or they wouldn't be AABBs

##### 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 msAABB 31 msAABB 47 msAABB 47 msAABB 62 msAABB 32 msAABB 47 msAABB 47 msAABB 47 msAABB 31 msSphere 78 msSphere 94 msSphere 94 msSphere 93 msSphere 78 msSphere 110 msSphere 94 msSphere 78 msSphere 93 msSphere 94 ms

AABB 47 msAABB 47 msAABB 47 msAABB 46 msAABB 47 msAABB 31 msAABB 31 msAABB 47 msAABB 47 msAABB 47 msSphere 94 msSphere 94 msSphere 109 msSphere 94 msSphere 109 msSphere 78 msSphere 110 msSphere 94 msSphere 78 msSphere 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 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 on other sites
Quote:
 Original post by MotorherpFor 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 on other sites
Quote:
 Original post by ShmeeBegekI 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 16
• 14
• 10
• 9
• 11
• ### Forum Statistics

• Total Topics
634094
• Total Posts
3015497
×