馬東嶺，李銘通，朱悅凱

(山東建筑大學測繪地理信息學院，山東 濟南 250101)

0 引言

傾斜攝影是遙感和測繪領域近年來發(fā)展起來的一項高新技術[1]。 基于傾斜影像生成的實景三維模型已經(jīng)廣泛應用于測繪、 地理信息系統(tǒng)(Geographic Information System，GIS)、環(huán)境應用、城市和土地管理、災害與應急、三維地圖服務和三維導航等領域[2]。 然而，傾斜影像密集匹配的點云非常密集，所生成的模型包含成千萬甚至上億個點，給三維模型的應用帶來極大的不便，因此通常采用“分層分塊”構建多細節(jié)層次(Levels of Detail，LOD)模型的方式處理，即利用裁剪窗口對模型多次裁剪和簡化[3]。 LOD 的裁剪在傾斜攝影三維模型應用中有著重要作用。 目前，常用的基于逐邊裁剪思想的方法使用多個裁剪器進行裁剪，在凸多邊形裁剪中可以準確地獲得想要的多邊形。 然而，該方法涉及編碼計算、求交計算和多邊形三角化3 個方面，因此大量的計算會導致算法時間效率不高。

多邊形裁剪算法是在電腦圖形和圖像處理領域中最為基本、使用最多的算法之一，在實景三維模型裁剪中的應用范圍也越來越廣泛[4]。 Bae 等[5]提出了端點編碼(Cohen–Sutherland)算法，實現(xiàn)了快速檢測完全在裁剪區(qū)域內或外的線段，減少了求交計算數(shù)據(jù)量，但在復雜情況下會進行多次不必要的計算。 基于該編碼思想，Sutherland 等[6]提出的多邊形裁剪(Sutherland－Hodgman)算法使用了分而治之的策略，將裁剪操作分解為裁剪窗口的一條邊裁剪原始多邊形的一條邊，使用多個裁剪器進行裁剪，該方法在凸多邊形裁剪中具有極高的效率與高度的并行性[7]。 而在復雜多邊形裁剪研究中，陳國軍等[8]提出一種可以裁剪凹多邊形、多連通多邊形以及自相交多邊形的裁剪算法，可將復雜多邊形分解為簡單的凸多邊形，并根據(jù)頂點與裁剪窗口拓撲關系裁剪。

裁剪后將會得到由一組有序頂點表示的多邊形，在LOD 裁剪中需要將其分解為三角形集合，并入裁剪后的三角網(wǎng)格結構。 因此，需要對頂點序列進一步三角化，進而構建Mesh 網(wǎng)。 多邊形三角化是代數(shù)拓撲學里最基本的研究方法[9]。 在三角化眾多算法中最常使用的是狄洛尼三角化(Delaunay Triangulation)算法，其遵循“最小角最大”和“空外接圓”規(guī)則，通過有約束三角化生成含有內嵌邊界的三角網(wǎng)格模型。 雖然此方法適于裁剪多邊形的三角化，但存在約束條件繁瑣、運行效率低的問題[10]。相比之下，Eberly[11]提出的耳切三角化算法有著易實現(xiàn)、效率高的特點，其算法思路為找出多邊形的耳朵構造一個三角形，剔除多邊形的頂點數(shù)組中對應頂點，遞歸執(zhí)行以完成裁剪。

多邊形裁剪和三角化算法多是基于中央處理器(Central Processing Unit， CPU)處理，隨著裁剪次數(shù)的增加，其算法的耗時呈線性增長趨勢，計算效率較低。 但同時，多邊形裁剪與三角化均屬于計算密集型任務，并行性高，因此適合并行化加速。 近年來，隨著制程工藝和集成技術的發(fā)展，圖形處理器(Graphic Processing Unit， GPU)的計算能力越來越強大[12]。 為適應傾斜攝影三維模型LOD 快速裁剪的需求，文章利用GPU 的并行計算能力，提出了一種基于統(tǒng)一計算設備架構(Compute Unified Device Architecture，CUDA)的實景三維模型裁剪算法。 其將CPU 算法劃分為大小相同的子任務，以滿足并行編程的需要；再設計了一個多級索引結構，將數(shù)據(jù)映射到CUDA 線程，保證一個線程處理一個三角面，避免讀寫沖突的同時保證線程間負載均衡；在不影響裁剪網(wǎng)格質量的前提下，使用幾種策略提升算法性能，并將GPU 裁剪并行算法應用于LOD 裁剪實驗，以期在保證算法裁剪精度的同時，顯著提高三維模型的裁剪效率。

