基于OpenGL的DEM建模效率分析

成毅

(東北石油大學(xué) 石油工程學(xué)院， 大慶 163000)

0 引言

數(shù)字高程模型是數(shù)字地形模型的一個(gè)分支，當(dāng)數(shù)字地形模型中的地形屬性為高程時(shí)，數(shù)字地形模型就稱為數(shù)字高程模型(DEM)。

隨著科技的發(fā)展，數(shù)字高程模型的相關(guān)理論與研究方法廣泛應(yīng)用于水文、氣象等各個(gè)領(lǐng)域[1]。因此，國內(nèi)外學(xué)者對(duì)DEM的模型進(jìn)行了深入的研究。葉海建對(duì)建立DEM模型的原理和影響DEM生成效率的因素進(jìn)行了分析，提出改進(jìn)DEM生成算法效率的關(guān)鍵點(diǎn)是改進(jìn)離散數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和其中的查找算法[2];安樂等采用四叉樹結(jié)構(gòu)對(duì)采樣數(shù)據(jù)進(jìn)行存儲(chǔ)，使DEM模型的生成效率得到了顯著的提高，尤其是在數(shù)據(jù)量很大的情況下，效果非常明顯[3]。

在我國學(xué)者的努力下，我國關(guān)于數(shù)字高程模型的理論和方法取得了豐碩的成果[4]，但是都未提出影響DEM建模效率的具體的模型，本文利用OpenGL，基于仿真實(shí)驗(yàn)結(jié)果，提出了效率模型，結(jié)果表明，該模型可靠度高，適用性強(qiáng)，為未來提高DEM模型的生成效率提供了一定的思路。

1 penGL

近些年來，OpenGl作為一個(gè)性能卓越的三維圖形標(biāo)準(zhǔn)發(fā)展迅猛，它在本質(zhì)上是一個(gè)開放的三維圖形軟件包，包括了200多個(gè)圖像處理函數(shù)[5]。OpenGL獨(dú)立于操作系統(tǒng)和窗口系統(tǒng)[6]，與硬件條件無關(guān),用它編寫的軟件可以在UNIX、Windows NT/XP等系統(tǒng)間實(shí)現(xiàn)移植[7]，而且使用簡便，效率高。OpenGL不僅提供了基本的點(diǎn)線多邊形的繪制函數(shù)[8]，而且提供了可以繪制復(fù)雜三維物體以及曲線和曲面的函數(shù)，這就為實(shí)現(xiàn)三維地形可視化奠定了基礎(chǔ)。

使用OpenGL建立DEM的基本思想[9]是：根據(jù)采樣得到離散隨機(jī)分布的三維空間高程數(shù)據(jù)，可以根據(jù)精度要求，首先對(duì)離散數(shù)據(jù)進(jìn)行網(wǎng)格劃分，然后再通過反距離權(quán)重插值法得到網(wǎng)格節(jié)點(diǎn)的高程值，進(jìn)而形成三維地形。

2 反距離權(quán)重插值

在眾多空間插值方法中，反距離權(quán)重插值法插值原理易于理解，算法簡單便于實(shí)現(xiàn)，因此，常常作為離散點(diǎn)空間分析的傳統(tǒng)方法之一[10]。反距離權(quán)重插值法的基本思想是：以插值點(diǎn)與采樣點(diǎn)間的距離為權(quán)重進(jìn)行加權(quán)平均，離插值點(diǎn)越近，樣本點(diǎn)被賦予的權(quán)重就越大，離插值點(diǎn)越遠(yuǎn)，樣本點(diǎn)被賦予的權(quán)重就越小，如圖1所示。

反距離權(quán)重插值如式(1)。

(1)

式(1)中，Z是插值點(diǎn)高程估計(jì)值；Zi是第i個(gè)插值點(diǎn)的高程值，di為第i個(gè)樣本點(diǎn)與插值點(diǎn)的歐幾里得距離；n是用于估算插值點(diǎn)值的樣點(diǎn)數(shù)；p是冪。

圖1 反距離權(quán)重插值法示意圖

3 DEM地形模擬仿真

現(xiàn)有某一地區(qū)三維空間離散點(diǎn)數(shù)據(jù)，基于此高程數(shù)據(jù)，采用反距離權(quán)重插值法得到該地區(qū)高度圖，在OpenGL中對(duì)高度圖進(jìn)行網(wǎng)格化得到DEM。

