快速凸包并行設計與研究

邵　寧，張德珍

（大連海事大學，遼寧 大連　116026）

0　引言

凸包是計算幾何中非常重要的幾何結構，非幾何的問題往往也可以抽象為幾何概念并求解。因此凸包幾何結構在科學研究和工程實踐中有著非常廣泛的應用[1-2]。三維的凸包是指包含所有輸入點的最小凸包[3]。許多有關三維凸包的算法，比如，卷包裹算法[4]，是最早處理三維凸包的算法之一，分治算法算法[5]，快包算法[6]等。隨著凸包的點集規模逐步增多，耗費的時間增多，無法滿足人們對構造凸包時間的要求。

隨著計算機的硬件和軟件的不斷更迭發展，從原先傳統化的串行數據處理方式，轉變成與GPU大規模并行處理方法相結合的方式。20世紀80年代，由于隨機存取并行機器（PRAM）與串行模型相類似，大多數研究者使用的此模型設計算法。現今，依靠 GPU通用計算能力實現大規模數據處理。Srikanth,等人[7]利用并行計算對快包算法的二維凸包問題求解過程進行加速，降低處理器間通信成本。Gao等研究人員[8]提出gHull算法，運用泰森多邊形初步求解出六面體內的凸多面體，最后運用Splaying算法對凸多面體再次最終形成完整凸包。Gang[9]根據原始的輸入點集狀態和多角度旋轉后點集的狀態，確定邊界極值點。以此極值點創建凸多面體；最后內部點被剔除形成凸包。

本文通過對有關三維凸包的相關文獻的研究，分析快速凸包算法的計算任務，將求解凸包的問題劃分為可并執行的子問題。利用GPU的通用計算能力，對計算量多且可以獨立的部分進行并行的任務設計。選取不同規模點集數據分別以串行和并行的方式計算構造凸包消耗的時間。從而印證快速凸包算法在時間性能上的顯著提高。

1　三維快速凸包算法

1.1　凸包的相關定義

三維的凸包是指包含所有輸入點的最小凸包。其定義為集合C中所有點的凸組合的集合。

集合C的凸包是能夠包含C的最小的凸集。同時也是包含S的所有凸集的交。

性質 1空間中給定點集凸包是唯一的，且凸包頂點是給定點集中的點[10]。

性質2極值點必為凸包的頂點中的點。

凸多面體的構造可以描述為：三維空間條件下，對給定點集中選取若干個非線性頂點組成新的點集。頂點所構成的邊界面包含給定點集且包含自身。此點集可稱為凸包點集。

1.2　三維快速凸包算法

Barber[6]等人提出了快速凸包算法，此算法是以隨機增量算法為基礎上進行改進的算法，能夠在三維和高維空間上應用。相較于其他構建三維凸包算法，此算法初始階段大幅度的排除非凸包點而不是逐個或者小部分排除。通過實驗證明快速凸包算法比隨機增量算法的速度更快，需要的存儲空間更小，算法的平均復雜度為 O(nlogn)，最壞情況下的復雜度為O(n2)[6]。算法流程：

步驟 1：初始化四個頂點構成的四面體。以坐標X軸方向選取正反方向兩個極值點構成線段。然后選取距離線段最遠的點形成平面，再取距離平面最遠的點。這四個極值點構成初始的凸多面體，且極值點為非退化的極值點。

步驟 2：存儲每個面的數據結構。對于四面體的每個面F，遍歷點集，找到所有在面F上方的點，保存面F的外部點集中，每個面結構都記錄有一個外部點集，把外部點集非空的面保存在一個集合中，稱這個集合為待定面集。

步驟3：面F的外部點集中找到與面F距離最遠的點p，并且把點p從面F的外部點集中移除。

步驟4：初始可見面集V，且V中每個面中的未被訪問過的鄰居面N，如果點p在面N的上方，把N加到集合V中。然后把集合V中每個面的外部點集集中在點集L中。

步驟5：集合V中所有可見面的臨界邊，構成一個集合 V。連接點和集合中的邊界邊，創建出新的面，更新新的面的相鄰面。

步驟 6：對于每個新的面 F′，遍歷點集 L，如果對于點集L中未分配的點q，它在F′的上方，則把它添加到面F′的外部點集中。若待定面集Q和可見面集V的交不為空，則從待定面集Q中移除它們的交集。

最后，對于每個新的面F′，若它的外部點集非空，則把它添加到待定面集Q中，進行下次的迭代。

與平面點集相比較，三維空間構造凸包構造過程和計算較為復雜。在構建初始化凸多面體后按照步驟開始迭代，直至所有點集都處理完畢。計算任務相互獨立，耦合性較低使得算法可以充分并行展開。

