有理Bézier曲線高階導(dǎo)矢界的計算

劉建貞，李亞娟

(杭州電子科技大學(xué)理學(xué)院,浙江 杭州 310018)

0 引 言

計算機輔助幾何設(shè)計與圖形學(xué)中，有理Bézier曲線等自由曲線曲面的導(dǎo)矢界計算問題一直都是非常重要的研究方向。許多學(xué)者對有理Bézier曲線、曲面的一階導(dǎo)矢界進行了研究。Floater[1]首先用控制頂點和權(quán)因子來表示有理Bézier曲線的一階導(dǎo)矢界；文獻[2]利用不等式給出了有理Bézier曲線的一階導(dǎo)矢界；文獻[3]估計了特殊點處的導(dǎo)矢界；文獻[4]給出一個較大的誤差界。Hermann[5]采用M?bius變換，討論了有理二次Bézier曲線的一階導(dǎo)矢界問題；文獻[6-12]利用不同的不等式對有理Bézier曲線的一階導(dǎo)矢界進行了估計，并不斷加以改進；文獻[13]對有理二次Bézier曲線的導(dǎo)矢界模長進行了優(yōu)化。除此之外，還有部分文獻估計了曲面導(dǎo)矢界。如文獻[14]將有理Bézier曲線的一階導(dǎo)矢界估值推廣到曲面，文獻[15]對NURBS曲面的偏導(dǎo)矢界進行了估計。但是，由于有理Bézier曲線的高階導(dǎo)矢計算公式異常復(fù)雜，其界的估計比較困難，相關(guān)文獻涉及較少。文獻[16]給出了有理Bézier曲線的二階，三階導(dǎo)矢界，文獻[17]提供了一種n次有理Bézier曲線任意階導(dǎo)矢界的上確界的理論計算方法，但沒有給出確定的界的表示。在文獻[2]方法基礎(chǔ)上，本文提出一種n次有理Bézier曲線高階導(dǎo)矢界計算方法。

1 計算導(dǎo)矢界的框架

一條n次有理Bézier曲線R(t)定義如下：

(1)

1.1 有理Bézier曲線的一階導(dǎo)矢界

一條n次有理Bézier曲線(1)的一階導(dǎo)矢記為：

(2)

文獻[2]給出如下引理，并以此計算n次有理Bézier曲線的一階導(dǎo)矢界。

引理1[2]如果ai≥0,bi≥0,i=0,1,2,…,n，那么

(3)

(4)

(5)

再由

(6)

R′(t)的分子中的第1個乘積項表示為：

(7)

同樣，由

(8)

(9)

得到R′(t)的分子中的第2個乘積項表達式：

(10)

(11)

結(jié)合式(6)，R′(t)的分母表示為：

(12)

把式(7)，式(10)和式(12)代入式(2)，由引理1，再結(jié)合(1-t)wi+twi+1≥min{wi,wi+1}，得到導(dǎo)矢界公式(4)。導(dǎo)矢界公式(4)的核心是5個函數(shù)P′(t),w(t),w′(t),P(t)和w(t)，分別由式(5)，式(6)，式(8)，式(9)和式(11)表示。首先，把P′(t)w(t),w′(t)P(t)和w(t)w(t)分解為簡單函數(shù)的乘積，結(jié)果如表1所示。

表1 一階導(dǎo)矢的函數(shù)分解

然后，把4個簡單函數(shù)P′(t),w′(t),P(t),w(t)按照同一行函數(shù)采用相同系數(shù)表達式的方法歸類綜合，結(jié)果如表2所示。

表2 一階導(dǎo)矢的歸類綜合

最后，根據(jù)表1和表2的結(jié)果，計算有理Bézier曲線的一階導(dǎo)矢界。

1.2 有理Bézier曲線的2階導(dǎo)矢界

由式(2)計算可得：

(13)

和一階導(dǎo)矢界的計算方法一樣。首先，把w3(t)和R″(t)的分子中每一個乘積項分解成簡單函數(shù)的乘積，結(jié)果如表3所示。

表3 二階導(dǎo)矢的函數(shù)分解

分解時須按照簡單函數(shù)的導(dǎo)矢階數(shù)遞減排列。記

Δ(wiPi)=wi+1Pi+1-wiPi，Δwi=wi+1-wi，
Δ2(wiPi)=Δ(wi+1Pi+1-wiPi)=wi+2Pi+2-2wi+1Pi+1+wiPi，
Δ2wi=Δ(wi+1-wi)=wi+2-2wi+1+wi。

然后，把簡單函數(shù)按照同一行函數(shù)采用相同系數(shù)表達式的方法歸類綜合，結(jié)果如表4所示。

表4 二階導(dǎo)矢的歸類綜合

把表3與表4中的公式代入式(13)，得到：

這里，

