王晨明， 蘇天赟， 王國(guó)宇， 宋慶磊

(1. 青島朗訊科技通訊設(shè)備有限公司，山東 青島 266100； 2. 國(guó)家海洋局第一海洋研究所，山東 青島266061；3. 中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266100)

?

海底地形實(shí)時(shí)繪制技術(shù)研究和實(shí)現(xiàn)?

王晨明1， 蘇天赟2， 王國(guó)宇3， 宋慶磊2

(1. 青島朗訊科技通訊設(shè)備有限公司，山東 青島 266100； 2. 國(guó)家海洋局第一海洋研究所，山東 青島266061；3. 中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266100)

為了提高大規(guī)模海底地形的繪制效率，LOD(細(xì)節(jié)層次，Levels of Details)技術(shù)必不可少。在ROAM(Real-time Optimally Adapting Meshes，實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格)算法的基礎(chǔ)上，通過數(shù)據(jù)加載、視域剪裁、建立評(píng)價(jià)方法等技術(shù)手段，根據(jù)視點(diǎn)位置實(shí)時(shí)更新可視區(qū)域，避免了多余三角面片的生成和繪制。同時(shí)，采用對(duì)不共斜邊節(jié)點(diǎn)強(qiáng)制分割的方法處理裂縫問題，通過索引坐標(biāo)與實(shí)際坐標(biāo)轉(zhuǎn)換以及無效值處理實(shí)現(xiàn)任意范圍海底地形對(duì)ROAM算法的應(yīng)用，消除了傳統(tǒng)ROAM算法對(duì)數(shù)據(jù)網(wǎng)格大小的限制，保證了繪制的效果和正確性。最后，通過GPU實(shí)時(shí)計(jì)算和繪制各頂點(diǎn)的法線和顏色，實(shí)現(xiàn)了大規(guī)模海底地形的實(shí)時(shí)建模和高效繪制，滿足了高精度、海量海底地形漫游瀏覽的需求，特別是針對(duì)起伏比較大的地形漫游瀏覽。

細(xì)節(jié)層次(LOD)； 二叉樹； 實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格(ROAM)； 海底地形； 評(píng)價(jià)因子

隨著陸地資源的急劇減少和能源價(jià)格的不斷攀升，人們將視線轉(zhuǎn)移到了海洋。海底地形也是如大陸地形一樣復(fù)雜多變，不但有高山深谷，而且還有平原丘陵。外貌不但奇特壯觀，規(guī)模更是非常巨大。目前多種格式的海洋數(shù)據(jù)以及爆發(fā)式增長(zhǎng)的信息量，在三維場(chǎng)景渲染時(shí)需要占據(jù)很大內(nèi)存空間。由于傳統(tǒng)二維電子海圖在表現(xiàn)海底地形信息時(shí)不夠清晰直觀，因此，在不影響顯示效果的前提下，盡量簡(jiǎn)化場(chǎng)景模型顯得尤為重要。

1976年Clark首次提出了LOD[1]的概念。在距離視點(diǎn)較近的區(qū)域，采用較高的細(xì)節(jié)層次，進(jìn)行較為逼真的3D渲染；較遠(yuǎn)的區(qū)域，采用較低的細(xì)節(jié)層次，大致渲染。除了保證畫面細(xì)節(jié)，還能節(jié)省計(jì)算量。

1991年至今，LOD技術(shù)日趨完善。1996年，P.Lindstrom第一次實(shí)現(xiàn)了基于視點(diǎn)的連續(xù)層次細(xì)節(jié)，采用了四叉樹的邊剖分方法表示地形[2]。在此基礎(chǔ)上，Duchaineau等提出了ROAM算法，用三角形二叉樹表示地形網(wǎng)格[3]。1998年，Hugues Hoppe等在他們?cè)缙谔岢龅囊环N可以從任意網(wǎng)格增減三角形的方法的基礎(chǔ)上，提出了基于視向的漸進(jìn)網(wǎng)格VDPM[4]。2001年，Lindstrom等又提出了基于外存(out-of-core)的大規(guī)模地形可視化技術(shù)，使用操作系統(tǒng)文件映射的虛擬內(nèi)存空間來存儲(chǔ)地形數(shù)據(jù)[5]。2003年，陸艷青提出一種對(duì)視點(diǎn)預(yù)測(cè)的預(yù)裝載策略，根據(jù)視點(diǎn)移動(dòng)方向來預(yù)測(cè)下一幀視點(diǎn)的位置，繪制當(dāng)前幀的同時(shí)，裝載下一幀用到的地形數(shù)據(jù)[6]。2004年，芮小平等人提出了一種改進(jìn)的ROAM算法，基于非等腰三角形實(shí)現(xiàn)ROAM算法[7]。2005年，Hoppe提出了在geometry clipmaps技術(shù)基礎(chǔ)上基于GPU的硬件加速的靜態(tài)多分辨率地形渲染算法[8]。2009年，YotamLivny等提出了另一種基于GPU的四叉樹地形算法[9]。在LOD技術(shù)的發(fā)展過程中，ROAM算法的簡(jiǎn)單和可擴(kuò)展性使其成為目前地形渲染中被廣泛研究的算法。

