# AABB overlap

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

## Recommended Posts

Hi, I have a set of objects represented as AABBs. I want to find the subset that overlaps another AABB. I already have their x and y bounds sorted in two lists. Is there a way to find which ones overlap the other AABB without traversing the whole list? There should be some nice sortcut given that the list is sorted, but the best I can think of fails when a box totally contains the test box. Thanks.

##### Share on other sites
I guess it depends on precisely how your list is sorted and what shape your AABB's can have. As you say you've sorted them by coordinate components, you can do incremental sweeps through all of the AABB's and test only then ones that start after the near side of X and before the far side of X against X along any of the axes. Not too efficient in 3D, but still much more efficient than matching all possible pairs.

Generally it won't matter too much how you organize your AABB's in memory unless there's some spatial coherence involved: that is, you're using some kind of a tree structure (eg BSP, quadree, octree etc) to sort them by proximity.

##### Share on other sites
Not sure what you mean by "precision of sort". It's just a plain old array sort (qsort). As far as algorithm, this is just to test one box that isn't in the set against all, not all against all. As for shape of the AABBs, they are AABBs, so axis aligned rectangular.

Your algorithm sounds like what i was thinking of until i realized that it doesn't cover the case where one of the boxes completely contains the test box.

Thanks anyways.

##### Share on other sites

//first order all aabb's based on their minumum bound along x-axis into x[];//store y, z, sizex, sizey and sizez in respective arrays as well as x is sorted//for all aabb's save for the last one (let's call this src)for(int src = 0; src < iNumAABBs - 1; src++)  {  //check all aabb's starting with the next one up to the  //last one  (let's call this dst)  for(int dst = src + 1; dst < iNumAABBs; dst++)    {    //skip to next if there can't be any overlap: dst min bound is    //greater than src max bound    if(x[dst] > x[src] + sizex[src])      break;    //at this point you're guaranteed that aabb[src] and    //aabb[dst] overlap along the x-axis, now you do checks    //on other axes:    //if...    if(       //minimum bound of dst is greater than maximum bound of src       (y[dst] > y[src] + sizey[src] || //or       //maximum bound of dst is smaller than minimum bound of src       (y[dst] + sizey[dst] < y[src]))       //then there can't be an overlap       break;        //otherwise x and y axes overlap - check z axis the same way    if((z[dst] > z[src] + sizez[src] ||       (z[dst] + sizez[dst] < z[src]))       break;    //if we didn't hit any breaks, then there's a definite overlap between    //src and dst. success.    bOverlap = true;    }  }

Should work with all types of overlap, even if src includes dst and vice versa.

Of course I pulled this out of my thumb, so I haven't compiled it or anything.

[Edited by - irreversible on December 6, 2009 11:06:24 PM]

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633288
• Total Posts
3011222
• ### Who's Online (See full list)

There are no registered users currently online

×