劉建貞，李亞娟

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

0 引 言

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

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

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

(1)

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

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

(2)

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

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

(3)

(4)

(5)

再由

(6)

R′(t)的分子中的第1個(gè)乘積項(xiàng)表示為：

(7)

同樣，由

(8)

(9)

得到R′(t)的分子中的第2個(gè)乘積項(xiàng)表達(dá)式：

(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個(gè)函數(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)分解為簡(jiǎn)單函數(shù)的乘積，結(jié)果如表1所示。

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

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

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

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

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

由式(2)計(jì)算可得：

(13)

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

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

分解時(shí)須按照簡(jiǎn)單函數(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。

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

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

把表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曲線(xiàn)的h階導(dǎo)矢界計(jì)算方法

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

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

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

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

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

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

(14)

首先，把函數(shù)w4(t)和R?(t)的分子中的每一個(gè)乘積項(xiàng)分解成簡(jiǎn)單函數(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。

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

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

把表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é)束語(yǔ)

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