孔祥洪　李迪　焦青松

(華南理工大學(xué) 機械與汽車工程學(xué)院, 廣東 廣州510640)

?

NURBS插補快速求值算法*

孔祥洪李迪焦青松

(華南理工大學(xué) 機械與汽車工程學(xué)院, 廣東 廣州510640)

摘要：當(dāng)對非均勻有理B樣條(NURBS)曲線進行高密度插值時,運用分段冪函數(shù)方法對基函數(shù)進行求值的效率遠高于傳統(tǒng)的de-Boor算法.為此,文中從NURBS插補計算的特點出發(fā),結(jié)合de-Boor遞推計算規(guī)律,設(shè)計了NURBS插補快速求值算法.首先采用該算法計算NURBS在各節(jié)點區(qū)間的基函數(shù)顯式方程,再運用顯式方程進行NURBS插補點求值,并設(shè)計相應(yīng)的NURBS曲線插補器.復(fù)雜NURBS曲線的銑削加工實驗結(jié)果表明,該算法能夠有效地縮減NURBS曲線插補求值的計算耗時,提高插補計算的實時性.

關(guān)鍵詞：NURBS;基函數(shù);快速算法;參數(shù)插補

在手機工業(yè)、航空工業(yè)以及模具工業(yè)中,出于對特殊形狀、特殊功能或高加工質(zhì)量的需求,自由曲面零件的加工制造已成為常態(tài).

加工自由曲面零件通常是一個復(fù)雜且費時費力的過程.越來越多的零件加工開始采用非均勻有理B樣條(NURBS)插補來規(guī)避傳統(tǒng)的計算機輔助制造(CAM)系統(tǒng)在自由曲面和自由曲線加工方面的不足.然而,目前大量的NURBS插補器的研究主要集中于三階NURBS曲線插補[1-7].過于沉重的計算負荷成為限制高階(四階以上)NURBS曲線應(yīng)用于加工工業(yè)的重要因素.高階NURBS曲線能夠提供更高的擬合精度、更優(yōu)秀的連續(xù)性,適合有高加工精度需求的場合.目前的NURBS插補算法都只能在精度與實時性之間進行取舍[8].大部分的插補算法都傾向于為了獲取更好的實時性而在插補精度方面做出適當(dāng)?shù)耐讌f(xié).

高階NURBS曲線插補的高負荷計算量主要來源于其求值求導(dǎo)計算,而在NURBS求值求導(dǎo)計算中最耗時的是NURBS基函數(shù)的求值計算.NURBS基函數(shù)的定義方法主要有采用截尾冪函數(shù)的差商定義、開花定義、遞推公式定義等[9-11].文獻[12-13]基于差商定義提出了NURBS曲線曲面的顯示矩陣表示方法及其算法.文獻[11]基于遞推公式定義提出了基函數(shù)遞推算法(de-Boor算法),由于該算法易于在計算機中實現(xiàn)而成為了NURBS基函數(shù)求值最為常用的算法.

運用分段冪函數(shù)對NURBS基函數(shù)進行求值的算法也漸漸引起人們的關(guān)注,當(dāng)要對NURBS曲線進行高密度插值時,該算法要比傳統(tǒng)de-Boor算法高效得多[13].NURBS曲面曲線矩陣表示正是源于該算法的研究.但有關(guān)系數(shù)矩陣的顯式表示研究大多集中于推導(dǎo)計算,很少應(yīng)用于插補算法中[14-15].王國勛等[16]提出的快速求值求導(dǎo)插補算法也局限于對NURBS曲線的某個節(jié)點區(qū)間進行插補研究.

運用系數(shù)矩陣推導(dǎo)計算NURBS基函數(shù)的分段冪函數(shù),由于其計算過程過于復(fù)雜而難以應(yīng)用于NURBS插補算法中.為了簡化推導(dǎo)過程,提高計算效率,文中設(shè)計了基于前向路徑增益求和方法的NURBS插補快速求值算法:通過計算基函數(shù)Ni,p(u)與零階基函數(shù)Ni,0(u)之間的前向路徑增益之和來快速計算Ni,p(u)在其對應(yīng)的節(jié)點區(qū)間的分段冪函數(shù)表達式;應(yīng)用該算法設(shè)計了相應(yīng)的NURBS插補器,并通過加工實驗驗證該算法的效率.

