B樣條曲線全局插值優(yōu)化算法及其實(shí)現(xiàn)

B樣條曲線全局插值優(yōu)化算法及其實(shí)現(xiàn)

吳婷1,2，鄒海2

(1.安徽國(guó)防科技職業(yè)學(xué)院 網(wǎng)絡(luò)信息中心， 安徽 六安 237011；

2.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 安徽 合肥 230601)

[摘要]通過插值給定的數(shù)據(jù)點(diǎn)來創(chuàng)建B樣條曲線時(shí)，需要對(duì)曲線的初始形狀進(jìn)行多次修改。為使首次生成的曲線更接近設(shè)計(jì)者的意圖，從數(shù)據(jù)點(diǎn)參數(shù)化和確定節(jié)點(diǎn)矢量?jī)蓚€(gè)方面優(yōu)化了現(xiàn)有算法。提出了一種改進(jìn)的弦長(zhǎng)參數(shù)化方法來求取給定數(shù)據(jù)點(diǎn)的對(duì)應(yīng)參數(shù)值，改善了數(shù)據(jù)點(diǎn)急轉(zhuǎn)彎處的過渡情況；通過平均值法確定節(jié)點(diǎn)矢量，有效避免了系數(shù)矩陣中奇異方程組的產(chǎn)生。總體上實(shí)現(xiàn)了一種B樣條曲線全局插值的優(yōu)化算法，最后對(duì)兩組典型數(shù)據(jù)點(diǎn)的實(shí)驗(yàn)直觀地驗(yàn)證了該算法的可行性。

[關(guān)鍵詞]B樣條曲線；全局插值；優(yōu)化算法

[文章編號(hào)]1673-2944(2015)03-0071-04

[中圖分類號(hào)]O241.5

收稿日期：2014-11-13

基金項(xiàng)目：國(guó)家科技重大專項(xiàng)基金資助項(xiàng)目(2009ZX05039-004)

作者簡(jiǎn)介：吳婷(1983—)，女，安徽省金寨縣人，安徽國(guó)防科技職業(yè)學(xué)院實(shí)驗(yàn)師，安徽大學(xué)碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)；鄒海(1969—)，男，安徽省壽縣人，安徽大學(xué)副教授，碩士生導(dǎo)師，博士，主要研究方向?yàn)橹悄苡?jì)算、中間件技術(shù)。

B樣條在CAD領(lǐng)域受到人們的廣泛關(guān)注，非均勻有理B樣條由于諸多優(yōu)點(diǎn)而被確定為工業(yè)產(chǎn)品物理形狀的唯一數(shù)學(xué)方法[1-2]。在參數(shù)化設(shè)計(jì)B樣條時(shí)，由于通過控制頂點(diǎn)來直接生成曲線的方法很難得到滿意的形狀，設(shè)計(jì)者一般先通過給定一系列關(guān)鍵點(diǎn)來確定曲線的大致形狀，再由造型系統(tǒng)反算出控制頂點(diǎn)進(jìn)而插值這些關(guān)鍵點(diǎn)，生成初始的B樣條曲線[3-4]。由于曲線插值的結(jié)果存在不唯一性，初始曲線可能與設(shè)計(jì)者意圖之間存在較大的出入，通常需通過調(diào)整控制頂點(diǎn)或調(diào)節(jié)權(quán)重系數(shù)反復(fù)修改曲線形狀，才能最終獲得滿意的設(shè)計(jì)結(jié)果[5-6]。設(shè)計(jì)者的思想正是通過給定數(shù)據(jù)點(diǎn)的分布情況來表達(dá)的。因此，為了提高設(shè)計(jì)效率，應(yīng)該使初次生成的曲線盡可能合理地反映數(shù)據(jù)點(diǎn)分布。B樣條曲線插值最重要的任務(wù)就是確定節(jié)點(diǎn)矢量和各給定數(shù)據(jù)點(diǎn)對(duì)應(yīng)的參數(shù)值，合理的參數(shù)值和節(jié)點(diǎn)矢量有利于更快地獲得理想的設(shè)計(jì)效果，提高設(shè)計(jì)效率。

