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

文/李秀怡

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

文/李秀怡

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

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

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

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

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

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

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

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

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

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

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

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

3.1 三維場景模型間相鄰關(guān)系檢測

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

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

表1：動態(tài)可視化時間（毫秒）

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

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

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

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

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

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

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

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

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

圖3：基于擴展的合并算法

4 快速三維可視化

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

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

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

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

5 實驗結(jié)果

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

6 結(jié)束語

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

[1]潘志庚,馬小虎,石教英.多細節(jié)層次模型自動生成技術(shù)綜述[J].軟件學(xué)報,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].遙感測繪,2017(01).

[5]章孝燦,黃智才,戴企成,潘云鶴.GIS中基于拓撲結(jié)構(gòu)和凸殼技術(shù)的決速TIN生成算法[J].計算機學(xué)報,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īng)大學(xué)） 江蘇省南京市 210000

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

李秀怡（1979-），碩士研究生。研究方向為圖像處理。