李朝奎，方 軍，方 文，卜 璞

(1. 湖南科技大學(xué)地理空間信息技術(shù)國家地方聯(lián)合工程實驗室，湖南 湘潭 411201; 2. 湖南科技大學(xué)地理空間信息湖南省工程實驗室，湖南 湘潭 411201)

集群環(huán)境下基于視點(diǎn)移動的三維城市模型快速顯示方法

李朝奎1,2，方 軍1,2，方 文1,2，卜 璞1,2

(1. 湖南科技大學(xué)地理空間信息技術(shù)國家地方聯(lián)合工程實驗室，湖南 湘潭 411201; 2. 湖南科技大學(xué)地理空間信息湖南省工程實驗室，湖南 湘潭 411201)

大范圍三維城市模型數(shù)據(jù)在現(xiàn)有的單機(jī)運(yùn)行環(huán)境下，因數(shù)據(jù)量大導(dǎo)致運(yùn)行速度慢、計算耗時等難題。為解決該問題，本文結(jié)合集群并行運(yùn)算，提出了一種基于視點(diǎn)移動規(guī)則的大范圍三維城市模型的快速顯示方法。采用靜態(tài)細(xì)節(jié)層次簡化算法將三維城市模型簡化為4個分辨率層次，根據(jù)視點(diǎn)移動規(guī)律，利用距離和偏心率選擇不同層次的細(xì)節(jié)層次模型，逐級加載不同分辨率層次模型，并在集群系統(tǒng)中并行顯示，從而有效地解決了大范圍三維城市模型加載顯示過慢、場景效果跳躍等問題，實現(xiàn)了對大范圍三維城市模型的快速可視化。試驗結(jié)果表明：隨視點(diǎn)變化分層逐級加載不同等級LOD模型，采用PC集群并行繪制，可以快速有效地對大范圍三維城市模型進(jìn)行渲染處理，在兼顧效率的同時，并行地顯示模型的細(xì)節(jié)，具有良好的可視化效果，對智慧城市的建設(shè)具有重要的指導(dǎo)意義。

集群環(huán)境；視點(diǎn)移動；三維城市模型；快速顯示

隨著智慧城市和虛擬現(xiàn)實技術(shù)的快速發(fā)展，三維城市模型(three dimension city model，3DCM)在導(dǎo)航、交通及城市空間規(guī)劃等多方面起著至關(guān)重要的作用，它具有多種細(xì)節(jié)層次的三維幾何表達(dá)，并提供逼真的材質(zhì)和紋理特征及目標(biāo)的屬性信息。但由于目前三維城市模型數(shù)據(jù)量大、單機(jī)運(yùn)算處理時間長、顯示繪制壓力大，單機(jī)繪制和靜態(tài)算法已無法滿足日益增長的3DCM數(shù)據(jù)對其可視化的要求。因此，迫切需要研究大范圍3DCM的快速并行顯示方法。

Clark指出多細(xì)節(jié)層次模型(level of details,LOD)是解決大范圍3DCM的高精度表達(dá)困難最重要的方法之一[1]。目前，許多學(xué)者針對LOD簡化進(jìn)行了研究，簡化方法主要有頂點(diǎn)聚類法、幾何元素刪除法、頂點(diǎn)采樣法、小波分解法、聚類算法等[2-4]，通過這些方法可進(jìn)行模型簡化并實現(xiàn)三維模型的顯示。但上述方法的共同缺陷是丟失了一定量的精細(xì)信息，對于大范圍三維模型數(shù)據(jù)顯示速度較慢，不利于三維場景的快速顯示與可視化決策。

針對這些問題，本文通過構(gòu)建集群并行顯示系統(tǒng)，對3DCM進(jìn)行多分辨處理，生成多層次細(xì)節(jié)模型(LOD)，分析視點(diǎn)變化規(guī)律，并根據(jù)距離和偏心率選擇不同層次的三維模型，既能兼顧模型的顯示速度，又可表達(dá)較為完整的精細(xì)信息，實現(xiàn)了大范圍3DCM的集群并行快速顯示。