確定給定數(shù)據(jù)點(diǎn)所對(duì)應(yīng)參數(shù)值的方法不一，目前常用的有均勻參數(shù)化和弦長(zhǎng)參數(shù)化，而節(jié)點(diǎn)矢量則常用等距分布法[5]。當(dāng)數(shù)據(jù)點(diǎn)分布不均勻時(shí)，采用均勻參數(shù)化會(huì)出現(xiàn)打圈相交的現(xiàn)象，容易產(chǎn)生與原始設(shè)計(jì)意圖較大的偏差，不利于分析和控制曲線形狀。而對(duì)于弦長(zhǎng)參數(shù)化，則當(dāng)給定數(shù)據(jù)點(diǎn)急轉(zhuǎn)彎變化時(shí)會(huì)出現(xiàn)過大的曲率變化，亦難以獲得滿意的效果。采用等距分布確定節(jié)點(diǎn)矢量的方法容易產(chǎn)生奇異方程組，給系數(shù)矩陣的求解增加了難度。在對(duì)給定數(shù)據(jù)點(diǎn)進(jìn)行插值擬合的研究中，Gofuku等[7]提出了滿足多個(gè)數(shù)據(jù)點(diǎn)處切向量的算法，但這些算法主要用于數(shù)據(jù)點(diǎn)分布較均勻的場(chǎng)合，否則插值的效果不夠理想。為此，本文充分考慮相鄰兩個(gè)給定數(shù)據(jù)點(diǎn)之間的距離對(duì)曲線形狀的影響，擬采用改進(jìn)弦長(zhǎng)參數(shù)化方法，結(jié)合平均值法確定節(jié)點(diǎn)矢量，力圖使曲線走勢(shì)更準(zhǔn)確地反映出給定數(shù)據(jù)點(diǎn)分布情況。

1　 B樣條曲線的定義

一條p次B樣條曲線定義為[6]：

(1)

其中：a≤u≤b；Pi是曲線的控制頂點(diǎn)；Ni,p(u)是p次B樣條基函數(shù)；定義域?yàn)榉侵芷诠?jié)點(diǎn)矢量U，其數(shù)值在區(qū)間[ui,ui+p+1)上非零，并按照公式(2)和(3)求?。?/p>

(2)

(3)

圖1　B樣條曲線控制多邊形示意圖

節(jié)點(diǎn)矢量U中a和b的重復(fù)度都為p+1，除非特別聲明，通常取a=0，b=1。如圖1所示，依次連接控制頂點(diǎn)即為控制多邊形。

2　給定數(shù)據(jù)點(diǎn)的 B樣條曲線插值算法

(4)

其中：k=0,1,…,n；n+1個(gè)控制點(diǎn)Pi是待求的未知量。

2.1求取參數(shù)值

為使最終獲得的曲線能充分反映出給定型值點(diǎn)的分布情況，兼顧曲線的光滑性，此處采用改進(jìn)的弦長(zhǎng)參數(shù)化，即對(duì)弦長(zhǎng)進(jìn)行開3次方運(yùn)算，旨在適當(dāng)降低弦長(zhǎng)的直接影響，改善曲線在數(shù)據(jù)點(diǎn)處的過渡平滑性。

(5)

2.2　確定節(jié)點(diǎn)矢量

從理論上講，節(jié)點(diǎn)矢量可以等距分布，即u0=…=up=0，um-p=…=um=1，uj+p=1/(n-p+1)，j=1,2,…,n-p。但是如果將其與公式(5)聯(lián)合使用，方程組(4)可能變成奇異方程組。為避免這種情況出現(xiàn)，此處采用取平均值的方法，中間的節(jié)點(diǎn)矢量用公式(6)求出：

(6)

2.3反算控制頂點(diǎn)

(7)

3　算法應(yīng)用實(shí)例

為直觀地比較所提算法與均勻參數(shù)化和弦長(zhǎng)參數(shù)化方法的不同效果，以兩組較典型的數(shù)據(jù)點(diǎn)為例，分別用上述3種方法進(jìn)行2次和3次非有理B樣條插值，其結(jié)果如圖2所示。

第一組數(shù)據(jù)點(diǎn)為Q=[8，9；12，12；16，10；22，15；30，11；36，13；45，9]，所得對(duì)應(yīng)的參數(shù)為Uk=[0，0.11，0.28，0.50，0.65，0.88，1.0]，節(jié)點(diǎn)矢量為U=[0，0，0，0.19，0.39，0.57，0.76，1.0，1.0，1.0]，全局插值所得的2次B樣條曲線見圖2(a)。