ROAM是一種自底向上的基于三角形二叉剖分的算法。由于該算法在幀更新過程中只分裂和合并少量三角形，因此能較快更新地形網(wǎng)格，一度成為L(zhǎng)OD地形算法研究的熱點(diǎn)。本文在ROAM算法的基礎(chǔ)上，通過改進(jìn)數(shù)據(jù)建模和繪制過程的關(guān)鍵技術(shù)，實(shí)現(xiàn)了大規(guī)模、高精度、任意邊界范圍海底地形的實(shí)時(shí)繪制。

1 算法

ROAM算法中，整個(gè)地形由多個(gè)二叉樹組成。二叉樹結(jié)構(gòu)的特點(diǎn)是使用二元三角樹來保持三角坐標(biāo)，每個(gè)節(jié)點(diǎn)都是一個(gè)正二等邊三角形。從三角形的頂點(diǎn)到其斜邊的中點(diǎn)進(jìn)行分割，生成2個(gè)新的等邊三角形，這兩個(gè)三角形構(gòu)成原節(jié)點(diǎn)的2個(gè)孩子節(jié)點(diǎn)。

在算法中每個(gè)節(jié)點(diǎn)需要包含5個(gè)指向樹中其它節(jié)點(diǎn)的指針，分別指向基鄰居、左鄰居、右鄰居、左孩子和右孩子，它們構(gòu)成了合并與增加三角形操作的基礎(chǔ)，也是ROAM技術(shù)得以實(shí)現(xiàn)的關(guān)鍵所在(見圖1)。

圖1 二元三角樹節(jié)點(diǎn)的5個(gè)指針

每個(gè)二叉樹根節(jié)點(diǎn)會(huì)根據(jù)一定準(zhǔn)則分割為所需的細(xì)節(jié)層次，遞歸分割過程(見圖2)：

圖2 遞歸分割過程

2 關(guān)鍵技術(shù)

采用如下步驟對(duì)海底地形進(jìn)行實(shí)時(shí)建模：

(1)載入地形數(shù)據(jù)；

(2)初始化地形，將地形分為N×N個(gè)小方塊Patch，每個(gè)Patch由2個(gè)正三角形組成，每個(gè)正三角形為1個(gè)根節(jié)點(diǎn)；

(3)將所有Patch互連，建立相互間的鄰接關(guān)系，斜邊處于邊界的節(jié)點(diǎn)，其基鄰居設(shè)為NULL；

(4)獲得視點(diǎn)位置，根據(jù)視點(diǎn)位置進(jìn)行視域剪裁，(6)(7)(8)都是只對(duì)可見區(qū)域作用；

(5)根據(jù)視點(diǎn)位置、地形粗糙度和地形塊大小獲得評(píng)價(jià)準(zhǔn)則，根據(jù)這個(gè)準(zhǔn)則決定細(xì)節(jié)層次；

(6)遞歸計(jì)算視域內(nèi)每個(gè)節(jié)點(diǎn)的誤差，若大于閾值，則分割；否則，不分割；

(7)每個(gè)節(jié)點(diǎn)被分割時(shí)進(jìn)行裂縫處理；

(8)通過OpenGL的頂點(diǎn)著色器和片元著色器[11]繪制每個(gè)頂點(diǎn)的顏色、法線等，渲染所有二叉樹的葉子節(jié)點(diǎn)；

(9)操作鼠標(biāo)和鍵盤改變視點(diǎn)，通過新視點(diǎn)設(shè)置新的可見區(qū)域，重復(fù)(4)。

相應(yīng)的海底建模流程圖(見圖3)：

圖3 海底建模流程圖

2.1 數(shù)據(jù)與處理

ROAM算法有2個(gè)限制條件[7]：

(1)地形為正方形；

(2)地形數(shù)據(jù)量必須為(2n+1)×(2n+1)。

