基于細節(jié)層次模型的多面體優(yōu)化探討

趙迪　陳哲夫　莫操湖　金古月

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

關(guān)鍵詞：多面體簡化 LOD 可視化

1簡介

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

2 LOD

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

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

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

3算法分析

3.1任意網(wǎng)格的多重決定分析

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

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

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

3.2進化網(wǎng)格

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

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

該算法執(zhí)行效率較高，并且由于考慮目標物體的顏色和結(jié)構(gòu)，一般效果也較好。

3.3包絡(luò)線簡化

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

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

該算法的優(yōu)點是沒有測量誤差，可以用包絡(luò)線來控制簡化，但計算過程復(fù)雜，尤其是合適包絡(luò)線的構(gòu)建。

4結(jié)論

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

參考文獻

[1]張毅，呂秀琴.大規(guī)模點云內(nèi)外存調(diào)度繪制技術(shù)[J].計算機工程，2014，40（1）： 49-54.

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

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

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