葉麗，謝明紅

（華僑大學(xué)機(jī)電及自動(dòng)化學(xué)院，福建 泉州 362021）

采用積累弦長法擬合3次NURBS曲線

葉麗，謝明紅

（華僑大學(xué)機(jī)電及自動(dòng)化學(xué)院，福建 泉州 362021）

根據(jù)已知的3次非均勻有理B樣條（NURBS）曲線型值點(diǎn)，采用效果較好的積累弦長參數(shù)化方法構(gòu)造節(jié)點(diǎn)矢量，從而得到B樣條基；利用帶權(quán)控制頂點(diǎn)的矩陣計(jì)算出全部控制頂點(diǎn)，最后擬合出所要求的曲線.擬合結(jié)果表明，該方法可以反映數(shù)據(jù)點(diǎn)按弦長的分布情況，適用于構(gòu)造任意次非均勻有理B樣條曲線節(jié)點(diǎn)矢量參數(shù)的計(jì)算，較好地適合于工程實(shí)踐的應(yīng)用.

非均勻有理B樣條；積累弦長；參數(shù)化；型值點(diǎn)；控制頂點(diǎn)；曲線擬合

CAD系統(tǒng)在設(shè)計(jì)自由曲面零件時(shí)，由于缺乏傳統(tǒng)方法的觸覺和視覺優(yōu)勢，因此常采用粘土等材料進(jìn)行傳統(tǒng)的手工設(shè)計(jì)，然后利用曲線曲面反求技術(shù)將其轉(zhuǎn)化為計(jì)算機(jī)可用的CAD模型.反求技術(shù)可以極大地縮短產(chǎn)品周期，更重要的是可以快速趕上或超過世界先進(jìn)生產(chǎn)技術(shù)水平.STEP（Standard Exchange of Product Data Model）國際標(biāo)準(zhǔn)中關(guān)于工業(yè)產(chǎn)品幾何定義的統(tǒng)一數(shù)學(xué)方法——非均勻有理B樣條（NURBS）方法為標(biāo)準(zhǔn)解析形式的初等曲線曲面、自由型曲線曲面的精確表示和設(shè)計(jì)提供了一個(gè)公共的數(shù)學(xué)表示.NURBS曲線曲面在實(shí)際應(yīng)用中可以分為兩種形式［1］：一種是已知控制點(diǎn)求解曲線曲面上的點(diǎn)，稱為正算問題；另一種情況是已知曲線曲面上的型值點(diǎn)求解曲線曲面的控制點(diǎn)，稱為反算問題.本文只討論3次NURBS曲線問題.

1 3次NURBS曲線

由n+1個(gè)多邊形控制頂點(diǎn)定義的1條k次NURBS曲線［2］，可以表示為1條分段有理多項(xiàng)式矢函數(shù)，即

式中：ωi（i=0，1，…，n）為權(quán)或者權(quán)因子，分別與控制頂點(diǎn)d（i=0，1，…，n）相聯(lián)系；首、末權(quán)因子ω0，ωn＞0，其他ωi≥0，順序k個(gè)權(quán)因子不同時(shí)為零，以防止分母為零，保留凸包性質(zhì)，曲線不致因權(quán)因子而退化為一點(diǎn).Ni，k（u）是由節(jié)點(diǎn)矢量U=［u0，ui，…，un+k+1］，按德布爾-考克斯遞推公式?jīng)Q定的k次規(guī)范B樣條基函數(shù).其遞推公式為

u0=u1=…=uk，un+1=un+2=…=un+k+1.

在大多數(shù)實(shí)際應(yīng)用里，端節(jié)點(diǎn)值分別取為0與1，因此有曲線定義域u∈［uk，un+1］=［0，1］.給定一組有序數(shù)據(jù)點(diǎn)qi（i=0，1，…，n），要求構(gòu)造一條NURBS曲線，順序通過這些數(shù)據(jù)點(diǎn)，也就是要從給定的數(shù)據(jù)點(diǎn)，求出定義該NURBS曲線的控制頂點(diǎn)，進(jìn)而擬合加工出NURBS曲線.

2 3次NURBS曲線擬合

2.1 參數(shù)值的計(jì)算