為了便于ROAM算法的實(shí)施，本文的地形數(shù)據(jù)采用網(wǎng)格文件進(jìn)行組織，文件中包含地形要分割的行數(shù)、列數(shù)、網(wǎng)格大小、地形的起始經(jīng)緯度、無效值和所有頂點(diǎn)的高度值。

為了提高系統(tǒng)對(duì)于數(shù)據(jù)文件的兼容性，本文對(duì)文件讀取部分做了改進(jìn)。讀取文件時(shí)，記錄Patch的行列數(shù)、寬度、起始經(jīng)緯度和無效值。在每行頂點(diǎn)高度取出的同時(shí)，系統(tǒng)判斷本行數(shù)據(jù)的個(gè)數(shù)是否為2n+1。若是，繼續(xù)取出下一行數(shù)據(jù)，同時(shí)將數(shù)據(jù)放入指針數(shù)組；若不是，補(bǔ)充無效值到本行，直到達(dá)到2n+1的個(gè)數(shù)，剩余行也同樣處理。通過這種方法，系統(tǒng)可以適用于行列數(shù)為任意值的高程數(shù)據(jù)。

如圖4，本文可將有效數(shù)據(jù)量為x×y的地形(黃色部分)補(bǔ)充為(2n+1)×(2n+1)。使得算法不再受到傳統(tǒng)ROAM算法中地形原始數(shù)據(jù)量必須為(2n+1)×(2n+1)的限制。

圖4 補(bǔ)充無效值

整塊地形渲染前，要對(duì)地形初始化。把它分成若干個(gè)Patch，對(duì)每一個(gè)Patch沿對(duì)角線劃分為基本左三角形和基本右三角形。

2.2 視域剪裁

為提高繪制效率，應(yīng)盡量減少渲染的三角形個(gè)數(shù)，因此需要進(jìn)行視域剪裁。

圖5表示對(duì)分塊后的地形進(jìn)行裁剪測(cè)試，如果其中心點(diǎn)位于可視范圍之外，將其視為不可見；否則，可見。此外，將地形中所有高度為無效值的區(qū)域設(shè)為不可見。用戶可以根據(jù)需要自行調(diào)整視角大小。根據(jù)剪裁規(guī)則，采用全局變量g_bIsVisibile標(biāo)識(shí)每個(gè)Patch的可見狀態(tài)，并且只針對(duì)可見區(qū)域進(jìn)行鄰接關(guān)系建立、節(jié)點(diǎn)誤差計(jì)算、裂縫處理、繪制等操作，以便于提高繪制效率。

判斷可見區(qū)域的實(shí)現(xiàn)方法如下：

令Patch的中點(diǎn)坐標(biāo)為patchCenter(x,y)，則

a(x,y)=right(x,y)-eye(x,y)

b(x,y)=patchCenter(x,y)-eye(x,y)

result=a(x,y)×b(x,y)

如果result>0，Patch可見；否則不可見。

2.3 空白區(qū)域處理

在傳統(tǒng)ROAM方法的基礎(chǔ)上，為了提高繪制效率，只需要繪制可見區(qū)域內(nèi)的節(jié)點(diǎn)。漫游模式下，隨著視點(diǎn)的不斷變化，在視域兩側(cè)會(huì)出現(xiàn)沒有繪制的空白區(qū)域。由于最小的繪制單位為Patch，在視點(diǎn)移動(dòng)時(shí)，視域內(nèi)會(huì)存在已經(jīng)被視為不可見Patch的一部分，該部分不繪制導(dǎo)致了空白區(qū)域的出現(xiàn)。因此，為了提高繪制效果，本文對(duì)不可見區(qū)域不分割，只繪制出最低細(xì)節(jié)層次,并且通過建立鄰接關(guān)系，避免與可見區(qū)域細(xì)分網(wǎng)格之間出現(xiàn)裂縫(見圖6)。這樣，既解決了不可見區(qū)域的空白問題，又不影響繪制效率。

圖5 視域剪裁

圖6 消除空白區(qū)域

2.4 評(píng)價(jià)方法的建立

如何決定某個(gè)時(shí)刻使用哪個(gè)層次細(xì)節(jié)度是ROAM實(shí)現(xiàn)的關(guān)鍵。因此，需要建立一個(gè)節(jié)點(diǎn)評(píng)價(jià)方法，根據(jù)評(píng)價(jià)因子，設(shè)置閾值，實(shí)時(shí)更新所需的細(xì)節(jié)層次。

(1)評(píng)價(jià)因子

評(píng)價(jià)因子1：動(dòng)態(tài)視點(diǎn)依賴誤差

