Bézier曲線的多項(xiàng)式重新參數(shù)化檢測(cè)

沈莞薔，王宏凱

Bézier曲線的多項(xiàng)式重新參數(shù)化檢測(cè)

沈莞薔，王宏凱

(江南大學(xué)理學(xué)院，江蘇 無(wú)錫 214122)

研究了一種用于精確檢測(cè)一條Bézier曲線的次數(shù)是否可以通過(guò)多項(xiàng)式重新參數(shù)化降低的算法。該算法對(duì)任意一條Bézier曲線，將重新參數(shù)化前后的基函數(shù)的關(guān)系用方程組的形式表達(dá)，但不需要解方程，而是通過(guò)系數(shù)表示的金字塔算法直接計(jì)算，可以精確求出用于重新參數(shù)化的多項(xiàng)式和降低次數(shù)后的Bézier曲線的控制頂點(diǎn)，并且該重新參數(shù)化的多項(xiàng)式在相差一個(gè)線性變換的前提下是唯一的。通過(guò)實(shí)例應(yīng)用，該算法運(yùn)算速度較之前的算法快。

Bézier曲線；多項(xiàng)式；重新參數(shù)化；基函數(shù)；金字塔算法

Bézier曲線憑借優(yōu)良的造型性質(zhì)，在幾何設(shè)計(jì)中有著重要應(yīng)用[1-2]。由于在參數(shù)曲線中，參數(shù)選擇的多樣性，有些參數(shù)化會(huì)使得一些Bézier曲線出現(xiàn)不適當(dāng)?shù)那闆r[3]，一旦使用了合適的參數(shù)化，Bézier曲線可以精確轉(zhuǎn)換為低次的Bézier曲線，相比高次Bézier曲線，低次Bézier曲線具有數(shù)據(jù)量少[4]、計(jì)算更快[5]、更好的系統(tǒng)兼容性[6-7]、對(duì)多邊形曲線的控制性更強(qiáng)[8-9]等優(yōu)點(diǎn)。

已有文獻(xiàn)在不改變曲線參數(shù)化的情況下，對(duì)Bézier曲線降次，如文獻(xiàn)[10]通過(guò)選取合適的函數(shù)，在不受拐角插值約束的條件下，實(shí)現(xiàn)了形狀參數(shù)可調(diào)的SG-Bézier曲線的降次；文獻(xiàn)[11]提出一種基于約束對(duì)偶Bernstein多項(xiàng)式，是計(jì)算降次Bézier曲線控制頂點(diǎn)的方法；文獻(xiàn)[12]用L2范數(shù)連續(xù)分段多項(xiàng)式曲線求解有理Bézier曲線逼近問(wèn)題；文獻(xiàn)[13]利用Bézier曲線本身的升次性質(zhì)，結(jié)合廣義逆矩陣的最小二乘理論，給出了一種新的降次逼近方法；文獻(xiàn)[14]利用3次PH曲線來(lái)逼近代數(shù)曲線；文獻(xiàn)[15]基于端點(diǎn)約束的Bézier曲線降次方法，為了保證曲線的平滑程度，在常規(guī)目標(biāo)函數(shù)的基礎(chǔ)上，提出了附加平滑項(xiàng)的Bézier曲線生成方法；文獻(xiàn)[16]闡述了以高階導(dǎo)消失為B樣條曲線自身退化的條件，利用約束優(yōu)化逼近原曲線。

事實(shí)上，一條多項(xiàng)式曲線有許多種參數(shù)形式，有些高次的曲線通過(guò)重新參數(shù)化可精確的以低次的形式表示，文獻(xiàn)[3]將原高次曲線的參數(shù)化稱為不適當(dāng)?shù)?。這種改變參數(shù)化降階的相關(guān)工作主要有：文獻(xiàn)[17]和文獻(xiàn)[3]使用類似求最大公約式的輾轉(zhuǎn)相除法，檢測(cè)多項(xiàng)式曲線參數(shù)化是否適當(dāng)；文獻(xiàn)[18]使用分段線性參數(shù)，對(duì)Bézier曲線進(jìn)行降次，取得了更好的逼近效果；文獻(xiàn)[19]給出了2條Bézier曲線完全重合的條件。

