gdalgorithms-list

[Algorithms] Bounding Box calculation

[Stephen C. <ste...@la...>]

Hi,

I need to calculate an oriented bounding box form a point cloud. I have
previously used a rather brute-force rotating-caliper style approach, which
gave good results but was slow. I need something faster now; I guess the
covariance matrix method is the way to go..? Does anyone bother taking the
convex hull of the points first, or does this not make much difference in
practice?

Cheers,
Steve.

Stephen Clibbery
Technology Director 
Lateral Visions Software Company 

Re: [Algorithms] Bounding Box calculation

[Mustapha B. <ja...@gm...>]

Hi,

A "long time ago" (2000, not that far hopefully), I implemented it using the
covariance matrix (Sorry, the work was explained in french only -
http://mustapha.bismi.free.fr/articles/obb.pdf ).

The paper I used as a reference was "OBB-Tree: A Hierarchical Structure for
Rapid Interference Detection" (http://citeseer.ist.psu.edu/108215.html). The
whole "hierarchical OBB tree" thing is maybe over the top, but the algorithm
to compute the OBBs is detailed there.

Hope this helps ^_^

Cheers,

- Mustapha Bismi
- http://antipatterns.hautetfort.com

On 10/29/07, Stephen Clibbery <ste...@la...> wrote:
>
>
> Hi,
>
> I need to calculate an oriented bounding box form a point cloud. I have
> previously used a rather brute-force rotating-caliper style approach,
> which
> gave good results but was slow. I need something faster now; I guess the
> covariance matrix method is the way to go..? Does anyone bother taking the
> convex hull of the points first, or does this not make much difference in
> practice?
>
> Cheers,
> Steve.
>
> Stephen Clibbery
> Technology Director
> Lateral Visions Software Company
>
>
>
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc.
> Still grepping through log files to find problems?  Stop.
> Now Search log events and configuration files using AJAX and a browser.
> Download your FREE copy of Splunk now >> http://get.splunk.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Bounding Box calculation

[Andy F. <an...@si...>]

John Ratcliff's code repository at 
<http://www.amillionpixels.us/sourcecode.htm> has another beastie:

http://codesuppository.blogspot.com/2006/06/best-fit-oriented-bounding-box.html

Likely this is also brute-force, but John writes wicked-fast code, so it 
might be acceptable.

--andy


Mustapha Bismi wrote:
> Hi,
>
> A "long time ago" (2000, not that far hopefully), I implemented it 
> using the covariance matrix (Sorry, the work was explained in french 
> only - http://mustapha.bismi.free.fr/articles/obb.pdf ).
>
> The paper I used as a reference was "OBB-Tree: A Hierarchical 
> Structure for Rapid Interference Detection" ( 
> http://citeseer.ist.psu.edu/108215.html). The whole "hierarchical OBB 
> tree" thing is maybe over the top, but the algorithm to compute the 
> OBBs is detailed there.
>
> Hope this helps ^_^
>
> Cheers,
>
> - Mustapha Bismi
> - http://antipatterns.hautetfort.com
>
> On 10/29/07, *Stephen Clibbery* < 
> ste...@la... 
> <mailto:ste...@la...>> wrote:
>
>
>     Hi,
>
>     I need to calculate an oriented bounding box form a point cloud. I
>     have
>     previously used a rather brute-force rotating-caliper style
>     approach, which
>     gave good results but was slow. I need something faster now; I
>     guess the
>     covariance matrix method is the way to go..? Does anyone bother
>     taking the
>     convex hull of the points first, or does this not make much
>     difference in
>     practice?
>
>     Cheers,
>     Steve.
>
>     Stephen Clibbery
>     Technology Director
>     Lateral Visions Software Company
>
>
>
>
>     -------------------------------------------------------------------------
>
>     This SF.net email is sponsored by: Splunk Inc.
>     Still grepping through log files to find problems?  Stop.
>     Now Search log events and configuration files using AJAX and a
>     browser.
>     Download your FREE copy of Splunk now >> http://get.splunk.com/
>     _______________________________________________
>     GDAlgorithms-list mailing list
>     GDA...@li...
>     <mailto:GDA...@li...>
>     https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>     Archives:
>     http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
> ------------------------------------------------------------------------
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc.
> Still grepping through log files to find problems?  Stop.
> Now Search log events and configuration files using AJAX and a browser.
> Download your FREE copy of Splunk now >> http://get.splunk.com/
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Bounding Box calculation

[Stephen C. <ste...@la...>]

> Mustapha Bismi:

> A "long time ago" (2000, not that far hopefully), I implemented it using
the covariance matrix (Sorry, the work was explained in french only -
http://mustapha.bismi.free.fr/articles/obb.pdf ).



Thanks, guess I'll have to brush up on my French :-)

In any case, that looks like another vote for the convex hull being a
potentially important step in the covariance approach.

 

> --andy

> Likely this is also brute-force, but John writes wicked-fast code, so it
might be acceptable.

 

Hehe, this looks a lot like my previous code (except it's a bit smarter than
mine :)

This kind of approach has worked very nicely for us in the past as an
offline process, but I need something faster now because it needs to be able
to update while the app is running.

 

In fact, I'm willing to trade off quite a lot on the closeness of the fit
(these OBBs will only be used for frustum-cull tests), so maybe a
brute-force approach trying just a few coarse orientations would be good
enough and faster than anything else. I guess I'll just have to buckle down
and implement the different approaches and compare them :-)

 

Cheers,

Steve.

Re: [Algorithms] Bounding Box calculation

[Jon W. <hp...@mi...>]

Stephen Clibbery wrote:
>
> In fact, I’m willing to trade off quite a lot on the closeness of the 
> fit (these OBBs will only be used for frustum-cull tests), so maybe a 
> brute-force approach trying just a few coarse orientations would be 
> good enough and faster than anything else. I guess I’ll just have to 
> buckle down and implement the different approaches and compare them J
>

So why not use an AABB in model space instead, and then turn it into 
OOBB as part of model orientation? That's as fast as it gets to 
calculate, assuming you still need to look at all vertices. Another 
option is a bounding sphere, which doesn't even need rotation.

Cheers,

/ h+

-- 
-- Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] Bounding Box calculation

[Stephen C. <ste...@la...>]

> So why not use an AABB in model space instead, and then turn it into
> OOBB as part of model orientation? That's as fast as it gets to

That makes sense; it's actually exactly what I've got at the moment as my
first-cut temporary solution. I was thinking to try some alternatives in
case there's something better than an AABB, but still pretty cheap. AABBs
can be pretty bad in worst cases, eg a pencil on the diagonal in model
space. OTOH, it would take a worst-case artist to make a pencil on a
diagonal in model space... :)

Cheers,
Steve.

Re: [Algorithms] Bounding Box calculation

[Johnson, M. <Mat...@am...>]

Everything is a tradeoff. What's the goal? AABB alone makes for a pretty
coarse collision detection system. If you want a quick initial rejection
test, use spheres.=20

P.S. Tutorial on Principle Component Analysis:
http://csnet.otago.ac.nz/cosc453/student_tutorials/principal_components.
pdf

Matthew

> So why not use an AABB in model space instead, and then turn it into
> OOBB as part of model orientation? That's as fast as it gets to

That makes sense; it's actually exactly what I've got at the moment as
my
first-cut temporary solution. I was thinking to try some alternatives in
case there's something better than an AABB, but still pretty cheap.
AABBs
can be pretty bad in worst cases, eg a pencil on the diagonal in model
space. OTOH, it would take a worst-case artist to make a pencil on a
diagonal in model space... :)