視點(diǎn)依賴誤差是物體在屏幕上的投影大小，通常用觀察者到物體的距離度量。距離視點(diǎn)近的區(qū)域具有更高精度，精細(xì)分割；距離視點(diǎn)遠(yuǎn)的區(qū)域具有較低精度，簡(jiǎn)單分割或不分割(見圖7)：

節(jié)點(diǎn)M的動(dòng)態(tài)視點(diǎn)依賴誤差的計(jì)算方式表示為：

其中：dMcenterx、dMcentery表示節(jié)點(diǎn)斜邊中點(diǎn)坐標(biāo);eyex、eyey表示視點(diǎn)坐標(biāo)。如果dM<動(dòng)態(tài)視點(diǎn)依賴誤差閾值，分割；否則，不分割。

僅根據(jù)節(jié)點(diǎn)動(dòng)態(tài)誤差分割的效果如圖8，視點(diǎn)位于屏幕下方，動(dòng)態(tài)視點(diǎn)依賴誤差閾值分別為656、196m，即中心坐標(biāo)與視點(diǎn)距離小于656、196m的節(jié)點(diǎn)分割：

圖7 根據(jù)視點(diǎn)分割

圖8 僅根據(jù)節(jié)點(diǎn)與視點(diǎn)的距離分割

評(píng)價(jià)因子2：靜態(tài)地形起伏誤差(即物體的粗糙程度)。

由于地形的復(fù)雜程度不同，起伏大的區(qū)域需要更多三角形表示。因此要在地形平坦處采用低分辨率三角網(wǎng)，地形粗糙處采用高分辨率三角網(wǎng)。

由于分割一個(gè)節(jié)點(diǎn)只改變了該三角形斜邊中點(diǎn)的高度值，二元三角樹中一個(gè)節(jié)點(diǎn)的局部偏差可以通過該點(diǎn)的插值高度與其實(shí)際高度差計(jì)算[3](見圖9)。

圖9 節(jié)點(diǎn)的局部偏差

節(jié)點(diǎn)靜態(tài)地形起伏誤差的計(jì)算方式表示為：

hb、hc、hd分別表示點(diǎn)b、c、d的高度。

如果hΔ>靜態(tài)地形起伏誤差閾值，分割；否則，不分割。

僅根據(jù)節(jié)點(diǎn)靜態(tài)地形起伏誤差分割的效果如圖10，地形最大、最小高度差為1 200m，靜態(tài)地形起伏誤差閾值分別為90、150m：

評(píng)價(jià)因子3:地形尺寸。

對(duì)于較大地形，當(dāng)觀察全部區(qū)域時(shí)，視點(diǎn)距離整個(gè)地形都很遠(yuǎn)，根據(jù)評(píng)價(jià)因子1(動(dòng)態(tài)視點(diǎn)依賴誤差)，只能觀察到較低的細(xì)節(jié)層次。為了滿足對(duì)大地形的層次顯示，將地形的尺寸也作為一個(gè)評(píng)價(jià)因子，用于下一步綜合評(píng)價(jià)。

評(píng)價(jià)因子4：幀誤差。

當(dāng)整個(gè)場(chǎng)景的三角形數(shù)量沒有達(dá)到或者超過預(yù)期的三角形數(shù)量時(shí)，通過幀誤差調(diào)節(jié)三角形數(shù)量，直到達(dá)到預(yù)期三角形個(gè)數(shù)。

通過如下公式調(diào)節(jié)幀誤差：

式中：FrameVariance是用戶最初指定的幀誤差，繪制過程中會(huì)自行調(diào)整；Nodes是場(chǎng)景中實(shí)際的三角形數(shù)量；DesireTris表示期望的場(chǎng)景三角形總數(shù)。利用幀之間的相關(guān)性，自動(dòng)調(diào)節(jié)幀誤差，在一定程度上減少了計(jì)算量，從而提高繪制速度。

(2)聯(lián)合4個(gè)因子，進(jìn)行綜合評(píng)價(jià)，以判別該節(jié)點(diǎn)是否進(jìn)一步分割。評(píng)價(jià)公式如下：

式中：hΔ是節(jié)點(diǎn)的靜態(tài)地形起伏誤差；d是節(jié)點(diǎn)的動(dòng)態(tài)依賴誤差；size是地形尺寸，即地形每行、列的點(diǎn)數(shù)；K是調(diào)節(jié)因子，通過改變K值調(diào)整地形分割程度；FrameVariance是用戶剛開始指定的幀誤差；通過判斷f的正負(fù)決定節(jié)點(diǎn)是否分割，f>0時(shí)三角形分割，f<=0時(shí)不分割。