1NURBS表達式和de-Boor算法

1.1　NURBS曲線表達式

根據(jù)NURBS曲線的數(shù)學(xué)定義[17],對于給定的節(jié)點向量U=(u0,u1,…,um)、權(quán)重向量W=(w0,w1,…,wn)以及控制點向量P=(P0,P1,…,Pn),p階NURBS曲線公式可以表示為

(1)

k階NURBS導(dǎo)矢計算公式為

(2)

式中,A(k)和W(i)可由B樣條曲線的導(dǎo)矢公式

(3)

求得.

1.2　NURBS基函數(shù)的de-Boor遞推算法

de-Boor算法的遞推計算公式為

(4)

根據(jù)式(4),在參數(shù)區(qū)間u∈[ui,ui+1)內(nèi),零階基函數(shù)有且僅有Ni,0(u)取值非0;根據(jù)式(4)中的遞推關(guān)系,p階基函數(shù)只有p+1個基函數(shù)取值為非0.該性質(zhì)被稱為基函數(shù)的局部支撐性.因此p階NURBS曲線上任意點的求值都只需要計算p+1項非0的基函數(shù)的值.de-Boor算法是運用基函數(shù)局部支撐性的算法.在u∈[ui,ui+1)區(qū)間內(nèi),只有基函數(shù)Ni,p(u),Ni-1,p(u),…,Ni-p,p(u)取值非0,則運用de-Boor算法對以上基函數(shù)進行求值計算的過程形如金字塔的結(jié)構(gòu),如圖1所示.

圖1　de-Boor算法計算B樣條基函數(shù)的過程Fig.1　Calculation process of B-spline basis function using de-Boor algorithm

2基函數(shù)的分段冪函數(shù)快速計算方法

如前所述,運用de-Boor算法計算NURBS基函數(shù)需要從零階基函數(shù)開始依次向上進行遞推計算.而運用式(1)計算NURBS曲線上的點只需要p階基函數(shù),即運用de-Boor算法計算得到的0~p-1階基函數(shù)的值均為計算p階基函數(shù)而產(chǎn)生的中間值.文中設(shè)計的算法是運用基函數(shù)的分段冪函數(shù)直接計算p階基函數(shù)的值,避免了0~p-1階基函數(shù)求值的計算,從而提高計算效率.

通常是使用差商法[13]計算NURBS基函數(shù)的分段冪函數(shù),進而得到系數(shù)矩陣.但該方法的計算推導(dǎo)過程較為復(fù)雜且存在高階誤差.為了簡化NURBS基函數(shù)的分段冪函數(shù)的計算過程,提高計算效率,文中設(shè)計了一種快速計算基函數(shù)的分段冪函數(shù)的方法,即將式(4)改寫為

(5)

圖2給出了一階基函數(shù)Ni-1,1、二階基函數(shù)Ni-1,2和三階基函數(shù)Ni-1,3、Ni-2,3的遞推計算過程.運用式(5)計算得到這4個基函數(shù)的取值分別為

圖 2　B樣條基函數(shù)的遞推計算過程Fig.2　Recursive calculation process of B-spline basis function

根據(jù)圖2所示的基函數(shù)遞推過程,以上列舉的基函數(shù)遞推計算過程存在如下規(guī)律:假設(shè)圖1中所有基函數(shù)值被看作計算節(jié)點,節(jié)點間的連線為通道,連線的箭頭指示通道的前進方向,節(jié)點間的系數(shù)(fi,p或gi,p)為通道增益,將從初始節(jié)點Ni,0沿著通道前進方向連接到任意節(jié)點Ni,p所經(jīng)過的通道定義為前向路徑,所經(jīng)過通道的增益的積定義為路徑增益,則Ni,p的值等于所有不重復(fù)的路徑增益之和,即

(6)

式中,L(j)為第j條前向路徑的增益值,R為不重復(fù)的前向路徑總數(shù).

