Sign in to follow this  
taz0010

Generating a set of intersecting AABBs

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

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