經(jīng)測(cè)試，建議FrameVariance的設(shè)定規(guī)則為：

FrameVariance=(hmax-hmin)/10，

其中，hmax、hmin分別為地形的最大和最小高度值。k的建議取值為2。

(3)內(nèi)存控制因子

為防止分割過程中內(nèi)存溢出，本文采用內(nèi)存池(PoolSize)、期望三角形數(shù)(DesiredTris)和誤差樹深度(VarianceDepth)等參數(shù)控制內(nèi)存的使用。

所有二叉樹節(jié)點(diǎn)被存放在內(nèi)存池中，若節(jié)點(diǎn)數(shù)大于內(nèi)存池容量，停止分割；

DesiredTris為每一幀設(shè)置最大能容納的三角形個(gè)數(shù)，若個(gè)數(shù)過多，停止分割。

VarianceDepth控制二元三角樹的誤差計(jì)算深度，當(dāng)一個(gè)Patch中節(jié)點(diǎn)數(shù)超過2VarianceDepth時(shí)，誤差仍然不滿足停止分割的要求，則不再計(jì)算誤差，而且以節(jié)點(diǎn)邊長(zhǎng)L作為停止分割的閾值。本文測(cè)試中L=8。

經(jīng)測(cè)試，內(nèi)存池(PoolSize)的建議取值規(guī)則為：

NumPatchx表示地形每行分割的Patch數(shù);

NumPatchy表示地形每列分割的Patch數(shù);

hmax、hmin分別表示地形的最大和最小高度值;

DesiredTris的建議取值規(guī)則為：DesiredTris=2.5×PoolSize;

VarianceDepth的建議取值規(guī)則為[3]：

Patch_size表示每個(gè)Patch的邊長(zhǎng)。

2.5 裂縫問題

二元三角樹網(wǎng)格關(guān)于鄰節(jié)點(diǎn)有一個(gè)規(guī)律，即一個(gè)節(jié)點(diǎn)和它的鄰節(jié)點(diǎn)只存在兩種關(guān)系：共直角邊關(guān)系和共斜邊關(guān)系[6]。

如果相鄰子塊的分辨率不一致，在構(gòu)建三角形網(wǎng)格時(shí)，會(huì)因?yàn)橄噜忂吔绲募?xì)節(jié)層次不同而出現(xiàn)裂縫(見圖11)。

圖11 裂縫

因此，為了避免產(chǎn)生裂縫，分割2個(gè)構(gòu)成菱形的節(jié)點(diǎn)，稱之為“鉆石結(jié)構(gòu)(diamond)”[3]。

分割一個(gè)節(jié)點(diǎn)時(shí)存在3種可能：

(1)節(jié)點(diǎn)和其基鄰居互為下鄰關(guān)系——分割兩者(見圖12)；

圖12 分割鉆石結(jié)構(gòu)

(2)節(jié)點(diǎn)在地形塊的邊界上——只分割這個(gè)節(jié)點(diǎn)；

(3)節(jié)點(diǎn)不在邊界上并與基鄰居不為下鄰關(guān)系——強(qiáng)制分割，直到出現(xiàn)情況(1)或(2)。

強(qiáng)制分割過程為圖13中的(a)(b)(c)：

當(dāng)需要剖分黃色三角形時(shí)，由于其斜邊鄰居處于高一層細(xì)節(jié)層次，必須對(duì)其斜邊鄰居強(qiáng)制剖分，以此類推，直到找到鉆石結(jié)構(gòu)，再反方向逐級(jí)剖分[3]。

圖13 強(qiáng)制分割過程

2.6 坐標(biāo)轉(zhuǎn)換

傳統(tǒng)ROAM算法要求地形大小為(2n+1)×(2n+1)[3]。初始化時(shí)，每個(gè)Patch邊長(zhǎng)為1，給算法的應(yīng)用帶來很大局限性。

為打破這種局限性，本文設(shè)置了索引坐標(biāo)Ix、Iy，用于對(duì)ROAM算法的地形分塊進(jìn)行索引。同時(shí)，設(shè)置了2個(gè)轉(zhuǎn)換函數(shù)，分別用來將行和列對(duì)應(yīng)的索引坐標(biāo)轉(zhuǎn)化為實(shí)際坐標(biāo)，真實(shí)再現(xiàn)任意大小的地形。

Tx、Ty表示x、y的實(shí)際坐標(biāo);

Ix、Iy表示x、y的索引坐標(biāo);

dx、dy表示每個(gè)小塊的實(shí)際長(zhǎng)、寬;