為了驗證式(6)計算方法的可行性,以圖2為例進行說明.如圖2(a)所示,從Ni,0到Ni-1,1只有一條前向路徑,其增益為gi,1,Ni-1,1的路徑增益之和為gi,1.在圖2(b)中,Ni,0到Ni-1,2有兩條不重復(fù)的前向路徑,其增益分別為fi,1gi,2和gi,1fi-1,2,Ni-1,2的路徑增益之和為fi,1gi,2+gi,1fi-1,2.在圖2(c)中,Ni,0到Ni-1,3有3條不重復(fù)的前向路徑,它們的增益分別為fi,1fi,2gi,3、fi,1gi,2fi-1,3和gi,1fi-1,2gi-1,3,Ni-1,3的路徑增益之和為fi,1fi,2gi,3+fi,1gi,2fi-1,3+gi,1fi-1,2gi-1,3.顯然,以上結(jié)果與運用式(5)遞推計算得到的結(jié)果完全一致.

現(xiàn)用數(shù)學(xué)歸納法證明式(6).

證明當(dāng)p=1時,根據(jù)圖1可以知道,Ni,1(u)和Ni-1,1(u)的前向路徑數(shù)為1,其通道增益分別為fi,1和gi,1,根據(jù)式(6)計算可以得到Ni,1(u)=fi,1,Ni-1,1(u)=gi,1.

運用de-Boor遞推公式(式(4))計算Ni,1(u)和Ni-1,1(u)的值:

顯然，當(dāng)p=1時式(6)成立.

假設(shè)當(dāng)p=n-1時式(6)成立,則有

根據(jù)式(4)有

Ni,n(u)=fi,pNi,n-1(u)+gi+1,pNi+1,n-1(u)=

(7)

式中,∑fi,pL1(j)為Ni,0節(jié)點經(jīng)由Ni,n-1節(jié)點連接到Ni,n節(jié)點的前向路徑的增益之和,∑gi+1,pL2( j )為Ni,0節(jié)點經(jīng)由Ni+1,n-1節(jié)點連接到Ni,n節(jié)點的前向路徑的增益之和,兩者的路徑不重復(fù)且所有從Ni,0節(jié)點連接至Ni,n節(jié)點的前向路徑必然經(jīng)過以上兩節(jié)點,故∑fi,pL1(j)與∑gi+1,pL2(j)的和等于所有Ni,0節(jié)點連接到Ni,n節(jié)點的不重復(fù)路徑增益之和,即當(dāng)p=n時式(6)的結(jié)論也成立,證畢.

根據(jù)式(5)可以確定任意階NURBS基函數(shù)與Ni,0的遞推關(guān)系.圖3給出了一階到五階的NURBS基函數(shù)遞推關(guān)系.結(jié)合圖3所示的NURBS基函數(shù)遞推關(guān)系,運用式(6)能夠簡單、直觀地計算得到五階以內(nèi)的NURBS各參數(shù)節(jié)點區(qū)間的基函數(shù)的分段冪函數(shù),繼之能夠快速、高效地計算得到基函數(shù)的值,完成NURBS插補求值計算.若需要計算五階以上的NURBS的分段冪函數(shù),只需要運用式(5),把圖3中的遞推關(guān)系依次向上往高階遞推即可.

圖3　五階B樣條基函數(shù)的遞推計算過程Fig.3　Recursive calculation process of 5-order B-spline basisfunction

3NURBS曲線插補器設(shè)計

應(yīng)用于NURBS曲線的插補器設(shè)計流程如圖3所示.該NURBS曲線插補器主要由速度規(guī)劃算法、插補算法及插補點求值算法組成.速度規(guī)劃算法主要是根據(jù)設(shè)定的動力學(xué)模型規(guī)劃插補過程中每個插補周期的插補速度.插補算法主要是根據(jù)當(dāng)前的規(guī)劃速度和當(dāng)前樣條參數(shù)值(uk)計算出下一插補點的參數(shù)值(uk+1).求值算法則要根據(jù)計算得到的樣條參數(shù)值(u)計算出與之相對應(yīng)的插補點的值.

