基于三维凸包计算凸多面体Minkowski和算法

赵 强，郭希娟（燕山大学信息科学与工程学院，河北秦皇岛066004）

基于三维凸包计算凸多面体Minkowski和算法

赵 强，郭希娟∗
（燕山大学信息科学与工程学院，河北秦皇岛066004）

摘 要：传统的Minkowski和算法在计算实际物体间的精确的碰撞干涉时，很难直接获取运算所需的数据，进而需要进行大量的数据预处理。为了提高运算速度，减少数据处理量，本文设计了一种新的三维凸包计算方法，通过空间两凸多面体外表的点云信息直接计算其Minkowski和，用计算得到的凸包的面集表示Minkowski和的边界信息。然后，给出详细的算法描述和复杂度分析，并通过对比分析实验数据，验证了该算法的有效性。

关键词：凸包；Minkowski和；凸多面体；三维点云

0　引言

自从德国数学家Herman Minkowski定义向量空间中两个集合中元素的位置向量和为Minkowski和的概念后，Minkowski和算法成为计算几何研究领域中的一个重要分支，在理论分析和实际应用方面有着重要的意义。对于空间中两个凸多面体，Minkowski和是一种研究其相对位置关系的重要工具，如今该方法已经被应用到精确的碰撞检测算法之中［1］。

国内外学者提出的空间凸多面体Minkowski和计算方法主要有4类：基于卷积的算法［2］、基于倾斜图的算法［3⁃4］、基于平面投影叠置的算法［5⁃7］和基于贡献点的算法［8⁃9］。这些算法的主要目的是找出Minkowski和的边界值并表示［10］。Ghosh［3］最早提出通过求两个多面体倾斜图的边界来表示Minkowski和，但计算十分复杂，算法实现困难。Dan Halperin［6］使用立方体高斯映射计算三维空间内凸多面体的Minkowski和，把三维空间内的凸多面体映射到立方体的6个平面上，计算出六对平面映射的叠置即为多面体的Minkowski和。之后，Guo Xijuan［7，10］将空间凸多面体映射到正四面体上，提高了这一算法的效率。

已有方法理论设计复杂，实际计算的时间复杂度也较高，更重要的是这些算法都需要空间凸多面体的顶点、点边关系和点面关系的信息。在实际算例中，计算机更容易获取目标物体的点云信息，而已有算法必须先对点云进行表面重建［11］等工作后，再提取出多面体的顶点、边、面信息后进行计算。这时，针对物体的点云信息使用凸包的方法，更加直接简单。Wu Yanyan［4］曾对基于凸包的Minkowski和算法和基于倾斜图的Minkowski和算法进行讨论。利用凸包计算Minkowski和的主要难点在于如何快速计算出三维点集的凸包和如何用凸包结果表示Minkowski和的边界信息。Mark de Berg［12］在其书中给出了二维和三维凸包计算的几何理论和算法设计，同时也表明了其凸包算法较高的复杂度仍可以进行优化。目前已有一些三维凸包改进方法［13⁃14］改进了最初的凸包计算方法，提高了凸包的计算速度，证明了提高三维凸包算法计算速度的可行性，但这些方法仅计算了离散点云的凸包，而没有给出可以表示Minkowski和边界的方法。

本文提出一种新的面包裹方法来计算凸包，同时计算出Minkowski和与用来表示Minkowski和边界的面集。文中从理论上阐述二维和三维情况下的凸包计算方法和Minkowski和边界的表示方法，给出算法并分析算法的复杂度；最后通过本文算法与传统算法实验数据间的对比分析，验证了该算法的有效性。

1　凸包表示凸多面体的Minkowski和

1.1基本定义

定义1 在欧几里德三维空间中，由若干平面多边形围成的封闭连通的空间区域称为多面体，从多面体上任取一个面，多面体的所有顶点都在这个面上或面的一侧，则称该多面体为凸多面体。

定义2 在欧几里德三维空间内，假设P和Q为两个封闭的多面体，那么P和Q的Minkowski和为多面体M＝P⊕Q＝｛p＋q｜p∈P，q∈Q｝［12］，其中p和q分别属于多面体P和Q的点，p＋q为位置矢量p和q的矢量和。

定义3 包含三维点集的所有凸集的公共交集，称为三维点集的凸包［12］。

1.2二维凸包与Minkowski和

两个凸多边形的Minkowski和是其中一个凸多边形上所有点沿着另一个凸多边形上所有点和原点构成的向量进行平移后形成的新凸多边形，也就是一个凸多边形的所有顶点沿着另一个凸多边形的棱进行平移之后围成的新凸多边形。而根据定义2，Minkowski和是两个凸多面体中所有点矢量和的集合，在二维情况下，表示如图1。

