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);
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.
– Simon F Apr 28 '16 at 08:14