1 集群環(huán)境下視點(diǎn)移動模型繪制方法

1.1 構(gòu)建并行集群

集群就是通過高速網(wǎng)絡(luò)連接多臺相互獨(dú)立的計算機(jī)(節(jié)點(diǎn))，使多臺計算機(jī)作為一個整體向用戶提供網(wǎng)絡(luò)資源和服務(wù)。集群中各節(jié)點(diǎn)除了可以作為單一計算機(jī)供用戶使用，還可以協(xié)同作為一個整體使用。集群是一個系統(tǒng)，用戶無須了解集群系統(tǒng)內(nèi)部的節(jié)點(diǎn)和構(gòu)造，且集群系統(tǒng)的管理員可以隨意增加和刪改集群系統(tǒng)的節(jié)點(diǎn)。集群具有高可擴(kuò)展性、高可用性、高性能、高性價比等特點(diǎn)[5]。集群系統(tǒng)結(jié)構(gòu)[6]如圖1所示。

圖1 集群系統(tǒng)結(jié)構(gòu)

在集群系統(tǒng)中，選用一臺計算機(jī)作為主節(jié)點(diǎn)整體協(xié)調(diào)控制多臺子節(jié)點(diǎn)計算機(jī)，每臺計算機(jī)控制一個顯示屏。主節(jié)點(diǎn)負(fù)責(zé)將數(shù)據(jù)劃分至各個子節(jié)點(diǎn)，協(xié)調(diào)管理各個子節(jié)點(diǎn)的數(shù)據(jù)量大小和處理進(jìn)度，由各個子節(jié)點(diǎn)對分配到的數(shù)據(jù)進(jìn)行處理渲染并最終顯示。通過集群并行計算，可以有效地解決單一計算機(jī)硬件性能有限、計算能力不足等問題，實現(xiàn)大范圍3DCM快速處理顯示任務(wù)。

1.2 多分辨率三維模型

LOD是一種為了提高繪制速度，適度放棄精度的簡化方法，根據(jù)人眼分辨率的感知原理和視點(diǎn)的移動規(guī)律，對不同的視距采用不同精細(xì)程度的物體細(xì)節(jié)層次，達(dá)到漫游幀速流暢的目的。在構(gòu)建模型的細(xì)節(jié)層次時，要綜合考慮細(xì)節(jié)層次與數(shù)據(jù)量之間的關(guān)系[7]。細(xì)節(jié)層次太多，數(shù)據(jù)量相應(yīng)變大，不利于存儲管理；而細(xì)節(jié)層次太少，在場景切換時畫面呈跳躍感，影響場景的連續(xù)性。

目前常用的建立LOD的方法主要有靜態(tài)LOD和動態(tài)LOD兩種[8-10]。靜態(tài)LOD，即預(yù)先生成幾個層次的細(xì)節(jié)模型，在渲染時根據(jù)算法確定所需的分辨率及細(xì)節(jié)層次，這種方法繪制速度快，但需要存儲多個細(xì)節(jié)層次模型，占用過多的存儲空間，在模型切換的時畫面會有跳躍感；動態(tài)LOD，即通過模型簡化算法或迭代運(yùn)算生成任意多個連續(xù)的細(xì)節(jié)層次模型，從而得到相鄰的細(xì)節(jié)層次模型，模型切換時能夠保持很好的視覺平滑效果，但是算法復(fù)雜，計算量大，影響顯示速度，且目前并不能實現(xiàn)完全動態(tài)模型簡化。

雖然靜態(tài)LOD簡化需要占用較多的存儲空間，但在目前存儲空間足夠的情況下，可通過預(yù)先生成多層次細(xì)節(jié)模型，在渲染顯示時不需要再通過算法實現(xiàn)模型層次的構(gòu)建，進(jìn)而提高了運(yùn)行速度[11]。在大范圍3DCM渲染顯示時，不需要顯示全部的細(xì)節(jié)信息，無需將所有分辨率下的模型全部加載顯示，可以根據(jù)視點(diǎn)移動規(guī)律對模型進(jìn)行動態(tài)調(diào)度。

