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

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

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

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

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

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

1 預(yù)備知識

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

(1)

其中

(2)

l1和l2的奇偶性相同，且

(3)

1.1 M進制細分時需要給出掩模公式的點數(shù)

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

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

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

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

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

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

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

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

fnum=3k2+ik+t,

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

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

(4)

2 M進制細分掩模的計算

2.1 計算方法

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

根據(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時,在Q(x,y)支集中對生成的部分點標(biāo)號如圖3所示.

另一方面,由

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

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

圖3 M=2時新生成的部分點標(biā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,得從而對所有的cm-i,n-j,僅當(dāng)且時,cm-i,n-j≠0.這里l1～l4共有(3M2-3M+1)2種情況,利用式(4)分別計算每種情況的系數(shù)

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

(6)

2) 新邊點的掩模.

3) 新面點的掩模.

綜上,可得:

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

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

2.2 掩模實例

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

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

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

圖5 M=2時的掩模Fig.5 Masks for M=2

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

新頂點：666,105,105,105,105,105,105;

新邊點1：630,196,140,140,70,70,50;

新邊點2：545,310,165,165,40,40,20,5,5,1;

新邊點3：432,432,174,174,18,18,18,18,6,6;

新面點1：570,240,240,90,90,30,30,6;

新面點2：472,356,264,102,50,22,14,10,4,2;

新面點3：372,372,372,54,54,54,3,3,3,3,3,3.

圖6 M=6時的掩模Fig.6 Masks for M=6

3 應(yīng)用實例

圖7和圖8為利用本文算法得到的五進制細分掩模計算實例.

圖7 五進制細分實例1(Feline,初始網(wǎng)格有250個點,504個面；五進制細分1次得到258 046個點,516 096個面)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 五進制細分實例2(Horse,初始網(wǎng)格有112個點,220個面；五進制細分1次得到112 642個點,225 280個面)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ī)則點的多進制細分掩模計算方法.此外,利用生成函數(shù)的方法也可以得到三角形網(wǎng)格規(guī)則點的多進制細分掩模計算方法.結(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樣條的可加細性質(zhì) [D].長春：吉林大學(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樣條多尺度細分 [J].吉林大學(xué)學(xué)報: 理學(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)揚.基于三角網(wǎng)格的任意尺度細分方法模板研究 [D].長春：吉林大學(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樣條的可加細性質(zhì)研究 [D].長春：吉林大學(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.