1 CUDA 并行計算架構

CUDA 是一種操作GPU 計算的硬件和軟件架構，是建立在NVIDIA 的GPUs 上的一個通用并行計算平臺和編程模型[13]。 GPU 由若干個流多處理器(Streaming Multiprocessor，SM)組成，每個SM 由若干個流處理器(Streaming Processor，SP)、存儲器、控制邏輯和少量的其他計算單元組成[14]。 每個SP 都是獨立的運算單元。 CUDA 架構能夠將計算量均衡、靈活地分配到執(zhí)行單元SM 上，適合數(shù)據(jù)并行的計算密集型任務。 GPU 結構如圖1 所示，線程(Thread)是GPU 最小的執(zhí)行單元，大量的線程被組織成線程塊(Block)，若干線程塊又組成整體的線程格(Grid)，同一個線程塊中的線程可以通過共享存儲器以很低的代價進行通信。 CUDA 架構通過將線程塊映射到SM 上實現(xiàn)應用程序的并行計算。 SM通過線程調度器實現(xiàn)任務的分配，每個SM 能夠運行一個或多個線程塊。 根據(jù)線程塊數(shù)目和每個線程塊中線程數(shù)目的不同，線程調度器能夠自動地將一個或多個塊分配到SM 上運行。

圖1 GPU 結構示意圖

2 LOD 裁剪算法原理

當前，LOD 裁剪算法大多基于逐邊裁剪思想，構建若干個六面體作為裁剪窗口逐次裁剪實景三維模型中的空間三角形。 裁剪窗口的6 個四邊形所在平面將空間劃分為27 個子空間，構建6 個裁剪器將裁剪操作分解為裁剪窗口的裁剪面與原始多邊形一條邊的裁剪。 算法主要思路為:(1) 通過編碼值邏輯運算判斷三角面空間位置拓撲類型，減少求交計算的數(shù)據(jù)量；(2) 根據(jù)三角面的空間位置進行裁剪。編碼值由頂點坐標值與對應邊界的差值符號確定，6 位編碼值分別表示裁剪包圍盒的6 個裁剪面。 如果某編碼位的值為1，則代表當前頂點落在了以對應裁剪面劃分相對位置的外部，為0 則處于相對位置的內部。 三角面的空間位置拓撲類型由分區(qū)編碼邏輯運算結果確定。 假設code0、code1、code2 分別表示某三角面的3 個頂點編碼，如果3 個頂點編碼邏輯“或”計算結果為0，則該面位于裁剪包圍盒內；邏輯“與”計算結果不為0，則對應位置為裁剪包圍盒外；不滿足上述條件的即為相交類型。 單層LOD三維裁剪包圍盒如圖2 所示。

圖2 單層LOD 三維裁剪包圍盒示意圖

判斷三角面的空間位置拓撲后，分3 種情況處理:若該面為包含類型，則予以保留；若該面為相離類型，則予以舍棄；若該面為相交類型，則對其進行逐邊裁剪求交計算并輸出裁剪點序列，三角化后寫入裁剪Mesh。 重復上述操作直至遍歷所有三角面后裁剪結束，得到裁剪后Mesh 模型。

3 GPU 并行裁剪計算

由LOD 裁剪算法原理可知，CPU 算法以三角面為裁剪元串行裁剪會產(chǎn)生大量的重復編碼計算，并且重復計算量會隨著Mesh 模型中三角面數(shù)量以及復雜度增加，影響算法時間效率。 為適應傾斜攝影三維模型LOD 快速裁剪需求，文章利用GPU 的并行計算能力，優(yōu)化算法流程，提出了一種基于GPU的實景三維模型裁剪算法。 為了在GPU 上高效地執(zhí)行裁剪計算，每個線程的負載應該在相同的比例上。 由于非相交類型三角面不參與求交計算，假設算法僅用一個kernel 實現(xiàn)，每個線程中分配一個三角面，會導致活躍線程數(shù)減少、GPU 隱藏延遲的能力下降，并且無法解決不必要重復編碼計算問題。因此，將裁剪過程分解為:(1) 計算所有頂點分區(qū)編碼，避免重復編碼計算；(2) 對相交類型三角面逐邊裁剪計算，設計基于面拓撲的多級索引結構，索引重復交點，實現(xiàn)線程間負載均衡；(3) 對裁剪點序列三角化，編號構建Mesh 拓撲關系。

