邵 寧 張德珍

（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 大連 116026）

1 引言

凸包是計算幾何中非常重要的幾何結(jié)構(gòu)，同時也是得到廣泛研究的問題之一。模式識別，聚類分析，碰撞檢測等研究領(lǐng)域和行業(yè)都具重大的應(yīng)用價值。于此同時，非幾何的問題往往可以通過提取分析并簡化為抽象的幾何概念問題的求解。這些幾何結(jié)構(gòu)在科學(xué)研究和工程實踐中有著非常廣泛的應(yīng)用［1］。

三維的凸包是指包含所有輸入點的最小凸包［2］。許多有關(guān)三維凸包的算法，比如，卷包裹算法（gift wrapping）［3］，是最早處理三維凸包的算法之一。該算法使個平面持續(xù)的圍繞直邊旋轉(zhuǎn)，尋找出構(gòu)成最終凸包的所有小平面。三維空間點集呈隨機分布時，它能夠取得較好的時間效果。分治算法（Divide-and-Conquer）［4］，將三維子凸包連接成完整的三維凸包。具體是結(jié)合Gift-Wrapping 查詢式的角度合并三維的凸包。其他算法還有隨機增量算法［5］和QuickHull算法［6］等。目前，由于模型趨向于復(fù)雜化，精細(xì)化的設(shè)計，其點集規(guī)模和片面數(shù)增多導(dǎo)致構(gòu)造凸包的時間也隨之增多，超出合理的時間范圍。單純地從串行角度進(jìn)行凸包構(gòu)建無法滿足人們對快速構(gòu)造時間性能的要求。

隨著計算機的硬件和軟件的不斷更迭發(fā)展，不論是二維空間還是三維空間，凸包的計算方法迎來了新的機遇。從原先傳統(tǒng)化的串行數(shù)據(jù)處理方式，轉(zhuǎn)變成與GPU 大規(guī)模并行處理方法相結(jié)合的方式。20 世紀(jì)80 年代，由于隨機存取并行機器（PRAM）與串行模型相類似，大多數(shù)研究者使用的此模型設(shè)計算法［7～8］。雖然這些并行算法可以有效的構(gòu)造凸包，但是由于基于PRAM 模型算法是依賴于共享內(nèi)存。現(xiàn)今，NVIDIA 全新的并行計算體系架構(gòu)CUDA 依靠物理計算上的優(yōu)勢將GPU 作為并行計算的設(shè)備，于此同時科研人員的研究方式逐漸向并行計算方面傾斜。Srikanth 等［9］與Srungarapu等［10］利用并行計算對QuickHull 算法的二維凸包問題求解過程進(jìn)行加速，降低處理器間通信成本。Gao 等研究人員［11］提出gHull 算法，運用泰森多邊形初步求解出六面體內(nèi)的凸多面體，最后運用Splaying 算法對凸多面體再次最終形成完整凸包。Gang［12］根據(jù)原始的輸入點集狀態(tài)和多角度旋轉(zhuǎn)后點集的狀態(tài)，確定邊界極值點。以此極值點創(chuàng)建凸多面體；最后內(nèi)部點被剔除形成凸包。Liu［13］等提出了新的三維凸包算法，該算法模擬人們視覺注意過程，以點集粗略分布的重心為中心劃分出初始凸包部分，然后再按邊界判斷點是否為凸包定點，這用方式也為以后的算法優(yōu)化提供新的思路，使得凸包算法不僅僅局限于迭代式構(gòu)建。Phan［14］等依據(jù)基于定向曲線方法的思想提出了新的凸包算法，其性能優(yōu)于傳統(tǒng)的卷包裹算法。

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

2 三維快速凸包算法

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

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

集合C的凸包是能夠包含C的最小的凸集。

性質(zhì)1空間中給定點集凸包是唯一的，且凸包頂點是給定點集中的點［15］。

性質(zhì)2極值點必為凸包的頂點中的點［16］。

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

構(gòu)建凸包為兩方面。首先凸包頂點占據(jù)點集的小部分，大部分的離散點都聚集于凸包的內(nèi)部，所以一般情況下要快速構(gòu)建凸包，盡可能地快速剔除內(nèi)部頂點從而提高算法效率，降低時間損耗。另一方面考慮存儲凸包的數(shù)據(jù)結(jié)構(gòu)，不同情況下選擇合適的存儲結(jié)構(gòu)或者處理過程，同樣加快構(gòu)建凸包的速度。

