面向側面紋理的金字塔管理算法

孫立偉 袁昱緯 員建廈

摘要：針對傳統(tǒng)三維場景管理方法中易損失側面紋理的問題，提出了一種改進的多分辨率金字塔模型。從傳統(tǒng)的金字塔模型出發(fā)，采用鏈表結構對模型結構的頂點進行拓展，首先是場景構造瓦片四叉樹，對海量地形數(shù)據(jù)中的正射影像部分進行金字塔模型下的分塊和分層管理；然后對基于金字塔模型下的分塊場景的三維地形進行預處理，并從每個地形分塊節(jié)點出發(fā)采用指針鏈表管理三維場景的幾何信息和側面紋理信息。在三維場景下進行了試驗，試驗表明顯示效率有顯著提高，已應用于工程實踐。

關鍵詞：三維場景；側面紋理；鏈表；金字塔模型；地形

中圖分類號：TP393文獻標志碼：A文章編號：1008-1739（2019）09-68-4

0引言

多分辨率金字塔模型是一種典型的層次結構，能夠在同一空間參照下，根據(jù)用戶需求按照分辨率從高到低、規(guī)模由大到小對數(shù)據(jù)進行不同分辨率的管理，已被廣泛應用于三維地理信息系統(tǒng)[1-2]、地形動態(tài)繪制[3]、海量空間數(shù)據(jù)存儲[4-5]及影像處理[6]等領域。

近年來，隨著計算機計算能力和存儲容量的大幅提升，人們對于高質量三維場景的需求越來越迫切，對需要組織數(shù)據(jù)的類型越來越多，數(shù)據(jù)的規(guī)模和精細程度也越來越高，尤其是對三維場景中的側面紋理。三維場景通常采用多分辨率金字塔模型實現(xiàn)高效存儲、管理與組織，以提供不同分辨率的地形數(shù)據(jù)。傳統(tǒng)的地形金字塔模型是基于遙感正射影像和數(shù)字高程模型進行的[7]，用于顯示的地形圖像均為俯視遙感正射影像[8]，僅能管理單一的數(shù)據(jù)類型，難以解決數(shù)字高程和三維模型帶來的側面紋理問題。

1研究現(xiàn)狀

不少學者針對傳統(tǒng)金字塔模型的不足，提出了相應的改進方法。晏雄鋒等[9]通過結合多尺度表達數(shù)據(jù)結構和空間索引等策略，提出了矢量金字塔模型，實現(xiàn)了空間數(shù)據(jù)連續(xù)尺度的表達，但該模型對三維場景的側面紋理管理能力較弱。田珊珊等[10]以影像數(shù)據(jù)為出發(fā)點來組織數(shù)據(jù)，提出了一種改進的基于數(shù)據(jù)庫的數(shù)據(jù)組織方法，但該方法需要對側面紋理進行裁剪和正射校正，會損失部分高分辨率側面紋理信息。鮑鵬等[11]提出一種基于嵌入式金字塔模型的三維數(shù)據(jù)組織方法，僅在邏輯層面對海量異構的三維場景進行統(tǒng)一管理，沒有對存儲方式進行論述。姜代紅等[12]采用數(shù)據(jù)鏈表對分層、分塊數(shù)據(jù)進行組織和內存調度，實現(xiàn)了地圖動態(tài)漫游。

本文從傳統(tǒng)的金字塔模型出發(fā)，采用鏈表結構對模型結構的頂點進行拓展，提出了一種改進的多分辨率金字塔模型。這種模型結構可以將側面紋理同正射影像在同一金字塔模型結構下進行管理，具有較高的組織管理效率，同時能夠保證更高質量的側面紋理。

2面向側面紋理的三維場景多分辨率金字塔模型

2.1總體思路

算法設計的總體思路是結合多分辨率金字塔模型、擴展和改進瓦片四叉樹，并結合指針鏈表算法，提出2級瓦片四叉樹和鏈表相結合的索引，用于三維場景的管理。對海量地形數(shù)據(jù)中的頂視部分進行2步分層、分塊處理，在此基礎上構建數(shù)據(jù)的2級索引編碼，并對每個頂視部分的分塊節(jié)點采用指針鏈表管理三維場景的側面信息。

