王 燕， 李志明

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

Wang-Bézier型廣義Ball曲線的降階

王 燕1， 李志明2

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

分別應(yīng)用擾動法和最佳一致逼近法，提出WBGB曲線的降階算法，并給出了誤差估計(jì)。實(shí)驗(yàn)結(jié)果表明，用最佳一致逼近法效果比擾動法要好。若利用擾動法得到的降階曲線不能達(dá)到預(yù)期的誤差，則可以先利用細(xì)分算法對曲線做細(xì)分，再逐段用擾動法降階。WBGB曲線的降階算法豐富了廣義Ball曲線曲面的理論。

WBGB曲線；擾動法；最佳一致逼近

Ball[1-3]在 CONSURF系統(tǒng)中首次提出了 Ball基函數(shù)，Ball曲線的基函數(shù)僅限于三次，因此一些學(xué)者對其做了次數(shù)上的推廣和研究，得到了高次的 Ball曲線，包括 Said-Ball曲線[4]與 Wang-Ball曲線[5]以及其一些擴(kuò)展曲線[6-9]。這些擴(kuò)展曲線與Bézier曲線有許多類似的性質(zhì)，如計(jì)算穩(wěn)定性、對稱性、凸包性、端點(diǎn)插值性等，在曲線求值及升降階的計(jì)算速度方面，Ball曲線明顯優(yōu)于 Bézier曲線。2000年，Wu[10]根據(jù) Wang-Ball曲線和Said-Ball曲線的特點(diǎn)，又提出了兩族新的帶位置參數(shù)的廣義Ball曲線(Wang-Said型廣義Ball曲線和Said-Bézier型廣義Ball曲線，簡稱WSGB曲線和SBGB曲線)。WSGB曲線包含了Wang-Ball曲線、Said-Ball曲線以及介于兩者之間的曲線；SBGB曲線包含了 Said-Ball曲線、Bézier曲線以及介于兩者之間的曲線，很自然的會想到能不能構(gòu)造一組新的曲線，使其包含 Wang-Ball曲線、Bézier曲線以及介于兩者之間的曲線。2008年，汪志華和朱曉臨[11]通過引入位置參數(shù)，定義了能實(shí)現(xiàn)這一目標(biāo)的曲線，稱其為Wang-Bézier型廣義Ball曲線，簡稱WBGB曲線。

對高次曲線曲面的降階處理是實(shí)現(xiàn)不同階數(shù)

的曲線曲面的數(shù)據(jù)轉(zhuǎn)換的必要步驟。Hu等[12]曾討論了Said-Ball曲線與Wang-Ball曲線的降階，Wu[10]給出了WSGB曲線和SBGB曲線的降階公式，江平和檀結(jié)慶[13]給出了WSGB曲線的降階算法，劉剛和王國瑾[14]給出了SBGB曲線的顯式降多階逼近算法，但是關(guān)于WBGB曲線的降階問題鮮有文章涉及。

本文分別應(yīng)用擾動法和最佳一致逼近法，給出WBGB曲線的降階算法及誤差估計(jì)。實(shí)驗(yàn)結(jié)果表明，用最佳一致逼近法比擾動法的效果要好，若利用擾動法得到的降階曲線不能達(dá)到預(yù)期的誤差，則可以先利用細(xì)分算法對曲線做細(xì)分，再逐段用擾動法降階。WBGB曲線的降階算法豐富了廣義Ball曲線曲面的理論體系。

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

定義1. 給定自然數(shù)m，L=0,1,…,m,n=2m+1，或n=2m，n+1個(gè)R2( R3)中的控制頂點(diǎn)｛pi｝, i=0,1,… ,n, n次WBGB曲線定義如下

式中，「n」與「n」分別表示小于或等于n的最大的整數(shù)與大于或等于n的最小的整數(shù)。顯然，當(dāng) L=0時(shí)，p( t, n,0)為Bézier曲線；當(dāng)L=m時(shí)，p ( t, n,m) 為Wang-Ball曲線；當(dāng)1 ≤L≤m-1時(shí)，為介于兩者之間的曲線(如圖1為L取不同值時(shí)對應(yīng)的7次WBGB曲線)。

2 WBGB曲線的降階

下面將給出將n次的 WBGB曲線式(1)降成n-1次曲線的方法，如式(3)

圖1 7次WBGB曲線

