吳東亞，邵 偉，黃璽瑛，夏永春

(1.裝甲兵工程學(xué)院科研部，北京100072;2.裝甲兵工程學(xué)院裝備指揮與管理系，北京100072)

目前，三維地形可視化技術(shù)在多個行業(yè)中已得到廣泛應(yīng)用，如三維城市建設(shè)、軍事中戰(zhàn)場地形的三維可視化顯示等，眾多成熟的商業(yè)可視化開發(fā)平臺大都支持地形建模和可視化顯示，但價格昂貴。OpenSceneGraph(OSG)是一個基于工業(yè)圖形標(biāo)準(zhǔn)OpenGL的高層次圖形開發(fā)API接口，具有開源、平臺無關(guān)性、高品質(zhì)及高性能等優(yōu)點，已廣泛用于虛擬仿真、虛擬現(xiàn)實、科學(xué)和工程可視化等領(lǐng)域［1］，OSG在地形可視化方面也提出了VirtualPlanetBuilder、osgGIS及osgEarth等解決方案。

隨著地形顯示范圍的擴(kuò)大和顯示精度的提高，數(shù)字高程模型(Digital Elevation Model，DEM)數(shù)據(jù)量呈幾何倍數(shù)增長，從而加大了計算機(jī)實時渲染的難度。針對這一問題，筆者以O(shè)SG為實現(xiàn)平臺，構(gòu)建了地形多分辨率四叉樹模型，闡述了該模型的存儲機(jī)制及調(diào)度策略，最后在OSG中采用該模型實現(xiàn)了按需動態(tài)加載地形數(shù)據(jù)并進(jìn)行實時渲染。

1 地形多分辨率四叉樹模型定義

大規(guī)模地形實時渲染存在的主要問題是數(shù)據(jù)量過大，計算機(jī)無法一次全部加載數(shù)據(jù)。隨著計算機(jī)軟、硬件技術(shù)的發(fā)展，計算機(jī)的計算能力與存儲容量均得到大幅度提升，采用傳統(tǒng)的地形數(shù)據(jù)調(diào)度、渲染算法，一方面無法實現(xiàn)流暢渲染，另一方面也造成了計算機(jī)計算與存儲優(yōu)勢的極大浪費。解決這一問題的核心是對地形數(shù)據(jù)的存儲結(jié)構(gòu)進(jìn)行科學(xué)、合理的組織，優(yōu)化數(shù)據(jù)調(diào)度算法，提高渲染效率。四叉樹是一種數(shù)據(jù)組織結(jié)構(gòu)，該結(jié)構(gòu)的每個節(jié)點最多有4個子節(jié)點，如圖1所示，常用于數(shù)據(jù)庫存儲或文件存儲［2］。

圖1 四叉樹示例

地形多分辨率四叉樹模型是將同一塊地形數(shù)據(jù)按照不同分辨率進(jìn)行分割存儲管理的數(shù)據(jù)結(jié)構(gòu)模型，適用于矩形柵格DEM，分割前后地形數(shù)據(jù)分辨率呈倍數(shù)遞增關(guān)系，即分割后地形數(shù)據(jù)的網(wǎng)格間距是分割前網(wǎng)格間距的1/2。

矩形柵格DEM由地表規(guī)則網(wǎng)格單元構(gòu)成［3］，結(jié)構(gòu)如圖2所示。

圖2 矩形柵格DEM結(jié)構(gòu)

地形多分辨率四叉樹模型具有以下2個特點:一是除葉子節(jié)點外，其余節(jié)點都擁有4個子節(jié)點;二是4個子節(jié)點將父節(jié)點地幅按面積均分為4份。下面以如圖3中所示的A地域為例，建立3級分辨率四叉樹模型。

根據(jù)建立模型分辨率的層級數(shù)，將地域進(jìn)行相應(yīng)分割。建立3級分辨率模型，先將A地域按面積均分為4塊，分別為 A1、A2、A3、A4，而后將該4塊地域繼續(xù)進(jìn)行分割，生成16塊地域，最終形成了A地域的3級分辨率四叉樹模型，模型結(jié)構(gòu)如圖4所示。

建立多分辨率層級結(jié)構(gòu)后，需設(shè)計對應(yīng)的存儲及調(diào)用機(jī)制，從而可按需調(diào)用不同分辨率的地形數(shù)據(jù)。

圖3 A地域

圖4 四叉樹分割模型

2 地形多分辨率四叉樹模型存儲機(jī)制

2.1 存儲結(jié)構(gòu)

為便于快速檢索數(shù)據(jù)，多分辨率四叉樹模型采用大數(shù)據(jù)文件加索引文件的形式進(jìn)行存儲，大文件將模型中所有節(jié)點的地形數(shù)據(jù)進(jìn)行整合，四叉樹節(jié)點數(shù)據(jù)的存儲順序為從上到下、由左至右。大文件存儲模式如圖5所示。

