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

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

(北京航空航天大學機械工程及自動化學院，北京 100191)

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

(北京航空航天大學機械工程及自動化學院，北京 100191)

提出一種基于逆3細分的漸進網(wǎng)格生成算法，用于解決圖形的快速傳輸和顯示問題。算法的基本思路是：將細密網(wǎng)格通過邊折疊操作得到簡化網(wǎng)格，以細分極限點逼近原始網(wǎng)格為準則進行網(wǎng)格調整，采用3細分得到高密度網(wǎng)格，調整后進行逆3細分，即逐層次刪除部分頂點，生成用于重構漸進網(wǎng)格模型的基網(wǎng)格，并記錄每層刪除頂點在采用本層表示時相對于細分計算位置的幾何調整量。3細分過程中三角片數(shù)量增長速度較慢，采用逆3細分利于生成多層次的漸進網(wǎng)格，經(jīng)實例驗證，逆3細分生成漸進網(wǎng)格的效果能滿足快速、多分辨率顯示要求。

網(wǎng)格壓縮；漸進網(wǎng)格；逆細分；3細分

隨著多媒體通信技術的發(fā)展，三維圖形的快速 解決此問題最為有效的方法之一[1]。傳輸和顯示問題成為一個研究熱點。三維圖形的表 漸進網(wǎng)格的概念首先由 Hoppe[2]提出，其基本示是對高密度的復雜三角網(wǎng)格模型的渲染，采用多 思路是采用邊折疊和點分裂的方法進行模型簡化分辨率的層次細節(jié)模型(levels of detail，LOD)成為 生成多分辨率的網(wǎng)格模型。此后，模型簡化算法得

到了不斷地完善[3]，而采用逆細分的方法生成漸進網(wǎng)格的研究相對較少。Samavati等[4]提出了逆向細分的觀點，研究了逆Doo-S細分；Mongkolnam[5]對逆Loop細分進行了詳細的介紹；Luo和Zheng[6]研究了基于插值型的逆蝶形細分，并將生成的漸進網(wǎng)格應用于移動設備的圖形傳輸和渲染。

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

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

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

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

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

圖2 邊收縮示意圖

(5) 調整：調整細分網(wǎng)格頂點坐標，使其細分極限點逼近原始曲面。

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

2.1 細分規(guī)則

圖3細分拓撲規(guī)則

圖4細分模板

對于第k層細分模型可以用細分矩陣表示：

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

2.2 特征邊處理

圖5 邊界處分裂

特征邊分裂點計算公式為：

2.3 網(wǎng)格調整

網(wǎng)格調整的原則是移動控制網(wǎng)格頂點 v，使其所對應的新的細分極限點v∞′位于原始曲面上。

2.3.1 頂點極限位置計算

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

其中，

2.3.2 位置調整

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

令頂點位置調整后的極限位置 v∞ ′=P0，則極限位置的位移量為：

若每次移動頂點時不考慮周圍點的影響，由式(2)可知頂點的位移量應為：

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

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

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

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

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

細分矩陣S可以寫成下面形式：

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

若矩陣嚴格對角最優(yōu)，則矩陣可逆，而矩陣嚴格對角最優(yōu)的條件為對角元素的絕對值大于該行其他元素的絕對值之和，即：若新點點細分矩陣 S為嚴格對角最優(yōu)，則需滿足：

即

則

即

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

本文算法的主要目標是將網(wǎng)格模型 MN作為原始網(wǎng)格，經(jīng)過 N次逆細分生成同構的網(wǎng)格模型Mk(k=0,1,···,N)，其中， M0為基網(wǎng)格。逆細分算法的流程如圖6所示。為方便描述算法，需定義奇點和偶點。奇點：當前網(wǎng)格中將要刪除的點，其對應的是對控制網(wǎng)格做正向細分生成的新面點。偶點：當前網(wǎng)格中需要保留的點，其對應著控制網(wǎng)格中的點。

圖6 算法流程圖