1.2.1 三維模型LOD簡化

3DCM主要由許多個三角面片組成，因此模型的簡化可以轉(zhuǎn)換為對三角面片的簡化。采用一種改進(jìn)的基于邊折疊簡化算法，依據(jù)小波曲面細(xì)分原理，并對邊折疊生成的新頂點(diǎn)提取矯正系數(shù)，對新頂點(diǎn)進(jìn)行修正[7]。圖2為邊折疊算法示意圖。

圖2 邊折疊算法示意圖

假設(shè)新生成頂點(diǎn)為X0(x0,y0,z0),頂點(diǎn)實際坐標(biāo)為X1(x1,y1,z1)，則矯正系數(shù)J就是X0與X1之差，即

J=X0(x0,y0,z0)-X1(x1,y1,z1)

(1)

根據(jù)上述算法，并參照《城市三維建模技術(shù)規(guī)范》，將三維模型簡化為4個LOD層次，并進(jìn)行存儲。表1為LOD細(xì)節(jié)層次分級。

表1 LOD細(xì)節(jié)層次分級

1.2.2 基于視點(diǎn)和距離選擇的LOD層次選擇

在進(jìn)行三維場景繪制時，視野的變化范圍隨著人眼視點(diǎn)的移動而移動。雖然視點(diǎn)的變化是隨機(jī)的，但是整體來說包含6種變化趨勢：沿著X軸的正、反方向的移動(沿X軸前進(jìn)或后退)，沿著Y軸的正、反方向的移動(沿Y軸前進(jìn)或后退)，沿著Z軸的正、反方向的移動(沿Z軸前進(jìn)或后退)[12-13]。將其投影至二維平面變化為向上、向下、向左、向右、左上、左下、右上、右下等幾種情況，如圖3所示。

圖3 視點(diǎn)變化情況

因此在進(jìn)行三維場景顯示時，可以根據(jù)視點(diǎn)位置及其變化趨勢對三維場景分級逐漸顯示。采用距離選擇法和偏心率選擇法相結(jié)合的方法選擇LOD細(xì)節(jié)層次。距離選擇法是根據(jù)場景內(nèi)視點(diǎn)距離模型的歐氏距離選擇合適的LOD模型，這是最簡單也最常用的一種方法。場景的精細(xì)程度隨著視點(diǎn)到模型距離的增大而減小，當(dāng)距離視點(diǎn)較遠(yuǎn)時，一些細(xì)節(jié)就變得不重要，可以選擇較低分辨率，甚至可以選擇不顯示。偏心率選擇法是根據(jù)視覺規(guī)律，通常居于視野中心的模型往往具有更高的關(guān)注度，可以選擇較高分辨率的細(xì)節(jié)模型，而居于邊緣的模型容易不被重視，選擇較低分辨率的細(xì)節(jié)模型。圖4(a)、圖4(b)分別為距離選擇法和偏心率選擇法的示意圖。

1.3 不同層次LOD模型加載

對構(gòu)建的不同層次三維模型進(jìn)行樹形結(jié)構(gòu)存儲和建立索引，便于后期加載繪制。集群系統(tǒng)采用4臺子節(jié)點(diǎn)，每臺節(jié)點(diǎn)控制一臺投影儀，將4臺投影儀進(jìn)行多屏拼接繪制。按投影屏幕范圍與模型顯示區(qū)域進(jìn)行換算，將屏幕范圍劃分為4塊進(jìn)行顯示，并在此基礎(chǔ)上再次劃分為16塊及64塊等更高等級。根據(jù)人眼觀察規(guī)律，視點(diǎn)通常位于屏幕中心，因此選擇屏幕中心作為初始視點(diǎn)，并以初始視點(diǎn)為中心進(jìn)行屏幕等級劃分。在視點(diǎn)移動規(guī)律下，可知通常上、下、左、右 4個方向是人眼視野最易變化的方向，由模型在這4個方向上距離初始視點(diǎn)的歐式距離作為判定模型分辨率等級的標(biāo)準(zhǔn)。與此同時，兼顧左上、左下、右上、右下 4種視點(diǎn)移動情況，將對這4個方向上(即對角線方向)的模型層次等級進(jìn)行一定的提高。以X軸、Y軸分別進(jìn)行八等分，取交點(diǎn)作為屏幕劃分依據(jù)，得到均勻劃分區(qū)域，不同屏幕區(qū)域?qū)?yīng)不同范圍下的三維模型，進(jìn)而計算得到不同等級屏幕區(qū)域所需加載顯示范圍。LOD模型分級加載顯示流程如下圖5所示。