Iminx、Iminy表示初始繪制點(diǎn)坐標(biāo)。

這2個(gè)函數(shù)只在模型轉(zhuǎn)換、視點(diǎn)移動(dòng)、頂點(diǎn)繪制和法線計(jì)算時(shí)用到。

2.7 繪制

為了減少運(yùn)行時(shí)刻CPU的動(dòng)態(tài)三角化負(fù)載，本文利用GPU進(jìn)行重建后的地形繪制工作，主要包括法線和顏色的繪制，提高地形的顯示效率和效果。

2.7.1 法線 海底地形凹凸不平，必須進(jìn)行法線計(jì)算達(dá)到光照下的立體效果。OpenGL中用表面表示物體，一個(gè)物體就是一組平面。光線照射在平面上會(huì)產(chǎn)生反射，入射線與反射線的角平分線就是法線，它垂直于平面。

鑒于使用面法線會(huì)使整個(gè)地形看起來分塊比較明顯，為使其整體效果更佳，需要計(jì)算每個(gè)頂點(diǎn)的法線。

OpenGL中定義面法線和頂點(diǎn)法線(見圖14)：

圖14 面法線、頂點(diǎn)法線

如上圖所示，根據(jù)V0、V1、V2確定的平面，可以求出這個(gè)平面的2條相交線，這兩條線叉乘即為所求法線。

面法線Vnormal=Va×Vb,頂點(diǎn)法線為包含該頂點(diǎn)三角形面法線之和：

V=V12+V23+V34+V41,

繪制前，定義一個(gè)size×size×3的法線數(shù)組，存放各個(gè)頂點(diǎn)的法線，數(shù)組的索引是各頂點(diǎn)的索引坐標(biāo)，size為地形尺寸，即每行、列的點(diǎn)數(shù)。遍歷這一幀的所有節(jié)點(diǎn)，通過坐標(biāo)轉(zhuǎn)換函數(shù)獲得每個(gè)節(jié)點(diǎn)中3個(gè)頂點(diǎn)的實(shí)際坐標(biāo)，計(jì)算面法線，將面法線累加到這3個(gè)頂點(diǎn)的法線數(shù)組里，從而得到這一幀所有頂點(diǎn)的法線。圖15的(a)(b)分別展示了不加法線和加法線的效果：

2.7.2 顏色 為達(dá)到更明顯地形高度差異和更清晰的效果，需要為地形的每個(gè)頂點(diǎn)賦予不同顏色值。本文采用高級(jí)著色語言GLSL，實(shí)現(xiàn)在GPU上對(duì)地形不同高度值快速著色。

圖15 不加法線和加法線的效果圖

著色分為N個(gè)色段，高度最小值Hmin對(duì)應(yīng)顏色最暗色(藍(lán)色)，最大值Hmax對(duì)應(yīng)最亮色(紅色)，對(duì)落在色段之間的高度按比例進(jìn)行顏色插值。如下式和圖16所示，高度為Hi的頂點(diǎn)落在M色段上，Mmin、Mmax的顏色值分別為colorMmin、colorMmax，計(jì)算Hi的顏色值colorHi：

圖16 計(jì)算頂點(diǎn)的顏色

顏色渲染效果(見圖15)。

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

為了進(jìn)行應(yīng)用測(cè)試，本文對(duì)研究的算法進(jìn)行了開發(fā)和實(shí)現(xiàn)。測(cè)試平臺(tái)為普通計(jì)算機(jī)，CPU為Intel T5670，顯卡為ATI Mobility Radeon X1350，內(nèi)存為2G。操作系統(tǒng)為Windows XP，開發(fā)環(huán)境為VisualStudio 2008 C++，底層圖形接口采用OpenGL。

本文使用的數(shù)據(jù)為南海某峽谷區(qū)域，數(shù)據(jù)分辨率為10 m，地區(qū)大小約為8.3萬km2，存放于網(wǎng)格文件中，網(wǎng)格數(shù)為5 732×2 892，頂點(diǎn)數(shù)量超過107。為使地形起伏更明顯，繪制時(shí)將高度放大10倍，顯示效果如圖17所示。

表1是在某一地形起伏較大處測(cè)試的參數(shù)對(duì)比。網(wǎng)格大小PatchSize=32,地形高度差hmax-hmin=1 322.375，內(nèi)存池大小PoolSize=200 000,期望的三角形總數(shù)DesiredTris=50 000,最大誤差計(jì)算深度VarianceDepth=12時(shí)，改變幀誤差值的效果比較(見表1)：

