面向側(cè)面紋理的金字塔管理算法

孫立偉 袁昱緯 員建廈

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

關(guān)鍵詞：三維場(chǎng)景；側(cè)面紋理；鏈表；金字塔模型；地形

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2019）09-68-4

0引言

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

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

1研究現(xiàn)狀

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

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

2面向側(cè)面紋理的三維場(chǎng)景多分辨率金字塔模型

2.1總體思路

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

2.2預(yù)處理與多分辨率金字塔構(gòu)建過(guò)程

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

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

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

第4步：在編碼時(shí)需要增加額外信息，①塊所在層次；②塊在其層次中的編碼（，），即對(duì)軸和軸的坐標(biāo)；③分塊對(duì)應(yīng)側(cè)面信息的指針，如圖2所示。

2.3相關(guān)算法的執(zhí)行過(guò)程

（1）讀取頂視塊

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

（2）讀取側(cè)面信息

在查詢到各細(xì)節(jié)層次中的塊后，根據(jù)該塊中存儲(chǔ)的鏈表指針，依次讀取鏈表下的節(jié)點(diǎn)，以獲得該塊對(duì)應(yīng)的側(cè)面信息。

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

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

3實(shí)驗(yàn)仿真

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

（1）數(shù)據(jù)結(jié)構(gòu)構(gòu)建測(cè)試

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

從表1可以看出，采用本文管理模式時(shí)，還需對(duì)曾經(jīng)單獨(dú)管理的三維模型做預(yù)處理，才能達(dá)到采用統(tǒng)一的方法管理。另外，由于本文方法需要對(duì)傳統(tǒng)的三維模型進(jìn)行剖分，部分三角形格網(wǎng)會(huì)被“切開(kāi)”，因此，本文方法需要略多的存儲(chǔ)空間。

（2）隨機(jī)區(qū)域讀取測(cè)試

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

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

（3）綜合測(cè)試，考慮采用運(yùn)動(dòng)視角的幀速率進(jìn)行衡量

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

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

[4]馬駿，陳玉林.基于面向?qū)ο蟮姆植际竭b感數(shù)據(jù)存儲(chǔ)模型研究[J].河南大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，47（2）：185-193.

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

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

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

[8]陳華，夏青，蔣秉川，等.一種面向?qū)ο蟮娜蚨喾直媛始y理數(shù)據(jù)的預(yù)處理方法的研究[J].測(cè)繪科學(xué)，2008，33（S1）： 52-53，15.

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

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

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

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