图1　二维空间中凸包表示Minkowski和示意图Fig.1　Schematic diagram of Minkowski sum in convex hull representation in two dimensional space

由图1可以看出，在二维平面中，点集P｛x，y，z｝中的元素分别沿着OA，OB，OC，OD向量平移之后，形成新的点集M｛xa，xb，xc，xd，ya，yb，yc，yd，za，zb，zc，zd｝，点集M就是点集P和点集Q｛a， b，c，d｝的Minkowski和。其中，点集N｛xa，xd，ya，yc，zc，zb｝形成一个包围所有其它点的新点集，这个点集N既是点集M的一个凸包，也是包含了所要描述Minkowski和边界的端点。

因此，只要计算出一个Minkowski和的凸包，就得到了Minkowski和边界值的表示方法。在二维空间中计算凸包即计算包含平面上所有点的最小凸多边形，类似的，在三维空间中，则是求一个包含所有点的最小凸多面体。

1.3三维凸包方法建立Minkowski和边界

根据定义2，三维空间中，两个凸多面体的Minkowski和是这两个凸多面体点集的矢量和所构成的新点集，同时，Minkowski和边界则是包含所有点的最小凸多面体的面。那么，三维空间中求Minkowski和的问题就是求解最小凸多面体外表面面集的问题。

为了表示凸多面体外表面面集，设计一种凸多面体外表面表示方法，如图2所示。图中凸多面体的任意一个面都是由一个或多个三角面构成，每个三角面的顶点按照逆时针排序构成3条有序边。不难发现，图中任意一个三角面的先后两边向量叉乘和多面体表面的外法向量同向。例如图中△BCC1和△BC1B1，存在向量BC1×C1B1和向量C1B×BC均与面BCC1B1的外法向量同向。依据此性质设计数据结构，如图3所示，其中边的信息是具有方向性的，而面的信息中存储了面的任意一个外法向量。

图2　凸多面体点、边、面关系图Fig.2　Diagram of convex polyhedron point，edge，face

通过点云模型直接获得Minkowski和边界特征的具体算法过程如下：

1）从外部设备获取凸多面体A和凸多面体B的点云信息，并根据定义2计算出Minkowski和的点集信息，以此作为计算其边界的输入量。

2）根据定义1，只要找到点云中3个点所构成的面，并且点云中其余点均在这个面的一侧，那么这个面就是Minkowski和的一个边界面。这个面的构造过程如图4（a）所示。首先，根据点云中所有点的z值坐标排序，找到极小值点p，显然p点是凸包上一点，构造一辅助点q与p点具有相同的z值，易知q点在凸包外。过pq做与平面XOY平行的面S1，发现其余点均在S1的上方。然后，求出点云的中心点（均值点），面S1以pq为轴，向点云中心点的方向旋转，碰到的第一个点记为p1，并得到过pp1的面S2。再以pp1为轴，向中心点旋转面S2，得到点p2。获得的面PP1P2就是Minkowski的一个边界面，其余点均在这个面的一侧。

图3　数据结构图Fig.3　Diagram of data structure

图4　Minkowski和边界面建立示意图Fig.4　Diagram of boundary establishment of Minkowski sum

3）根据得到的面PP1P2（逆时针排序，确保面外法向量与中心点反向），分别以其3条边pp1，p1p2，p2p为轴绘制平面并向中心点方向包裹，会得到p3，p4，p53个点。此时得到3个新的面，并以得到的新边为轴重复执行上述过程，直到所得到的面相互连接成封闭的凸多面体。

4）在计算过程中，为了降低计算量，需要加上约束条件来进行动态的冗余点排除。当每次得到一个新点之后，连接该点与最初三角面PP1P2形成四面体，删除点云中在该四面体中的点。当每次得到一条新边之后，判断是否存在与该边反向的边，若存在，证明两面连接封闭，停止以该边为轴的运算。当每次得到一个新面之后，删除点云中在该面上的点（面的顶点除外）。

2　算法描述及分析

根据上述理论推导，基于三维凸包的Minkowski和算法描述如下：

算法第一步需要寻找初始点集的极值点，因此需要遍历所有点，其消耗时间为O（n），第二步中构造Minkowski和的第一个边界面需要遍历两次所有点，所以时间消耗为O（n＋n），即O（n）。本算法的主要时间都消耗在第三步上。设总共有n个输入点，最终得到的面集中有f个面，s条边和r个顶点。那么根据欧拉定理有r＋f－s＝2。根据文献［16］可知，如果有r个点，那么生成面的最大数目为f＝O（r）。所以，步骤三中，最差情况是输入点全是顶点，边栈含有n＋f－2个元素。而每条边都需要遍历全部顶点n，复杂度为O（2n×n），即O（n2）。最佳情况是仅有r个顶点，并且每次边栈中仅有一组边，复杂度为O（r）。而多数时间入栈边迭代总保持lgs条，所以复杂度一般情况下为O（nlg2r），即O（nlgr）。

