Fast oriented bounding box optimization on the rotation group SO (3,ℝ)
Authors:
Open Access
- 22 October 2011
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 30 (5) , 1-16
Abstract
An exact algorithm to compute an optimal 3D oriented bounding box was published in 1985 by Joseph O'Rourke, but it is slow and extremely hard to implement. In this article we propose a new approach, where the computation of the minimal-volume OBB is formulated as an unconstrained optimization problem on the rotation group SO (3,ℝ). It is solved using a hybrid method combining the genetic and Nelder-Mead algorithms. This method is analyzed and then compared to the current state-of-the-art techniques. It is shown to be either faster or more reliable for any accuracy.Keywords
This publication has 30 references indexed in Scilit:
- High‐quality surface remeshing using harmonic mapsInternational Journal for Numerical Methods in Engineering, 2010
- Bounds on the quality of the PCA bounding boxesComputational Geometry, 2009
- Faster core-set constructions and data-stream algorithms in fixed dimensionsComputational Geometry, 2006
- 3D collision detection: a surveyComputers & Graphics, 2001
- Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three DimensionsJournal of Algorithms, 2001
- Optimized View Frustum Culling Algorithms for Bounding BoxesJournal of Graphics Tools, 2000
- Incremental algorithms for collision detection between polygonal modelsIEEE Transactions on Visualization and Computer Graphics, 1997
- Efficient Collision Detection of Complex Deformable Models using AABB TreesJournal of Graphics Tools, 1997
- Finding minimal enclosing boxesInternational Journal of Parallel Programming, 1985
- Optimization by Simulated AnnealingScience, 1983