運用式(6)計算得到的基函數(shù)分段冪函數(shù)表達式在NURBS的參數(shù)節(jié)點區(qū)間內(nèi)是分段連續(xù)的.在NURBS曲線插補的過程中,樣條參數(shù)逐漸增大并依次跨越NURBS曲線的各個參數(shù)節(jié)點.基于以上冪函數(shù)得到分段連續(xù)性,當(dāng)樣條參數(shù)跨越參數(shù)節(jié)點時,需要定位樣條參數(shù)當(dāng)前所處的節(jié)點區(qū)間,并重新計算基函數(shù)對應(yīng)于該參數(shù)節(jié)點區(qū)間的顯式方程.在樣條參數(shù)跨越下一個參數(shù)節(jié)點前,計算NURBS插補點所需要的基函數(shù)值，均可以運用以上顯式方程進行快速地計算.因此，在圖4的NURBS曲線插補器中設(shè)計了判斷環(huán)節(jié),用于判斷插補過程中樣條參數(shù)的值是否跨越參數(shù)節(jié)點,并依次判斷是否需要重新計算基函數(shù)在該節(jié)點區(qū)間的顯式方程.

圖4　NURBS曲線插補器流程圖Fig.4　Flowchart of NURBS curve interpilator

4算法效率分析與實驗

4.1　算法效率分析

對各階基函數(shù)的求值計算在NURBS的求值求導(dǎo)計算過程中占用了絕大部分的計算耗時.通過分析每個NURBS插補點各階基函數(shù)求值的計算規(guī)模，即能評估不同求值求導(dǎo)算法的計算效率.

為評估文中提出的快速求值求導(dǎo)算法的計算效率,本節(jié)設(shè)計了實例仿真對算法進行分析.用于仿真實驗的NURBS曲線參數(shù)如下:階數(shù)p=3;節(jié)點序列U={0,0,0,0,1,2,3,4,5,6,7,8,9,10,10,10,10};控制頂點集P={(0,0),(0.1,20.01),(0.2,20.02),(0.3,20.03),(20,40),(25,33),(30,20),(35,7),

(40,0),(54.8,18.98),(54.9,18.99),(55,19),(60,20)};權(quán)重向量w=(1,1,1,1,1,1,1,1,1,1,1,1,1).由以上參數(shù)確定的NURBS曲線如圖5所示.

文中采用的仿真實例為三階NURBS曲線,故在曲線插補計算中需要計算三階基函數(shù)的顯式方程.假設(shè)當(dāng)前所處的參數(shù)節(jié)點區(qū)間為[ui,ui+1],運用式(6)表示的算法并結(jié)合圖3所示的基函數(shù)遞推關(guān)系,得到基函數(shù)的分段冪函數(shù)顯式表達式的計算過程,如圖6所示.根據(jù)NURBS的局部支撐性性質(zhì),

圖5　NURBS仿真曲線及控制多邊形Fig.5　NURBS simulation curve and control ploygon

圖6　B樣條基函數(shù)的分段冪函數(shù)的計算過程Fig.6　Calculation process of piecewise power function of B-spline basis function

在該節(jié)點區(qū)間內(nèi)只有Ni,3、Ni-1,3、Ni-2,3和Ni-3,3的值為非0.圖6中Ni,3和Ni-3,3分別只有一條前向路徑,其增益分別為fi,1fi,2fi,3和gi,1gi-1,2gi-2,3;Ni-1,3和Ni-2,3各有3條前向路徑,它們的增益分別為fi,1fi,2gi,3、fi,1gi,2fi-1,3、gi,1fi-1,2fi-1,3和fi,1fi,2gi,3、fi,1gi,2fi-1,3、fi,1gi,2fi-1,3、gi,1fi-1,2fi-1,3.根據(jù)式(6)可以求得基函數(shù)Ni,3、Ni-1,3、Ni-2,3和Ni-3,3的前向路徑增益之和:

(8)

把式(5)中的fi,p和gi,p代入式(7),則有

(ui+1-ui-1)-1(ui+1-ui)-1,

