# AABB Intersections with Space Partitions, A Sample Code Performance and Reliability

I have originally written the following Matlab code to find intersection between a set of Axes Aligned Bounding Boxes (AABB) and space partitions (here 8 partitions). I believe it is readable by itself, moreover, I have added some comments for even more clarity.

function [A,B] = AABBPart(bbx,it)                                     % bbx: aabb, it: iteration
global F
IT = it+1;
n = size(bbx,1);
F = cell(n,it);
A = Part([min(bbx(:,1:3)),max(bbx(:,4:6))],it,0);                     % recursive partitioning
B = F;                                                                % matlab does not allow
function s = Part(bx,it,J)                                        %   output to be global
s = {};
if it < 1; return; end
s = cell(8,1);
p = bx(1:3);
q = bx(4:6);
h = 0.5*(p+q);
prt = [p,h;...                                                % 8 sub-parts (octa)
h(1),p(2:3),q(1),h(2:3);...
p(1),h(2),p(3),h(1),q(2),h(3);...
h(1:2),p(3),q(1:2),h(3);...
p(1:2),h(1),h(1:2),q(3);...
h(1),p(2),h(3),q(1),h(2),q(3);...
p(1),h(2:3),h(1),q(2:3);...
h,q];
for j=1:8                                                     % check for each sub-part
k = 0;
t = zeros(0,1);
for i=1:n
if all(bbx(i,1:3) <= prt(j,4:6)) && ...               % interscetion test for
all(prt(j,1:3) <= bbx(i,4:6))                 %   every aabb and sub-parts
k = k+1;
t(k) = i;
end
end
if ~isempty(t)
s{j,1} = [t; Part(prt(j,:),it-1,j)];                  % recursive call
for i=1:numel(t)                                      % collecting the results
if isempty(F{t(i),IT-it})
F{t(i),IT-it} = [-J,j];
else
F{t(i),IT-it} = [F{t(i),IT-it}; [-J,j]];
end
end
end
end
end
end


Concerns:

• In my tests, it seems that probably few intersections are missing, say, 10 or so for 1000 or more setup. So I would be glad if you could help to find out any problematic parts in the code.

• I am also concerned about using global F. I prefer to get rid of it.

• Any other better solution in terms of speed, will be loved.

Note that the code is complete. And you can easily try it by some following setup.

n = 10000;                        % in the original application, n would be millions
bbx = rand(n,6);
it = 3;
[A,B] = AABBPart(bbx,it);

• pics? its very hard to understand what its trying to do. – BKSpurgeon Mar 30 '17 at 10:11
• @BKSpurgeon you may check AABB Intersection Tests to get an idea of AABB intersection tests. The rest of code in the question is to implement space partitioning (as regular grid recursively divided into smaller ones and find their intersection with given AABBs. – Developer Mar 31 '17 at 6:15
• that's extremely helpful. i'll have a look when i get the chance. – BKSpurgeon Mar 31 '17 at 8:45
• Sorry if my comments seem superficial, but I think that your choice of words does not help to understand what you're doing : parameter "it" actually refers to depth in the recursive partitioning, but you call that iteration. Your algorithm apparently computes the intersection in one pass. Also the word partitioning is not appropriate : your algorithm is actually a special case of a general intersection test, where P = the first input and Q = a set of bounding boxes defining a recursive partition of 3D space in 8 equal parts with limited depth. – titus Apr 25 '17 at 10:35
• Computing intersections with Q does not define a partition : for instance, if the depth is 1, then any centered box will intersect with all 8 members of Q, as long as its surface is not zero. – titus Apr 25 '17 at 10:39