圖17 測(cè)試結(jié)果

幀誤差Framevariance初始場(chǎng)景三角形總數(shù)Initialnumberoftriangles初始幀速Initialframerate/frame×s-1幀誤差平衡所需時(shí)間Timerequiredforbalanceofframeerror/s平衡后的幀誤差Framevarianceafterbalance平衡后的三角形總數(shù)Numberoftrianglesafterbalance平衡后的幀速Framerateafterbalance/frame×s-1450479512131299．924160520300704941222296．40635820211501043761015294．43736048221001034811025298．4963584021501020401029299．13573619251024811035299．0763551020

表1證實(shí)了幀誤差會(huì)自我調(diào)整，直到平衡。經(jīng)測(cè)試，上述所有情況平衡后的幀速均能達(dá)到20幀/s，三角形總數(shù)約為36 000個(gè)。幀誤差FrameVariance=300時(shí)，既能較好繪制地形，又能使三角形總數(shù)最快達(dá)到穩(wěn)定。本文建議的評(píng)價(jià)因子(如期望三角形總數(shù)、最大誤差計(jì)算深度、調(diào)節(jié)因子K和幀誤差等)閾值是基于現(xiàn)有數(shù)據(jù)集測(cè)試后的結(jié)果，不一定適用于所有地形數(shù)據(jù)。因此，在使用本文提出的地形建模方法時(shí)，需要根據(jù)建議值對(duì)評(píng)價(jià)因子進(jìn)行測(cè)試，以確定最佳的評(píng)價(jià)因子的閾值，來實(shí)現(xiàn)海底地形的快速、動(dòng)態(tài)建模。

表2為不同地形算法的幀速對(duì)比圖，內(nèi)容均為實(shí)際實(shí)驗(yàn)數(shù)據(jù)。表二繪制幀速及繪制效果的對(duì)比表明，本文方法在繪制效果相同的情況下，繪制速率比傳統(tǒng)的ROAM方法提高了大約30%，適用于大規(guī)模、任意網(wǎng)格大小海底地形的動(dòng)態(tài)繪制。

表2 繪制效率對(duì)比

5 結(jié)語

為了提高大規(guī)模三維地形的實(shí)時(shí)繪制效率，本文在ROAM算法基礎(chǔ)上，提出了一種高效地形實(shí)時(shí)繪制算法，針對(duì)數(shù)據(jù)加載、視域剪裁、評(píng)價(jià)方法建立、裂縫處理、GPU繪制等關(guān)鍵技術(shù)進(jìn)行了研究和實(shí)現(xiàn)，并應(yīng)用在海底地形的動(dòng)態(tài)繪制中。通過對(duì)無效值的處理提高了數(shù)據(jù)的兼容性，索引坐標(biāo)到實(shí)際坐標(biāo)的轉(zhuǎn)換消除了對(duì)網(wǎng)格大小的限制，解決了不可見區(qū)域不參與繪制導(dǎo)致的空白區(qū)域問題。通過測(cè)試，本方法能夠提高大數(shù)據(jù)量海底地形的繪制效率和顯示效果，為海洋工程勘察和科學(xué)研究提供高效、直觀的海底地形動(dòng)態(tài)瀏覽服務(wù)。

[1] Clark J H. Hierarchical geometric models for visible surface algorithms[J]. Communications of the ACM, 1976, 19(10): 547-554.

[2] Lindstrom P, Koller D, Ribarsky W, et al. Real-time, continuous level of detail rendering of height fields[C]// New York: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, 1996: 109-118.

[3] Duchaineau M, Wolinsky M, Sigeti D E, et al. ROAMing terrain: real-time optimally adapting meshes[C]// Arizons: Proceedings of the 8th Conference on Visualization'97. IEEE Computer Society Press, 1997: 81-88.

[4] Hoppe H. Smooth view-dependent level-of-detail control and its application to terrain rendering[C]// North Carolina: Visualization'98. Proceedings. IEEE, 1998: 35-42.

[5] Lindstrom P. Out-of-core simplification of large polygonal models[C]// New York: Proceedings of the 27th Annual Conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 2000: 259-262.

[6] 陸艷青. 海量地形數(shù)據(jù)實(shí)時(shí)繪制的技術(shù)研究[D]. 杭州: 浙江大學(xué), 2003. Lu Y Q. Study of the Real-Time Rendering for Large-Scale Terrain Dataset[D]. A Dissertation Presented to the Graduate School of Zhejiang University in Partial Fulfillment of the Requirement for the Degree of Doctor of Philosophy, 2003.