(ui+1-ui-1)-1(ui+1-ui)-1,

以上等式即為在u∈[ui,ui+1)區(qū)間內(nèi)的基函數(shù)分段冪函數(shù)的顯式表達式.取圖5所示曲線的u∈[1,2)計算該節(jié)點區(qū)間的基函數(shù)顯式方程,該節(jié)點區(qū)間的節(jié)點索引值i=4,根據(jù)NURBS局部支撐性,在該節(jié)點區(qū)間不為0的基函數(shù)為N1,3、N2,3、N3,3和N4,3.計算顯式方程所需參數(shù)節(jié)點值為ui-2=ui-1=0,ui=1,ui+1=2,ui+2=3,ui+3=4.

把以上參數(shù)節(jié)點的值代入基函數(shù)的分段冪函數(shù)方程,可以得到u∈[1,2)的基函數(shù)顯式方程,即

運用以上基函數(shù)顯式方程,可以通過樣條參數(shù)u代入直接計算基函數(shù)的值.在NURBS插補點求值計算過程中,計算三階基函數(shù)N1,3、N2,3、N3,3和N4,3的取值只需要進行12次乘法運算和12次加法運算.

為比較,按圖1所示的計算方法,基于de-Boor算法進行基函數(shù)求值是一個逐階向上遞推的計算過程.根據(jù)遞推公式(4),對于NURBS曲線任意一個p階基函數(shù)的求值,運用de-Boor算法需要進行5p(p+1)/2次加法計算、p(p+1)次乘法計算和p(p+1)次除法計算,故計算p階所有基函數(shù)時需要進行5p(p+1)2/2次加法計算、 p(p+1)2次乘法計算和p(p+1)2次除法計算.

文獻[17]給出了優(yōu)化的de-Boor算法.運用該優(yōu)化算法能夠減少傳統(tǒng)de-Boor算法中存在的冗余計算,明顯提高計算效率.3種算法在一次NURBS插補中計算基函數(shù)取值需要耗費的計算量比較如表1所示.

表13種算法的計算量對比

Table1Comparisonofarithmeticoperationamongthreealgorithms

運算傳統(tǒng)de-Boor算法優(yōu)化de-Boor算法文中算法加法1204512乘法481812除法48180

為了簡化比較結(jié)果,假設(shè)乘法運算和除法運算的計算耗時與加法運算的計算耗時相等,則運用傳統(tǒng)de-Boor算法在一次NURBS插補中需要進行216次運算,運用優(yōu)化de-Boor算法需要進行81次運算,而文中算法只需要進行24次運算.文中算法所需計算耗時為傳統(tǒng)de-Boor算法的1/9,相當(dāng)于優(yōu)化de-Boor算法的1/3.基于以上比較結(jié)果,文中算法的計算效率明顯優(yōu)于de-Boor算法.若是四階以上的NURBS基函數(shù)求值,文中算法的優(yōu)勢將會更加明顯.

4.2　加工實驗及結(jié)果分析

如圖7所示,加工實驗由基于PC平臺構(gòu)建的運動控制系統(tǒng)完成.運動控制系統(tǒng)主要是由PC機、上位機編程軟件、運動控制卡以及插補算法構(gòu)成.上位機編程軟件主要用于實現(xiàn)人機數(shù)據(jù)交互功能,方便地導(dǎo)入NURBS曲線、設(shè)置參數(shù)和監(jiān)視加工狀態(tài).運動控制卡采用PCI接口與PC機實現(xiàn)數(shù)據(jù)交換,在板卡中采用了高性能DSP芯片實現(xiàn)插補算法,再通過板卡上的FPGA芯片采集IO信號和實現(xiàn)控制脈沖輸出.

圖7　加工實驗Fig.7　Machining experiment

