Lupa? q-Bézier曲線的幾何求值算法及其應(yīng)用

柳麗宏，左 華，韓力文,2

(1.河北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，河北 石家莊 050024；2.河北省計(jì)算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050024)

de Casteljau 算法[1]是1959 年由法國(guó)汽車工程師de Casteljau 為加速車身設(shè)計(jì)并使其具有計(jì)算能力而提出的。其是一種曲線曲面的幾何求值算法，可將一個(gè)復(fù)雜的幾何問(wèn)題化簡(jiǎn)為一系列的簡(jiǎn)單問(wèn)題，具有數(shù)值穩(wěn)定性，可用于曲線細(xì)分和開(kāi)花[2-3]。de Casteljau 算法已經(jīng)成為計(jì)算機(jī)輔助幾何設(shè)計(jì)(computer aided geometric design，CAGD)的基本工具，在汽車和船舶設(shè)計(jì)、飛機(jī)工業(yè)以及醫(yī)學(xué)領(lǐng)域均有應(yīng)用。經(jīng)典Bézier 曲線的de Casteljau 算法在遞歸求值的過(guò)程中每一層的每個(gè)點(diǎn)都是一條低次的Bézier 曲線，每一層節(jié)點(diǎn)都有顯式的矩陣表示，并且倒數(shù)第二層2 個(gè)節(jié)點(diǎn)的連線與曲線相切。

Bernstein 算子具有許多優(yōu)良的幾何性質(zhì)及應(yīng)用[4]，為CAGD 中的曲線曲面造型奠定了堅(jiān)實(shí)的理論基礎(chǔ)。隨著q-微積分的發(fā)展[5]，一類包含q-整數(shù)的廣義Bernstein 算子應(yīng)運(yùn)而生。目前研究較多的有2 類：①Phillipsq-Bernstein 算子；②Lupa?q-Bernstein 算子[6]，其中第一類算子廣泛應(yīng)用于逼近論和幾何造型中[7-11]。本文致力于推進(jìn)Lupa?q-Bernstein 算子的應(yīng)用。LUPAS[12]是研究廣義Bernstein 算子的先驅(qū)。1987年，他引入了Lupa?q-Bernstein 算子，其由有理函數(shù)而不是多項(xiàng)式表示，當(dāng)q=1 時(shí)，退化為經(jīng)典Bernstein算子。2014 年，HAN 等[13]基于Lupa?q-Bernstein 算子構(gòu)造了以q-整數(shù)作為形狀參數(shù)的Lupa?q-Bézier 曲線曲面，該曲線曲面具有與經(jīng)典Bézier 曲線曲面相似的幾何性質(zhì)和算法。如幾何不變性和仿射不變性、凸包性和升階性質(zhì)、de Casteljau 算法。2016 年，以此為基礎(chǔ)，HAN 等[14]通過(guò)增加權(quán)因子，構(gòu)造了加權(quán)Lupa?q-Bézier 曲線。本文構(gòu)造的曲線是基于廣義Bernstein 算子，在曲線曲面的形狀控制上具有優(yōu)勢(shì)。相比于經(jīng)典Bézier 曲線，Lupa?q-Bézier 曲線多了一個(gè)形狀參數(shù)q，可用于控制曲線，通過(guò)調(diào)節(jié)參數(shù)q的大小，可以使曲線靠近或遠(yuǎn)離控制多邊形，而且Lupa?q-Bézier 曲線可以比經(jīng)典Bézier 曲線更接近控制多邊形。相比于Phillipsq-Bézier 曲線，Lupa?q-Bézier 曲線在首末端點(diǎn)處與控制多邊形的首尾2 邊P1-P0和Pn-Pn-1相切，而Phillipsq-Bézier 曲線不具有此性質(zhì)。

