# Calculate Oriented Bounding Box?

## Recommended Posts

Zoomby    122
Hi, how can I calculate an Oriented-Bounding-Box from a set of points? Is there an easy way to do it? Bye Chris

##### Share on other sites
z80    134
Uhhm.. I never actually tried it, but perhaps the following article is helpful?

http://graphics.stanford.edu/courses/cs468-06-winter/Papers/har-peled-bbox.pdf

The article presents both a compex but efficient and a simpler but less efficient solution.

I am afraid there is no easy way at the moment tho.

##### Share on other sites
Zoomby    122
Thanks! I'll take a look...

##### Share on other sites
MikeWW    224
To calculate good OBBs is actually quite convoluted. Here is what I do:

1. First find the convex hull of the set of points (I used to use my own code, then John Ratcliff's QuickHull hack and now I use Stan Melax's StanHull (packaged up by John again and put out on the GDAlgorithms list)).

2. After finding the hull I then calculate the covariance matrix of the set of vertices of the hull.

3. I then extract the eigenvectors of the covariance matrix - these are the axis of the OBB. (Again I used to use my own solving code for the eigenvectors but I now use a better solver written by James M. Van Verth - I think it was in a Game Programming Gems book...)

The reasoning for calculating the hull first and not just calculating the covariance matrix of the original points set is that you don't want the covariance of of all the points - just the points whose distribution (roughly) matches that of the OBB axis. An approximation of this (as you don't know the OBB axis as that is what you want!) is are the set of points that are the vertices of the convex hull of the original point set.

I can provide more info/references if you wish. I'm not sure if StanHull has a permanent place on the web yet but I can send it to you if you want. I'm sure Van Verth's code is around online somewhere.

Hope this helps!

EDIT: That paper looks interesting z80, thanks for the link!

Mike.

[Edited by - MikeWW on March 15, 2006 4:10:51 AM]