胡志刚 秦启飞

摘    要：针对复杂物体三维点集的建模问题，提出一种基于凸包的最小体积的封闭有向包围盒生成算法.对凸包和其最小体积有向包围盒的关系进行分析，总结了其4种边面接触类型.通过枚举凸包中边的所有可能的组合，唯一确定包围盒的最优方向.实验证明，该算法可以快速生成符合模型体积特征的最小有向包围盒，且拟合效果良好.

关键词：有向包围盒;几何计算;凸包;三维点集;图搜索

中图分类号：TP30                              文献标志码：A

Algorithm for Finding Minimum Volume Oriented

Bounding Boxes Based on Convex Hull

HU Zhigang，QIN Qifei

（School of Software，Central South University，Changsha 410083，China）

Abstract： 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.

Key words： oriented bounding box;computational geometry;convex hull;three-dimensional point set;graph search

物體的包围盒广泛应用于图像处理、模式识别、碰撞检测、模具分型设计和机械控制等领域[1-2].目前应用最广泛的OBB（Oriented Bounding Box，有向包围盒）根据物体本身的几何形状来决定包围盒的大小和方向，可以对原模型进行紧凑的拟合[3].对于给定的三维点集，怎样高效而准确地得到其最小有向包围盒一直是国内外学者关注的问题[4].

一般考虑物体的所有顶点在空间的分布，通过不同的算法找到最佳方向，以确定OBB包围盒的几个轴.主要使用数值和统计优化方法来找到非最优、但在实际使用中足够好的近似值.目前的主流方法是使用主成分分析（PCA）[5]，根据物体表面的顶点，计算特征向量来估计点集中最大扩展的方向，并作为OBB的主轴.这个过程必须使用凸包上的连续集合表示来完成，否则近似值可能是无界差的[5].为了获得接近最优的结果，Barequet 和HarPeled提出一个（1+α）逼近方案[6]，而另一方面，Larsson和 K？覿llberg则提出可以采用预定义的启发式方法来……