形狀可調的Loop細分曲面漸進插值方法

陳甜甜，閆 迪，王 偉，趙 罡

?

形狀可調的Loop細分曲面漸進插值方法

陳甜甜，閆 迪，王 偉，趙 罡

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

針對Loop細分無法調整形狀與不能插值的問題，提出了一種形狀可調的Loop細分曲面漸進插值方法。首先給出了一個既能對細分網格頂點統一調整又便于引入權因子實現細分曲面形狀可調的等價Loop細分模板。其次，通過漸進迭代調整初始控制網格頂點生成新網格，運用本文的兩步Loop細分方法對新網格進行細分，得到插值于初始控制頂點的形狀可調的Loop細分曲面。最后，證明了該方法的收斂性，并給出實例驗證了該方法的有效性。

Loop細分；形狀可調；漸進插值；權因子

細分曲面造型技術由于具有算法簡單、容易實現、可以表示任意拓撲結構的物體等優點，已經在幾何造型、計算機動畫、游戲等領域得到了廣泛的應用[1]。細分方法按其極限曲面是否插值于初始控制頂點分為逼近型細分方法與插值型細分方法。經典的逼近型細分方法有Catmull-Clark細分[2]和Loop細分[3]，這類細分方法的極限曲面相對初始網格都會有收縮[4]。典型的插值型細分方法有Butterfly細分[5]和Kobbelt細分[6]，這類細分方法的極限曲面不存在收縮，但連續性不好，只能達到整體1連續，而且細分曲面也可能會產生一定程度的變形，因此僅僅憑借初始控制網格無法準確預判其極限曲面的形狀。

針對插值型細分的上述缺點，人們提出了利用逼近型細分構造插值細分曲面的方法。HOPPE等[7]提出了一種基于Loop細分的插值型細分方法。NASRI[8]通過修改Doo-Sabin細分方法的規則使之具有插值特性。BRUNET[9]改進了Nasri的方法，增加了形狀控制特性。HALSTEAD等[10]提出構造線性方程組反求控制頂點，對反求后的控制網格進行細分，得到細分后的極限曲面插值于初始網格控制頂點。但這些方法需求解線性方程組，方程組有可能是病態的。為了避免繁瑣的線性方程組求解，CHEN等[11]和CHENG等[12]分別提出了基于Catmull-Clark細分和基于Loop細分的漸進迭代插值方法。這類方法首先對細分曲面的初始控制頂點進行迭代調整，接著采用已有的逼近型細分方法對調整后的初始控制網格進行細分，不僅易于實現，而且具有較好的曲面連續性。為了進一步提高漸進迭代插值細分方法的靈活性，林曉晶和潘日晶[13]提出了一種基于Loop細分的漸進插值方法，該方法通過引入參數修改Loop細分幾何規則，增加了形狀調整的靈活性。2014年，CHEN和PRAUTZSCH[14]提出了廣義三角形中點細分方法(以下簡稱廣義中點細分)，該方法給出了一種廣義中點細分模板，在細分過程中引入可調權因子，實現細分曲面的形狀可調。文獻[13]運用經典Loop細分模板，文獻[14]運用廣義中點細分模板，兩者雖然都能實現形狀可調，但是細分模板較復雜，實現過程較繁瑣。

通過研究Loop細分與廣義中點細分之間的聯系，本文給出了一種能對細分網格頂點統一調整的等價Loop細分模板，并在此模板的基礎上，提出了一種形狀可調的Loop細分曲面漸進插值方法。該方法通過漸進迭代調整初始控制頂點的位置，使得相應的細分曲面插值于初始控制網格。同時通過在本文中給出的等價Loop細分模板中引入權因子，從而實現Loop細分曲面形狀可調的特性。

1 等價Loop細分模板

1.1 Loop細分

Loop細分方法是一種基于三角形網格的細分模式，其極限曲面是三向四次箱樣條曲面的推廣，在正則點和奇異點處可分別達到2連續與1連續。在實現過程中，新頂點-頂點和新邊點-頂點采用不同的規則進行計算。文獻[3]中給出了新頂點與新邊點的計算公式。

