文/李秀怡

基于多細(xì)節(jié)層次結(jié)構(gòu)擴(kuò)展合并的快速三維可視化方法

文/李秀怡

三維模型可視化技術(shù)近年來(lái)得到迅速發(fā)展，已經(jīng)應(yīng)用于如游戲、地理信息系統(tǒng)、電子商務(wù)展示等多個(gè)領(lǐng)域。隨著移動(dòng)終端的普及以及大數(shù)據(jù)時(shí)代的到來(lái)，對(duì)三維模型實(shí)時(shí)顯示的速度和精度不斷提出更高的要求。本文通過(guò)建立多細(xì)節(jié)層次結(jié)構(gòu)，依據(jù)最小距離實(shí)現(xiàn)對(duì)相鄰三維模型的擴(kuò)展合并，以減少讀取模型的數(shù)據(jù)量，達(dá)到簡(jiǎn)化模型的目的。通過(guò)實(shí)驗(yàn)研究證明，將其應(yīng)用于三維可視化可以提高三維模型顯示效率。

三維可視化 多細(xì)節(jié)層次模型 擴(kuò)展合并

隨著計(jì)算機(jī)視覺(jué)技術(shù)的快速發(fā)展，以及人們對(duì)信息實(shí)時(shí)共享和用戶體驗(yàn)感受需求的不斷提升，三維模型可視化技術(shù)近年來(lái)得到迅速發(fā)展，已經(jīng)應(yīng)用于如游戲、地理信息系統(tǒng)、電子商務(wù)展示等多個(gè)領(lǐng)域。三維模型的可視化功能對(duì)于路徑導(dǎo)航、位置查詢(xún)，以及信息展示有著重要的推動(dòng)作用，在移動(dòng)服務(wù)領(lǐng)域有著廣闊的應(yīng)用前景，人們可以通過(guò)移動(dòng)終端設(shè)備獲得當(dāng)前所處城市位置，并獲得身臨其境的三維可視化服務(wù)（如信息推薦、商品展示以及室內(nèi)導(dǎo)航等），極大地提高了三維模型可視化技術(shù)的普及率。然而，由于一些客觀條件的影響，比如移動(dòng)設(shè)備計(jì)算和存儲(chǔ)能力較弱、無(wú)線網(wǎng)絡(luò)帶寬較小等，都會(huì)影響三維模型處理處理與顯示的速度，降低客戶端顯示效果，影響用戶體驗(yàn)度。而三維模型數(shù)據(jù)的傳輸和大量計(jì)算也需要較高配置要求，這些因素都可能阻礙三維可視化技術(shù)應(yīng)用成果的普及。

為此，在本文中我們提出一種對(duì)多細(xì)節(jié)層次模型進(jìn)行擴(kuò)展合并的算法，基于此算法實(shí)現(xiàn)三維模型的快速動(dòng)態(tài)可視化。這種方法可以在減少傳輸數(shù)據(jù)的同時(shí)，盡可能保留原模型的視覺(jué)特征，并且可以根據(jù)用戶視點(diǎn)選擇需要可視化的模型細(xì)節(jié)層次。在此過(guò)程中，三維模型的大小和清晰度可以隨著用戶視點(diǎn)而發(fā)生動(dòng)態(tài)變化。

1 三維模型的多細(xì)節(jié)層次模型的產(chǎn)生

細(xì)節(jié)層次(Level ofDetail,簡(jiǎn)稱(chēng)LOD)模型是指對(duì)同一個(gè)場(chǎng)景或場(chǎng)景中的物體,使用具有不同細(xì)節(jié)的描述方法得到一組模型,供繪制時(shí)選擇使用。由于人們通常用多邊形網(wǎng)格(特例為三角形網(wǎng)格)來(lái)描述場(chǎng)景中的圖形物體,因而LOD模型自動(dòng)生成模型就轉(zhuǎn)化為三維多邊形網(wǎng)格簡(jiǎn)化問(wèn)題。為物體提供不同的LOD描述是控制場(chǎng)景復(fù)雜度和加速圖形繪制速度的一個(gè)非常有效的方法, LOD模型在復(fù)雜3D場(chǎng)景的快速繪制、飛行模擬器、3D動(dòng)畫(huà)、交互式可視化和虛擬現(xiàn)實(shí)等領(lǐng)域得到廣泛應(yīng)用。