針對(duì)Bézier曲線參數(shù)化是不適當(dāng)[3]的情況，本文給出了一種算法，即檢測(cè)Bézier曲線的參數(shù)化是否是不適當(dāng)?shù)模绻?，將給出重新參數(shù)化后的Bézier曲線的控制頂點(diǎn)和相應(yīng)的重新參數(shù)化多項(xiàng)式；同時(shí)與文獻(xiàn)[3]的算法相比，并經(jīng)實(shí)例應(yīng)用對(duì)比表明，本文算法有更快的運(yùn)算速度。

1 理論分析

如果()是DRPR曲線，那么()的LD的Bézier曲線可記為

與文獻(xiàn)[3]相同，本文將Bernstein基轉(zhuǎn)化為冪基的形式?；D(zhuǎn)換有2個(gè)目的：①為了排除在Bernstein基下最高次項(xiàng)系數(shù)為0的自身退化的情況；②在冪基形式，利用高次基(包括低次基作為子集)以及同次基中函數(shù)的次數(shù)差異性，在后續(xù)構(gòu)造金字塔時(shí)，避免進(jìn)行反求方程。

檢驗(yàn)式(4)是否為DRPR，有

其中，=[01···]。由式(4)和式(6)，以及的線性無(wú)關(guān)性，得到

1.1 重新參數(shù)化多項(xiàng)式

重新參數(shù)化多項(xiàng)式()具有如下性質(zhì)。

性質(zhì) 1.如果()是曲線式(4)的重新參數(shù)化多項(xiàng)式，則()的任意線性變換，如()+(,?,且≠0)，也是式(4)的重新參數(shù)化多項(xiàng)式。

證明：由題意知

其中

證畢

證明將在1.3節(jié)給出。

1.2 基表示矩陣

其中，①是考慮多項(xiàng)式S()的次數(shù)得到的，=0,1,···,；②是顯然的；③是S≠0的結(jié)果；④可以由①通過(guò)數(shù)學(xué)歸納法證明得到。

性質(zhì) 4. 在曲線式(4)為DRPR的情況下，如果次重新參數(shù)化多項(xiàng)式()確定，那么矩陣是唯一的。

1.3 方程的解

根據(jù)性質(zhì)3的①，式(7)中的方程組為

在式(9)中，初始的行，每行有個(gè)方程，最后一行有1個(gè)方程，由該方程組可以依次解出,–1,···,1,0。

根據(jù)性質(zhì)1，不失一般性，令()中0=0，S=1。有a=0 (0≤<≤)，且a,ik=1 (0≤≤)，根據(jù)性質(zhì)3的②，若式(4)為DRPR，則有

滿足式(9)的第一行的第一個(gè)方程和最后一行的方程。

命題1. 如果式(4)為DRPR，那么向量–1,···,–k+1均為的倍數(shù)，其中為重新參數(shù)化多項(xiàng)式的次數(shù)。

該命題給出了一種求的方法，由于在初始的Bernstein基形式(1)中，單點(diǎn)和直線段的情況均很容易判斷，所以=的情況可以單獨(dú)考慮。另外，=1的情況不會(huì)降低式(4)的次數(shù)。所以，只考慮的非平凡約數(shù)。當(dāng)式(4)中的給定時(shí)，有如下性質(zhì)。

性質(zhì)5.如果式(4)是DRPR，那么任意可用于重新參數(shù)化的多項(xiàng)式的次數(shù)，均要滿足：

①是的一個(gè)非平凡約數(shù)；

②≤，其中是滿足–1,–2,···,–l+1都是的倍數(shù)這個(gè)條件的最大值。

此外，希望找到式(4)的MD曲線，即取最大值，在下一節(jié)的算法中，的取值從大到小列出。同時(shí)，如果不存在滿足條件的，則式(4)為非DRPR。

為了解出S,=1,2,···,–1，仍然考慮式(9)的第一行方程，對(duì)于的每一個(gè)候選值，–1,–2,···,–l+1均為的倍數(shù)，并且≠0，記向量中首個(gè)不為0的分量為，對(duì)應(yīng)的分量為，其中,,，根據(jù)式(9)的第一行方程可得