在Windows 7系統(tǒng)和Visual C++6.0平臺(tái)上，建立的DEM的模型，如圖2所示。

圖2 分辨率為16時(shí)建立的DEM模型

利用VS2016的性能探查器進(jìn)行性能探查，如圖3所示。

圖3 性能探查

4 影響DEM建模的四方面因素

在圖3中的drawScene函數(shù)為建立DEM模型的主要函數(shù)，總CPU消耗的時(shí)間包括執(zhí)行此函數(shù)中的代碼和此函數(shù)調(diào)用的函數(shù)中的代碼所花費(fèi)的時(shí)間，自CPU消耗的時(shí)間是執(zhí)行此函數(shù)中的代碼所花費(fèi)的時(shí)間。由此可以看出，建立DEM模型消耗的時(shí)間包括計(jì)算機(jī)建立DEM模型的時(shí)間和計(jì)算機(jī)調(diào)用數(shù)據(jù)的時(shí)間。因此，建立DEM的效率不僅與插值函數(shù)有關(guān)，而且與數(shù)據(jù)的存儲(chǔ)和調(diào)用有關(guān)?？傮w來說，建立DEM的效率與四方面因素有關(guān)：采樣密度，網(wǎng)格劃分精度[11]，數(shù)據(jù)的存儲(chǔ)和讀取效率，插值方法的搜索半徑[12]。

4.1 采樣密度

采樣密度即在同一區(qū)域內(nèi)采集的數(shù)據(jù)點(diǎn)個(gè)數(shù)，如表1、圖4所示。

表1 不同采樣密度下建立DEM模型耗費(fèi)的建模時(shí)間(ms)

圖4 不同采樣密度下建立DEM模型耗費(fèi)的建模時(shí)間折線圖

從表1、圖4中可以清楚的看出，采樣密度越大，DEM建模所耗費(fèi)的時(shí)間越長，效率越低。

采樣密度越大，則需要存儲(chǔ)的數(shù)據(jù)就越多，這就直接造成了數(shù)據(jù)的存儲(chǔ)和讀取效率的降低，進(jìn)而降低了DEM的建模效率。

4.2 網(wǎng)格劃分精度

在Windows 7系統(tǒng)和Visual C++6.0平臺(tái)上，分辨率分別為32,16,8時(shí)建立DEM的模型，如圖5-8所示。

圖5 32×32網(wǎng)格地形圖

圖6 64×64網(wǎng)格地形圖

圖7 128×128網(wǎng)格地形圖

圖8 不同網(wǎng)格精度下建立DEM模型耗費(fèi)的建模時(shí)間折線圖

隨著網(wǎng)格劃分精度越來越高，建立的DEM的分辨率也越高，但與此同時(shí)，建模所需要的時(shí)間也越多，建模效率越低，因此，在建立DEM模型時(shí)應(yīng)綜合考慮精度和時(shí)間的關(guān)系，如表2所示。

表2 不同網(wǎng)格劃分精度時(shí)建立DEM模型所耗費(fèi)時(shí)間