2　基于CUDA快速凸包算法的實現

2.1　三維快速凸包算法并行性分析

快速凸包算法易于理解，對以上步驟分析可知。步驟1求極值點初始化四面體，步驟2區分各個小平面點集是內部點或者外部點的過程和步驟3求可見面的最遠極值點是可以獨立的部分，耦合性較低。步驟2和步驟3部分所完成的計算任務是全部程序中計算任務中的大部分，耗費時間比較長，尤其是數據規模較大的情況下。以上過程可以高度并行處理，且運用空間幾何方法進行判斷和操作。并由其中大量的計算單元同時對點集進行計算，從而縮短處理時間。

2.2　基于CUDA快速凸包算法的實現

快速凸包算法在并行上可以分為兩個部分。一部分是大量的離散點中按照相應的坐標求取極值點構建初始的四面體。另一部分是將點集按照凸包上的小平面進行分割，然后求取離可見面所對應最遠的距離的極值點。

本文中，利用CUDA并行編程模型隨快速凸包算法進行重構。首先將點集傳輸到設備內存中，其次多線程運用不同的數據執行相同的指令來尋找到點集中的四個極值點，然后將極值點傳回主機端構建初始化四面體，剔除內部點。將剩余的點集重新依照新的小平面進行分配。在分配好的點集中選出距離小平面最遠的極值點，極值點與相應的小平面的邊相連組成新的四面體，并且判斷點是否在凸包外，如果分布于內側則剔除。此四面體與原先凸包結合。進行迭代直至所有的外部點都處理過。整個過程結束。

在設備端，調用核函數完成計算量多的并行計算部分。線程網格與線程塊的維度依據點集數據和圖形處理器所能夠承載的數目進行分配(點集數據+線程塊數量-2)/線程塊數量。實踐過程中線程塊的數目設置為32的倍數。有文獻表明當線程取512時，設備端的占有率實現最大化。合理的對所調用的內核函數線程塊和線程維度分配，大幅度縮短因訪存導致的時間消耗與延遲。每一個線程塊處理以相同的操作來處理部分點集。由于數據存儲于全局變量中，存取過程耗時較長，因此利用共享內存實現線程之間的塊內通信減少通信訪問開銷，訪存效率得到明顯的改善。

計算相對小平面的極值點時，先將點按照小平面順序進行排序，然后再根據距離遠選取。這里利用了歸約求和的思想。其思想是對于一個輸入數組執行加法運算，產生更小的結果數據，將數據按照規則合并。

每次歸約運算位于目前所有線程的一半線程，循環執行，最終在初始線程中得到最終用結果。這種歸約方式改進了數據訪問不對齊，多線程執行計算的問題。計算大量離散點集情況下降低執行的消耗時間，有效的排除凸包內部點。程序優化的另一方面是，通過原子操作保證每個線程互斥地訪問全局存儲或共享存儲上的計算結果，避免并行程序總多個線程同時修改某一變量出現沖突問題。最終將相應平面的極值點從GPU傳回到CPU中以進行接下來的操作。

3　實驗結果及分析

本文基于 CUDA實現計算幾何的快速凸包算法，通過不同點集數據量的復雜幾何模型分別按照串行算法和并行算法進行實驗且對數據分析和對比，如下圖。實驗結果表明利用GPU實現算法能夠將算法速度達到幾倍的加速。輸入點集規模較大時算法加速有著明顯的提高。

實驗設備參數CPU采用Intel i7處理器，GPU為 Quadro k3100M，線程塊的最大線程數為1024。實驗選取的三維模型為斯坦福大學大型模型幾何庫和其他三維幾何模型。

圖1　實驗的三維模型與構造后的凸包Fig.1　3D model and convex hull

表1　快速凸包算法在CPU與GPU性能表現Tab. 1　The performance comparison of quickhull algorithm base on CPU and CUDA

從表中可以看出，數據量較少的的情況下，基于CPU和基于GPU的快速凸包算法時間性能上比較接近。隨著實驗點集數據的增多，對于不同平臺上實驗所消耗的時間差距不斷擴大。三維模型點集數量越多，CPU構建凸包所消耗的時間成線性增長趨勢，而與此同時GPU消耗的時間方面基本持平，時間消耗不明顯。在CUDA上實現快速凸包算法處理的速度遠超過CPU構建凸包的速度。模型點集規模數量較多時，有著明顯的加速效果和優勢。

4　結論

本文在原有快速凸包算法的基礎上，利用GPU并行計算的優勢實現凸包算法速度提升。分別對構建凸包時初始化和求取極值點的過程進行詳細分析和并行設計。實驗結果表明基于GPU的快速凸包算法在數據量過多情況下能夠得到很好的加速效果。