性質(zhì)3的②與④表明，通過(guò)金字塔算法可計(jì)算a，其算法路徑為

即

同樣的，當(dāng)=–2,–3,···,1，存在

其中，c,n–k+j為(S+1t+1+S+2t+2+···+St)展開(kāi)式中t–k+j前的系數(shù)。因此，c,n–k+j的值可以通過(guò)a用同樣的金字塔算法得出，所以有

其中

并且00=1，根據(jù)上述計(jì)算可看出：S,=–2,–3,···,1可通過(guò)S+1, S+2,···,S得到。所以性質(zhì)2的證明如下：

證明：若式(4)為DRPR，由于性質(zhì)1，如果0和S都是固定的，那么，S,=–2,–3,···,1均是唯一的，因此，性質(zhì)2成立。

證畢

計(jì)算其余，當(dāng)=–1,–2,···,1，根據(jù)式(9)的第一列方程，依次有

另外，得到后，式(9)的第+1–行中就沒(méi)有未知數(shù)了。然后檢查方程是否成立，排除非DRPR的情況。

目前曲線式(4)有2種情況：

(1) 非DRPR；

(2) DRPR，可求得式(4)的MD曲線的控制頂點(diǎn)矩陣，以及重新參數(shù)化多項(xiàng)式()。

最后，用一個(gè)簡(jiǎn)單方法控制重新參數(shù)化多項(xiàng)式()的值域，使得該值域?yàn)閇0,1]，記，分別為()在[0,1]的最大值和最小值，則

并且

其中，為式(8)中的矩陣，且=1/(–)，=–/(–)。

2 算 法

本文算法需首先考慮單點(diǎn)和直線段的特殊情況。

2.1 特殊情況

在Bernstein基形式(1)下直接考慮特殊情況。

并且

2.2 算法實(shí)現(xiàn)

算法：檢測(cè)Bézier曲線是否為DRPR。

(1) 若為單點(diǎn)，可根據(jù)輸入的控制頂點(diǎn)個(gè)數(shù)進(jìn)行判斷。

(2) 若是共線，可根據(jù)輸入的控制頂點(diǎn)個(gè)數(shù)進(jìn)行判斷。

步驟4. 對(duì)于的每一個(gè)候選值：

(2) 根據(jù)式(11)，依次得到a,j,=–1,–2,···,–+1的值。

(3) 根據(jù)式(12)，得到S–1的值，根據(jù)式(13)，依次計(jì)算得到S–2, S–3,···,1的值。

(4) 根據(jù)性質(zhì)3中的②和④，計(jì)算出其余的a,=1,2,···,–1,=,+1,···,，當(dāng)=時(shí)，=,+1,···, (–1)。

(5) 當(dāng)=–1,=–2, ···,1時(shí)，

①根據(jù)式(15)，計(jì)算。

(6) DRPR=T，根據(jù)式(3)得到()，跳出當(dāng)前循環(huán)。

3 實(shí) 例

實(shí)驗(yàn)環(huán)境見(jiàn)表1，每個(gè)實(shí)例中，用紅色空心圈表示輸入的Bézier曲線()的控制頂點(diǎn)，用藍(lán)色虛線表示對(duì)應(yīng)的控制多邊形，用藍(lán)色粗實(shí)線表示曲線()，用綠色方塊表示Bézier曲線()的控制頂點(diǎn)，用粉色虛線表示對(duì)應(yīng)的控制多邊形，用粉色細(xì)實(shí)線表示曲線()。

表1 實(shí)驗(yàn)環(huán)境

例1．輸入Bézier曲線的控制頂點(diǎn)

經(jīng)算法得DRPR=，重新參數(shù)化多項(xiàng)式

其中，MD的Bézier曲線的控制頂點(diǎn)為：，如圖1所示。

圖2 平面4次非DRPR曲線

例3. 輸入Bézier曲線的控制頂點(diǎn)：

經(jīng)算法得DRPR=。重新參數(shù)化多項(xiàng)式

