research-article

Fast oriented bounding box optimization on the rotation group SO(3,ℝ)

Authors:

Chia-Tche Chang,

Bastien Gorissen,

Samuel MelchiorAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 30, Issue 5

Article No.: 122, Pages 1 - 16

https://doi.org/10.1145/2019627.2019641

Published: 22 October 2011 Publication History

Get Access

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.

Supplementary Material

chang (chang.zip)

Supplemental movie and image files for, Fast oriented bounding box optimization on the rotation group SO(3,ℝ)

Download
1.29 MB

References

[1]

Agarwal, P., Har-Peled, S., and Varadarajan, K. 2004. Approximating extent measures of points. J. ACM 51, 4, 606--635.

Digital Library

Google Scholar

[2]

Assarsson, U. and Möller, T. 2000. Optimized view frustum culling algorithms for bounding boxes. J. Graph. GPU Game Tools 5, 1, 9--22.

Digital Library

Google Scholar

[3]

Barequet, G., Chazelle, B., Guibas, L., Mitchell, J., and Tal, A. 1996. BOXTREE: A hierarchical representation for surfaces in 3D. Comput. Graph. Forum. 15, 3, 387--396.

Crossref

Google Scholar

[4]

Barequet, G. and Har-Peled, S. 2001. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algor. 38, 1, 91--109.

Digital Library

Google Scholar

[5]

Borckmans, P. B. and Absil, P.-A. 2010. Oriented bounding box computation using particle swarm optimization. In Proceedings at the European Symposium on Artificial Neural Networks (ESANN'10). 345--350.

Google Scholar

[6]

Chan, T. 2006. Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom. Theory Appl. 35, 1-2, 20--35.

Digital Library

Google Scholar

[7]

Chelouah, R. and Siarry, P. 2003. Genetic and nelder-mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions. Euro. J. Oper. Res. 148, 2, 335--348.

Crossref

Google Scholar

[8]

Conn, A. R., Gould, N. I. M., and Toint, P. L. 2000. Trust Region Methods. SIAM, Philadelphia, PA.

Digital Library

Google Scholar

[9]

Conn, A. R., Scheinberg, K., and Vicente, L. N. 2009. Introduction to Derivative-Free Optimization. SIAM, Philadelphia, PA.

Digital Library

Google Scholar

[10]

den Bergen, G. V. 1998. Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools 2, 1--13.

Digital Library

Google Scholar

[11]

Dimitrov, D., Holst, M., Knauer, C., and Kriegel, K. 2009a. Closed-form solutions for continuous pca and bounding box algorithms. Comput. Vis. Comput. Graph. Theory Appl. 24, 26--40.

Google Scholar

[12]

Dimitrov, D., Knauer, C., Kriegel, K., and Rote, G. 2009b. Bounds on the quality of the pca bounding boxes. Comput. Geom. Theory Appl. 42, 8, 772--789.

Digital Library

Google Scholar

[13]

Durand, N. and Alliot, J.-M. 1999. A combined nelder-mead simplex and genetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'99). Morgan Kaufmann, 1--7.

Google Scholar

[14]

Edelsbrunner, H. and Maurer, H. A. 1985. Finding extreme points in three dimensions and solving the post-office problem in the plane. Inf. Process. Lett. 21, 1, 39--47.

Crossref

Google Scholar

[15]

Ericson, C. 2004. Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology). Morgan Kaufmann.

Digital Library

Google Scholar

[16]

Freeman, H. and Shapira, R. 1975. Determining the minimum-area encasing rectangle for an arbitrary closed curve. Comm. ACM 18, 7, 409--413.

Digital Library

Google Scholar

[17]

GAMMA Group. 2008. 3d meshes research database of the group Génération Automatique de Maillages et Méthodes d'Adaptation, INRIA, France. http://www-roc.inria.fr/gamma/gamma/download/download. php.

Google Scholar

[18]

Garcia-Alonso, A., Serrano, N., and Flaquer, J. 1994. Solving the collision detection problem. IEEE Comput. Graph. Appl. 14, 3, 36--43.

Digital Library

Google Scholar

[19]

