Lupa q-Bézier曲線的離散卷積生成與求值算法*

耿夢圓,解 濱,韓力文,3,4

(1.河北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，河北 石家莊 050024；2.河北師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，河北 石家莊 050024；3.河北省計(jì)算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050024；4.河北省數(shù)學(xué)與交叉科學(xué)國際聯(lián)合研究中心，河北 石家莊 050024)

1 引言

在計(jì)算機(jī)輔助幾何設(shè)計(jì)CAGD(Computer Aided Geometric Design)中,Bernstein基函數(shù)因其優(yōu)良性質(zhì)使得Bézier曲線曲面成為描述自由曲線曲面的重要工具[1-3]。 近年來,q-微積分理論[4]引發(fā)眾多研究人員的研究興趣并在超幾何分析、量子力學(xué)等領(lǐng)域廣為應(yīng)用。 其迅猛發(fā)展促使基于q-整數(shù)的廣義Bernstein算子陸續(xù)被提出,其中研究較為廣泛的主要為Lupaq-Bernstein算子和Phillipsq-Bernstein算子。 1987年,Lupa[5]首次提出有理形式的q-模擬Bernstein算子,研究其逼近和保形性質(zhì),后被稱之為Lupaq-Bernstein算子。 Ostrovska[6]和Wang等[7]探究了算子的一致收斂性及收斂速度等問題。 1996年P(guān)hillips[8]引入基于q-整數(shù)的多項(xiàng)式形式的q-Bernstein算子,可由q-差分簡單表示,為便于區(qū)分,本文稱之為Phillipsq-Bernstein算子。 隨后Oru?等[9]構(gòu)造出Phillipsq-Bézier曲線,引起研究人員的關(guān)注與研究。 在此帶動(dòng)與影響下,帶有形狀參數(shù)的廣義Bézier曲線曲面在曲線曲面造型上發(fā)揮了重要作用。

2014年,Han等[10]依據(jù)Lupaq-Bernstein算子構(gòu)造出基于q-整數(shù)的Lupaq-Bézier曲線曲面,得到了曲線的幾何不變性、升階等性質(zhì)及de Casteljau算法等。 相比于Phillipsq-Bézier曲線,Lupaq-Bézier曲線的函數(shù)類型、形狀參數(shù)q的取值范圍及端點(diǎn)相切的性質(zhì)均不同:(1) Phillipsq-Bézier曲線為多項(xiàng)式形式且參數(shù)q∈(0,1],而Lupaq-Bézier曲線為有理函數(shù)形式且q∈(0,+∞)，取值范圍更廣;(2) Phillipsq-Bézier曲線僅與首控制邊相切,而Lupaq-Bézier曲線與首末控制邊均相切。

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

2.1 Lupa q-Bézier曲線的相關(guān)定義

特別地,q-二項(xiàng)式系數(shù)滿足Pscal-type關(guān)系式,如式(1)和式(2)所示:

(1)

(2)

(3)

為n次Lupaq-Bézier曲線,其中:

(4)

為n次Lupaq-Bernstein基函數(shù)。 當(dāng)q=1時(shí),Lupaq-Bézier曲線退化為經(jīng)典Bézier曲線。

2.2 離散卷積的相關(guān)定義

(5)

離散卷積滿足交換律及結(jié)合律，如式(6)和式(7)所示:

A(t)?B(t)=B(t)?A(t)

(6)

A(t)?(B(t)?C(t))=(A(t)?B(t))?C(t)

(7)

定義6[20]離散卷積的微分法則，如式(8)所示：

(A(t)?B(t))′=

A′(t)?B(t)+A(t)?B′(t)

(8)

3 離散卷積生成Lupa q-Bézier曲線

3.1 Lupa q-Bernstein基函數(shù)的離散卷積形式

根據(jù)q-二項(xiàng)式系數(shù)滿足的Pascal-type關(guān)系式(1)，給出Lupaq-Bernstein基函數(shù)的遞推關(guān)系。

引理1[10]n次Lupaq-Bernstein基函數(shù)是2個(gè)n-1次Lupaq-Bernstein基函數(shù)的仿射組合,如式(9)所示:

(9)

利用此遞推關(guān)系式,從零次基函數(shù)開始，依次向高一次的基函數(shù)遞推,得到Lupaq-Bernstein基函數(shù)的向下遞推三角形,如圖1所示。 從上至下第i層的中間節(jié)點(diǎn)恰好是第i次的Lupaq- Bernstein基函數(shù)。

Figure 1 Downward recurrence of Lupa q-Bernstein basis functions圖1 Lupa q-Bernstein基函數(shù)的向下遞推

n次Lupaq-Bernstein基函數(shù)出現(xiàn)在第n層向下遞推三角形的底部。 同時(shí),基函數(shù)是由頂端到底部第i個(gè)位置的所有路徑乘積之和,例如，對(duì)于4次Lupaq-Bernstein基函數(shù)式(10)成立:

(10)

結(jié)合定義5,此過程等同于函數(shù)序列離散卷積的計(jì)算過程,由此構(gòu)造出Lupaq-Bernstein基函數(shù)的離散卷積形式。

定理1設(shè)函數(shù)序列如式(11)所示：

k=1,2,…n

(11)

則Ak(t;q)可離散卷積生成n次Lupaq- Bernstein基函數(shù)序列,如式(12)所示:

A1(t;q)?…?Ak(t;q)?…?An(t;q)

(12)

注1當(dāng)q=1時(shí),式(12)退化為經(jīng)典Bernstein基函數(shù)的離散卷積形式[20]。

注2文獻(xiàn)[15]主要圍繞Lupaq-Bernstein基函數(shù)的離散概率模型給出離散卷積形式。本文則是從基函數(shù)的向下遞推結(jié)合路徑角度得到該形式,同時(shí)在下文中將進(jìn)一步發(fā)揮離散卷積表示與向下遞推三角形的作用,探究Lupaq-Bézier曲線的特點(diǎn)與優(yōu)良性質(zhì)。

Figure 2 Basis functions constructed by convolutionof function sequences in reverse order圖2 函數(shù)序列逆序卷積構(gòu)造的基函數(shù)

3.2 Lupa q-Bézier曲線的de Casteljau算法

Figure 3 A de Casteljau algorithm for Lupa q-Bézier curve圖3 Lupa q-Bézier曲線的一種de Casteljau算法

定理2對(duì)于任一條n次Lupaq-Bézier曲線,基于離散卷積可生成n!種de Casteljau算法。

(13)

如圖4所示,當(dāng)以圖2定義的離散卷積順序構(gòu)造時(shí),de Casteljau算法具有顯式矩陣表示[12],記為de Casteljau算法2，如式(14)所示:

(14)

Figure 4 de Casteljau algorithm with explicit matrix representation圖4 具有顯式矩陣表示的de Casteljau算法

注3定理2所提出的n!種de Casteljau算法在計(jì)算Lupaq-Bézier曲線上任意點(diǎn)的效率上是一致的,針對(duì)不同的使用需求可選擇不同的算法。

例1對(duì)于一條形狀參數(shù)q=4的3次Lupaq-Bézier曲線,可生成3!種de Casteljau算法,如圖5所示,‘o’點(diǎn)為不同算法求得的曲線上的同一點(diǎn)。

與經(jīng)典Bézier曲線de Casteljau算法求得切點(diǎn)[21]不同,Lupaq-Bézier曲線de Casteljau算法倒數(shù)第2層2節(jié)點(diǎn)構(gòu)成的直線段與曲線相交于2個(gè)點(diǎn),本文將這2個(gè)交點(diǎn)統(tǒng)稱為割點(diǎn)。 如圖5所示,不同的de Casteljau算法得到的割點(diǎn)不同,有時(shí)為左割點(diǎn),有時(shí)為右割點(diǎn)。 第5節(jié)將給出2種de Casteljau算法，分別求得左/右割點(diǎn)的判定條件。

Figure 5 3! de Casteljau algorithms for cubic Lupa q-Bézier curve圖5 3次Lupa q-Bézier曲線的3!種de Casteljau算法

4 速端曲線

定理3設(shè)n次Lupaq-Bézier曲線的一階速端曲線表達(dá)式如式(15)所示:

(15)

Aj-1(t;q)?Bj(t;q)?Aj+1(t;q)?…?An(t;q)

(16)

(17)

(18)

當(dāng)q=1時(shí),該速端曲線是以原曲線控制頂點(diǎn)的向前差分ΔP0和ΔP1為首末控制頂點(diǎn)的一次Bézier曲線;當(dāng)q∈(0,1)∪(1,+∞)時(shí),二次Lupaq-Bézier曲線的速端曲線是以P′(0;q),P′(1;q)為首末端點(diǎn)的直線段。

除此之外,通過定理3進(jìn)一步整理可得到首末2個(gè)n次Lupasq-Bernstein基函數(shù)的導(dǎo)函數(shù)的顯式表達(dá)式。

(19)

(20)

根據(jù)離散卷積的微分法則可在基函數(shù)一階導(dǎo)序列式(16)的基礎(chǔ)上繼續(xù)微分,得到基函數(shù)的高階導(dǎo)數(shù),進(jìn)而計(jì)算Lupaq-Bézier曲線的高階導(dǎo)矢。

定理4Lupaq-Bernstein基函數(shù)的二階導(dǎo)函數(shù)序列的離散卷積結(jié)構(gòu)如式(21)所示:

(21)

(22)

(23)

5 de Casteljau算法左/右割點(diǎn)分類