3　实验与对比分析

本文在相同的PC机上使用VS2010集成环境，选取文献［15］中算法作为传统Minkowski和算法和本文算法进行对比实验，并针对本文的凸包算法部分分别与文献［13⁃14］进行比较。实验环境：Core Duo E7500 CPU；2GB内存；Windows XP操作系统。实验数据：4、6、18、20、80、180、320、960面体的数据信息，其中的18面体为不规则凸多面体。选取任意两个凸多面体进行计算，挑选具有特征性的5组实验数据绘制表1如下。需要特别说明的是，传统算法的输入信息需要将点云信息处理为具有点面关系的数据（即先要根据点云信息进行表面重建，进而得到点边、点面关系数据），在计算时间上分为表面重建时间t1和Minkowski和计算时间t2。

表1　传统Minkowski和算法与本文算法的数据对比表Tab.1　Data comparison of the traditional Minkowski sum algorithm with the proposed algorithm

由表1可知，首先，传统的Minkowski和计算方法所需要的输入数据比较苛刻，既要求输入多面体的顶点坐标又需要多面体的点面关系，这些数据无法直接从外部设备获取；本文算法只需要凸多面体表面点的信息，而这些信息包含在物体的点云数据中。其次，若以相同的点云数据作为输入，传统算法需要先进行表面重建，得到点面与点边关系后才可以进行Minkowski和运算，大量的时间被用于表面重建过程中，总的运算时间明显大于本文算法所需时间。同时，传统算法在计算两相同物体的Minkowski和时，速度明显变慢；而本文算法速度只与输入点云的数目有关。最后，本文算法除了运算速度有大幅度提升外，最终得到的面集信息即Minkowski和的边界信息也与传统算法一致。

为了更好的说明本文算法的优势，结合本文实验数据和文献［15］的实验数据绘制凸多面体点数与程序运行时间的关系图。图5～6中，横坐标表示输入的点云数目，纵坐标表示程序运行时间。其中，传统Minkowski和算法时间t是表面重建时间和计算Minkowski和时间的和。

从图5中可以看出，本文算法与传统算法的运算时间均与点数成正比，而在处理点数较少的多面体时，本文算法速度显著提高；当计算两个相同或相似多面体时，传统算法运算时间出现波动，时间明显增加。针对本文采用的凸包算法，绘制本文实验数据与文献［13⁃14］中的数据，比较分析本文凸包算法的优劣。

图5　Minkowski和算法运算时间对比图Fig.5　Comparison chart of running time of Minkowski sum algorithm

图6　凸包算法运行时间对比图Fig.6　Comparison chart of running time of convex hull algorithm

图6中，本文凸包算法与文献［13］的计算时间几乎相同，但比文献［14］运算略慢。说明本文的凸包方法达到了凸包算法的正常运算速度，但仍存在优化和提高计算速度的可能性。为了更直观的证明本文算法的正确性，用传统算法和本文算法分别对多面体与球体、锥体与球体进行Minkowski和计算，并用计算机仿真，效果如图7～8所示。

由图7～8可以看出对于任意两个凸多面体，本文算法都可以得到和传统算法一样的结果，进一步证明了本文算法的正确性与可行性。观察两组仿真结果发现，本文算法仅与输入多面体面的点集相关，而传统算法则需要多面体的点、边、面关系数据，本文算法虽然输入数据简单，但很好的表现了计算结果的每个边界值，对于形状相似的凸多面体计算效果更佳。

图7　多面体与球体计算效果图Fig.7　Calculation effect chart of the polyhedron and the sphere

图8　锥体与球体计算效果图Fig.8 Calculation effect chart of the cone and the sphere

4　结论

1）给出了基于三维凸包的两个凸多面体Minkowski和算法的构造方法；

2）与传统算法相比，本文算法可以直接利用点云信息进行Minkowski和计算，算法设计简单；

3）理论分析了算法的复杂度，并通过对比实验数据，证明本文算法执行效率更高。

参考文献

［1］Geng Qingjia Guo Xijuan Zhang Jianfei et al.An efficient collision detection algorithm of convex polygons based on Minkowski sum J .ICIC Express Letters 2013 7 2 461⁃464.