同時，考慮到kernel 并行特點與Device 內存的限制，設計的適合CUDA 并行的Mesh 存儲格式如圖3 所示。 GPUVertices、GPUFaces、GPUEdges 分別存儲Mesh 的點、面、邊信息，包括頂點坐標及編號、面頂點編號、面鄰接拓撲、邊頂點編號、邊所在面編號及局部編號等。

圖3 GPUMesh 數(shù)據(jù)組織圖

3.1 空間位置拓撲類型判斷

裁剪的第一步是確定三角面的拓撲類型，其由編碼邏輯運算確定，以三角面為單位通常更容易求解。 因此，大多數(shù)現(xiàn)有的算法將編碼計算與拓撲類型判斷整體上劃分為同一子任務。 但該方法會產(chǎn)生大量點編碼的重復計算。 以連接5 個三角面的頂點為例，傳統(tǒng)算法需要重復計算該頂點編碼5 次，存在著4 次重復計算。 由于編碼計算與拓撲判斷相互是獨立的，因此針對編碼計算中重復計算造成的性能損失問題，將任務分解為點編碼計算與面拓撲判斷兩部分。

編碼計算kernel 每個線程的主要任務是確定所有頂點的編碼。 編碼值計算方式由頂點坐標值與對應裁剪邊界的差值符號確定，分別判斷裁剪包圍盒6 個平面，得到對應的6 位編碼值。 計算頂點編碼后，面拓撲判斷kernel 每個線程的主要任務是編碼邏輯運算。 在線程中輸入三角面，通過邏輯運算確定線程內三角面的空間拓撲類型后結束。

3.2 逐邊裁剪

在編碼計算確定三角面空間位置拓撲類型后，需處理的三角面數(shù)量大大減少。 由逐邊裁剪算法原理可知，每個裁剪元的裁剪計算之間相互獨立，有著極高的并行性。 在實際應用中，三角面經(jīng)過裁剪可能包含9 個頂點。 受GPU 并行處理特點限制，若以變長數(shù)組存儲裁剪多變形頂點，實現(xiàn)復雜且無法保證算法時間效率。 綜合考慮內存消耗與該應用程序特點，以最大頂點數(shù)分配內存，采用定長數(shù)組存儲裁剪后頂點編號及坐標，并將新增頂點編號存儲為頂點數(shù)與該點存儲位置之和。 但是，該方法會導致共享交點的多次編號。 重復點索引示例如圖4 所示。以0 號面為例，裁剪交點b、c 在3 和1 號面所在線程多次編號。 因此，針對共享交點多次編號產(chǎn)生重復點問題，文章設計了一個基于面拓撲的重復交點索引結構，構建相交類型三角面的拓撲關系以查找重復頂點，并確保每個線程僅處理一個三角面與其相鄰面保證線程間負載均衡。

圖4 重復點索引示例圖

由圖4 可以看出，Mesh 中線段最多連接兩個三角面，可以通過面拓撲查找對應共享邊上的拓撲信息，對于非共享邊上的面拓撲信息則表示為該面本身。 裁剪后點編號表示相交類型三角面被裁剪后的多邊形點序列，可以根據(jù)多邊形點序列中有效頂點數(shù)查找目標點。 裁剪點坐標與裁剪點編號一一對應，存儲新增點的點坐標。 裁剪點索引用于根據(jù)面編號查找其所在線程，如由面編號等于3 可以查找到其線程索引為2。 線程內基于面拓撲的索引結構查找過程如圖5 所示，根據(jù)線程編號可以查詢到線程內三角面編號及其面拓撲信息，進而根據(jù)面－線程間索引查詢到該三角面與其面臨域內三角面裁剪點序列，比較坐標后即可定位重復點。

圖5 基于面拓撲的索引結構圖

索引結構的關鍵在于面拓撲的構建，根據(jù)面拓撲可以從當前相交三角面查找出與該面相交的所有三角面。 主要構建思路為:(1) 將三角面邊的頂點編號與所在面編號信息寫入GPU；(2) 構建輔助排序數(shù)組，根據(jù)輔助排序數(shù)組中元素值對Mesh 中邊排序，排序后使頂點相同的邊在數(shù)組內相鄰；(3) 在線程中索引一組相鄰邊，比較頂點編號并構建拓撲關系。 其中，輔助排序數(shù)組元素為邊起點編號乘以MAX＿INT 與終點編號之和。 排序示例如圖6 所示。

圖6 排序示意圖