圖3與圖4為曲線具有的2種de Casteljau算法。 圖6a和圖6b分別展示了不同形狀參數(shù)q下的二次Lupaq-Bézier曲線,其中q=1所表示的曲線為經(jīng)典Bézier曲線。 由圖6可知,Lupaq-Bézier曲線始終位于控制多邊形與經(jīng)典Bézier曲線之間,并且通過選取不同的形狀參數(shù)q值,可以任意調(diào)整曲線形狀,增加曲線造型的靈活性[10]。

Figure 6 Quadratic Lupa q-Bézier curves with different shape parameters圖6 不同形狀參數(shù)的二次Lupa q-Bézier曲線

Figure 7 Comparison of de Casteljau algorithmsbetween Lupa q-Bézier curve and classical Bézier curve圖7 Lupa q-Bézier曲線與經(jīng)典Bézier曲線de Casteljau算法對(duì)比

下面分別給出de Casteljau算法1和算法2得到左割點(diǎn)或右割點(diǎn)時(shí)的充分必要條件。

定理5任意給定參數(shù)t∈(0,1),de Casteljau算法1求得左割點(diǎn)當(dāng)且僅當(dāng)形狀參數(shù)q>1;求得右割點(diǎn)當(dāng)且僅當(dāng)0

證明對(duì)比Lupaq-Bézier曲線de Casteljau算法1與經(jīng)典Bézier曲線de Casteljau算法,為便于區(qū)分,記二次經(jīng)典Bézier曲線de Casteljau算法節(jié)點(diǎn)為和

(24)

(25)

定理6任意給定參數(shù)t∈(0,1),de Casteljau算法2求得左割點(diǎn)當(dāng)且僅當(dāng)形狀參數(shù)01。

(26)

(27)

注4Lupaq-Bézier曲線具有端點(diǎn)插值性,即當(dāng)參數(shù)t=0時(shí),de Casteljau算法1或算法2求得參數(shù)對(duì)應(yīng)曲線上一點(diǎn)為P0;t=1時(shí),算法1或算法2求得曲線上一點(diǎn)為P2。

圖8a和圖8b展示了de Casteljau算法1分別在q>1時(shí)取不同參數(shù)t得到的左割點(diǎn)和0

Figure 8 Left/right cut points gotten by de Casteljau algorithm 1 圖8 de Casteljau算法1得到的左/右割點(diǎn)

Figure 9 Left/right cut points gotten by de Casteljau algorithm 2 圖9 de Casteljau算法2得到的左/右割點(diǎn)

上述定理5和定理6分別給出了de Casteljau算法1和算法2得到左割點(diǎn)或右割點(diǎn)時(shí)形狀參數(shù) 的取值范圍。

算法3雙割點(diǎn)算法

輸入:控制頂點(diǎn)P0,P1,P2,參數(shù)t,q。

輸出:左/右割點(diǎn)CL,CR。

步驟3計(jì)算另一割點(diǎn)

步驟4根據(jù)形狀參數(shù)的取值范圍判斷,倘若q≥1,則CL=C1,CR=C2;若0

定理7給定二次Lupaq-Bézier曲線P(t;q),其中q∈(0,+∞),t∈(0,1),應(yīng)用雙割點(diǎn)算法3時(shí),節(jié)點(diǎn)與左/右割點(diǎn)CL,CR構(gòu)成的交比固定。

證明當(dāng)q>1時(shí),利用雙割點(diǎn)算法3中的步驟2與步驟3得到2個(gè)割點(diǎn)且CL=C1,CR=C2,則式(28)和式(29)滿足:

(28)

0

(29)

證畢。

6 結(jié)束語

本文通過引入向下遞推三角形和離散卷積函數(shù)序列,提出n次Lupaq-Bernstein基函數(shù)的離散卷積結(jié)構(gòu),并將向下遞推三角形反轉(zhuǎn)箭頭方向自下而上卷積生成Lupaq-Bézier曲線。 借助離散卷積的交換性,進(jìn)而得到n!種新的de Casteljau算法。 文中列舉出了其中的2種算法及其優(yōu)勢,對(duì)于其他算法的特征有待進(jìn)一步探究。

根據(jù)對(duì)2種de Casteljau算法及其形狀參數(shù)q的討論,二次Lupaq-Bézier曲線可選擇性得到左/右割點(diǎn)。 另外給出同時(shí)計(jì)算2個(gè)割點(diǎn)的算法,并證明雙割點(diǎn)算法具有交比不變性。

本文僅得到2個(gè)n次基函數(shù)導(dǎo)數(shù)的顯式表達(dá)式。 對(duì)于其他基函數(shù)導(dǎo)數(shù)的具體形式還有待探究。 對(duì)于3次或更高次Lupaq-Bézier曲線的割點(diǎn)討論及其應(yīng)用需要進(jìn)一步研究。