2.2預處理與多分辨率金字塔構建過程

第1步：將地形數(shù)據(jù)進行投影變換和分塊。針對原始分辨率的地形數(shù)據(jù)，先將數(shù)據(jù)平移到平面坐標原點，在水平及豎直方向按照大小2×2進行初級剖分（通常取8或9）。利用面片的水平方向和豎直方向的編號形成格網索引第一級編碼（，），其中，為指定分塊在軸的坐標，為指定分塊在軸的坐標。

第2步：以初級劃分面片為基礎，每一塊構建局部瓦片四叉樹的層次細節(jié)模型形成次級劃分面片。如圖1所示，圖左邊的初級劃分形成的每塊都對應圖右邊分層、分塊構成的一個四叉樹，形成金字塔狀的數(shù)據(jù)模型，再對局部四叉樹中的數(shù)據(jù)進行第2級編碼。

第3步：在第2步構建金字塔數(shù)據(jù)模型的過程中，需要遍歷每一個節(jié)點，在遍歷節(jié)點時，對同屬于不同節(jié)點的三角形格網按照格網邊界進行切分，每個節(jié)點僅對應落在其內部的三角形面片。

第4步：在編碼時需要增加額外信息，①塊所在層次；②塊在其層次中的編碼（，），即對軸和軸的坐標；③分塊對應側面信息的指針，如圖2所示。

2.3相關算法的執(zhí)行過程

（1）讀取頂視塊

在進行影像劃分時，將塊大小規(guī)定為2的次冪，有利于數(shù)據(jù)的快速檢索。當應用給定所需區(qū)域的世界坐標后，要確定它屬于哪個初級分塊，只需要取其軸和軸方向坐標二進制值的第位以上的數(shù)字即可直接對應到塊，而不需進行附加變換和判斷。

（2）讀取側面信息

在查詢到各細節(jié)層次中的塊后，根據(jù)該塊中存儲的鏈表指針，依次讀取鏈表下的節(jié)點，以獲得該塊對應的側面信息。

在按照鏈表順序讀取側面信息時，可以同時考慮基于視點的裁剪，減少進入渲染時的數(shù)據(jù)量。讀取鏈表節(jié)點的過程如圖3所示。

在讀取每一個鏈表節(jié)點時，首先判讀該側面的法線方向是否是正對視點方向，如果是則繼續(xù)讀取其角點位置，并判斷其對視點的可見性；如果法線方向不是正對視點方向，或者對視點不可見，則直接跳過該鏈表節(jié)點并讀取下一個。如果法線方向正對視點方向，并且對視點可見，則繼續(xù)讀取該側面的材質，并進行渲染計算，在鏈表中進行下一個節(jié)點的讀取。

3實驗仿真

實驗硬件環(huán)境為Intel Xeon CPU E3-1271 V3 3.60 GHz，8 G內存，NVIDIA Quadro K2200顯卡，軟件環(huán)境為Windows7。本文選取場景A、場景B和場景C這3個典型實驗場景，數(shù)據(jù)規(guī)模分別為151.22，343.87，1 156.03MB，預處理前的三角形面片分別為71 401，304 112，1 241 514。

（1）數(shù)據(jù)結構構建測試

對3個典型場景分別采用傳統(tǒng)方式[1]（管理結構中的頂視影像、模型單獨管理）和本文方法（頂視影像和模型共同使用本文方法管理）構建管理結構，對比分析2種方法消耗的存儲空間和構建的時間，如表1所示。

從表1可以看出，采用本文管理模式時，還需對曾經單獨管理的三維模型做預處理，才能達到采用統(tǒng)一的方法管理。另外，由于本文方法需要對傳統(tǒng)的三維模型進行剖分，部分三角形格網會被“切開”，因此，本文方法需要略多的存儲空間。

（2）隨機區(qū)域讀取測試

讀取隨機區(qū)域影像塊和三維模型，測算包括讀取的數(shù)據(jù)量，以及讀取、渲染、顯示在內的時間。實驗時，本文方法和傳統(tǒng)方法[1]隨機選取10個相同的區(qū)域進行顯示、對比和實驗，并計算平均值。實驗結果如表2所示。