加工實驗采用了一段較為復(fù)雜的三階NURBS曲線(形如一只飛翔中的鴿子).NURBS插補器被構(gòu)建于板卡的DSP芯片內(nèi).上位機軟件采集的NURBS曲線參數(shù)直接傳輸至板卡上的DSP芯片中進行插補運算,并結(jié)合FPGA芯片完成NURBS的加工控制.加工實驗采用的運動控制參數(shù)如下:最大速度為50 mm/s,最大加速度為100 mm/s2,最大加加速度為5 000 mm/s3,插補周期為1 ms,前瞻周期數(shù)為2 000,弦高容差為0.001 mm,速度浮動容差為0.005%.

如圖4所示,完整的NURBS插補算法主要由運動規(guī)劃、參數(shù)插補、插補點求值3個步驟組成.在運動規(guī)劃方面,加工試驗采用了具有前瞻功能的自適應(yīng)運動規(guī)劃算法及S型加減速策略.在參數(shù)插補求值方面,加工試驗中采用了重構(gòu)映射插補算法[1].

運用DSP內(nèi)部的定時器能夠監(jiān)測插補過程的總耗時.傳統(tǒng)de-Boor算法[11]、差商算法[12]、系數(shù)矩陣算法[14]、優(yōu)化de-Boor算法[17]及文中算法的插補總耗時分別為35.636、30.691、26.706、26.592、20.628 s.如前所述,插補器中除了插補求值算法外,還有運動規(guī)劃算法、前瞻算法、曲率自適應(yīng)算法等.插補總耗時是插補求值算法耗時加上其他算法耗時的結(jié)果.由于實驗條件所限，無法在加工實驗過程中分別檢測得到各算法在插補過程中的耗時，但以前面的總插補耗時結(jié)果進行粗略評估,文中算法的耗時依然明顯少于其他算法,算法效率以及實時性都有明顯的優(yōu)勢.若將前面的插補總耗時減去其他算法的耗時,則文中算法的計算效率相對于其他算法具有更加明顯的優(yōu)勢.

5結(jié)論

文中從NURBS插補計算的特點出發(fā),結(jié)合de-Boor遞推計算規(guī)律,設(shè)計了快速獲取NURBS基函數(shù)的分段多項式解析式的算法.該算法獲得的多項式解析式能直接用于樣條函數(shù)求值,避免了繁雜的遞推計算,大幅度削減所需的計算耗時.文中算法通過有效控制樣條基函數(shù)的計算量來實現(xiàn)NURBS曲線曲面上插補點及其導(dǎo)數(shù)的快速求值,增強了插補器的實時性.文中基于所提快速求值算法設(shè)計開發(fā)了NURBS插補運動控制系統(tǒng),并完成復(fù)雜NURBS曲線的銑削加工實驗,結(jié)果表明,該算法能夠有效地縮減NURBS曲線插補求值的計算耗時,提高插補計算的實時性.文中所提算法不僅適用于提高樣條基函數(shù)的計算效率,還可以進一步導(dǎo)出NURBS曲線曲面的基函數(shù)系數(shù)矩陣,拓寬NURBS在理論和應(yīng)用中的研究空間.

參考文獻:

[1]LIU Min,HUANG Yu,YIN Ling.Development and implementation of a NURBS interpolator with smooth feedrate scheduling for CNC machine tools [J].International Journal of Machine Tools & Manufacture,2014,87:1-15.

[2]ZHAO Huan,ZHU LiMin,DING Han.A parametric interpolator with minimal feed fluctuation for CNC machine tools using arc-length compensation and feedback correction [J].International Journal of Machine Tools & Manufacture,2013,75:1-8.

[3]CHENG C W,TSAI M C.Real-time variable feedrate NURBS curve interpolator for CNC machining [J].International Journal of Advanced Manufacturing Technology,2004,23(11):865- 873.

[4]SUN Yuwen,ZHAO Yang,BAO Yurong,et al.A novel adaptive-feedrate interpolation method for NURBS tool path with drive constraints [J].International Journal of Machine Tools & Manufacture,2014,77:74-81.

[5]FANG Jing-Jing,HUNG Chia-Lien.An improved parameterization method for B-spline curve and surface interpolation [J].Computer-Aided Design,2013,45(6):1005-1028.

[6]GRECO L,CUOMO M.B-spline interpolation of Kirchhoff-love space rods [J].Computer Methods in Applied Mechanics and Engineering,2013,56:251-269.