2.2 三維凸包算法簡介

考慮到凸包計算的并行性，以凸包分治法和隨機增量法為主。它們的共同特點是算法思想易于分解，可以形成并行處理模式。但是由于分治法需要使用增量的方式構(gòu)造子集凸包且將子凸包以卷包裹法完成合并構(gòu)成新的新的凸包，這部分雖然可以按照并行的任務(wù)分割，但是這一過程存儲數(shù)據(jù)結(jié)構(gòu)較代碼實現(xiàn)較為復(fù)雜且數(shù)據(jù)量較少的情況下效果并不明顯。而隨機增量法則不受此限制，在構(gòu)建初始化凸多面體后按照步驟開始迭代，直至所有點集都處理完畢。計算任務(wù)相互獨立，耦合性較低使得算法可以充分并行展開。

2.3 三維凸包算法簡介

Barber［6］等提出了快速凸包算法（Quickhull），此算法是以隨機增量算法為基礎(chǔ)上進(jìn)行改進(jìn)的算法，能夠在三維和高維空間上應(yīng)用。其基本思想是大量離散點集中排除一部分內(nèi)部點。凡是極值點都是凸包的頂點，并以此特性逐次排除剩余非凸包頂點，最終形成凸包。相較于其他構(gòu)建三維凸包算法，此算法初始階段大幅度的排除非凸包點而不是逐個或者小部分排除。通過實驗證明快速凸包算法比隨機增量算法的速度更快，需要的存儲空間更小，算法的平均復(fù)雜度為O（nlogn），最壞情況下的復(fù)雜度為O（n2）［6］。算法流程如下。

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

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

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

Step4：初始化可見面集V。

Step5：可見面集V中每個面中的未被訪問過的鄰居面N，如果點p 在面N 的上方，把N 加到集合V中?？梢娒婕疺 的初始情況只有一個面F，從面F向周圍的面遍歷，將所有對點p 可見的面保存在可見集V中。

Step6：把可見面集合V中每個面的外部點集匯總到一個點集L中。

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

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

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

圖1 通過可見面的極值點構(gòu)造凸多面體

與平面點集相比較，三維空間構(gòu)造凸包構(gòu)造過程和計算較為復(fù)雜。隨著點集規(guī)模的增多，計算量也逐步增多而且需考慮浮點運算能力。

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

3.1 CUDA并行設(shè)計架構(gòu)

近些年，圖形處理器的性能提升以及計算圖形學(xué)的深入研究，關(guān)于凸包算法的研究也逐步深入。不僅僅是為求構(gòu)造凸包過程的精確性和改進(jìn)復(fù)雜度，而且由于數(shù)據(jù)模型的點集規(guī)模擴大，時間性能逐步受到重視。CUDA?是一種由NVIDIA 推出的通用并行計算架構(gòu)，該架構(gòu)使GPU 能夠解決復(fù)雜的計算問題。 它包含了CUDA 指令集架構(gòu)（ISA）以及GPU內(nèi)部的并行計算引擎［17］。

GPU 硬件架構(gòu)是由若干個SM（streaming multiproecssor），存儲控制器，各級緩存，PCI-E接口等組成。CUDA 編程模型中，每一個線程（thread）作為線程塊的一部分，單獨擁有一個私有的本地存儲器，并以block 為單位分配到SM 上。每32 個thread為一組形成一個warp，warp 是SM 中調(diào)度和執(zhí)行的基本單位［18］同一個warp 中的thread以不同的數(shù)據(jù)，執(zhí)行同樣的指令。這種執(zhí)行特性有效提高了程序處理效率，理論上在較多數(shù)據(jù)時能夠獲得很好的加速性能。

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

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

具體描述如下：

Step1：在CPU 端讀入模型點集數(shù)據(jù)并存儲在數(shù)組上，判斷點集是否是線性。如果不是則在GPU上開辟相同大小空間并分配模型各點在三維空間中的浮點坐標(biāo)數(shù)據(jù)，以及初始化其他隊列向量。

Step2：在 主 機 端 調(diào) 用Init_tetr_kernel（grid，thread）函數(shù)。求出當(dāng)前點集中四個極值點。將極值點拷貝回主機端。

