几何迭代法及其应用-几何迭代法综述

几何迭代法及其应用综述摘要:几何迭代法,又称渐进迭代逼近(progressive-iterativeapproximation,PIA),是一种具有明显几何意义的迭代方法.它通过不断调整曲线曲面的控制顶点,生成的极限曲线曲面插值(逼近)给定的数据点集.文中从理论和应用2个方面对几何迭代法进行了综述.在理论方面,介绍了插值型几何迭代法的迭代格式、收敛性证明、局部性质、加速方法,以及逼近型几何迭代法的迭代格式和收敛性证明等.进而,展示了几何迭代法在几个方面的成功应用,包括自适应数据拟合、大规模数据拟合、对称曲面拟合,以及插值给定位置﹑切矢量和曲率矢量的曲线迭代生成,有质量保证的四边网格和六面体网格生成,三变量B-spline体的生成等.关键词：渐进迭代逼近;几何迭代法;数据拟合;几何设计SurveyonGeometricIterativeMethodswithApplicationsAbstract:Geometriciterativemethod,alsocalledprogressive-iterativeapproximation(PIA),isaniterativeme-thodwithcleargeometricmeaning.Justbyadjustingthecontrolpointsofcurvesorsurfacesiteratively,thelimitcurveorsurfacewillinterpolate(approximate)thegivendatapointset.Inthispaper,weintroducethegeometriciterativemethodintwoaspects,i.e.,theoryandapplication.Intheory,wepresenttheiterativeformatsoftheinterpolatoryandapproximatinggeometriciterationmethods,respectively,showtheirconvergenceandlocalproperty,anddeveloptheacceleratingtechniques.Moreover,somesuccessfulapplicationsofthegeometricitera-tivemethodsaredemonstrated,includingadaptivedatafitting,largescaledatafitting,symmetricsurfacefitting,generationofthecurveinterpolatinggivenpositions,tangentvectors,andcurvaturevectors,generationofthequadrilateralandhexahedralmeshwithguaranteedquality,andgenerationofthetrivariateB-splinesolid,etc.Keywords:Progressive-IterativeApproximation;GeometricIterativeMethods;DataFitting;GeometricDesign几何迭代法是一种具有明显几何意义的迭代方法.从一条初始混合曲线开始,通过迭代调整它的控制顶点,就可以使这条曲线插值或逼近给定的数据点列.由于几何迭代法的迭代过程具有明显的几何意义,在迭代的每一步,可以很容易地加入各种几何约束条件,使得几何迭代法生成的极限曲线曲面满足这些约束.由于几何迭代法的这一性质,近年来,它在几何设计及相关领域得到了成功地应用,包括自适应数据拟合,大规模数据拟合,对称曲面拟合,插值给定位置、切矢量和曲率第4期583iiiiiii矢量的曲线迭代生成,有质量保证的四边网格和六面体网格生成,三变量B-spline体的生成等.几何迭代法肇始于1975年由齐东旭等学者提出的均匀3次B样条曲线的盈亏修正算法[1],1979年,deBoor也独立证明了这一算法的收敛性[2].2004年,Lin等证明了非均匀3次B样条曲线曲面这个过程迭代进行,产生了一个曲线序列{P(k)(t),k=0,1,2,⋯}.对于混合曲面(张量积曲面),也可以类似生成这样一个曲面序列[3-4].记(k)(k)(k)(k)T[1,2,n](1)的盈亏修正性质[3];2006年,又证明了所有全正基混合曲线曲面都具有这一性质,并创造了英文术语progressive-iterativeapproximation(PIA:渐进迭代逼近)来描述这一方法[4].在PIA算法中,每一个则式(1)矩阵形式[3-4]为(k1)(IC)(k);其中,I为单位矩阵,B0(t0)B1(t0)Bn(t0)数据点对应的参数值在迭代中是固定不变的.2007CB0(t1)B1(t1)Bn(t1)年,日本学者Maekawa等[5]将数据点的参数值取为每次迭代生成的拟合曲线曲面上最近点的参数B(t)B(t)B(t)值,并命名为geometricinterpolation(GI)[5-7].由于0n1nnnPIA和GI算法迭代步骤类似,都具有明显的几何意义,我们将这些具有明显几何意义的迭代法统称为几何迭代法.本文对几何迭代法的理论和应用进行了综述.为基函数的配置矩阵.文献[3]中证明了当混合曲线曲面的基函数是非均匀3次B样条基函数时,这个曲线曲面序列收敛到插值于给定点列的曲线曲面,即(k)limPk(ti)Qi,i0,1,n;1插值型几何迭代算法本节综述了几何设计中常用的几种曲线曲面的插值型几何迭代算法,包括全正基混合曲线曲面,NURBS曲线曲面,三角Bernstein-Bézier(B-B)曲线曲面,以及细分曲线曲面等;同时还介绍了几何迭代法的加速技术和局部性质.1.1全正基混合曲线曲面的插值型几何迭代算法给定一个点列{Qi,i=0,1,⋯,n},其中每一个点Qi赋予一个参数值ti,i=0,1,⋯,n,满足t0t1⋯tn.以这个点列为初始控制点列,构造一条初始混合n这称为混合曲线曲面的渐进迭代逼近(PIA)性质.进一步,文献[4]中证明了只要基函数是全正基函数,这个曲线曲面序列就有渐进迭代逼近性质.由于Bernstein基函数和B样条基函数都是全正基函数,因而Bézier曲线曲面、B样条曲线曲面都具有渐进迭代逼近性质.特别地,当混合曲线为周期均匀B样条曲线时,几何迭代的极限曲线表达式可以直接求出[8].另外,文献[9]给出了渐进迭代的拟合误差估计公式.给定不同的拟合精度以及不同的初始数据参数化,利用拟合误差估计公式可以预估迭代次数.1.2NURBS曲线曲面的插值型几何迭代算法我们首先构造NURBS曲线的几何迭代算法,曲线P(0)(t)P(0)B(t);这里,P(0)=Qi,Bi(t)为基iiii0函数,i=0,1,⋯,n.假设第k次迭代后生成的第k次曲线为nNURBS曲面的几何迭代算法可以类似构造.NURBS曲线在射影空间中的齐次形式为nR(t)RiBi(t);P(k)(t)i0P(k)B(t).i0其中,Ri=(wiPi,wi)=(wixi,wiyi,wizi,wi),i=0,1,⋯,n;为进行第k+1次迭代,首先计算差向量wi为权因子,Pi=(xi,yi,zi)为欧氏空间的一个点,Bi(t)(k)(k)(),i=QiPtii=0,1,⋯,n;为Bernstein基函数或B样条基函数.它在3D欧氏然后,将其加到曲线P(k)(t)的相应控制顶点上,即空间中对应一条有理曲线P(k1)P(k)(k),i=0,1,⋯,n;nwiPiBi(t)从而生成了第k+1次曲线nP(k1)(t)i0P(k1)B(t).P(t)i0.nwiBi(t)i0584第27卷iiiiiiiiiiiiiiiii,ijkijkijkijkiiiin给定齐次射影空间中一个点列{Q(wQ,limT(h)i,j,k=Q.wi)(wixi,wiyi,wizi,wi)},构造一条初始曲线hnnnijkR(0)(t)ni0R(0)B(t);在一般情况下,目前仅证明了4次和4次以下三角B-B曲面序列的收敛性[12].其中,R(0)=Q,i=0,1,n.在齐次形式下的几何1.4细分曲面的几何迭代算法本节中涉及的细分曲面为逼近型细分曲面,迭代格式与第1.1节一样.这样产生了一个齐次形式表示的曲线序列{R(k)(t),k=0，1}.它对应着3D欧氏空间中的一个有理曲线序列w(k)P(k)B(t)具体为Catmull-Clark,Doo-Sabin及Loop细分曲面.假设Q={Qi}为一个细分曲面的控制网格顶点集合,其中,Qi为网格顶点.每一个网格顶点Qi在细分极限曲面上都有一个极限位置Qi,,它可以表示为相P(k)(t)i0,i=0,1,应控制网格顶点的线性组合,例如ni0w(k)B(t)Qi,c1Qi,1c2Qi,2ckQi,k.和一个权函数序列nw(k)(t)i0w(k)B(t),iik=0,1.以给定的控制网格Q为初始控制网格P(0){P(0)},其中,(0)可以证明[10],上述2个序列都是收敛的,并且PiQi,可以生成一张初始细分曲面S.limP(k)(t)Q,i0,1,n;kii假设第k次迭代后生成的第k次细分曲面S(k)的控制网格为P(k)={Pk},它的每一个网格顶点limw(k)(t)w,i0,1,n.(k)(k)(k)kiiPi在细分曲面S上的极限位置为Pi,.构造差1.3三角B-B曲面的插值型几何迭代算法给定一个点列{Qijk,i,j,k,=0,1,n;ijk向量(k)QP(k),并将它加到第k次控制网格的顶点上,生成了第k+1次细分曲面S(k+1)的控制网n},其中每一个点Qijk对应参数值(ui,vj,wk).以格(k1)={(k+1)}(k+1)=(k)(k).PPi，PiPii这样,就产生这组点作为初始控制点,构造一张初始三角B-B曲面了一系列细分曲面序列{S(k),k=0,1,⋯}.当细分曲面为Doo-Sabin[13-14]或Loop[15-16]细分曲面时,T(0)(u,v,w)T(0)B(u)B(v)B(w);或当细分曲面为Catmull-Clark细分曲面[17],并且i,j,kijkijk它的控制网格中不存在度为3的顶点时,有其中,T(0)Q，0≤u,v,w≤uvw1.(k)ijkijklimPi,Qi.假设第h次迭代后生成了第h次三角B-B曲面kT(h)(u,v,w)T(h)B(u)B(v)B(w)；1.5插值型几何迭代算法的迭代速度和加速方法ijkijkijk如第1.1节所述,当混合曲线曲面的基函数是为生成第h+1次三角B-B曲面,计算(h)(h)(,,);全正基函数时,插值型几何迭代算法都收敛.由于B样条基函数和Bernstein基函数都是全正基函数,ijkQijkTuivjwk所以B样条曲线曲面和Bézier曲线曲面的插值型将其加到控制顶点(h)上,得到第h+1次三角B-B几何迭代格式都收敛.这两者之中,B样条曲线曲曲面的控制顶点(h1)(h)(h).这样,就生成面的迭代速度更快[18-19].了第h+1次三角B-B曲面(h1)(u,v,w).这个迭代过程产生了一个三角B-B曲面序列{Th(u,v,w),0≤u,v,w≤1,uvw1}.当数据点对应的参数值取均匀参数时,即ijk插值型几何迭代法的加速是通过在差向量(k)前面乘以一个权因子ω来实现的.这样,迭代格式变为P(k1)P(k)(k),i