三角形網(wǎng)格規(guī)則點(diǎn)的多進(jìn)制細(xì)分算法

趙義武,婁 巖,李 強(qiáng),戰(zhàn) 揚(yáng),梁學(xué)章

(1.長(zhǎng)春理工大學(xué) 空間光電技術(shù)國(guó)家地方聯(lián)合工程研究中心,長(zhǎng)春 130022;2.吉林大學(xué) 數(shù)學(xué)學(xué)院,長(zhǎng)春 130012)

對(duì)基于三角形網(wǎng)格的多進(jìn)制曲面細(xì)分算法的研究目前已有許多結(jié)果.文獻(xiàn)[1-7]討論了基于三角形網(wǎng)格的三進(jìn)制細(xì)分算法;文獻(xiàn)[8-9]討論了二元Box樣條和最小支集二元B樣條的多進(jìn)制細(xì)分方法;文獻(xiàn)[10]給出了Ⅰ型和Ⅱ型剖分上的多元B樣條多進(jìn)制細(xì)分方程;文獻(xiàn)[11]給出了多進(jìn)制細(xì)分在規(guī)則點(diǎn)的掩模表達(dá)式,但未給出嚴(yán)格證明.圖1為初始網(wǎng)格與應(yīng)用三進(jìn)制Loop細(xì)分算法2次的結(jié)果及在規(guī)則點(diǎn)的三進(jìn)制細(xì)分掩模.

上述方法均未給出規(guī)則點(diǎn)的多進(jìn)制細(xì)分掩模的顯式表達(dá)式,也未嚴(yán)格說明掩模用到點(diǎn)的范圍.事實(shí)上,二進(jìn)制細(xì)分算法存在局限性,如當(dāng)初始網(wǎng)格確定后,對(duì)每次細(xì)分生成的點(diǎn)不能進(jìn)行人為控制,經(jīng)常會(huì)遇到前一步細(xì)分生成的點(diǎn)數(shù)不滿足實(shí)際需求,而再細(xì)分一次生成的點(diǎn)有大量冗余的情況.不僅需要大量的內(nèi)存和硬盤空間,增加了計(jì)算量,提高了對(duì)運(yùn)算和顯示設(shè)備的性能要求,而且在后期的渲染和顯示時(shí),經(jīng)常出現(xiàn)“慢”和“卡”的現(xiàn)象.解決這些問題的方法是改變細(xì)分算法的進(jìn)制,根據(jù)實(shí)際需求確定細(xì)分進(jìn)制,從而克服二進(jìn)制細(xì)分算法的局限性,并能滿足實(shí)際需求.

圖1 初始網(wǎng)格(A)與利用三進(jìn)制Loop細(xì)分算法2次的結(jié)果(B)及規(guī)則點(diǎn)的三進(jìn)制掩模(C)Fig.1 Original control mesh (A) followed by two ternary Loop subdivisions (B) and regular masks (C)

1 預(yù)備知識(shí)

掩模(Mask)也稱為面具,表示在細(xì)分過程中利用舊點(diǎn)生成新點(diǎn)的計(jì)算規(guī)則.掩模的系數(shù)表示相應(yīng)的舊點(diǎn)對(duì)生成新點(diǎn)的貢獻(xiàn).若一個(gè)點(diǎn)有n條邊與它相連,則稱該點(diǎn)的價(jià)為n.對(duì)三角形網(wǎng)格,規(guī)則點(diǎn)的價(jià)為6(規(guī)則邊界點(diǎn)的價(jià)為4).

(1)

其中

(2)

l1和l2的奇偶性相同，且

(3)

1.1 M進(jìn)制細(xì)分時(shí)需要給出掩模公式的點(diǎn)數(shù)

在細(xì)分過程中,雖然需要計(jì)算的新頂點(diǎn)、新邊點(diǎn)和新面點(diǎn)的個(gè)數(shù)很多,但根據(jù)對(duì)稱性,許多新點(diǎn)采用的掩模系數(shù)結(jié)構(gòu)相同,從而極大減少了需要給出掩模公式的點(diǎn)個(gè)數(shù).在一個(gè)三角形內(nèi),需要給出掩模公式的點(diǎn)數(shù)如下.

1) 頂點(diǎn)數(shù)：需要給出掩模的頂點(diǎn)數(shù)為1.

3) 面點(diǎn)數(shù)：采用從三角形三邊形成的環(huán)向內(nèi)收縮的方法來考慮需要給出掩模的面點(diǎn)個(gè)數(shù),最終收縮的結(jié)果必為下列3種情況之一：

① 收縮結(jié)果為1個(gè)點(diǎn),最后一層環(huán)上需要給出掩模的面點(diǎn)數(shù)為1,如圖2(A)所示;

② 收縮結(jié)果為1個(gè)小三角形,最后一層環(huán)上需要給出掩模的面點(diǎn)數(shù)為1,如圖2(B)所示;

③ 收縮結(jié)果為1個(gè)大三角形,最后一層環(huán)上需要給出掩模的面點(diǎn)數(shù)為2,如圖2(C)所示.

