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

?

形狀可調(diào)的Loop細(xì)分曲面漸進(jìn)插值方法

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

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

針對(duì)Loop細(xì)分無(wú)法調(diào)整形狀與不能插值的問(wèn)題，提出了一種形狀可調(diào)的Loop細(xì)分曲面漸進(jìn)插值方法。首先給出了一個(gè)既能對(duì)細(xì)分網(wǎng)格頂點(diǎn)統(tǒng)一調(diào)整又便于引入權(quán)因子實(shí)現(xiàn)細(xì)分曲面形狀可調(diào)的等價(jià)Loop細(xì)分模板。其次，通過(guò)漸進(jìn)迭代調(diào)整初始控制網(wǎng)格頂點(diǎn)生成新網(wǎng)格，運(yùn)用本文的兩步Loop細(xì)分方法對(duì)新網(wǎng)格進(jìn)行細(xì)分，得到插值于初始控制頂點(diǎn)的形狀可調(diào)的Loop細(xì)分曲面。最后，證明了該方法的收斂性，并給出實(shí)例驗(yàn)證了該方法的有效性。

Loop細(xì)分；形狀可調(diào)；漸進(jìn)插值；權(quán)因子

細(xì)分曲面造型技術(shù)由于具有算法簡(jiǎn)單、容易實(shí)現(xiàn)、可以表示任意拓?fù)浣Y(jié)構(gòu)的物體等優(yōu)點(diǎn)，已經(jīng)在幾何造型、計(jì)算機(jī)動(dòng)畫(huà)、游戲等領(lǐng)域得到了廣泛的應(yīng)用[1]。細(xì)分方法按其極限曲面是否插值于初始控制頂點(diǎn)分為逼近型細(xì)分方法與插值型細(xì)分方法。經(jīng)典的逼近型細(xì)分方法有Catmull-Clark細(xì)分[2]和Loop細(xì)分[3]，這類(lèi)細(xì)分方法的極限曲面相對(duì)初始網(wǎng)格都會(huì)有收縮[4]。典型的插值型細(xì)分方法有Butterfly細(xì)分[5]和Kobbelt細(xì)分[6]，這類(lèi)細(xì)分方法的極限曲面不存在收縮，但連續(xù)性不好，只能達(dá)到整體1連續(xù)，而且細(xì)分曲面也可能會(huì)產(chǎn)生一定程度的變形，因此僅僅憑借初始控制網(wǎng)格無(wú)法準(zhǔn)確預(yù)判其極限曲面的形狀。

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

通過(guò)研究Loop細(xì)分與廣義中點(diǎn)細(xì)分之間的聯(lián)系，本文給出了一種能對(duì)細(xì)分網(wǎng)格頂點(diǎn)統(tǒng)一調(diào)整的等價(jià)Loop細(xì)分模板，并在此模板的基礎(chǔ)上，提出了一種形狀可調(diào)的Loop細(xì)分曲面漸進(jìn)插值方法。該方法通過(guò)漸進(jìn)迭代調(diào)整初始控制頂點(diǎn)的位置，使得相應(yīng)的細(xì)分曲面插值于初始控制網(wǎng)格。同時(shí)通過(guò)在本文中給出的等價(jià)Loop細(xì)分模板中引入權(quán)因子，從而實(shí)現(xiàn)Loop細(xì)分曲面形狀可調(diào)的特性。

1 等價(jià)Loop細(xì)分模板

1.1 Loop細(xì)分

Loop細(xì)分方法是一種基于三角形網(wǎng)格的細(xì)分模式，其極限曲面是三向四次箱樣條曲面的推廣，在正則點(diǎn)和奇異點(diǎn)處可分別達(dá)到2連續(xù)與1連續(xù)。在實(shí)現(xiàn)過(guò)程中，新頂點(diǎn)-頂點(diǎn)和新邊點(diǎn)-頂點(diǎn)采用不同的規(guī)則進(jìn)行計(jì)算。文獻(xiàn)[3]中給出了新頂點(diǎn)與新邊點(diǎn)的計(jì)算公式。

1.2 等價(jià)Loop細(xì)分模板

廣義中點(diǎn)細(xì)分屬于1-4三角形面片分裂細(xì)分方法，其細(xì)分規(guī)則為

其中，R為線性細(xì)分；A為加權(quán)平均。R運(yùn)算與A運(yùn)算如圖1所示。

廣義中點(diǎn)細(xì)分在進(jìn)行運(yùn)算之后使用式(4)對(duì)所有細(xì)分網(wǎng)格頂點(diǎn)進(jìn)行運(yùn)算，由式(3)和式(4)得到進(jìn)行一次廣義中點(diǎn)細(xì)分之后內(nèi)部-頂點(diǎn)的計(jì)算表達(dá)式(5)和內(nèi)部-頂點(diǎn)的計(jì)算表達(dá)式(6)，即

內(nèi)部-頂點(diǎn)的計(jì)算表達(dá)式

(5)

內(nèi)部-頂點(diǎn)的計(jì)算表達(dá)式

廣義中點(diǎn)細(xì)分邊界-頂點(diǎn)與邊界-頂點(diǎn)的處理方式與Loop細(xì)分一致，給出廣義中點(diǎn)細(xì)分的等價(jià)細(xì)分模板如圖3所示。通過(guò)對(duì)比該等價(jià)細(xì)分模板和Loop細(xì)分模板可以發(fā)現(xiàn)：兩者在形式上完全一致。

圖3 廣義中點(diǎn)細(xì)分的等價(jià)模板