LOD的生成可以追溯到20世紀(jì)80年代。1982年，Rubin[2]結(jié)合光線跟蹤算法，提出了復(fù)雜場(chǎng)景的層次表示算法及相關(guān)的繪制算法,從而使計(jì)算機(jī)能以較少的時(shí)間繪制復(fù)雜場(chǎng)景。90年年代以后，隨著虛擬現(xiàn)實(shí)和數(shù)據(jù)可視化等計(jì)算機(jī)新興領(lǐng)域的出現(xiàn)，對(duì)交互式圖形應(yīng)用系統(tǒng)的圖形生成速度提出更高的要求，隨之掀起了對(duì)多LOD生成技術(shù)的研究熱潮，諸多研究人員提出了很多有意義的研究結(jié)果。

2 三維可視化技術(shù)發(fā)展與應(yīng)用

自從三維可視化技術(shù)得到廣泛應(yīng)用以來(lái)，在三維模型實(shí)現(xiàn)的算法精度與繪制速度之間一直存在著矛盾。雖然隨著計(jì)算機(jī)新技術(shù)的發(fā)展不斷有新算法提出，可以一定程度上緩解這種矛盾。但是大數(shù)據(jù)時(shí)代的到來(lái)，使三維場(chǎng)景應(yīng)用的數(shù)據(jù)量急速膨脹，面向各種移動(dòng)終端的應(yīng)用需求也迅速擴(kuò)展，使這種矛盾又變得突出起來(lái)。

目前的三維可視化技術(shù)水平，在處理醫(yī)學(xué)影像、生物試驗(yàn)數(shù)據(jù)以及工程數(shù)據(jù)等方面配備優(yōu)越的硬件設(shè)備，可以實(shí)現(xiàn)海量數(shù)據(jù)的顯示與漫游，透視數(shù)據(jù)的內(nèi)部細(xì)節(jié)，還可以對(duì)動(dòng)靜態(tài)分子結(jié)構(gòu)數(shù)據(jù)進(jìn)行可視化分析。目前的可視化技術(shù)手段已經(jīng)深入化工、生物化學(xué)、制藥等行業(yè)，應(yīng)用于機(jī)械設(shè)計(jì)、通信、輔助設(shè)計(jì)領(lǐng)域，游戲、大地測(cè)量等領(lǐng)域，已經(jīng)展示了其獨(dú)特的優(yōu)越性，取得了有目共睹的良好效果。

傳統(tǒng)意義上的三維可視化技術(shù)是指運(yùn)用計(jì)算機(jī)圖形學(xué)和圖像處理技術(shù),將三維空間數(shù)據(jù)轉(zhuǎn)換為二維圖像或圖形模型,并在計(jì)算機(jī)上顯示、處理及交互的理論、方法和技術(shù)。而隨著相關(guān)數(shù)據(jù)技術(shù)的不斷深入發(fā)展，三維可視化技術(shù)在注重系統(tǒng)功能的同時(shí)也越來(lái)越注重用戶的視覺(jué)體驗(yàn)度。當(dāng)前三維可視化應(yīng)用系統(tǒng)的基本框架包括數(shù)據(jù)采集與處理模塊、三維模型生成模塊和面向用戶的瀏覽模塊。本文的重點(diǎn)工作內(nèi)容在后兩部分，對(duì)三維模型細(xì)節(jié)進(jìn)行相應(yīng)處理，然后應(yīng)用于可視化平臺(tái)。

3 多細(xì)節(jié)層次結(jié)構(gòu)擴(kuò)展合并

3.1 三維場(chǎng)景模型間相鄰關(guān)系檢測(cè)

