基于凸包的最小体积有向包围盒生成算法
|
摘要
针对复杂物体三维点集的建模问题,提出一种基于凸包的最小体积的封闭有向包围盒生成算法.对凸包和其最小体积有向包围盒的关系进行分析,总结了其4种边面接触类型.通过枚举凸包中边的所有可能的组合,唯一确定包围盒的最优方向.实验证明,该算法可以快速生成符合模型体积特征的最小有向包围盒,且拟合效果良好.
A new method was presented for computing the tight-fitting enclosing minimum volume oriented bounding boxes for constructing the model of complex object point sets in three dimensions. The relationship between the convex hull and its minimum volume oriented bounding box with the smallest volume was analyzed,and four kinds of edge contact types were summarized. The optimal box orientations are uniquely determined by combinations of edges in the convex hull of the input point set. Empirical evidence shows that this process always yields the globally minimum bounding box by volume feature, which concludes that this method provides a good simulation.
A new method was presented for computing the tight-fitting enclosing minimum volume oriented bounding boxes for constructing the model of complex object point sets in three dimensions. The relationship between the convex hull and its minimum volume oriented bounding box with the smallest volume was analyzed,and four kinds of edge contact types were summarized. The optimal box orientations are uniquely determined by combinations of edges in the convex hull of the input point set. Empirical evidence shows that this process always yields the globally minimum bounding box by volume feature, which concludes that this method provides a good simulation.
引文
[1]史旭升,乔立红,朱作为.基于改进OBB包围盒的碰撞检测算法[J].湖南大学学报(自然科学版),2014,41(5):26—31.SHI X S,QIAO L H,ZHU Z W. Algorithm of collision detectionbased on improved oriented bounding box[J]. Journal of HunanUniversity(Natural Sciences),2014,41(5):26—31.(In Chinese)
[2]陈华.确定任意形状物体最小包围盒的一种方法[J].工程图学学报,2010,31(2):49—53.CHEN H. A method to generate the minimum bounding boxes forshape-arbitrary objects[J]. Journal of Engineering Graphics,2010,31(2):49—53.(In Chinese)
[3] O′ROUKRE J. Finding minimal enclosing boxes[J]. InternationalJournal of Computer&Information Sciences,1985,14(3):183—199.
[4]陈柏松,叶雪梅,安利.基于非线性主成分分析的最小包围盒计算方法[J].计算机集成制造系统,2010,16(11):2375—2378.CHEN B S,YE X M,AN L. Minimum bounding box calculationbased on nonlinear principle component analysis[J]. ComputerIntegrated Manufacturing Systems,2010,16(11):2375—2378.(InChinese)
[5] DIMITROV D,KNAUER C,KRIEGEL K,et al. Bounds on thequality of the PCA bounding boxes[J]. Computational GeometryTheory&Applications,2009,42(8):772—789.
[6] BAREQUET G,HAR-PELED S. Efficiently approximating theminimum[J]. Journal of Algorithms,2001,38(1):91—109.
[7] LARSSON T,Ka LLBERG L. Fast computation of tight fitting ori-ented bounding boxes[J]. Game Engine Gems,2011,2:3—19.
[8] BORCKMANS P B,ABSIL P A. Oriented bounding box computa-tion using particle swarm optimization[C]//European Symposiumon Artificial Neural Networks. Bruges,Belgium,2010.
[9]孙殿柱,史阳,刘华东,等.基于遗传算法的散乱点云最小包围盒求解[J].北京航空航天大学学报,2013,39(8):995—998.SUN D Z,SHI Y,LIU H D,et al. Solution of minimum boundingbox of scattered points based on genetic algorithm[J]. Journal ofBeijing University of Aeronautics and Astronautics,2013,39(8):995—998.(In Chinese)
[10]CHANG C T,GORISSEN B,MELCHIOR S. Fast oriented boundingbox optimization on the rotation group SO(3,R)[J]. ACM Transac-tions on Graphics,2011,30(5):1—16.
[11] FREEMAN H, SHAPIRA R. Determining the minimum-area en-casing rectangle for an arbitrary closed curve[J]. Communicationsof the ACM, 1975, 18(7):409—413.
[12]BARBER C B,DOBKIN D P,HUHDANPAA H. The quickhull al-gorithm for convex hulls[J]. ACM Transactions on MathematicalSoftware,1996,22(4):469—483.
[13]IMAI H,IRI M. Polygonal approximations of a curve[J]. Compu-tational Morphology,2014,6(1):71—86.
[14]李仁忠,杨曼,刘阳阳,等.一种散乱点云的均匀精简算法[J].光学学报,2017,37(7):89—97.LI R Z,YANG M,LIU Y Y,et al. An uniform simplification algo-rithm for scattered point cloud[J]. Acta Optica Sinica,2017,37(7):89—97.(In Chinese)
[15] A C++library for linear algebra and geometry manipulation forcomputer graphics[EB/OL]. https://github.com/juj/MathGeoLib.2017 March.
[16] GAMMA GROUP,2008. 3D meshes research database.[EB/OL].https://www-roc.inria.fr/gamma/gamma/download/download.php.
[2]陈华.确定任意形状物体最小包围盒的一种方法[J].工程图学学报,2010,31(2):49—53.CHEN H. A method to generate the minimum bounding boxes forshape-arbitrary objects[J]. Journal of Engineering Graphics,2010,31(2):49—53.(In Chinese)
[3] O′ROUKRE J. Finding minimal enclosing boxes[J]. InternationalJournal of Computer&Information Sciences,1985,14(3):183—199.
[4]陈柏松,叶雪梅,安利.基于非线性主成分分析的最小包围盒计算方法[J].计算机集成制造系统,2010,16(11):2375—2378.CHEN B S,YE X M,AN L. Minimum bounding box calculationbased on nonlinear principle component analysis[J]. ComputerIntegrated Manufacturing Systems,2010,16(11):2375—2378.(InChinese)
[5] DIMITROV D,KNAUER C,KRIEGEL K,et al. Bounds on thequality of the PCA bounding boxes[J]. Computational GeometryTheory&Applications,2009,42(8):772—789.
[6] BAREQUET G,HAR-PELED S. Efficiently approximating theminimum[J]. Journal of Algorithms,2001,38(1):91—109.
[7] LARSSON T,Ka LLBERG L. Fast computation of tight fitting ori-ented bounding boxes[J]. Game Engine Gems,2011,2:3—19.
[8] BORCKMANS P B,ABSIL P A. Oriented bounding box computa-tion using particle swarm optimization[C]//European Symposiumon Artificial Neural Networks. Bruges,Belgium,2010.
[9]孙殿柱,史阳,刘华东,等.基于遗传算法的散乱点云最小包围盒求解[J].北京航空航天大学学报,2013,39(8):995—998.SUN D Z,SHI Y,LIU H D,et al. Solution of minimum boundingbox of scattered points based on genetic algorithm[J]. Journal ofBeijing University of Aeronautics and Astronautics,2013,39(8):995—998.(In Chinese)
[10]CHANG C T,GORISSEN B,MELCHIOR S. Fast oriented boundingbox optimization on the rotation group SO(3,R)[J]. ACM Transac-tions on Graphics,2011,30(5):1—16.
[11] FREEMAN H, SHAPIRA R. Determining the minimum-area en-casing rectangle for an arbitrary closed curve[J]. Communicationsof the ACM, 1975, 18(7):409—413.
[12]BARBER C B,DOBKIN D P,HUHDANPAA H. The quickhull al-gorithm for convex hulls[J]. ACM Transactions on MathematicalSoftware,1996,22(4):469—483.
[13]IMAI H,IRI M. Polygonal approximations of a curve[J]. Compu-tational Morphology,2014,6(1):71—86.
[14]李仁忠,杨曼,刘阳阳,等.一种散乱点云的均匀精简算法[J].光学学报,2017,37(7):89—97.LI R Z,YANG M,LIU Y Y,et al. An uniform simplification algo-rithm for scattered point cloud[J]. Acta Optica Sinica,2017,37(7):89—97.(In Chinese)
[15] A C++library for linear algebra and geometry manipulation forcomputer graphics[EB/OL]. https://github.com/juj/MathGeoLib.2017 March.
[16] GAMMA GROUP,2008. 3D meshes research database.[EB/OL].https://www-roc.inria.fr/gamma/gamma/download/download.php.