3.2.1 網(wǎng)格預處理

(1) 特征點。只有一個相關面的邊為邊界邊，邊界邊上的點為邊界點。

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

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

邊界邊和特征邊上的點統(tǒng)稱為特征點，網(wǎng)格預

處理階段將特征點及奇異點標記為偶點，以保持模型的特征。

圖7 兩面片夾角

(2) 非正則點。頂點關聯(lián)邊的個數(shù)稱為頂點的度，度為6的內部頂點為正則點。細分不改變控制網(wǎng)格上頂點的度，并且產(chǎn)生的新面點的度為6，因此，在逆細分中只有度為6的內部頂點，即正則點，才可作為奇點刪除，故將非正則點標記為偶點。

3.2.2 奇偶點分類

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

圖8 偶點鄰域

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

3.2.3 拓撲重建

圖9 刪除奇點v0示意圖

根據(jù)式(7)求解控制網(wǎng)格上頂點的坐標，調整網(wǎng)格。為了網(wǎng)格重構，對每次逆細分在刪除奇點為網(wǎng)格層次，i=0,1,···,m–1)時，采用細分模板計算還原時生成奇點的位置，在刪除奇點的同時，記錄頂點的調整量。

3.2.4 特征保持

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

3.3 漸進網(wǎng)格重構

漸進網(wǎng)格是解決三維圖形在線傳輸和顯示問題的有效方法之一，逆細分生成漸進網(wǎng)格可實現(xiàn)圖形的高度壓縮和快速還原。漸進網(wǎng)格重建時，

首先建立控制網(wǎng)格 Mk(k=0,1,···,N–1)，根據(jù)細分模板計算細分新面點位置 vik+1′，然后由誤差 ek+1進行位置補償，即：

圖10 特征邊處理

4 實 例

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

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

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

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

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

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

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

表1 重構漸進網(wǎng)格模型參數(shù)

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

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

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

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

5 結 論

并不會引起太大的視覺影響。

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

表2 逆細分和網(wǎng)格重建運行時間(s)

表3 壓縮率對比(%)

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

[1] 馬建平, 羅笑南, 凌若天, 等. 漸進網(wǎng)格及其在移動計算中的應用[J]. 中國圖象圖形學報, 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] 王玉慧. 牙體預備的力覺交互仿真算法研究[D]. 北京:北京航空航天大學, 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.

Progressive Mesh Generation Algorithm Based on InverseSubdivision

Zhang Weihua, Wang Yuhui
(School of Mechanical Engineering and Automation, Beihang University, Beijing 100191, China)

A progressive mesh algorithm is proposed to accelerate the transmission and display of 3D graphics based on inverse 3subdivision. Main steps of the algorithm are as follows. Firstly, the original mesh is simplified by edge contraction. Secondly, vertexes of control mesh are modified for the purposes of their subdivision limit points which are approximate to the original mesh. Thirdly, the high-density mesh is obtained by 3subdivision. Finally, inverse 3subdivision is implemented. In detail, some vertexes are removed from mesh after each time of inverse 3subdivision. The base mesh and a set of displacement values are kept for reconstructing a series of progressive meshes. For 3subdivision, the growth rate of number of triangles is lower than some other subdivision scheme. As a result, more levels of meshes can be obtained by inverse 3subdivision. Experiment results show that progressive meshes generated by 3subdivision can meet the need of fast and multi-resolution display.

mesh compression; progressive mesh; inverse subdivision;3subdivision

TP 391

A

2095-302X(2015)04-0495-08

2014-09-30；定稿日期：2014-12-27

張衛(wèi)華(1988–)，女，河南?？h人，碩士研究生。主要研究方向為計算機圖形學。E-mail：1034102310@qq.com

王玉慧(1964–)，女，河南鄭州人，副教授，博士，碩士生導師。主要研究方向為計算機圖形圖像處理、虛擬現(xiàn)實。E-mail：wangyuhui64611@buaa.edu.cn