3
$\begingroup$

I'm attempting to test out the maths behind bounding volume algorithms (prior to ray tracing) using MATLAB.

So far, I have successfully created the relatively trivial axis aligned bounding volume, and I believe I have successfully created a bounding sphere.

I've attempted to then create an object aligned bounding volume - but although I believe I have got the principle axes correct because the box appears to be a suitable shape - I have been unable to translate it correctly "onto" the shape.

Essentially my question is - what am I doing wrong in my algorithm & how do I translate my bounding volume onto the shape.

The two sources I have been using are Maths for 3D Games, as well as a blog which gives some indication on to do the translation - but doesn't seem to have worked very well.

I have put my source code below - thanks very much!

%//===================Declare vertices and faces===================
vp_vtx = [379.379,684.302,319.752,711.497,215.956,439.237,600,600,732.938,418.084,600,600,747.081;
    225.836,158.305,394.208,337.480,84.834,245.958,212.858,342.251,322.344,330.576,300,416.190,398.885;
    0.933,0.917,0.904,0.878,0.854,0.923,0.914,0.949,0.943,0.908,0.896,0.940,0.933;
    1,1,1,1,1,1,1,1,1,1,1,1,1];
ws_fcs = [2,4,3,6,6,7,7,10,10; %//Faces forming shape
    4,3,1,7,11,9,13,11,13;
    5,5,5,11,10,13,11,13,12];
%//===================Create an AA bounding box===================
x = vp_vtx(1,:);y = vp_vtx(2,:);z = vp_vtx(3,:); %//Seperate vertex coordinates
bb_vtx = [min(x),max(x),min(x),max(x),min(x),max(x),min(x),max(x); %//Take min/max from each
    min(y),min(y),max(y),max(y),min(y),min(y),max(y),max(y); %//To form enclosing box
    min(z),min(z),min(z),min(z),max(z),max(z),max(z),max(z)];

bb_fcs = [1,2,6,1,1,3; 2,4,5,5,2,4;4,8,7,7,6,8; 3,6,8,3,5,7]; %//Allocate faces of box

figure(); grid on; hold on; xlabel('x'); ylabel('y'); zlabel('z');
scatter3(vp_vtx(1,:),vp_vtx(2,:),vp_vtx(3,:),'r'); %//Plot shape
patch('Faces',ws_fcs','Vertices',vp_vtx(1:3,:)', 'Facecolor', 'r','FaceAlpha', 0.1)
patch('Faces',bb_fcs', 'Vertices',bb_vtx','FaceColor','g','FaceAlpha', 0.05);%//Plot enclosing box

mean_point = sum(vp_vtx,2)/length(vp_vtx);
C = zeros(4,4); %//Create 4x4 empty matrix
for i = 1:length(vp_vtx)
    C = C+(vp_vtx(:,i)-mean_point)*(vp_vtx(:,i)-mean_point)'; %//Sum to get covarience matrix
end;
C = C/length(vp_vtx); %//Scale by the number of samples

[y,v] = eig(C(1:3,1:3)) ;%//Get eigenvalues & eigen vectors

R = y(:,1); %//Eigen vectors & values form object aligned axes
S = y(:,2);
T = y(:,3);%//T is principle axis as derived from largest eigenvalue

%//========Create an Object Orientated Bounding Box=========
dot_arr = zeros(size(vp_vtx));
for i = 1:length(vp_vtx)  %//Create array of dot products with each OO axis
    dot_arr(1,i) = dot(vp_vtx(1:3,i),T);
    dot_arr(2,i) = dot(vp_vtx(1:3,i),R);
    dot_arr(3,i) = dot(vp_vtx(1:3,i),S);
end
%//Get min/max variation in each OO axis
a = 0.5*(min(dot_arr(1,:)) + max(dot_arr(1,:)));
b = 0.5*(min(dot_arr(2,:)) + max(dot_arr(2,:)));
c = 0.5*(min(dot_arr(3,:)) + max(dot_arr(3,:)));
%//Centre is point where the 3 planes of the box intersect? (from book)
q = a*T + b*R + c*S;

Tr = vertcat(horzcat(T,S,R,q),[0,0,0,1]); %//Transform & translate original AA box
bb_vtx = Tr*vertcat(bb_vtx, ones(1,length(bb_vtx)));
patch('Faces',bb_fcs', 'Vertices',bb_vtx(1:3,:)','FaceColor','g','FaceAlpha', 0.05);
$\endgroup$
  • 2
    $\begingroup$ "Matlab is not the choice of language for this particular task"... nor mine. I'm not familiar with the language nor have access to Matlab. Having said that, I see you have the eigenvectors of the covariance matrix and are taking the dot product of each vertex against each of those vectors. The mins and maxs give the bounds of a box. However, I don't think this is guaranteed to give you a good bound. Imagine a dense central cluster of vertices with a few outliers. The directions of your axes are going to governed by the dense cluster but your box really only depends on the outliers. $\endgroup$ – Simon F Apr 28 '16 at 8:14
  • 1
    $\begingroup$ There seems to be a problem with matlab on this site, every time somebody puts up a question with matlab code it seems to rot forever. I have matlab installed but honestly would not care to fire it up for debugging $\endgroup$ – joojaa Apr 28 '16 at 8:54
  • $\begingroup$ @SimonF Surely though, as a bounding box, it still has to include those outliers - unless of course you have multiple bounding boxes. However, I'm only attempting to model the mathematics and the shape in question is just one I quickly drew up while I had the time... $\endgroup$ – davidhood2 Apr 28 '16 at 12:24
  • $\begingroup$ Well, yes, it will still include the outliers, but one aim of OBBs over AABBs is to get a much smaller bounding volume. I just meant to point out that using PCA might not give a good result. I must admit, though, I don't really have an efficient scheme for doing better :-| $\endgroup$ – Simon F Apr 28 '16 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.