圖5 大文件存儲模式

索引文件負(fù)責(zé)記錄大文件中各個節(jié)點數(shù)據(jù)的相關(guān)信息，包括節(jié)點編碼、分辨率級別、存儲起始地址等信息，索引文件結(jié)構(gòu)如圖6所示。

圖6 索引文件結(jié)構(gòu)

圖6中各個節(jié)點均有一條索引記錄來記錄該節(jié)點的相關(guān)信息，記錄中的區(qū)域1-8地址信息為當(dāng)前節(jié)點毗鄰地域DEM數(shù)據(jù)的存儲地址信息，如圖7所示，節(jié)點A索引記錄中的區(qū)域1-8地址信息依次記錄A1，…，A8地域DEM數(shù)據(jù)的存儲地址信息。

圖7 區(qū)域關(guān)系圖

2.2 DEM數(shù)據(jù)存儲處理

將DEM數(shù)據(jù)進(jìn)行處理，生成上述存儲結(jié)構(gòu)，即通過數(shù)據(jù)內(nèi)插、分塊、合并等多種操作對DEM數(shù)據(jù)進(jìn)行處理。DEM數(shù)據(jù)處理流程如圖8所示。

圖8 DEM數(shù)據(jù)處理流程

分辨率高的分塊的DEM數(shù)據(jù)主要由低分辨率數(shù)據(jù)采用內(nèi)插算法生成，即根據(jù)若干相鄰的高程點求出待定點上的高程值，如常用的加權(quán)平均算法等，在數(shù)學(xué)上屬于插值問題;而后將同一地域不同分辨率的DEM數(shù)據(jù)組織成大文件，并生成索引文件。

構(gòu)建DEM多分辨率數(shù)據(jù)時，還需考慮文件大小的影響，若生成的文件過大，文件的定位索引會變慢，不便于對其進(jìn)行處理。對此，可將要處理的地域合理劃分為多塊，對每塊建立多分辨率模型并存儲為大文件，由此減小各個文件的大小，文件名需包含各塊地域在整個地幅中的位置，如采用行號、列號對文件進(jìn)行命名，便于處理系統(tǒng)調(diào)用不同地塊文件［4］。

2.3 紋理數(shù)據(jù)存儲處理

為提供逼真的地形顯示效果，還需在地形表面粘貼紋理圖片。因此，需為各級分辨率地形數(shù)據(jù)準(zhǔn)備一塊對應(yīng)的紋理圖片并進(jìn)行存儲，紋理圖片處理步驟如下［5］。

1)定位。根據(jù)地形數(shù)據(jù)塊覆蓋的區(qū)域，確定相應(yīng)的紋理圖片，即選取該地域的紋理圖片進(jìn)行處理。

2)紋理文件處理。為確保地形顯示正確、不變形，紋理圖片像素需和地形數(shù)據(jù)采樣的行列數(shù)成正比關(guān)系。如對行列數(shù)為500×300(地域內(nèi)的高程數(shù)據(jù)按照縱向500行、橫向300列采樣獲取)的地形數(shù)據(jù)，紋理圖片需處理為a×b(像素)，a與b滿足條件a/500=b/300。

3)合并處理。若低分辨率紋理短缺時，該紋理文件還可由高分辨率紋理文件合并生成。

4)存儲。將生成的紋理文件按照對應(yīng)的DEM數(shù)據(jù)存儲模式進(jìn)行存儲，生成大數(shù)據(jù)文件及索引文件，以供調(diào)度使用。

通過以上4個步驟，即可生成紋理文件，紋理文件的組織方式與地形數(shù)據(jù)相類似。

3 地形多分辨率四叉樹模型調(diào)度機(jī)制

3.1 模型調(diào)度策略

并行處理技術(shù)是在同一時刻或同一時間間隔內(nèi)執(zhí)行或完成2種或2種以上性質(zhì)相同或不同的工作［6］。從工程角度考慮，采用計算機(jī)實現(xiàn)并行處理，多是在程序設(shè)計中構(gòu)建多線程機(jī)制，給各個線程分配任務(wù)，并利用約束條件使線程運行達(dá)到同步，由此實現(xiàn)線程的并行運行。

采用多線程并行機(jī)制對地形多分辨率四叉樹模型進(jìn)行調(diào)度，關(guān)鍵是如何分配任務(wù)，任務(wù)劃分不合理，反而會適得其反，另外多個調(diào)度任務(wù)還需設(shè)計機(jī)制進(jìn)行同步。多線程并行調(diào)度機(jī)制設(shè)計思路如圖9所示。

圖9 多線程調(diào)度模式