(A) 收縮結(jié)果為1個(gè)點(diǎn) (B) 收縮結(jié)果為1個(gè)小三角形 (C) 收縮結(jié)果為1個(gè)大三角形圖2 收縮結(jié)果Fig.2 Contraction results

命題1當(dāng)M=6k+i(i=0,1,…,5)時(shí),需要給出掩模公式的面點(diǎn)數(shù)為

fnum=3k2+ik+t,

其中: 當(dāng)i=0,1,2時(shí),t=0；當(dāng)i=3,4時(shí),t=1;當(dāng)i=5時(shí),t=2.

1.2 系數(shù)的計(jì)算公式

(4)

2 M進(jìn)制細(xì)分掩模的計(jì)算

2.1 計(jì)算方法

引理1給出的細(xì)分公式是Fourier變換形式,不是顯式計(jì)算公式.下面推導(dǎo)掩模的顯式計(jì)算公式.先確定哪些舊頂點(diǎn)對(duì)新點(diǎn)有貢獻(xiàn),然后求出相應(yīng)的掩模系數(shù).不失一般性,新生成的點(diǎn)應(yīng)包括新頂點(diǎn)、多個(gè)新邊點(diǎn)及多個(gè)新面點(diǎn),本文僅討論M≥4的情形.M=2,3時(shí)的情形類似.

根據(jù)引理1，有

利用Fourier逆變換,可得

其中l(wèi)1和l2及l(fā)3和l4分別滿足式(3).

注意到s(x,y)在加密網(wǎng)格上的表示為

而Q(x,y)在加密網(wǎng)格上可表示為

(5)

從而

設(shè)s(x,y)=Q(x,y).當(dāng)M=2時(shí),在Q(x,y)支集中對(duì)生成的部分點(diǎn)標(biāo)號(hào)如圖3所示.

另一方面,由

顯然Mm=l1+l3≤4M-4,可得

且Mn=l2+l4≤2M-2,從而

圖3 M=2時(shí)新生成的部分點(diǎn)標(biāo)號(hào) (虛線為加密的網(wǎng)格)Fig.3 Notation of the generated vertices for M=2 (dotted lines are the refined mesh)

其中m,n∈/M且M·m與M·n同奇偶.又由|l1|+|l2|≤2M-2且|l3|+|l4|≤2M-2,得從而對(duì)所有的cm-i,n-j,僅當(dāng)且時(shí),cm-i,n-j≠0.這里l1～l4共有(3M2-3M+1)2種情況,利用式(4)分別計(jì)算每種情況的系數(shù)

下面以舊頂點(diǎn)(0,0)右上三角形中的點(diǎn)為例給出掩模計(jì)算方法.

(6)

2) 新邊點(diǎn)的掩模.

3) 新面點(diǎn)的掩模.

綜上,可得:

定理1在M進(jìn)制三角形細(xì)分算法中,在一個(gè)三角形上生成的所有新點(diǎn)為圍繞該三角形的一層三角形環(huán)所有頂點(diǎn)的線性組合,組合公式為式(6)～(11).

圖4給出了一個(gè)三角形(粗線表示)及圍繞此三角形的一層環(huán).

2.2 掩模實(shí)例

為了更直觀地說明上述方法,下面以M=2的情形為例使用上述方法推導(dǎo)細(xì)分算法的掩模公式.此時(shí)

其中l(wèi)1和l2及l(fā)3和l4分別滿足式(3).這里l1～l4共有49種情況,分別計(jì)算系數(shù),合并同類項(xiàng),再與式(5)比較知,當(dāng)M=2時(shí),計(jì)算得到如圖5所示的掩模系數(shù)如下: 新頂點(diǎn)：10,1,1,1,1,1,1;新邊點(diǎn)：6,6,2,2 (分母統(tǒng)一為24).該結(jié)果與Loop給出的二進(jìn)制三角形細(xì)分掩模相同.

圖4 三角形(粗線表示)及圍繞此三角形的一層環(huán)Fig.4 A triangle (thick line) and the first ring around it

圖5 M=2時(shí)的掩模Fig.5 Masks for M=2

采用本文方法得到的三進(jìn)制細(xì)分掩模公式與Loop給出的三進(jìn)制細(xì)分掩模公式相同(見圖1).對(duì)任意給定的M,都可以采用本文方法求得規(guī)則點(diǎn)的細(xì)分掩模.當(dāng)M=6時(shí),計(jì)算得到如圖6所示的細(xì)分掩模(分母統(tǒng)一為64)如下:

新頂點(diǎn)：666,105,105,105,105,105,105;

新邊點(diǎn)1：630,196,140,140,70,70,50;

新邊點(diǎn)2：545,310,165,165,40,40,20,5,5,1;

新邊點(diǎn)3：432,432,174,174,18,18,18,18,6,6;

新面點(diǎn)1：570,240,240,90,90,30,30,6;

新面點(diǎn)2：472,356,264,102,50,22,14,10,4,2;