Step3：將拷貝的回的點添加到初始化的凸包向量中。同時更新面的信息。再將剩余點傳輸?shù)紾PU 端，調(diào)用segmentation_kernel（grid，thread）核函數(shù)按照面分割點集。

Step4：分割好的點集傳送回主機端，如果還有未處理的點則進(jìn)行如下操作，更新點和面的數(shù)據(jù)。將相應(yīng)面的歸屬點傳送到設(shè)備端，distance_kernel（grid，thread）函數(shù)求出平面極值點，同時進(jìn)行排序，數(shù)據(jù)拷貝回主機端。

Step5：根據(jù)面數(shù)結(jié)構(gòu)的信息，找出可見面和地平線。點集和平面信息傳送到設(shè)備端，判別并標(biāo)記內(nèi)部點從而方便剔除。將相關(guān)數(shù)據(jù)拷貝回主機端。

Step6：重復(fù)以上步驟，直至所有的點全部處理。

Step7：將最終凸包結(jié)果導(dǎo)出，過程結(jié)束。

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

根據(jù)算法的內(nèi)容和結(jié)構(gòu)，剔除凸包的內(nèi)部點的計算是相互獨立，并行執(zhí)行。這一部分計算占計算總量的大部分。利用CUDA 的特性能夠充分發(fā)揮運行速度的優(yōu)勢。另外一方面判斷點是否屬于平面內(nèi)這一過程中可以采用CUDA 編程模型中的向量內(nèi)積的前綴求和操作或者執(zhí)行原子加法的操作。采用低線程歸約可以最小化執(zhí)行warp 數(shù)量數(shù)據(jù)對齊訪問和避免bank沖突。

凸包的點集主要取決于凸包邊界附近點，凸包內(nèi)部點則不會對凸包產(chǎn)生任何影響。快速凸包算法其核心思想是通過對點集篩選逐步刪除凸包內(nèi)部點。其獨立性質(zhì)這也為算法的并行性提供了可能性。

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

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

圖2 快速凸包算法CUDA流程示意圖

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

算法的數(shù)據(jù)結(jié)構(gòu)是基于半邊表的數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，記錄邊和三角面相的鄰臨面的拓?fù)湫畔ⅰ＿@種類型的數(shù)據(jù)結(jié)構(gòu)允許任何類型的相鄰網(wǎng)格元素上進(jìn)行快速查詢以及修改。

點結(jié)構(gòu)：記錄每個點的三維空間坐標(biāo)值。

邊結(jié)構(gòu)：記錄邊所連接的兩個端點和兩個鄰接面。

面結(jié)構(gòu)：記錄小平面的三個端點，以及三個鄰接面，外部點集，確定可見面集過程中的指示標(biāo)志。待處理的平面列表位置信息。

在分配設(shè)備內(nèi)存的基礎(chǔ)上，將模型數(shù)據(jù)從主機端傳入設(shè)備端，通過核函數(shù)使得數(shù)據(jù)可以在設(shè)備端進(jìn)行相應(yīng)的處理。利用多線程處理器完成一系列的數(shù)據(jù)操作。在此期間數(shù)據(jù)在主機端和設(shè)備端之間進(jìn)行傳輸。CUDA 架構(gòu)中，CPU 不直接訪問設(shè)備內(nèi)存，GPU 不能直接訪問主機內(nèi)存，因此數(shù)據(jù)傳遞需要通過調(diào)用特定函數(shù)對點集數(shù)據(jù)進(jìn)行傳遞。同時盡量減少CPU 與GPU 之間的切換，執(zhí)行過程中所有有關(guān)內(nèi)部點和外部點，距離的存儲是通過更改索引值或者移動至末尾來進(jìn)行操作和維護(hù)。

在設(shè)備端，調(diào)用kernel（）函數(shù)完成計算量多的并行計算部分。線程網(wǎng)格與線程塊的維度依據(jù)點集數(shù)據(jù)和圖形處理器所能夠承載的數(shù)目進(jìn)行分配（點集數(shù)據(jù)+線程塊數(shù)量-2）/線程塊數(shù)量。每一個線程塊處理以相同的操作來處理部分點集。由于數(shù)據(jù)存儲于全局變量中，存取過程耗時較長，因此利用共享內(nèi)存實現(xiàn)線程之間的塊內(nèi)通信減少通信訪問開銷，訪存效率得到明顯的改善。