其中，MD的Bézier曲線的控制頂點(diǎn)為：，如圖3所示。

例4. 輸入Bézier曲線的控制頂點(diǎn)：

經(jīng)算法得DRPR=T，重新參數(shù)化多項(xiàng)式為

曲線()在Bernstein基下控制頂點(diǎn)為：

圖4 平面6次DRPR曲線

Fig. 4 DRPR planar curve of degree 6

最后將本文算法與文獻(xiàn)[3]的算法進(jìn)行比較。文獻(xiàn)[3]的算法，輸入和輸出是冪基下的多項(xiàng)式曲線的頂點(diǎn)，所以本文對(duì)比的時(shí)間是從曲線轉(zhuǎn)換為冪基形式之后(即步驟2)開(kāi)始計(jì)時(shí)，到程序輸出重新參數(shù)化多項(xiàng)式()和冪基形式下頂點(diǎn)(即步驟5)結(jié)束計(jì)時(shí)。時(shí)間對(duì)比見(jiàn)表2。

表2 算法運(yùn)行時(shí)間對(duì)比(s)

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

本文給出的算法可以用來(lái)判斷任意一條Bézier曲線是否為DRPR，若是DRPR，可以精確求出該曲線的MD的Bézier曲線的控制頂點(diǎn)，以及相應(yīng)的重新參數(shù)化多項(xiàng)式。

本文的算法用于精確判斷曲線是否為DRPR的情況，但是，大部分的Bézier曲線均是非DRPR的。在后續(xù)的工作中，將研究給定Bézier曲線的近似DRPR逼近算法，即通過(guò)控制頂點(diǎn)微小擾動(dòng)，使得非DRPR曲線變?yōu)镈RPR曲線。

[1] 王國(guó)瑾, 汪國(guó)昭, 鄭建民. 計(jì)算機(jī)輔助幾何設(shè)計(jì)[M]. 北京: 高等教育出版社, 2001: 249-250. WANG G J, WANG G Z, ZHENG J M. Computer aided geometric design[M]. Beijing: Higher Education Press, 2001: 249-250 (in Chinese).

[2] 郭大勇, 成佳頤. 基于二項(xiàng)式系數(shù)設(shè)計(jì)矩陣的Bézier 曲線擴(kuò)展[J]. 圖學(xué)學(xué)報(bào), 2014, 35(4): 511-517.GUO D Y, CHENG J Y. Extension of Bézier curve based on the design of matrix using binomial coefficient[J]. Journal of Graphics, 2014, 35(4): 511-517 (in Chinese).

[3] SEDERBERG T W. Degenerate parametric curves[J]. Computer Aided Geometric Design, 1984, 1(4): 301-307.

[4] 胡倩倩, 王國(guó)瑾. 球域Bézier曲面的精確邊界及其多項(xiàng)式逼近[J]. 浙江大學(xué)學(xué)報(bào): 工學(xué)版, 2008, 42(11): 1906-1909. HU Q Q, WANG G J. Exact boundary of ball Bézier surface and its approximation by polynomial form[J]. Journal of Zhejiang University: Engineering, 2008, 42(11): 1906-1909 (in Chinese).

[5] QIAO Z F, HU M, TAN Z H, et al. An accurate and fast method for computing offsets of high degree rational Bézier/NURBS curves with user-definable tolerance[J]. Journal of Computer Languages, 2019, 52: 1-9.

[6] RABABAH A, IBRAHIM S. Gometric degree reduction of Bézier curves[C]//International Conference on Mathematics and Computing. Heidelberg: Springer, 2018: 87-95.

[7] 胡倩倩. 曲線曲面的兩類幾何逼近與兩類代數(shù)表示[D]. 杭州: 浙江大學(xué), 2008. HU Q Q, Two kinds of geometric approximations and algebraic representations of curves and surfaces[D]. Hangzhou: Zhejiang University, 2008 (in Chinese).

[8] CHEN Y, CAI Y Y, ZHENG J M, et al. Accurate and efficient approximation of clothoids using Bézier curves for path planning[J]. IEEE Transactions on Robotics, 2017, 33(5): 1242-1247.

