C－Bézier曲線顯式降階算法

周聯(lián)

(上海海事大學(xué) 文理學(xué)院，上海 201306)

0 引言

近年來(lái)，C曲線曲面方法［1－3］作為一種新的曲線曲面造型理論，引起廣大幾何設(shè)計(jì)工作者的密切關(guān)注，其主要優(yōu)點(diǎn)［4］在于它兼?zhèn)溆欣鞡ézier曲線或有理B樣條曲線能統(tǒng)一表示圓錐曲線和自由曲線的長(zhǎng)處，且能擺脫有理曲線曲面在微分運(yùn)算和積分運(yùn)算上較為繁瑣的困境.因而，有關(guān)C曲線曲面的幾何性質(zhì)、幾何計(jì)算、幾何逼近的研究［5－9］，在一定程度上成為國(guó)內(nèi)外計(jì)算機(jī)輔助幾何設(shè)計(jì)學(xué)術(shù)界的研究熱點(diǎn).

目前，在C曲線曲面的理論探索與實(shí)用技術(shù)開發(fā)上，一個(gè)值得注意的動(dòng)向是大部分研究偏重于其幾何性質(zhì)和幾何表示方面，但在幾何計(jì)算和幾何逼近方面相對(duì)滯后.事實(shí)上，幾何計(jì)算和幾何逼近方法對(duì)工程應(yīng)用顯得更為重要、現(xiàn)實(shí).例如，在Bézier曲線的幾何逼近方面，國(guó)際上眾多學(xué)者已經(jīng)對(duì)降階課題作了多年的深入研究［10－21］，并且將 Bézier曲線降階方法推廣到曲面［22－24］，但C曲線降階的研究論文卻寥若晨星.趙林玉［8］應(yīng)用廣義逆矩陣?yán)碚摵蛿_動(dòng)約束法分別給出兩種降階逼近算法:前者考慮端點(diǎn)高階插值的一次降多階情形，但其逼近誤差比較大;后者由于C－Bézier曲線退化條件的復(fù)雜，事實(shí)上只給出將4次曲線降為3次的特殊算法.此外，趙林玉［8］把曲線的廣義逆矩陣方法推廣到C－Bézier曲面的約束降階.林新輝［9］討論 C－Bézier曲線在 L2范數(shù)下的保持端點(diǎn)C1，C2，G1，G2約束降1階逼近，但沒(méi)有考慮到一次降多階情形.由此可見，研究并開發(fā)優(yōu)質(zhì)高效的C曲線降階算法是當(dāng)務(wù)之急.所謂優(yōu)質(zhì)，是指算法必須滿足一次性降多階、保端點(diǎn)高階連續(xù)、精度最高、顯式表示;所謂高效，是指算法必須穩(wěn)定且速度最快.

基于文獻(xiàn)［9］的基轉(zhuǎn)換矩陣，本文利用分而治之的思想，首先把端點(diǎn)高階插值的C曲線最佳降多階這一復(fù)雜問(wèn)題分解為兩個(gè)簡(jiǎn)單問(wèn)題——僅有端點(diǎn)高階插值但無(wú)須降階，以及無(wú)須端點(diǎn)插值的最佳降多階;其次，利用 C－Bézier基函數(shù)在空間 Γn=span{1，t，…，tn－2，sint，cos t}下的顯式表示，結(jié)合最小二乘法，給出C－Bézier曲線保端點(diǎn)高階插值的顯式最佳降多階算法.

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

1.1 基函數(shù)的定義

設(shè)定初始函數(shù):

式中:t∈［0，α］.在空間 Γn=span{1，t，…，tn－2，sin t，cos t}上采用遞歸的方法構(gòu)造 n次 C－Bézier基函數(shù){u0，n(t)u1，n(t)… un，n(t)}，定義［3］

引理1 n次C－Bézier基函數(shù)在基{1 t …tn－2sin t cos t}下的顯式［9］表示為

式中:Un(t)=(u0，n(t)，u1，n(t)，…，un，n(t));Tn(t)=(ti，n)1×(n+1)=(1，t，…，tn－2，sin t，cos t);Βn=(b0，n，b1，n，…，bn，n).

當(dāng)0≤k≤n－2時(shí)，

