Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## Re: [Algorithms] Bounding Box calculation

 Re: [Algorithms] Bounding Box calculation From: Stephen Clibbery - 2007-10-31 10:41:15 ```> 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. ```

 [Algorithms] Bounding Box calculation From: Stephen Clibbery - 2007-10-29 17:23:48 ```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 From: Mustapha Bismi - 2007-10-30 16:41:18 Attachments: Message as HTML ```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 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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > ```
 Re: [Algorithms] Bounding Box calculation From: Andy Finkenstadt - 2007-10-30 16:56:03 Attachments: Message as HTML ```John Ratcliff's code repository at ; 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* < > stephen.clibbery@... > > 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 > GDAlgorithms-list@... > > 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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 Re: [Algorithms] Bounding Box calculation From: Stephen Clibbery - 2007-10-30 17:16:50 Attachments: Message as HTML ```> 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 From: Jon Watte - 2007-10-30 20:38:31 ``` 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 From: Stephen Clibbery - 2007-10-31 10:41:15 ```> 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 From: Johnson, Matt - 2007-10-31 15:36:28 ```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... :) ```