二次b樣條曲線插值方法

二次b樣條曲線插值方法

1動(dòng)態(tài)參數(shù)化方法插值是曲線曲線形狀和逆向工程中基本而重要的技術(shù)。b樣條是cagd中曲線曲線形狀應(yīng)用廣泛的工具。插值b樣條是指將一組數(shù)據(jù)點(diǎn)指定給一系列數(shù)據(jù)點(diǎn)，并構(gòu)建b樣條曲線以使序列位于這些數(shù)據(jù)點(diǎn)。對(duì)于指定的一組數(shù)據(jù)點(diǎn)和端點(diǎn)的限制，插值曲線的確定取決于數(shù)據(jù)點(diǎn)的參數(shù)化和節(jié)點(diǎn)向量的選擇。在確定數(shù)量后，不同的數(shù)據(jù)點(diǎn)參數(shù)化方法和不同的節(jié)點(diǎn)向量導(dǎo)致不同形狀的插值曲線。因此，要形成一個(gè)良好的形狀（例如光順）或b樣條的預(yù)期形狀，必須建立成本的參數(shù)化方法。在主要參數(shù)化方法中，等距參數(shù)化方法使數(shù)據(jù)點(diǎn)的參數(shù)值在參數(shù)間隔內(nèi)均勻分布。輸入鉤子的參數(shù)化方法基于鉤子的輪廓，因?yàn)殂^子的長(zhǎng)度類似于曲線的圓弧。參數(shù)化方法是基于鉤子輪廓的概念。參數(shù)化方法是改進(jìn)累積繩長(zhǎng)參數(shù)的方法。采用foley參數(shù)化方法，充分考慮了繩長(zhǎng)與相鄰約束之間的角度。節(jié)點(diǎn)向量的選擇通常符合參數(shù)化，但也存在不一致的情況。例如，在文獻(xiàn)中，節(jié)點(diǎn)向量是通過(guò)上述參數(shù)化方法進(jìn)行選擇的，相應(yīng)的b樣條基函數(shù)最大值的參數(shù)值作為數(shù)據(jù)點(diǎn)的參數(shù)值。在這項(xiàng)工作中，我們希望參數(shù)化和節(jié)點(diǎn)向量的選擇一致。以上提到的參數(shù)化方法主要是根據(jù)數(shù)據(jù)點(diǎn)的分布及其幾何性質(zhì)預(yù)先確定各數(shù)據(jù)點(diǎn)的參數(shù)值.但由于數(shù)據(jù)點(diǎn)的分布與插值曲線幾何性質(zhì)之間的關(guān)系十分復(fù)雜,還未得到很好的研究,所以這些參數(shù)化方法時(shí)常不能直觀地控制B樣條插值曲線的幾何形狀,難使插值曲線具預(yù)期的幾何性質(zhì),導(dǎo)致在有些情況下,這些參數(shù)化方法失效,插值曲線形狀完全失控.參數(shù)化為構(gòu)造B樣條插值曲線提供了自由度,但在以往的研究中,這些自由度并未得到充分利用.如何充分利用這些自由度構(gòu)造出具有滿意形狀的B樣條插值曲線是一個(gè)困難的問(wèn)題.本文從相對(duì)簡(jiǎn)單的二次B樣條曲線入手,基于插值曲線本身的幾何性質(zhì)來(lái)進(jìn)行參數(shù)化,以使插值曲線具有預(yù)期的幾何性質(zhì).不同于以往的參數(shù)化方法,本文的方法不是預(yù)先選定數(shù)據(jù)點(diǎn)的參數(shù)值,而是在構(gòu)造插值曲線的過(guò)程中根據(jù)B樣條插值曲線預(yù)期的幾何約束條件,遞推地確定各數(shù)據(jù)點(diǎn)的參數(shù)值,因此稱之為動(dòng)態(tài)參數(shù)化方法.實(shí)驗(yàn)結(jié)果表明,本文給出的參數(shù)化方法十分有效.本文的第2節(jié)給出二次B樣條曲線的有關(guān)公式;第3節(jié)分別以曲線在各數(shù)據(jù)點(diǎn)處的切向和曲線各段的相對(duì)高度作為插值曲線的幾何約束條件,用動(dòng)態(tài)參數(shù)化構(gòu)造相應(yīng)的二次B樣條插值曲線,并給出相應(yīng)的算法;第4節(jié)給出本文方法的應(yīng)用例子;第5節(jié)小結(jié)本文的結(jié)果.2節(jié)點(diǎn)向量ttn二次B樣條曲線表示如下:其中,d0,d1,…,dn為曲線的控制頂點(diǎn),Ni,2(t)為二次規(guī)范B樣條基函數(shù),由節(jié)點(diǎn)向量T={t0,t1,…,tn+3}確定,t0≤t1≤…≤tn+3.當(dāng)t0=t1=t2,tn+1=tn+2=tn+3時(shí),相應(yīng)的二次B樣條曲線為端點(diǎn)插值的,即c(t2)=d0,c(tn+1)=dn.本文討論C1連續(xù)的二次B樣條曲線,為此下面總是設(shè)節(jié)點(diǎn)向量T在[t2,tn+1]中無(wú)重節(jié)點(diǎn),即t2<t3<…<tn+1.根據(jù)k次B樣條基函數(shù)的deBoor-Cox公式,規(guī)定和式(1)直接推算得,二次B樣條曲線c(t)在節(jié)點(diǎn)ti和參數(shù)值處的位置向量可分別表示為其中,;c(t)的一階導(dǎo)向量(切向量)可表示為ti≤t<ti+1,i=2,3,…,n(4)c(t)在節(jié)點(diǎn)ti處的一階導(dǎo)向量可表示為3動(dòng)態(tài)參數(shù)化構(gòu)造順序給定平面上n個(gè)互異的數(shù)據(jù)點(diǎn)p1,p2,…,pn,本節(jié)將利用動(dòng)態(tài)參數(shù)化方法構(gòu)造順序通過(guò)這些數(shù)據(jù)點(diǎn)且滿足一定的幾何約束條件的二次B樣條插值曲線.3.1次b樣條插值曲線設(shè)已知數(shù)據(jù)點(diǎn)pi處的單位切向量vi,i=1,2,…,n.若不能直接獲得vi,可根據(jù)數(shù)據(jù)點(diǎn)預(yù)先計(jì)算預(yù)期的vi,相關(guān)的計(jì)算方法見(jiàn)文獻(xiàn).記αi為vi到向量pi+1-pi的有向夾角,θi為vi到vi+1的有向夾角,i=1,2,…,n-1(如圖1).定義1.設(shè)u,v為向量,u到v的有向夾角記作〈u,v〉.當(dāng)u和v方向相反時(shí),〈u,v〉=π;否則,〈u,v〉指從u的正向到v的正向的角度絕對(duì)值<π的夾角,夾角的符號(hào)取逆時(shí)針?lè)较驗(yàn)檎?順時(shí)針?lè)较驗(yàn)樨?fù).下面要構(gòu)造如式(1)表示的二次B樣條插值曲線c(t),使得根據(jù)B樣條曲線的性質(zhì)和式(2)、式(5),在區(qū)間[ti,ti+1]上c(t)為兩端分別切于控制多邊形的邊di-1-di-2和di-di-1且包含在三角形Δdi-2di-1di中的凸曲線段.因此,為了保證滿足式(6)、式(7)的二次B樣條插值曲線c(t)存在,對(duì)單位切向量vi作如下限定是合理的:構(gòu)造在各數(shù)據(jù)點(diǎn)具指定切向的二次B樣條插值曲線的方法由下面定理1給出.定理1.給定平面上n個(gè)互異的數(shù)據(jù)點(diǎn)p1,p2,…,pn以及n個(gè)滿足式(8)的單位切向量v1,v2,…,vn,取控制頂點(diǎn)序列d0,d1,…,dn如下:其中,li為過(guò)點(diǎn)pi以vi為方向的直線,取節(jié)點(diǎn)向量T如下:其中,為滿足c1<c2的任意實(shí)數(shù),則二次B樣條曲線c(t)=diNi,2(t)為滿足式(6)、式(7)條件的插值曲線.證明.要構(gòu)造滿足式(6)和式(7)的二次B樣條插值曲線c(t),由式(1),(2)和式(5)知,只要確定控制頂點(diǎn)序列d0,d1,…,dn和節(jié)點(diǎn)向量T使得下列條件成立:pi=(1-ai+1)di-1+ai+1di,i=1,2,…,n(11)di-di-1與vi同向,i=1,2,…,n(12)其中.顯然,按式(9)確定的d0,d1,…,dn滿足條件式(12),而且使pi位于以di-1和di為兩端點(diǎn)的線段上,i=1,2,…,n.由此不難驗(yàn)證,按式(9)和式(10)確定的d0,d1,…,dn和T滿足條件式(11),本定理得證.證畢.根據(jù)定理1構(gòu)造的二次B樣條插值曲線c(t)為端點(diǎn)插值的.若要構(gòu)造非端點(diǎn)插值的滿足式(6)和式(7)的二次B樣條插值曲線,只要將式(9)改為d0=d1+a(p1-d1),dn=dn-1+b(pn-dn-1),其中,a,b為>1的任意實(shí)數(shù),di(i=1,2,…,n-1)如式(9)確定,將式(10)改為其中,βi與式(10)中的相同.算法1.根據(jù)算法1構(gòu)造的二次B樣條插值曲線具有局部性質(zhì),即改變某個(gè)數(shù)據(jù)點(diǎn)的位置時(shí),相應(yīng)的插值曲線的形狀只作局部改變.定理2.對(duì)于平面上n個(gè)互異的數(shù)據(jù)點(diǎn)p1,p2,…,pn以及n個(gè)滿足式(8)的單位切向量v1,v2,…,vn,設(shè)c1(t)是根據(jù)算法1構(gòu)造的相應(yīng)的二次B樣條插值曲線.對(duì)于某個(gè)整數(shù)j,1≤j≤n,改變數(shù)據(jù)點(diǎn)pj的位置得新的數(shù)據(jù)點(diǎn)可作改變或不變,其余的數(shù)據(jù)點(diǎn)及切向保持不變,設(shè)c2(t)是根據(jù)算法1構(gòu)造的相應(yīng)的二次B樣條插值曲線,則當(dāng)1<j<n時(shí),c1(t)和c2(t)除了第j-1,j段外形狀完全一致;當(dāng)j=1時(shí),c1(t)和c2(t)除了第1段外形狀完全一致;當(dāng)j=n時(shí),c1(t)和c2(t)除了第n-1段外形狀完全一致.證明.由于對(duì)于任意一條二次B樣條曲線c(t)=diNi,2(t),其第i段的形狀完全由該段的兩個(gè)端點(diǎn)以及控制頂點(diǎn)di確定,而由定理1知根據(jù)算法1構(gòu)造的插值曲線c1(t)和c2(t)除了第j-1,j段(當(dāng)j=1時(shí)除了第1段,當(dāng)j=n時(shí)除了第n-1段)外,各段的兩個(gè)端點(diǎn)以及控制頂點(diǎn)di對(duì)應(yīng)相同,所以本定理成立.證畢.3.2次b樣條插值曲線的估計(jì)設(shè)二次B樣條曲線c(t)插值數(shù)據(jù)點(diǎn)p1,p2,…,pn,即c(t)滿足式(6),用rh(i)表示c(t)第i段的相對(duì)高度,即i=1,2,…,n-1(13)其中,為過(guò)數(shù)據(jù)點(diǎn)pi,pi+1的直線,dist指距離.引理1.給定數(shù)據(jù)點(diǎn)p1,p2,…,pn,設(shè)控制頂點(diǎn)為d0,d1,…,dn節(jié)點(diǎn)向量為T(mén)的二次B樣條插值曲線c(t)滿足式(6),則c(t)第i段的相對(duì)高度rh(i)有如下表示式:其中,Δi為三角形Δdi-1pipi+1的面積.證明.設(shè),顯然,dist當(dāng)且僅當(dāng)c(t)在處的切向平行于弦pi+1-pi,即由式(2)和式(6)可得pi+1-pi=(1-ai+1)(di-di-1)+ai+2(di+1-di),其中,.于是由上式和式(4)知,式(15)等價(jià)于可見(jiàn)當(dāng)時(shí),式(15)成立,從而由式(13)得,i=1,2,…,n-1(16)由于dist,而且利用式(2),(3)和式(6)可推得因此,(pi+1-pi)|,將上式代入式(16)得式(14),本引理得證.證畢.下面定理3給出構(gòu)造各段具指定相對(duì)高度的二次B樣條插值曲線的方法.定理3.給定平面上n個(gè)互異的數(shù)據(jù)點(diǎn)p1,p2,…,pn,n-1個(gè)正實(shí)數(shù)h1,h2,…,hn-1和不平行于向量p2-p1的單位向量v1,取節(jié)點(diǎn)向量T和控制頂點(diǎn)序列d0,d1,…,dn如下:其中,c1,c2為滿足c1<c2的任意實(shí)數(shù),a=2h1|p2-p1|2/|v1×(p2-p1)|,Δi-1為三角形Δdi-2pi-1pi的面積,則二次B樣條曲線c(t)=diNi,2(t)滿足插值條件(6),在端點(diǎn)p1處的切向?yàn)関1而且對(duì)于i=1,2,…,n-1,當(dāng)Δi≠0時(shí),第i段的相對(duì)高度rh(i)=hi.證明.由式(18)知c(t)為端點(diǎn)插值的,所以c(t2)=d0=p1,c(tn+1)=dn=pn.另一方面,對(duì)于i=3,4,…,n有,從而pi-1=(1-ai)di-2+aidi-1,其中,ai與式(2)中的相同,于是由式(2)知c(t)滿足插值條件(式(6)).而利用式(5)有,即c(t)在端點(diǎn)p1處的切向?yàn)関1.最后,由引理1和式(18)和式(19)知,當(dāng)Δi≠0時(shí),rh(i)=hi,i=2,3,…,n-1,而由引理1證明中的式(16)和式(17)可得本定理得證.證畢.由于當(dāng)Δi=0時(shí),總有rh(i)=0,所以若所給定的hi>0,則按定理3確定的B樣條插值曲線c(t)在第i段不滿足rh(i)=hi,但能保證所取的di位于以pi和pi+1為兩端點(diǎn)的線段上,使得曲線c(t)保持C1連續(xù).算法2.當(dāng)所指定的各段相對(duì)高度充分小時(shí),根據(jù)算法2構(gòu)造的二次B樣條插值曲線具有近似局部性質(zhì),即由改變某個(gè)數(shù)據(jù)點(diǎn)的位置而引起的相應(yīng)插值曲線形狀的改變?cè)谠摂?shù)據(jù)點(diǎn)的一定范圍外逐漸減弱.該近似局部性質(zhì)由下面定理4給出.定理4.對(duì)于平面上n個(gè)互異的數(shù)據(jù)點(diǎn)p1,p2,…,pn,n-1個(gè)正實(shí)數(shù)h1,h2,…,hn-1和不平行于向量p2-p1的單位向量v1,設(shè)c1(t)=diNi,2(t)是根據(jù)算法2構(gòu)造的相應(yīng)的二次B樣條插值曲線.對(duì)于某個(gè)整數(shù)j,1≤j≤n,改變數(shù)據(jù)點(diǎn)pj的位置得新的數(shù)據(jù)點(diǎn),其余的數(shù)據(jù)點(diǎn)保持不變,設(shè)c2(t)=是根據(jù)算法2構(gòu)造的相應(yīng)的二次B樣條插值曲線.若i=j+1,j+2,…,n-1(20)其中,ε為某個(gè)給定的正實(shí)數(shù),Δi和i分別為三角形Δdi-1pipi+1和的面積,則對(duì)于i=1,2,…,j-2,c1(t)和c2(t)在第i段上形狀完全一致,而對(duì)于i=j+1,j+2,…,n-1,其中,,而且c1(t)和c2(t)在第i段上滿足:其中,和分別是插值曲線c1(t)和c2(t)的節(jié)點(diǎn)向量,證明.由定理3的式(18)知從而對(duì)于i=1,2,…,j-2,c1(t)和c2(t)在第i段上的兩端點(diǎn)以及中間的控制頂點(diǎn)對(duì)應(yīng)相同,由此知c1(t)和c2(t)在第i段上形狀完全一致.對(duì)于i=j+1,j+2,…,n-1,若,則根據(jù)式(19),對(duì)于c1(t),γi+1=|pi+1-pi|2hi/Δi,對(duì)于,于是,顯然,,從而有而由式(18)得于是,若式(20)成立,則利用式(19)和式(24)得所以,對(duì)于i=j+1,j+2,…,n-1,式(21)成立.最后,對(duì)于任意的i,j+1≤i≤n-1,可通過(guò)插入節(jié)點(diǎn)和參數(shù)變換分別將c1(t)和c2(t)的第i段化為二次Bézier曲線段和:u∈[0,1),t∈[ti+1,ti+2),,其中,為二次Bernstein基函數(shù).于是有,其中t與滿足式(23),從而式(22)得證.證畢.4基于動(dòng)態(tài)參數(shù)化構(gòu)造二次b樣條插值曲線例1.取如下n=11個(gè)數(shù)據(jù)點(diǎn):p1=(40,170),p2=(51,196),p3=(81,213),p4=(88,193),p5=(92,196),p6=(96,211),p7=(116,191),p8=(107,178),p9=(110,169),p10=(130,165),p11=(138,192),用各種參數(shù)化方法(參數(shù)化與節(jié)點(diǎn)向量的選取相一致)構(gòu)造二次B樣條插值曲線,結(jié)果見(jiàn)圖2.其中,用等距參數(shù)化、累加弦長(zhǎng)參數(shù)化、向心參數(shù)化和Foley參數(shù)化方法構(gòu)造插值曲線時(shí)端點(diǎn)條件均取為規(guī)定兩端的切線.圖2(a)～(e)取一致的端點(diǎn)條件.圖2表明,在構(gòu)造二次B樣條插值曲線過(guò)程中,本文提出的動(dòng)態(tài)參數(shù)化方法比起等距參數(shù)化、累加弦長(zhǎng)參數(shù)化、向心參數(shù)化和Foley參數(shù)化等傳統(tǒng)的參數(shù)化方法來(lái),能更直觀有效地控制插值曲線的形狀,使之達(dá)到預(yù)期的要求.由圖2(a)～(d)可知,當(dāng)由數(shù)據(jù)點(diǎn)確定的多邊形拐點(diǎn)較多時(shí),傳統(tǒng)的參數(shù)化方法易使插值曲線的形狀失控.而由于給定各數(shù)據(jù)點(diǎn)處的切向就完全確定了控制多邊形,所以按算法1構(gòu)造的二次B樣條插值曲線的基本形狀可預(yù)期.由圖2(e)和(f)可看出,插值曲線的形狀完全被所指定的數(shù)據(jù)點(diǎn)處的切向所控制.用算法2可構(gòu)造逼近由數(shù)據(jù)點(diǎn)確定的多邊形的插值曲線(見(jiàn)圖2(g)),也可利用各段的相對(duì)高度構(gòu)造具預(yù)期形狀的插值曲線,這種情況下采用交互形式選取各段的相對(duì)高度更為有效(見(jiàn)圖2(h)).例2.取n=11個(gè)與例1相同的數(shù)據(jù)點(diǎn).改變某個(gè)數(shù)據(jù)點(diǎn)的位置,其余數(shù)據(jù)點(diǎn)不變.用算法1和算法2分別構(gòu)造二次B樣條插值曲線,比較改變數(shù)據(jù)點(diǎn)位置前后的插值曲線,結(jié)果如圖3和圖4.圖3表明用算法1構(gòu)造的二次B樣條插值曲線的局部性質(zhì)與定理2的結(jié)果相符.圖4表明用算法2構(gòu)造的二次B樣條插值曲線具有近似局部性質(zhì),實(shí)際的結(jié)果顯得比由定理4給出的理論結(jié)果更好.設(shè)改變數(shù)據(jù)點(diǎn)pj的位置,則從圖4可看出,改變數(shù)據(jù)點(diǎn)前后的兩條插值曲線除了第j-1和j兩段外,在其余各段的形狀完全一致或幾乎一致.5動(dòng)態(tài)參數(shù)化和節(jié)點(diǎn)向量的選取(1)本文給出的二次B樣條曲線插值方法充分利用了參數(shù)化的自由度,直接利用插值曲線直觀的幾何約束條件如曲線在數(shù)據(jù)點(diǎn)處的切向、曲線段的相對(duì)高度等而不僅僅是數(shù)據(jù)點(diǎn)分布的幾何性