當(dāng)k=n－1，n時(shí)，

根據(jù)引理1，易知:

若記

則

最后，令 Gn，m=(gi，j)(n+1)×(m+1).

Gn，n為實(shí)對(duì)稱正定矩陣，所以它可逆.Gn，m只與降階前后的階數(shù)有關(guān)系，所以可以先把它們逐一計(jì)算出來(lái)，存入數(shù)據(jù)庫(kù)中，以備隨時(shí)調(diào)用.這可保障C－Bézier曲線降階的高效率計(jì)算.通過(guò)下面6個(gè)積分公式，可以迭代求得矩陣Gn，m中的系數(shù).

1.2 端點(diǎn)插值

給定控制頂點(diǎn)pi，可以確定一條C－Bézier曲線

根據(jù)前述基函數(shù)定義，易知式(1)曲線的導(dǎo)矢曲線就是一條n－1次C－Bézier曲線，即

根據(jù)上面的導(dǎo)矢曲線形式，可以推出引理2.引理2 式(1)所示曲線P(t)在兩端點(diǎn)上的(k，l)階導(dǎo)矢分別為

2 C－Bézier曲線顯式約束降多階

首先把式(1)所示的曲線改記為Pn(t).目標(biāo)是找一條同樣的帶參數(shù)α但次數(shù)低達(dá)m(m＜n)的C－Bézier曲線

使得它與原曲線Pn(t)在兩端點(diǎn)處保持(k，l)階連續(xù)(k，l≥0;k+l≤m)，并且它們之間的最小二乘距離最小，即

2.1 確定約束控制頂點(diǎn)

在工程應(yīng)用中，兩條拼接曲線在端點(diǎn)處往往需要保持高階連續(xù).為此，根據(jù)引理1導(dǎo)出降階前后兩條曲線的端點(diǎn)約束條件.

引理3 曲線Pn(t)和Qm(t)在兩端點(diǎn)處分別保持(k，l)階連續(xù)，則有

(1)對(duì)于t=0，

(2)對(duì)于t=α，

并且有

借助引理3，可求出降階曲線Qm(t)的兩端約束控制頂點(diǎn) q0，q1，…，qk和 qm－l，…，qm.

2.2 確定無(wú)約束控制頂點(diǎn)

為得到Qm(t)的其余控制頂點(diǎn)(無(wú)約束控制部分)，下面將其全部控制頂點(diǎn)和相應(yīng)的基函數(shù)全體分別分成兩部分.先設(shè)指標(biāo)集

那么，可以寫出

則問(wèn)題(3)可以表述為

上式可寫成矩陣形式

其中

由于矩陣Gff為實(shí)對(duì)稱正定，所以它可逆.因而欲求的降階曲線的未約束控制頂點(diǎn)為

2.3 實(shí)例和比較

例1 采用文獻(xiàn)［8］中例1的數(shù)據(jù).已知原曲線的控制頂點(diǎn)為

取α=π/4求保端點(diǎn)插值且降3階的逼近曲線.采用本文方法所求得的降階曲線控制頂點(diǎn)為其中，逼近誤差為0.044 6.而采用文獻(xiàn)［8］的方法所得到的逼近誤差為0.089 7.

文獻(xiàn)［9］只能每次降1階，效率不高.圖1給出原曲線(實(shí)線)和最佳降3階逼近曲線(虛線).

圖1 原曲線和最佳降3階逼近曲線

例2 采用文獻(xiàn)［9］中例4數(shù)據(jù).已知原曲線的控制頂點(diǎn)為

取α=π/3求保端點(diǎn)插值且降2階的逼近曲線.采用本文方法所求得的降階曲線控制頂點(diǎn)為q0(0，0)，q1(1.507 0，－ 4.681 2)，q2(4.443 6，8.523 7)，q3(4.895 8，－9.099 4)，q4(6.664 4，5.276 3)，q5(8，0)，逼近誤差為0.100 5.而采用文獻(xiàn)［8］的方法所得到的逼近誤差為0.206 8.圖2給出原曲線(實(shí)線)和最佳降2階逼近曲線(虛線).

圖2 原曲線和最佳降2階逼近曲線

3 結(jié)束語(yǔ)

