OBB algorithm

[christer_ericson at playstation.sony.com]

Jeff Erickson <jeffe at cs.uiuc.edu> wrote on 09/30/2003 08:18:51 AM:

> Nash Aragam wrote:
> > Can somebody send me a link for a quick and easy code sample/algorithm
> > for computing OBB on a cloud of 3D points? Thanks much,
>
>[...]
>
> Here's code to quickly compute a provably-good approximation:
> http://valis.cs.uiuc.edu/~sariel/research/papers/00/diameter/
> diam_prog.html
>
> For a description of the algorithm, see
> http://valis.cs.uiuc.edu/~sariel/research/papers/98/bbox.html
> 
> Sariel and Gill's paper also includes a description of several
> commonly-used heuristics, none of which is guaranteed to be very good,
> although most of them are decent in practice.

I believe it's generally acknowledged by practitioners that
fitting an oriented bounding box by principal component analysis
or some other measurement of spread (as done in the above paper)
gives a rather poor OBB fit.

The best practical approach is to simply search the space of box
orientations in a brute-force, hill-climbing like manner. That is,
parameterize the orientation space using, say, Euler angles. Search
in increments of n degrees. Then refine the area around the best
fitting box by searching in increments of n/k degrees. Rinse and
repeat until you've reached a (local) maximum.


Christer Ericson
Sony Computer Entertainment, Santa Monica


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.