一種三次均勻B樣條曲線快速反算的方法＊

李道軍，鄔向偉

(1.鄭州職業(yè)技術(shù)學(xué)院，河南 鄭州 450121；2.中州大學(xué)，河南 鄭州 450044)

在計(jì)算機(jī)輔助幾何設(shè)計(jì)(CAGD)實(shí)踐中，常遇到設(shè)計(jì)者事先并不知道控制多邊形頂點(diǎn)的位置，而只知道曲線上的某些型值點(diǎn)的情況。從設(shè)計(jì)角度上來說，通常考慮的是曲線的大致形狀，而非控制多邊形的大致形狀。為了構(gòu)造B-spline曲線，就需要由已知的型值點(diǎn)反算出控制多邊形的頂點(diǎn)。在實(shí)際工程應(yīng)用中，B-spline曲線的反算過程所涉及到的計(jì)算量很大，因此討論B-spline曲線的快速反算算法有著很重要的意義[1]。

對于三次均勻B-spline曲線的反算，朱心雄[2]給出了一種計(jì)算速度快且易于編程的反算控制頂點(diǎn)的迭代方法，可以得到在允許誤差范圍內(nèi)的C2連續(xù)曲線。而參考文獻(xiàn)[3]通過A-1的研究對三對角矩陣提出了一種優(yōu)于追趕法和LU分解法的求解方法。但是它們都是以兩端曲率為零作為邊界條件，可能出現(xiàn)人們所不希望看到的曲線在端點(diǎn)處不連續(xù)的現(xiàn)象。針對B-spline曲線的反算過程計(jì)算量大，重構(gòu)曲線端點(diǎn)處曲率不連續(xù)的問題，本文提出了一個(gè)有效的解決辦法，并在Matlab[4]中予以編程實(shí)現(xiàn)，大大降低了程序的復(fù)雜性，提高了運(yùn)算效率，并使重構(gòu)所得曲線的兩個(gè)端點(diǎn)處曲率不為零，至少滿足了一階連續(xù)。

1 反求B-spline曲線

為了使一條k次B-spline曲線通過一組數(shù)據(jù)點(diǎn)qi(i=0，1，…，m)，反算曲線時(shí)，一般使曲線的首末端點(diǎn)分別與首末數(shù)據(jù)點(diǎn)一致，將內(nèi)數(shù)據(jù)點(diǎn)依次作為樣條曲線的分段連接點(diǎn)，則數(shù)據(jù)點(diǎn)qi將依次與B-spline曲線定義域內(nèi)的節(jié)點(diǎn)一一對應(yīng)，即數(shù)據(jù)點(diǎn)qi有節(jié)點(diǎn)值uk+i(i=0，1，…，m)。該B-spline插值曲線將由 n+1個(gè)控制頂點(diǎn) di(i=0，1，…，n)與節(jié)點(diǎn)矢量 U=[u0，u1，…，un+k+1]來定義。 其中，n=m+k-1，即控制頂點(diǎn)數(shù)目要比數(shù)據(jù)點(diǎn)數(shù)目多出k-1個(gè)，共有m+k個(gè)未知頂點(diǎn)。由端點(diǎn)插值要求，應(yīng)取k+1重節(jié)點(diǎn)端點(diǎn)的固支條件，又取規(guī)范定義域。于是u0=u1=…uk=0，un+1=un+2=…un+k+1=1。

以反算三次均勻B-spline曲線為例，曲線的定義域?yàn)閡∈[u3，un+1]，曲線的控制頂點(diǎn)應(yīng)有 n＝m+3個(gè)。 則 B-spline曲線方程可表示為：

式中總共有m+1個(gè)線性方程組，但有n+1個(gè)控制頂點(diǎn)未知量。因此，要想得到唯一解，需要另外補(bǔ)充兩個(gè)方程，這兩個(gè)方程一般由邊界條件給定。邊界的補(bǔ)充條件有多種形式，如給定兩端點(diǎn)的切向量、自由端點(diǎn)條件、虛節(jié)點(diǎn)條件和拋物線條件等，實(shí)際應(yīng)用中根據(jù)具體情況選取適合的邊界補(bǔ)充條件。有了補(bǔ)充方程，即可用迭代法或追趕法等求解所建立的線性方程組。

2 快速反算算法

將定義在每一個(gè)節(jié)點(diǎn)區(qū)間上用整體參數(shù)u表示的B-spline基變換成用局部參數(shù) t∈[0，1]表示，則三次均勻B-spline曲線段的矩陣表示為：

式中，[1 t t2t3]M3為三次均勻B-spline基的矩陣表示，M3為三次B-spline基函數(shù)系數(shù)矩陣，表示為：

補(bǔ)充邊界條件：由均勻B-spline曲線的局部性質(zhì)可知， 數(shù)據(jù)點(diǎn)的端點(diǎn) P1與 d0、d1、d2、d3有關(guān)，Pn與 dn+1、dn、dn-1、dn-2有關(guān)。邊界條件的補(bǔ)充除上述選用端點(diǎn)曲率為零外，還有兩種方法：(1)令d0、dn位于其相鄰的其他三個(gè)控制頂點(diǎn)所確定的拋物線上，這樣能保證兩個(gè)邊界點(diǎn)的曲率不為零，但缺點(diǎn)是邊界處卷曲過大；(2)令d0、dn位于其相鄰的其他三個(gè)控制頂點(diǎn)的反向延伸直線段上，但不足之處是兩個(gè)邊界點(diǎn)的曲率也為零。比較好的方法是令d0、dn分別等于與其相鄰的其他三個(gè)控制頂點(diǎn)所確定的拋物線及反向延伸直線的平均值，即：

由幾何可知，三次均勻B-spline曲線在節(jié)點(diǎn)處，數(shù)據(jù)點(diǎn)與控制頂點(diǎn)之間有下列關(guān)系：

那么在Matlab中求解式(8)線性方程組將非常簡單，本文用直接法進(jìn)行求解，只需輸入A和P，然后進(jìn)行矩陣左除，即D=AP，即可輸出方程組的解D=[d0d1…dn+1]T。需要說明的是，由于矩陣A中n一般很大，且元素多為非零元素，故儲存時(shí)易用稀疏矩陣形式。 上述算法部分Matlab程序如下：

%輸入數(shù)組 A，數(shù)據(jù)點(diǎn) qi，i=1，2，…n；qx、qz分別為其坐標(biāo)；

求出控制頂點(diǎn)后，再由式(3)即可求出參數(shù)定義域內(nèi)任意節(jié)點(diǎn)上的數(shù)據(jù)點(diǎn)值，從而也就求出了所需曲線。

利用上述算法對圖1所示經(jīng)過預(yù)處理后的數(shù)據(jù)點(diǎn)進(jìn)行運(yùn)算，圖2所示為反求的控制頂點(diǎn)，圖3為上述算法重構(gòu)的曲線。上述均勻三次B-spline曲線反求算法，可擴(kuò)展到均勻雙三次B-spline曲面控制網(wǎng)格頂點(diǎn)的反算。

[1]劉德平.逆向工程關(guān)鍵技術(shù)及其應(yīng)用研究[D].西安：西安電子科技大學(xué)，2008.

[2]朱心雄.自由曲線曲面造型技術(shù)[M].北京：科學(xué)出版社，1999.

[3]吳光亞，王小華.反求三次B樣條曲線控制頂點(diǎn)的一種快速算法[J].杭州電子科技大學(xué)學(xué)報(bào)，2005，25(3)：64-66.

[4]王學(xué)輝，張明輝.Matlab 6.1最新應(yīng)用詳解[M].北京：中國水利水電出版社，2002.