第二組數(shù)據(jù)點(diǎn)為Q=[-2，-4；10，0；6，20；21，40；36，20；32，0；44，-4]，所得對(duì)應(yīng)的參數(shù)為Uk=[0，0.17，0.39，0.60，0.78，0.89，1.0]，節(jié)點(diǎn)矢量為U=[0，0，0，0，0.39，0.59，0.75，1.0，1.0，1.0，1.0]，全局插值所得的3次B樣條曲線見圖2(b)。

(a) 全局插值所得的2次B樣條曲線　　　　　　　　　　(b) 全局插值所得的3次B樣條曲線

由圖2可見，采用改進(jìn)后的參數(shù)化方法所得到的插值曲線，可以更好地處理各數(shù)據(jù)點(diǎn)處的過渡，沒有出現(xiàn)曲率突變的情況，使曲線更光滑，更合理地反映了數(shù)據(jù)點(diǎn)的分布情況。

4　結(jié)　論

對(duì)于給定數(shù)據(jù)點(diǎn)的非有理B樣條曲線插值，兩個(gè)重要環(huán)節(jié)就是數(shù)據(jù)點(diǎn)參數(shù)化和節(jié)點(diǎn)矢量的確定，它們將影響曲線的形狀。本文在分析現(xiàn)有算法的基礎(chǔ)上，提出了一種改進(jìn)的參數(shù)化和確定節(jié)點(diǎn)矢量的方法，結(jié)合反算出的控制頂點(diǎn)，總體上實(shí)現(xiàn)了一套曲線插值方法，該方法可以較準(zhǔn)確地反映出設(shè)計(jì)者的意圖，若在此基礎(chǔ)上形狀修改，則易于構(gòu)造所需的NURBS曲線。最后對(duì)兩組數(shù)據(jù)點(diǎn)進(jìn)行的仿真實(shí)驗(yàn)，驗(yàn)證了該算法的可行性和有效性。

[參考文獻(xiàn)]

[1]于謙,李纓,張彩明.基于切向約束構(gòu)造復(fù)合二次B樣條插值曲線[J].計(jì)算機(jī)學(xué)報(bào),2014,37(6):1342-1351.

[2]WEN Wei-bin,JIAN Kai-lin,LUO Shao-ming.2D numerical manifold method based on quartic uniform B-spline interpolation and its application in thin plate bending[J].Appl.Math.Mech.Engl.Ed.,2013,34(8):1017-1030

[3]葉鐵麗,李學(xué)藝,曾慶良.基于誤差控制的自適應(yīng)3次B樣條曲線插值[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(1):199-216.

[4]劉晶,施侃樂,雍俊海,等.利用控制頂點(diǎn)插值的光滑B樣條曲線構(gòu)造方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011,23(5):813-819.

[5]施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條[M].北京:高等教育出版社,2001.

[6]LES P,WAYNE T.非均勻有理B樣條[M].2版.趙罡,穆國(guó)旺,王拉柱,譯.北京:清華大學(xué)出版社,2010.

[7]GOFUKU S,TAMURA S,MAEKAWA T.Point-tangent point-normal B-spline curve interpolation by geometric algorithms[J].Computer Aided Design,2009,41(6):412-422.

[責(zé)任編輯：魏 強(qiáng)]

Optimization algorithm of B-spline curve global interpolation

and its implementation

WU Ting1,2,ZOU Hai2

(1.Network Information Center, Anhui Vocational College of Defense Technology, Lu’an 237011, China;

2.School of Computer Science and Technology, Anhui University, Hefei 230601, China)

Abstract:In the course of creating a B-spline curve by interpolating the given data points, it is needed to modify the initial shape of the curve repeatedly. In order to make the initial curve closer to the designers’ intentions, the existing algorithms were improved from two aspects of the data point parameterization and node vector determination. A modified method of chord length parameterization was put forward to calculate corresponding parameters for data points, and it could improve the transition of sharp turning. A method of average value was presented to obtain node vector, and it could effectively avoid the singular equations in coefficient matrix. On the whole, an algorithm of B-spline curve global interpolation was optimized, and in the end, the feasibility of the algorithm was visually proved by the experiment with two groups of typical data points.

Key words:B-spline curve;global interpolation;optimization algorithm