NURBS插補(bǔ)快速求值算法*

孔祥洪　李迪　焦青松

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

?

NURBS插補(bǔ)快速求值算法*

孔祥洪李迪焦青松

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

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

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

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

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

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

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

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

1NURBS表達(dá)式和de-Boor算法

1.1　NURBS曲線表達(dá)式

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

(1)

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

(2)

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

(3)

求得.

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

de-Boor算法的遞推計(jì)算公式為

(4)

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

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

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

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

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

(5)

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

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

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

(6)

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

為了驗(yàn)證式(6)計(jì)算方法的可行性,以圖2為例進(jìn)行說明.如圖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é)果與運(yùn)用式(5)遞推計(jì)算得到的結(jié)果完全一致.

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

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

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

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

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

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

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

3NURBS曲線插補(bǔ)器設(shè)計(jì)

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

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

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

4算法效率分析與實(shí)驗(yàn)

4.1　算法效率分析

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

為評估文中提出的快速求值求導(dǎo)算法的計(jì)算效率,本節(jié)設(shè)計(jì)了實(shí)例仿真對算法進(jìn)行分析.用于仿真實(shí)驗(yàn)的NURBS曲線參數(shù)如下:階數(shù)p=3;節(jié)點(diǎn)序列U={0,0,0,0,1,2,3,4,5,6,7,8,9,10,10,10,10};控制頂點(diǎn)集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所示.

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

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

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

在該節(jié)點(diǎn)區(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ù)的顯式表達(dá)式.取圖5所示曲線的u∈[1,2)計(jì)算該節(jié)點(diǎn)區(qū)間的基函數(shù)顯式方程,該節(jié)點(diǎn)區(qū)間的節(jié)點(diǎn)索引值i=4,根據(jù)NURBS局部支撐性,在該節(jié)點(diǎn)區(qū)間不為0的基函數(shù)為N1,3、N2,3、N3,3和N4,3.計(jì)算顯式方程所需參數(shù)節(jié)點(diǎn)值為ui-2=ui-1=0,ui=1,ui+1=2,ui+2=3,ui+3=4.

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

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

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

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

表13種算法的計(jì)算量對比

Table1Comparisonofarithmeticoperationamongthreealgorithms

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

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

4.2　加工實(shí)驗(yàn)及結(jié)果分析

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

圖7　加工實(shí)驗(yàn)Fig.7　Machining experiment

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

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

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

5結(jié)論

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

參考文獻(xiàn):

[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圖形激光雕刻算法及其嵌入式實(shí)現(xiàn) [J].華南理工大學(xué)學(xué)報(bào)(自然科學(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].計(jì)算機(jī)學(xué)報(bào),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的符號(hào)矩陣表示及其應(yīng)用 [J].計(jì)算機(jī)學(xué)報(bào),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 直接插補(bǔ)技術(shù)中快速求值求導(dǎo)算法 [J].東北大學(xué)學(xué)報(bào)(自然科學(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

中圖分類號(hào)：TP391

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

*基金項(xiàng)目：國家“863”計(jì)劃項(xiàng)目(2012AA040909)

收稿日期：2015-05-07

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

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