Jump to content
  • Advertisement
Sign in to follow this  
apefish

AABB overlap

This topic is 3179 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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
What about something like this:


//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]

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!