二次b樣條曲線插值方法

二次b樣條曲線插值方法

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