2.1 WBGB曲線的可精確降階條件

由定義1可知，在1≤L≤m的情況下，當(dāng)n為奇數(shù)時(shí)，ωi( t, n, L)僅中間兩項(xiàng)次數(shù)為n，即

當(dāng)n為偶數(shù)時(shí)，ωi( t, n, L)僅中間三項(xiàng)次數(shù)為n，即

故p( t, n, L)的首項(xiàng)系數(shù)為

定理1. 定義1中的n次WBGB曲線 (,,) p t n L可精確降階為 n-1次WBGB曲線的充要條件，為其控制頂點(diǎn)滿足：當(dāng) n=2 m+1時(shí)，Δpm=0；當(dāng)n=2m時(shí)，，即

根據(jù)n次WBGB曲線可精確降階的條件，以及文獻(xiàn)[7]中給出的升階公式，就可以得到 n-1次的WBGB曲線的控制頂點(diǎn)與n次WBGB曲線的控制頂點(diǎn)的關(guān)系。

定理2. 若定義1中的n次WBGB曲線可精確降階為 n-1次，即滿足式(5)，設(shè)其n-1次 WBGB曲線所對應(yīng)的控制頂點(diǎn)為，即

(1) 當(dāng)n=2m+1，

(2) 當(dāng)n=2m，

2.2 擾動法

對式(1)中的控制頂點(diǎn)添加適當(dāng)?shù)臄_動εi, i=0,1,…,n，若添加擾動后的控制頂點(diǎn)，i=0,1,…, n滿足式(5)，即可精確降階為形如式(3)中的n-1次多項(xiàng)式 q( t, n-1,L)，則該多項(xiàng)式可作為式(1)的降一階逼近，由定理 2可得如下的關(guān)系式：

(1) 當(dāng) n= 2 m+1，

(2) 當(dāng) n= 2m，

討論n次WBGB曲線的降階問題即為討論如何取得適當(dāng)?shù)臄_動 εi，使得擾動后的n-1次WBGB曲線與原曲線的誤差最小，也即轉(zhuǎn)化為求解優(yōu)化問題1

由Lagrange乘數(shù)法可得：

(1) 當(dāng) n=2 m+1時(shí)，

代入式(6)得

(2) 當(dāng) n= 2m時(shí)，

代入式(7)得

擾動法直觀簡易，從上述結(jié)論可以看出，其僅對中間幾個(gè)控制點(diǎn)作修正，即可達(dá)到降階逼近的目的，且當(dāng) n≥ 3時(shí)，擾動法的降階多項(xiàng)式是保端點(diǎn)的。

2.3 最佳一致逼近法

一般將其稱為 Chebyshev 多項(xiàng)式或Chebyshev基函數(shù)。

引理1[15]. 若定義在區(qū)間[0,1]上的n次多項(xiàng)式p( t)都可表示為

則n-1次多項(xiàng)式

為p(t)的最佳一致逼近。

引理2[15]. n次Bernstein基函數(shù)與Chebyshev基函數(shù)之間的轉(zhuǎn)化關(guān)系為

文獻(xiàn)[11]給出了n次 WBGB基函數(shù)的Bernstein基表示，文獻(xiàn)[16]中給出了WBGB基函數(shù)的對偶泛函，并由此推導(dǎo)出Bernstein基函數(shù)到WBGB基函數(shù)的轉(zhuǎn)化公式。

引理3[16]. n次Bernstein基函數(shù)可由WBGB基函數(shù)表示為：

(1) 當(dāng)n=2 m+1時(shí)，

其中，①0≤j≤m-L,

②m-L+1≤j≤ m,

(2) 當(dāng)n=2m時(shí)，

其中，①0≤j≤m-L,

②當(dāng)m-L+1≤j≤m時(shí)，

當(dāng)m-L+1≤j≤ m-1時(shí)，

有了以上基轉(zhuǎn)換公式，就可以實(shí)現(xiàn)一條WBGB曲線由Bézier曲線的形式繪出，反之亦然。

為方便起見，將 n-1次WBGB曲線式(3)升階為n次曲線，即

定理 3. 若式(13)中 n-1次多項(xiàng)式 q( t, n-1,L)為式(1)中n次多項(xiàng)式 p( t, n, L)的最佳一致逼近，則

其中

證明. 當(dāng) n=2 m+1時(shí)，由引理1可得

