二次b样条曲线插值方法

二次b样条曲线插值方法

1动态参数化方法插值是曲线曲线形状和逆向工程中基本而重要的技术。b样条是cagd中曲线曲线形状应用广泛的工具。插值b样条是指将一组数据点指定给一系列数据点，并构建b样条曲线以使序列位于这些数据点。对于指定的一组数据点和端点的限制，插值曲线的确定取决于数据点的参数化和节点向量的选择。在确定数量后，不同的数据点参数化方法和不同的节点向量导致不同形状的插值曲线。因此，要形成一个良好的形状（例如光顺）或b样条的预期形状，必须建立成本的参数化方法。在主要参数化方法中，等距参数化方法使数据点的参数值在参数间隔内均匀分布。输入钩子的参数化方法基于钩子的轮廓，因为钩子的长度类似于曲线的圆弧。参数化方法是基于钩子轮廓的概念。参数化方法是改进累积绳长参数的方法。采用foley参数化方法，充分考虑了绳长与相邻约束之间的角度。节点向量的选择通常符合参数化，但也存在不一致的情况。例如，在文献中，节点向量是通过上述参数化方法进行选择的，相应的b样条基函数最大值的参数值作为数据点的参数值。在这项工作中，我们希望参数化和节点向量的选择一致。以上提到的参数化方法主要是根据数据点的分布及其几何性质预先确定各数据点的参数值.但由于数据点的分布与插值曲线几何性质之间的关系十分复杂,还未得到很好的研究,所以这些参数化方法时常不能直观地控制B样条插值曲线的几何形状,难使插值曲线具预期的几何性质,导致在有些情况下,这些参数化方法失效,插值曲线形状完全失控.参数化为构造B样条插值曲线提供了自由度,但在以往的研究中,这些自由度并未得到充分利用.如何充分利用这些自由度构造出具有满意形状的B样条插值曲线是一个困难的问题.本文从相对简单的二次B样条曲线入手,基于插值曲线本身的几何性质来进行参数化,以使插值曲线具有预期的几何性质.不同于以往的参数化方法,本文的方法不是预先选定数据点的参数值,而是在构造插值曲线的过程中根据B样条插值曲线预期的几何约束条件,递推地确定各数据点的参数值,因此称之为动态参数化方法.实验结果表明,本文给出的参数化方法十分有效.本文的第2节给出二次B样条曲线的有关公式;第3节分别以曲线在各数据点处的切向和曲线各段的相对高度作为插值曲线的几何约束条件,用动态参数化构造相应的二次B样条插值曲线,并给出相应的算法;第4节给出本文方法的应用例子;第5节小结本文的结果.2节点向量ttn二次B样条曲线表示如下:其中,d0,d1,…,dn为曲线的控制顶点,Ni,2(t)为二次规范B样条基函数,由节点向量T={t0,t1,…,tn+3}确定,t0≤t1≤…≤tn+3.当t0=t1=t2,tn+1=tn+2=tn+3时,相应的二次B样条曲线为端点插值的,即c(t2)=d0,c(tn+1)=dn.本文讨论C1连续的二次B样条曲线,为此下面总是设节点向量T在[t2,tn+1]中无重节点,即t2<t3<…<tn+1.根据k次B样条基函数的deBoor-Cox公式,规定和式(1)直接推算得,二次B样条曲线c(t)在节点ti和参数值处的位置向量可分别表示为其中,;c(t)的一阶导向量(切向量)可表示为ti≤t<ti+1,i=2,3,…,n(4)c(t)在节点ti处的一阶导向量可表示为3动态参数化构造顺序给定平面上n个互异的数据点p1,p2,…,pn,本节将利用动态参数化方法构造顺序通过这些数据点且满足一定的几何约束条件的二次B样条插值曲线.3.1次b样条插值曲线设已知数据点pi处的单位切向量vi,i=1,2,…,n.若不能直接获得vi,可根据数据点预先计算预期的vi,相关的计算方法见文献.记αi为vi到向量pi+1-pi的有向夹角,θi为vi到vi+1的有向夹角,i=1,2,…,n-1(如图1).定义1.设u,v为向量,u到v的有向夹角记作〈u,v〉.当u和v方向相反时,〈u,v〉=π;否则,〈u,v〉指从u的正向到v的正向的角度绝对值<π的夹角,夹角的符号取逆时针方向为正,顺时针方向为负.下面要构造如式(1)表示的二次B样条插值曲线c(t),使得根据B样条曲线的性质和式(2)、式(5),在区间[ti,ti+1]上c(t)为两端分别切于控制多边形的边di-1-di-2和di-di-1且包含在三角形Δdi-2di-1di中的凸曲线段.因此,为了保证满足式(6)、式(7)的二次B样条插值曲线c(t)存在,对单位切向量vi作如下限定是合理的:构造在各数据点具指定切向的二次B样条插值曲线的方法由下面定理1给出.定理1.给定平面上n个互异的数据点p1,p2,…,pn以及n个满足式(8)的单位切向量v1,v2,…,vn,取控制顶点序列d0,d1,…,dn如下:其中,li为过点pi以vi为方向的直线,取节点向量T如下:其中,为满足c1<c2的任意实数,则二次B样条曲线c(t)=diNi,2(t)为满足式(6)、式(7)条件的插值曲线.证明.要构造满足式(6)和式(7)的二次B样条插值曲线c(t),由式(1),(2)和式(5)知,只要确定控制顶点序列d0,d1,…,dn和节点向量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),本定理得证.证毕.根据定理1构造的二次B样条插值曲线c(t)为端点插值的.若要构造非端点插值的满足式(6)和式(7)的二次B样条插值曲线,只要将式(9)改为d0=d1+a(p1-d1),dn=dn-1+b(pn-dn-1),其中,a,b为>1的任意实数,di(i=1,2,…,n-1)如式(9)确定,将式(10)改为其中,βi与式(10)中的相同.算法1.根据算法1构造的二次B样条插值曲线具有局部性质,即改变某个数据点的位置时,相应的插值曲线的形状只作局部改变.定理2.对于平面上n个互异的数据点p1,p2,…,pn以及n个满足式(8)的单位切向量v1,v2,…,vn,设c1(t)是根据算法1构造的相应的二次B样条插值曲线.对于某个整数j,1≤j≤n,改变数据点pj的位置得新的数据点可作改变或不变,其余的数据点及切向保持不变,设c2(t)是根据算法1构造的相应的二次B样条插值曲线,则当1<j<n时,c1(t)和c2(t)除了第j-1,j段外形状完全一致;当j=1时,c1(t)和c2(t)除了第1段外形状完全一致;当j=n时,c1(t)和c2(t)除了第n-1段外形状完全一致.证明.由于对于任意一条二次B样条曲线c(t)=diNi,2(t),其第i段的形状完全由该段的两个端点以及控制顶点di确定,而由定理1知根据算法1构造的插值曲线c1(t)和c2(t)除了第j-1,j段(当j=1时除了第1段,当j=n时除了第n-1段)外,各段的两个端点以及控制顶点di对应相同,所以本定理成立.证毕.3.2次b样条插值曲线的估计设二次B样条曲线c(t)插值数据点p1,p2,…,pn,即c(t)满足式(6),用rh(i)表示c(t)第i段的相对高度,即i=1,2,…,n-1(13)其中,为过数据点pi,pi+1的直线,dist指距离.引理1.给定数据点p1,p2,…,pn,设控制顶点为d0,d1,…,dn节点向量为T的二次B样条插值曲线c(t)满足式(6),则c(t)第i段的相对高度rh(i)有如下表示式:其中,Δi为三角形Δdi-1pipi+1的面积.证明.设,显然,dist当且仅当c(t)在处的切向平行于弦pi+1-pi,即由式(2)和式(6)可得pi+1-pi=(1-ai+1)(di-di-1)+ai+2(di+1-di),其中,.于是由上式和式(4)知,式(15)等价于可见当时,式(15)成立,从而由式(13)得,i=1,2,…,n-1(16)由于dist,而且利用式(2),(3)和式(6)可推得因此,(pi+1-pi)|,将上式代入式(16)得式(14),本引理得证.证毕.下面定理3给出构造各段具指定相对高度的二次B样条插值曲线的方法.定理3.给定平面上n个互异的数据点p1,p2,…,pn,n-1个正实数h1,h2,…,hn-1和不平行于向量p2-p1的单位向量v1,取节点向量T和控制顶点序列d0,d1,…,dn如下:其中,c1,c2为满足c1<c2的任意实数,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,当Δ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)知,当Δi≠0时,rh(i)=hi,i=2,3,…,n-1,而由引理1证明中的式(16)和式(17)可得本定理得证.证毕.由于当Δi=0时,总有rh(i)=0,所以若所给定的hi>0,则按定理3确定的B样条插值曲线c(t)在第i段不满足rh(i)=hi,但能保证所取的di位于以pi和pi+1为两端点的线段上,使得曲线c(t)保持C1连续.算法2.当所指定的各段相对高度充分小时,根据算法2构造的二次B样条插值曲线具有近似局部性质,即由改变某个数据点的位置而引起的相应插值曲线形状的改变在该数据点的一定范围外逐渐减弱.该近似局部性质由下面定理4给出.定理4.对于平面上n个互异的数据点p1,p2,…,pn,n-1个正实数h1,h2,…,hn-1和不平行于向量p2-p1的单位向量v1,设c1(t)=diNi,2(t)是根据算法2构造的相应的二次B样条插值曲线.对于某个整数j,1≤j≤n,改变数据点pj的位置得新的数据点,其余的数据点保持不变,设c2(t)=是根据算法2构造的相应的二次B样条插值曲线.若i=j+1,j+2,…,n-1(20)其中,ε为某个给定的正实数,Δ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)的节点向量,证明.由定理3的式(18)知从而对于i=1,2,…,j-2,c1(t)和c2(t)在第i段上的两端点以及中间的控制顶点对应相同,由此知c1(t)和c2(t)在第i段上形状完全一致.对于i=j+1,j+2,…,n-1,若,则根据式(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,可通过插入节点和参数变换分别将c1(t)和c2(t)的第i段化为二次Bézier曲线段和:u∈[0,1),t∈[ti+1,ti+2),,其中,为二次Bernstein基函数.于是有,其中t与满足式(23),从而式(22)得证.证毕.4基于动态参数化构造二次b样条插值曲线例1.取如下n=11个数据点: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),用各种参数化方法(参数化与节点向量的选取相一致)构造二次B样条插值曲线,结果见图2.其中,用等距参数化、累加弦长参数化、向心参数化和Foley参数化方法构造插值曲线时端点条件均取为规定两端的切线.图2(a)～(e)取一致的端点条件.图2表明,在构造二次B样条插值曲线过程中,本文提出的动态参数化方法比起等距参数化、累加弦长参数化、向心参数化和Foley参数化等传统的参数化方法来,能更直观有效地控制插值曲线的形状,使之达到预期的要求.由图2(a)～(d)可知,当由数据点确定的多边形拐点较多时,传统的参数化方法易使插值曲线的形状失控.而由于给定各数据点处的切向就完全确定了控制多边形,所以按算法1构造的二次B样条插值曲线的基本形状可预期.由图2(e)和(f)可看出,插值曲线的形状完全被所指定的数据点处的切向所控制.用算法2可构造逼近由数据点确定的多边形的插值曲线(见图2(g)),也可利用各段的相对高度构造具预期形状的插值曲线,这种情况下采用交互形式选取各段的相对高度更为有效(见图2(h)).例2.取n=11个与例1相同的数据点.改变某个数据点的位置,其余数据点不变.用算法1和算法2分别构造二次B样条插值曲线,比较改变数据点位置前后的插值曲线,结果如图3和图4.图3表明用算法1构造的二次B样条插值曲线的局部性质与定理2的结果相符.图4表明用算法2构造的二次B样条插值曲线具有近似局部性质,实际的结果显得比由定理4给出的理论结果更好.设改变数据点pj的位置,则从图4可看出,改变数据点前后的两条插值曲线除了第j-1和j两段外,在其余各段的形状完全一致或几乎一致.5动态参数化和节点向量的选取(1)本文给出的二次B样条曲线插值方法充分利用了参数化的自由度,直接利用插值曲线直观的几何约束条件如曲线在数据点处的切向、曲线段的相对高度等而不仅仅是数据点分布的几何性