圖4

將屏幕按照劃分規(guī)則劃分為4個等級(如圖6所示)，其中最小框線包含的區(qū)域(區(qū)域Ⅰ)是視點(diǎn)最關(guān)注區(qū)域，區(qū)域Ⅱ次之，區(qū)域Ⅲ進(jìn)一步模糊化，最外層區(qū)域Ⅳ采用LOD4。在模型顯示及變化時，先在整體范圍Ⅳ內(nèi)加載LOD4，區(qū)域Ⅲ進(jìn)一步加載LOD3，區(qū)域Ⅱ加載LOD2，區(qū)域Ⅰ加載LOD1。當(dāng)顯示區(qū)域穩(wěn)定不變后，根據(jù)需要按照Ⅱ、Ⅲ、Ⅳ的順序逐步加載更為精細(xì)的模型。

圖5 LOD模型分級加載顯示流程

圖6 屏幕等級劃分方案

2 試驗及結(jié)果分析

2.1 并行結(jié)果顯示

試驗采用的集群系統(tǒng)由1臺主節(jié)點(diǎn)機(jī)、4臺子節(jié)點(diǎn)機(jī)和4臺投影儀組成。所有節(jié)點(diǎn)計算機(jī)操作系統(tǒng)均為Windows 7，其中主節(jié)點(diǎn)內(nèi)存為4.00 GB，子節(jié)點(diǎn)內(nèi)存為2.00 GB。在集群系統(tǒng)中，通過主節(jié)點(diǎn)對4臺子節(jié)點(diǎn)進(jìn)行控制，每臺子節(jié)點(diǎn)連接一臺投影儀，利用4臺投影儀對模型進(jìn)行并行顯示，以解決單一計算機(jī)繪制時易產(chǎn)生卡頓、運(yùn)行緩慢等現(xiàn)象。試驗所使用的測試數(shù)據(jù)為自主構(gòu)建的三維城市場景模型。

使用OSG(OpenSceneGraph)三維描繪引擎對三維城市模型進(jìn)行管理渲染，通過OSG渲染流水線(依次遍歷操作、更新遍歷、揀選遍歷和繪制遍歷)，得到三維場景的渲染結(jié)果。將所有層次LOD模型一次載入，利用OSG中的PageLOD節(jié)點(diǎn)代替LOD節(jié)點(diǎn)，每一層分辨率模型只在顯示時加載，不顯示時可動態(tài)卸載[15-16]。采用改進(jìn)的邊折疊算法[7]對模型進(jìn)行簡化，構(gòu)建4個層次等級的LOD模型，并存儲在計算機(jī)節(jié)點(diǎn)中，由主節(jié)點(diǎn)對模型繪制過程進(jìn)行整體管理和調(diào)度。按照不同等級屏幕對應(yīng)的模型范圍，根據(jù)視點(diǎn)的選擇，每塊屏幕逐級加載對應(yīng)的不同等級LOD層次模型，并隨視點(diǎn)變化動態(tài)的加載符合重要度等級的LOD模型，卸載當(dāng)前等級LOD模型。待視點(diǎn)穩(wěn)定后，分區(qū)域逐級完成整個模型的加載及繪制。

