基于OpenGL的DEM建模效率分析

成毅

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

0 引言

數字高程模型是數字地形模型的一個分支，當數字地形模型中的地形屬性為高程時，數字地形模型就稱為數字高程模型(DEM)。

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

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

1 penGL

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

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

2 反距離權重插值

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

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

(1)

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

圖1 反距離權重插值法示意圖

3 DEM地形模擬仿真

現有某一地區三維空間離散點數據，基于此高程數據，采用反距離權重插值法得到該地區高度圖，在OpenGL中對高度圖進行網格化得到DEM。

在Windows 7系統和Visual C++6.0平臺上，建立的DEM的模型，如圖2所示。

圖2 分辨率為16時建立的DEM模型

利用VS2016的性能探查器進行性能探查，如圖3所示。

圖3 性能探查

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

在圖3中的drawScene函數為建立DEM模型的主要函數，總CPU消耗的時間包括執行此函數中的代碼和此函數調用的函數中的代碼所花費的時間，自CPU消耗的時間是執行此函數中的代碼所花費的時間。由此可以看出，建立DEM模型消耗的時間包括計算機建立DEM模型的時間和計算機調用數據的時間。因此，建立DEM的效率不僅與插值函數有關，而且與數據的存儲和調用有關。總體來說，建立DEM的效率與四方面因素有關：采樣密度，網格劃分精度[11]，數據的存儲和讀取效率，插值方法的搜索半徑[12]。

4.1 采樣密度

采樣密度即在同一區域內采集的數據點個數，如表1、圖4所示。

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

圖4 不同采樣密度下建立DEM模型耗費的建模時間折線圖

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

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

4.2 網格劃分精度

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

圖5 32×32網格地形圖

圖6 64×64網格地形圖

圖7 128×128網格地形圖

圖8 不同網格精度下建立DEM模型耗費的建模時間折線圖

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

表2 不同網格劃分精度時建立DEM模型所耗費時間

隨著網格劃分精度的增加，相同區域內需要計算的網格節點數增多，那么需要搜索的采樣點數勢必就要增加，這就造成了周圍高程數據的搜索效率的降低。例如，在某一區域內，網格劃分精度為時，在此區域內需要計算高程值的網格節點數為54個，反距離權重插值法計算一個網格節點時需要搜索12個周圍采樣點，則在此區域內一共需要搜索個采樣點，當網格劃分精度為時，在此區域內需要計算高程值的網格節點數變為112個，則在此區域內一共需要搜索個周圍采樣點，所以在確定網格精度的過程中必須權衡周圍高程數據的搜索效率這個重要因素。網格的精度劃分同樣會對數據的存儲和讀取效率產生影響。隨著網格精度的增加，相同區域內需要存儲的高程數據就會不斷增多，計算網格節點時需要提取的采樣點高程數據也會隨之增多，這勢必就會造成內存開銷的增大以及讀取效率的降低。網格劃分精度是通過數據的存儲和讀取以及周圍高程數據的搜索效率對插值方法的計算效率產生影響的[13]。在插值函數一定的情況下，隨著網格劃分精度越高的提高，數據索引速度和周圍高程數據的搜索效率都會逐漸降低，這在一定程度上就會降低插值函數的計算效率。綜上所述，網格劃分精度是四個因素里面最重要的一個，我們在進行DEM建模時應重點考慮其影響。

4.3 數據的存儲和讀取效率

數據的存儲和讀取效率與網格劃分精度和插值方法的計算效率都有關聯。前面已經介紹了網格劃分精度與數據的存儲和讀取效率的關系，這里僅介紹數據的存儲和讀取效率與插值方法的計算效率的關系。在計算網格節點的高程值時，需要先搜索出網格節點周圍的高程數據點，然后再提取出這些采樣點的高程值進行插值計算[14]。從這個過程來看，提高數據的存儲和讀取效率有助于提高插值函數的計算效率。

數據的存儲和讀取效率的高低取決于數據存儲結構是否合理。合理的數據存儲結構可以存儲文件數量較多和單個文件較大的數據，在數據的提取時也會非常方便，如表3所示。

表3 采用數據以不同結構存儲時生成DEM模型所需要時間

在采樣密度，網格劃分精度，插值方法以及周圍高程數據的搜索效率一定的情況下，采樣數據以不同的結構存儲生成DEM模型時,四叉樹結構的效率明顯高于線性表。因此本文采用四叉樹結構進行數據的存儲和讀取。

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

nq=3,m=4;

nq=6,m=3;

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

圖11 四叉樹下建立DEM模型耗費的建模時間折線圖

圖12 線性表下建立DEM模型耗費的建模時間折線圖

4.4 插值方法搜索半徑

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

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

圖13 不同搜索半徑下建立DEM模型耗費的建模時間折線圖

5 建立DEM的效率分析模型

設DEM的建模效率為采樣密度為四叉樹數據結構的閾值為，插值函數的搜索半徑為，則分析模擬實驗結果可得：

ρ∝1U

δ∝1U

α∝1U

β∝1U

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

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

cdρβ

αδ

(2)

式(2)中:a為采樣密度影響權重；b為四叉樹數據結構的閾值的影響權重；c為插值函數的搜索半徑影響權重；d為網格劃分精度的影響權重；

此模型中的采樣密度，網格精度，數據的存儲和讀取效率，插值函數的搜索半徑網格劃分精度等四方面因素都會對DEM的建模效率產生影響，這四方面因素相當于自變量，DEM的建模效率相當于因變量，基于此種關系，使用最小二乘法計算各個因素所占的權重。

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

∑ni=1Xiβi=U

(3)

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

6 總結

采樣密度，網格劃分精度，數據的存儲和讀取效率，插值方法搜索半徑，是DEM建模效率的四個主要影響因素。在這4個因素中，網格劃分精度對DEM的建模效率影響最大，起到牽一發而動全身的作用，因此，在DEM建模時，應該重點考慮其影響，使精度和效率達到一個最優的平衡。