1.2 等價Loop細分模板

廣義中點細分屬于1-4三角形面片分裂細分方法，其細分規則為

其中，R為線性細分；A為加權平均。R運算與A運算如圖1所示。

廣義中點細分在進行運算之后使用式(4)對所有細分網格頂點進行運算，由式(3)和式(4)得到進行一次廣義中點細分之后內部-頂點的計算表達式(5)和內部-頂點的計算表達式(6)，即

內部-頂點的計算表達式

(5)

內部-頂點的計算表達式

廣義中點細分邊界-頂點與邊界-頂點的處理方式與Loop細分一致，給出廣義中點細分的等價細分模板如圖3所示。通過對比該等價細分模板和Loop細分模板可以發現：兩者在形式上完全一致。

圖3 廣義中點細分的等價模板

為了保持Loop細分曲面的形狀不變，又兼具廣義中點細分的細分網格頂點統一調整的優勢，本文給出了一個既能對細分網格頂點統一調整又便于引入權因子實現細分曲面形狀可調的等價Loop細分模板。

對比Loop細分的幾何規則和廣義中點細分的等價模板可知，當權因子滿足式(7)時，Loop細分的內部-頂點與內部-頂點才可以進行統一調整，即

其中，為相應的內部-頂點的價，化簡得

本節通過分析對比廣義中點細分的等價細分模板與Loop細分模板之間的聯系，給出了-頂點和-頂點統一調整的等價Loop細分模板?？傮w來說，等價Loop細分模板有以下兩方面的意義，一是能夠簡化Loop細分算法在計算機上的實現過程，二是便于在Loop細分模板中引入權因子，以實現Loop細分曲面形狀可調。

圖4 Loop細分網格頂點統一調整的等價細分模板

2 兩步漸進插值細分方法

Loop細分是一種基于三角形網格的逼近型細分方法，這種方法的細分曲面不能插值于初始網格的控制頂點，相比于初始網格存在一定的收縮，且細分曲面形狀不可調整。因此，本文提出了一種形狀可調的Loop細分曲面漸進插值方法，該方法既能實現插值，又可以通過改變權因子的大小實現細分曲面形狀可調。

2.1 兩步Loop細分

兩步細分方法是ZHENG和CAI[16]在2006年首次提出的一種細分方法，該方法實現了Catmull-Clark細分方法的形狀可調。本文將這種方法應用于Loop細分，結合迭代插值算法實現形狀可調的Loop細分漸進插值方法。具體的兩步Loop細分實現過程如下：

(2) 對第(1)步得到的新網格運用等價Loop細分模板進行細分，直至得到極限細分曲面。

2.2 兩步Loop細分方法的極限點公式

2.3 迭代插值

3 收斂性證明

將式(14)以矩陣形式表示

根據矩陣的這些性質，可將其分解為一個對角矩陣和一個對稱矩陣，即。其中，對角矩陣為

故

引理3. 正定矩陣的特征值是正值。

4 算法實例

所有實驗均在配置為Intel(R) Core(TM) i5-6500 CPU @ 3.20 GHz 處理器和8 GB內存的電腦上進行，程序運行環境為Visual Studio 2010。實驗均在Knot、Cat、Pig和Bear等4種網格模型的基礎上進行。

首先，為了對比傳統Loop細分模板與等價Loop細分模板的運行時間，以Loop細分4次為例，對4種網格模型進行了實驗，實驗數據見表1。從表1中可以看出，隨著初始網格頂點數的增加，等價Loop細分模板在實現Loop細分上的優勢愈發明顯，效率更高。

表1 傳統Loop細分方法與等價Loop細分模板的運行時間對比

圖 5 不同值所對應的Knot 模型插值曲面

圖 6 Loop 細分曲面及不同值所對應的Cat 模型插值曲面

圖 7 Loop 細分曲面及不同值所對應的Pig 模型插值曲面

圖 8 Loop 細分曲面及不同值所對應的Bear 模型插值曲面

5 結 論