確定每個三角面及其面拓撲后，遍歷該面裁剪點序列中頂點與臨接面頂點就可以確定重復點。 因此，去重過程中每個線程的主要任務是重復交點測試，測試由幾個嵌套循環(huán)組成，這意味著有大量的判斷分支，因測試的頻率較高，分支的減少將帶來相當大的性能改進。 因此，考慮到該應用程序的特點，僅對臨接面編號小于當前面編號情況進行重復點標記，將當前面該點編號轉換為臨接面點序列中該點編號，避免線程間讀寫沖突的同時，消除了測試過程的最大(最外層)分支。

3.3 多邊形三角化

Mesh 在裁剪后得到若干組多邊形點序列，需要進行三角化以保持Mesh 三角網(wǎng)格結構，同時因逐邊裁剪計算相互獨立，多邊形點序列中存在大量重復交點，需要去重并構建Mesh 拓撲關系，避免裁剪結果出現(xiàn)縫隙、T 形交點等錯誤[4]。

由幾何學的知識可以知道，連接凸多邊形的任意兩個不相鄰頂點，可以將其劃分成兩個小的凸多邊形[15]。 遞歸執(zhí)行該步驟直到多邊形不能繼續(xù)劃分為止，即可完成該多邊形的三角化。

在諸多三角化方法中，最簡單的算法就是耳切法。 具體思路是找出n 個頂點簡單多邊形的一個耳朵來構造一個三角形，并將這個耳朵的耳尖從簡單多邊形的頂點數(shù)組中剔除。 簡單多邊形的耳朵，是指由連續(xù)頂點V0、V1和V2組成的內部不包含其余任意頂點的三角形。 V0與V2之間的連線稱之為多邊形的對角線，點V1稱之為耳尖[16]。 針對由N 個定點組成的多邊形，找到其耳尖，移除唯一耳尖上的頂點，此時剩余頂點組成了一個n－1 個頂點的簡單多邊形[17]。 遞歸執(zhí)行上一步直到剩下2 個頂點為止，這樣就把這樣一個簡單多邊形構造成了一組三角形。 為提高算法性能，耳切法使用雙向鏈表存儲多邊形，遍歷頂點尋找耳朵。 對于每個頂點Vi和圍繞該頂點的三角形＜Vi－1、Vi、Vi＋1＞，測試其余頂點是否在當前三角形中，若有頂點在三角形里面，則不是耳尖[18]。 在實驗中可以發(fā)現(xiàn)如果一個頂點是耳尖，則一定是凸頂點。 由于三角形被裁剪面裁剪后所有頂點均可視為耳尖，且形成的凸多邊形頂點數(shù)有限，因此省去原算法中鏈表構建等過程，進一步簡化了三角化算法。 其算法流程圖如圖7 所示。

圖7 耳切法流程圖

針對多邊形點序列中的重復交點，算法通過構建計算編碼數(shù)組前綴和(Prefix sum)的方式構建Mesh 拓撲關系。 主要思路為對原Mesh 與裁剪后新增頂點、三角面編碼，需要保留的編碼為1，否則編碼為0。 計算編碼數(shù)組前綴和，將所有點、面分配到線程中，獲取該點、面的編碼判斷取舍，獲取編碼前綴和作為該點、面編號。 編號后將Mesh 下載至CPU 中裁剪結束。 前綴和計算方式如圖8 所示，前綴和數(shù)組中的元素為編碼數(shù)組中對應位置前所有元素之和。 前綴和數(shù)組對應存儲位置即為裁剪結果Mesh 的點、面編號。

圖8 Prefix sum 示意圖

3.4 算法性能優(yōu)化

為進一步提升基于GPU 的三維模型裁剪算法性能，在現(xiàn)有算法的基礎上進行優(yōu)化，以保證算法的并行效率。

(1) 快速浮點計算 在處理裁剪窗口與三角形的交點問題時，精度問題顯得尤為重要。 如果使用浮點運算，由于精度不高，可能會產(chǎn)生誤差導致裁剪結果出現(xiàn)裂縫等拓撲錯誤。 相反，精確的算法可以修復這些錯誤，但會導致較低的性能。 為了解決點三角化時的精確性問題，文獻[19]采用了兩道計算策略，即①通過浮點運算處理所有數(shù)據(jù)，并標記需要精確計算的數(shù)據(jù)；②計算采用多精度算法，并且只對標記的數(shù)據(jù)執(zhí)行。 精確的運算是通過增加數(shù)字的位數(shù)實現(xiàn)的，因此需要更多的硬件資源如寄存器和緩存，這會導致算法并發(fā)性較低。 與混合方法不同，文章通過調整線段的方向實現(xiàn)了基于浮點精度的高精度計算，從而實現(xiàn)了更高的性能。 在交點計算中，應計算線段頂點坐標差值分量的絕對值及差值符號，再根據(jù)絕對值最大分量的差值符號限制線段起點。 若差值符號為負號，則交換起點與終點；否則，保持現(xiàn)有關系。 該方法確保了相同線段交點計算的浮點計算誤差相同，滿足裁剪精度要求。

