基于分塊矩陣求導(dǎo)的Bézier曲線降階方法

李建東，楊 艷

(呂梁學(xué)院 數(shù)學(xué)系，山西呂梁 033000)

基于分塊矩陣求導(dǎo)的Bézier曲線降階方法

李建東，楊 艷

(呂梁學(xué)院 數(shù)學(xué)系，山西呂梁 033000)

Bézier曲線的降階逼近有著實(shí)際應(yīng)用價(jià)值，但是逼近程度會(huì)受端點(diǎn)約束條件的影響。提出了基于分塊矩陣求導(dǎo)的降階逼近方法。該方法能產(chǎn)生降多階，且滿足端點(diǎn)約束條件的顯式表達(dá)式。最后將中點(diǎn)分割法與分塊矩陣求導(dǎo)的降階方法結(jié)合并應(yīng)用到數(shù)值實(shí)驗(yàn)中，驗(yàn)證了該算法的優(yōu)越性。

Bézier曲線;降階;分塊矩陣求導(dǎo);中點(diǎn)分割

Bézier曲線的降階有著重要的實(shí)際應(yīng)用價(jià)值。例如在CAD系統(tǒng)間進(jìn)行數(shù)據(jù)交換時(shí)，由于不同的CAD系統(tǒng)對(duì)多項(xiàng)式的次數(shù)限制不同，因此需要將多項(xiàng)式的次數(shù)調(diào)整相同，也就是對(duì)曲線的階進(jìn)行統(tǒng)一。而統(tǒng)一的方法一般有2種:升階和降階。雖然Bézier曲線有升階性質(zhì)，可以得到精確的結(jié)論，但是卻使系統(tǒng)變得復(fù)雜，導(dǎo)致可靠性降低。相反，降階方法不僅可以提高計(jì)算效率以及系統(tǒng)的穩(wěn)定性和可靠性，而且對(duì)于數(shù)據(jù)壓縮也有重要的作用。

對(duì)于Bézier曲線降階的研究，目前已有較成熟的技術(shù)。早在1972年Forrset給出Bézier曲線的定義后，就提出了Bézier曲線的降階算法。本文在對(duì)有關(guān)降階逼近主要方法深入分析的基礎(chǔ)上，針對(duì)Bézier曲線滿足端點(diǎn)任意階連續(xù)性的降多階逼近進(jìn)行了研究。

定義1［2］設(shè)pi∈Rd，d=2，3;i=0，1，2，…，n，Bn

i(t)為n次Bernstein基函數(shù)。若對(duì)n次Bézier曲線，

則稱這種降階為在該范數(shù)下帶(r，s)次端點(diǎn)插值條件的Bézier曲線降n－m階逼近。

1 基于分塊矩陣求導(dǎo)的Bézier曲線降階方法

本節(jié)討論的降階方法中，用式(5)定義距離。

1.3 基于中點(diǎn)分割的分段逼近

以上幾種情況中誤差均由式(7)計(jì)算得到。如果誤差結(jié)果比控制值大，可以將曲線分為兩段，直到誤差小于控制值。

依據(jù)Bézier曲線割角的產(chǎn)生辦法可得出:對(duì)曲線的分段降階逼近，實(shí)質(zhì)上是由分割成的兩段子曲線分別做次數(shù)相同的降階，再拼到一起的。此處要求分割點(diǎn)也達(dá)到要求的端點(diǎn)連續(xù)性。依據(jù)擾動(dòng)約束方法［5］的理論分析，降階的誤差與由原曲線本身所決定的控制因子‖Δnp0‖有關(guān)，同時(shí)論證了隨著分割的進(jìn)行，該因子會(huì)減小。由此保證了分割會(huì)使逼近誤差降低［9］。

算法如下:

步驟1 輸入誤差限e、最多分割次數(shù)k與原曲線的控制頂點(diǎn)。

步驟2 再用分塊矩陣求導(dǎo)的方法，按照式(11)計(jì)算出初步逼近曲線的控制頂點(diǎn)，并計(jì)算誤差。如果誤差大于e，且分段次數(shù)小于k，則執(zhí)行步驟3，否則執(zhí)行步驟4。

步驟3 由Bézier曲線的de Casteljau算法計(jì)算原曲線中點(diǎn)分割點(diǎn)，同時(shí)計(jì)算得到2條子曲線的控制頂點(diǎn)，對(duì)2組控制頂點(diǎn)分別執(zhí)行步驟2。

步驟4 輸出各子曲線的控制頂點(diǎn)，并繪制與原曲線的比較圖像。

2 數(shù)值實(shí)驗(yàn)

