三角形網格規則點的多進制細分算法

趙義武,婁 巖,李 強,戰 揚,梁學章

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

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

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

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

1 預備知識

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

(1)

其中

(2)

l1和l2的奇偶性相同，且

(3)

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

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

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

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

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

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

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

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

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

fnum=3k2+ik+t,

其中: 當i=0,1,2時,t=0；當i=3,4時,t=1;當i=5時,t=2.

1.2 系數的計算公式

(4)

2 M進制細分掩模的計算

2.1 計算方法

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

根據引理1，有

利用Fourier逆變換,可得

其中l1和l2及l3和l4分別滿足式(3).

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

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

(5)

從而

設s(x,y)=Q(x,y).當M=2時,在Q(x,y)支集中對生成的部分點標號如圖3所示.

另一方面,由

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

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

圖3 M=2時新生成的部分點標號 (虛線為加密的網格)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,僅當且時,cm-i,n-j≠0.這里l1～l4共有(3M2-3M+1)2種情況,利用式(4)分別計算每種情況的系數

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

(6)

2) 新邊點的掩模.

3) 新面點的掩模.

綜上,可得:

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

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

2.2 掩模實例

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

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

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

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

采用本文方法得到的三進制細分掩模公式與Loop給出的三進制細分掩模公式相同(見圖1).對任意給定的M,都可以采用本文方法求得規則點的細分掩模.當M=6時,計算得到如圖6所示的細分掩模(分母統一為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 應用實例

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

圖7 五進制細分實例1(Feline,初始網格有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,初始網格有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)

綜上,本文得到了三角形網格規則點的多進制細分掩模計算方法.此外,利用生成函數的方法也可以得到三角形網格規則點的多進制細分掩模計算方法.結果表明,兩種方法所得結果相符.

[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.(韓力文.關于多元B樣條的可加細性質 [D].長春：吉林大學,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].吉林大學學報: 理學版,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.(戰揚.基于三角網格的任意尺度細分方法模板研究 [D].長春：吉林大學,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樣條的可加細性質研究 [D].長春：吉林大學,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.