王 燕，李志明

(1.合肥師范學院 數(shù)學與統(tǒng)計學院,安徽 合肥 230601；2. 合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009)

?

Bézier-Said-Wang型廣義Ball曲線的細分算法

王 燕1，李志明2

(1.合肥師范學院 數(shù)學與統(tǒng)計學院,安徽 合肥 230601；2. 合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009)

利用BSWGB曲線的對偶基給出了BSWGB曲線的顯式細分算法。與傳統(tǒng)的細分方法相比，該算法避免了繁瑣的矩陣求逆運算和基轉(zhuǎn)換運算，而且該算法的使用可歸結為細分矩陣與頂點向量陣的乘積，易于繪圖。該方法給出了現(xiàn)有的一些廣義Ball曲線的細分矩陣的統(tǒng)一表達式，可以很方便的利用此表達式，解決這一類曲線的細分問題。最后通過實例證明了本文算法的有效性。

BSWGB曲線；對偶基；細分算法；細分矩陣

用于CONSURF系統(tǒng)的三次Ball曲線是Ball在1974年提出的[1]。從此之后，許多學者對三次Ball曲線作了擴展[2-7]。隨著Said-Ball曲線、Wang-Ball 曲線等廣義Ball曲線的提出，許多學者開始研究各種不同的廣義Ball曲線的統(tǒng)一表示。Wu[8]提出了Wang-Said型廣義Ball曲線和Said- Bézier型廣義Ball曲線(分別簡稱為WSGB曲線和SBGB曲線)，分別得到了 Wang-Ball 曲線和Said-Ball曲線，以及Said-Ball曲線和 Bézier曲線的統(tǒng)一表示。沈[9]構造了一組介于Wang-Ball 曲線和Said-Ball曲線之間的新的廣義Ball曲線。汪志華和朱曉臨[10]給出了Bézier曲線和Wang-Ball 曲線的統(tǒng)一表示，簡稱WBGB曲線。張莉[11]提出了Bézier-Said-Wang型廣義Ball曲線，包含了現(xiàn)有的廣義Ball曲線(Said- Ball 曲線、Wang-Ball曲線、WSGB曲線、SBGB曲線和WBGB曲線)，Bézier曲線以及中間曲線。

細分算法是CAGD中構造曲線曲面的一種有效的方法，在曲線曲面的降階、求交等中具有重要的作用。王國瑾[4]中給出了Wang-Ball曲線的細分方法：首先求出Wang-Ball基轉(zhuǎn)換成冪基的轉(zhuǎn)換矩陣，然后求轉(zhuǎn)換矩陣的逆矩陣，再乘以另一個由轉(zhuǎn)換矩陣演化得到的矩陣。該方法適用于任何多項式參數(shù)曲線, 是一種普遍適用的方法，但未給出顯式表達式。蔣素榮和王國瑾[12]運用類似的方法給出了Wang-Ball曲線的中點離散公式。余等[13]給出了Wang-Ball曲線的細分算法。2006年，江和檀[14]給出了WSGB曲線的細分算法。本文利用文獻[11]中提出的對偶基給出了BSWGB曲線的細分算法。這個方法與傳統(tǒng)的細分方法相比，可以避免繁瑣的矩陣求逆運算和BSWGB基轉(zhuǎn)換成冪基的運算。并且，當BSWGB基中的參數(shù)K和L取不同的值時，該方法給出了現(xiàn)有的一些廣義Ball曲線的細分算法的統(tǒng)一表示。

1 Bézier-Said-Wang型廣義Ball曲線

2 BSWGB基函數(shù)的對偶基

(1)

(2)

其中,

(i,j=0,1,…,n).

3 BSWGB曲線的細分算法

不失一般性，我們假設n=2m+1。

給定一個實數(shù)c,0≤c≤1，記

(3)

和

(4)

分別表示BSWGB曲線在區(qū)間[0,c]和[c,1]上相應的部分。

(5)

(6)

定理2 由式(5)定義的曲線的控制頂點定義如下：