Geuzaine, C. and Remacle, J.-F. 2009. Gmsh: a three-dimensional finite element mesh generator with built-in pre- and post-processing facilities. Int. J. Numer. Methods Engin. 79, 1309--1331.

Crossref

Google Scholar

[20]

Glover, F. 1989. Tabu Search---Part I. ORSA J. Comput. 1, 3, 190--206.

Crossref

Google Scholar

[21]

Glover, F. 1990. Tabu Search---Part II. ORSA J. Comput. 2, 1, 4--32.

Crossref

Google Scholar

[22]

Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing.

Digital Library

Google Scholar

[23]

Golub, G. H. and van Loan, C. F. 1996. Matrix Computations 3rd Ed. Johns Hopkins University Press.

Digital Library

Google Scholar

[24]

Gottschalk, S., Lin, M. C., and Manocha, D. 1996. Obbtree: a hierarchical structure for rapid interference detection. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH96). ACM, New York, 171--180.

Digital Library

Google Scholar

[25]

Holland, J. H. 1975. Adaptation in Natural and Artificial Systems 2nd Ed. University of Michigan Press, Ann Arbor, MI.

Google Scholar

[26]

Iones, A., Zhukov, S., and Krupkin, A. 1998. On optimality of obbs for visibility tests for frustum culling, ray shooting and collision detection. In Proceedings of the Computer Graphics International Conference. IEEE Computer Society, Los Alamitos, CA, 256.

Digital Library

Google Scholar

[27]

Jiménez, P., Thomas, F., and Torras, C. 2000. 3d collision detection: A survey. Comput. Graph. 25, 269--285.

Crossref

Google Scholar

[28]

Jolliffe, I. T. 2002. Principal Component Analysis. Springer, New York.

Google Scholar

[29]

Kelley, C. T. 1999. Iterative Methods for Optimization. 18 Frontiers in Applied Mathematics. SIAM, Philadelphia, PA.

Google Scholar

[30]

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Sci. 220, 4598, 671--680.

Google Scholar

[31]

Kolda, T. G., Lewis, R. M., and Torczon, V. 2003. Optimization by direct search: New perspectives on some classical and modern methods. SIAM Rev. 45, 3, 385--482.

Crossref

Google Scholar

[32]

Korsawe, J. 2008. Minimal bounding box. MATLAB Central File Exchange. http://www.mathworks.com/matlabcentral/fileexchange/18264.

Google Scholar

[33]

