趙 罡， 季寶朋， 白 杰

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

一種Loop細分小波的邊界處理方法

趙 罡， 季寶朋， 白 杰

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

細分小波近年來發(fā)展迅速，在計算機圖形顯示、漸進網(wǎng)格傳輸和網(wǎng)格多分辨率編輯等領域獲得了廣泛的應用。Bertram提出的 Loop細分小波是基于提升格式的雙正交細分小波的典型范例，它所針對的對象均為網(wǎng)格的內(nèi)部頂點。目前尚未發(fā)現(xiàn)相關文獻提及細分小波對于邊界的處理。該文在Loop細分小波算法的基礎上，給出了一種Loop細分小波邊界處理的方法，經(jīng)驗證效果令人滿意。

計算機應用；Loop細分曲面；細分小波；曲面邊界處理

Loop細分模式是一種基于三角網(wǎng)格模型的細分方法[1]。隨后，Hoppe等人對Loop細分方法進一步拓展，拓展的Loop算法具有任意性、整體連續(xù)性、算法穩(wěn)定性和可伸縮性等，因此受到越來越多的關注。

近年來，小波技術在曲面造型中的應用也越來越廣泛，對小波的多分辨率和“數(shù)學顯微鏡”等特性的應用，能夠實現(xiàn)物體的快速造型和靈活修改[2-4]。隨著對Loop細分曲面的研究進一步加深，Bertram于2000年給出了基于提升格式構造雙正交 Loop細分小波的算法[5]，這在很大程度上提升了Loop細分曲面的形狀可調(diào)節(jié)性。但是，到目前為止，筆者所看到的關于Loop細分小波的文獻都只提到了對于網(wǎng)格內(nèi)部頂點的小波分解和小波重構方法[5-6]，尚未見到針對非閉合曲面邊界的小波分解和重構方法，而在工程應用中，非閉合曲面大量存在。針對有邊界的非閉合網(wǎng)格，也有文章做了簡單的處理，沒有考慮內(nèi)部點對邊界的影響[7]。但對于類似面具（如圖 1）這種非閉合網(wǎng)格，若仍然對其進行簡單的邊界處理而不考慮內(nèi)部點對邊界的影響，會造成小波分解結果的不合理性，所以對于邊界如何進行有效的Loop細分小波處理顯得尤為重要。

圖1 非閉合曲面示例

1 雙正交Loop細分小波介紹

1.1 Loop細分方法

細分曲面是多邊形網(wǎng)格的極限狀態(tài)，在曲面造型中應用很廣。1987年Utah大學的Loop提出一種基于三角網(wǎng)格的細分模式[1]，所生成的曲面是箱樣條(Box spline)曲面的推廣。Loop模式采用1-4三角形分裂，只生成E-頂點和V-頂點（如圖2所示）。

圖2 1-4細分示意圖

頂點計算規(guī)則如下：

即頂點本身與其所有相鄰頂點的加權和，其自身的權值為nnβ-1，而鄰點權值為

圖3為Loop細分曲面實例。

圖3 Loop細分曲面實例

1.2 基于提升格式的Loop雙正交細分小波

細分曲面的小波分解過程可以看作將網(wǎng)格曲面上的細節(jié)特征分層去除的過程，而小波重構過程可以看作將細節(jié)特征添加到網(wǎng)格曲面的過程。Martin Bertram提出的Loop雙正交小波是細分小波的典型范例[5]。

最簡單的Loop細分曲面小波重構公式如下

e為小波頂點，v為尺度頂點，n為尺度頂點的鄰點個數(shù)。

相對應的Loop細分曲面小波分解過程為其重構過程的逆過程。但如文獻[5]中所述此種細分小波變換不能產(chǎn)生令人滿意的效果，Bertram稱其為“懶小波變換”(Lazy wavelet synthesis)，同時Bertram在文獻[5]中給出了正交化的小波分解和重構方法。

提升格式是快速構造雙正交小波的有效工具[8]?；谔嵘袷降恼换?Loop細分小波分解公式如下

提升格式的正交化Loop細分小波重構公式如下

其中，n為頂點v的鄰點個數(shù)；iω為細分正交化系數(shù)，其計算過程和常用正交化系數(shù)參見文獻[5]，在此不再贅述。圖4為Loop細分小波分解實例。

圖4 對重構網(wǎng)格執(zhí)行l(wèi)oop細分小波分解的過程

2 邊界處理

2.1 邊界處理方法介紹

Bertram 提出的 Loop細分小波的構造中，只給出了對網(wǎng)格內(nèi)部點的處理方法，而對非閉合網(wǎng)格的邊界沒有給出相應的處理。秦開懷等介紹過一種邊界處理方式[8]，但此方法將邊界當成分離曲線來處理，未充分考慮到內(nèi)部點對邊界的影響。

本文提出了另一種邊界處理方法，避免了以上的不足。

對于具有邊界的網(wǎng)格，先將其進行一次“虛復制”處理。所謂虛復制，即對非邊界上所有的頂點和邊，執(zhí)行一次全局復制，這里的“復制”并非真正意義上的復制，而是僅存于大腦中。這樣一來，結果相當于把內(nèi)部所有的點和邊看成是兩份的重疊，邊界點和邊保持不變，如圖5所示。因此，就可以得到以原網(wǎng)格邊界為分隔線的封閉網(wǎng)格。換句話說，這一操作的目的就是把原網(wǎng)格的邊界“造”成內(nèi)部點和邊，生成一張“半虛半實封閉網(wǎng)格”，而又不失其合理性。因為整個過程并沒有改變原網(wǎng)格實際的幾何信息和拓撲信息。該方法的最大優(yōu)點是具備通用性，可以對具有任意邊界的網(wǎng)格曲面進行細分小波處理。