近幾年，學(xué)者從de Casteljau 算法的不同角度進(jìn)行探究。WINKEL[15]利用啞積分位移算子構(gòu)造了基于啞積分的廣義Bézier 曲線的de Casteljau 算法；?íR和JüTTLER[16]將Lupa?q-Bézier 曲線推廣到一般有理空間，通過(guò)改變基本元素累乘的順序給出n！種de Casteljau 算法。張燕和韓力文[17]利用q-二項(xiàng)式系數(shù)的Pascal 遞推關(guān)系式重新構(gòu)造了Lupa?q-Bézier 曲線的de Casteljau 算法，每一層節(jié)點(diǎn)由關(guān)于初始控制多邊形的顯式矩陣表示。WO?NY 和CHUDY[18]提出了線性時(shí)間的Bézier 曲線的幾何求值算法，降低算法的計(jì)算復(fù)雜度。文獻(xiàn)[19-20]將曲線曲面的de Casteljau 算法與其他類型求值算法在算法精度與效率方面進(jìn)行比較。HERMES[21]利用無(wú)誤差變換的原理，提出了一系列補(bǔ)償算法，以精確地計(jì)算具有浮點(diǎn)系數(shù)的Bernstein形式的多項(xiàng)式。除此之外，近幾年，de Casteljau 算法思想也被用在了流形值的數(shù)據(jù)計(jì)算[22]。

經(jīng)典有理Bézier 曲線具有相切性質(zhì)，即倒數(shù)第二層2 個(gè)節(jié)點(diǎn)的仿射組合與曲線相切，可以用于分割曲線。本文將Lupa?q-Bézier 曲線表示成經(jīng)典有理Bézier 曲線的形式，再應(yīng)用經(jīng)典有理Bézier 曲線的de Casteljau 算法，構(gòu)造的算法具有相切的性質(zhì)，對(duì)于2 次Lupa?q-Bézier 曲線，證得分割后2 條子線段的形狀參數(shù)相乘等于原來(lái)曲線的形狀參數(shù)，進(jìn)一步給出Lupa?q-Bézier 曲線導(dǎo)矢的一種新形式，最后將具有顯式矩陣表示的、計(jì)算復(fù)雜度低的Lupa?q-Bézier 曲線的de Casteljau 算法推廣到加權(quán)Lupa?q-Bézier 曲線上，所得到的de Casteljau 算法具有一些新的特點(diǎn)：每一層每個(gè)節(jié)點(diǎn)都是一條低次的加權(quán)Lupa?q-Bézier 曲線。

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

1.1 q-整數(shù)的相關(guān)概念

為了介紹Lupa?q-Bézier 曲線，首先回顧一下q-整數(shù)的相關(guān)概念[23]。

定義1.對(duì)于給定的實(shí)數(shù)q＞0，及任意r∈N，定義q-整數(shù)為

定義2.對(duì)于給定的實(shí)數(shù)q＞0，及任意r∈N，定義q-階乘為

定義3.對(duì)于給定的實(shí)數(shù)q＞0，及任意整數(shù)n≥r≥0，定義q-二項(xiàng)式系數(shù)為

其滿足Pascal 遞推關(guān)系式，即

1.2 Lupa? q-Bézier 曲線的定義及算法

定義4.令實(shí)數(shù)q＞0，t∈[0,1]，給定n+1 個(gè)向量Pi∈R3(i=0,1,…,n)，則稱n次參數(shù)曲線段

為n次Lupa?q-Bézier 曲線，由相鄰2 個(gè)控制頂點(diǎn)Pi依次連接得到的n邊折線多邊形稱為控制多邊形。

稱之為n次Lupa?q-Bernstein 基函數(shù)。

文獻(xiàn)[13]通過(guò)基函數(shù)的遞推公式，得到Lupa?q-Bézier 曲線的de Casteljau 算法，即

算法1.1

文獻(xiàn)[16]利用Pascal 關(guān)系式重新構(gòu)造Lupa?q-Bézier 曲線的de Casteljau 算法，得到了該曲線上某一點(diǎn)的顯式遞歸求值的de Casteljau 算法，即

算法1.2

以上2 種de Casteljau 算法都不具有經(jīng)典de Casteljau 算法相切的性質(zhì)，即倒數(shù)第二層2 個(gè)節(jié)點(diǎn)的仿射組合與曲線不相切。在第2 節(jié)中本文利用經(jīng)典有理Bézier 曲線的de Casteljau 算法，構(gòu)造了具有相切性質(zhì)的Lupa?q-Bézier 曲線的de Casteljau 算法。此算法具有顯式的矩陣表示，并給出了此算法的2個(gè)應(yīng)用。

