基于逆細(xì)分的漸進(jìn)網(wǎng)格生成算法研究

張衛(wèi)華， 王玉慧

(北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京 100191)

隨著多媒體通信技術(shù)的發(fā)展，三維圖形的快速傳輸和顯示問題成為一個(gè)研究熱點(diǎn)。三維圖形的表示是對(duì)高密度的復(fù)雜三角網(wǎng)格模型的渲染，采用多分辨率的層次細(xì)節(jié)模型(levels of detail，LOD)成為解決此問題最為有效的方法之一[1]。

漸進(jìn)網(wǎng)格的概念首先由Hoppe[2]提出，其基本思路是采用邊折疊和點(diǎn)分裂的方法進(jìn)行模型簡化生成多分辨率的網(wǎng)格模型。此后，模型簡化算法得到了不斷地完善，而采用逆細(xì)分的方法生成漸進(jìn)網(wǎng)格的研究相對(duì)較少。Samavati等[4]提出了逆向細(xì)分的觀點(diǎn)，研究了逆Doo-S細(xì)分；Mongkolnam[5]對(duì)逆Loop細(xì)分進(jìn)行了詳細(xì)的介紹；Luo和Zheng[6]研究了基于插值型的逆蝶形細(xì)分，并將生成的漸進(jìn)網(wǎng)格應(yīng)用于移動(dòng)設(shè)備的圖形傳輸和渲染。

由于Loop細(xì)分和蝶形細(xì)分都是1~4分裂的細(xì)分模式，面片數(shù)量增長速度太快，生成多分辨率模型的層次較少。為此，本文提出了一種基于逆細(xì)分的算法生成漸進(jìn)網(wǎng)格，細(xì)分為1~3細(xì)分模式，較其他細(xì)分模式面片數(shù)量增長較慢，因此可以生成較多層次的漸進(jìn)網(wǎng)格模型；細(xì)分模板相關(guān)聯(lián)的頂點(diǎn)數(shù)目較少，加快了漸進(jìn)網(wǎng)格的生成和渲染的速度。

1 生成漸進(jìn)網(wǎng)格的整體思路

圖1 算法實(shí)現(xiàn)流程

(1) 輸入：高密度的原始網(wǎng)格M。

(2) 模型簡化：通過多次邊折疊操作將原始模型M最終簡化為一個(gè)粗的網(wǎng)格模型′，圖2為一次邊折疊的示意圖。

(3) 網(wǎng)格調(diào)整：調(diào)整簡化后的模型，使頂點(diǎn)的極限位置逼近原始曲面，得到初始控制網(wǎng)格M0。

圖2 邊收縮示意圖

(5) 調(diào)整：調(diào)整細(xì)分網(wǎng)格頂點(diǎn)坐標(biāo)，使其細(xì)分極限點(diǎn)逼近原始曲面。

(7) 輸出：用于曲面重構(gòu)的一個(gè)基網(wǎng)格M0和一系列位置調(diào)整量。

2.1 細(xì)分規(guī)則

圖3細(xì)分拓?fù)湟?guī)則

圖4細(xì)分模板

對(duì)于第k層細(xì)分模型可以用細(xì)分矩陣表示：

Vv是新點(diǎn)點(diǎn)，Vf是新面點(diǎn)，k是細(xì)分次數(shù)，S是細(xì)分矩陣，m為新點(diǎn)點(diǎn)個(gè)數(shù)，q為新面點(diǎn)個(gè)數(shù)，S矩陣的每一行元素由細(xì)分模板計(jì)算。

2.2 特征邊處理

圖5 邊界處分裂

特征邊分裂點(diǎn)計(jì)算公式為：

2.3 網(wǎng)格調(diào)整

網(wǎng)格調(diào)整的原則是移動(dòng)控制網(wǎng)格頂點(diǎn)v，使其所對(duì)應(yīng)的新的細(xì)分極限點(diǎn)v∞′位于原始曲面上。

2.3.1 頂點(diǎn)極限位置計(jì)算

內(nèi)部頂點(diǎn)v的相鄰頂點(diǎn)為vi(i=0,1,…,n–1)，n為頂點(diǎn)v的度，頂點(diǎn)v的極限位置公式[7]為：

2.3.2 位置調(diào)整

