title: 3D Object Oriented Bounding Box using PCA
body: <p>I am trying to compute the object oriented bounding box for a set of points. I'm using c++ and the Eigen linear algebra library.</p>
  
  <p>I have been using two blog posts as guides yet still my bounding boxes are incorrect (see images).</p>
  
  <p><a href="https://hewjunwei.wordpress.com/2013/01/26/obb-generation-via-principal-component-analysis/" rel="nofollow noreferrer">blog post 1</a>
  <a href="http://jamesgregson.blogspot.co.uk/2011/03/latex-test.html" rel="nofollow noreferrer">blog post 2</a></p>
  
  <p>I hope my commented code is clear of my attempt but the gist of the algorithm is to use PCA to find the basis vectors for the object oriented coordinate frame.</p>
  
  <p>To then project all points into the new frame, find the min and max points that define the box, then project these point into the original coordinate frame and render them.</p>
  
  <p>I can successfully render a box but is isn't a bounding box and appears to be aligned to the normal x,y,z axis. This is clear in the first image for each of the two objects shown.</p>
  
  <p>Any help would be really appreciated. Thanks in advance.</p>
  
  <pre><code>// iglVertices is a X by 3 Eigen::::MatrixXf
  // Covariance matrix and eigen decomposition
  Eigen::MatrixXf centered = iglVertices.rowwise() - iglVertices.colwise().mean();
  Eigen::MatrixXf cov = centered.adjoint() * centered;
  Eigen::SelfAdjointEigenSolver&lt;Eigen::MatrixXf&gt; eig(cov);
  
  //Setup homogenous tranformation to act as new basis functions for new coordinate frame
  auto basis = Eigen::Matrix4f(eig.eigenvectors().colwise().homogeneous().rowwise().homogeneous());
  basis.row(3) = Eigen::Vector4f::Zero();
  basis.col(3) = Eigen::Vector4f::Zero();
  basis(3,3) = 1.0f;
  
  std::cout &lt;&lt; "eig.eigenvectors() " &lt;&lt; eig.eigenvectors() &lt;&lt; std::endl;
  std::cout &lt;&lt; "Basis " &lt;&lt; basis &lt;&lt; std::endl;
  
  //invert matrix and and transform points into new coordinate frame
  auto invBasis = basis.inverse();
  auto newVertices = invBasis * iglVertices.rowwise().homogeneous().transpose();
  
  //Find max and min for all of the new axis
  auto maxP = newVertices.rowwise().maxCoeff();
  auto minP = newVertices.rowwise().minCoeff();
  
  std::cout &lt;&lt; "max " &lt;&lt; maxP &lt;&lt; std::endl;
  std::cout &lt;&lt; "min " &lt;&lt; minP &lt;&lt; std::endl;
  
  //Find center and half extent in new coordinate frame
  auto center = Eigen::Vector4f((maxP + minP) / 2.0);
  auto half_extent = Eigen::Vector4f((maxP - minP) / 2.0);
  
  auto t = Eigen::Vector4f((basis * center));
  std::cout &lt;&lt; "t " &lt;&lt; t &lt;&lt; std::endl;
  //Update basis function with the translation between two coordinate origins
  //I don't actually understand why I need this and have tried without it but still my bounding
  //box is wrong
  basis.col(3) = Eigen::Vector4f(t[0], t[1], t[2], t[3]);
  
  
  std::cout &lt;&lt; "Basis complete " &lt;&lt; basis &lt;&lt; std::endl;
  
  std::cout &lt;&lt; "center " &lt;&lt; center &lt;&lt; std::endl;
  std::cout &lt;&lt; "half_extent " &lt;&lt; half_extent &lt;&lt; std::endl;
  
  //This is the same as the previous minP/maxP but thought i should try this as
  // box is paramaterised with center and half-extent
  auto max = center + half_extent;
  auto min = center - half_extent;
  
  //Transform back into the original coordinates
  auto minNormalBasis = (basis * min).hnormalized();
  auto maxNormalBasis = (basis * max).hnormalized();
  
  std::cout &lt;&lt; "min new coord" &lt;&lt; min &lt;&lt; std::endl;
  std::cout &lt;&lt; "max new coord"&lt;&lt; max &lt;&lt; std::endl;
  std::cout &lt;&lt; "min old coord" &lt;&lt; minNormalBasis &lt;&lt; std::endl;
  std::cout &lt;&lt; "max old coord"&lt;&lt; maxNormalBasis &lt;&lt; std::endl;
  
  //Extract min and max
  auto min_x = minNormalBasis[0];
  auto min_y = minNormalBasis[1];
  auto min_z = minNormalBasis[2];
  
  auto max_x = maxNormalBasis[0];
  auto max_y = maxNormalBasis[1];
  auto max_z = maxNormalBasis[2];
  
  bBox.clear();
  //Build box for rendering
  //Ordering specific to the faces I have manually generated
  bBox.push_back(trimesh::point(min_x, min_y, min_z));
  bBox.push_back(trimesh::point(min_x, max_y, min_z));
  
  bBox.push_back(trimesh::point(min_x, min_y, max_z));
  bBox.push_back(trimesh::point(min_x, max_y, max_z));
  
  bBox.push_back(trimesh::point(max_x, min_y, max_z));
  bBox.push_back(trimesh::point(max_x, max_y, max_z));
  
  bBox.push_back(trimesh::point(max_x, min_y, min_z));
  bBox.push_back(trimesh::point(max_x, max_y, min_z));
  </code></pre>
  
  <p>The print output for the spray bottle example is</p>
  
  <pre><code>eig.eigenvectors()           0   -0.999992 -0.00411613
    -0.707107 -0.00291054    0.707101
     0.707107 -0.00291054    0.707101
  Basis           0   -0.999992 -0.00411613           0
    -0.707107 -0.00291054    0.707101           0
     0.707107 -0.00291054    0.707101           0
            0           0           0           1
  max 2.98023e-08
     0.216833
     0.582629
            1
  min -2.98023e-08
        -0.215
     -0.832446
             1
  t -0.000402254
    -0.0883253
    -0.0883253
             1
  Basis complete            0    -0.999992  -0.00411613 -0.000402254
     -0.707107  -0.00291054     0.707101   -0.0883253
      0.707107  -0.00291054     0.707101   -0.0883253
             0            0            0            1
  center           0
  0.000916399
    -0.124908
            1
  half_extent 2.98023e-08
     0.215916
     0.707537
            0
  min new coord-2.98023e-08
        -0.215
     -0.832446
             1
  max new coord2.98023e-08
     0.216833
     0.582629
            1
  min old coord 0.218022
  -0.676322
  -0.676322
  max old coord-0.219631
   0.323021
   0.323021
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/pZ0IX.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pZ0IX.png" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/iFSpY.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/iFSpY.png" alt="enter image description here"></a></p>
  
  <p><a href="https://i.stack.imgur.com/VkgVB.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/VkgVB.png" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/CMtgt.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/CMtgt.png" alt="enter image description here"></a></p>