根據(jù) C－Bézier基的顯式表示，給出 C－Bézier曲線曲面的約束顯式最佳降階算法.

該算法有以下優(yōu)點(diǎn):(1)降階曲線顯式表示;(2)一次降多階;(3)逼近誤差最佳;(4)降階曲線滿足端點(diǎn)高階插值.

該算法的不足之處是降階逼近誤差不能在曲線降階之前先驗(yàn)性地求出，但由于降階曲線的控制頂點(diǎn)是顯式表示的，上述不足并不影響本算法的計(jì)算效率.

［1］ZHANG J W.C－Curves:an extension of cubic curves［J］.Comput Aided Geometric Des，1996，13(3):199－217.

［2］ZHANG J W.Two different forms of C－B－splines［J］.Comput Aided Geometric Des，1997，14(1):31－41.

［3］CHEN Q Y，WANG G Z.A class of Bézier－like curves［J］.Comput Aided Geometric Des，2003，20(1):29－39.

［4］FARIN G.Algorithms for rational Bézier curves［J］.Comput Aided Des，1983，15(2):73－77.

［5］MAINAR E，PENA J M.A basis of C－Bézier splines with optimal properties［J］.Comput Aided Geometric Des，2002，19(4):291－295.

［6］樊建華，鄔義杰，林興.C－Bézier曲線分割算法及G1并接條件［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14(5):421－424.

［7］YANG Q，WANG G Z.Inflection points and singularities on C－curves［J］.Comput Aided Geometric Des，2004，21(2):207－213.

［8］趙林玉.高階C－Bézier曲線曲面性質(zhì)研究及其應(yīng)用［D］.南京:南京航空航天大學(xué)，2005.

［9］林新輝.C－Bézier曲線降階逼近［D］.杭州:浙江大學(xué)，2005.

［10］WATKINS M，WORSEY A.Degree reduction for Bézier curves［J］.Comput Aided Des，1988，20(3):398－405.

［11］ECK M.Degree reduction of Bézier curves［J］.Comput Aided Geometric Des，1993，10(3):237－252.

［12］CHEN Guodong，WANG Guojin.Optimal multi－degree reduction of Bézier curves with constraints of endpoints continuity［J］.Comput Aided Geometric Des，2002，19(6):365－377.

［13］ZHANG Renjiang，WANG Guojin.Constrained Bézier curves’best multi－degree reduction in the L2－norm［J］.Progress in Nat Sci，2005，15(9):843－850.

［14］WOZ'NY P，LEWANOWICZ S.Constrained multi－degree reduction of triangular Bézier surfaces using dual Bernstein polynomials［J］.J Computational＆ Applied Math，2010，235(3):785－804.

［15］周聯(lián)，王國(guó)瑾.帶G1連續(xù)約束的Bézier曲線顯式最佳降多階［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22(4):735－740.

［16］RABABAH A，MANN S.Iterative process for G2－multi degree reduction of Bézier curves［J］.Applied Math ＆ Computation，2011，217(20):8126－8133.

［17］CHEN Xiaodiao，MA Weiyin，PAUL J C.Multi－degree reduction of Bézier curves using reparameterization［J］.Comput Aided Des，2011，43(2):161－169.

［18］康寶生，石茂，張景嶠.有理Bézier曲線的降階［J］.軟件學(xué)報(bào)，2004，15(10):1522－1527.

［19］覃廉，關(guān)履泰.有理曲線曲面的降階逼近［J］.中國(guó)圖像圖形學(xué)報(bào)，2006，11(8):62－69.

［20］江明，羅予頻，楊士元.基于微粒群算法的有理Bézier曲線降階［J］.計(jì)算機(jī)應(yīng)用，2007，27(6):1524－1526.

［21］劉彬.基于遺傳算法的NURBS曲線降階［J］.計(jì)算機(jī)工程，2008，34(14):194－196.

［22］郭清偉，朱功勤.張量積Bézier曲面降多階逼近的方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16(6):777－782.

［23］周登文，劉芳，居濤，等.張量積Bézier曲面降階逼近的新方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14(6):553－556.

［24］ZHOU Lian ，WANG Guojin.Constrained multi－degree reduction of Bézier surfaces using Jacobi polynomials［J］.Comput Aided Geometric Des，2009，26(3):259－270.