(2) 空間排序 當相鄰線程訪問內存的相鄰位置的時候，算法能獲得內存的最佳帶寬，通過沿著空間填充曲線對點、三角面等數(shù)組排序，可以改善裁剪時的隨機內存訪問。 以同樣的方式，去重復點和Mesh 重構也受益于空間排序。

(3) 線程分配 對于Block 維度的設定，一個合適的Block 維數(shù)可以使得并行問題更好地映射到CUDA 架構上，但對程序運行效率起的作用很小[20]。 同時，GPU 中的多流處理器(SM)在取指令和發(fā)射指令時，是以warp 為單位并交給流處理單元(SP)執(zhí)行的。 因此，為了有效利用執(zhí)行SP，線程分配不考慮Block 維度，每個Block 中線程數(shù)目均設置為線程數(shù)(32)的倍數(shù)[21]。

4 實驗結果與分析

4.1 實驗環(huán)境與實驗數(shù)據(jù)

實驗平臺的CPU 為Intel Core i7－6700，其主頻為3.40 GHz、內存為16 GB，GPU 為Nvidia GeForce GTX 1050，GPU 主要配置參數(shù)見表1。 所有程序在Windows10 系統(tǒng)下的Visual Studio 2017 和CUDA10.1環(huán)境下運行。 CPU 上的對比版本由VCGLib 框架提供。

表1 GPU 設備參數(shù)表

為測試算法的性能，選取9 組不同大小的基于傾斜影像構建的實景三維Mesh 模型數(shù)據(jù)進行實驗測試。 所有影像數(shù)據(jù)均采用搭載DQ5 傾斜攝影測量系統(tǒng)的多旋翼無人機獲取影像，Mesh 模型數(shù)據(jù)均采用ContextCapture 軟件獲得實景三維建模。 影像采集區(qū)域分別位于湖北省武漢市、河北省石家莊市、廣東省東莞市、福建省福州市。 Mesh 模型信息表見表2。

表2 Mesh 模型信息表

4.2 結果分析

為了比較不同數(shù)據(jù)量對處理效率的影響，設計3 組實驗以驗證算法性能，其中第一組實驗運行基于CPU 平臺的串行裁剪算法；第二組實驗運行GPU平臺的并行裁剪算法；第三組實驗運行性能優(yōu)化后的GPU 平臺并行裁剪算法。 針對多組測試數(shù)據(jù)，多次測試取其平均統(tǒng)計值進行分析，計算出各組實驗的平均耗時，數(shù)值結果保留小數(shù)點后兩位。 定義加速比s 為串行算法執(zhí)行時間和并行算法執(zhí)行時間之比，由式(1)表示為

式中TS、Tp分別為串行算法、并行算法的執(zhí)行時間，ms。

加速比反映了在相應并行計算架構下的并行算法相比于CPU 串行算法系統(tǒng)執(zhí)行效率的改善情況，能夠對實際系統(tǒng)的速度客觀評價。 不同Mesh 數(shù)據(jù)的并行裁剪結果如圖9 所示，其中圖9(a)～(c)為高樓和古建筑等區(qū)域，圖9(d)～(f)為住宅和道路，圖9(g)～(i)為田地區(qū)域。 所有區(qū)域均取得了正確裁剪結果，保證了CPU 算法性能。

圖9 不同Mesh 數(shù)據(jù)的并行裁剪結果

在單次裁剪實驗中，算法執(zhí)行時間對比見表3，當Mesh 數(shù)據(jù)大小相同時，GPU 并行算法相對CPU串行執(zhí)行時間都有不同程度的縮減，即均獲得了加速效果。 對于數(shù)據(jù)大小為68.65 MB 的1 號數(shù)據(jù)，Mesh 串行裁剪運算時間為549.63 ms，在CUDA 計算平臺下運算時間大幅縮短為159.77 ms，性能優(yōu)化后則進一步縮減為150.58 ms。 在相同大小數(shù)據(jù)下，并行處理后的裁剪算法的運算時間相比單線程的串行算法運算時間有明顯的減少，并且在相同的線程數(shù)下隨著Mesh 數(shù)據(jù)規(guī)模的增大，其運行時間也越來越長，基本符合線性增長的趨勢。