為了保持Loop細(xì)分曲面的形狀不變，又兼具廣義中點(diǎn)細(xì)分的細(xì)分網(wǎng)格頂點(diǎn)統(tǒng)一調(diào)整的優(yōu)勢(shì)，本文給出了一個(gè)既能對(duì)細(xì)分網(wǎng)格頂點(diǎn)統(tǒng)一調(diào)整又便于引入權(quán)因子實(shí)現(xiàn)細(xì)分曲面形狀可調(diào)的等價(jià)Loop細(xì)分模板。

對(duì)比Loop細(xì)分的幾何規(guī)則和廣義中點(diǎn)細(xì)分的等價(jià)模板可知，當(dāng)權(quán)因子滿足式(7)時(shí)，Loop細(xì)分的內(nèi)部-頂點(diǎn)與內(nèi)部-頂點(diǎn)才可以進(jìn)行統(tǒng)一調(diào)整，即

其中，為相應(yīng)的內(nèi)部-頂點(diǎn)的價(jià)，化簡(jiǎn)得

本節(jié)通過(guò)分析對(duì)比廣義中點(diǎn)細(xì)分的等價(jià)細(xì)分模板與Loop細(xì)分模板之間的聯(lián)系，給出了-頂點(diǎn)和-頂點(diǎn)統(tǒng)一調(diào)整的等價(jià)Loop細(xì)分模板。總體來(lái)說(shuō)，等價(jià)Loop細(xì)分模板有以下兩方面的意義，一是能夠簡(jiǎn)化Loop細(xì)分算法在計(jì)算機(jī)上的實(shí)現(xiàn)過(guò)程，二是便于在Loop細(xì)分模板中引入權(quán)因子，以實(shí)現(xiàn)Loop細(xì)分曲面形狀可調(diào)。

圖4 Loop細(xì)分網(wǎng)格頂點(diǎn)統(tǒng)一調(diào)整的等價(jià)細(xì)分模板

2 兩步漸進(jìn)插值細(xì)分方法

Loop細(xì)分是一種基于三角形網(wǎng)格的逼近型細(xì)分方法，這種方法的細(xì)分曲面不能插值于初始網(wǎng)格的控制頂點(diǎn)，相比于初始網(wǎng)格存在一定的收縮，且細(xì)分曲面形狀不可調(diào)整。因此，本文提出了一種形狀可調(diào)的Loop細(xì)分曲面漸進(jìn)插值方法，該方法既能實(shí)現(xiàn)插值，又可以通過(guò)改變權(quán)因子的大小實(shí)現(xiàn)細(xì)分曲面形狀可調(diào)。

2.1 兩步Loop細(xì)分

兩步細(xì)分方法是ZHENG和CAI[16]在2006年首次提出的一種細(xì)分方法，該方法實(shí)現(xiàn)了Catmull-Clark細(xì)分方法的形狀可調(diào)。本文將這種方法應(yīng)用于Loop細(xì)分，結(jié)合迭代插值算法實(shí)現(xiàn)形狀可調(diào)的Loop細(xì)分漸進(jìn)插值方法。具體的兩步Loop細(xì)分實(shí)現(xiàn)過(guò)程如下：

(2) 對(duì)第(1)步得到的新網(wǎng)格運(yùn)用等價(jià)Loop細(xì)分模板進(jìn)行細(xì)分，直至得到極限細(xì)分曲面。

2.2 兩步Loop細(xì)分方法的極限點(diǎn)公式

2.3 迭代插值

3 收斂性證明

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

根據(jù)矩陣的這些性質(zhì)，可將其分解為一個(gè)對(duì)角矩陣和一個(gè)對(duì)稱(chēng)矩陣，即。其中，對(duì)角矩陣為

故

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

4 算法實(shí)例

所有實(shí)驗(yàn)均在配置為Intel(R) Core(TM) i5-6500 CPU @ 3.20 GHz 處理器和8 GB內(nèi)存的電腦上進(jìn)行，程序運(yùn)行環(huán)境為Visual Studio 2010。實(shí)驗(yàn)均在Knot、Cat、Pig和Bear等4種網(wǎng)格模型的基礎(chǔ)上進(jìn)行。

首先，為了對(duì)比傳統(tǒng)Loop細(xì)分模板與等價(jià)Loop細(xì)分模板的運(yùn)行時(shí)間，以Loop細(xì)分4次為例，對(duì)4種網(wǎng)格模型進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表1。從表1中可以看出，隨著初始網(wǎng)格頂點(diǎn)數(shù)的增加，等價(jià)Loop細(xì)分模板在實(shí)現(xiàn)Loop細(xì)分上的優(yōu)勢(shì)愈發(fā)明顯，效率更高。

表1 傳統(tǒng)Loop細(xì)分方法與等價(jià)Loop細(xì)分模板的運(yùn)行時(shí)間對(duì)比

圖 5 不同值所對(duì)應(yīng)的Knot 模型插值曲面

圖 6 Loop 細(xì)分曲面及不同值所對(duì)應(yīng)的Cat 模型插值曲面

圖 7 Loop 細(xì)分曲面及不同值所對(duì)應(yīng)的Pig 模型插值曲面

圖 8 Loop 細(xì)分曲面及不同值所對(duì)應(yīng)的Bear 模型插值曲面

5 結(jié) 論

[1] 李桂清. 細(xì)分曲面造型及應(yīng)用[D]. 北京: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所, 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細(xì)分的漸進(jìn)插值方法[J]. 福建師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 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

國(guó)家自然科學(xué)基金項(xiàng)目(51305016，61572056)

陳甜甜(1982–)，女，上海人，實(shí)驗(yàn)師，博士，碩士生導(dǎo)師。主要研究方向?yàn)镃AD/CAM、復(fù)雜曲線曲面造型。E-mail：chentt@buaa.edu.cn