摘 要： 高分辨率網(wǎng)格模型因其數(shù)據(jù)量龐大，對其在網(wǎng)絡(luò)中很難進行實時處理，因此，根據(jù)Loop細分模板，將邊點作為小波的細節(jié)信息構(gòu)造出了Loop細分小波，用于對網(wǎng)絡(luò)模型進行多分辨率分析。該方法未涉及曲面幾何拓撲關(guān)系，因而不受曲面拓撲特征的影響，具有很強的適應(yīng)性。利用其對三維網(wǎng)格模型進行多分辨率分析，得到的低分辨率模型輪廓逼真，面片數(shù)量大幅度減少。由于該方法對細節(jié)信息取舍尺度還不能用統(tǒng)一的公式確定下來，因此只適合對模型做一些簡單的處理。

關(guān)鍵詞： 網(wǎng)格模型； Loop細分小波； 多分辨率分析； 小波重構(gòu)； 小波分解

中圖分類號：TP391 文獻標(biāo)志碼：A 文章編號：1006-8228（2013）02-14-03

Application of Loop subdivision wavelets to multi-resolution analysis in the mesh model

Wang Yanyan1， Luo Xiaofeng2， Hui Lifeng1， Wang Ping1

（1. School of Coal， Inner Mongolia University of Science Technology， Baotou， Neimenggu 014010， China；

2. School of Mining Engineering， Inner Mongolia University of Science Technology）

Abstract： The amount of data of the high-resolution model is very large so that its real-time processing in the network is difficult. Thus the Loop subdivision wavelet is constructed by the way of treating edge points as the details of the wavelet based on the Loop subdivision mask in this paper. This method involving the surface geometry is not independent of the features of the surface topology and thus is of strong adaptability. The three-dimensional grid model is analyzed by using this method. The low-resolution model obtained is vivid and its face number largely decreases. Because it is not yet able to determine scale of option using unified formula， it is only suitable to do some simple processing on models.

Key words： mesh model； Loop subdivision wavelet； multi-resolution analysis； wavelet reconstruction； wavelet decomposition

0 引言

隨著三維掃描技術(shù)與互聯(lián)網(wǎng)的高速發(fā)展，大規(guī)模三維網(wǎng)格模型又成為一種新的數(shù)字媒體。要想在計算機中對這些模型進行處理，就需要將其用數(shù)學(xué)形式表示出來。這些模型的數(shù)據(jù)量非常龐大，將其在網(wǎng)絡(luò)中進行實時編輯、壓縮、傳輸、濾波等操作是很困難的。多分辨率幾何造型技術(shù)是解決上述問題的強有力工具，而小波變換[1]則是實現(xiàn)多分辨率分析的重要手段。近年來小波技術(shù)在曲面造型中的應(yīng)用越來越普遍，對其 “數(shù)學(xué)顯微鏡”和多分辨率特性的應(yīng)用，可以實現(xiàn)模型的快速造型和靈活修改。Lounsbery[2]提出的基于小波多分辨率分析方法不能直接應(yīng)用于不規(guī)則網(wǎng)格。Bonneau[3]提出了一種能夠直接應(yīng)用于不規(guī)則表面網(wǎng)格的多分辨率分析方法，但它只限于平面的或者球形的網(wǎng)格。王健等[4]提出一種基于半邊數(shù)據(jù)結(jié)構(gòu)的自適應(yīng)分割的動態(tài)網(wǎng)格生成算法，較好地處理了分割邊界。隨著對Loop細分曲面的研究進一步加深，Bertram于2000年給出了基于提升格式構(gòu)造雙正交Loop細分小波的算法[5]，這在很大程度上提升了Loop細分曲面的形狀可調(diào)節(jié)性。目前對Loop細分小波的研究大都集中在對網(wǎng)格內(nèi)部頂點的小波分解和小波重構(gòu)方法[6-7]研究上，對非閉合曲面的研究較少，而在工程應(yīng)用中，非閉合曲面大量存在。針對有邊界的非閉合網(wǎng)格，秦[8]等對其做了簡單的處理，但沒有考慮內(nèi)部點對邊界的影響。

本文根據(jù)傳統(tǒng)的Loop細分模板構(gòu)造出了不涉及曲面幾何拓撲結(jié)構(gòu)的Loop細分小波，因此不受曲面拓撲特征的影響，具有很強的適應(yīng)性。

1 Loop細分小波

Loop細分算法是基于頂點的1-4細分，細分規(guī)則如下：對曲面上原有頂點利用其鄰接頂點的加權(quán)平均進行調(diào)整，得到頂點V'；對任意一條邊，利用其鄰接三角面片頂點的加權(quán)平均得到邊點Ve；把在一個三角面片內(nèi)的把頂點V'與其相鄰的邊點Ve連接，邊點Ve之間也連接起來，這樣，原來一個三角面片就被分為四個三角面片。

從小波的角度去理解Loop細分模板，頂點V0、V1、V2、V3可分別看作的是尺度函數(shù)Φ0、Φ1、Φ2、Φ3，邊點Ve被看作是小波基Ψ，Ψ和Φ共同支撐出新的尺度函數(shù)空間。

因此可通過Loop細分模板構(gòu)造出對應(yīng)細分小波（圖1所示），使用公式表示如下：

⑴

⑵

其中，Vi1為Vi的1-鄰域頂點，ki為點Vi的價。

[1][3][1][3][Φ1][Φ0][Φ2][Φ3]

圖1 由Loop細分模板得到的Loop細分小波示意圖

Loop細分算法的局部細分矩陣如下：

⑶

1.1 Loop細分小波的重構(gòu)

