基于OSG的地形多分辨率四叉樹模型

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

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

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

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

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

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

圖1 四叉樹示例

地形多分辨率四叉樹模型是將同一塊地形數(shù)據(jù)按照不同分辨率進(jìn)行分割存儲(chǔ)管理的數(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個(gè)特點(diǎn):一是除葉子節(jié)點(diǎn)外，其余節(jié)點(diǎn)都擁有4個(gè)子節(jié)點(diǎn);二是4個(gè)子節(jié)點(diǎn)將父節(jié)點(diǎn)地幅按面積均分為4份。下面以如圖3中所示的A地域?yàn)槔?，建?級(jí)分辨率四叉樹模型。

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

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

圖3 A地域

圖4 四叉樹分割模型

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

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

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

圖5 大文件存儲(chǔ)模式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)現(xiàn)效果

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

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

圖12 低分辨率地形可視化

圖13 中分辨率地形可視化

圖14 高分辨率地形可視化

5 結(jié)論

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

［1］ 王銳，錢學(xué)雷.OpenSceneGraph三維渲染引擎設(shè)計(jì)與實(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ì)算機(jī)仿真技術(shù)［M］.北京:化學(xué)工業(yè)出版社，2005:199-205.

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