一种插值与逼近运动物体活动标架的新方法

11一种插值与逼近运动物体活动标架的新方法姜忠鼎1马利庄1,21(浙江大学CAD&CG国家重点实验室杭州310027)2(CentreforAdvancedMediaTechnologyNanyangTechnologicalUniversity639798Singapore)Email:{zdjiang,mlz}@cad.zju.edu.cn摘要插值运动物体给定活动标架（原点位置和三个坐标轴朝向）是计算机图形学、机器人等领域的一个重要问题.本文提出一种采用B样条曲线插值与逼近运动物体活动标架的新方法.采用4个欧拉参数对正交活动标架的旋转变换矩阵进行参数化,得到了一个简单的优化方程.采用迭代法求解该优化方程来逼近运动轨迹任意处伪活动标架的旋转变换矩阵.本文也证明了插值和逼近所引起的误差是可控的.由于活动标架的计算只涉及2阶或3阶线性方程组,该方法具有很高的运行效率.关键词运动设计,插值与逼近,活动标架,B样条中图法分类号TP391在计算机图形学、机器人等领域,人们通常设定运动物体的若干关键位置},...2,1,,,;{mizyxOiiii即一组物体所在的局部坐标向量,对这些关键位置进行适当的插值或逼近,以确定运动坐标系的一般位置,进而可确定物体的一般位置.物体的朝向一般可用欧拉角来表示,因此朝向的插值问题可简单地转化为3个欧拉角的插值问题.但欧拉角又有它的局限性.因旋转矩阵是不可交换的,欧拉角的旋转一定要按某个特定的次序进行；等量的欧拉角变化不一定引起等量的旋转变化,导致了旋转的不均匀性；欧拉角还有可能导致自由度的丧失,即所谓的gimblelock现象.Shoemake为解决因采用欧拉角表示引起的麻烦,最早将四元数引入计算机动画领域,并提出用单位四元数空间上的Bezier样条来插值四元数[1].Barr等人提出了一个采用四元数对带有角速度约束的景物的朝向进行光滑插值方法,他们的方法允许对轨迹端点处的角速度进行约束.首先把关键帧处的旋转角转化为四元数,然后把非欧几里德空间四元数路径的切向加速度取极小,并用有限差分和最优化方法求解得到的能量方程[2].Kim通过构造一组新的基,提出了把R3空间曲线变换到单位四元数的一般性方法[3].在CAD/CAM、机器人等领域常要求插值方法必须保证所得运动坐标系既是单位正交,又为NURBS曲线表示形式.最近这一问题引起学者们的广泛兴趣.Roschel于1998年对运动物体的有理运动表示方法作了综述[4].许多商用机器人控制系统采用分段线性或分段园弧插值方式.它简单实用,但也存在明显缺点,如物体的运动在连接处很不自然[5].为此Wang和Yang引入了一种近似弧长参数化的5次样条曲线[6]；Farouki和shah则引入了一种所谓的PH曲线[7]；但这两种方法中曲线活动标架的表达式并非真正的NURBS表示形式.为使活动标架具有精确的NURBS表示形式,Ge和Ravani引入了刚体运动群SE（3）的单位四元数表示方法[8],本质是将R3中正交变换表示成四元数,然后将给定运动位置的插值问题转化为四元数的插值问题.此后又有作者发展了相应四元数插值方法[9,10].采用四元数,活动标架最终可表示成NURBS形式,但表示形式仍复杂.例如,若利用k次NURBS曲线对局部坐标原点路径采用四元数方法插值,则最终的活动标架为k2次NURBS形式.为降低表示次数,*本文研究得到国家自然科学基金(No.69973043)和杰出青年科学基金(No.69625304)资助.作者姜忠鼎,男，1975年生，博士生,主要研究领域为计算图形学与科学计算可视化.马利庄,男，1963年生，研究员，博士生导师,主要研究领域为计算机辅助几何设计与科学计算可视化。2提高计算效率,有必要对此作进一步研究,以满足CAD虚拟环境中快速计算的需要.此外,仍缺乏一个好的误差估计公式,而这又是实际应用中必需的.本文提出了一种用B样条曲线统一插值和逼近活动标架坐标原点和三个坐标轴朝向的新方法.该方法并不精确计算物体在运动时所对应的正交活动标架,而是先得到一个伪活动标架,然后求得最佳逼近该伪活动标架的正交活动标架.同时我们还证明了逼近误差是可控的.采用了逐步求精的迭代技术,可根据需要得到更精确的正交活动标架.迭代求解计算只涉及2阶或3阶线性方程组,该方法具有很高的运行效率.本文内容安排如下.第1节对活动标架插值问题进行了描述并给出我们用B样条曲线统一插值活动标架原点和三个坐标轴朝向的方法；第2节证明了活动标架的逼近误差是可控的；第3节给出逼近伪活动标架的方法和该算法的一个运行实例；最后是本文的结论.1插值运动物体活动标架令R3表示三维欧几里德空间.采用Cartesian坐标架},,;{zyxO和},,;{zyxO来分别表示固定标架'和活动标架.固定标架'中的点表示为),,(zyxP,活动标架中的点表示为Pxyz(,,).设',,,...,iin01为活动标架通过变换（1.1）得到的n1个相关位置.PADPPiii)((1.1)其中Dabciiiit'(,,)为平移向量,Aexeyeziiii(,,)为33正交矩阵.插值问题可以描述为寻找一参数运动满足PtAtDPtP)()(),((1.2)物体运动可分为平移变换)(tD和旋转变换At()两部分.平移变换部分可通过对数据点iD采用普通B样条插值方法来得到[11].],[,)()(10,nkniikitttDtNtD(1.3)其中Ntik,()为第i个k次B样条基函数,},...,,{110knttt)1,...,1,0,(1knittii为严格递增的节点矢量.对活动标架插值的传统方法中,应用较广的手段是对每一个分量分别进行插值,然后根据单位正交化要求进行相应处理,但它有明显缺点[4].为克服该缺点,对给定的活动标架niezeyexDiiii,...,1,0},,,;{,采用k次B样条曲线)(),(),(),(tezteytextD来分别逼近平移变换部分Di'和三个正交向量exeyeziii,,.这四条曲线定义在同一节点矢量Ttttnk{,,...,}011上.即niikinikiiiiDtNtDtNezeyextezteytextA0,0,)()()(),,())(),(),(()((1.4)但)}(),(),();({tezteytextD通常并不形成精确的正交活动标架.我们首先证明它形成一个伪活动标架,然后提出一种方法来计算最佳逼近该伪活动标架的正交活动标架.2逼近误差控制公式3我们采用奇次B样条曲线来考虑活动标架插值问题.设Ft()为一给定的1k次连续可微曲线,曲线Ct()在参数01,,...,n处插值曲线Ft().令km12,考虑完全样条插值问题：knitttttttttniFCimiknnmnmmknnnkkii,...,2,1,..................,...,1,0),()(1001110(2.1)对连续函数Ft(),定义|)(|max)(],[tFtFbat.对该样条插值问题,有以下结论成立.结论1.设XCtYCtZCt(),(),()和XFtYFtZFt(),(),()分别表示曲线Ct()和Ft()的zyx,,三个分量部分,||max||1iii.存在一正常数constk和常数cons,(,)tkMm对任意k1次连续可微曲线Ft(),有111),(,||conscons)()(kkkmMkkdtXFdtttXFtXC(2.2)其中jmjimijimM,max),(.)()(tYFtYC及)()(tZFtZC也存在类似不等式.证明：由奇次样条插值的理论知,存在一常数cons,(,)tkMm满足),dist(||cons)()(,),(,TmmmmmMkSdtXFdttXFtXC其中dist(,),dXFdtSmmmT表示SmT,中的光滑函数到该曲线的距离.SmT,为定义在节点矢量T上的m阶（1m次）样条空间.对于m次连续可微函数dXFdtmm,存在一正常数constk满足dist(,)cons||,dXFdtStTdXFdtmmmTkmmm22,其中||||max||1iiittT.则结论1得证.由方程(2.2)可知,当||趋向于0时,原始曲线与插值样条曲线之间的误差以1k阶的速度也趋向于0.从应用角度出发,以上结论可另表述为结论2.结论2设一给定活动标架)}(*),(*),(*);(*{:*tezteytextD在时间域上1k次连续可微,iiiiiDexeyez:{;,,}为时间tini,,,...,01处相应的采样值.设:{();(),(),()}Dtexteytezt为*的k次完全样条插值结果,则存在一个仅依赖k和*的正常数M满足1111||)(*)(||)(*)(||)(*)(||)(*)(kkkkMteztezMteyteyMtextexMtDtD(2.3)4上述方程可简记为()*()||ttMk1.在采样时间间隔充分小,连续标架'i和'i1相当接近,则对于一给定的任意小正数0,存在一个0,当||时,即||,,,...,iiin101,利用结论2,有()*()tt成立.对于仿射活动标架:{();(),(),()}Dtexteytezt,它可以不必是正交的.对于任意小正数0,有MMexexMMeyex2|)1|(||2||2222(2.4)可得到关于zy,分量的类似不等式.由以上结论可知,:{();(),(),()}Dtexteytezt近似为一正交活动标架,我们称它为伪活动标架.3正交活动标架逼近伪活动标架令SOR()3表示欧几里德空间R3中的旋转群,C为SOR()3中的正交矩阵.可采用四个不同时为零的欧拉参数cccc0123,,,对C进行参数化.23222120103220311032232221203021203130212322212023222120)(2)(2)(2)(2)(2)(21ccccccccccccccccccccccccccccccccccccccccC(3.1)不失一般性可假设00c,dcciii0123,,,,这时矩阵C只含321,,ddd三个独立变量,简化为2322211322311322322213212313212322212322211)(2)(2)(21)(2)(2)(2111ddddddddddddddddddddddddddddddC(3.2)对于一给定的伪活动标架,设B为代表其三个坐标轴朝向的非正交矩阵,Bbbbbbbbbbbij11121321222331323333()目标是寻找一正交矩阵C满足)(,minimum3RSOCBC(3.3)其中为矩阵的平方范数.令traceBbbb112233,它表示矩阵B对角线元素之和.利用相关公式易求得下式成立.ttttraceBBBCCBtraceBCBCtraceBCdddF)(-3))((),,(2321(3.4)5方程(3.3)的优化问题转化为寻找合适的ddd123,,使F最小,即ddd123,,应满足下面的方程.0321dFdFdF(3.5)利用矩阵技术,方程(3.5)可表示为如下形式,0]111[1312321tBdddddddCdtrace