通過(guò)語(yǔ)義網(wǎng)格對(duì)三維場(chǎng)景中顯示模型的全連接圖進(jìn)行剪枝分割，對(duì)分割后的連通子圖，采用三角網(wǎng)生長(zhǎng)算法生成Delaunay三角網(wǎng)。Delaunay三角網(wǎng)檢測(cè)相鄰關(guān)系具有以下特性：最接近、唯一性、最優(yōu)性、最規(guī)則、區(qū)域性以及具有圖多面體的外殼。圖1給出了一個(gè)Delaunay三角網(wǎng)的示例。從圖1中可以看出，Delaunay三角網(wǎng)能夠較為準(zhǔn)確的檢測(cè)出模型之間的空間相鄰關(guān)系，再通過(guò)對(duì)三角網(wǎng)的分割，刪除節(jié)點(diǎn)不屬于同一類(lèi)型的邊，則能準(zhǔn)確找出模型之間的語(yǔ)義空間相鄰關(guān)系，為模型合并做好準(zhǔn)備。

圖2：多細(xì)節(jié)層次模型生成

表1：動(dòng)態(tài)可視化時(shí)間（毫秒）

3.2 多細(xì)節(jié)層次模型的生成與合并

在相鄰關(guān)系的基礎(chǔ)上，通過(guò)將最近的模型進(jìn)行合并，從而生成多細(xì)節(jié)層次模型，如圖2所示。圖2中圓形表示原始三維模型。合并順序的選擇如下：計(jì)算每個(gè)模型之間的距離，按照距離由小到大的順序進(jìn)行合并，每一次合并后重新計(jì)算模型間的距離，并進(jìn)行調(diào)整。具體而言，合并后節(jié)點(diǎn)的相鄰節(jié)點(diǎn)是其子節(jié)點(diǎn)相鄰節(jié)點(diǎn)的集合，合并后節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)之間的距離為其所有子節(jié)點(diǎn)與該相鄰節(jié)點(diǎn)之間的最小距離。

模型之間的距離計(jì)算遵循如下原則：

（1）模型間距離為三維距離，充分考慮模型在三維空間的分布；

（2）模型間距離為模型所有幾何特征之間的最近距離，即充分考慮模型本身的大?。?/p>

（3）模型間距離考慮模型的語(yǔ)義距離，即如果模型之間被網(wǎng)格分割，則模型間距離為無(wú)窮大。

按照上述方法生成多細(xì)節(jié)層次模型如下：模型1,2距離最近，首先進(jìn)行合并生成D，然后4與5合并生成C，D與3合并后生成B，最后C與B合并生成A。

生成多細(xì)節(jié)層次模型之后，實(shí)現(xiàn)基于擴(kuò)展的合并。設(shè)待合并模型為A與B，則分別對(duì)A與B的邊進(jìn)行延伸與連接，選擇其中能夠相交的模型，并計(jì)算相交后體積的增量，選擇增量最小的模型作為合并后的結(jié)果。

對(duì)于一個(gè)二維模型合并情況的示例如圖3所示。通過(guò)對(duì)邊的延長(zhǎng)，從而實(shí)現(xiàn)模型的合并。對(duì)于三維模型，則需要在每個(gè)平面上進(jìn)行相應(yīng)的操作。

圖3：基于擴(kuò)展的合并算法

4 快速三維可視化

多細(xì)節(jié)層次模型可以使用離線的方式生成，生成后存儲(chǔ)于服務(wù)器，在需要時(shí)可以直接實(shí)現(xiàn)動(dòng)態(tài)可視化，因此具有較高的效率。

基于合并后的模型實(shí)現(xiàn)快速三維可視化過(guò)程如下：