實(shí)例 以平面上16個(gè)點(diǎn)(0，0)，(1.5，－2)，(4.5，－1)，(9，0)，(4.5，1.5)，(2.5，3)，(0，5)，(－4，8.5)，(3，9.5)，(4.4，10.5)，(6，12)，(8，11)，(9，10)，(9.5，5)，(7，6)與(5，7)為控制頂點(diǎn)的15次Bézier曲線用分塊矩陣求導(dǎo)方法降到m階并且保端點(diǎn)(r，s)階連續(xù)。圖1和2中，虛線為原Bézier曲線，實(shí)線為降階后的曲線，d為誤差。圖2為中點(diǎn)分割后的曲線逼近(其中*號(hào)為分割點(diǎn))，圖像看起來(lái)重合。當(dāng)保端點(diǎn)(0，0)階連續(xù)時(shí)，中心分一次，誤差由0.016 3降為10－4級(jí);保端點(diǎn)(2，2)階連續(xù)時(shí)，中心分了2次，誤差由2.025 4降到10－5級(jí)，并且中間的2段誤差均達(dá)到10－8級(jí)。

圖1 分塊矩陣求導(dǎo)方法分別降了1階和9階不保端點(diǎn)插值的逼近曲線

圖2 中點(diǎn)分割后再用矩陣分塊求導(dǎo)的保端點(diǎn)不同連續(xù)階的逼近曲線

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

提出了基于分塊矩陣求導(dǎo)的方法，該方法的優(yōu)點(diǎn)在于將原曲線分為3部分，但沒(méi)有各自獨(dú)立，解決了端點(diǎn)約束與降多階的矛盾，并且可以得到顯式的表達(dá)式。同時(shí)結(jié)合了中心分割的分段逼近，使之能夠達(dá)到任意精度。

本文僅討論了事后誤差，沒(méi)有找到誤差上限，不能進(jìn)行事先誤差估計(jì)。如果有先驗(yàn)誤差，就可以避免盲目降階，從而可以先對(duì)原曲線進(jìn)行分割，再對(duì)子曲線求先驗(yàn)誤差，直到小于事先給定的控制值，再實(shí)行降階。

［1］ 王仁宏，李崇君，朱春鋼.計(jì)算幾何教程［M］.北京:科學(xué)出版社，2008.

［2］ 郭清偉，朱工勤.Bézier曲線降多階逼近的一種方法［J］.應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào)，2003，17(2):49－54.

［3］ 劉慶生.Bézier曲線可降階條件及其降階逼近［J］.同濟(jì)大學(xué)學(xué)報(bào)，2001，29(4):470－473.

［4］ Lu L Z，Wang G Z.Application of ChebyshevⅡ－Bernstein basis transformations to degree reduction of Bézier curves［J］.Journal of Computational and Applied Mathematics，2008，221(1):52－65.

［5］ Hu S，Sun J，Jin T，et al.Approximate Degree Reduction of Bézier Curves［J］.Tsinghua Science and Technology，1998，3(2): 997－1000.

［6］ 陳國(guó)棟，王國(guó)瑾.基于廣義逆矩陣的Bézier曲線降階逼近［J］.軟件學(xué)報(bào)，2001，12(3):435－439.

［7］ 滿家巨，胡事民，雍俊海，等.Bézier曲線的降階逼近［J］.清華大學(xué)學(xué)報(bào):自然科學(xué)版，2000，40(7):117－120.

［8］ 陸利正，胡倩倩，王國(guó)昭.Bézier曲線降階的迭代算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，21(12):1689－1693.

［9］ 曾輝.基于中心分割的Bézier曲線降階［D］.大連:大連理工大學(xué)，2008.

(責(zé)任編輯 何杰玲)

Method for Degree Reduction of Bézier Curve Based on Partitioned Matrix Derivation

LI Jian－dong，YANG Yan
(School of Mathematics，Lyuliang University，Lyuliang 033000，China)

The approximation of degree reduction to Bézier curve has its practical application value but is limited by constrained condition of endpoints.It comes up a new method for degree reduction approximation based on partitioned matrix derivation.This new method can produce explicit formulation with multi－degree reduction and satisfies constrained condition of endpoints.Finally combining mid－point segmentation with partitioned matrix’s derivation and putting them into numerical experiment show the advantages of this algorithm.

Bézier curve;degree reduction;partitioned matrix derivation;midpoint subdivision

O174

A

1674－8425(2014)07－0142－05

10.3969/j.issn.1674－8425(z).2014.07.028

2014－03－25

呂梁學(xué)院科研項(xiàng)目(JYYB201304)

李建東(1978—)，男，山西方山人，碩士，講師，主要從事微分方程及其應(yīng)用研究。

李建東，楊艷.基于分塊矩陣求導(dǎo)的Bézier曲線降階方法［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2014(7): 142－146.

format:LI Jian－dong，YANG Yan.Method for Degree Reduction of Bézier Curve Based on Partitioned Matrix Derivation［J］.Journal of Chongqing University of Technology:Natural Science，2014(7):142－146.