根據(jù)公式⑴，在計算奇頂點過程中加入小波系數(shù)Ve（表示細節(jié)信息），對原有的細分矩陣改進如下：

⑷

根據(jù)Bertram的小波構(gòu)造思想，把公式⑴、⑵轉(zhuǎn)換為具有Lifting運算性質(zhì)的操作[5]：

⑸

⑹

其中

公式⑸為預(yù)測操作，利用小波系數(shù)Ve來計算奇點；公式⑹為更新操作，從新得到的奇頂點來重新計算偶頂點，即使用來更新 V'，是頂點Vi 的1-鄰域奇頂點。更新操作的細分矩陣如下：

⑺

與原Loop細分方法相比，Loop細分小波在計算奇點時增加了細節(jié)信息Ve。

1.2 Loop細分小波的分解

把公式⑸、⑹進行逆運算，很容易得到Loop細分小波的分解過程：

⑻

⑼

其中

公式⑻用來提取小波系數(shù)，公式⑼用來計算偶頂點的幾何信息。保留偶點去掉奇點，同時保存舍棄的小波系數(shù)，這樣就完成了一次高分辨率到低分辨率的曲面分解過程。

上述方法僅僅從幾何角度出發(fā)給出一種曲面數(shù)值分析的簡單策略，沒有使用傳統(tǒng)的正交性作為小波的構(gòu)造條件。由于Loop細分小波的數(shù)值計算沒有涉及到曲面的幾何拓撲，因而不會受到曲面拓撲特征的影響，具有較好的適應(yīng)性。

2 算法的實現(xiàn)

Loop細分小波處理的對象主要是三角面片中的頂點信息，而在模型細分和化簡這兩個互逆的過程中，就不可避免要處理曲面的幾何拓撲信息，即頂點間的鄰接關(guān)系與面片的構(gòu)成信息。因此，對于Loop細分小波可主要用兩個過程來對模型進行處理。

⑴ 模型的細分。由低分辨率得到高分辨率模型，對曲面上所有的三角面片利用傳統(tǒng)的Loop細分算法進行1-4細分，這樣便可以得到曲面在高分辨率下的拓撲關(guān)系。

⑵ 模型的簡化。由高分辨率得到低分辨率模型，這個過程相對細分過程要復(fù)雜一些。遍歷模型上所有的頂點Vi，判斷出哪些點是奇點，哪些點是偶點。根據(jù)條件去除一定數(shù)量的奇點并保存這些細節(jié)信息，隨后再利用原來的幾何拓撲信息，將偶頂點重新連接構(gòu)造出新的拓撲關(guān)系。

3 實驗

本文把經(jīng)過Loop細分的cat模型（頂點數(shù)為352，面片數(shù)為671）、nefertiti模型（頂點數(shù)為654，面片數(shù)為1252）在Matlab中利用三維圖像函數(shù)重新建模型，利用Loop細分小波對該模型進行多分辨率分析，實驗效果如圖2所示。從圖2中可以看出，在經(jīng)過一次小波分解后，兩個模型的面片數(shù)都大量減少，cat模型輪廓較為逼真，加入小波系數(shù)，就可重構(gòu)出原始模型。但nefititi模型就失真較多，這是由于在此試驗中，對奇頂點（即小波系數(shù)）進行了取舍，取舍尺度還沒有一個能夠統(tǒng)一確定的公式，這個問題還待進一步研究。

（a） cat模型的細分圖和一次小波分解圖

（b） nefertiti模型的細分圖和一次小波分解圖

圖2 Loop 細分小波實驗結(jié)果圖

4 結(jié)束語

用本文構(gòu)造的Loop細分小波對高分辨率模型進行處理的過程中，由于奇點（小波系數(shù)Ve）是由奇點和偶點的拓撲信息計算得到的，而偶點應(yīng)用的標(biāo)準(zhǔn)是Loop細分模板的運算結(jié)果，其在小波的合成與分解過程中都是無損的。因此在對模型的多分辨率分析過程中，將小波系數(shù)作為細節(jié)信息存儲起來，可以用于無誤差的模型合成；但在對模型的分解過程，就要舍棄一些高頻信息Ve得到一個近似的幾何模型，但這個舍棄尺度還不能用一個公式確定下來，所以對模型分解過程中還存在很大偏差，這是該方法的不足之處，在以后的工作中，需著手對細節(jié)的取舍尺度做進一步深入的研究，將其用公式確定下來。

參考文獻：

[1] Finkelstein， Salesin D H. Multiresolution curves[A]. In： Proceedingsof SIGGRAPH '94[C].ACM，1994：261-268

[2] Eck M， DeRose T， Duchamp T， et al. Multiresolution analysis of arbitrary meshes[A]. In：ACM Siggraph Conference Proceedings[C]. New York，1995：173-182

[3] Bonneau G P. Multiresolution analysis on irregular surface meshes[J]. IEEE Trans. Visualization and Computer Graphics，1998.4（4）：365-378

[4] 王健，何明一.自適應(yīng)分割的動態(tài)網(wǎng)格生成算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005.17（7）：1434-1439

[5] Bertram M. Biorthogonal loop subdi-vision wavelets[J].Computing Springer，2004.72（1-2）：29-39

[6] Lounsbery J M. Multiresolution analysis for surfaces of arbitrary topological type[D]. Ph.D.Thesis， Department of Mathematics， University of Washingtown，1994.

[7] Wang H W， Qin K H， Tang K. Efficient wavelet construction with Catmull-Clark subdivision [J]. The Visual Computer，2006.22（9-11）：874-884

[8] Sweldens W. The lifting scheme：A custom-design construction ofbi-orthogonal wavelets[J]. Appl Comput Harmon Anal，1996.3（2）：186-200