馬東嶺，李銘通，朱悅凱

(山東建筑大學(xué)測(cè)繪地理信息學(xué)院，山東 濟(jì)南 250101)

0 引言

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

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

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

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

1 CUDA 并行計(jì)算架構(gòu)

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

圖1 GPU 結(jié)構(gòu)示意圖

2 LOD 裁剪算法原理

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

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

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

3 GPU 并行裁剪計(jì)算

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

同時(shí)，考慮到kernel 并行特點(diǎn)與Device 內(nèi)存的限制，設(shè)計(jì)的適合CUDA 并行的Mesh 存儲(chǔ)格式如圖3 所示。 GPUVertices、GPUFaces、GPUEdges 分別存儲(chǔ)Mesh 的點(diǎn)、面、邊信息，包括頂點(diǎn)坐標(biāo)及編號(hào)、面頂點(diǎn)編號(hào)、面鄰接拓?fù)?、邊頂點(diǎn)編號(hào)、邊所在面編號(hào)及局部編號(hào)等。

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

3.1 空間位置拓?fù)漕愋团袛?/h3>

裁剪的第一步是確定三角面的拓?fù)漕愋?，其由編碼邏輯運(yùn)算確定，以三角面為單位通常更容易求解。 因此，大多數(shù)現(xiàn)有的算法將編碼計(jì)算與拓?fù)漕愋团袛嗾w上劃分為同一子任務(wù)。 但該方法會(huì)產(chǎn)生大量點(diǎn)編碼的重復(fù)計(jì)算。 以連接5 個(gè)三角面的頂點(diǎn)為例，傳統(tǒng)算法需要重復(fù)計(jì)算該頂點(diǎn)編碼5 次，存在著4 次重復(fù)計(jì)算。 由于編碼計(jì)算與拓?fù)渑袛嘞嗷ナ仟?dú)立的，因此針對(duì)編碼計(jì)算中重復(fù)計(jì)算造成的性能損失問題，將任務(wù)分解為點(diǎn)編碼計(jì)算與面拓?fù)渑袛鄡刹糠帧?/p>

編碼計(jì)算kernel 每個(gè)線程的主要任務(wù)是確定所有頂點(diǎn)的編碼。 編碼值計(jì)算方式由頂點(diǎn)坐標(biāo)值與對(duì)應(yīng)裁剪邊界的差值符號(hào)確定，分別判斷裁剪包圍盒6 個(gè)平面，得到對(duì)應(yīng)的6 位編碼值。 計(jì)算頂點(diǎn)編碼后，面拓?fù)渑袛鄈ernel 每個(gè)線程的主要任務(wù)是編碼邏輯運(yùn)算。 在線程中輸入三角面，通過邏輯運(yùn)算確定線程內(nèi)三角面的空間拓?fù)漕愋秃蠼Y(jié)束。

3.2 逐邊裁剪

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

圖4 重復(fù)點(diǎn)索引示例圖

由圖4 可以看出，Mesh 中線段最多連接兩個(gè)三角面，可以通過面拓?fù)洳檎覍?duì)應(yīng)共享邊上的拓?fù)湫畔?，?duì)于非共享邊上的面拓?fù)湫畔t表示為該面本身。 裁剪后點(diǎn)編號(hào)表示相交類型三角面被裁剪后的多邊形點(diǎn)序列，可以根據(jù)多邊形點(diǎn)序列中有效頂點(diǎn)數(shù)查找目標(biāo)點(diǎn)。 裁剪點(diǎn)坐標(biāo)與裁剪點(diǎn)編號(hào)一一對(duì)應(yīng)，存儲(chǔ)新增點(diǎn)的點(diǎn)坐標(biāo)。 裁剪點(diǎn)索引用于根據(jù)面編號(hào)查找其所在線程，如由面編號(hào)等于3 可以查找到其線程索引為2。 線程內(nèi)基于面拓?fù)涞乃饕Y(jié)構(gòu)查找過程如圖5 所示，根據(jù)線程編號(hào)可以查詢到線程內(nèi)三角面編號(hào)及其面拓?fù)湫畔?，進(jìn)而根據(jù)面－線程間索引查詢到該三角面與其面臨域內(nèi)三角面裁剪點(diǎn)序列，比較坐標(biāo)后即可定位重復(fù)點(diǎn)。

圖5 基于面拓?fù)涞乃饕Y(jié)構(gòu)圖

索引結(jié)構(gòu)的關(guān)鍵在于面拓?fù)涞臉?gòu)建，根據(jù)面拓?fù)淇梢詮漠?dāng)前相交三角面查找出與該面相交的所有三角面。 主要構(gòu)建思路為:(1) 將三角面邊的頂點(diǎn)編號(hào)與所在面編號(hào)信息寫入GPU；(2) 構(gòu)建輔助排序數(shù)組，根據(jù)輔助排序數(shù)組中元素值對(duì)Mesh 中邊排序，排序后使頂點(diǎn)相同的邊在數(shù)組內(nèi)相鄰；(3) 在線程中索引一組相鄰邊，比較頂點(diǎn)編號(hào)并構(gòu)建拓?fù)潢P(guān)系。 其中，輔助排序數(shù)組元素為邊起點(diǎn)編號(hào)乘以MAX＿INT 與終點(diǎn)編號(hào)之和。 排序示例如圖6 所示。

圖6 排序示意圖

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

3.3 多邊形三角化

Mesh 在裁剪后得到若干組多邊形點(diǎn)序列，需要進(jìn)行三角化以保持Mesh 三角網(wǎng)格結(jié)構(gòu)，同時(shí)因逐邊裁剪計(jì)算相互獨(dú)立，多邊形點(diǎn)序列中存在大量重復(fù)交點(diǎn)，需要去重并構(gòu)建Mesh 拓?fù)潢P(guān)系，避免裁剪結(jié)果出現(xiàn)縫隙、T 形交點(diǎn)等錯(cuò)誤[4]。

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

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

圖7 耳切法流程圖

針對(duì)多邊形點(diǎn)序列中的重復(fù)交點(diǎn)，算法通過構(gòu)建計(jì)算編碼數(shù)組前綴和(Prefix sum)的方式構(gòu)建Mesh 拓?fù)潢P(guān)系。 主要思路為對(duì)原Mesh 與裁剪后新增頂點(diǎn)、三角面編碼，需要保留的編碼為1，否則編碼為0。 計(jì)算編碼數(shù)組前綴和，將所有點(diǎn)、面分配到線程中，獲取該點(diǎn)、面的編碼判斷取舍，獲取編碼前綴和作為該點(diǎn)、面編號(hào)。 編號(hào)后將Mesh 下載至CPU 中裁剪結(jié)束。 前綴和計(jì)算方式如圖8 所示，前綴和數(shù)組中的元素為編碼數(shù)組中對(duì)應(yīng)位置前所有元素之和。 前綴和數(shù)組對(duì)應(yīng)存儲(chǔ)位置即為裁剪結(jié)果Mesh 的點(diǎn)、面編號(hào)。

圖8 Prefix sum 示意圖

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

表2 Mesh 模型信息表

4.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

針對(duì)當(dāng)前傾斜攝影實(shí)景三維模型的常用裁剪算法存在的時(shí)間復(fù)雜高、計(jì)算效率較低等問題，文章提出了一種基于GPU 的實(shí)景三維模型裁剪算法。 在保證裁剪結(jié)果準(zhǔn)確的情況下，最大限度地利用了GPU 并行計(jì)算資源，提高算法效率。 通過多次試驗(yàn)測(cè)試性能后，得到以下結(jié)論:

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

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

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

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