基于三維凸包計算凸多面體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