# 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.

## 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 on other sites
Quote:
 Original post by taz0010I'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 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.

1. 1
2. 2
Rutin
22
3. 3
JoeJ
18
4. 4
5. 5

• 15
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631724
• Total Posts
3001904
×