基于多細節層次結構擴展合并的快速三維可視化方法

文/李秀怡

基于多細節層次結構擴展合并的快速三維可視化方法

文/李秀怡

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

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

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

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

1 三維模型的多細節層次模型的產生

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

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

2 三維可視化技術發展與應用

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

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

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

3 多細節層次結構擴展合并

3.1 三維場景模型間相鄰關系檢測

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

圖2：多細節層次模型生成

表1：動態可視化時間（毫秒）

3.2 多細節層次模型的生成與合并

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

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

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

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

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

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

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

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

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

4 快速三維可視化

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

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

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

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

5 實驗結果

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

6 結束語

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

[1]潘志庚,馬小虎,石教英.多細節層次模型自動生成技術綜述[J].軟件學報,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]朱恒.關于數字城市三維建模可視化技術分析[J].遙感測繪,2017(01).

[5]章孝燦,黃智才,戴企成,潘云鶴.GIS中基于拓撲結構和凸殼技術的決速TIN生成算法[J].計算機學報,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.

作者單位江蘇省電子商務省級重點實驗室（南京財經大學） 江蘇省南京市 210000

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

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