αi,j,k(t)=(1-t)βi,j,k+tγi,j,k，
βi,j,k=n(n-1)wj[Δ2(wiPi)-Δ2(wiPj)]+2nΔwj[Δ(wiPk)-Δ(wi+1Pi+1)]，
γi,j,k=n(n-1)wj+1[Δ2(wiPi)-Δ2(wiPj+1)]+2n2Δwj[Δ(wi+1Pk)-Δ(wi+1Pi+1)]。

1.3 有理Bézier曲線的h階導(dǎo)矢界計算方法

根據(jù)1.1節(jié)和1.2節(jié)給出的有理Bézier曲線一階、二階導(dǎo)矢界的計算方法，本文歸納出有理Bézier曲線的h階導(dǎo)矢界(h=1,2,…)的計算方法。先對導(dǎo)矢公式中的各項函數(shù)進行分解，再對導(dǎo)矢公式的各項函數(shù)進行歸類綜合，其計算方法如下。

(2)把導(dǎo)矢R(h)(t)的分母w(h+1)(t)和組成分子的所有乘積項按照P(t)導(dǎo)矢階數(shù)從高到低的順序排列在第1張函數(shù)分解表中的第1行，每個乘積項占據(jù)一列，如表1和表3。

(3)從第1個乘積項元素開始，每個乘積項都拆成h+1個簡單函數(shù)的乘積，按照導(dǎo)矢階數(shù)從高到低的順序依次排列在該乘積項的同一列，每個簡單函數(shù)占據(jù)一行，共占據(jù)第2行到第h+2行。分解時，既要考慮導(dǎo)矢階數(shù)從高到低的排列順序，又要考慮彼此之間的聯(lián)系。比如不同乘積項分解的結(jié)果中，使得處在同一行的簡單函數(shù)盡可能相同。分解的次序不同，后面導(dǎo)矢界計算的結(jié)果也會不同。

(5)由第2張歸納綜合表和引理1，并考慮到每個乘積項展開式中相同的系數(shù)，即可給出R(h)(t)的界。

1.4 有理Bézier曲線的三階導(dǎo)矢界

使用1.3節(jié)給出的次有理Bézier曲線的高階導(dǎo)矢界的計算方法來計算有理Bézier曲線的三階導(dǎo)矢界。

(14)

首先，把函數(shù)w4(t)和R?(t)的分子中的每一個乘積項分解成簡單函數(shù)的乘積，結(jié)果如表5所示。

表5 三階導(dǎo)矢的函數(shù)分解

記Δ3(wiPi)=Δ[Δ2(wi+1Pi+1)-Δ2(wiPi)]=wi+3Pi+3-3wi+2Pi+2+3wi+1Pi+1-wiPi，

Δ3wi=Δ(Δ2wi+1-Δ2wi)=wi+3-3wi+2+3wi+1-wi。

然后，把簡單函數(shù)按同一行函數(shù)采用相同系數(shù)表達式的方法歸類綜合，結(jié)果如表6所示。

表6 三階導(dǎo)矢的歸類綜合

把表5與表6中公式代入式(14)，得到：

這里，

ξi,j,k,g(t)=(1-t)2λi,j,k,g+(1-t)μi,j,k,g+t2νi,j,k,g，

ηj,k(t)=[(1-t)wj+twj+1][(1-t)wk+twk+1]，

λi,j,k,g=n(n-1)(n-2)wjwk[Δ3(wiPi)-Δ3(wiPg)]+6n3ΔwjΔwk[Δ(wiPi)-Δ(wiPg)]-

3n2(n-1)wk[ΔwjΔ2(wiPi)+2ΔwjΔ2(wiPg)+Δ2wiΔ(wjPj)]，

μi,j,k,g=n(n-1)(n-2)(wjwk+1+wj+1wk)[Δ2(wiPi)-Δ3(wiPg)]-

3n2(n-1)Δ(wjPj)(wk+1Δ2wi+wkΔ2wi+1)+

3n2(n-1)Δwj[2Δ2(wjwk+1Pg)+2Δ2(wi+1wkPg)-wkΔ2(wi+1Pi+1)-wk+1Δ2(wiPi)]+

12n3ΔwjΔwk[Δ(wi+1Pi+1)-Δ(wi+1Pg)]，

νi,j,k,g=n(n-1)(n-2)wj+1wk+1[Δ3(wiPi)-Δ3(wiPg)]+

6n3ΔwjΔwk[Δ(wi+2Pi+2)-Δ(wi+2Pg)]+

3n2(n-1)wk+1[2ΔwjΔ2(wi+1Pg)+ΔwjΔ2(wi+1Pi+1)-Δ2wi+1Δ(wjPj)]

2 結(jié)束語

本文在不等式計算的基礎(chǔ)上，采用乘積分解之后再歸類綜合的方法，提出了一種n次有理Bézier曲線高階導(dǎo)矢界的框架計算法，并對文獻[2]中導(dǎo)矢界計算方法做了進一步推廣。但是，隨著導(dǎo)矢階數(shù)的增高，本文算法得出的高階導(dǎo)矢界表達式變得比較復(fù)雜，如何簡化導(dǎo)矢界的表達式是下一步研究的重點。