基于GPU的海量離散點(diǎn)高程并行插值算法*

王智廣,張騰暢,吳相錦,魯 強(qiáng)1，

(1.中國(guó)石油大學(xué)(北京)石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 102249；2.中國(guó)石油大學(xué)(北京)計(jì)算機(jī)科學(xué)與技術(shù)系，北京 102249;3.北京中油瑞飛信息技術(shù)有限責(zé)任公司，北京 102206)

1 引言

在遙感測(cè)繪技術(shù)快速發(fā)展的背景下，測(cè)繪獲得的地形數(shù)據(jù)規(guī)模也隨之增大。實(shí)際工程有對(duì)三維地表上實(shí)時(shí)渲染海量離散點(diǎn)并支持對(duì)其進(jìn)行基本編輯交互操作的迫切需求。因此，對(duì)地表數(shù)據(jù)進(jìn)行空間分析具有必要性[1]。三維地表上海量離散點(diǎn)對(duì)渲染速率、渲染品質(zhì)和實(shí)時(shí)交互具有較高的要求，因此通常采用插值算法實(shí)時(shí)獲取離散點(diǎn)所在地表處的實(shí)際高程值，并賦值給該點(diǎn)進(jìn)行顯示[2]。在目前國(guó)內(nèi)外的研究中，對(duì)海量離散點(diǎn)的三維實(shí)時(shí)渲染存在如下2方面的缺陷：

(1) 地表網(wǎng)格實(shí)時(shí)改變使得渲染速率偏低。已有研究使用CPU實(shí)現(xiàn)相應(yīng)的高程插值算法[3]獲取地表某處實(shí)際高程，并將其賦給位于該處的地標(biāo)物，使之嵌入到三維地表網(wǎng)格中[4]，同時(shí)由于三維地表是基于細(xì)節(jié)層次模型LOD(Levels of Detail)結(jié)構(gòu)，其網(wǎng)格結(jié)構(gòu)會(huì)實(shí)時(shí)發(fā)生改變，為保證渲染精度需動(dòng)態(tài)執(zhí)行插值算法[5]，因此當(dāng)待渲染數(shù)據(jù)量過(guò)大時(shí)，整個(gè)三維場(chǎng)景的渲染速率大幅降低。

(2) 傳統(tǒng)的紋理貼圖方式降低了數(shù)據(jù)渲染品質(zhì)與空間分析能力[6]。為解決此問(wèn)題，研究者對(duì)矢量數(shù)據(jù)預(yù)處理生成多層紋理對(duì)象，并投影到對(duì)應(yīng)層次的三維地表[7]。該方式在某種程度上提高了場(chǎng)景的渲染速率，但使得矢量喪失了立體感，從而降低了渲染品質(zhì)[8]，同時(shí)紋理對(duì)象的預(yù)處理生成導(dǎo)致其無(wú)法較好地支持基本編輯交互操作，極大影響了矢量數(shù)據(jù)的空間分析能力[9]。

本文在已有研究的基礎(chǔ)上，針對(duì)海量離散點(diǎn)提出了基于GPU的高程并行插值算法，利用GPU編程語(yǔ)言GLSL(OpenGL Shading Language)[10]編寫(xiě)著色器程序，動(dòng)態(tài)控制圖形渲染管線并行獲取高程數(shù)據(jù)和自定義片元著色，在渲染速率和渲染品質(zhì)上有了極大提高，并支持?jǐn)?shù)據(jù)的實(shí)時(shí)編輯交互。

2 基于GPU的高程插值算法

2.1 原始數(shù)據(jù)組織

本文算法通過(guò)GPU編程實(shí)現(xiàn)海量離散點(diǎn)在三維地表上的并行加速渲染與編輯交互，因此高效地對(duì)海量離散點(diǎn)數(shù)據(jù)和原始地表高程數(shù)據(jù)進(jìn)行組織與管理[11]直接影響數(shù)據(jù)在內(nèi)存與顯存間傳遞的效率，為將離散點(diǎn)渲染量級(jí)從百萬(wàn)級(jí)提高到千萬(wàn)級(jí)提供了數(shù)據(jù)組織基礎(chǔ)。研究?jī)?nèi)容包含2個(gè)方面：