［2］Basch J Guibas L J Ramkumar G D et al.Polyhedral tracings and their convolution C //Proceedings of 2nd Workshop on Algorithmic Foundations of Robotics A.K.Peters Wellesley 1996 171⁃184.

［3］Pijush K Ghosh.A unified computation framework for the Mikowski operations J .Computers＆Graphics 1993 17 4 357⁃378.

［4］Wu Yanyan Shah J J Davidson J K.Improvements to algorithms for computing the Minkowski Sum of 3⁃polytopes J .Computer⁃Aided Design 2003 35 13 1181⁃1192.

［5］Zhang Jianfei Guo Xijuan.Redundant filter⁃based efficient Mink⁃woski sum computation of polyhedral J .ICIC Express Letters 2014 8 10 2939⁃2944.

［6］Fogel Efi Halperin Dan.Exact and efficient construction of Minkowski Sums of convex polyhedral with applications J .Com⁃puter⁃Aided Design 2007 39 11 929⁃940.

［7］Geng Qingjia Guo Xijuan Zhang Ya.Research on exact Minkowski sum algorithm of convex polyhedron based on direct mapping C //Advanced Materials Research Wuhan China 2011 377⁃380.

［8］Barki Hichem Denis Florence Dupont Florent.Contributing vertices⁃based Minkowski sum computation of convex polyhedral J .Computer⁃Aided Design 2009 41 7 525⁃538.

［9］Weibel Christophe.Maximal f⁃vectors of Minkowski sums of large numbers of polytopes J .Discrete＆Computational Geometry 2012 47 3 519⁃537.

［10］Zhang Jianfei Guo Xijuan Geng Qingjia.Minkowski sum modeling of polyhedral based on VRML J .ICIC Express Letters 2013 7 2 455⁃460.

［11］Nurunnabi Abdul West Geoff Belton David.Outlier detection and robust normal⁃curvature estimation in mobile laser scanning 3D point cloud data J .Original Research Article Pattern Recognition 2015 48 4 1404⁃1419.

［12］Mark de Berg Otfried Cheong Marc van Kreveld et al.Computa⁃tional geometry algorithms and applications M .Third Edition.Hei⁃delberg Springer⁃Verlag Berlin 2008 243⁃257.

［13］Igarashi Yuki Suzuki Hiromasa.Cover geometry design using mul⁃tiple convex hulls J .Computer⁃Aided Design 2011 43 9 1154⁃1162.

［14］Stein Ayal Geva Eran El⁃Sana Jihad.CudaHull Fast parallel 3D convex hull on the GPU J .Computers＆Graphics 2012 36 4 265⁃271.

［15］Zhang Buying Guo Xijuan Geng Qingjia et al.A new algorithm for computing exact Minkowski sum of convex polyhedral J .Ad⁃vances in Information Sciences and Service Sciences 2013 5 6 382⁃390.

［16］Klee V.Convex Polytopes and Linear Programming C //Proc of the IBM Scientific Computing Sympos Combinatorial Problems Yorktown Heights New York 1966 123⁃158.

Minkowski sum algorithm of convex polyhedron based on three⁃dimensional convex hull

ZHAO Qiang，GUO Xi⁃juan
（School of Information Science and Engineering，Yanshan University，Qinhuangdao，Hebei 066004，China）

Abstract：In the calculation of the exact collision detection between the actual object，the traditional Minkowski sum algorithm are dif⁃ficult to directly obtain data required for operation，so there needs for large amounts of data pre⁃processing.In order to improve the computing speed，reduce the amount of data processing，a new calculation method of 3D convex hull is designed and used to calculate the Minkowski sum of two spatial convex polyhedrons directly through their point cloud information.And the Minkowski sum boundary information is represented by the calculated results of convex hull face set.A detailed description of the algorithm is given and the complexity of the algorithm is analyzed.The results show that the algorithm is effectiveness through comparing the experimental data.

Key words：convex hull；Minkowski sum；convex polyhedron；three⁃dimensional point cloud

作者简介：赵强（1987⁃），男，山西大同人，博士研究生，主要研究方向为碰撞检测、图像处理；∗通信作者：郭希娟（1959⁃），女，吉林舒兰人，博士，教授，博士生导师，主要研究方向为机器人路径规划、机构性能分析、图像处理等，Email：xjguo＠ysu.edu.cn。

基金项目：国家自然科学基金资助项目（51175446）

收稿日期：2014⁃12⁃09

文章编号：1007⁃791X（2015）02⁃0152⁃06

DOI：10.3969/j.issn.1007⁃791X.2015.02.009

文献标识码：A

中图分类号：TP399