2.2 結(jié)果及分析

3DCM在集群并行系統(tǒng)下的顯示效果如圖7所示。表2為原始未簡化三維模型和LOD簡化后模型的頂點(diǎn)數(shù)、面數(shù)、幀數(shù)等試驗結(jié)果?？梢钥闯觯ㄟ^簡化后的模型的三角面片數(shù)和頂點(diǎn)個數(shù)減少，模型數(shù)據(jù)量變小，為模型可視化提供了良好的數(shù)據(jù)準(zhǔn)備；利用分層逐級加載模式進(jìn)行場景加載，每塊模型根據(jù)視點(diǎn)重要度只在顯示使加載，不顯示時動態(tài)卸載，模型加載時間由21 s提升至8 s，能夠快速地渲染顯示；根據(jù)視點(diǎn)變化規(guī)律動態(tài)加載模型，運(yùn)行效率得到了大幅提高，幀率由18.9幀/s加速至30.1幀/s，能夠滿足連貫流暢的可視化效果。采用基于視點(diǎn)變化規(guī)律，通過距離選擇法與偏心率選擇法相結(jié)合的方法分層次、分區(qū)域的渲染顯示三維場景，能夠在較短時間內(nèi)完成3DCM的顯示，且具有良好的可視化效果。

圖7 3DCM集群并行環(huán)境顯示效果

表2 不同分辨率模型實驗結(jié)果對比

3 結(jié) 論

針對三維城市模型數(shù)據(jù)量大、運(yùn)行速度慢、計算壓力大等問題，對三維模型構(gòu)建了多層次細(xì)節(jié)模型，根據(jù)視點(diǎn)變化規(guī)律，結(jié)合距離選擇法與偏心率選擇法，對屏幕進(jìn)行劃分，按照劃分方案對三維模型分層次加載，在集群系統(tǒng)中并行地實現(xiàn)了3DCM的快速顯示。研究表明：

(1) 對三維場景進(jìn)行LOD簡化，可以大大減少模型的數(shù)據(jù)量。

(2) 基于視點(diǎn)的模型加載顯示可以有效地提高三維場景的顯示速率，且顯示連貫，沒有明顯的跳幀現(xiàn)象。

(3) 在集群系統(tǒng)中采用并行的方式對三維模型進(jìn)行處理，是一種快速有效的方法，可以大幅提高3DCM的處理顯示速度，提供流暢連貫的可視化效果。

隨著數(shù)字城市的快速發(fā)展，需要越來越精細(xì)的3DCM。如何解決大范圍模型數(shù)據(jù)的處理顯示，建立更連貫精細(xì)的LOD層次模型，以及利用GPU加速圖形的渲染等問題還需要進(jìn)一步研究；同時，在多屏幕顯示繪制中屏幕中間易產(chǎn)生裂縫，影響整體可視化效果，通過硬件軟件相結(jié)合的方法解決屏幕裂縫，實現(xiàn)多屏無縫可視化繪制將會是下一步研究方向。

[1] CLARK J.Hierarchical Geometric Models for Visible Surface Algorithms[J].Communications of the ACM，1976, 19(10):547-554.

[2] 俞凌云,王毅剛,王亢.大屏幕無縫拼接系統(tǒng)的應(yīng)用軟件平臺開發(fā)[J].計算機(jī)應(yīng)用,2008,28(9):2434-2436.

[3] 張志國.基于邊塌陷和頂點(diǎn)分裂的動態(tài)多分辨率網(wǎng)格生成[D].上海：上海交通大學(xué),2006.

[4] CHEN Huahong,LUO Xiaonan,LING Ruotian. Surface Simplifi-cation Using Multi-edge Mesh Collapse[C]∥International Conference on Image and Graphics.[S.l.]: IEEE, 2007:954-959.

[5] 石教英.分布式并行圖形繪制技術(shù)及其應(yīng)用[M].北京:科學(xué)出版社, 2010.

[6] 遲學(xué)斌.高性能并行計算[M].北京：中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心,2010.