表3 單次裁剪中CPU 與GPU 算法的執(zhí)行時間表

Mesh 數(shù)據(jù)大小與加速比關系如圖10 所示，并行裁剪算法的加速比隨著Mesh 數(shù)據(jù)增大而增大，主要原因是當Mesh 數(shù)據(jù)較小時，GPU 算法大部分時間消耗在系統(tǒng)調度方面，設備高性能計算的優(yōu)勢沒有展現(xiàn)，單次裁剪運算時間與CPU 運算時間差別不明顯；隨著數(shù)據(jù)的增大，GPU 算法在編碼計算等計算密集型任務中的性能充分發(fā)揮，加速比也隨之上升。

圖10 Mesh 數(shù)據(jù)大小與加速比關系圖

在單層LOD 裁剪實驗中，算法執(zhí)行時間見表4?？梢钥闯觯谙嗤瑪?shù)據(jù)下單層裁剪加速比要比單次裁剪加速比高得多，主要原因是CPU 裁剪算法逐面進行串行處理，隨著實驗的裁剪次數(shù)增加，裁剪耗時呈線性增加。 而使用GPU 裁剪算法多次裁剪的情況下，CPU 和GPU 間的數(shù)據(jù)傳輸與單次裁剪一樣只需要上傳和下載兩次，避免了CPU 和GPU 間頻繁的數(shù)據(jù)傳輸，減少了數(shù)據(jù)傳輸造成的耗時占比，加速比也隨之增長。 為測試文章算法最大性能，對9 組數(shù)據(jù)進行固定裁減次數(shù)的多組實驗，裁剪次數(shù)與加速比的關系如圖11 所示。 隨著裁減次數(shù)增加，加速比增長速度也隨之增加。 不管是在給定遞增裁剪次數(shù)的模式下，還是給定足夠多的裁剪次數(shù)的模式下，相比于CPU 串行裁剪算法，所提出的GPU 并行算法都可獲得約10 倍以上的加速。

表4 LOD 多次裁剪中CPU 與GPU 算法的執(zhí)行時間表

圖11 裁剪次數(shù)與加速比關系圖

同時，為測試文章所采取的優(yōu)化策略對于提升三維模型裁剪并行算法性能的有效性，對比采取優(yōu)化策略與未采取優(yōu)化策略的實驗結果，結果如圖12所示。 可以看出，以優(yōu)化前算法(未采取優(yōu)化策略)加速比1 為基準，文章的3 種優(yōu)化策略在不同數(shù)據(jù)下均獲得了不同程度的性能提升，其中空間排序與線程分配優(yōu)化策略對算法3 個部分都有影響，因此加速效果較為明顯。 快速浮點計算僅用于算法的裁剪部分，但也在一定程度上提高了算法的性能。

圖12 優(yōu)化策略加速比對比結果圖

5 結論

針對當前傾斜攝影實景三維模型的常用裁剪算法存在的時間復雜高、計算效率較低等問題，文章提出了一種基于GPU 的實景三維模型裁剪算法。 在保證裁剪結果準確的情況下，最大限度地利用了GPU 并行計算資源，提高算法效率。 通過多次試驗測試性能后，得到以下結論:

(1) GPU 并行算法相較于傳統(tǒng)CPU 算法，在保證CPU 算法性能的前提下，單次裁剪實驗中最大獲得了13.93 倍的加速比，在LOD 構建實驗中加速比達到了35.85，并且在所有實驗數(shù)據(jù)集中都有不同程度的優(yōu)化，均獲得了加速效果。

(2) 在相同的實驗條件下，隨著Mesh 規(guī)模的增大，GPU 算法在編碼計算等計算密集型任務中性能充分發(fā)揮，加速比也隨之上升。

(3) 由于LOD 多次裁剪情況下，主機與設備間數(shù)據(jù)傳輸造成的耗時占比下降，因此隨著裁剪次數(shù)增多，加速比隨之增大。

(4) 為了更好地發(fā)揮GPU 性能，需要通過對算法的深入剖析，盡可能優(yōu)化數(shù)據(jù)的存儲；通過CPU與GPU 協(xié)同計算的方式，減少GPU 內存消耗；研究多GPU 協(xié)同計算機制，并利用GPU 集群進一步提升算法的性能。