除主線程外，另創(chuàng)建9個分線程，其中:8個分線程負(fù)責(zé)調(diào)度區(qū)域1-8的地形數(shù)據(jù);剩余的1個分線程負(fù)責(zé)讀取索引文件，讀取結(jié)果供8個調(diào)度線程使用。

采用上述調(diào)度機(jī)制，線程9需與其余線程達(dá)到同步，線程9讀取到數(shù)據(jù)地址后，其余線程才可按照地址訪問數(shù)據(jù)，同步采用共享內(nèi)存的方式進(jìn)行實施，在內(nèi)存中共開辟10個狀態(tài)標(biāo)志位，分別記錄10個線程的工作狀態(tài)，操作關(guān)系如圖10所示。

圖10 線程-狀態(tài)標(biāo)志位操作關(guān)系

線程9對標(biāo)志位9進(jìn)行讀寫操作，記錄數(shù)據(jù)地址是否找到，主線程及線程1-8讀取標(biāo)志位9信息，而后判斷是否可讀取地形數(shù)據(jù);主線程及線程1-8對標(biāo)志位10及1-8進(jìn)行讀寫操作，線程9讀取標(biāo)志位10及標(biāo)志位1-8信息，而后可判斷是否可讀取新的地址信息。

3.2 調(diào)度觸發(fā)器

對于觀察者而言，視點距離決定調(diào)用不同級別的分辨率數(shù)據(jù)。人眼視角通常為120°，集中注意力時約為25°，視點越高，人眼可觀察區(qū)域越大，人眼觀察物體時，能清晰看清的視場區(qū)域?qū)?yīng)的分辨率為2 169×1 213(像素)，加上上下、左右比較模糊的區(qū)域，總的分辨率約在6 000×4 000(像素)［7］。從上述人眼的可視條件考慮，當(dāng)視點較高、觀察區(qū)域較大時，可調(diào)用低分辨率地形數(shù)據(jù)，若調(diào)用高分辨率地形數(shù)據(jù)，人眼無法辨析;當(dāng)視點拉近時，觀察區(qū)域變小，可充分利用人眼觀察能力，調(diào)用高分辨率地形數(shù)據(jù)。不同級別分辨率地形數(shù)據(jù)調(diào)度與觀察者視點高低存在映射關(guān)系，結(jié)合多次試驗，3個級別分辨率地形數(shù)據(jù)切換設(shè)置如圖11所示。

圖11 分辨率級別設(shè)定

4 實現(xiàn)效果

結(jié)合上述地形多分辨率四叉樹模型生成、存儲及調(diào)度機(jī)制，本文使用OSG對該模型進(jìn)行了實現(xiàn)，不同視點高度的顯示效果如圖12-14所示。

3幅圖分別為不同分辨率地形數(shù)據(jù)的顯示效果，當(dāng)觀察視點拉高、顯示地幅幅員變大時，動態(tài)調(diào)用低分辨率地形數(shù)據(jù)進(jìn)行渲染顯示;當(dāng)觀察視點降低、顯示地幅幅員變小時，調(diào)用高分辨率地形數(shù)據(jù)進(jìn)行顯示。從渲染幀時上分析，3種分辨率渲染幀時均大于30，畫面顯示流暢。

圖12 低分辨率地形可視化

圖13 中分辨率地形可視化

圖14 高分辨率地形可視化

5 結(jié)論

為實現(xiàn)高效處理大地形數(shù)據(jù)，本文構(gòu)建了地形多分辨率四叉樹模型，對模型的定義、存儲及調(diào)度機(jī)制進(jìn)行了闡述。模型中分辨率級別的設(shè)定要合理、適中，設(shè)定過多級別會造成數(shù)據(jù)量龐大、索引文件結(jié)構(gòu)復(fù)雜，不利于查找調(diào)用，而過少級別又會對渲染效果造成一定影響，分辨率級別大小需根據(jù)需求及硬件情況綜合考慮。

［1］ 王銳，錢學(xué)雷.OpenSceneGraph三維渲染引擎設(shè)計與實踐［M］.北京:清華大學(xué)出版社，2009:14-19.

［2］ 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，2005:157-178.

［3］ 韓元利.大區(qū)域DEM數(shù)據(jù)處理及其三維可視化應(yīng)用［D］.武漢:武漢大學(xué)，2004.

［4］ 張玉杰.大規(guī)模地形數(shù)據(jù)的組織與可視化研究［D］.鄭州:信息工程大學(xué)，2006.

［5］ 劉颯.基于Opengl的三維地形可視化技術(shù)研究［D］.大慶:大慶石油學(xué)院，2007.

［6］ 吳旭光.計算機(jī)仿真技術(shù)［M］.北京:化學(xué)工業(yè)出版社，2005:199-205.

［7］ 張起貴.人眼快速檢測技術(shù)［J］.電子設(shè)計工程，2010(9):63-64.