同一組型值點(diǎn)，即使采用同樣的插值（逼近）法，若選擇不同的參數(shù)化方法［3］，將得到不同的插值（逼近）曲線.型值點(diǎn)的參數(shù)化應(yīng)盡可能反映被插值（逼近）曲線的性質(zhì)，或設(shè)計(jì)員欲用型值點(diǎn)所構(gòu)造的曲線的性質(zhì).對型值點(diǎn)的基本參數(shù)化方法，主要有均勻參數(shù)化、積累弦長參數(shù)化、向心參數(shù)化等.

均勻參數(shù)化就是使每個(gè)節(jié)點(diǎn)區(qū)間長度是一個(gè)常數(shù)，即節(jié)點(diǎn)在參數(shù)軸上呈等距分布.這種參數(shù)化方法僅適合于型值點(diǎn)多邊形各邊（弦長）接近相等的場合.當(dāng)相鄰段弦長相差懸殊的情況下，生成插值曲線后，弦長較長的那一段曲線顯得較扁平，弦長較短的那段曲線則容易出現(xiàn)尖點(diǎn)或自交.積累弦長參數(shù)化法，可以反映數(shù)據(jù)點(diǎn)按弦長的分布情況，適用于構(gòu)造的任意k次非均勻有理B樣條曲線節(jié)點(diǎn)矢量，即參數(shù)的計(jì)算適合于工程實(shí)踐的應(yīng)用.

假定一條k次NURBS曲線通過的數(shù)據(jù)點(diǎn)為qi（i=0，1，…，n），其參數(shù)值的計(jì)算為

對于3次NURBS曲線，則有

由此可準(zhǔn)確算出每一個(gè)參數(shù)值，并得到其節(jié)點(diǎn)矢量U，以便繼續(xù)后面的運(yùn)算.

2.2 控制頂點(diǎn)的定義

一條NURBS曲線通過一組給定的數(shù)據(jù)點(diǎn)qi（i=0，1，…，n），要使其首、末端點(diǎn)分別與首、末數(shù)據(jù)點(diǎn)一致.即曲線的分段連接點(diǎn)依次與曲線定義域內(nèi)的節(jié)點(diǎn)一一對應(yīng)［4］，qi點(diǎn)有節(jié)點(diǎn)值uk+i（i=0，1，…，n）.該NURBS曲線由n+2個(gè)控制頂點(diǎn)di（i=0，1，…，n+2）與節(jié)點(diǎn)矢量U=［u0，u1，…，un+6］來定義，即控制頂點(diǎn)數(shù)目要比數(shù)據(jù)點(diǎn)數(shù)目多2個(gè)，共有n+2個(gè)未知頂點(diǎn).對于一條通過數(shù)據(jù)點(diǎn)qi（i=0，1，…，n）的3次NURBS曲線（k=3），其節(jié)點(diǎn)值為u3+i（i=0，1，…，n），節(jié)點(diǎn)矢量為U=［u0，u1，…，un+6］，對應(yīng)的控制頂點(diǎn)為di（i=0，1，…，n+2）.

2.3 3次B樣條基的計(jì)算

對于周期3次NURBS曲線，首、末數(shù)據(jù)點(diǎn)q0=qn.由于數(shù)據(jù)點(diǎn)是作為NURBS曲線的分段連接點(diǎn)，因此由NURBS曲線的性質(zhì)可知，這些數(shù)據(jù)點(diǎn)僅由其前后相鄰的3個(gè)帶權(quán)控制頂點(diǎn)決定［5］.

設(shè)帶權(quán)控制頂點(diǎn)為di（i=0，1，…，n+2）.其中：每一個(gè)di都是用齊次坐標(biāo)表示，而帶權(quán)數(shù)據(jù)點(diǎn)qi，i=0，1，…，n亦轉(zhuǎn)化為齊次坐標(biāo)表示.它們之間關(guān)系為

由上述NURBS曲線基本理論可知，Ni，3（u）叫做3次規(guī)范B樣條基函數(shù)，是由節(jié)點(diǎn)矢量U=［u0，u1，…，un+6］按德布爾-考克斯遞推公式?jīng)Q定的，即式（1）.

對于3次NURBS開曲線，常將兩端節(jié)點(diǎn)的重復(fù)度取為4，即