(1) 海量離散點(diǎn)數(shù)據(jù)組織方式。

根據(jù)實(shí)際應(yīng)用要求，離散點(diǎn)的存儲(chǔ)方式為按線存儲(chǔ)，即一系列離散點(diǎn)組成一條邏輯線，每條線中包含3個(gè)指針ptrv、ptrc和ptrf，分別指向GPU對(duì)應(yīng)的3個(gè)頂點(diǎn)緩沖區(qū)VertexBuffer，這3個(gè)緩沖區(qū)分別存儲(chǔ)線上離散點(diǎn)序列的頂點(diǎn)、顏色和標(biāo)志3類(lèi)數(shù)據(jù)，緩沖區(qū)作為內(nèi)存-顯存數(shù)據(jù)交換區(qū)域，為基于GPU的渲染算法提供基礎(chǔ)數(shù)據(jù)。

(2) 三維地表高程數(shù)據(jù)組織方式。

由于地表網(wǎng)格實(shí)時(shí)變換，本文算法創(chuàng)建高程紋理隊(duì)列，用于存儲(chǔ)不同分辨率的二維紋理對(duì)象，根據(jù)當(dāng)前地表網(wǎng)格采樣點(diǎn)變換情況，將數(shù)據(jù)存入隊(duì)列內(nèi)相應(yīng)的紋理對(duì)象中。紋理對(duì)象行列數(shù)、所占存儲(chǔ)大小及其處理最大地表網(wǎng)格數(shù)據(jù)大小的對(duì)應(yīng)關(guān)系如表1所示。

Table 1 Storage of digital elevation model grid data

本文研究的三維地表對(duì)象均為規(guī)則網(wǎng)格數(shù)據(jù)，地表數(shù)據(jù)分層分塊組織，每個(gè)地形塊的采樣點(diǎn)個(gè)數(shù)一致(默認(rèn)為64×64),單個(gè)地表級(jí)數(shù)不超過(guò)表1中所示的8級(jí)，根據(jù)紋理大小列中數(shù)據(jù)顯示，本文算法的硬件實(shí)驗(yàn)環(huán)境允許將紋理隊(duì)列一次性放入顯存中。

2.2 算法描述

以2.1節(jié)中數(shù)據(jù)作為輸入，本文算法通過(guò)高程紋理生成、高程并行插值和圖元紋理采樣3個(gè)主要過(guò)程實(shí)現(xiàn)海量離散點(diǎn)在三維地表上的實(shí)時(shí)渲染，為離散點(diǎn)渲染從百萬(wàn)級(jí)提高到千萬(wàn)級(jí)提供算法基礎(chǔ)，算法的流程圖如圖1所示。

Figure 1 Flow chart of the algorithm proposed in this paper圖1 本文算法流程圖

對(duì)圖1所描述算法的具體步驟說(shuō)明如下：

Step 1在進(jìn)行離散點(diǎn)渲染前，將三維地表作為輸入數(shù)據(jù)通過(guò)圖形渲染管線進(jìn)行一遍離屏渲染，生成對(duì)應(yīng)的高程紋理對(duì)象DTEX并通過(guò)調(diào)用DMAP.PUT(DISv,DTEX)將其存入高程紋理隊(duì)列，其中DISv表示當(dāng)前視距，DISv∈(0，DISmax]，DISmax表示三維場(chǎng)景載入時(shí)的視距，設(shè)為最大標(biāo)準(zhǔn)視距。

Step 2根據(jù)當(dāng)前視距DISv從高程紋理隊(duì)列中獲取對(duì)應(yīng)的高程紋理對(duì)象DTEX=DMAP.GET(DISv)，并通過(guò)uniform塊數(shù)據(jù)將DTEX、地表包圍盒TB和網(wǎng)格采樣間隔SINTVAL封裝成統(tǒng)一值塊，批量從內(nèi)存?zhèn)魅隚PU顯存中。顯存中uniform塊數(shù)據(jù)結(jié)構(gòu)如下所示,其中vec3為三維向量數(shù)據(jù)類(lèi)型：

