OBB algorithm

[Suresh Venkatasubramanian]

On Fri, 3 Oct 2003 christer_ericson at playstation.sony.com wrote:

> Jeff Erickson <jeffe at cs.uiuc.edu> wrote on 09/30/2003 08:18:51 AM:
>
> 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.
>

If you have code that does this well, I'd be curious to take a look at it.
At the risk of tooting my own horn, we have a paper at this year's ESA
that among other things computes oriented bounding boxes (the conf version
doesn't go into this in detail, but in our full version we do experiments
on computing OBBs). Our approach uses graphics cards to do the
computation: it compares efficiency wise to the code by Sariel and Gil,
and also fits well into the framework of search-and-zoom (I can give more
details via email if anyone is interested).

The paper is:

Streaming Geometric optimization in graphics hardware
P.Agarwal, S. Krishnan, N. Mustafa, and S. Venkatasubramanian



Suresh Venkatasubramanian, Ph: 973 360 8951 (o)
Member, Technical Staff    Web: http://www.research.att.com/~suresh/
AT&T Shannon Labs

I made a killing in the stock market once, but the only casualty was my investment - Frank & Ernest 7/8/00

-------------
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.