趙迪 陳哲夫 莫操湖 金古月
摘要:細節(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.