利用Pascal 關(guān)系式構(gòu)造的算法即算法1.2 與本文提出的算法2.1 均用顯式的矩陣表示，本文將這2 種算法在計(jì)算復(fù)雜度方面進(jìn)行比較，得到算法1.2計(jì)算復(fù)雜度小，本文在第3 節(jié)中將其推廣到加權(quán)Lupa?q-Bézier 曲線上。與之前用中心投影所得到算法相比，具有一些新的優(yōu)良特點(diǎn)。

2 具有相切性質(zhì)的Lupa? q-Bézier 曲線de Casteljau 算法及其應(yīng)用

2.1 具有相切性質(zhì)的de Cateljau 算法

對(duì)于n次Lupa?q-Bézier 曲線，可以將其表示成經(jīng)典有理Bézier 曲線的形式，再應(yīng)用經(jīng)典有理Bézier 的de Casteljau 算法，得到de Casteljau 算法的2 種表達(dá)形式，①相鄰兩層控制頂點(diǎn)的關(guān)系；②第r層與第0 層控制頂點(diǎn)的關(guān)系。進(jìn)一步，該de Casteljau 算法可以分割曲線，給出細(xì)分后的2 條子曲線段以及對(duì)于2 次曲線2 條子曲線段形狀參數(shù)滿足的性質(zhì)。并利用de Casteljau 算法給出Lupa?q-Bézier 曲線導(dǎo)矢的另一種表達(dá)形式。

將n次Lupa?q-Bézier 曲線

利用經(jīng)典有理Bézier 曲線的de Casteljau 算法[24]以及第r層與第0 層間權(quán)因子wi的關(guān)系可得：

算法2.1.具有相切性質(zhì)的Lupa?q-Bézier 曲線的de Casteljau 算法。

形式1.

形式2.

注1.形式1 為相鄰兩層控制頂點(diǎn)之間的關(guān)系，形式2 反映了各層控制頂點(diǎn)與初始控制頂點(diǎn)的關(guān)系?？芍苯佑?jì)算中間節(jié)點(diǎn)，用于曲線細(xì)分。

每一層的每個(gè)節(jié)點(diǎn)都可以表示成一條有理Bézier 曲線。由此可得到每一層節(jié)點(diǎn)關(guān)于初始多邊形的顯式矩陣

2.2 具有顯式矩陣表示的de Casteljau 算法的實(shí)現(xiàn)與計(jì)算復(fù)雜度

算法1.2 與本文提出的算法2.1 均具有顯式的矩陣表示，接下來(lái)，將比較這2 種算法的計(jì)算復(fù)雜度。

2.3 Lupa? q-Bézier 曲線導(dǎo)矢的新形式

文獻(xiàn)[25]給出了經(jīng)典有理Bézier 曲線的導(dǎo)矢，若將Lupa?q-Bézier 曲線表示成經(jīng)典有理Bézier 曲線的形式，易得n次Lupa?q-Bézier 曲線在t處的導(dǎo)矢為

通過(guò)2 個(gè)節(jié)點(diǎn)之間連線的斜率來(lái)代替曲線的斜率，從而得到Lupa?q-Bézier 曲線導(dǎo)矢的一種新形式。

定理1.Lupa?q-Bézier 曲線的一種新形式的導(dǎo)矢為

證明：通過(guò)倒數(shù)第二層2 個(gè)節(jié)點(diǎn)連線的斜率來(lái)代替曲線的斜率。

利用算法2.1 的形式2 可得

容易寫(xiě)出2 點(diǎn)確定的直線斜率，即為所求曲線的斜率。

例1：設(shè)3 次Lupa?q-Bézier 曲線的控制頂點(diǎn)為P0=(0,1)，P1=(2,2)，P2=(3,2)，P3=(4,1)，形狀參數(shù)為q=3。

由算法2.1 可得

此形式的導(dǎo)矢將曲線的斜率轉(zhuǎn)換為2 個(gè)節(jié)點(diǎn)間直線的斜率，推導(dǎo)過(guò)程簡(jiǎn)單，幾何意義明顯，計(jì)算量少。

2.4 曲線分割