根據(jù)式(2)計(jì)算當(dāng)前點(diǎn)的極限位置v∞，在原始曲面上尋找v∞在最近曲面上的投影點(diǎn)P0，參考Suzuki等[8]的迭代逼近方法求解頂點(diǎn)的位移量。

令頂點(diǎn)位置調(diào)整后的極限位置v∞′=P0，則極限位置的位移量為：

若每次移動(dòng)頂點(diǎn)時(shí)不考慮周圍點(diǎn)的影響，由式(2)可知頂點(diǎn)的位移量應(yīng)為：

由式(3)可知頂點(diǎn)移動(dòng)的位移與δ成正比?？紤]到網(wǎng)格的平滑，控制頂點(diǎn)v在移動(dòng)過程中用相鄰頂點(diǎn)進(jìn)行制約，添加平滑項(xiàng)[9]。點(diǎn)的坐標(biāo)依式(4)進(jìn)行更新。

其中，μ為收斂因子，η為平滑因子，由實(shí)驗(yàn)選定，這兩個(gè)參數(shù)的選取決定了誤差的收斂性和網(wǎng)格的平滑性。

對(duì)于特征邊上的頂點(diǎn)，偶次分裂產(chǎn)生的新點(diǎn)位置調(diào)整到最近的特征邊上。

用表示頂點(diǎn)vi(i=0,1,…,m–1)到原始網(wǎng)格表面的距離，則網(wǎng)格中所有頂點(diǎn)到原始網(wǎng)格表面的平均距離為：

平均距離E將作為衡量網(wǎng)格逼近原始網(wǎng)格模型的指標(biāo)。

為保證細(xì)分后的模型最大程度逼近原始網(wǎng)格模型，在最后一次細(xì)分后，將網(wǎng)格上的所有頂點(diǎn)都移到原始曲面上，得到模型NM。

細(xì)分矩陣S可以寫成下面形式：

其中，每行中沒有列出來的項(xiàng)之和為αn,i(i=1,2,…,m)。

若矩陣嚴(yán)格對(duì)角最優(yōu)，則矩陣可逆，而矩陣嚴(yán)格對(duì)角最優(yōu)的條件為對(duì)角元素的絕對(duì)值大于該行其他元素的絕對(duì)值之和，即：

即

則

即

細(xì)分矩陣S中，對(duì)角線元素si,i=1-αn,i，對(duì)任意頂點(diǎn)對(duì)(i,j),(i≠j)，如果j是i的相鄰點(diǎn)，則(i,j)∈E，否則(i,j)?E，則細(xì)分矩陣中si,j的取值如下：

本文算法的主要目標(biāo)是將網(wǎng)格模型NM作為原始網(wǎng)格，經(jīng)過N次逆細(xì)分生成同構(gòu)的網(wǎng)格模型Mk(k=0,1,…,N)，其中，M0為基網(wǎng)格。逆細(xì)分算法的流程如圖6所示。

圖6 算法流程圖

為方便描述算法，需定義奇點(diǎn)和偶點(diǎn)。

奇點(diǎn)：當(dāng)前網(wǎng)格中將要?jiǎng)h除的點(diǎn)，其對(duì)應(yīng)的是對(duì)控制網(wǎng)格做正向細(xì)分生成的新面點(diǎn)。

偶點(diǎn)：當(dāng)前網(wǎng)格中需要保留的點(diǎn)，其對(duì)應(yīng)著控制網(wǎng)格中的點(diǎn)。

3.2.1 網(wǎng)格預(yù)處理

(1) 特征點(diǎn)。只有一個(gè)相關(guān)面的邊為邊界邊，邊界邊上的點(diǎn)為邊界點(diǎn)。

內(nèi)部邊根據(jù)其所關(guān)聯(lián)面片的二面角標(biāo)記特征邊，特征邊上的點(diǎn)為特征點(diǎn)。兩面片夾角可通過其法矢夾角進(jìn)行求取(式(8))，如圖7。

奇異點(diǎn)：Hoppe等[10]對(duì)曲面的尖銳特征做了具體的分類，其將刺點(diǎn)、角點(diǎn)、折痕頂點(diǎn)等具有尖銳特征的頂點(diǎn)統(tǒng)稱為奇異點(diǎn)。奇異點(diǎn)是模型的重要特征，在模型處理的各個(gè)階段都不能刪除。