[9] HAN X L, GUO X. Optimal parameter values for approximating conic sections by the quartic Bézier curves[J]. Journal of Computational and Applied Mathematics, 2017, 322: 86-95.

[10] HU G, QIAO Y, QIN X Q, et al. Approximate multi-degree reduction of SG-Bézier curves using the grey wolf optimizer algorithm[J]. Symmetry, 2019, 11(10): 1242-1260.

[11] GOSPODARCZYK P, LEWANOWICZ S, WO?NY P. Degree reduction of composite Bézier curves[J]. Applied Mathematics and Computation, 2017, 293: 40-48.

[12] ESLAHCHI M R, KAVOOSI M. The use of Jacobiwavelets for constrained approximation of rational Bézier curves[J]. Computational and Applied Mathematics, 2018, 37(3): 3951-3966.

[13] 陳國(guó)棟, 王國(guó)瑾. 基于廣義逆矩陣的Bézier曲線降階逼近[J]. 軟件學(xué)報(bào), 2001, 12(3): 435-439. CHEN G D, WANG G J. Degree reduction approximation of Bézier curves by generalized inverse matrices[J]. Journal of Software, 2001, 12(3): 435-439 (in Chinese).

[14] 壽華好, 江瑜, 繆永偉. 基于三次PH曲線誤差可控代數(shù)曲線等距線逼近算法[J]. 圖學(xué)學(xué)報(bào), 2012, 33(2): 30-33. SHOU H H, JIANG Y, MIAO Y W. Error controllable algebraic curve offset approximation based on cubic PH curve[J]. Journal of Graphics, 2012, 33(2): 30-33 (in Chinese).

[15] HAN X L, YANG J. Multi-degree reduction of Bézier curves with distance and energy optimization[J]. Journal of Applied Mathematics and Physics, 2016, 4(1): 8-15.

[16] YONG J H, HU S M, SUN J G, et al. Degree reduction of B-spline curves[J]. Computer Aided Geometric Design, 2001, 18(2): 117-127.

[17] SEDERBERG T W. Improperly parametrized rational curves[J]. Computer Aided Geometric Design, 1986, 3(1): 67-75.

[18] CHEN X D, MA W Y, PAUL J C. Multi-degree reduction of Bézier curves using reparameterization[J]. Computer-Aided Design, 2011, 43(2): 161-169.

[19] CHEN X D, YANG C, MA W Y. Coincidence condition of two Bézier curves of an arbitrary degree[J]. Computers & Graphics, 2016, 54: 121-126.

Polynomial reparameterization detection of Bézier curves

SHEN Wan-qiang, WANG Hong-kai

(School of Science, Jiangnan University, Wuxi Jiangsu 214122, China)

An algorithm is presented to determine whether the degree of Bézier curve can be reduced by polynomial reparameterization. In the algorithm, for any Bézier curve, the relation between the basis functions before and after reparameterization is expressed as a system of equations. Instead of solving the equations,the polynomial for reparameterization and the control points of the lower degree Bézier curve can be calculated directly by apyramid algorithm of coefficient reparameterization.In addition,the polynomial for reparameterization is unique to within a scale factor and a constant. Compared with the previous algorithm by examples, this algorithm possesses shorter computational time.

Bézier curve; polynomial; reparameterization; basis function; pyramid algorithm

TP 391.72

10.11996/JG.j.2095-302X.2020040576

A

2095-302X(2020)04-0576-07

2020-01-19；

2020-03-29

29 March，2020

19 January，2020；

國(guó)家自然科學(xué)基金項(xiàng)目(61772013)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金項(xiàng)目(JUSRP21816)

National Natural Science Foundation of China (61772013); Fundamental Research Funds for the Central Universities (JUSRP21816)

沈莞薔(1981-)，女，江蘇無(wú)錫人，副教授，博士，碩士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)、計(jì)算機(jī)圖形學(xué)等。E-mail：wq_shen@163.com

SHEN Wan-qiang (1981-), femal, associate professor, Ph.D. Her main research interest covers computer aided geometric design, computer graphics, etc. E-mail：wq_shen@163.com