新面點(diǎn)3：372,372,372,54,54,54,3,3,3,3,3,3.

圖6 M=6時(shí)的掩模Fig.6 Masks for M=6

3 應(yīng)用實(shí)例

圖7和圖8為利用本文算法得到的五進(jìn)制細(xì)分掩模計(jì)算實(shí)例.

圖7 五進(jìn)制細(xì)分實(shí)例1(Feline,初始網(wǎng)格有250個(gè)點(diǎn),504個(gè)面；五進(jìn)制細(xì)分1次得到258 046個(gè)點(diǎn),516 096個(gè)面)Fig.7 Segmentation example 1 by quinary subdivision (Feline,initial mesh with 250 points,504 surfaces,segment 1 get 258 046 points,516 096 surfaces)

圖8 五進(jìn)制細(xì)分實(shí)例2(Horse,初始網(wǎng)格有112個(gè)點(diǎn),220個(gè)面；五進(jìn)制細(xì)分1次得到112 642個(gè)點(diǎn),225 280個(gè)面)Fig.8 Segmentation example 2 by quinary subdivision (Horse,initial mesh with 112 points,220 surfaces,segment 1 get 112 642 points,225 280 surfaces)

綜上,本文得到了三角形網(wǎng)格規(guī)則點(diǎn)的多進(jìn)制細(xì)分掩模計(jì)算方法.此外,利用生成函數(shù)的方法也可以得到三角形網(wǎng)格規(guī)則點(diǎn)的多進(jìn)制細(xì)分掩模計(jì)算方法.結(jié)果表明,兩種方法所得結(jié)果相符.

[1] Loop C.Smooth Ternary Subdivision of Triangle Meshes [C]//Curve and Surface Fitting：Saint-Malo 2002.Brentwood: Nashboro Press,2003：295-302.

[2] Dodgson N A,Augsdorfer U H,Cashman T J,et al.Deriving Box-Spline Subdivision Schemes [C]//Proceedings of the 13th IMA International Conference on Mathematics of Surfaces XⅢ.Berlin: Springer-Verlag,2009：106-123.

[3] Beccari C,Casciola G,Romani L.Shape Controlled Interpolatory Ternary Subdivision [J].Applied Mathematics and Computation,2009,215(3)：916-927.

[4] HAN Bin,JIA Rong-qing.OptimalC2Two-Dimensional Interpolatory Ternary Subdivision Schemes with Two-Ring Stencils [J].Math Comp,2006,75：1287-1308.

[5] LI Gui-qing,MA Wei-yin.Interpolatory Ternary Subdivision Surfaces [J].Computer Aided Geometric Design,2006,23(1)：45-77.

[6] ZHENG Hong-chan,PENG Guo-hua,YE Zheng-lin,et al.A New Ternary Interpolatory Subdivision Scheme for Polyhedral Meshes with Arbitrary Topology [J].Journal of Physics：Conference Series,2008,96(1)：1-7.

[7] Ghulam M,DENG Jian-song.Estimating Error Bounds for Ternary Subdivision Curves/Surfaces [J].Journal of Computational Mathematics,2007,25(4)：473-484.

[8] HAN Li-wen.On the Refinability of Multivariate B-Splines [D].Changchun：Jilin University,2002.(韓力文.關(guān)于多元B樣條的可加細(xì)性質(zhì) [D].長(zhǎng)春：吉林大學(xué),2002.)

[9] HAN Li-wen,WU Tie-ru.Multiresolution Subdivision of Bivariate B-Splines Based on Integral Method [J].Journal of Jilin University: Science Edition,2002,40(4)：358-360.(韓力文,伍鐵如.基于積分方法的二元B樣條多尺度細(xì)分 [J].吉林大學(xué)學(xué)報(bào): 理學(xué)版,2002,40(4)：358-360.)

[10] GUAN Yu-jing,HAN Li-wen,ZHOU Yun-shi.M-Band Subdivision of Multivariate B-Spline [J].Journal of Computational and Applied Mathematics,2004,163(1)：117-126.

[11] ZHAN Yang.Study of the Masks of M-Band Subdivision Algorithm Based on Triangulation Mesh [D].Changchun：Jilin University,2010.(戰(zhàn)揚(yáng).基于三角網(wǎng)格的任意尺度細(xì)分方法模板研究 [D].長(zhǎng)春：吉林大學(xué),2010.)

[12] Chui C K,WANG Ren-hong.Multivariate Spline Space [J].J Math Anal Appl,1983,94：197-221.

[13] ZHAO Yi-wu.On the Refinability of Multivariate B-Splines of Uniform Partition in Three Directions [D].Changchun：Jilin University,2003.(趙義武.均勻三向剖分上的B樣條的可加細(xì)性質(zhì)研究 [D].長(zhǎng)春：吉林大學(xué),2003.)

[14] ZHAO Yi-wu,HAN Li-wen.M-band Subdivision of Bivariate B-Splines of Uniform Partition in Three Directions [C]//Proceedings on Geometric Modeling and Processing.Los Alamitos,California: IEEE Computer Society,2004：355-358.