de Casteljau 算法也給出了曲線的分割。給定形狀參數(shù)q，參數(shù)t∈[0,1]運(yùn)用算法2.1 可求出Lupa?q-Bézier 曲線上的一點(diǎn)P(t0;q)，該點(diǎn)將曲線分割成2條Lupa?q-Bézier 曲線，形狀參數(shù)分別為q1和q2，其對(duì)應(yīng)的頂點(diǎn)分別為 Lupa?q-Bézier 曲線 de Casteljau 算法所得三角陣列的2 條邊上的頂點(diǎn)：

定理2.一條形狀參數(shù)為q的Lupa?q-Bézier 曲線，在參數(shù)t0運(yùn)用有理Bézier 曲線de Casteljau 算法，分割得到2 條子曲線段：

推論1.特別地，對(duì)一條形狀參數(shù)為q的n=2次Lupa?q-Bézier 曲線分割得到的2 條n次子曲線段的形狀參數(shù)滿足q1×q2=q。

證明：當(dāng)n=2 時(shí)，給定形狀參數(shù)q，設(shè)控制頂點(diǎn)為P0，P1，P2，2 次Lupa?q-Bézier 曲線的表達(dá)式為

任取參數(shù)t0∈[0,1]，在t0處應(yīng)用de Casteljau 算法，該點(diǎn)把曲線P(t;q)分成2 條二次的子線段分別為

因?yàn)镻(u1;q1)和P(u2;q2)分別對(duì)應(yīng)曲線P(t;q)在[0,t0]和[t0,1]上的2 條子線段

在[0,t0]區(qū)間有

例2.設(shè)二次Lupa?q-Bézier 曲線的形狀參數(shù)q=3，控制頂點(diǎn)為P0=(1,0)，P1=(3,6)，P2=(5,2)。

根據(jù)算法2.1 的形式二可得中間點(diǎn)為

圖1 q=3 時(shí)，運(yùn)用de Casteljau 算法分割得到的 2 條子曲線 Fig.1 q=3,the de Casteljua algorithm is used to segment two sub-curve segments

3具有顯式矩陣表示的加權(quán)Lupa? q-Bézier 曲線的de Castejau 算法

定義5.設(shè)實(shí)數(shù)q＞0 和一組正實(shí)數(shù)ω0,ω1,…,ωn給出n+1 個(gè)空間向量Pi∈R3(i=0,1,…,n)，那么[0,1]上的n次加權(quán)Lupa?q-Bézier 曲線定義為

此de Casteljau 算法所具有的新特性

(1) 每一層每一個(gè)節(jié)點(diǎn)都是一條低次的加權(quán)Lupa?q-Bézier 曲線；

(2) 每一層節(jié)點(diǎn)都有顯式矩陣表示。

下面給出每層節(jié)點(diǎn)關(guān)于初始多邊形的顯式矩陣表示

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

本文構(gòu)造了具有相切性質(zhì)的Lupa?q-Bézier 曲線的de Casteljau 算法，當(dāng)q=1 時(shí)，Lupa?q-Bézier曲線的de Casteljau 算法退化為經(jīng)典Bézier 曲線的de Casteljau 算法。此算法具有顯式的矩陣表示，并得到了此算法的2 個(gè)應(yīng)用：①用來(lái)分割曲線;對(duì)于二次的情況，分割得到的2 條子曲線段的形狀參數(shù)相乘還是原來(lái)曲線的形狀參數(shù)；②是得到Lupa?q-Bézier 曲線導(dǎo)矢的一種新表示，因本文算法計(jì)算量小，并且具有顯式的矩陣表示，故將其推廣到加權(quán)Lupa?q-Bézier 曲線上。后續(xù)將探究對(duì)于高次曲線分割得到的2 條子曲線段的形狀參數(shù)滿足什么條件。Phillipsq-Bézier 曲線一直以來(lái)也是學(xué)者研究的比較深入、比較廣泛的曲線，Phillipsq-Bézier 曲線沒(méi)有具有相切性質(zhì)的de Casteljau 算法。進(jìn)一步構(gòu)造具有相切性質(zhì)的Phillipsq-Bézier 曲線的幾何求值算法。