結(jié)合引理2、3，將 Tn(2 t- 1)用WBGB基函數(shù)表示，上式即變?yōu)?/p>

定理 3即為最佳一致逼近法。其較擾動法復(fù)雜，但從后文誤差分析可看出其逼近效果較擾動法有很大提高，然而卻不插值端點(diǎn)，下面導(dǎo)出插值端點(diǎn)的約束最佳一致逼近降階方法。

3 誤差分析

為刻畫降階曲線對原曲線的逼近程度，定義逼近誤差與相對誤差分別為

其中

3.1 擾動法誤差

定理 4. 擾動法所得降階曲線 q( t, n - 1,L)與原曲線 p( t, n, L)的逼近誤差為

證明. 先討論 n=2 m+1的情形，由擾動法及式(8)，有

同理可得 n= 2m時(shí)結(jié)論成立。 證畢。

3.2 最佳一致逼近法誤差

定理 5. 最佳一致逼近法所得降階曲線q( t, n - 1,L)與原曲線 p( t, n, L)的逼近誤差為

4 數(shù)值實(shí)例

例1給定一條6次WBGB曲線 p( t, 6,1)，其控制頂點(diǎn)為{(210,110),(170,220),(190,360),(260,410), (355,425),(470,320),(430,110)}。

利用擾動法對其降一階后得到的5次WBGB曲線的控制頂點(diǎn)為{(210,110),(156.6667,256.6667), (185.8333,365.8333),(469.1667,572.5000),(483.3333, 390.0000),(430,110)}。圖 2為 6次 WBGB曲線p( t, 6,1)，當(dāng) L=1時(shí)的降階前后的圖形，其中原曲線和原控制多邊形用實(shí)線表示，降階后的曲線和控制多邊形用虛線表示，其降階誤差為6.562 5。

圖2 6次WBGB曲線的降階(擾動法)

利用最佳一致逼近法對其降一階后得到的 5 次WBGB曲線的控制頂點(diǎn)為{(208.8800,111.5683), (162.8375,248.0254),(183.9610,368.4563),(348.9610, 433.4563),(489.5041,381.3592),(428.8800,111.5683)}。

圖3為6次WBGB曲線 p( t, 6,1)，當(dāng) L= 1時(shí)的降階前后的圖形，其中原曲線和原控制多邊形用實(shí)線表示，降階后的曲線和控制多邊形用虛線表示，其降階誤差為0.1025。

圖3 6次WBGB曲線的降階(最佳一致逼近法)

例2給定一條7次WBGB曲線 p( t, 7,L)，其控制頂點(diǎn)為{(230,110),(170,230),(190,350),(260,400), (355,425),(470,320),(490,240),(430,100)}。

利用擾動法對其降一階后得到的6次WBGB曲線的控制頂點(diǎn)為{(230,110),(170,230),(190,350), (307.5,412.5),(470,320),(490,240),(430,100)}。圖4 為7次WBGB曲線 p( t, 7,L)，當(dāng) L=1和 L= 3時(shí)降階前后的圖形，其中原曲線和原控制多邊形用實(shí)線表示，降階后的曲線和控制多邊形用虛線表示，其誤差分別為29.687 5和11.875 0。

利用最佳一致逼近法對其降一階后得到的 6 次WBGB曲線的控制頂點(diǎn)，當(dāng) L= 1時(shí)為{(224.2512,98.4878),(196.6600,237.0128),(145.8949, 338.3984),(294.8198,409.1592),(514.1051,331.6016), (463.3400,232.9872),(435.7488,101.5122)}；當(dāng) L=3時(shí)降階后的控制頂點(diǎn)為{(219.3535,91.2007), (204.4126,239.0481),(145.8759,338.3984),(294.8348, 409.1592),(514.1241,331.6016),(455.5874,230.9519), (440.6465,102.7993)}。圖 5為 7次 WBGB曲線p( t,7, L)，當(dāng) L=1和 L= 3時(shí)降階前后的圖形，其中原曲線和原控制多邊形用實(shí)線表示，降階后的曲線和控制多邊形用虛線表示，其誤差分別為0.231 9和0.092 8。

圖4 7次WBGB曲線的降階(擾動法)

圖5 7次WBGB曲線的降階(最佳一致逼近法)

