王智廣,張騰暢,吳相錦,魯 強1，

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

1 引言

在遙感測繪技術(shù)快速發(fā)展的背景下，測繪獲得的地形數(shù)據(jù)規(guī)模也隨之增大。實際工程有對三維地表上實時渲染海量離散點并支持對其進行基本編輯交互操作的迫切需求。因此，對地表數(shù)據(jù)進行空間分析具有必要性[1]。三維地表上海量離散點對渲染速率、渲染品質(zhì)和實時交互具有較高的要求，因此通常采用插值算法實時獲取離散點所在地表處的實際高程值，并賦值給該點進行顯示[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ù)進行組織與管理[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在進行離散點渲染前，將三維地表作為輸入數(shù)據(jù)通過圖形渲染管線進行一遍離屏渲染，生成對應(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)進行變換，將其從初始時模型坐標(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僅表示深度值，用于進行深度裁剪。在圖形管線中可實時獲取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；對離散點進行編輯操作并改變數(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é)果

實驗主要針對海量離散點在三維地表上進行實時渲染，實驗中引入變量k=DISmax/DISv，用以度量當(dāng)前場景視距；圖3～圖6是基于本文算法實現(xiàn)的效果圖，分別表示在由遠(yuǎn)到近不同視距對應(yīng)的k值下離散點的顯示情況。由圖3～圖6中可以看出，離散點能夠緊密貼合在各分辨率地表網(wǎ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高程插值算法理論上最大能支持量級為一百萬的離散點進行渲染，但實際速率很低，因此本文為將其與基于GPU的高程插值算法進行對比，選取的最大離散點數(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)量級的離散點正常渲染，而本文算法使離散點三維渲染量級擴展到千萬級，因此對GPU1、GPU2實現(xiàn)的基于GPU高程插值算法的速率進行進一步測試，其結(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萬，許多離散點超出視錐體范圍，圖形渲染管線會對這一部分模型進行裁剪剔除，因此實際渲染數(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的海量離散點的高程并行插值算法進行了深入的討論，在三維地表原始高程數(shù)據(jù)基礎(chǔ)上提出了高程紋理這一結(jié)構(gòu)作為算法的基礎(chǔ)，該數(shù)據(jù)結(jié)構(gòu)可有效地組織不同網(wǎng)格分辨率下的地表高程數(shù)據(jù)；在此基礎(chǔ)上，通過GLSL編寫的GPU著色器程序動態(tài)控制圖形渲染管線，在幾何著色器中，通過本文設(shè)計的插值算法并行獲取離散點高程數(shù)據(jù)，極大提高了渲染速率，并在著色階段對紋理進行采樣，在不影響效率的前提下提高了渲染品質(zhì)。最后，通過詳細(xì)的實驗對本文算法進行驗證，顯示了其可行性。

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