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

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

(1.河北師范大學數學科學學院，河北 石家莊 050024；2.河北省計算數學與應用重點實驗室，河北 石家莊 050024)

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

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

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

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

1 預備知識

1.1 q-整數的相關概念

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

定義1.對于給定的實數q＞0，及任意r∈N，定義q-整數為

定義2.對于給定的實數q＞0，及任意r∈N，定義q-階乘為

定義3.對于給定的實數q＞0，及任意整數n≥r≥0，定義q-二項式系數為

其滿足Pascal 遞推關系式，即

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

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

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

稱之為n次Lupa?q-Bernstein 基函數。

文獻[13]通過基函數的遞推公式，得到Lupa?q-Bézier 曲線的de Casteljau 算法，即

算法1.1

文獻[16]利用Pascal 關系式重新構造Lupa?q-Bézier 曲線的de Casteljau 算法，得到了該曲線上某一點的顯式遞歸求值的de Casteljau 算法，即

算法1.2

以上2 種de Casteljau 算法都不具有經典de Casteljau 算法相切的性質，即倒數第二層2 個節點的仿射組合與曲線不相切。在第2 節中本文利用經典有理Bézier 曲線的de Casteljau 算法，構造了具有相切性質的Lupa?q-Bézier 曲線的de Casteljau 算法。此算法具有顯式的矩陣表示，并給出了此算法的2個應用。

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

2 具有相切性質的Lupa? q-Bézier 曲線de Casteljau 算法及其應用

2.1 具有相切性質的de Cateljau 算法

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

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

利用經典有理Bézier 曲線的de Casteljau 算法[24]以及第r層與第0 層間權因子wi的關系可得：

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

形式1.

形式2.

注1.形式1 為相鄰兩層控制頂點之間的關系，形式2 反映了各層控制頂點與初始控制頂點的關系。可直接計算中間節點，用于曲線細分。

每一層的每個節點都可以表示成一條有理Bézier 曲線。由此可得到每一層節點關于初始多邊形的顯式矩陣

2.2 具有顯式矩陣表示的de Casteljau 算法的實現與計算復雜度

算法1.2 與本文提出的算法2.1 均具有顯式的矩陣表示，接下來，將比較這2 種算法的計算復雜度。

2.3 Lupa? q-Bézier 曲線導矢的新形式

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

通過2 個節點之間連線的斜率來代替曲線的斜率，從而得到Lupa?q-Bézier 曲線導矢的一種新形式。

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

證明：通過倒數第二層2 個節點連線的斜率來代替曲線的斜率。

利用算法2.1 的形式2 可得

容易寫出2 點確定的直線斜率，即為所求曲線的斜率。

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

由算法2.1 可得

此形式的導矢將曲線的斜率轉換為2 個節點間直線的斜率，推導過程簡單，幾何意義明顯，計算量少。

2.4 曲線分割

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

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

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

證明：當n=2 時，給定形狀參數q，設控制頂點為P0，P1，P2，2 次Lupa?q-Bézier 曲線的表達式為

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

因為P(u1;q1)和P(u2;q2)分別對應曲線P(t;q)在[0,t0]和[t0,1]上的2 條子線段

在[0,t0]區間有

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

根據算法2.1 的形式二可得中間點為

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

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

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

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

(1) 每一層每一個節點都是一條低次的加權Lupa?q-Bézier 曲線；

(2) 每一層節點都有顯式矩陣表示。

下面給出每層節點關于初始多邊形的顯式矩陣表示

4 結束語

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