實(shí)際上，p ( t, 7,3)即為Wang-Ball曲線，文獻(xiàn)[12]利用曲線升階和降階的關(guān)系給出了 Wang-Ball曲線的一種降階方法。通過計(jì)算發(fā)現(xiàn)，與本文擾動法降階后得到的曲線是一致的，但是誤差不如最佳一致逼近法的小，這說明本文的方法還是有效的。

從以上數(shù)據(jù)及圖形還可以看出來，擾動法和最佳一致逼近法，當(dāng)n固定時(shí)，L的值越大，降階效果越好。

5 結(jié) 論

本文分別利用擾動法和最佳一致逼近法給出了WBGB曲線的降階算法。實(shí)驗(yàn)結(jié)果表明，從逼近效果而言，用最佳一致逼近法效果比擾動法要好，若利用擾動法得到的降階曲線不能達(dá)到預(yù)期的誤差，則可以先利用細(xì)分算法對曲線做細(xì)分，再逐段用擾動法降階；利用擾動法對 n( n ≥ 3)次的WBGB曲線降階所得曲線插值端點(diǎn)，而最佳一致逼近法降階所得曲線不插值端點(diǎn)；擾動法計(jì)算耗時(shí)要比最佳一致逼近法少。值得一提的是，本文是在 WBGB曲線的位置參數(shù)1≤L≤m(此時(shí)WBGB曲線包含 Wang-Ball曲線以及介于 Bézier曲線和 Wang-Ball曲線之間的一些中間曲線)的前提下進(jìn)行的，因?yàn)槲恢脜?shù) L=0時(shí)(此時(shí) WBGB曲線即為Bézier曲線)，精確降階條件并不成立，因此本文的降階方法對Bézier曲線并不成立。

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

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

[3] Ball A A. CONSURF, Part 3: How the program is used [J]. Computer-Aided Design, 1977, 9(1): 9-12.

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

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

[6] 王成偉. 三次 Ball曲線的擴(kuò)展[J]. 工程圖學(xué)學(xué)報(bào), 2008, 29(1): 77-81.

[7] 王成偉. 四次 Wang-Ball曲線的擴(kuò)展[J]. 工程圖學(xué)學(xué)報(bào), 2009, 30(1): 80-84.

[8] 嚴(yán)蘭蘭, 梁炯豐, 饒智勇. 三次 Ball曲線的兩種新擴(kuò)展[J]. 工程圖學(xué)學(xué)報(bào), 2011, 32(5): 20-24.

[9] 嚴(yán)蘭蘭, 張 文, 溫榮生. 兩類形狀可調(diào)五次廣義Ball曲線[J]. 工程圖學(xué)學(xué)報(bào), 2011, 32(6): 16-20.

[10] Wu H Y. 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.

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

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

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

[14] 劉 剛, 王國瑾. Said-Bézier型廣義Ball曲線顯示降多階[J]. 軟件學(xué)報(bào), 2010, 21(6): 1473-1479.

[15] Brunnett G, Schreiber T, Braun J. The geometry of optimal degree reduction of Bézier curves [J]. Computer Aided Geometric Design, 1996, 13(8): 773-788.

[16] Zhang L, Wu H Y, Tan J Q. Dual bases for Wang-Bézier basis and their applications [J]. Applied Mathematics and Computation, 2009, 214(1): 218-227.

Degree Reduction of Wang-Bézier Generalized Ball Curves

Wang Yan1, Li Zhim ing2

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

The degree reduction of generalized Ball curves of Wang-Bézier type is discussed by perturbation and the best uniform approximation respectively. The approximation error is given. The experimental results demonstrate that the effect of the best uniform approximation is better than that of perturbation. If the error cannot be obtained in advance, the original curve can be subdivide firstly, and then reduce the degree by using of perturbation part by part. The degree reduction method of WBGB curves enriches the theory system of generalized Ball curves effectively.

WBGB curves; perturbation method; best uniform approximation

TP 391.72

A

2095-302X(2016)04-0476-07

2015-11-26；定稿日期：2016-01-20

國家自然科學(xué)基金項(xiàng)目(60773043，61070227)；教育部科學(xué)技術(shù)研究重大項(xiàng)目(309017)；合肥師范學(xué)院人才科研啟動基金項(xiàng)目(2014rcjj05)

王 燕(1985–)，女，山東泰安人，講師，博士。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)。E-mail：wy030515@163.com