Hey all,

So I recently implemented the oriented bounding box algorithm from David Eberly's website into my engine. The process involves computing a covariance matrix and then getting the eigenvectors/values. It makes use of the theorem that distinct eigenvalues of a real symmetric matrix will have corresponding eigenvectors that are mutually orthogonal, thus perfect for forming an OBB.

The algorithm is very fast and is an approximation. Eberly also has a minimum OBB computation algorithm which I have attempted to implement but it is very very slow (and not working atm).

When I ran the algorithm on different objects in my game, some have what looks like an almost perfect fitting OBB while others are a little strange. The object is contained in the OBB and there do not appear to be any violations that make the OBB incorrect, it just seems to not fit the object very well.

For example, on rectangular object with only 4 vertices, the optimal OBB should fit perfectly along the edges of the rectangle, but using this algorithm I get an OBB that is slightly rotated (maybe about 45 degrees) and thus has a lot of empty space.

I wonder if this is just a side effect of having an OBB approximation algorithm or if I may have done something slightly wrong.

I was hoping that someone who is familiar with OBB bounding volume computation could comment on the restrictions of using the approximation algorithm.

Also, I wanted to add that running the algorithm on a simple square object such as [(1, 1, 1), (-1, -1, 1), (-1, 1, 1), (1, -1, 1)]
will give an OBB:
Center: -0.5 -0.5 1.0
Axis[0]: 0 0 -1
Axis[1]: 0.707106781187 0.707106781187 0.0
Axis[2]: 0.707106781187 -0.707106781187 0.0
Extent[0]: 0.0
Extent[1]: 0.707106781187
Extent[2]: 1.41421356237


Thanks for the help!

The problem with a square is that the covariance matrix has an eigenvalue of multiplicity 2; that is, the dimension of the eigenspace is 2, so there are infinitely many choices for a pair of orthogonal eigenvectors. A numerical eigensolver is free to compute any of these pairs, and you cannot expect that the pair it chooses leads to the "best fit" you are expecting.. Generally, if there is a symmetry in the input data, you will probably have eigenspaces of dimension 2 or 3, and the OBB might not fit well for the eigenvectors returned by the numerical eigensolver.

In your square example in 3D, the center does not look right. The center should be the average of the vertices, which is (0,0,1), not (-0.5,-0.5,1). So your implementation might have other problems. Compute the center first. When building the covariance matrix, do not forget to subtract the center from each vertex before computing the sum of squared values.

The legend himself responds to my post! Thanks for the info Mr. Eberly. So for symmetric objects it would be best for me to use the minOBB algorithm that you have?

I fixed the bug you mentioned. I am doing everything in a python script, the error came from passing a reference when I didnt mean to, which in turn changed the value of one of my input points unexpectedly.

Thanks again,
Darkbouncer

If you want as good a fit as possible, the minimum-volume OBB is a decent choice. As mentioned, it is slow, so probably better for off-line computations rather than during the real-time application.

Alternatively, you can use the covariance approach. If you have two (nearly) equal eigenvalues (eigenspace of dimension 2) and a third eigenvalue that is different from them (eigenspace of dimension 1), you can project out the eigenvector from the third eigenvalue. You now have a model in the 2-dimensional eigenspace. Now you can use the method of rotating calipers to find the minimum-area rectangle containing the (projected) points. Effectively, this allows you to search the 2-dimensional eigenspace for a pair of orthogonal eigenvectors that give you a good fit. I suspect this approach is faster than always trying to compute the minimum-volume OBB.

Thanks for all of the help! I doubt I would have been able to have OBB collision in my engine without all of your hard work to reference from. I always have your book sitting next to me =)