uniformUniforms{

Sampler2DDTEX;

Sampler2DIMAGETEX;

floatDISv;

floatSINTVAL;

vec3TB.min;

vec3TB.max;}

結(jié)構(gòu)封裝使得內(nèi)存-顯存間的數(shù)據(jù)傳遞更加高效。

Step 3執(zhí)行頂點(diǎn)著色器程序SHv，根據(jù)式(1)計(jì)算離散點(diǎn)在高程紋理中對(duì)應(yīng)的紋理坐標(biāo)，并將其作為輸出數(shù)據(jù)傳入渲染管線的下一階段。式(1)中Vertex為圖形渲染管線中內(nèi)置向量型四維向量數(shù)據(jù)類(lèi)型vec4的變量，表示被當(dāng)前著色器處理的頂點(diǎn)的坐標(biāo)，紋理坐標(biāo)TC∈[0,1]：

(1)

(2)

Figure 2 Diagram of discrete point圖2 離散點(diǎn)分布示意圖

Step 4在完成高程插值后，需對(duì)頂點(diǎn)坐標(biāo)進(jìn)行變換，將其從初始時(shí)模型坐標(biāo)系轉(zhuǎn)換到二維屏幕坐標(biāo)中，該過(guò)程如式(3)所示，三維點(diǎn)坐標(biāo)通過(guò)右乘模型-視圖變換矩陣Matrixmv、投影變換矩陣Matrixp和視口矩陣Matrixv完成到二維顯示坐標(biāo)的轉(zhuǎn)換。其中(xm,ym,H0)表示點(diǎn)的模型坐標(biāo)，(xw,yw,zw)表示經(jīng)過(guò)轉(zhuǎn)換后的屏幕坐標(biāo)，第三維zw僅表示深度值，用于進(jìn)行深度裁剪。在圖形管線中可實(shí)時(shí)獲取Matrixmv和Matrixp。最后，根據(jù)二維顯示窗口的參數(shù)：起始二維坐標(biāo)值(x0,y0)、屏幕深度范圍(zmin,zmax),顯示窗口長(zhǎng)度width和顯示窗口寬度height，確定視口變換矩陣Matrixv。

(3)

Step 5執(zhí)行片元著色器程序SHf，其主要完成的功能是根據(jù)離散點(diǎn)的采樣坐標(biāo)glpointCoord從對(duì)應(yīng)的圖像紋理中獲取像素值。如式(4)所示，根據(jù)點(diǎn)的采樣坐標(biāo)獲取圖像紋理對(duì)應(yīng)位置的顏色值。

FragColor=

texture2D(IMAGETEX,PointCoord.xy)

(4)

其中texture2D是GLSL中默認(rèn)的紋理采樣函數(shù)，其作用是根據(jù)紋理坐標(biāo)從二維紋理對(duì)象對(duì)應(yīng)位置獲取元素值。

Step 6如果三維場(chǎng)景視點(diǎn)信息發(fā)生變化后導(dǎo)致地表網(wǎng)格數(shù)據(jù)發(fā)生改變，而DMAP中沒(méi)有相應(yīng)的高程紋理對(duì)象DTEX，則跳轉(zhuǎn)到Step 1；對(duì)離散點(diǎn)進(jìn)行編輯操作并改變數(shù)據(jù)狀態(tài)后，跳轉(zhuǎn)到Step 2；否則結(jié)束三維場(chǎng)景的渲染。

3 實(shí)驗(yàn)設(shè)置與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

本文算法效率主要受硬件條件的影響，表2列出了2組不同的實(shí)驗(yàn)環(huán)境影響算法執(zhí)行效率的主要指標(biāo)，其中CPU均為Intel Xeon系列，GPU均為NVIDIA Quadro系列。如無(wú)特殊說(shuō)明，在接下來(lái)內(nèi)容中，本文用CPU1、CPU2、GPU1、GPU2分別表示表2中的CPU與GPU型號(hào)。

