基于GPU的海量離散點高程并行插值算法*

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

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

1 引言

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

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

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

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

2 基于GPU的高程插值算法

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

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

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

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

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

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

Table 1 Storage of digital elevation model grid data

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

2.2 算法描述

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

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

對圖1所描述算法的具體步驟說明如下：

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

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

uniformUniforms{

Sampler2DDTEX;

Sampler2DIMAGETEX;

floatDISv;

floatSINTVAL;

vec3TB.min;

vec3TB.max;}

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

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

(1)

(2)

Figure 2 Diagram of discrete point圖2 離散點分布示意圖

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

(3)

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

FragColor=

texture2D(IMAGETEX,PointCoord.xy)

(4)

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

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

3 實驗設(shè)置與結(jié)果

3.1 實驗環(huán)境

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

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

3.2 實驗結(jié)果

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

Figure 3 Diagram of rendering while k=1圖3 k=1時離散點渲染示意圖

Figure 4 Diagram of rendering while k=2圖4 k=2時離散點渲染示意圖

Figure 5 Diagram of rendering while k=5圖5 k=5時離散點渲染示意圖

Figure 6 Diagram of rendering while k=10圖6 k=10時離散點渲染示意圖

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

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 實驗分析

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

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

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

Figure 8 Comparison of rendering rate with near distance圖8 近視距下離散點渲染速率對比

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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