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

2013-10-08 07:28:30吳東亞黃璽瑛夏永春

裝甲兵工程學院學報 2013年1期

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

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

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

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

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

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

圖1 四叉樹示例

地形多分辨率四叉樹模型是將同一塊地形數據按照不同分辨率進行分割存儲管理的數據結構模型，適用于矩形柵格DEM，分割前后地形數據分辨率呈倍數遞增關系，即分割后地形數據的網格間距是分割前網格間距的1/2。

矩形柵格DEM由地表規則網格單元構成［3］，結構如圖2所示。

圖2 矩形柵格DEM結構

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

根據建立模型分辨率的層級數，將地域進行相應分割。建立3級分辨率模型，先將A地域按面積均分為4塊，分別為 A1、A2、A3、A4，而后將該4塊地域繼續進行分割，生成16塊地域，最終形成了A地域的3級分辨率四叉樹模型，模型結構如圖4所示。

建立多分辨率層級結構后，需設計對應的存儲及調用機制，從而可按需調用不同分辨率的地形數據。

圖3 A地域

圖4 四叉樹分割模型

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

2.1 存儲結構

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

圖5 大文件存儲模式

索引文件負責記錄大文件中各個節點數據的相關信息，包括節點編碼、分辨率級別、存儲起始地址等信息，索引文件結構如圖6所示。

圖6 索引文件結構

圖6中各個節點均有一條索引記錄來記錄該節點的相關信息，記錄中的區域1-8地址信息為當前節點毗鄰地域DEM數據的存儲地址信息，如圖7所示，節點A索引記錄中的區域1-8地址信息依次記錄A1，…，A8地域DEM數據的存儲地址信息。

圖7 區域關系圖

2.2 DEM數據存儲處理

將DEM數據進行處理，生成上述存儲結構，即通過數據內插、分塊、合并等多種操作對DEM數據進行處理。DEM數據處理流程如圖8所示。

圖8 DEM數據處理流程

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

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

2.3 紋理數據存儲處理

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

1)定位。根據地形數據塊覆蓋的區域，確定相應的紋理圖片，即選取該地域的紋理圖片進行處理。

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

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

4)存儲。將生成的紋理文件按照對應的DEM數據存儲模式進行存儲，生成大數據文件及索引文件，以供調度使用。

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

3 地形多分辨率四叉樹模型調度機制

3.1 模型調度策略

并行處理技術是在同一時刻或同一時間間隔內執行或完成2種或2種以上性質相同或不同的工作［6］。從工程角度考慮，采用計算機實現并行處理，多是在程序設計中構建多線程機制，給各個線程分配任務，并利用約束條件使線程運行達到同步，由此實現線程的并行運行。

采用多線程并行機制對地形多分辨率四叉樹模型進行調度，關鍵是如何分配任務，任務劃分不合理，反而會適得其反，另外多個調度任務還需設計機制進行同步。多線程并行調度機制設計思路如圖9所示。

圖9 多線程調度模式

除主線程外，另創建9個分線程，其中:8個分線程負責調度區域1-8的地形數據;剩余的1個分線程負責讀取索引文件，讀取結果供8個調度線程使用。

采用上述調度機制，線程9需與其余線程達到同步，線程9讀取到數據地址后，其余線程才可按照地址訪問數據，同步采用共享內存的方式進行實施，在內存中共開辟10個狀態標志位，分別記錄10個線程的工作狀態，操作關系如圖10所示。

圖10 線程-狀態標志位操作關系

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

3.2 調度觸發器

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