隨著網(wǎng)格劃分精度的增加，相同區(qū)域內(nèi)需要計(jì)算的網(wǎng)格節(jié)點(diǎn)數(shù)增多，那么需要搜索的采樣點(diǎn)數(shù)勢必就要增加，這就造成了周圍高程數(shù)據(jù)的搜索效率的降低。例如，在某一區(qū)域內(nèi)，網(wǎng)格劃分精度為時(shí)，在此區(qū)域內(nèi)需要計(jì)算高程值的網(wǎng)格節(jié)點(diǎn)數(shù)為54個(gè)，反距離權(quán)重插值法計(jì)算一個(gè)網(wǎng)格節(jié)點(diǎn)時(shí)需要搜索12個(gè)周圍采樣點(diǎn)，則在此區(qū)域內(nèi)一共需要搜索個(gè)采樣點(diǎn)，當(dāng)網(wǎng)格劃分精度為時(shí)，在此區(qū)域內(nèi)需要計(jì)算高程值的網(wǎng)格節(jié)點(diǎn)數(shù)變?yōu)?12個(gè)，則在此區(qū)域內(nèi)一共需要搜索個(gè)周圍采樣點(diǎn)，所以在確定網(wǎng)格精度的過程中必須權(quán)衡周圍高程數(shù)據(jù)的搜索效率這個(gè)重要因素。網(wǎng)格的精度劃分同樣會(huì)對(duì)數(shù)據(jù)的存儲(chǔ)和讀取效率產(chǎn)生影響。隨著網(wǎng)格精度的增加，相同區(qū)域內(nèi)需要存儲(chǔ)的高程數(shù)據(jù)就會(huì)不斷增多，計(jì)算網(wǎng)格節(jié)點(diǎn)時(shí)需要提取的采樣點(diǎn)高程數(shù)據(jù)也會(huì)隨之增多，這勢必就會(huì)造成內(nèi)存開銷的增大以及讀取效率的降低。網(wǎng)格劃分精度是通過數(shù)據(jù)的存儲(chǔ)和讀取以及周圍高程數(shù)據(jù)的搜索效率對(duì)插值方法的計(jì)算效率產(chǎn)生影響的[13]。在插值函數(shù)一定的情況下，隨著網(wǎng)格劃分精度越高的提高，數(shù)據(jù)索引速度和周圍高程數(shù)據(jù)的搜索效率都會(huì)逐漸降低，這在一定程度上就會(huì)降低插值函數(shù)的計(jì)算效率。綜上所述，網(wǎng)格劃分精度是四個(gè)因素里面最重要的一個(gè)，我們?cè)谶M(jìn)行DEM建模時(shí)應(yīng)重點(diǎn)考慮其影響。

4.3 數(shù)據(jù)的存儲(chǔ)和讀取效率

數(shù)據(jù)的存儲(chǔ)和讀取效率與網(wǎng)格劃分精度和插值方法的計(jì)算效率都有關(guān)聯(lián)。前面已經(jīng)介紹了網(wǎng)格劃分精度與數(shù)據(jù)的存儲(chǔ)和讀取效率的關(guān)系，這里僅介紹數(shù)據(jù)的存儲(chǔ)和讀取效率與插值方法的計(jì)算效率的關(guān)系。在計(jì)算網(wǎng)格節(jié)點(diǎn)的高程值時(shí)，需要先搜索出網(wǎng)格節(jié)點(diǎn)周圍的高程數(shù)據(jù)點(diǎn)，然后再提取出這些采樣點(diǎn)的高程值進(jìn)行插值計(jì)算[14]。從這個(gè)過程來看，提高數(shù)據(jù)的存儲(chǔ)和讀取效率有助于提高插值函數(shù)的計(jì)算效率。

數(shù)據(jù)的存儲(chǔ)和讀取效率的高低取決于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)是否合理。合理的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)可以存儲(chǔ)文件數(shù)量較多和單個(gè)文件較大的數(shù)據(jù)，在數(shù)據(jù)的提取時(shí)也會(huì)非常方便，如表3所示。

表3 采用數(shù)據(jù)以不同結(jié)構(gòu)存儲(chǔ)時(shí)生成DEM模型所需要時(shí)間

在采樣密度，網(wǎng)格劃分精度，插值方法以及周圍高程數(shù)據(jù)的搜索效率一定的情況下，采樣數(shù)據(jù)以不同的結(jié)構(gòu)存儲(chǔ)生成DEM模型時(shí),四叉樹結(jié)構(gòu)的效率明顯高于線性表。因此本文采用四叉樹結(jié)構(gòu)進(jìn)行數(shù)據(jù)的存儲(chǔ)和讀取。

四叉樹算法是一種空間均勻網(wǎng)格剖分方法，它的基本思想是：首先確定閾值nq，檢查區(qū)域內(nèi)的采樣點(diǎn)個(gè)數(shù)是否超過了閾值nq；如果超過了閾值nq，則將該區(qū)域進(jìn)行四等分，然后對(duì)4個(gè)子分區(qū)進(jìn)行同樣的遞歸操作，直到所有子分區(qū)的采樣數(shù)據(jù)個(gè)數(shù)均不超過該閾值為止。閾值的選取對(duì)四叉樹的深度和形態(tài)會(huì)產(chǎn)生重要的影響，分割閾值不同，算法的執(zhí)行效率不同，如圖9、10所示。

nq=3,m=4;

nq=6,m=3;