邊界邊和特征邊上的點(diǎn)統(tǒng)稱為特征點(diǎn)，網(wǎng)格預(yù)處理階段將特征點(diǎn)及奇異點(diǎn)標(biāo)記為偶點(diǎn)，以保持模型的特征。

圖7 兩面片夾角

(2) 非正則點(diǎn)。頂點(diǎn)關(guān)聯(lián)邊的個(gè)數(shù)稱為頂點(diǎn)的度，度為6的內(nèi)部頂點(diǎn)為正則點(diǎn)。

3.2.2 奇偶點(diǎn)分類

由于模型MN是由細(xì)分得到的網(wǎng)格模型，具有細(xì)分連通性，根據(jù)網(wǎng)格中奇偶點(diǎn)的分布規(guī)律對(duì)網(wǎng)格頂點(diǎn)進(jìn)行分類。為避免分類時(shí)出錯(cuò)，從網(wǎng)格MN中的奇異點(diǎn)或非正則點(diǎn)v開始標(biāo)記。圖8為偶點(diǎn)v周圍頂點(diǎn)的奇偶性分布情況。

圖8 偶點(diǎn)鄰域

根據(jù)圖8設(shè)定標(biāo)記偶點(diǎn)的規(guī)則：將偶點(diǎn)v的一環(huán)鄰域中未標(biāo)記的點(diǎn)va標(biāo)記為奇點(diǎn)，并將v關(guān)于一環(huán)對(duì)邊ee對(duì)稱的點(diǎn)vs標(biāo)記為偶點(diǎn)，算法如下：

3.2.3 拓?fù)渲亟?/p>

圖9 刪除奇點(diǎn)v0示意圖

根據(jù)式(7)求解控制網(wǎng)格上頂點(diǎn)的坐標(biāo)，調(diào)整網(wǎng)格。為了網(wǎng)格重構(gòu)，對(duì)每次逆細(xì)分在刪除奇點(diǎn)(k為網(wǎng)格層次，i=0,1,…,m-1)時(shí)，采用細(xì)分模板計(jì)算還原時(shí)生成奇點(diǎn)的位置′，在刪除奇點(diǎn)的同時(shí)，記錄頂點(diǎn)的調(diào)整量。

3.2.4 特征保持

模型特征邊上的頂點(diǎn)對(duì)于保持模型的形狀特征尤為重要，因此，在逆細(xì)分中對(duì)特征邊的處理如圖10所示。只在奇次逆細(xì)分時(shí)，刪除特征邊e在偶次細(xì)分時(shí)產(chǎn)生的頂點(diǎn)v1、v2，同時(shí)記錄v0、v3點(diǎn)，這些頂點(diǎn)在奇次逆細(xì)分后的度為5，在偶次逆細(xì)分中作為奇點(diǎn)單獨(dú)處理。特征邊上頂點(diǎn)的位置不做調(diào)整。

3.3 漸進(jìn)網(wǎng)格重構(gòu)

漸進(jìn)網(wǎng)格是解決三維圖形在線傳輸和顯示問題的有效方法之一，逆3細(xì)分生成漸進(jìn)網(wǎng)格可實(shí)現(xiàn)圖形的高度壓縮和快速還原。漸進(jìn)網(wǎng)格重建時(shí)，首先建立控制網(wǎng)格M(k=0,1,…,N-1)，根據(jù)細(xì)分模板計(jì)算細(xì)分新面點(diǎn)位置′，然后由誤差ek+1進(jìn)行位置補(bǔ)償，即：

圖10 特征邊處理

4 實(shí) 例

本文采用具有邊界和尖銳特征的潛艇艇身網(wǎng)格模型(圖11)，對(duì)基于逆細(xì)分生成漸進(jìn)網(wǎng)格進(jìn)行了驗(yàn)證，算例程序的編程環(huán)境為VS2010。

圖11 網(wǎng)格模型M和

每次細(xì)分后進(jìn)行網(wǎng)格調(diào)整，參數(shù)μ和η由實(shí)驗(yàn)選定，圖12是收斂因子μ和平滑因子η變化時(shí)，對(duì)初次調(diào)整后的控制網(wǎng)格及細(xì)分調(diào)整后的網(wǎng)格與原始網(wǎng)格模型的平均距離誤差E的影響。

