为什么使用四元数

为什么使用四元数

为了回答这个问题，先来看看一般关于旋转（面向）的描述方法－欧拉描述法。它使用最简单的x,y,z值来分别表示在x，y，z轴上的旋转角度，其取值为0-360(或者0-2pi），一般使用roll，pitch，yaw来表示这些分量的旋转值。需要注意的是，这里的旋转是针对世界坐标系说的，这意味着第一次的旋转不会影响第二、三次的转轴，简单的说，三角度系统无法表现任意轴的旋转，只要一开始旋转，物体本身就失去了任意轴的自主性，这也就导致了万向轴锁（GimbalLock）的问题。还有一种是轴角的描述方法（即我一直以为的四元数的表示法），这种方法比欧拉描述要好，它避免了GimbalLock，它使用一个3维向量表示转轴和一个角度分量表示绕此转轴的旋转角度，即(x,y,z,angle)，一般表示为(x,y,z,w)或者(v,w)。但这种描述法却不适合插值。那到底什么是GimbalLock呢？正如前面所说，因为欧拉描述中针对x,y,z的旋转描述是世界坐标系下的值，所以当任意一轴旋转90°的时候会导致该轴同其他轴重合，此时旋转被重合的轴可能没有任何效果，这就是GimbalLock，这里有个例子演示了GimbalLock，点击这里下载。运行这个例子，使用左右箭头改变yaw为90°，此时不管是使用上下箭头还是Insert、PageUp键都无法改变Pitch，而都是改变了模型的roll。那么轴、角的描述方法又有什么问题呢？虽然轴、角的描述解决了GimbalLock，但这样的描述方法会导致差值不平滑，差值结果可能跳跃，欧拉描述同样有这样的问题。什么是四元数四元数一般定义如下：q=w+xi+yj+zk其中w是实数，x,y,z是虚数，其中:i*i=-1j*j=-1k*k=-1也可以表示为：q=[w,v]其中v=(x,y,z)是矢量，w是标量，虽然v是矢量，但不能简单的理解为3D空间的矢量，它是4维空间中的的矢量，也是非常不容易想像的。四元数也是可以归一化的，并且只有单位化的四元数才用来描述旋转（面向），四元数的单位化与Vector类似，首先||q||=Norm(q)=sqrt(w2+x2+y2+z2)因为w2+x2+y2+z2=1所以Normlize(q)=q/Norm(q)=q/sqrt(w2+x2+y2+z2)说了这么多，那么四元数与旋转到底有什么关系？我以前一直认为轴、角的描述就是四元数，如果是那样其与旋转的关系也不言而喻，但并不是这么简单，轴、角描述到四元数的转化：w=cos(theta/2)x=ax*sin(theta/2)y=ay*sin(theta/2)z=az*sin(theta/2)其中(ax,ay,az)表示轴的矢量，theta表示绕此轴的旋转角度，为什么是这样？和轴、角描述到底有什么不同？这是因为轴角描述的“四元组”并不是一个空间下的东西，首先（ax,ay,az）是一个3维坐标下的矢量，而theta则是级坐标下的角度，简单的将他们组合到一起并不能保证他们插值结果的稳定性，因为他们无法归一化，所以不能保证最终插值后得到的矢量长度（经过旋转变换后两点之间的距离）相等，而四元数在是在一个统一的4维空间中，方便归一化来插值，又能方便的得到轴、角这样用于3D图像的信息数据，所以用四元数再合适不过了。关于四元数的运算法则和推导这里有篇详细的文章介绍，重要的是一点，类似与Matrix的四元数的乘法是不可交换的，四元数的乘法的意义也类似于Matrix的乘法－可以将两个旋转合并，例如：Q=Q1*Q2表示Q的是先做Q2的旋转，再做Q1的旋转的结果，而多个四元数的旋转也是可以合并的，根据四元数乘法的定义，可以算出两个四元数做一次乘法需要16次乘法和加法，而3x3的矩阵则需要27运算，所以当有多次旋转操作时，使用四元数可以获得更高的计算效率。为什么四元数可以避免GimbalLock在欧拉描述中，之所以会产生GimbalLock是因为使用的三角度系统是依次、顺序变换的，如果在OGL中，代码可能这样：glRotatef(angleX,1,0,0)glRotatef(angleY,0,1,0)glRotatef(angleZ,0,0,1)注意：以上代码是顺序执行，而使用的又是统一的世界坐标，这样当首先旋转了Y轴后，Z轴将不再是原来的Z轴，而可能变成X轴，这样针对Z的变化可能失效。而四元数描述的旋转代码可能是这样：TempQ=FromEula(x,y,z)FinalQ=CameraQ*NewQtheta,ax,ay,az=From(FinalQ)glRotatef(theta,ax,ay,az);其中(ax,ay,az)描述一条任意轴，theta描述了绕此任意轴旋转的角度，而所有的参数都来自于所有描述旋转的四元数做乘法之后得到的值，可以看出这样一次性的旋转不会带来问题。这里有个例子演示了使用四元数不会产生GimbalLock的问题。关于插值使用四元数的原因就是在于它非常适合插值，这是因为他是一个可以规格化的4维向量，最简单的插值算法就是线性插值，公式如：q(t)=(1-t)q1+tq2但这个结果是需要规格化的，否则q(t)的单位长度会发生变化，所以q(t)=(1-t)q1+tq2/||(1-t)q1+tq2||如图:尽管线性插值很有效，但不能以恒定的速率描述q1到q2之间的曲线，这也是其弊端，我们需要找到一种插值方法使得q1->q(t)之间的夹角θ是线性的，即θ(t)=(1-t)θ1+t*θ2，这样我们得到了球形线性插值函数q(t)，如下：q(t)=q1*sinθ(1-t)/sinθ+q2*sinθt/sineθ如果使用D3D，可以直接使用D3DXQuaternionSlerp函数就可以完成这个插值过程。第二篇:四元数入门四元数常常可以在3D的书上看到。但我的那本3D图形学书上，在没讲四元数是干什么的之前，就列了几张纸的公式，大概因为自己还在上高中，不知道的太多，看了半天没看懂。。。终于，在gameres上看到了某强人翻译的一个“4元数宝典”（原文是日本人写的。。。），感觉很好，分享下。★旋转篇：我将说明使用了四元数（siyuanshu,quaternion）的旋转的操作步骤（１）四元数的虚部，实部和写法所谓四元数，就是把4个实数组合起来的东西。4个元素中，一个是实部，其余3个是虚部。比如，叫做Q的四元数，实部t而虚部是x,y,z构成，则像下面这样写。Q=(t;x,y,z)又，使用向量V=(x,y,z)，Q=(t;V)也可以这么写。正规地用虚数单位i,j,k的写法的话，Q=t+xi+yj+zk也这样写，不过，我不大使用（２）四元数之间的乘法虚数单位之间的乘法ii=-1,ij=-ji=k(其他的组合也是循环地以下同文)有这么一种规则。（我总觉得，这就像是向量积（外积），对吧）用这个规则一点点地计算很麻烦，所以请用像下面这样的公式计算。A=(a;U)B=(b;V)AB=(ab-U?V;aV+bU+U×V)不过，“U?V”是内积，「U×V」是外积的意思。注意：一般AB<>BA所以乘法的左右要注意！（3）3次元的坐标的四元数表示如要将某坐标(x,y,z)用四元数表示，P=(0;x,y,z)则要这么写。另外，即使实部是零以外的值，下文的结果也一样。用零的话省事所以我推荐。（４）旋转的四元数表示以原点为旋转中心，旋转的轴是(α,β,γ)（但α^2+β^2+γ^2=1），（右手系的坐标定义的话，望向向量(α,β,γ)的前进方向反时针地）转θ角的旋转，用四元数表示就是，Q=(cos(θ/2);αsin(θ/2),βsin(θ/2),γsin(θ/2))R=(cos(θ/2);-αsin(θ/2),-βsin(θ/2),-γsin(θ/2))(另外R叫Q的共轭四元数。）那么，如要实行旋转，则RPQ=(0;答案)请像这样三明治式地计算。这个值的虚部就是旋转之后的点的坐标值。（另外，实部应该为零。请验算看看）例子代码///Quaternion.cpp///©ToruNakata,toru-nakata@aist.go.jp///2004Dec29#include<math.h>#include<iostream.h>///DefineDatatypetypedefstruct{doublet;//real-componentdoublex;//x-componentdoubley;//y-componentdoublez;//z-component}quaternion;////Bill注：Kakezan在日语里是“乘法”的意思quaternionKakezan(quaternionleft,quaternionright){quaternionans;doubled1,d2,d3,d4;d1=left.t*right.t;d2=-left.x*right.x;d3=-left.y*right.y;d4=-left.z*right.z;ans.t=d1+d2+d3+d4;d1=left.t*right.x;d2=right.t*left.x;d3=left.y*right.z;d4=-left.z*right.y;ans.x=d1+d2+d3+d4;d1=left.t*right.y;d2=right.t*left.y;d3=left.z*right.x;d4=-left.x*right.z;ans.y=d1+d2+d3+d4;d1=left.t*right.z;d2=right.t*left.z;d3=left.x*right.y;d4=-left.y*right.x;ans.z=d1+d2+d3+d4;returnans;}////MakeRotationalquaternionquaternionMakeRotationalQuaternion(doubleradian,doubleAxisX,doubleAxisY,doubleAxisZ){quaternionans;doublenorm;doubleccc,sss;ans.t=ans.x=ans.y=ans.z=0.0;norm=AxisX*AxisX+AxisY*AxisY+AxisZAxisZ;if(norm<=0.0)returnans;norm=1.0/sqrt(norm);AxisX=norm;AxisY=norm;AxisZ=norm;ccc=cos(0.5*radian);sss=sin(0.5*radian);ans.t=ccc;ans.x=sss*AxisX;ans.y=sss*AxisY;ans.z=sssAxisZ;returnans;}////PutXYZintoquaternionquaternionPutXYZToQuaternion(doublePosX,doublePosY,doublePosZ){quaternionans;ans.t=0.0;ans.x=PosX;ans.y=PosY;ans.z=PosZ;returnans;}/////mainintmain(){doublepx,py,pz;doubleax,ay,az,th;quaternionppp,qqq,rrr;cout<<“PointPosition(x,y,z)”<<endl;cout<<“x=”;cin>>px;cout<<“y=”;cin>>py;cout<<“z=”;cin>>pz;ppp=PutXYZToQuaternion(px,py,pz);while(1){cout<<“\nRotationDegree?(Enter0toQuit)”<<endl;cout<<“angle=”;cin>>th;if(th==0.0)break;cout<<“RotationAxisDirection?(x,y,z)”<<endl;cout<<“x=”;cin>>ax;cout<<“y=”;cin>>ay;cout<<“z=”;cin>>az;th=3.^{1415926535897932384626433832795}⁄₁₈₀.0;///Degree->radian;qqq=MakeRotationalQuaternion(th,ax,ay,az);rrr=MakeRotationalQuaternion(-th,ax,ay,az);ppp=Kakezan(rrr,ppp);ppp=Kakezan(ppp,qqq);cout<<“\nAnserX=”<<ppp.x<<“\nY=”<<ppp.y<<“\nZ=”<<ppp.z<<endl;}return0;}又一篇在以前涉及的程序中，处理物体的旋转通常是用的矩阵的形式。由于硬件在纹理映射和光栅化上的加强，程序员可以将更多的CPU周期用于物理模拟等工作，这样将使得程序更为逼真。一，原文出处：http://www.gamasutra.com/features/19980703/quaternions_01.htm二，摘录：有三种办法表示旋转：矩阵表示，欧拉角表示，以及四元组表示。矩阵，欧拉角表示法在处理插值的时候会遇到麻烦。Therearemanywaystorepresenttheorientationofanobject.Mostprogrammersuse3x3rotationmatricesorthreeEuleranglestostorethisinformation.Eachofthesesolutionsworksfineuntilyoutrytosmoothlyinterpolatebetweentwoorientationsofanobject.矩阵表示法不适合于进行插值(在转动的前后两个朝向之间取得瞬时朝向)。矩阵有9个自由度（3×3矩阵），而实际上表示一个旋转只需要3个自由度（旋转轴3）。Rotationsinvolveonlythreedegreesoffreedom(DOF),aroundthex,y,andzcoordinateaxes.However,nineDOF(assuming3x3matrices)arerequiredtoconstraintherotation-clearlymorethanweneed.Anothershortcomingofrotationmatricesisthattheyareextremelyhardtouseforinterpolatingrotationsbetweentwoorientations.Theresultinginterpolationsarealsovisuallyveryjerky,whichsimplyisnotacceptableingamesanymore.欧拉角表示法Youcanalsouseanglestorepresentrotationsaroundthreecoordinateaxes.Youcanwritethisas(q,c,f);simplystated,"Transformapointbyrotatingitcounterclockwiseaboutthezaxisbyqdegrees,followedbyarotationabouttheyaxisbycdegrees,followedbyarotationaboutthexaxisbyfdegrees."欧拉角表示法的缺陷：把一个旋转变成了一系列的旋转。并且，进行插值计算也不方便。However,thereisnoeasywaytorepresentasinglerotationwithEuleranglesthatcorrespondstoaseriesofconcatenatedrotations.Furthermore,thesmoothinterpolationbetweentwoorientationsinvolvesnumericalintegration目录[隐藏]?1四元组表示法?2四元组的基本运算法则?3用四元组进行旋转的公式?4旋转叠加性质[编辑]四元组表示法[w,v]其中v是矢量，表示旋转轴。w标量，表示旋转角度。所以，一个四元组即表示一个完整的旋转。Thereareseveralnotationsthatwecanusetorepresentquaternions.Thetwomostpopularnotationsarecomplexnumbernotation(Eq.1)and4Dvectornotation(Eq.2).w+xi+yj+zk(wherei2=j2=k2=-1andij=k=-jiwithrealw,x,y,z)(Eq.1)[w,v](wherev=(x,y,z)iscalleda"vector"andwiscalleda"scalar")(Eq.2)4D空间以及单元四元组：Eachquaternioncanbeplottedin4Dspace(sinceeachquaternioniscomprisedoffourparts),andthisspaceiscalledquaternionspace.Unitquaternionshavethepropertythattheirmagnitudeisoneandtheyformasubspace,S3,ofthequaternionspace.Thissubspacecanberepresentedasa4Dsphere.(thosethathaveaone-unitnormal),sincethisreducesthenumberofnecessaryoperationsthatyouhavetoperform.[编辑]四元组的基本运算法则Table1.Basicoperationsusingquaternions.Addition:q+q′=[w+w′,v+v′]Multiplication:qq′=[ww′-v?v′,vxv′+wv′+w′v](?isvectordotproductandxisvectorcrossproduct);Note:qq′?q′q//为什么是这样？－－定义成这样滴，木有道理可以讲Conjugate:q*=[w,-v]共轭Norm:N(q)=w2+x2+y2+z2模Inverse:q-1=q*/N(q)UnitQuaternion:qisaunitquaternionifN(q)=1andthenq-1=q*Identity:[1,(0,0,0)](wheninvolvingmultiplication)and[0,(0,0,0)](wheninvolvingaddition)[编辑]用四元组进行旋转的公式重要!!!!：只有单元四元组才表示旋转。为什么????－－已解决（shoemake有详细证明）Itisextremelyimportanttonotethatonlyunitquaternionsrepresentrotations,andyoucanassumethatwhenItalkaboutquaternions,I'mtalkingaboutunitquaternionsunlessotherwisespecified.Sinceyou'vejustseenhowothermethodsrepresentrotations,let'sseehowwecanspecifyrotationsusingquaternions.Itcanbeproven(andtheproofisn'tthathard)thattherotationofavectorvbyaunitquaternionqcanberepresentedasv′=qvq-1(wherev=[0,v])(Eq.3)////////////////////////////////////////////////////////////四元组和旋转参数的变换一个四元组由(x,y,z,w)四个变量表达,假设给定一个旋转轴axis和角度angle,那么这个四元组的计算公式为:voidQuaternion::fromAxisAngle(constVector3&axis,Realangle){Vector3u=axis;u.normalize();Reals=Math::rSin(angle/2.f);x=s*u.x;y=s*u.y;z=s*u.z;w=Math::rCos(angle/2.f);}由四元组反算回旋转轴axis和角度angle的公式为:/voidQuaternion::toAxisAngle(Vector3&axis,Real&angle)const{angle=acos(w)*2axis.x=xaxis.y=yaxis.z=z}英文版:RotatingObjectsUsingQuaternionsLastyearmaygodowninhistoryasTheYearoftheHardwareAcceleration.Muchoftheworkrasterizingandtexture-mappingpolygonswasoff-loadedtodedicatedhardware.Asaresult,wegamedevelopersnowhavealotofCPUcyclestospareforphysicssimulationandotherfeatures.Someofthoseextracyclescanbeappliedtotaskssuchassmoothingrotationsandanimations,thankstoquaternions.Manygameprogrammershavealreadydiscoveredthewonderfulworldofquaternionsandhavestartedtousethemextensively.Severalthird-persongames,includingbothTOMBRAIDERtitles,usequaternionrotationstoanimatealloftheircameramovements.Everythird-persongamehasavirtualcameraplacedatsomedistancebehindortothesideoftheplayer'scharacter.Becausethiscameragoesthroughdifferentmotions(thatis,througharcsofadifferentlengths)thanthecharacter,cameramotioncanappearunnaturalandtoo"jerky"fortheplayertofollowtheaction.Thisisoneareawherequaternionscometorescue.Anothercommonuseforquaternionsisinmilitaryandcommercialflightsimulators.Insteadofmanipulatingaplane'sorientationusingthreeangles(roll,pitch,andyaw)representingrotationsaboutthex,y,andzaxes,respectively,itismuchsimplertouseasinglequaternion.Manygamescomingoutthisyearwillalsofeaturereal-worldphysics,allowingamazinggameplayandimmersion.Ifyoustoreorientationsasquaternions,itiscomputationallylessexpensivetoaddangularvelocitiestoquaternionsthantomatrices.BothTombRaidertitlesusequaternionrotationstoanimatecameramovements.Therearemanywaystorepresenttheorientationofanobject.Mostprogrammersuse3x3rotationmatricesorthreeEuleranglestostorethisinformation.Eachofthesesolutionsworksfineuntilyoutrytosmoothlyinterpolatebetweentwoorientationsofanobject.Imagineanobjectthatisnotusercontrolled,butwhichsimplyrotatesfreelyinspace(forexample,arevolvingdoor).Ifyouchosetostorethedoor'sorientationsasrotationmatricesorEulerangles,you'dfindthatsmoothlyinterpolatingbetweentherotationmatrices'valueswouldbecomputationallycostlyandcertainlywouldn'tappearassmoothtoaplayer'seyeasquaternioninterpolation.TryingtocorrectthisproblemusingmatricesorEulerangles,ananimatormightsimplyincreasethenumberofpredefined(keyed)orientations.However,onecanneverbesurehowmanysuchorientationsareenough,sincethegamesrunatdifferentframeratesondifferentcomputers,therebyaffectingthesmoothnessoftherotation.Thisisagoodtimetousequaternions,amethodthatrequiresonlytwoorthreeorientationstorepresentasimplerotationofanobject,suchasourrevolvingdoor.Youcanalsodynamicallyadjustthenumberofinterpolatedpositionstocorrespondtoaparticularframerate.Beforewebeginwithquaterniontheoryandapplications,let'slookathowrotationscanberepresented.I'lltouchuponmethodssuchasrotationmatrices,Eulerangles,andaxisandanglerepresentationsandexplaintheirshortcomingsandtheirrelationshipstoquaternions.Ifyouarenotfamiliarwithsomeofthesetechniques,Irecommendpickingupagraphicsbookandstudyingthem.Todate,Ihaven'tseenasingle3Dgraphicsbookthatdoesn'ttalkaboutrotationsusing4x4or3x3matrices.Therefore,IwillassumethatmostgameprogrammersareveryfamiliarwiththistechniqueandI'lljustcommentonitsshortcomings.Ialsohighlyrecommendthatyoure-readChrisHecker'sarticleintheJune1997issueoftheGameDeveloper("Physics,Part4:TheThirdDimension,"pp.15-26),sinceittacklestheproblemoforienting3Dobjects.Rotationsinvolveonlythreedegreesoffreedom(DOF),aroundthex,y,andzcoordinateaxes.However,nineDOF(assuming3x3matrices)arerequiredtoconstraintherotation-clearlymorethanweneed.Additionally,matricesareproneto"drifting,"asituationthatariseswhenoneofthesixconstraintsisviolatedandthematrixintroducesrotationsaroundanarbitraryaxis.Combattingthisproblemrequireskeepingamatrixorthonormalized-makingsurethatitobeysconstraints.However,doingsoisnotcomputationallycheap.AcommonwayofsolvingmatrixdriftreliesontheGram-Schmidtalgorithmforconversionofanarbitrarybasisintoanorthogonalbasis.UsingtheGram-SchmidtalgorithmorcalculatingacorrectionmatrixtosolvematrixdriftingcantakealotofCPUcycles,andithastobedoneveryoften,evenwhenusingfloatingpointmath.Anothershortcomingofrotationmatricesisthattheyareextremelyhardtouseforinterpolatingrotationsbetweentwoorientations.Theresultinginterpolationsarealsovisuallyveryjerky,whichsimplyisnotacceptableingamesanymore.Youcanalsouseanglestorepresentrotationsaroundthreecoordinateaxes.Youcanwritethisas(q,c,f);simplystated,"Transformapointbyrotatingitcounterclockwiseaboutthezaxisbyqdegrees,followedbyarotationabouttheyaxisbycdegrees,followedbyarotationaboutthexaxisbyfdegrees."Thereare12differentconventionsthatyoucanusetorepresentrotationsusingEulerangles,sinceyoucanuseanycombinationofaxestorepresentrotations(XYZ,XYX,XYY…).Wewillassumethefirstconvention(XYZ)forallofthepresentedexamples.Iwillassumethatallofthepositiverotationsarecounterclockwise(Figure1).EuleranglerepresentationisveryefficientbecauseitusesonlythreevariablestorepresentthreeDOF.Euleranglesalsodon'thavetoobeyanyconstraints,sothey'renotpronetodriftinganddon'thavetobereadjusted.However,thereisnoeasywaytorepresentasinglerotationwithEuleranglesthatcorrespondstoaseriesofconcatenatedrotations.Furthermore,thesmoothinterpolationbetweentwoorientationsinvolvesnumericalintegration,whichcanbecomputationallyexpensive.Euleranglesalsointroducetheproblemof"Gimballock"oralossofonedegreeofrotationalfreedom.Gimballockhappenswhenaseriesofrotationsat90degreesisperformed;suddenly,therotationdoesn'toccurduetothealignmentoftheaxes.Figure1:Euleranglerepresentation.Forexample,imaginethataseriesofrotationstobeperformedbyaflightsimulator.YouspecifythefirstrotationtobeQ1aroundthexaxis,thesecondrotationtobe90degreesaroundtheyaxis,andQ3tobetherotationaroundthezaxis.Ifyouperformspecifiedrotationsinsuccession,youwilldiscoverthatQ3rotationaroundthezaxishasthesameeffectastherotationaroundtheinitialxaxis.Theyaxisrotationhascausedthexandzaxestogetaligned,andyouhavejustlostaDOFbecauserotationaroundoneaxisisequivalenttooppositerotationaroundtheotheraxis.IhighlyrecommendAdvancedAnimationandRenderingTechniques:TheoryandPracticebyAlanandMarkWatt(AddisonWesley,1992)foradetaileddiscussionoftheGimballockproblem.Usinganaxisandanglerepresentationisanotherwayofrepresentingrotations.Youspecifyanarbitraryaxisandanangle(positiveifinacounterclockwisedirection),asillustratedinFigure2.Eventhoughthisisanefficientwayofrepresentingarotation,itsuffersfromthesameproblemsthatIdescribedforEuleranglerepresentation(withtheexceptionoftheGimballockproblem).Intheeighteenthcentury,W.R.Hamiltondevisedquaternionsasafour-dimensionalextensiontocomplexnumbers.Soonafterthis,itwasproventhatquaternionscouldalsorepresentrotationsandorientationsinthreedimensions.Thereareseveralnotationsthatwecanusetorepresentquaternions.Thetwomostpopularnotationsarecomplexnumbernotation(Eq.1)and4Dvectornotation(Eq.2).w+xi+yj+zk(wherei2=j2=k2=-1andij=k=-jiwithrealw,x,y,z)(Eq.1)[w,v](wherev=(x,y,z)iscalleda"vector"andwiscalleda"scalar")(Eq.2)Iwillusethesecondnotationthroughoutthisarticle.Nowthatyouknowhowquaternionsarerepresented,let'sstartwithsomebasicoperationsthatusethem.Ifqandq′aretwoorientationsrepresentedasquaternions,youcandefinetheoperationsinTable1onthesequaternions.Allotheroperationscanbeeasilyderivedfromthesebasicones,andtheyarefullydocumentedintheaccompanyinglibrary,whichyoucanfindhere.Iwillalsoonlydealwithunitquaternions.Eachquaternioncanbeplottedin4Dspace(sinceeachquaternioniscomprisedoffourparts),andthisspaceiscalledquaternionspace.Unitquaternionshavethepropertythattheirmagnitudeisoneandtheyformasubspace,S3,ofthequaternionspace.Thissubspacecanberepresentedasa4Dsphere.(thosethathaveaone-unitnormal),sincethisreducesthenumberofnecessaryoperationsthatyouhavetoperform.Itisextremelyimportanttonotethatonlyunitquaternionsrepresentrotations,andyoucanassumethatwhenItalkaboutquaternions,I'mtalkingaboutunitquaternionsunlessotherwisespecified.Sinceyou'vejustseenhowothermethodsrepresentrotations,let'sseehowwecanspecifyrotationsusingquaternions.Itcanbeproven(andtheproofisn'tthathard)thattherotationofavectorvbyaunitquaternionqcanberepresentedasv′=qvq-1(wherev=[0,v])(Eq.3)Theresult,arotatedvectorv′,willalwayshavea0scalarvalueforw(recallEq.2earlier),soyoucanomititfromyourcomputations.Table1.Basicoperationsusingquaternions.Addition:q+q′=[w+w′,v+v′]Multiplication:qq′=[ww′-v?v′,vxv′+wv′+w′v](?isvectordotproductandxisvectorcrossproduct);Note:qq′?q′qConjugate:q*=[w,-v]Norm:N(q)=w2+x2+y2+z2Inverse:q-1=q*/N(q)UnitQuaternion:qisaunitquaternionifN(q)=1andthenq-1=q*Identity:[1,(0,0,0)](wheninvolvingmultiplication)and[0,(0,0,0)](wheninvolvingaddition)Today'smostwidelysupportedAPIs,Direct3Dimmediatemode(retainedmodedoeshavealimitedsetofquaternionrotations)andOpenGL,donotsupportquaternionsdirectly.Asaresult,youhavetoconvertquaternionorientationsinordertopassthisinformationtoyourfavoriteAPI.BothOpenGLandDirect3Dgiveyouwaystospecifyrotationsasmatrices,soaquaternion-to-matrixconversionroutineisuseful.Also,ifyouwanttoimportsceneinformationfromagraphicspackagethatdoesn'tstoreitsrotationsasaseriesofquaternions(suchasNewTek'sLightWave),youneedawaytoconverttoandfromquaternionspace.ANGLEANDAXIS.Convertingfromangleandaxisnotationtoquaternionnotationinvolvestwotrigonometricoperations,aswellasseveralmultipliesanddivisions.Itcanberepresentedasq=[cos(Q/2),sin(Q/2)v](whereQisanangleandvisanaxis)(Eq.4)EULERANGLES.ConvertingEuleranglesintoquaternionsisasimilarprocess-youjusthavetobecarefulthatyouperformtheoperationsinthecorrectorder.Forexample,let'ssaythataplaneinaflightsimulatorfirstperformsayaw,thenapitch,andfinallyaroll.Youcanrepresentthiscombinedquaternionrotationasq=qyawqpitchqrollwhere:qroll=[cos(y/2),(sin(y/2),0,0)]qpitch=[cos(q/2),(0,sin(q/2),0)]qyaw=[cos(f/2),(0,0,sin(f/2)](Eq.5)Theorderinwhichyouperformthemultiplicationsisimportant.Quaternionmultiplicationisnotcommutative(duetothevectorcrossproductthat'sinvolved).Inotherwords,changingtheorderinwhichyourotateanobjectaroundvariousaxescanproducedifferentresultingorientations,andtherefore,theorderisimportant.ROTATIONMATRIX.Convertingfromarotationmatrixtoaquaternionrepresentationisabitmoreinvolved,anditsimplementationcanbeseeninListing1.Conversionbetweenaunitquaternionandarotationmatrixcanbespecifiedas|1-2y2-2z22yz+2wx2xz-2wy|Rm=|2xy-2wz1-2x2-2z22yz-2wx||2xz+2wy2yz-2wx1-2x2-2y2|(Eq.6)It'sverydifficulttospecifyarotationdirectlyusingquaternions.It'sbesttostoreyourcharacter'sorobject'sorientationasaEulerangleandconvertittoquaternionsbeforeyoustartinterpolating.It'smucheasiertoincrementrotationaroundanangle,aftergettingtheuser'sinput,usingEulerangles(thatis,roll=roll+1),thantodirectlyrecalculateaquaternion.SinceconvertingbetweenquaternionsandrotationmatricesandEuleranglesisperformedoften,it'simportanttooptimizetheconversionprocess.Veryfastconversion(involvingonlyninemuls)betweenaunitquaternionandamatrixispresentedinListing2.Pleasenotethatthecodeassumesthatamatrixisinaright-handcoordinatesystemandthatmatrixrotationisrepresentedinacolumnmajorformat(forexample,OpenGLcompatible).

Listing1:Matrixtoquaternioncode.MatToQuat(floatm[4][4],QUAT*quat){floattr,s,q[4];inti,j,k;intnxt[3]={1,2,0};tr=m[0][0]+m[1][1]+m[2][2];//checkthediagonalif(tr>0.0){s=sqrt(tr+1.0);quat->w=s/2.0;s=0.5/s;quat->x=(m[1][2]-m[2][1])*s;quat->y=(m[2][0]-m[0][2])*s;quat->z=(m[0][1]-m[1][0])*s;}else{//diagonalisnegativei=0;if(m[1][1]>m[0][0])i=1;if(m[2][2]>m[i][i])i=2;j=nxt[i];k=nxt[j];s=sqrt((m[i][i]-(m[j][j]+m[k][k]))+1.0);q[i]=s*0.5;if(s!=0.0)s=0.5/s;q[3]=(m[j][k]-m[k][j])*s;q[j]=(m[i][j]+m[j][i])*s;q[k]=(m[i][k]+m[k][i])*s;quat->x=q[0];quat->y=q[1];quat->z=q[2];quat->w=q[3];}}Ifyouaren‘tdealingwithunitquaternions,additionalmultiplicationsandadivisionarerequired.EulerangletoquaternionconversioncanbecodedasshowninListing3.Oneofthemostusefulaspectsofquaternionsthatwegameprogrammersareconcernedwithisthefactthatit’seasytointerpolatebetweentwoquaternionorientationsandachievesmoothanimation.Todemonstratewhythisisso,let‘slookatanexampleusingsphericalrotations.Sphericalquaternioninterpolationsfollowtheshortestpath(arc)onafour-dimensional,unitquaternionsphere.Since4Dspheresaredifficulttoimagine,I’llusea3Dsphere(Figure3)tohelpyouvisualizequaternionrotationsandinterpolations.Let‘sassumethattheinitialorientationofavectoremanatingfromthecenterofthespherecanberepresentedbyq1andthefinalorientationofthevectorisq3.Thearcbetweenq1andq3isthepaththattheinterpolationwouldfollow.Figure3alsoshowsthatifwehaveanintermediatepositionq2,theinterpolationfromq1->q2->q3willnotnecessarilyfollowthesamepathastheq1->q3interpolation.Theinitialandfinalorientationsarethesame,butthearcsarenot.Quaternionssimplifythecalculationsrequiredwhencompositingrotations.Forexample,ifyouhavetwoormoreorientationsrepresentedasmatrices,itiseasytocombinethembymultiplyingtwointermediaterotations.R=R2R1(rotationR1followedbyarotationR2)(Eq.7)Listing2:Quaternion-to-matrixconversion.([07.30.02]Editor’sNote:thefollowingQuatToMatrixfunctionoriginallywaspublishedwithabug–itreversedtherow/columnordering.Thisisthecorrectversion.ThankstoJohnRatcliffandEricHainesforpointingthisout.)QuatToMatrix(QUAT*quat,floatm[4][4]){floatwx,wy,wz,xx,yy,yz,xy,xz,zz,x2,y2,z2;//calculatecoefficientsx2=quat->x+quat->x;y2=quat->y+quat->y;z2=quat->z+quat->z;xx=quat->x*x2;xy=quat->x*y2;xz=quat->x*z2;yy=quat->y*y2;yz=quat->y*z2;zz=quat->z*z2;wx=quat->w*x2;wy=quat->w*y2;wz=quat->w*z2;m[0][0]=1.0-(yy+zz);m[1][0]=xy-wz;m[2][0]=xz+wy;m[3][0]=0.0;m[0][1]=xy+wz;m[1][1]=1.0-(xx+zz);m[2][1]=yz-wx;m[3][1]=0.0;m[0][2]=xz-wy;m[1][2]=yz+wx;m[2][2]=1.0-(xx+yy);m[3][2]=0.0;m[0][3]=0;m[1][3]=0;m[2][3]=0;m[3][3]=1;}Thiscompositioninvolves27multiplicationsand18additions,assuming3x3matrices.Ontheotherhand,aquaternioncompositioncanberepresentedasq=q2q1(rotationq1followedbyarotationq2)(Eq.8)Asyoucansee,thequaternionmethodisanalogoustothematrixcomposition.However,thequaternionmethodrequiresonlyeightmultiplicationsandfourdivides(Listing4),socompositingquaternionsiscomputationallycheapcomparedtomatrixcomposition.Savingssuchasthisareespeciallyimportantwhenworkingwithhierarchicalobjectrepresentationsandinversekinematics.Nowthatyouhaveanefficientmultiplicationroutine,seehowcanyouinterpolatebetweentwoquaternionrotationsalongtheshortestarc.SphericalLinearintERPolation(SLERP)achievesthisandcanbewrittenas(Eq.9)wherepq=cos(q)andparametertgoesfrom0to1.TheimplementationofthisequationispresentedinListing5.Iftwoorientationsaretooclose,youcanuselinearinterpolationtoavoidanydivisionsbyzero.Figure3.Quaternionrotations.Listing3:Euler-to-quaternionconversion.EulerToQuat(floatroll,floatpitch,floatyaw,QUAT*quat){floatcr,cp,cy,sr,sp,sy,cpcy,spsy;//calculatetrigidentitiescr=cos(roll/2);cp=cos(pitch/2);cy=cos(yaw/2);sr=sin(roll/2);sp=sin(pitch/2);sy=sin(yaw/2);cpcy=cp*cy;spsy=sp*sy;quat->w=cr*cpcy+sr*spsy;quat->x=sr*cpcy-cr*spsy;quat->y=cr*sp*cy+sr*cp*sy;quat->z=cr*cp*sy-sr*sp*cy;}ThebasicSLERProtationalgorithmisshowninListing6.Notethatyouhavetobecarefulthatyourquaternionrepresentsanabsoluteandnotarelativerotation.Youcanthinkofarelativerotationasarotationfromtheprevious(intermediate)orientationandanabsoluterotationastherotationfromtheinitialorientation.Thisbecomesclearerifyouthinkoftheq2quaternionorientationinFigure3asarelativerotation,sinceitmovedwithrespecttotheq1orientation.Togetanabsoluterotationofagivenquaternion,youcanjustmultiplythecurrentrelativeorientationbyapreviousabsoluteone.Theinitialorientationofanobjectcanberepresentedasamultiplicationidentity[1,(0,0,0)].Thismeansthatthefirstorientationisalwaysanabsoluteone,becauseq=qidentityq(Eq.10)Listing4:Efficientquaternionmultiplication.QuatMul(QUAT*q1,QUAT*q2,QUATres){floatA,B,C,D,E,F,G,H;A=(q1->w+q1->x)(q2->w+q2->x);B=(q1->z-q1->y)(q2->y-q2->z);C=(q1->w-q1->x)(q2->y+q2->z);D=(q1->y+q1->z)(q2->w-q2->x);E=(q1->x+q1->z)(q2->x+q2->y);F=(q1->x-q1->z)(q2->x-q2->y);G=(q1->w+q1->y)(q2->w-q2->z);H=(q1->w-q1->y)*(q2->w+q2->z);res->w=B+(-E-F+G+H)/2;res->x=A-(E+F+G+H)/2;res->y=C+(E-F+G-H)/2;res->z=D+(E-F-G+H)/2;}AsIstatedearlier,apracticaluseforquaternionsinvolvescamerarotationsinthird-person-perspectivegames.EversinceIsawthecameraimplementationinTOMBRAIDER,I‘vewantedtoimplementsomethingsimilar.Solet’simplementathird-personcamera(Figure4).Tostartoff,let‘screateacamerathatisalwayspositionedabovetheheadofourcharacterandthatpointsataspotthatisalwaysslightlyabovethecharacter’shead.Thecameraisalsopositioneddunitsbehindourmaincharacter.Wecanalsoimplementitsothatwecanvarytheroll(angleqinFigure4)byrotatingaroundthexaxis.Assoonasaplayerchangestheorientationofthecharacter,yourotatethecharacterinstantlyanduseSLERPtoreorientthecamerabehindthecharacter(Figure5).Thishasthedualbenefitofprovidingsmoothcamerarotationsandmakingplayersfeelasthoughthegamerespondedinstantlytotheirinput.Figure4.Third-personcamera.Figure5.Camerafromtop.Youcansetthecamera‘scenterofrotation(pivotpoint)asthecenteroftheobjectitistracking.Thisallowsyoutopiggybackonthecalculationsthatthegamealreadymakeswhenthecharactermoveswithinthegameworld.NotethatIdonotrecommendusingquaternioninterpolationforfirst-personactiongamessincethesegamestypicallyrequireinstantresponsetoplayeractions,andSLERPdoestaketime.However,wecanuseitforsomespecialscenes.Forinstance,assumethatyou’rewritingatanksimulation.Everytankhasascopeorsimilartargetingmechanism,andyou‘dliketosimulateitasrealisticallyaspossible.Thescopingmechanismandthetank’sbarrelarecontrolledbyaseriesofmotorsthatplayerscontrol.Dependingonthezoompowerofthescopeandthedistancetoatargetobject,evenasmallmovementofamotorcouldcausealargechangeintheviewingangle,resultinginaseriesofhuge,seeminglydisconnectedjumpsbetweenindividualframes.Toeliminatethisunwantedeffect,youcouldinterpolatetheorientationaccordingtothezoomanddistanceofobject.Thistypeofinterpolationbetweentwopositionsoverseveralframeshelpsdampentherapidmovementandkeepsplayersfrombecomingdisoriented.Anotherusefulapplicationofquaternionsisforprerecorded(butnotprerendered)animations.Insteadofrecordingcameramovementsbyplayingthegame(asmanygamesdotoday),youcouldprerecordcameramovementsandrotationsusingacommercialpackagesuchasSoftimage3Dor3DStudioMAX.Then,usinganSDK,exportallofthekeyframedcamera/objectquaternionrotations.Thiswouldsavebothspaceandrenderingtime.Thenyoucouldjustplaythekeyframedcameramotionswheneverthescriptcallsforcinematicscenes.Listing5:SLERPimplementation.QuatSlerp(QUAT*from,QUAT*to,floatt,QUAT*res){floatto1[4];doubleomega,cosom,sinom,scale0,scale1;//calccosinecosom=from->x*to->x+from->y*to->y+from->z*to->z+from->w*to->w;//adjustsigns(ifnecessary)if(cosom<0.0){cosom=-cosom;to1[0]=-to->x;to1[1]=-to->y;to1[2]=-to->z;to1[3]=-to->w;}else{to1[0]=to->x;to1[1]=to->y;to1[2]=to->z;to1[3]=to->w;}//calculatecoefficientsif((1.0-cosom)>DELTA){//standardcase(slerp)omega=acos(cosom);sinom=sin(omega);scale0=sin((1.0-t)*omega)/sinom;scale1=sin(t*omega)/sinom;}else{//“from”and“to”quaternionsareveryclose//…sowecandoalinearinterpolationscale0=1.0-t;scale1=t;}//calculatefinalvaluesres->x=scale0*from->x+scale1*to1[0];res->y=scale0*from->y+scale1*to1[1];res->z=scale0*from->z+scale1*to1[2];res->w=scale0*from->w+scale1*to1[3];}AfterreadingChrisHecker‘scolumnsonphysicslastyear,IwantedtoaddangularvelocitytoagameengineonwhichIwasworking.Chrisdealtmainlywithmatrixmath,andbecauseIwantedtoeliminatequaternion-to-matrixandmatrix-to-quaternionconversions(sinceourgameengineisbasedonquaternionmath),Ididsomeresearchandfoundoutthatitiseasytoaddangularvelocity(representedasavector)toaquaternionorientation.Thesolution(Eq.11)canberepresentedasadifferentialequation.(Eq.11)wherequat(angular)isaquaternionwithazeroscalarpart(thatis,w=0)andavectorpartequaltotheangularvelocityvector.Qisouroriginalquaternionorientation.Tointegratetheaboveequation(Q+dQ/dt),IrecommendusingtheRunge-Kuttaorderfourmethod.Ifyouareusingmatrices,theRunge-Kuttaorderfivemethodachievesbetterresultswithinagame.(TheRunge-Kuttamethodisawayofintegratingdifferentialequations.Acompletedescriptionofthemethodcanbefoundinanyelementarynumericalalgorithmbook,suchasNumericalRecipesinC.Ithasacompletesectiondevotedtonumerical,differentialintegration.)Foracompletederivationofangularvelocityintegration,consultDaveBaraff’sSIGGRAPHtutorials.Quaternionscanbeaveryefficientandextremelyusefulmethodofstoringandperformingrotations,andtheyoffermanyadvantagesoverothermethods.Unfortunately,theyarealsoimpossibletovisualizeandcompletelyunintuitive.However,ifyouusequaternionstorepresentrotationsinternally,andusesomeothermethod(forexample,angle-axisorEulerangles)asanimmediaterepresentation,youwon‘thavetovisualizethem.NickBobickisagamedeveloperatCagedEntertainmentInc.andheiscurrentlyworkingonacool3Dgame.Hecanbecontactedatnb@netcom.ca.TheauthorwouldliketothankKenShoemakeforhisresearchandpublications.Withouthim,thisarticlewouldnothavebeenpossible.