Table 2 Hardware environment表2 實(shí)驗(yàn)硬件環(huán)境

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)主要針對(duì)海量離散點(diǎn)在三維地表上進(jìn)行實(shí)時(shí)渲染，實(shí)驗(yàn)中引入變量k=DISmax/DISv，用以度量當(dāng)前場(chǎng)景視距；圖3～圖6是基于本文算法實(shí)現(xiàn)的效果圖，分別表示在由遠(yuǎn)到近不同視距對(duì)應(yīng)的k值下離散點(diǎn)的顯示情況。由圖3～圖6中可以看出，離散點(diǎn)能夠緊密貼合在各分辨率地表網(wǎng)格上，從顯示效果上，離散點(diǎn)的顯示具有較強(qiáng)的立體感，同時(shí)可以根據(jù)視點(diǎn)動(dòng)態(tài)調(diào)整朝向，并且算法可為不同屬性的點(diǎn)對(duì)象貼合不同的紋理圖案，從而極大提高渲染品質(zhì)。

Figure 3 Diagram of rendering while k=1圖3 k=1時(shí)離散點(diǎn)渲染示意圖

Figure 4 Diagram of rendering while k=2圖4 k=2時(shí)離散點(diǎn)渲染示意圖

Figure 5 Diagram of rendering while k=5圖5 k=5時(shí)離散點(diǎn)渲染示意圖

Figure 6 Diagram of rendering while k=10圖6 k=10時(shí)離散點(diǎn)渲染示意圖

實(shí)驗(yàn)還測(cè)試了傳統(tǒng)CPU高程插值算法和本文基于GPU高程插值算法對(duì)三維場(chǎng)景渲染速率的影響。測(cè)試結(jié)果如表3～表6所示。其中n表示待渲染的離散點(diǎn)數(shù)量取值，單位是萬(wàn)個(gè)，表格中的數(shù)據(jù)表示在數(shù)量級(jí)為n、視距為k的情況下場(chǎng)景的渲染速率FPS(Frame Per Second)，單位為幀/秒。傳統(tǒng)CPU高程插值算法理論上最大能支持量級(jí)為一百萬(wàn)的離散點(diǎn)進(jìn)行渲染，但實(shí)際速率很低，因此本文為將其與基于GPU的高程插值算法進(jìn)行對(duì)比，選取的最大離散點(diǎn)數(shù)量為60萬(wàn)個(gè)。

Table 3 FPS of CPU1 rendering

Table 4 FPS of CPU2 rendering

Table 5 FPS of GPU1 rendering

Table 6 FPS of GPU2 rendering

3.3 實(shí)驗(yàn)分析

(1)圖7表示在視距DISv較大情況下，布設(shè)的離散點(diǎn)均需顯示在二維窗口內(nèi)時(shí)，隨著離散點(diǎn)數(shù)量增多，2組不同的硬件環(huán)境分別執(zhí)行傳統(tǒng)CPU插值算法與本文基于GPU高程插值算法渲染速率對(duì)比圖；圖8則表示在DISv較小情況下離散點(diǎn)的渲染速率對(duì)比。

Figure 7 Comparison of rendering rate with far distance圖7 遠(yuǎn)視距下離散點(diǎn)渲染速率對(duì)比

由于傳統(tǒng)CPU插值獲取高程方式只能支持百萬(wàn)級(jí)內(nèi)量級(jí)的離散點(diǎn)正常渲染，而本文算法使離散點(diǎn)三維渲染量級(jí)擴(kuò)展到千萬(wàn)級(jí)，因此對(duì)GPU1、GPU2實(shí)現(xiàn)的基于GPU高程插值算法的速率進(jìn)行進(jìn)一步測(cè)試，其結(jié)果圖9所示。圖9表示了在視距DISv較大，所有離散點(diǎn)均處于二維顯示窗口內(nèi)時(shí)，隨著點(diǎn)的量級(jí)增大，場(chǎng)景幀速率FPS的變換情況。由圖9可知，F(xiàn)PS變換分為3個(gè)階段：

Figure 8 Comparison of rendering rate with near distance圖8 近視距下離散點(diǎn)渲染速率對(duì)比

