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

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

<p>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.</p>

<p>Essentially my question is - what am I doing wrong in my algorithm &amp; how do I translate my bounding volume onto the shape.</p>

<p>The two sources I have been using are <a href="https://github.com/tl3shi/books/blob/master/GameDev/Math/Mathematics.for.3D.Game.Programming.and.Computer.Graphics,.Lengyel,.3rd,.2011.pdf" rel="nofollow">Maths for 3D Games</a>, as well as a <a href="http://jamesgregson.blogspot.co.uk/2011/03/latex-test.html" rel="nofollow">blog</a> which gives some indication on to do the translation - but doesn't seem to have worked very well.</p>

<p>I have put my source code below - thanks very much!</p>

<pre><code>%//===================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 &amp; eigen vectors

R = y(:,1); %//Eigen vectors &amp; 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 &amp; 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);
</code></pre>

CC BY-SA 3.0
2016-04-28T08:14:31.777Z
_"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.
Simon F
CC BY-SA 3.0
2016-04-28T08:54:03.000Z
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
joojaa
CC BY-SA 3.0
2016-04-28T12:24:01.427Z
@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...
davidhood2
CC BY-SA 3.0
2016-04-28T13:09:56.963Z
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 :-|
Simon F
<raytracing><transformations><bounding-volume-hierarchy><matlab>
Creating an Object Orientated Bounding Volume
davidhood2
# Creating an Object Orientated Bounding Volume

(Asked by: username_0 on 2016-04-24)

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](https://github.com/tl3shi/books/blob/master/GameDev/Math/Mathematics.for.3D.Game.Programming.and.Computer.Graphics,.Lengyel,.3rd,.2011.pdf), as well as a [blog](http://jamesgregson.blogspot.co.uk/2011/03/latex-test.html) 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);

```

**Tags:** raytracing, transformations, bounding-volume-hierarchy, matlab

> **Comments:**
> **username_1**: _"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.  
> **username_2**: 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  
> **username_0**: @username_1 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...  
> **username_1**: 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 :-|  

---

## 0 answers