首先獲取用戶當(dāng)前視點(diǎn)位置；基于多細(xì)節(jié)層次模型的根節(jié)點(diǎn)計(jì)算視點(diǎn)的角度是否包含，如不包含則不進(jìn)行可視化；如果包含，則計(jì)算當(dāng)前視點(diǎn)距多細(xì)節(jié)層次模型根節(jié)點(diǎn)之間的距離與根節(jié)點(diǎn)面積之比r，如果r大于所預(yù)設(shè)的值，則將根節(jié)點(diǎn)標(biāo)注為可視并返回，否則，對(duì)于根節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行上述計(jì)算與比較，并根據(jù)r與預(yù)設(shè)值的比較實(shí)現(xiàn)迭代處理，直到全部節(jié)點(diǎn)返回并選擇出可視節(jié)點(diǎn)。預(yù)設(shè)值可以根據(jù)不同應(yīng)用進(jìn)行靈活調(diào)整，從而實(shí)現(xiàn)自適應(yīng)的多細(xì)節(jié)層次結(jié)構(gòu)。

在可視化實(shí)現(xiàn)過(guò)程中，將所要展示三維的多細(xì)節(jié)層次模型結(jié)構(gòu)傳輸?shù)綖g覽器，該結(jié)構(gòu)不包括具體的幾何信息只包含節(jié)點(diǎn)的相互關(guān)系與節(jié)點(diǎn)所指向的具體三維模型ID。然后獲取用戶當(dāng)前視點(diǎn)并基于該視點(diǎn)與系統(tǒng)性能，在連續(xù)細(xì)節(jié)層次模型的架構(gòu)上選擇所需要載入的三維模型，并檢測(cè)本地緩存中是否已載入，如沒(méi)有則利用Websocket[7]將所需模型從服務(wù)器端載入并存儲(chǔ)于本地緩存中。

5 實(shí)驗(yàn)結(jié)果

表1給出了本文所提出的算法對(duì)于三維模型可視化效率的提高實(shí)驗(yàn)，從中可以看出通過(guò)采用多細(xì)節(jié)層次模型，能夠減少可視化耗時(shí)達(dá)到60%以上。

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

隨著大數(shù)據(jù)時(shí)代的到來(lái)和圖形圖像技術(shù)的飛速發(fā)展，對(duì)三維模型實(shí)時(shí)顯示的速度和精度不斷提出更高的要求。本文通過(guò)建立多細(xì)節(jié)層次結(jié)構(gòu)模型，依據(jù)最小距離實(shí)現(xiàn)對(duì)相鄰三維模型的擴(kuò)展合并，以減少讀取模型的數(shù)據(jù)量和簡(jiǎn)化模型，進(jìn)而達(dá)到提高三維可視化性能。今后將在三維模型紋理壓縮等方面進(jìn)行更深入研究，以期待更好的研究效果。

[1]潘志庚,馬小虎,石教英.多細(xì)節(jié)層次模型自動(dòng)生成技術(shù)綜述[J].軟件學(xué)報(bào),1998,3(09).

[2]Run in SM.The representation and display of sense with a wide range of detail,The Graphics and Image Processing,1982(19):291-299.

[3]Hansen CD.The Visualization Handbook[M].Burlington:Elsevier Butterworth Heinemann,2005:30-34.

[4]朱恒.關(guān)于數(shù)字城市三維建?？梢暬夹g(shù)分析[J].遙感測(cè)繪,2017(01).

[5]章孝燦,黃智才,戴企成,潘云鶴.GIS中基于拓?fù)浣Y(jié)構(gòu)和凸殼技術(shù)的決速TIN生成算法[J].計(jì)算機(jī)學(xué)報(bào),2002.

[6]Bo Mao,Yifang Ban.Web-based Visualisation of the Generalised 3D City Models using HTML5 an X3DOM.

[7]Bo Mao,Zhiang Wu,Jie Cao.A Framework For online Spatio-Temporal data Visualization Based on HTML5. International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences, Volume XXXIX-B2,2012.XXII ISPRS Congress,25 August-01 September 2012,Melbourne,Australia.

作者單位江蘇省電子商務(wù)省級(jí)重點(diǎn)實(shí)驗(yàn)室（南京財(cái)經(jīng)大學(xué)） 江蘇省南京市 210000

江蘇省高校自然基金（16KJB520016）。

李秀怡（1979-），碩士研究生。研究方向?yàn)閳D像處理。