閾值nq越大，四叉樹深度m越小，建立DEM模型的耗費(fèi)的時(shí)間T就越少;閾值nq越小，四叉樹深度m越大，建立DEM模型耗費(fèi)的時(shí)間T就越多，如圖11、12所示。

圖11 四叉樹下建立DEM模型耗費(fèi)的建模時(shí)間折線圖

圖12 線性表下建立DEM模型耗費(fèi)的建模時(shí)間折線圖

4.4 插值方法搜索半徑

搜索半徑越大，建立DEM模型所需要的時(shí)間越長，效率越低；反之，則時(shí)間越短，效率越高。在進(jìn)行DEM建模的過程中，需要對(duì)網(wǎng)格交點(diǎn)處的高程值進(jìn)行插值計(jì)算，而插值計(jì)算時(shí)則需要對(duì)周圍高程數(shù)據(jù)進(jìn)行搜索以獲得高程數(shù)據(jù)。搜索半徑越大(即計(jì)算一個(gè)網(wǎng)格節(jié)點(diǎn)時(shí)需要搜索的采樣點(diǎn)數(shù)越大)，則計(jì)算機(jī)需要存儲(chǔ)的數(shù)據(jù)就越多，讀取時(shí)消耗的時(shí)間也越多，同時(shí)，這也會(huì)增加插值計(jì)算時(shí)的時(shí)間復(fù)雜度。搜索半徑越小，則消耗的時(shí)間越少，效率越高，但同時(shí)插值計(jì)算出的網(wǎng)格節(jié)點(diǎn)高程值可能誤差較大；搜索半徑越大，消耗的時(shí)間越多，效率越低，但同時(shí)插值計(jì)算出的高程值誤差較小。因此，在選取搜索半徑時(shí)，應(yīng)綜合考慮誤差和效率兩個(gè)因素，使其達(dá)到一個(gè)最優(yōu)的平衡。模擬實(shí)驗(yàn)結(jié)果，如表4、圖13所示。

表4 采用不同搜索半徑建立DEM模型所需要的時(shí)間

圖13 不同搜索半徑下建立DEM模型耗費(fèi)的建模時(shí)間折線圖

5 建立DEM的效率分析模型

設(shè)DEM的建模效率為采樣密度為四叉樹數(shù)據(jù)結(jié)構(gòu)的閾值為，插值函數(shù)的搜索半徑為，則分析模擬實(shí)驗(yàn)結(jié)果可得：

ρ∝1U

δ∝1U

α∝1U

β∝1U

雖然DEM的建模效率受到五方面的因素影響，但是他們對(duì)建模效率的影響權(quán)重并不一樣，建立數(shù)學(xué)模型如式(2)。

U(ρ,α,β,γ,δ)=aρ+bα+cβ+dδ=ab

cdρβ

αδ

(2)

式(2)中:a為采樣密度影響權(quán)重；b為四叉樹數(shù)據(jù)結(jié)構(gòu)的閾值的影響權(quán)重；c為插值函數(shù)的搜索半徑影響權(quán)重；d為網(wǎng)格劃分精度的影響權(quán)重；

此模型中的采樣密度，網(wǎng)格精度，數(shù)據(jù)的存儲(chǔ)和讀取效率，插值函數(shù)的搜索半徑網(wǎng)格劃分精度等四方面因素都會(huì)對(duì)DEM的建模效率產(chǎn)生影響，這四方面因素相當(dāng)于自變量，DEM的建模效率相當(dāng)于因變量，基于此種關(guān)系，使用最小二乘法計(jì)算各個(gè)因素所占的權(quán)重。

將上述模型進(jìn)行變形可得式(3)。

∑ni=1Xiβi=U

(3)

其中:Xi為影響DEM建模效率的五個(gè)因素，i=1,2,3,4,5;βi為各個(gè)因素所占的權(quán)重，i=1,2,3,4,5;

6 總結(jié)

采樣密度，網(wǎng)格劃分精度，數(shù)據(jù)的存儲(chǔ)和讀取效率，插值方法搜索半徑，是DEM建模效率的四個(gè)主要影響因素。在這4個(gè)因素中，網(wǎng)格劃分精度對(duì)DEM的建模效率影響最大，起到牽一發(fā)而動(dòng)全身的作用，因此，在DEM建模時(shí)，應(yīng)該重點(diǎn)考慮其影響，使精度和效率達(dá)到一個(gè)最優(yōu)的平衡。