u0=u1=…=u3，un+3=un+4=…=un+6.

在大多數(shù)實(shí)際應(yīng)用里，端節(jié)點(diǎn)值分別取為0與1.因此，有曲線定義域u∈［u3，un+3］=［0，1］.于是，3次NURBS曲線有

u0=u1=…=u3=0，un+3=un+4=…=un+6=1.

當(dāng)u∈［ui，ui+1］，u=ui，i=0，1，2，…，n時(shí)，只有Ni+3，0（u）=1，其余均為0.這樣就將B樣條基中所有包含分母為0的項(xiàng)全部去掉了.經(jīng)整理，其公式為

2.4 控制頂點(diǎn)的計(jì)算

式（1）共含n+1個(gè)方程，對于C2連續(xù)的3次NURBS閉曲線，因首、末數(shù)據(jù)點(diǎn)相重，q0=qn，不計(jì)重復(fù)，方程數(shù)減少1個(gè)，剩下n個(gè).又由于首、末3個(gè)控制頂點(diǎn)依次相重［7］，即dn=d0，dn+1=d1，dn+2=d2，則未知控制頂點(diǎn)數(shù)少了3個(gè)，也剩下了n個(gè).因此，可從n個(gè)方程構(gòu)成的線性方程組中求解出n個(gè)未知控制頂點(diǎn).

將上述計(jì)算的3次B樣條基的結(jié)果代入，得到求解帶權(quán)控制頂點(diǎn)的矩陣表達(dá)式為

式（4）中：系數(shù)矩陣中的元素均為B樣條基函數(shù)的值，只與節(jié)點(diǎn)值有關(guān)，采用更直接方便的矩陣形式，有

由此，可求出全部未知控制頂點(diǎn).

對于3次NURBS開曲線，以及不要求在相重的首、末數(shù)據(jù)點(diǎn)q0=qn處C2連續(xù)的閉曲線，方程組（2）中的n+1個(gè)方程，不足以解決其中包含的n+3個(gè)未知控制頂點(diǎn)，還必須增加2個(gè)通常有邊界條件給定的附加方程.這時(shí)，求解擬合曲線未知控制頂點(diǎn)的線性方程組，可寫成矩陣形式，有式（6）中：系數(shù)矩陣中首行非零元素a1，b1，c1與右端列陣中矢量e1表示了首端點(diǎn)邊界條件；系數(shù)矩陣中末行非零元素an+1，bn+1，cn+1與右端列陣中矢量en+1表示了末端點(diǎn)邊界條件；其余各行元素ai，bi，ci（i=2，3，…，n）與閉曲線情況相同.較為常用的是切矢邊界條件［8］，即節(jié)點(diǎn)矢量兩端為4重節(jié)點(diǎn)和給定曲線兩端端點(diǎn)條件.

當(dāng)取首、末端節(jié)點(diǎn)重復(fù)度為4時(shí)，在四維空間中3次NURBS曲線首、末控制頂點(diǎn)就是首、末數(shù)據(jù)點(diǎn)，即d0=q0，dn+2=qn，且曲線在首、末端點(diǎn)處分別有切矢，即

其中：q0與qn分別為給定的首、末數(shù)據(jù)點(diǎn)q0與qn處的切矢，即端點(diǎn)切矢；其余元素的值同式（5）.

由節(jié)點(diǎn)矢量可求出系數(shù)矩陣，代入式（6），即可求出全部未知控制頂點(diǎn).

2.5 3次NURBS曲線擬合流程圖

在3次NURBS曲線擬合的過程中，首先根據(jù)已知的型值點(diǎn)，采用積累弦長參數(shù)化化法求出各個(gè)參數(shù)值；然后，求得節(jié)點(diǎn)矢量.根據(jù)節(jié)點(diǎn)矢量的節(jié)點(diǎn)集分別計(jì)算B樣條基函數(shù)，帶入帶權(quán)控制頂點(diǎn)矩陣，求解線性方程組.最后，經(jīng)計(jì)算可得到所有的控制頂點(diǎn)，并擬合出曲線.這個(gè)功能可以很方便的用C++語言編程實(shí)現(xiàn)，插補(bǔ)流程圖，如圖1所示.