(Q0,Q1,…,Qn)T=S(c)(P0,P1,…,Pn)T,

(7)

其中S(c)=(sij)(2m+2)×(2m+2)稱為細分矩陣，矩陣的元素為：

1) 0≤i≤m-K-L,

(8)

(9)

(10)

(11)

2)m-K-L+1≤i≤m-L,

(12)

(13)

(14)

(15)

3)m-L+1≤i≤m

(16)

(17)

(18)

(19)

證明 由定理1，公式(3)，公式(5)和公式(7) 可以得到：

sij=λiUj(ct,K,L),s2m+1-i,j=λ2m+1-iUj(ct,K,L),

第一種情況。當0≤i≤m-K-L，

(1)當0≤j≤m-K-L時，

(2)當m-K-L+1≤j≤m-L-1時，

(3)當m-L≤j≤m-1時，

(4)當j=m時，

由(1) ～ (4)，可以證明公式(8) 和公式(9)。

同理可以由公式(2)證明公式(10)和(11) 。

第2種情況。當m-K-L+1≤i≤m-L時，證明過程完全類似于第1種情況。由公式(1)和公式(2)，可以得到公式(12) ～ 公式 (15)。

第3種情況。當m-L+1≤i≤m時，由公式(1)可以得到

當0≤j≤m-K-L時，

當m-K-L+1≤j≤m-L-1，m-L≤j≤m-1和j=m 時，可以得到類似的結果，即公式(16) 和公式(17) 。

同理可以由公式(2)得到公式(10) 和公式(11) 。

證畢。

根據(jù)BSWGB基函數(shù)的對稱性和定理2，得到下面的定理3。

定理3 由式(6)定義的曲線的控制頂點為：

4 數(shù)值例子

例1 令n=5,K=L=1，由定理2可以得到如下細分矩陣：

例2 令n=7,K=0,L=1時，BSWGB曲線即為WSGB曲線，可以得到與文獻[15]中一樣的細分矩陣：

曲線曲面的細分算法用于曲線曲面的降階，可以提高降階的精度，降低降階的誤差，下面舉例說明。

例3 文獻[16]中給出了n=7,L=1時的WSGB曲線(對應本文的n=7,K=0,L=1的BSWGB曲線)的降階，原曲線的控制頂點為{(220,110),(160,220),(180,340),(260,400),

(355,425),(470,320),(490,200),(420,100)},利用擾動法將一階后的曲線的控制頂點為{(220,110),(160,220),(180,340),(307.5,412.5),(470,320),(490,200),(420,100)}(如圖1)，降階誤差為error=17.813，降階誤差比較大，這時候可以利用WSGB曲線的細分算法對曲線做細分，再逐段用擾動法降階。

圖1 七次WSGB曲線的降階

由例2得到的細分矩陣將該WSGB曲線細分一次(取c=0.5)，所得的細分曲線如圖2(a)所示，然后用擾動法分別對兩段曲線進行降階，得到的降階曲線如圖2(b)所示。

圖2 七次WSGB曲線細分后降階

為了更好的理解，給出了降階前后控制多邊形和曲線的局部放大圖(如圖2(c)-2(f)所示)。細分后再利用擾動法降階的誤差為error=0.0366，比直接利用擾動法降階的誤差大大的減少了。

5 結論

本文給出了BSWGB曲線的顯式細分算法，包含Said-Ball曲線、Wang-Ball曲線、 WSGB曲線、SBGB曲線、WBGB曲線和中間曲線的細分矩陣?？梢岳眠@個細分矩陣解決這類曲線的細分問題，只需要修改參數(shù)K和L,就可以快速的得到中間狀態(tài)的其它過渡曲線的細分矩陣, 加快了曲線、曲面的生成速度, 對計算機輔助幾何設計及圖形繪制系統(tǒng)的效率具有重要的意義。最后用實例說明了本文方法的有效性，并舉例說明了細分算法在曲線降階中的應用，細分后再進行降階比直接降階所得的誤差要小。本文的方法也可推廣到曲面細分的情形。