從表2的實驗數(shù)據(jù)中可以看出，采用傳統(tǒng)管理模式時，需要首先讀出指定區(qū)域的全部頂視圖和三維模型，然后再進行渲染和顯示。在本文方法的讀取中，一邊判斷一邊讀取三維模型分塊，讀取階段本文方法需要耗費略長時間，但是由于本文方法對不需要渲染和顯示的三維模型面片進行了剪枝，較大地減輕了后續(xù)渲染和顯示時的計算量（減少量一般在50%左右或以上），所以讀取顯示的總時間要少很多。

（3）綜合測試，考慮采用運動視角的幀速率進行衡量

分別采用傳統(tǒng)方法[1]和本文方法構建典型場景，采用運動視角飛過場景上方，得到三維場景顯示時的幀速率。可以考慮對初始時、平緩地表區(qū)、地表劇烈變化區(qū)1、地表劇烈變化區(qū)2進行實驗，結果如表3所示。

從表3的實驗數(shù)據(jù)可以看出，在初始階段，采用傳統(tǒng)方法和本文方法的幀速率相差不大；平緩地表區(qū)漫游過程中，主要只有塊查找的差異，本文方法減少的塊讀取量和渲染計算時間在整個繪制過程中所占比重較小。但是當視點移動到2個劇烈變化地表區(qū)時，傳統(tǒng)方法的管理結構需要裝入更多的頂視影像和三維模型數(shù)據(jù)，因此幀速下降，本文方法的優(yōu)勢較為明顯。

4結束語

本文提出的多分辨率金字塔管理算法有效地解決了三維場景中側面紋理顯示和渲染問題，該算法已經應用于三維場景展現(xiàn)的工程實踐中，顯示效率較傳統(tǒng)方式有明顯提高，尤其在地形變化劇烈的區(qū)域，應用效果更為顯著。

參考文獻

[1]霍亮，楊耀東，劉小勇，等.瓦片金字塔模型技術的研究與實踐[J].測繪科學， 2012，37（6）：144-146.

[2]魏磊，張建新.基于ArcGIS Engine無冗余地圖瓦片裁切方法的研究[J].測繪與空間地理信息，2016，39（5）：146-148.

[3]何榮茂，石川，常文泰，等.基于OSG的大規(guī)模地形動態(tài)繪制應用研究[J].計算機與數(shù)字工程，2017，45（10）：2022-2026.

[4]馬駿，陳玉林.基于面向對象的分布式遙感數(shù)據(jù)存儲模型研究[J].河南大學學報（自然科學版），2017，47（2）：185-193.

[5]袁昱緯，全吉成，吳婧文，等.基于小波變換的改進影像金字塔模型[J].電子設計工程，2012，20（11）：183-186.

[6]房曉東.一種基于顯著性區(qū)域的圖像分割算法[J].火力與指揮控制，2016，41（7）：48-51.

[7]朱留果，何衛(wèi)紅，阮曉雨，等.基于WorldWind與無人機影像的三維場景重建與漫游研究[J].現(xiàn)代測繪，2012，35（5）：48-50.

[8]陳華，夏青，蔣秉川，等.一種面向對象的全球多分辨率紋理數(shù)據(jù)的預處理方法的研究[J].測繪科學，2008，33（S1）： 52-53，15.

[9]晏雄鋒，艾廷華，張翔，等.空間數(shù)據(jù)連續(xù)尺度表達的矢量金字塔模型[J].武漢大學學報（信息科學版），2018，43（4）： 502-508.

[10]田珊珊，王慧青，張小國.大規(guī)模地形數(shù)據(jù)實時回執(zhí)的技術研究[J].控制工程，2018，25（2）：224-230.

[11]鮑鵬，霍亮，王銳，等.基于嵌入式金字塔模型的城市三維數(shù)據(jù)組織方法研究[J].北京建筑大學學報，2017，33（4）：33-38.

[12]姜代紅.基于影像金字塔的GIS地圖動態(tài)漫游算法[J].計算機工程與設計，2013，34（5）：1711-1715.