計算相對小平面的極值點時，先將點按照小平面順序進(jìn)行排序，然后再根據(jù)距離遠(yuǎn)選取。這一過程本文選取了CUDA Thrust 函數(shù)庫完成操作。Thrust 提供了豐富的數(shù)據(jù)并行算法，例如掃描、排序、歸約等，可以簡單快捷地構(gòu)成復(fù)雜算法，并使得代碼獲得更高的可讀性。Thrust 的排序是以基數(shù)排序為基礎(chǔ)，將點到平面的距離數(shù)組分為若干組，每組選出最小值一次移動到數(shù)列列尾；依次類推，將配需結(jié)果合并得到最終結(jié)果。這里利用了歸約求和的思想。其思想是對于一個輸入數(shù)組執(zhí)行加法運算，產(chǎn)生更小的結(jié)果數(shù)據(jù)，將數(shù)據(jù)按照規(guī)則合并。對于N個輸入數(shù)據(jù)和操作符，歸約可以表示為

如圖3所示。

圖3 歸約運算步驟

每次歸約運算位于目前所有線程的一半線程，循環(huán)執(zhí)行，最終在初始線程中得到最終用結(jié)果。這種歸約方式改進(jìn)了數(shù)據(jù)訪問不對齊，多warp 線程執(zhí)行計算的問題。計算大量離散點集情況下降低執(zhí)行的消耗時間，有效地排除凸包內(nèi)部點。另外，快速凸包算法初期在處理點集時，通過初始化四面體排除點集中大部分內(nèi)部點。而后隨著凸包的小平面增多以及剩余空間的減少，計算距離和判斷點位置的量隨之增多且需要多次重復(fù)讀取。這也是實現(xiàn)該算法并行性的原因。

4 實驗結(jié)果及分析

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

實驗設(shè)備參數(shù)CPU 采用Inter（R）Core（TM）i7-4810MQ 處理器，主頻為2.80GHz。GPU 則為可支持CUDA 的NVIDIA Quadro k3100M，計算能力3.0，其架構(gòu)為Kelper 架構(gòu)。4GB 的顯存，顯存位寬256-bit。擁有15 個SM 流處理器，每個65536 個寄存器，線程塊的最大線程數(shù)為1024。實驗選取的三維模型為斯坦福大學(xué)大型模型幾何庫和其他三維 幾 何 模 型，分 別 為3Dman，3DBull，3Dbunny，3DGragon，數(shù)據(jù)量依次增多。

本文實驗整體流程分為兩部分。首先算法模塊讀取實驗的模型數(shù)據(jù)，然后分別按照串行和并行的方式實現(xiàn)快速凸包算法的。求取的凸包的最終結(jié)果通過OpenGL圖形庫進(jìn)行模型展示，如圖4。

圖4 實驗的三維模型與構(gòu)造后的凸包

基于CUDA 的快速匹配算法在CPU 和GPU 上運行試驗效果如圖5。

表1 快速凸包算法在CPU與GPU性能表現(xiàn)

分別選取不同數(shù)據(jù)量的模型完成構(gòu)建凸包操作，實驗點集數(shù)據(jù)量少的情況下CPU串行所需的時間比GPU 并行的時間短很多。這是因為當(dāng)數(shù)據(jù)從主機端傳送到設(shè)備端時，相對于CPU 內(nèi)部數(shù)據(jù)處理，異構(gòu)系統(tǒng)在加載數(shù)據(jù)過程中往往耗費更多的時間，跟自身通信帶寬有關(guān)。而當(dāng)數(shù)據(jù)規(guī)模較大時，并行任務(wù)的計算量較多，傳輸數(shù)據(jù)過程消耗雖然沒有減少但是較好隱藏時間延遲。

從表1 可以看出不同的點集規(guī)模構(gòu)造凸包所消耗的時間隨著點集的增多而增多。CPU 平臺與GPU 的平臺上運行加速比隨之增多。數(shù)據(jù)量為之前的兩倍，加速比能夠達(dá)到相同的倍數(shù)，甚至是更多。

圖5 不同數(shù)據(jù)分別在CPU和GPU上的時間運行的時間

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

5 結(jié)語

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