基于細節層次模型的多面體優化探討

趙迪　陳哲夫　莫操湖　金古月

摘要：細節層次模型（Levels of Detail.LOD）可以緩解優化大規模空間數據的實時可視化渲染問題。本文基于LOD技術的基本原理，對優化過程中的模型簡化、測量近似誤差、視覺誤差估計等方面進行了深入探討，并針對各種算法在多面體簡化方面的效率進行比較，闡明了各自的優缺點及應用環境。

關鍵詞：多面體簡化 LOD 可視化

1簡介

大規模空間數據的實時可視化渲染計算和存儲需要大量的多面體顯示。1976年，Clark認為較遠地方的不清楚視覺效果可以用簡化的幾何圖形代替，即細節層次模型（LOD）。也就是說，在觀察者視野邊緣地區的或者處于運動狀態中的物體可以用簡化后的多面體描述。因此，目前主流軟件引入此種理念支持LOD技術的管理行為，一般是在多面體集合中歸納統計的幾何共性然后建模。本文主要針對3種支持LOD技術的最新算法進行比較，對執行過程和效率進行直觀判斷，闡述每種算法的優勢和缺點，并指明每種算法最適宜的運行環境。

2 LOD

多面體簡化的前提是不改變原始目標的基本外觀特征，理想結果是一個整體的系列簡化在此環境下的LOD稱為Geomorphe模式，據此生成的數據結構能夠增強LOD顯示的連續性，不易察覺相鄰簡化物體的不同。但是，如果LOD的數量較少，則相鄰LOD間的轉換就會明顯停頓，破壞LOD顯示的連續流暢性。此外，為保持框架比例的完整性，需要尋找完善模型和顯示時間間的最佳平衡點。

多面體的簡化結果必須保留原物體的基本外觀形狀特征，因此相關算法的研究重點在于目標物體的共面、棱邊、共點等方面。測試共面時，算法對于兩法線間的夾角有一個臨界值，若兩平面法線間的夾角大于該值則認為此兩面不共面。該值越高，則認為有更多面共面并被簡化。該值一般通過觀察者的視覺特征估計，但誤差較大且沒有統一模型支持。

為優化控制簡化效果，應考慮測量局部近似誤差的使用。一些算法用局部誤差或用到原始網格的直線距離來估算誤差，以在幾何結構上保證簡化不超過某一限值。此外，算法執行過程中允許用戶自主設定簡化數量的極值和保留多面體的數量，該值的設定需要實際經驗支持。一些算法為保留某一關注區域而大幅度簡化其余部分，即簡化數量隨網格大小的不同而隨之變化，也就是說，這些算法主要從視覺語義上考慮并可由用戶控制。總而言之，離觀測者近的區域選取低層次結點，離觀測者遠的區域采用高層次結點。

3算法分析

3.1任意網格的多重決定分析

該算法構造一種網格的多重選擇表示法，包含簡單的基本網格和一系列描述網格細節系數的地貌圖形。算法要求輸入網格通過遞歸細分構造，即每個三角形用4-to-l模式細分，直至達到所設定的限值。

該算法比較適用于顧及拓撲性質的環境，可以利用到原始網格的距離估計近似測量誤差，過程主要有四步：（1）劃分：在原始網格中用多種子線條構造Voronoi曲線圖，然后在網格的對偶曲線中尋找算法結構，曲線被Delaunay三角化;（2）生成基本網格：采用Harmonic maps法拉直邊緣線做出基本網格，保證網格沿每個面連續，使網格細節系數最小;（3）重采樣：再次用4-to-l模式對基本網格重采樣，直到基本網格與原始網格相似為止;（4）多重決定分析：將連續網格編碼為多重決定分析算法。

該算法的簡化范圍廣泛，并且一些細節可以被加入到指定區域，但操作復雜，尤其是提煉一個有效網格的進程。

3.2進化網格

該算法的簡化是通過運用消除邊緣線算子，生成一個簡化的基本網格和一系列分開的頂點。該算法主要考慮目標的顏色、結構、網格表面法線等不連續信息，目標是（1）保證簡化網格與原始網格相似;（2）在邊緣線上可以設置零剩余長度和用合適比例三角化;（3）不支持顏色和結構的不連續簡化;（4）不支持拓撲和法線的不連續簡化。

主要步驟如下：（1）緣線分類將簡化過程的圖形損失降到最小;（2）在簡化開始處對邊緣線應用消除算子，記錄不相連頂點;（3）在兩個初始頂點和邊的中心點里選取新頂點位置，取離原始網格最近的點為新頂點;（4）重新確定整理邊緣線損失清單;（5）如果清單是空的或者下一個簡化損失超過某限值，則終止算法并返回最終簡化網格（6）否則跳到第二步，重復。

該算法執行效率較高，并且由于考慮目標物體的顏色和結構，一般效果也較好。

3.3包絡線簡化

該算法保留平面區域和棱邊，僅用幾何結構控制簡化，不用誤差測量，偏移量由用戶設定且保證相鄰平面相交。然后在這兩個表面間再做一個新的表面，唯一約束條件是與之前兩個表面都不相交。相交的表面必須移向原始網格直到證實有足夠的空間，則在棱邊附近兩個表面間的空間越小做出的簡化越少。

主要步驟如下：（1）沿法線向頂點偏移外部表面，偏移量假定最終偏移量的一部分;（2）若頂點和表面相交則取消向頂點的移動;（3）重復（1）和（2），直到若表面不相交偏移量就不會再增或者偏移量到達理想值為止;（4）對內表面重復（1）和（3），對邊界區域建立包絡線。

該算法的優點是沒有測量誤差，可以用包絡線來控制簡化，但計算過程復雜，尤其是合適包絡線的構建。

4結論

綜上所述，大部分算法都有各自的簡化方式，但基本過程相同，即尋找共面區，然后簡化，尋找棱邊并保留。但無論使用哪種算法，在預測簡化的數量和設定各個參數的真值前都需要做大量實驗。并且，到目前為止，尚未有一種算法用人的視覺來設置參數，LOD的生成在很大程度上是一種保留行為模型。另一方面，物體的復雜性不斷增加如果把結構和光的信息添加進去會產生更加切合實際的透視圖，但執行速度勢必受到影響，所以在二者間如何尋求一個平衡點是需要進一步考慮的問題。最后，LOD的創建和選擇應結合渲染背景管理技術，對特殊背景選擇簡化數量時，背景的分布和可視化關系對簡化過程可能有較大幫助。

參考文獻

[1]張毅，呂秀琴.大規模點云內外存調度繪制技術[J].計算機工程，2014，40（1）： 49-54.

[2]林繼承，萬旺根，崔濱等，一種超大規模地形場景的實時渲染算法[J].計算機仿真，2009，26（11）：224-227.

[3]鄭順義.基于三角網無縫拼接的三維重建[J]，武漢大學學報（信息科學版），2009，34（1）： 15-19.

[4]王芳，叢文靜，祝海濤，基于頂點法向量重要度的模型簡化算法研究[J]計算機與數字工程，2011（7）：6-8.