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

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.

Thanks! I'll take a look...

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]