楊關(guān)良， 王 芳

（海軍工程大學(xué)船舶與動力學(xué)院，湖北 武漢 430033）

虛擬現(xiàn)實技術(shù)是利用計算機生成逼真的三維視覺、聽覺、觸覺等感覺形式而形成虛擬世界。但是在實時仿真應(yīng)用中，場景模型日益趨于多樣化，虛擬環(huán)境的規(guī)模不斷擴大，因此在保證較高圖像質(zhì)量的前提下對模型進行簡化是有效提高繪制效率的重要手段。

邊折疊算法是Hoppe[1]在1993年首先提出來的，它是一種適用于任意二維流形的三角網(wǎng)格模型的優(yōu)化方法。由于Hoppe 是對一個全局能量函數(shù)進行優(yōu)化，并且?guī)缀蝺?yōu)化是非線性的，因此，計算量很大，運行速度很慢。為此，Garland[2-3]在1997 年用局部二次誤差測度來衡量邊折疊的代價，以新頂點到被折疊邊的兩個頂點相關(guān)聯(lián)平面的距離平方和作為誤差測度。論文在Garland邊折疊算法基礎(chǔ)上，結(jié)合視點相關(guān)因子對復(fù)雜模型進行了簡化，并對通用的多邊形模型的數(shù)據(jù)結(jié)構(gòu)進行了改進，實時動態(tài)地生成了多層次的LOD模型[4-6]。LOD（Level of Details）技術(shù)是指將三維物體用多種不同精度的模型表示，并根據(jù)觀察點位置的變化而選擇不同精度的模型予以成像。

本文在邊折疊算法基礎(chǔ)上，將邊折疊算法與視點相關(guān)因子相結(jié)合，對復(fù)雜模型進行了簡化；并使用改進的多邊形模型的數(shù)據(jù)結(jié)構(gòu)，實時動態(tài)地生成了多層次的LOD 模型。

1 邊折疊算法

圖1 邊折疊操作(vi, vj )合并為v

2 模型簡化算法

2.1 誤差測度及新頂點的計算

誤差測度用于評價折疊前后產(chǎn)生的模型誤差情況。論文中的算法是以執(zhí)行折疊操作后得到 的新頂點v 到與該頂點相關(guān)的三角形集合ip 中每個三角形所在平面的距離的平方和為誤差測度，表示為 )(vQ ，這個距離越小越好。

原始模型中的三角面片定義成滿足方程nTv+d=0 的平面，其中n=[a b c]T為單位法矢量，d 為常數(shù)，則頂點到某一平面上的距離的平方為

如果定義誤差矩陣為Mi=(A b c)=( nidini)，則= Mi( v ) = vTAv + 2bTv +c ，將頂點和誤差矩陣均用齊次形式表達(dá)即為

則 Mi( v ) =vTMiv，所以誤差值為

當(dāng)邊對折疊成一個頂點時，折疊后的面片組成與初始邊對的兩個端點相關(guān)的面片組的并集。對原始網(wǎng)格中的每個三角形面片，依照式（2）來計算其誤差矩陣，當(dāng)對原始網(wǎng)格執(zhí)行折疊操作后，一些頂點的坐標(biāo)發(fā)生改變，在程序中直接使 新頂點的誤差矩陣 M = Mi+Mj，其誤差值為M ( v) = Mi( v ) +Mj( v)。

由式（2）可知，邊折疊操作后的誤差測度值為

新頂點位置的確定最優(yōu)的方法是取v 的位置使 )(vQ 最小，即令 )(vQ 的偏導(dǎo)數(shù)為0，求得梯度為 bAv 22 + 。因此，所求最優(yōu)新頂點的位置為

2.2 層次細(xì)節(jié)模型的生成

給定初始精細(xì)的多邊形模型M0，通過連續(xù)的邊折疊操作，可以自動生成具有不同細(xì)節(jié)的多個模型，每一個LOD 模型對應(yīng)于一邊折疊操作序列

式中 M0為原始的模型，edgecol 為邊折疊，Mn為簡化后的模型。

在實際應(yīng)用中，可依據(jù)視點的距離、方向或?qū)OD 模型投影到屏幕空間，按照模型所覆蓋的像素多少來選擇適當(dāng)?shù)腖OD 模型。本文采用視點相關(guān)因子來選擇適當(dāng)?shù)腖OD 模型。

設(shè)坐標(biāo)系原點為O(0，0，0)，視點為V(xv，yv，zv)，目標(biāo)點坐標(biāo)為P(xp，yp，zp)，設(shè)VP 與VO 的夾角為θ（見圖2），則距離d 可表示如下

在VP 的長度一定時，θ 越小的點視覺效果越好。因此，除了考慮距離因素以外，加入一個 視向因子F=sinθ，得到d 的最終表達(dá)式為

d 越小，則模型越精細(xì)。

圖2 視角的影響

2.3 算法實現(xiàn)

在計算機圖形學(xué)中，常用多邊形網(wǎng)格（通常是三角形網(wǎng)格）來描述對象模型，因此本算法的輸入模型使用三角形網(wǎng)格表示的模型。對通用的數(shù)據(jù)結(jié)構(gòu)進行了改進，不僅可以獲取每一個三角形頂點信息、每個頂點鄰近三角形和頂點信息，而且可以獲取頂點與視點的位置參數(shù)。數(shù)據(jù)結(jié)構(gòu)如下：

數(shù)據(jù)結(jié)構(gòu)定義后，即可通過存儲刪除頂點和與邊折疊操作的序列信息來實現(xiàn)模型的層次細(xì)節(jié)轉(zhuǎn)化，在交互顯示時可隨時調(diào)用任意層次細(xì)節(jié)的LOD 模型。

3 實例與分析

為了驗證本文所提出的算法，采用了人物面部模型進行了實驗，模型簡化結(jié)果如圖3 所示，實驗結(jié)果表明，該算法在提高繪制速率的同時很好地近似了原始模型的幾何特征。

圖3(a)為原始模型，有13364 個三角面。

圖3(b)為使用Garland 算法簡化后的模型，從13364 個三角面簡化到2313 個。

圖3(c)為使用本文改進算法簡化后的模型，從13364 個三角面簡化到1628 個。

圖3 簡化的模型

4 結(jié) 束 語

將折疊算法與視點相關(guān)因子有機結(jié)合所作的改進，達(dá)到了在保證視覺效果的前提下，得到較大幅度簡化的模型，節(jié)省了存儲空間，加速了虛擬場景中復(fù)雜模型的繪制。但如何將模型的其他一些屬性信息如紋理信息、顏色信息、光照信息等，附加到誤差度量準(zhǔn)則中以獲得更符合視覺感知特性的簡化模型，有待進一步研究。

[1] Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization [J]. Proc. of the Computer Graphics, 1993, 27： 19-26.

[2] Garland M, Heckbert P S. Surface simplification using quadric error metrics [J]. Proc. of the Computer Graphics, 1997, 18： 209-216.

[3] Schmeder W J, Zarge J A. Decimation of triangle meshes [J]. Computer Graphic, 1992, 16(3)： 64-77.

[4] Alliez P, Meyer M, Debrun M. Interactive geometry remeshing [J]. ACM Transactions on Graphics, 2002, 21(3)： 347-354.

[5] 李現(xiàn)民, 李桂清, 張小鈴, 等. 基于子分規(guī)則的邊折疊簡化算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2002, 14(1)： 8-13.

[6] [美]CASTLEMANKR. 數(shù)字圖像處理[M]. 朱志剛譯. 北京： 電子工業(yè)出版社, 2002. 390-393.