[7] 楊武. 三維城市模型數(shù)據(jù)組織與存儲方法研究[D].湘潭：湖南科技大學(xué),2014.

[8] 朱慶,龔俊,杜志強(qiáng),等.三維城市模型的多細(xì)節(jié)層次描述方法[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2005,30(11):965-969.

[9] ASTHEIMER P， P?CHE M.Level of Detail Generation and Its Applications in Virtual Reality[C]∥Conference on Virtual Reality Software and Technology.[S.l.]: World Scientific Publishing, 1994.

[10] 費(fèi)紅輝,王毅剛.大規(guī)模場景分割及LOD結(jié)構(gòu)生成算法研究[J].計算機(jī)應(yīng)用與軟件, 2012,29(7):227-230.

[11] 付燕平,羅明宇,劉其軍.大數(shù)據(jù)三維模型快速顯示技術(shù)研究[J].計算機(jī)技術(shù)與發(fā)展, 2015(5):87-90.

[12] 殷智慧. 三維空間數(shù)據(jù)存儲技術(shù)與動態(tài)調(diào)度機(jī)制研究[D].湘潭：湖南科技大學(xué),2014.

[13] 李擁.基于 OpenMP 的三維城市模型并行繪制研究[D].湘潭：湖南科技大學(xué).2013.

[14] 龔俊,朱慶,張葉廷,等.顧及多細(xì)節(jié)層次的三維 R 樹索引擴(kuò)展方法[J].測繪學(xué)報,2011,40(2):249-255.

[15] 聶小波,邢光成,陳濤,等.OpenGL 及其在 DEM 可視化中的應(yīng)用[J].地理空間信息,2009,7(3):48-50.

[16] 王銳,錢學(xué)雷. OpenSceneGraph三維渲染引擎設(shè)計與實現(xiàn)[M]. 北京:清華大學(xué)出版社,2009:74-86.

TheFastDisplayMethodfor3DCMBasedontheViewpointMovinginClusterEnvironment

LI Chaokui1,2，F(xiàn)ANG Jun1,2，F(xiàn)ANG Wen1,2，BU Pu1,2
(1. National-local Joint Engineering Laboratory of Geo-spatial Information Technology, Hunan University of Science and Technology, Xiangtan 411201, China; 2. Hunan Province Engineering Laboratory of Geospatial Information, Hunan University of Science and Technology, Xiangtan 411201, China)

With the rapid development of digital city construction, as the core content of digital city,3DCM has the characteristics of large amount of data, slow running speed, great calculation pressure and so on in the existing computer’s running environment.To solve these problems, combined with the parallel computing, a new fast display method for 3DCM based on the viewpoint move rules is proposed.Using static LOD simplification algorithm to simplify the 3DCM to four resolution level.Based on the viewpoint move rules, the LOD model was selected and gradual loading according to the distance and the eccentricity ratio.The results were parallel displaying in the cluster system, which effectively solves the problems of slow load display and scene jumping for large-scale 3DCM,achieved the fast display of large scale 3DCM.Experimental results show that this method can quickly and effectively deal with large-scale 3DCM rendering, while taking into account the efficiency and showing the details of the model, has a good visual effect, which has important significance for the development of digital city.

cluster environment; viewpoint moving; 3DCM;fast display

李朝奎，方軍，方文，等.集群環(huán)境下基于視點(diǎn)移動的三維城市模型快速顯示方法[J].測繪通報，2017(10)：74-78.

10.13474/j.cnki.11-2246.2017.0319.

2017-02-17

國家自然科學(xué)基金(41271390)；湖南省研究生創(chuàng)新基金(CX2016B541)；湖南省重點(diǎn)實驗室開放基金項目(JL16K01；CT16K02)；湖南省教育廳重點(diǎn)項目(16A070)

李朝奎(1967—)，男，教授，研究方向為GIS理論方法及其應(yīng)用。E-mail：616059644@qq.com

P208

A

0494-0911(2017)10-0074-05