# Sweep and Prune (Sort and Sweep)

## Recommended Posts

Hi, I'm having a problem grasping how the sweep and prune/sort and sweep collision detection works. I understand that you store an array of end points for each axis, you sort each one, then check for collision and if a collision is found you report it. What I'm having a hard time understanding is how/what to implement the SAP after each axis array of end points are sorted. Do you loop through the array of AABBs, check on one axis which end points are within the interval of the the AABB's end points, and if an intersection is found on that axis, go on to the next axis? Could someone please explain this to me? Thanks!

##### Share on other sites
oliii    2196
afaik,

// 1D sweep and prunefor (int i = 0; i < numSpansX; i ++){    for(int j = i+1; j < numSpansX; j ++)    {                                     /* always false */        if(span[i].xmax < span[j].xmin /*|| span[j].xmax < span[i].xmin*/)            break;        // check other axes of bounding box            if(span[i].ymax < span[j].ymin || span[j].ymax < span[i].ymin)            continue;         // test collision        // ....   } }

it's kinda like the normal brute force test, but the fact that the objects are sorted allow for shortcuts.

Note that this is only a 1D sweep and prune. To allow for 2D, you have to store intersection results onto two separate lists, and intersect the lists (intervals have to overlap on both axes).

// scan each axis. // Find intervals that overlap and store them into lists of potential collisions.for(int a = 0; a < numAxes; a++){    list[a].clear();    for (int i = 0; i < numSpans[a]; i ++)    {        for(int j = i+1; j < numSpans[a]; j ++)        {            if(span[i].max[a] < span[j].min[a])                break;            // entry into the list            // make sure the key to identify a pair of objects is unique            int high = max(span[i].key, span[j].key);                int low  = min(span[i].key, span[j].key);            int key  = ((high << 16) | low);            list[a].insertSort(key); // insert sort, qsort, ... pick your poison        }    }}// 'intersect' lists for each axis against each other.// basically, if a key isn't present in a list, then it means that the two // object do not overlap on some axis, and need to be prunedfor(int a = 1; a < numAxes; a++)    list[0].intersect(list[a]);// finally, test intersectionsfor(int a = 0; a < list[0].size(); a++){    // retrieve the keys of the two objects    int keya = (list[0].key[a] >> 16)    int keyb = (list[0].key[a] & 0xFFFF);    //test!    GetCollObject(keya).TestIntersection(GetCollObject(keyb));}

there are probably better algo for sorting and slotting items into a list, but I think you'll get the general idea.

EDIT : *Correction*

[Edited by - oliii on November 25, 2007 6:22:41 AM]

##### Share on other sites
Thanks, just to get a few things straight, there should be three arrays like "span". Each one hold the end points for one of the axis, right?

I'm going to write up a little code, and see then check back to make sure I'm on the right track.

Thanks!

##### Share on other sites
Sorry for the double post.

In your 1D example, is span sorted somehow? I'm really confused about why sorting the lists makes a difference in your example. Why would you sort the list of pairs, what's the point?

##### Share on other sites
Vorpy    869
I think that 1d version is a bit incorrect. The idea is that by sorting the objects along one axis, you only need to check for collisions between objects that overlap on that axis.

Maybe it should look like this:
// 1D sweep and prunefor (int i = 0; i < numSpansX; i ++){    for(int j = i+1; j < numSpansX; j ++)    {                                     /* always false */        if(span[i].xmax < span[j].xmin /*|| span[j].xmax < span[i].xmin*/)            break;        // check other axes of bounding box            if(span[i].ymax < span[j].ymin || span[j].ymax < span[i].ymin)            continue;        // the objects overlap on the x and y axis, handle the collision here    }}

That break in the inner loop is the reason to sort the objects on the x axis. Instead of explicitly checking every pair for overlap, it uses the sorted order to quickly locate only pairs that overlap on that axis.

For the multidimensional version it is also possible to store overlap information in a table of some sort and update the list of colliding pairs as overlaps are added. As you find the overlaps on the last axis, if any of those pairs overlapped on the other two axes already then they are colliding and are added to the list.

These multidimensional versions are easier to implement than the version that maintains the sorted lists between frames. That version is the most complex; it keeps a list of the end points for each bounding box on each axis and remembers overlap and collision information between frames. A bubblesort or something similiar can be used to update the list of endpoints, the overlap information, and the list of colliding pairs simultaneously.

##### Share on other sites
Quote:
 The idea is that by sorting the objects along one axis, you only need to check for collisions between objects that overlap on that axis.

Wouldn't you only need to sort one axis, check for collision on that axis and if an intersection is found proceed to performing a normal AABB-AABB collision test? The idea is, since an intersection in all three dimensions requires overlapping on all three axis, you can omit checking the last two sorted axis. So, you check the axis where there is more likely to be the least overlaps, right?

So, following what has been posted, is this correct?

