I am trying to use Gottschalk's algorithm (code available here) to create an oriented bounding box (OBB) for 3D triangular meshes. Since I am dealing with meshes, I am using the covariance matrix and eigenvalue decomposition approach to create the oriented bounding box. I have realized that the numerical accuracy in eigenvalue decomposition will lead to wrong OBB computation.
Let's clarify that with an example. Say I have a unit cube mesh consisting of 8 vertices in the range [0, 1] (depicted below). Clearly the OBB of this cube will be itself.
If I run Gottschalk's algorithm, I'd end up with a bounding box as shown below:
(Rotated for a better view)
Clearly the results are wrong. I've tracked down the problem to eigenvalue decomposition. Since the I'm dealing with a unit cube, the axes must be unit x, y and z directions. However, eigenvalue decomposition is producing axes in other directions. The wrong result stems from the covariance matrix. The covariance matrix I calculate for this cube is as follows:
Covariance matrix:
| 0.138889 -2.77556E-17 0 |
| -2.77556E-17 0.138889 0 |
| 0 0 0.138889 |
The resulting eigenvectors is as follows:
Eigenvectors:
| -0.7071 0 -0.7071 |
| -0.7071 0 0.7071 |
| 0 1.0000 0 |
Taking each column of this matrix as the OBB's axis will produce the wrong result shown in the picture above. If I replace the super small values in covariance matrix with zero, I will get the correct eigenvectors and (by extension) axes:
Correct eignenvectors:
| 1 0 0 |
| 0 1 0 |
| 0 0 1 |
This tends to be less of an issue with objects with more vertices. However, I do have objects with exactly 8 vertices and I need to be able to calculate their OBB correctly.
How should I account for these accuracy issues? How can I make my OBB algorithm more robust?
If it helps, I'm implementing the algorithm in C#. Convex hull is being computed using CGAL and the eigenvalue decomposition is carried out using Math.NET.
