快速凸包并行設(shè)計(jì)與研究

邵　寧，張德珍

（大連海事大學(xué)，遼寧 大連　116026）

0　引言

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

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

本文通過對有關(guān)三維凸包的相關(guān)文獻(xiàn)的研究，分析快速凸包算法的計(jì)算任務(wù)，將求解凸包的問題劃分為可并執(zhí)行的子問題。利用GPU的通用計(jì)算能力，對計(jì)算量多且可以獨(dú)立的部分進(jìn)行并行的任務(wù)設(shè)計(jì)。選取不同規(guī)模點(diǎn)集數(shù)據(jù)分別以串行和并行的方式計(jì)算構(gòu)造凸包消耗的時(shí)間。從而印證快速凸包算法在時(shí)間性能上的顯著提高。

1　三維快速凸包算法

1.1　凸包的相關(guān)定義

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

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

性質(zhì) 1空間中給定點(diǎn)集凸包是唯一的，且凸包頂點(diǎn)是給定點(diǎn)集中的點(diǎn)[10]。

性質(zhì)2極值點(diǎn)必為凸包的頂點(diǎn)中的點(diǎn)。

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

1.2　三維快速凸包算法

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

步驟 1：初始化四個(gè)頂點(diǎn)構(gòu)成的四面體。以坐標(biāo)X軸方向選取正反方向兩個(gè)極值點(diǎn)構(gòu)成線段。然后選取距離線段最遠(yuǎn)的點(diǎn)形成平面，再取距離平面最遠(yuǎn)的點(diǎn)。這四個(gè)極值點(diǎn)構(gòu)成初始的凸多面體，且極值點(diǎn)為非退化的極值點(diǎn)。

步驟 2：存儲(chǔ)每個(gè)面的數(shù)據(jù)結(jié)構(gòu)。對于四面體的每個(gè)面F，遍歷點(diǎn)集，找到所有在面F上方的點(diǎn)，保存面F的外部點(diǎn)集中，每個(gè)面結(jié)構(gòu)都記錄有一個(gè)外部點(diǎn)集，把外部點(diǎn)集非空的面保存在一個(gè)集合中，稱這個(gè)集合為待定面集。

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

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

步驟5：集合V中所有可見面的臨界邊，構(gòu)成一個(gè)集合 V。連接點(diǎn)和集合中的邊界邊，創(chuàng)建出新的面，更新新的面的相鄰面。

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

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

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

2　基于CUDA快速凸包算法的實(shí)現(xiàn)

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

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

2.2　基于CUDA快速凸包算法的實(shí)現(xiàn)

快速凸包算法在并行上可以分為兩個(gè)部分。一部分是大量的離散點(diǎn)中按照相應(yīng)的坐標(biāo)求取極值點(diǎn)構(gòu)建初始的四面體。另一部分是將點(diǎn)集按照凸包上的小平面進(jìn)行分割，然后求取離可見面所對應(yīng)最遠(yuǎn)的距離的極值點(diǎn)。

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

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

計(jì)算相對小平面的極值點(diǎn)時(shí)，先將點(diǎn)按照小平面順序進(jìn)行排序，然后再根據(jù)距離遠(yuǎn)選取。這里利用了歸約求和的思想。其思想是對于一個(gè)輸入數(shù)組執(zhí)行加法運(yùn)算，產(chǎn)生更小的結(jié)果數(shù)據(jù)，將數(shù)據(jù)按照規(guī)則合并。

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

3　實(shí)驗(yàn)結(jié)果及分析

本文基于 CUDA實(shí)現(xiàn)計(jì)算幾何的快速凸包算法，通過不同點(diǎn)集數(shù)據(jù)量的復(fù)雜幾何模型分別按照串行算法和并行算法進(jìn)行實(shí)驗(yàn)且對數(shù)據(jù)分析和對比，如下圖。實(shí)驗(yàn)結(jié)果表明利用GPU實(shí)現(xiàn)算法能夠?qū)⑺惴ㄋ俣冗_(dá)到幾倍的加速。輸入點(diǎn)集規(guī)模較大時(shí)算法加速有著明顯的提高。

實(shí)驗(yàn)設(shè)備參數(shù)CPU采用Intel i7處理器，GPU為 Quadro k3100M，線程塊的最大線程數(shù)為1024。實(shí)驗(yàn)選取的三維模型為斯坦福大學(xué)大型模型幾何庫和其他三維幾何模型。

圖1　實(shí)驗(yàn)的三維模型與構(gòu)造后的凸包Fig.1　3D model and convex hull

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

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

4　結(jié)論

本文在原有快速凸包算法的基礎(chǔ)上，利用GPU并行計(jì)算的優(yōu)勢實(shí)現(xiàn)凸包算法速度提升。分別對構(gòu)建凸包時(shí)初始化和求取極值點(diǎn)的過程進(jìn)行詳細(xì)分析和并行設(shè)計(jì)。實(shí)驗(yàn)結(jié)果表明基于GPU的快速凸包算法在數(shù)據(jù)量過多情況下能夠得到很好的加速效果。