Sign in to follow this  

Generating a set of intersecting AABBs

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

This topic is 2636 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this