Krakowski, K. A., Hüper, K., and Manton, J. H. 2007. On the computation of the karcher mean on spheres and special orthogonal groups. In Proceedings of the Workshop on Robotics and Mathematic (RoboMat'07). 119--124.

Google Scholar

[34]

Lahanas, M., Kemmerer, T., Milickovic, N., Karouzakis, K., Baltas, D., and Zamboglou, N. 2000. Optimized bounding boxes for three-dimensional treatment planning in brachytherapy. Med. Phys. 27, 10, 2333--2342.

Crossref

Google Scholar

[35]

McKinnon, K. 1999. Convergence of the Nelder-Mead simplex method to a nonstationary point. SIAM J. Optimiz. 9, 1, 148--158.

Digital Library

Google Scholar

[36]

Nelder, J. A. and Mead, R. 1965. A simplex method for function minimization. Comput. J. 7, 4, 308--313.

Crossref

Google Scholar

[37]

O'Rourke, J. 1985. Finding minimal enclosing boxes. Int. J. Comput. Inf. Sci. 14, 183--199.

Crossref

Google Scholar

[38]

Ponamgi, M. K., Manocha, D., and Lin, M. C. 1997. Incremental algorithms for collision detection between polygonal models. IEEE Trans. Vis. Comput. Graph. 3, 1, 51--64.

Digital Library

Google Scholar

[39]

Preparata, F. and Shamos, M. 1985. Computational Geometry: An Introduction. Springer, New York.

Digital Library

Google Scholar

[40]

Press, W., Teukolsky, S., Vetterling, W., and Flannery, B. 1992. Numerical Recipes in C 2nd Ed. Cambridge University Press, Cambridge, UK.

Digital Library

Google Scholar

[41]

Remacle, J.-F., Geuzaine, C., Compére, G., and Marchandise, E. 2010. High quality surface meshing using harmonic maps. Int. J. Numer. Methods Engin. 83, 403--425.

Google Scholar

[42]

Sarlette, A. and Sepulchre, R. 2009. Consensus optimization on manifolds. SIAM J. Control Optimiz. 48, 1, 56--76.

Digital Library

Google Scholar

[43]

Shamos, M. I. 1978. Computational geometry. Ph.D. thesis, Yale University, New Haven, CT.

Digital Library

Google Scholar

[44]

Toussaint, G. 1983. Solving geometric problems with the rotating calipers. In Proceedings of IEEE MELECON.

Google Scholar

Cited By

View all

Káčerik MBittner J(2024)SAH-Optimized k-DOP Hierarchies for Ray TracingProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753917:3(1-16)Online publication date: 9-Aug-2024
https://doi.org/10.1145/3675391
Meena PKumar HYadav S(2024)A Volumetric Saliency Guided Image Summarization for RGB-D Indoor Scene ClassificationIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2024.341294934:11_Part_1(10917-10929)Online publication date: 11-Jun-2024
https://dl.acm.org/doi/10.1109/TCSVT.2024.3412949
Piccolrovazzi MAdam MZakour MEger SSteinbach E(2024)BoxGrounder: 3D Visual Grounding Using Object Size EstimatesIEEE Robotics and Automation Letters10.1109/LRA.2024.34558989:10(9023-9030)Online publication date: Oct-2024
https://doi.org/10.1109/LRA.2024.3455898
Show More Cited By

Index Terms

Fast oriented bounding box optimization on the rotation group SO(3,ℝ)

Recommendations

Development and investigation of efficient artificial bee colony algorithm for numerical function optimization

Artificial bee colony algorithm (ABC), which is inspired by the foraging behavior of honey bee swarm, is a biological-inspired optimization. It shows more effective than genetic algorithm (GA), particle swarm optimization (PSO) and ant colony ...
Chaotic dynamic weight particle swarm optimization for numerical function optimization

Particle swarm optimization (PSO), which is inspired by social behaviors of individuals in bird swarms, is a nature-inspired and global optimization algorithm. The PSO method is easy to implement and has shown good performance for many real-world ...
Gravity-based particle swarm optimization with hybrid cooperative swarm approach for global optimization

Premature convergence has been recognized as one of the major drawbacks of particle swarm optimization PSO algorithms. In particular, the lack of diversity in PSO performance is an essential cause that commonly results in high susceptibility to ...

Reviews

Reviewer: Amos O Olagunju

Fitting oriented bounding boxes (OBBs) in real-time applications, such as the rapid rendering of 3D scenes and the discovery of interference, is an open research problem. Hierarchical OBB trees are used to minimize the computational time in the detection of two intersecting objects to identify disjoint pieces [1]. A variety of methods can be used for computing an OBB for a triangular mesh. Algorithms for fitting OBBs based on the minimum volume, the distribution of mesh points, and the distribution of mesh triangles exist in the literature [2]. The execution time is not typically an issue with these methods of fitting OBBs because they apply a preprocessing phase in real-time applications. However, how should practical algorithms, with a linear asymptotic time, for identifying the complexity of the convex hull of objects such as the heart work__?__ Chang et al. point out the time deficiencies of the well-known algorithms for finding the best OBBs. They critique O'Rourke's algorithm [3], the heuristics based on the principal component analysis, and the brute force approaches to locating the best OBBs as computationally inefficient for real-life applications. Consequently, they present a derivative-free optimization technique equipped with a genetic algorithm for finding the best OBBs. The authors articulate "the search of the minimal volume OBB as an optimization problem defined on a manifold." The objective function of the OBB optimization is tri-linear and the constraints are linear. The objective function "is not differentiable at every rotation matrix ... that brings at least one face of the OBB to be flush with one edge of the convex hull." These matrix rotations hypothetically produce the local minima of this OBB objective function. The hybrid bounding box rotation identification (HYBBRID) method is used to locate the global minimum volume of the OBB. The HYBBRID method contains a stochastic genetic algorithm and an a priori deterministic Nelder-Mead multi-scale grid search algorithm. The genetic algorithm is used to compute the initial condition that guarantees convergence in the determination of the global minimum using the Nelder-Mead simplex search algorithm. The performance of the HYBBRID method was evaluated with numerous replications of experiments designed to identify objects such as a ball, a hand, a heart, and a globe. Overall, the method was successful in locating an optimal OBB for each object. The authors succinctly review algorithms for exploring derivative-free optimization techniques that guarantee convergence to a local minimum, and meta-heuristics for locating the global optimum in an entire OBB search problem space. The graphical illustrations of the issues of, and solutions to, the fitting of OBBs in this paper are insightful and remarkable. Nevertheless, I challenge applied mathematicians to read this mind-bending paper, and recommend parameters that might be useful in genetic algorithms to guarantee the location of all solutions in the search spaces of data mining algorithms for real-time OBB applications. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 30, Issue 5

October 2011

198 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2019627

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2011

Accepted: 01 April 2011

Revised: 01 March 2011

Received: 01 December 2009

Published in TOG Volume 30, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
1,684
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Káčerik MBittner J(2024)SAH-Optimized k-DOP Hierarchies for Ray TracingProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753917:3(1-16)Online publication date: 9-Aug-2024
https://doi.org/10.1145/3675391
Meena PKumar HYadav S(2024)A Volumetric Saliency Guided Image Summarization for RGB-D Indoor Scene ClassificationIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2024.341294934:11_Part_1(10917-10929)Online publication date: 11-Jun-2024
https://dl.acm.org/doi/10.1109/TCSVT.2024.3412949
Piccolrovazzi MAdam MZakour MEger SSteinbach E(2024)BoxGrounder: 3D Visual Grounding Using Object Size EstimatesIEEE Robotics and Automation Letters10.1109/LRA.2024.34558989:10(9023-9030)Online publication date: Oct-2024
https://doi.org/10.1109/LRA.2024.3455898
Meena PKumar HYadav S(2024)An Indoor Scene Localization Method Using Graphical Summary of Multi-View RGB-D Images2024 IEEE International Conference on Image Processing (ICIP)10.1109/ICIP51287.2024.10648118(3306-3312)Online publication date: 27-Oct-2024
https://doi.org/10.1109/ICIP51287.2024.10648118
Xiao TDeng JWen CGu Q(2024)Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentationInternational Journal of Digital Earth10.1080/17538947.2024.230870717:1Online publication date: 25-Jan-2024
https://doi.org/10.1080/17538947.2024.2308707
Bao YLiu JJia XQie J(2024)An assisted assembly method based on augmented realityThe International Journal of Advanced Manufacturing Technology10.1007/s00170-024-14563-yOnline publication date: 28-Sep-2024
https://doi.org/10.1007/s00170-024-14563-y
Wang SSaeidi TLilge LBetz V(2023)Integrating clinical access limitations into iPDT treatment planning with PDT-SPACEBiomedical Optics Express10.1364/BOE.47821714:2(714)Online publication date: 9-Jan-2023
https://doi.org/10.1364/BOE.478217
Yang JJia XYan D(2023)Topology Guaranteed B-Spline Surface/Surface IntersectionACM Transactions on Graphics10.1145/361834942:6(1-16)Online publication date: 5-Dec-2023
https://doi.org/10.1145/3618349
Vitsas NEvangelou IPapaioannou GGkaravelis A(2023)Parallel Transformation of Bounding Volume Hierarchies into Oriented Bounding Box TreesComputer Graphics Forum10.1111/cgf.1475842:2(245-254)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14758
Li RZhang LLi CLai YGao L(2023)E3Sym: Leveraging E(3) Invariance for Unsupervised 3D Planar Reflective Symmetry Detection2023 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV51070.2023.01337(14497-14507)Online publication date: 1-Oct-2023
https://doi.org/10.1109/ICCV51070.2023.01337
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Development and investigation of efficient artificial bee colony algorithm for numerical function optimization

Chaotic dynamic weight particle swarm optimization for numerical function optimization

Gravity-based particle swarm optimization with hybrid cooperative swarm approach for global optimization

Reviews

Access critical reviews of Computing literature here