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

吳婷1,2，鄒海2

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

2.安徽大學 計算機科學與技術學院， 安徽 合肥 230601)

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

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

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

[中圖分類號]O241.5

收稿日期：2014-11-13

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

作者簡介：吳婷(1983—)，女，安徽省金寨縣人，安徽國防科技職業(yè)學院實驗師，安徽大學碩士研究生，主要研究方向為計算機應用技術；鄒海(1969—)，男，安徽省壽縣人，安徽大學副教授，碩士生導師，博士，主要研究方向為智能計算、中間件技術。

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

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

1　 B樣條曲線的定義

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

(1)

其中：a≤u≤b；Pi是曲線的控制頂點；Ni,p(u)是p次B樣條基函數(shù)；定義域為非周期節(jié)點矢量U，其數(shù)值在區(qū)間[ui,ui+p+1)上非零，并按照公式(2)和(3)求取：

(2)

(3)

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

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

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

(4)

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

2.1求取參數(shù)值

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

(5)

2.2　確定節(jié)點矢量

從理論上講，節(jié)點矢量可以等距分布，即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é)點矢量用公式(6)求出：

(6)

2.3反算控制頂點

(7)

3　算法應用實例

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

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

第二組數(shù)據(jù)點為Q=[-2，-4；10，0；6，20；21，40；36，20；32，0；44，-4]，所得對應的參數(shù)為Uk=[0，0.17，0.39，0.60，0.78，0.89，1.0]，節(jié)點矢量為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可見，采用改進后的參數(shù)化方法所得到的插值曲線，可以更好地處理各數(shù)據(jù)點處的過渡，沒有出現(xiàn)曲率突變的情況，使曲線更光滑，更合理地反映了數(shù)據(jù)點的分布情況。

4　結　論

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

[參考文獻]

[1]于謙,李纓,張彩明.基于切向約束構造復合二次B樣條插值曲線[J].計算機學報,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]葉鐵麗,李學藝,曾慶良.基于誤差控制的自適應3次B樣條曲線插值[J].計算機工程與應用,2013,49(1):199-216.

[4]劉晶,施侃樂,雍俊海,等.利用控制頂點插值的光滑B樣條曲線構造方法[J].計算機輔助設計與圖形學學報,2011,23(5):813-819.

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

[6]LES P,WAYNE T.非均勻有理B樣條[M].2版.趙罡,穆國旺,王拉柱,譯.北京:清華大學出版社,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.

[責任編輯：魏 強]

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