Figure 9 Diagram of the rendering based on GPU圖9 GPU加速渲染離散點(diǎn)速率示意圖

①當(dāng)離散點(diǎn)數(shù)量n<50萬(wàn)時(shí)，由于場(chǎng)景待渲染模型較少，導(dǎo)致FPS較低，因此n不是影響場(chǎng)景效率的主要因素；

②當(dāng)離散點(diǎn)數(shù)量50萬(wàn)≤n<200萬(wàn)，F(xiàn)PS下降速率較大，其原因是由于n的迅速增大，幾何著色器中執(zhí)行操作的插值算法消耗了大量的時(shí)間；

③當(dāng)離散點(diǎn)數(shù)量n≥200萬(wàn)，許多離散點(diǎn)超出視錐體范圍，圖形渲染管線會(huì)對(duì)這一部分模型進(jìn)行裁剪剔除，因此實(shí)際渲染數(shù)據(jù)并未按照線性直接增長(zhǎng)，F(xiàn)PS下降速率降低。

從圖8的渲染結(jié)果可以看出，在視距較小的情況下，只有部分點(diǎn)出現(xiàn)在二維顯示窗口內(nèi)，此時(shí)采用傳統(tǒng)CPU插值算法，渲染速率隨離散點(diǎn)的數(shù)量增加明顯下降。如果采用基于GPU高程插值算法，其速率下降幅度較小。其原因是：

①采用傳統(tǒng)CPU插值算法時(shí)，影響系統(tǒng)渲染速率的主要因素是計(jì)算離散點(diǎn)高程所消耗的時(shí)間，當(dāng)視距減小后，仍需計(jì)算所有離散點(diǎn)高程值，因此速率隨之下降較快。

②采用基于GPU高程插值算法，高程的計(jì)算由GPU內(nèi)部的幾何著色器并行完成，因此影響渲染速率的主要因素為場(chǎng)景內(nèi)離散點(diǎn)的數(shù)量；當(dāng)視距減小時(shí)，渲染管線將位于視錐體外部的離散點(diǎn)自動(dòng)裁剪，大規(guī)模地減少了待渲染離散點(diǎn)數(shù)量。所以，當(dāng)視點(diǎn)較近時(shí)，采用GPU高程插值算法可以保持場(chǎng)景渲染的較高速率。

Figure 10 Diagram of the rendering with the different distances圖10 不同視距下GPU渲染離散點(diǎn)速率示意圖

4 結(jié)束語(yǔ)

本文對(duì)基于GPU的海量離散點(diǎn)的高程并行插值算法進(jìn)行了深入的討論，在三維地表原始高程數(shù)據(jù)基礎(chǔ)上提出了高程紋理這一結(jié)構(gòu)作為算法的基礎(chǔ)，該數(shù)據(jù)結(jié)構(gòu)可有效地組織不同網(wǎng)格分辨率下的地表高程數(shù)據(jù)；在此基礎(chǔ)上，通過(guò)GLSL編寫(xiě)的GPU著色器程序動(dòng)態(tài)控制圖形渲染管線，在幾何著色器中，通過(guò)本文設(shè)計(jì)的插值算法并行獲取離散點(diǎn)高程數(shù)據(jù)，極大提高了渲染速率，并在著色階段對(duì)紋理進(jìn)行采樣，在不影響效率的前提下提高了渲染品質(zhì)。最后，通過(guò)詳細(xì)的實(shí)驗(yàn)對(duì)本文算法進(jìn)行驗(yàn)證，顯示了其可行性。

在海量離散點(diǎn)渲染過(guò)程中，視點(diǎn)遠(yuǎn)近決定了投影在二維顯示窗口內(nèi)離散點(diǎn)的個(gè)數(shù)，進(jìn)而直接影響渲染速率。未來(lái)將進(jìn)一步研究視點(diǎn)相關(guān)的調(diào)度算法，將顯示窗口中一次渲染總量控制在一定范圍內(nèi)，提高遠(yuǎn)視距下場(chǎng)景渲染速率。