//SAP.h//...class SapBroadPhase : public BroadPhaseStrategy{		class Box;	struct EndPoint	{			Box* owner;		float value;		bool isMin;		unsigned int index;			};		struct Box	{		EndPoint* min[3];		EndPoint* max[3];		RigidBody* owner;				void SetMin( const Vector3& vec )		{			min[0].value = vec.x;			min[1].value = vec.y;			min[2].value = vec.z;		}				void SetMax( const Vector3& vec )		{			max[0].value = vec.x;			max[1].value = vec.y;			max[2].value = vec.z;		}				void SetCenterExtents( const Vector3& center, center Vector3& extents )		{			SetMin(center - extents);			SetMax(center + extents);		}				bool Intersects( const Box& other )		{			if( max[0].value < other.min[0].value ||			 	other.max[0].value < min[0].value ||				max[1].value < other.min[1].value ||				other.max[1].value < min[1].value ||				max[2].value < other.min[2].value ||				other.max[2].value < min[2].value ) 			{				return false;			}						return true;		}				void Set( const Vector3& points, unsigned int numPoints )		{			if( !points ) return;			SetMin(points[0]);			SetMax(points[0]);			for( int i = 1; i < numPoints; ++i )			{				if (points[i].x < min[0].value)	            	min[0].value = points[i].x;	        	else if (points[i].x > max[0].value )	            	max[0].value = points[i].x;	        	if (points[i].y < min[1].value)	            	min[1].value = points[i].y;	        	else if (points[i].y > max[1].value )	            	max[1].value = points[i].y;	        	if (points[i].z < min[2].value)	            	min[2].value = points[i].z;	        	else if (points[i].z > max[2].value )	            	max[2].value = points[i].z;			}		}	};			void AddObject( const RigidBody& body );	void RemoveObject( const RemoveObject& body );	void SortEndPoints();	void CheckForCollisions();	void Update();	private:	void ComputeAABB( const RigidBody& body, Box& box );		std::list<Box> boxes;		 //Box* boxes;	unsigned int numBoxes;	std::vector<EndPoint> xAxis; //EndPoint* xAxis;	std::vector<EndPoint> yAxis; //EndPoint* yAxis;	std::vector<EndPoint> zAxis; //EndPoint* zAxis;}//...

//SAP.h//...void SapBroadPhase::SortEndPoints(){	std::stable_sort( xAxis.begin(), xAxis.end(), CompareEndPoints );		/*for( int i = 0; i < xAxis.size(); i++ )	{		xAxis[i].index = i;	}*/}// Finds overlapping aabb's, and creates a pair.void SapBroadPhase::CheckForCollisions(){	// We only need to check one sorted axis				for( int i = 0; i < boxes.size(); i++ )	{		for( int j = i+1; i <boxes.size(); j++ )		{			if( xAxis[i].owner->owner->Id() != xAxis[j].owner->owner->Id() ) // make sure they aren't the min and max of the same AABB			{				if( !xAxis[i].isMin && xAxis[j].isMin )				{					if( xAxis[i].value < xAxis[j].value )						break;											if( xAxis[i].owner->Intersects(xAxis[j].owner) )						pairManager.AddPair(i,j);				}			}		}	}}void SapBroadPhase::Update(){	// Update each Box/AABB	for( int i = 0; i < boxes.size(); i++ )	{		ComputeAABB( boxes[i].owner, boxes[i] );	}		SortEndPoints();	CheckForCollisions();}//...

##### Share on other sites
Vorpy    869
You're confusing the two different methods.

Method 1: Sort boxes by their min value over one axis, then iterate through this list looking at boxes that overlap on the chosen axis.

Method 2: Maintain lists of box endpoints on each axis and keep track of which boxes overlap on all three axes.

I can't think of any reason to keep a list of sorted endpoints if you're just doing method 1, which is definitely the easier method to implement. You can just sort the boxes by their minimum value along some axis instead.

##### Share on other sites
oliii    2196
Quote:
Original post by bronxbomber92
Quote:
 The idea is that by sorting the objects along one axis, you only need to check for collisions between objects that overlap on that axis.

Wouldn't you only need to sort one axis, check for collision on that axis and if an intersection is found proceed to performing a normal AABB-AABB collision test? The idea is, since an intersection in all three dimensions requires overlapping on all three axis, you can omit checking the last two sorted axis. So, you check the axis where there is more likely to be the least overlaps, right?

Correct, that would be the 1D sweep and prune. However, you can also do a 2D method if you find that you get loads of false positive (the two intervals overlap *but* the AABBs actually don't on other dimensions).

Generally, for a 3D game, a 2D sweep and prune should be sufficient (on the two horizontal axes). In a 2D game, it's debatable. Besides, there are probably better algorithms for that. Hash map, 2D grid, or this one

##### Share on other sites
Quote:
 Original post by VorpyYou're confusing the two different methods.Method 1: Sort boxes by their min value over one axis, then iterate through this list looking at boxes that overlap on the chosen axis.Method 2: Maintain lists of box endpoints on each axis and keep track of which boxes overlap on all three axes.I can't think of any reason to keep a list of sorted endpoints if you're just doing method 1, which is definitely the easier method to implement. You can just sort the boxes by their minimum value along some axis instead.

Ahhh, I guess what I'm asking then is: How do I test for intersection on all three axis using method 2?

##### Share on other sites
Vorpy    869
That's a little tricky.

You need to be able to store and retrieve information about a pair of objects. If the number of objects is below some value N and every object has an id number that is less than N, you cn use an NxN table. Really you only need the upper triangle part of the table, since the order of the objects doesn't matter, ie an overlap between objects 1 and 2 is the same as an overlap between 2 and 1.

Another way is to use a hash table and use the pair as the key in the table.

Once you can store information about pairs all you need to do is set this information as you sweep each access. When you find overlaps while sweeping the last axis you can check if the overlapping pair had overlapped on the other 2 axes by looking up the pair in the table.

You can also use olii's method of maintaining a sorted list for each axis and then intersection the lists to find the collisions.

Note that none of this requires having a list of the endpoints, just the objects themselves sorted by their min coordinate. The method that uses the endpoints is even trickier. In that method, you handle the sorting yourself so that as you are sorting you can update the overlap status, and you maintain the overlap status between frames. This takes advantage of spatial locality (ie usually the overlaps won't change by much each frame). Implementing this really efficiently is a bit trickier than just using a 1d sweep and prune.