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.

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.