[1] A.A. Ball, CONSURF. Part one: Introduction of the conic lofting tile [J]. Computer-Aided Design, 1974, 6 (4): 243-249.

[2] A.A. Ball, CONSURF. Part two: Description of the algorithms [J]. Computer-Aided Design, 1975, 7 (4): 237-242.

[3] H.B. Said. A generalized Ball curve and its recursive algorithm [J]. ACM Transactions on Graphics, 1989, 8 (4): 360-371.

[4]王國瑾. 高次Ball曲線及其幾何性質(zhì)[J]. 高校應用數(shù)學學報(A輯),1987, 2(1): 126-140.

[5] T.N.T. Goodman, H.B. Said. Properties of generalized Ball curves and surfaces [J]. Computer-Aided Design, 1991, 23 (8): 554-560.

[6] T.N.T. Goodman, H.B. Said. Shape-preserving properties of the generalized Ball basis [J]. Computer Aided Geometric Design, 1991, 8 (2): 115-121.

[7] S.M. Hu, G.Z. Wang, T.G. Jin. Properties of two types of generalized Ball curves [J]. Computer-Aided Design, 1996, 28 (2): 125-133.

[8] H.Y. Wu. Unifying representation of Bézier curve and generalized Ball curves [J]. Applied Mathematics: A Journal of Chinese Universities Series B, 2000, 15 (1): 109-121.

[9]沈莞薔, 汪國昭. Ball基的推廣[J]. 軟件學報, 2005, 16 (11): 1992-1999.

[10]汪志華, 朱曉臨. Bézier曲線與Wang-Ball曲線的統(tǒng)一表示[J]. 計算機輔助設計與圖形學學報, 2008, 20 (7): 888-893.

[11] L. Zhang, J.Q. Tan, Z.Y. Dong. The dual bases for the Bézier-Said-Wang type generalized Ball polynomial bases and their applications [J]. Applied Mathematics and Computations, 2010, 217 (7): 3088-3101.

[12] 蔣素榮, 王國瑾. Bézier 曲線到Wang-Ball 曲線的轉(zhuǎn)換矩陣及其應用[J]. 計算機學報, 2005, 28 (1): 75-80 .

[13] 余宏杰, 江平, 汪峻萍等. Wang-Ball 曲線的細分算法及包絡[J]. 計算機輔助設計與圖形學學報, 2005, 17 (4) : 637- 643.

[14] P. Jiang, J.Q. Tan. The subdivision algorithm for the generalized Ball curves [J]. Journal of Information & Computational Science, 2006, 3 (1): 21-31.

[15] 余宏杰. Wang-Said型廣義Ball曲線的細分算法[J]. 計算機輔助設計與圖形學學報, 2009, 21 (5) : 600-605.

[16] 江平, 檀結慶. Wang-Said型廣義Ball曲線的降階 [J]. 軟件學報, 2006, 17(增刊): 93-102.

The Subdivision Algorithm for Bézier-Said-Wang Type Generalized Ball Curves

WANG Yan, LI Zhiming

(1. School of Mathematics and Statistics, Hefei Normal University, Hefei 230601;2. School of Computer and Information, Hefei University of Technology, Hefei 230009)

This method gives an explicit subdivision matrix by using the dual bases of BSWGB bases, which is different from with the traditional subdivision algorithm needed to convert BSWGB bases into power bases and solve the inverse matrix. The algorithm can be efficiently achieved by multiple of subdivision matrix and vector of the vertices which leads to simple drawing of the curves. This algorithm is the unifying representation of subdivision matrices of the existed generalized Ball curves, which can be used in solving the subdivision of this kind of curves. Numerical examples are also given to show the effectiveness of our methods.

BSWGB curves; dual basis; subdivision algorithm; subdivision matrix

2016-08-10

合肥師范學院人才科研啟動基金(2014rcjj05)

王燕(1985-)，女，山東泰安人，講師，博士，主要研究方向為：計算機輔助幾何設計。

TP391.72

A

1674-2273(2016)06-0001-9