[7]王世勇,李迪.NURBS圖形激光雕刻算法及其嵌入式實現(xiàn) [J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2010,38(6):112-117.

WANG Shi-yong,LI Di.Algorithm and embedded implementation of laser marking of NURBS images [J].Journal of South China University of Technology(Natural Science Edition),2010,38(6):112-117.

[8]LEI W T,WANG S B.Robust real-time NURBS path interpolators [J].International Journal of Machine Tools & Manufacture,2009,49:625- 633.

[9]CURRY H B,SCHOENBERG I J.On spline distributions and their limits:the Pólya distribution functions [J].Bulletin of the American Mathematical Society,1947,53:109.

[10]RANSHAW L.Blossoming:a connect-the-dots approach to splines [R].Palo Alto:Digital,Systems Research Center,

1987.

[11]DE BOOR C.On calculating with B-splines [M].New York:Springer-Verlag,1978.

[12]SCHUMKER L.Spline functions:basic theory [M].New York:John Wiley & Sons,1981.

[13]潘日晶.NURBS曲線曲面的顯式矩陣表示及其算法 [J].計算機學(xué)報,2001,24(4):358-366.

PAN Ri-jing.Explicit matrix representation for NURBS curves and surfaces and its algorithm [J].Chinese Journal of Computers,2001,24(4):358-366.

[14]CHOI B K,YOO W S,LEE C S.Matrix representation for NURBS curves and surfaces [J].Computer-Aided Design,1990,22(4):235-240.

[15]王學(xué)福,孫家廣,秦開懷.NURBS的符號矩陣表示及其應(yīng)用 [J].計算機學(xué)報,1993,16(1):29-34.

WANG Xue-fu,SUN Jia-guang,QIN Kai-huai.Symbolic matrix representation of NURBS and its applications [J].Chinese Journal of Computers,1993,16(1):29-34.

[16]王國勛,舒啟林,王軍,等.NURBS 直接插補技術(shù)中快速求值求導(dǎo)算法 [J].東北大學(xué)學(xué)報(自然科學(xué)版),2012,33(7):1021-1024.

WANG Guo-xun,SHU Qi-lin,WANG Jun,et al.Algorithm of fast evaluation and derivation for the technique of NURBS direct interpolation [J].Journal of Northeas-tern University(Natural Science),2012,33(7):1021-1024.

[17]PIEGL L,TILLER W.The NURBS book [M].2nd ed.Berlin:Springer,1997.

An Efficient Evaluation Algorithm for NURBS Interpolation

KONGXiang-hongLIDiJIAOQing-song

(School of Mechanical and Automotive Engineering, South China University of Technology, Guangzhou 510640, Guangdong, China)

Abstract:In the high-density interpolation of non-uniform rational B-spline (NURBS) curves, using the piecewise power function method to evaluate the B-spline basis function consumes much less computing time than the traditional de-Boor algorithm. Therefore, on the basis of the characteristic of the NURBS interpolation, an efficient eva-luation algorithm for the NURBS interpolation is proposed by drawing on the recursive calculation laws of the de-Boor algorithm. First, the proposed algorithm is used to deduce the explicit equations of the B-spline basis function in each spline parameter knot interval. Then, NURBS interpolation points are evaluated by using explicit equations, and a corresponding NURBS curve interpolator is designed. The results of the milling experiment with complex NURBS curves show that the proposed algorithm can effectively reduce the computing time of the NURBS curve interpolation and can improve the real-time performance of NURBS interpolators.

Key words:NURBS; spline function; efficient algorithm; parametric interpolation

doi：10.3969/j.issn.1000-565X.2016.01.013

中圖分類號：TP391

作者簡介：孔祥洪(1984-),男,博士生,主要從事嵌入式運動控制算法研究.E-mail:6382026@qq.com

*基金項目：國家“863”計劃項目(2012AA040909)

收稿日期：2015-05-07

文章編號：1000-565X(2016)01- 0085- 08

Foundation item： Supported by the National High-Tech R & D Program of China(2012AA040909)