Jump to content
  • Advertisement
Sign in to follow this  
taz0010

Generating a set of intersecting AABBs

This topic is 2851 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'm working on a problem where I have axis asigned bounding boxes from two sets - A and B. For each element in A, I want to generate a list of elements in B that it's in intersection with. Members of a set are not tested for intersection with themselves, so any single intersection involves an element from A and an element from B.

Is there a way to speed this test up using SIMD? Or a least a faster method than the naive approach, which is:

for(int i=0; i<numA; i++){
for(int j=0; j<numB; j++){
if(intersects(setA(i), setB(j))
// Output pair
}
}


I'm not looking for any spatial partitioning methods, as I'm already using them to cull the initial set. Sets A and B are what's left over. I just need a faster O(n^2) algorithm.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by taz0010
I'm not looking for any spatial partitioning methods, as I'm already using them to cull the initial set. Sets A and B are what's left over.


What do you mean by "left over"?

Also, there's a data structure called interval tree that may help with this.

Share this post


Link to post
Share on other sites
Quote:
What do you mean by "left over"?


I use an octree to split up my scene. Sets A and B refer to the objects in a single octree node. Since these objects already have spatial locality, the degree of overlap will be fairly high. But I think testing AABBs is still worthwhile.

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!