圖1 3次NURBS曲線擬合流程圖Fig.1 Flow chart of third-order NURBS curve fitting

3 NURBS曲線擬合實(shí)例

設(shè)qk=｛（-80，-60），（-40，20），（-20，10），（-10，20），（30，-20），（50，40），（70，30）｝，采用3次曲線來重構(gòu)qk.其分段弦長分別是

則總弦長是266.所以，有節(jié)點(diǎn)矢量的值為

將節(jié)點(diǎn)矢量代入線性方程組，再結(jié)合式（5），可算出全部控制頂點(diǎn)，所擬合出的曲線，如圖2所示.

圖2 3次NURBS曲線擬合Fig.2 Third-order NURBS curve fitting

4 結(jié)束語

在反算控制點(diǎn)過程中，用的參數(shù)化方法不同，最后的結(jié)果也有差別.所以，在實(shí)際應(yīng)用中要根據(jù)數(shù)據(jù)點(diǎn)的分布情況，選擇合適的參數(shù)化方法來反算控制點(diǎn).比較而言，采用積累弦長參數(shù)化法最合適.積累弦長參數(shù)化法如實(shí)反映了數(shù)據(jù)點(diǎn)按弦長的分布情況，克服了數(shù)據(jù)點(diǎn)按弦長分布不均勻情況下采用均勻參數(shù)化所出現(xiàn)的問題，一直被認(rèn)為是最佳參數(shù)化法，擬合出的NURBS曲線符合要求.

［1］朱心雄.自由曲線曲面造型技術(shù)［M］.北京：科學(xué)出版社，2000.

［2］施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條［M］.北京：高等教育出版社，2001.

［3］BRADLEY C，VICKERS G W.Automated rapid prototyping utilizing laser scanning and free-form machining［J］.CIRP Annals，1992，41（2）：37-40.

［4］呂丹，童創(chuàng)明，鄧發(fā)升，等.3次NURBS曲線控制點(diǎn)的計(jì)算［J］.彈箭與制導(dǎo)學(xué)報(bào)，2006，26（4）：357-359.

［5］ZHANG Ying-jie，LIU Shang-ning.Feature extraction from slice data for reverse engineering［J］.Frontiers of Mechanical Engineering，2007，2（1）：25-31.

［6］韓慶瑤，趙保亞，譚建鑫，等.NURBS曲線曲面重構(gòu)的方法［J］.機(jī)械設(shè)計(jì)與制造，2006，3（3）：137-139.

［7］SHAMSUDDIN S M，AHMEDL M A，SAMIAN Y.NURBS skinning surface for ship hull design based on new parameterization method［J］.The International Journal of Advanced Manufacturing Technology，2006，28（9）：936-941.

［8］YEH Syh-Shiuh，SU Hsin-Chuan.Implementation of online NURBS curve fitting process on CNC machines［J］.The International Journal of Advanced Manufacturing Technology，2009，40（5/6）：531-540.

Third-Order Non-Uniform Rational B-Spline Curve Fitting Based on Method of Accumulating Chord Length

YE Li，XIE Ming-hong
（College of Mechanical Engineering and Automation，Huaqiao University，Quanzhou 362021，China）

According to a given set of data points of the third-order non-uniform rational B-spline（NURBS）curve，the parametrization method of accumulating chord length which is more effective is used to construct the knot vectors to obtain the B-spline basis.All of the control points are calculated using the matrix of the control points with powers to fit the required curve finally.The final result reveals that data distribution according to the chord length can be shown by this method.This method can be used in parameter calculation during construction of the knot vector of any order NURBS curve，and can be better fit for engineering practice.

non-uniform rational B-spline；accumulating chord length；parameterization；data point；control points；curve fitting

TB 115；TP 391.7

A

1000-5013（2010）04-0383-05

（責(zé)任編輯：陳志賢 英文審校：鄭亞青）

2008-12-12

謝明紅（1968-），男，研究員，主要從事于數(shù)控技術(shù)、CAD/CAM及計(jì)算機(jī)視覺的研究.E-mail：xmh3721@tom.com.

福建省自然科學(xué)基金計(jì)劃資助項(xiàng)目（E0640007）