Calculate Oriented Bounding Box?

This topic is 4484 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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
Thanks! I'll take a look...

Share on other sites
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]

1. 1
2. 2
3. 3
4. 4
Rutin
18
5. 5

• 14
• 12
• 9
• 12
• 37
• Forum Statistics

• Total Topics
631423
• Total Posts
3000003
×