[1] 李桂清. 細分曲面造型及應用[D]. 北京: 中國科學院計算技術研究所, 2001.

[2] CATMULL E, CLARK J. Recursively generated B-spline surfaces on arbitrary topological meshes [J]. Computer Aided Design, 1978, 10(6): 350-355.

[3] LOOP C T. Smooth subdivision surfaces based on triangles [D]. Salt Lake City: Department of Mathematics University of Utah, 1987.

[4] ODER P S, ZORIN D, DEROSE T, et al. Subdivision for modeling and animation [C]//ACM SIGGRAPH 2000 Course Notes. New York: ACM Press, 2000: 65-102.

[5] DYN N, LEVIN D, GREGORY J A. A butterfly subdivision scheme for surface interpolation with tension control [J]. ACM Transaction on Graphics, 1990, 9(2): 160-169.

[6] KOBBELT L. Interpolatory subdivision on open quadrilateral nets with arbitrary topology [J]. Computer Graphics Forum, 1996, 5(3): 409-420.

[7] HOPPE H, DEROSE T, DUCHAMP T, et al. Piecewise smooth surface reconstruction [C]//Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1994: 295-302.

[8] NASRI A H. Polyhedral subdivision methods for free-form surfaces [J]. ACM Transaction on Graphics, 1987, 6(1): 29-73.

[9] BRUNET P. Including shape handles in recursive subdivision surfaces [J]. Computer Aided Geometric Design, 1988, 5(1): 41-50.

[10] HALSTEAD M, KASS M, DEROSE T. Efficient, fair interpolation using Catmull-Clark surfaces [C]// Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1993: 35-44.

[11] CHEN Z X, LUO X N, TAN L, et al. Progressive interpolation based on Catmull-Clark subdivision surfaces [J]. Computer Graphics Forum, 2008, 27(7): 1823-1827.

[12] CHENG F H, FAN F T, LAI S H, et al. Loop subdivision surface based progressive interpolation [J]. Journal of Computer Science and Technology, 2009, 24(1): 39-46.

[13] 林曉晶, 潘日晶. 一種基于Loop細分的漸進插值方法[J]. 福建師范大學學報: 自然科學版, 2014(1): 18-24.

[14] CHEN Q, PRAUTZSCH H. General triangular midpoint subdivision [J]. Computer Aided Geometric Design, 2014, 31(7): 475-485.

[15] MA W Y, MA X H, TSO S-K, et al. A direct approach for subdivision surface fitting from a dense triangle mesh [J]. Computer Aided Design, 2004, 36(6): 525-536.

[16] ZHENG J, CAI Y. Interpolation over arbitrary topology meshes using a two-phase subdivision scheme [J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(3): 301-310.

A Progressive Interpolation Scheme for Loop Subdivision Surfaces with Shape Adjustment

CHEN Tiantian, YAN Di, WANG Wei, ZHAO Gang

(School of Mechanical Engineering and Automation, Beihang University, Beijing 100191, China)

Aming at the problems that Loop subdivision can’t satisfy the shape adjustment and interpolate the given mesh, a progressive interpolation scheme for Loop subdivision surfaces with shape adjustment is presented. Firstly, an equivalent Loop subdivision mask that can adjust the mesh vertices uniformly and facilitate the introduction of weight to adjust the shape of subdivision surfaces is proposed. Secondly, the new grid is generated by the iterative adjustment of the initial control grid, and using the two-phase Loop subdivision scheme presented in this paper to subdivide the new mesh, the shape-adjustable Loop subdivision surface that interpolate the initial control vertices is obtained. Finally, the convergence of the scheme is proved and some typical examples are illustrated to verify its effectiveness.

Loop subdivision; shape adjustment; progressive interpolation; weight

TP 391

10.11996/JG.j.2095-302X.2018030395

A

2095-302X(2018)03-0395-07

2017-01-14；

2017-05-11

國家自然科學基金項目(51305016，61572056)

陳甜甜(1982–)，女，上海人，實驗師，博士，碩士生導師。主要研究方向為CAD/CAM、復雜曲線曲面造型。E-mail：chentt@buaa.edu.cn