[7] 芮小平, 楊崇俊, 張彥敏. 一種改進(jìn)的 ROAM 算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2005, 29(11): 1008-1011. Rui X. An improved LOD algorithm based on ROAM[J]. Editorial Board of Geomatics& Information Science of Wuhan University, 2005.

[8] Asirvatham A, Hoppe H. Terrain rendering using GPU-based geometry Clipmaps[J]. GPU gems, 2005, 2(2): 27-46.

[9] Livny Y, Kogan Z, El-Sana J. Seamless patches for GPU-based terrain rendering[J]. The Visual Computer, 2009, 25(3): 197-208.

[10] Woo M, Neider J. OpenGL編程指南 (第四版)[M]. 北京： 人民郵電出版社, 2005. Woo M, Neider J. Opengl Architecture Review Board[M]. Beijing: PosTs & TELECOM PRESS, 2005.

[11] Wright Jr R S, 賴特, Lipchak B, et al. OpenGL 超級(jí)寶典[M]. 北京： 人民郵電出版社, 2005. Wright R S, Lipchak B. OpenGL Superbible[M]. Beijing: PosTs & TELECOM PRESS, 2005.

責(zé)任編輯 陳呈超

Research and Implementation on Real-Time Undersea Terrain Visualization Technology

WANG Chen-Ming1， SU Tian-Yun2， WANG Guo-Yu3， SONG Qing-Lei2

(1.Alcatel-Lucent Qingdao, Qingdao 266100, China; 2.The First Institute of Oceanography, SOA, Qingdao 266061,China; 3.College of Information Science and Engineering, Ocean University of China, Qingdao 266100,China)

With the rapid development of computer graphics, the three-dimensional terrain modeling and visualization are widely researched at home and abroad. The speed of real-time rendering becomes the key factor to determine whether a three-dimensional visualization system is good. But the large amount of data has became the huge obstacles of three-dimensional visualization. Scholars at home and abroad used LOD (Level of Detail) technology widely to solve this problem. The main function of this technology is to simplify the part of flat terrain and distant objects, to reduce the number of drawing primitives, to improve the rendering efficiency under the premise of ensuring visual effects.The content of this paper is study the draw technology of large-scale three-dimensional terrain. It introduces the research status and development in the relevant field at home and abroad. LOD (Levels of Details) technology is essential on improving the efficiency of large scale terrain. The main purpose of this project is to study the seabed terrain rendering progress at home and abroad, to analyze the pros and cons of different ways, to obtain feasible solutions, to optimize programs on this basis, at last, to improve the rendering efficiency and to meet the authenticity.Based on ROAM(Real-time Optimally Adapting Meshes)algorithm, the display area can be updated in real-time according to the viewpoint position by means of data source processing, field crop and the establishment of evaluation methods, which can avoid rendering superfluous triangular facets. At the same time, the nodes, which have different hypotenuses, are compulsively split to solve the problem of crack. Through transforming from the indexical coordinate to actual coordinate and utilizing the NONE data value, then any scope of undersea terrain can be modeled and visualized based on ROAM, which can clear up the limit of mesh size and guarantee the rendering effect and correctness. By computing and rendering each vertex’s normal and color with GPU, we accomplish the goal of large-scale terrain modeling and efficient rendering in real-time, which meets the needs of the high precision, massive undersea terrain roaming, especially for the terrain which ups and downs.

levels of details; binary tree; ROAM; undersea terrain;evaluation factors

海洋公益性行業(yè)科研專項(xiàng)(201205001)；國(guó)家科技重大專項(xiàng)“大型油氣田及煤層氣開發(fā)”子任務(wù)(2011ZX05056-001-01)資助 Supported by The Public Science and Technology Research Funds Projects of Ocean ( 201205001)； sub-project of “The Important Project of Science and Technology in Developing Great Oil & Gas Field and Coal Bed Gas”(2011ZX05056-001 )

2014-10-05；

2015-08-20

王晨明(1990-)，女，碩士生。E-mail：wangchenming1990@163.com

P714

A

1672-5174(2016)12-142-09

10.16441/j.cnki.hdxb.20140248

王晨明， 蘇天赟， 王國(guó)宇， 等. 海底地形實(shí)時(shí)繪制技術(shù)研究和實(shí)現(xiàn)[J]. 中國(guó)海洋大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 46(12)： 142-150.

WANG Chen-Ming， SU Tian-Yun， WANG Guo-Yu， et al. Research and implementation on real-time undersea terrain visualization technology[J]. Periodical of Ocean University of China, 2016, 46(12)： 142-150.