Fast Oriented Bounding Box Optimization on the Rotation Group SO(3, R)

被引：42

作者：

Chang, Chia-Tche ^{[1
]}

Gorissen, Bastien ^{[2
]}

Melchior, Samuel ^{[1
,2
]}

机构：

[1] Catholic Univ Louvain, Dept Engn Math, B-1348 Louvain, Belgium

[2] Catholic Univ Louvain, Div Appl Mech, B-1348 Louvain, Belgium

来源：

ACM TRANSACTIONS ON GRAPHICS | 2011年 / 30卷 / 05期

关键词：

Algorithms; Performance; Experimentation; Computational geometry; optimization; manifolds; bounding box; COLLISION DETECTION; ALGORITHMS; SET;

D O I：

10.1145/2019627.2019641

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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, R). 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.

引用

页数：16

共 43 条

[1] Approximating extent measures of points [J].

Agarwal, PK ;

Har-Peled, S ;

Varadarajan, KR .

JOURNAL OF THE ACM, 2004, 51 (04) :606-635

[2]

[Anonymous], 1999, P GECCO 1999

[3]

Assarsson U., 2000, Journal of Graphics Tools, V5, P9, DOI 10.1080/10867651.2000.10487517

[4] Efficiently approximating the minimum-volume bounding box of a point set in three dimensions [J].

Barequet, G ;

Har-Peled, S .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 38 (01) :91-109

[5]

Barequet G, 1996, COMPUT GRAPH FORUM, V15, pC387, DOI 10.1111/1467-8659.1530387

[6]

Borckmans P.B., 2010, ESANN 2010 P EUROPEA, P345

[7] Faster core-set constructions and data-stream algorithms in fixed dimensions [J].

Chan, Timothy M. .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2006, 35 (1-2) :20-35

[8] Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions [J].

Chelouah, R ;

Siarry, P .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 148 (02) :335-348

[9]

Conn A. R., 2000, MPS SIAM SERIES OPTI

[10]

Conn A. R., 2009, Introduction to Derivative-Free Optimization

← 1 2 3 4 5 →