由圖12中可以看出，當(dāng)μ=0.82，η=0.22時(shí)，平均距離誤差E的收斂性和平穩(wěn)性最佳，故將其作為本文細(xì)分時(shí)所選參數(shù)，細(xì)分得到網(wǎng)格模型M4，面片數(shù)為54 108。

由基網(wǎng)格和記錄的位置調(diào)整量組成的漸進(jìn)網(wǎng)格模型存儲(chǔ)量少，便于快速傳輸和重構(gòu)。讀取存儲(chǔ)數(shù)據(jù)進(jìn)行網(wǎng)格重構(gòu)，圖13是重構(gòu)的漸進(jìn)網(wǎng)格模型。

圖12 參數(shù)μ和η對(duì)平均誤差的影響

圖13 漸進(jìn)網(wǎng)格模型

表1 重構(gòu)漸進(jìn)網(wǎng)格模型參數(shù)

對(duì)VENUS和自行車座模型分別進(jìn)行算法測(cè)試，得到漸進(jìn)網(wǎng)格如圖14~15所示。

算法實(shí)現(xiàn)各部分的運(yùn)行時(shí)間如表2。

本文方法與現(xiàn)有逆Loop細(xì)分及逆蝶形細(xì)分方法生成各層次模型的壓縮率對(duì)比見表3，在壓縮率相同時(shí)，本文方法生成的層次更多，逆細(xì)分次數(shù)越多該優(yōu)勢(shì)越明顯。

圖14 VENUS漸進(jìn)網(wǎng)格模型(頂點(diǎn)數(shù)/面片數(shù))

5 結(jié) 論

圖15 自行車座漸進(jìn)網(wǎng)格模型(頂點(diǎn)數(shù)/面片數(shù))

表2 逆細(xì)分和網(wǎng)格重建運(yùn)行時(shí)間(s)

表3 壓縮率對(duì)比(%)

逆細(xì)分是一個(gè)逆向工程的實(shí)現(xiàn)，生成網(wǎng)格模型所需的存儲(chǔ)量非常少，是對(duì)原始網(wǎng)格模型的高度壓縮，便于存儲(chǔ)和傳輸；重構(gòu)漸進(jìn)網(wǎng)格時(shí)只需按照正向細(xì)分規(guī)則進(jìn)行細(xì)分，用存儲(chǔ)的調(diào)整量對(duì)新面點(diǎn)位置進(jìn)行修正，計(jì)算簡單，調(diào)整量少，因而重構(gòu)速度快，能夠滿足快速重構(gòu)和多分辨率顯示的要求。

[1] 馬建平,羅笑南,凌若天,等.漸進(jìn)網(wǎng)格及其在移動(dòng)計(jì)算中的應(yīng)用[J].中國圖象圖形學(xué)報(bào),2007,12(2):250-255.

[2] Hoppe H.Progressive meshes [C]//In: Proceeding of the 23rd Annual Conference on Computer Graphics and Interactive Techniques.New Orleans,LA,USA,1996:99-108.

[3] Garland M,Heckbert P S.Surface simplification using quadric error metrics [C]//In: Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH.Los Angeles,California,1997: 209-216.

[4] Samavati F F,Mahdavi-Amiri N,Bartels R H.Multiresolution surfaces having arbitrary topologies by a reverse Doo subdivision method [J].Computer Graphics Forum,2002,21(2): 121-136.

[5] Mongkolnam P.Solving the inverse Loop subdivision surface problem and its practical applications [D].USA:Arizona State University,2003.

[6] Luo Xiaonan,Zheng Guifeng.Progressive meshes transmission over a wired-to-wireless network [J].ACM Journal of Wireless Networks,2008,14(1): 47-53.

[8] Suzuki H,Takeuchi S,Kimura F,et al.Subdivision surface fitting to a range of points [C]//Proceedings of the 7th Pacific Conference on Computer Graphics and Applications.Seoul,Korea,1999: 158-167.

[9] 王玉慧.牙體預(yù)備的力覺交互仿真算法研究[D].北京:北京航空航天大學(xué),2009.

[10] Hoppe H,DeRose T,Duchamp T,et al. Piecewise smooth surface reconstruction [C]//In: Proceedings of Computer Graphics,Annual Conference Series,ACM SIGGRAPH.Orlando,Florida,1994: 295-302.