圖5 虛復制思想示意圖，粗實線L為邊界

2.2 具體實現(xiàn)及公式推導

與第1節(jié)提升格式小波分解過程相同，本文所述方法亦可分為4個步驟，下面分別闡述在小波分解的4個步驟中對邊界點的處理與Bertram方法中對內(nèi)部點處理的不同之處。

2.2.1 小波分解第一步

公式(5)等價于

其中，n為頂點v的鄰點個數(shù)。當處理邊界上的尺度頂點p時，如圖5所示，首先計算p點的δ值時應改為公式

設與點p相鄰的兩個邊界小波點分別為0e和1e，則處理邊界時，式(13)更改為

2.2.2 小波分解第二步

第二步處理時，邊界尺度頂點和內(nèi)部尺度頂點的處理公式相同，只需把計算的公式更其中n為頂點p的鄰點個數(shù)。

2.2.3 小波分解第三步

如公式（7）所示，細分曲面小波分解第三步以小波點為處理對象，要用到與該小波頂點有關的4個相鄰尺度頂點信息。設與該邊界小波頂點相鄰的3個尺度頂點為0v,1v和2v，設其中2v為內(nèi)部尺度頂點（如圖6），則處理邊界小波頂點時公式（7）要更改為改為

圖6 小波頂點的分類

2.2.4 小波分解第四步

第一類：邊界上的小波頂點；

第二類：有一個直接相鄰尺度頂點和一個間接相鄰尺度頂點為邊界點的小波頂點；

第三類：只有一個間接相鄰尺度頂點為邊界點的小波頂點；

第四類：只有一個直接相鄰尺度頂點為邊界點的小波頂點。

因此，當執(zhí)行第四步小波分解時，計算ω值之前先判斷小波頂點e屬于哪個類型，對于包含有邊界尺度頂點的小波頂點e，計算ω值時，傳入的各頂點的鄰點個數(shù)可相應分為四種情況（與圖6對應）。

（1） 對第一類：由虛復制原理可知，2v利用了兩次。則計算ω時針對10,vv ,2v,2v傳入的度分別為：220-n ， 221-n ，2n，2n；

（2） 對第二類：計算ω時針對10,vv ,2v,3v傳入的度分別為：220-n ，1n，2n， 223-n ；

（3） 對第三類：計算ω時針對10,vv ,2v,3v傳入的度分別為：0n，1n， 222-n ，3n；

（4） 對第四類：計算ω時針對10,vv ,2v,3v傳入的度分別為：0n， 221-n ，2n，3n。

小波重構為小波分解的逆過程，在此就不再詳述。

2.3 實 例

圖7為對具有邊界的網(wǎng)格模型執(zhí)行小波分解的實例。

3 結 論

本文提出了一種非閉合Loop細分曲面小波變換的方法。該方法將網(wǎng)格的邊界點“虛擬”成內(nèi)部點，使對邊界點和內(nèi)部點的細分小波處理得到統(tǒng)一，并且得到了滿意的結果。該方法具有通用性，可以用于具有任意邊界網(wǎng)格的細分小波變換。

對于實際工程應用中的一些特殊需要，如將網(wǎng)格曲面用于數(shù)控加工中要求邊界保持，即在小波分解過程中某些邊界要求保持不變，在本算法中并未予以考慮。此問題將會在今后的工作中解決。

圖7 對具有邊界網(wǎng)格曲面執(zhí)行Loop細分小波分解的實例

[1]Loop C T. Smooth subdivision surfaces based on triangles [D]. M.S. Thesis, Department of Mathematics, University of Utah, 1987.

[2]Daubechies I. Ten lectures on wavelets [M]. Phiadephia：SIMA Publ, 1992. 1-341.

[3]Biermann H, Martin I, Zorin D. Cut and past editing of multiresolution surfaces [J]. ACM Transactions on Graphics, 2002, 21(3)：330-338.

[4]Khodakovsky A, Schrode P, Sweldens W. Progressive geometry com- pression [C]// Proceedings of ACM Siggraph, 2000：271-278.

[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 of bi-orthogonal wavelets [J]. Appl Comput Harmon Anal, 1996, 3(2)：186-200.

An Algorithm to Deal with Boundary of Meshes with Loop Subdivision Wavelets

ZHAO Gang, JI Bao-peng, BAI Jie
( School of Mechanical Engineering and Automation, Beijing University of Aeronautics and Astronautics, Beijing 100191, China )

Subdivision wavelets have been developed very fast in recent years. They are widely used in computer graphics, progressive transmission and multiresolution editing etc. Based on the lifting scheme, Bertram has introduced a bi-orthogonal wavelet construction for the Loop subdivision. The vertexes involved in the Bertram’s method are all inner ones in the subdivision surface. The paper presents a method to deal with the boundary of the mesh with subdivision wavelets. Tests show the feasibility of the approach.

computer application; loop subdivision surface; subdivision wavelets; surface boundary subdivision

TP 391

A

1003-0158(2010)06-0034-05

2009-03-18

國家自然科學基金資助項目（60603089）；北京市科技新星計劃資助項目（2007B018）

趙 罡（1972-），男，河北文安人，副教授，主要研究方向為CAD/CAM，幾何造型，虛擬現(xiàn)實。