6.837-11 Animation 1: Interpolation and Kinematics

Computer Animation IIOrientation interpolationDynamicsSome slides courtesy of Leonard McMillan and Jovan Popovic Lecture 13 6.837 Fall 2002Review from ThursdayInterpolation􀂄SplinesArticulated bodies􀂄Forward kinematics􀂄Inverse Kinematics􀂄Optimization􀂄Gradient descent􀂄Following the steepest slope􀂄Lagrangianmultipliers􀂄Turn optimization with constraints into no constraints Lecture 11 Slide 2 6.837 Fall 2003DebuggingDebug all sub-parts as you write themPrint as much information as possibleUse simple test casesWhen stuck, use step-by-step debugging Lecture 11 Slide 3 6.837 Fall 2003Grid accelerationDebug all these steps:􀂄Sphere rasterization􀂄Ray initialization􀂄Marching􀂄Object insertion􀂄Acceleration Lecture 11 Slide 4 6.837 Fall 2003Final projectFirst brainstorming session on ThursdayGroups of threeProposal due Monday 10/27􀂄A couple of pages􀂄Goals􀂄Progression Appointment with staff Lecture 11 Slide 5 6.837 Fall 2003Computer-Assisted Animation Lecture 11 Slide 6 6.837 Fall 2003 Keyframing 􀂄automate the inbetweening􀂄good control􀂄less tedious􀂄creating a good animationstill requires considerable skilland talentProcedural animation􀂄describes the motion algorithmically􀂄express animation as a function of small number of parameteres􀂄Example: a clock with second, minute and hour hands􀂄hands should rotate together􀂄express the clock motions in terms of a “seconds” variable􀂄the clock is animated by varying the seconds parameter􀂄Example 2: A bouncing ball􀂄Abs(sin(ωt+θ0))*e-ktComputer-Assisted AnimationPhysically Based Animation􀂄Assign physical properties to objects (masses, forces, inertial properties) 􀂄Simulate physics by solving equations􀂄Realistic but difficult to controlMotion Capture􀂄Captures style, subtle nuances and realism􀂄You must observe someone do somethingACM© 1988 “SpacetimeConstraints” Lecture 11 Slide 7 6.837 Fall 2003OverviewInterpolation of rotations, quaternions􀂄Euler angles􀂄QuaternionsDynamics􀂄Particles􀂄Rigid body􀂄Deformable objects Lecture 11 Slide 8 6.837 Fall 2003Interpolating Orientations in 3-DRotation matricesGiven rotation matrices Miand time ti, find M(t) such that M(ti)=Mi.xyzuvuxvxnxuyvynyuzvznzM=n Lecture 11 Slide 9 6.837 Fall 2003Flawed SolutionInterpolate each entry independentlyExample: M0 is identity and M1is 90oaround x-axisIs the result a rotation matrix?100100100Interpolate (010,001)00.50.500101000.50.5⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥−−⎣⎦⎣⎦⎣⎦NO: For example, RRTdoes not equal identity. This interpolation does not preserve rigidity (angles and lengths) Lecture 11 Slide 10 6.837 Fall 20033D rotationsHow many degrees of freedom for 3D orientations?3 degrees of freedom:e.g. direction of rotation and angleOr 3 Euler angles Lecture 11 Slide 11 6.837 Fall 2003Euler AnglesAn Euler angle is a rotation about a single axis. Any orientation can be described composing three rotation around each coordinate axis. Roll, pitch and yawhttp://www.fho-emden.de/~hoffmann/gimbal09082002.pdf Lecture 11 Slide 12 6.837 Fall 2003 Courtesy of Gernot Hoffmann. Used with permission.Interpolating Euler AnglesNatural orientation representation: 3 angles for 3 degrees of freedomUnnatural interpolation: A rotation of 90o first around Z and then around Y = 120o around (1, 1, 1). But 30oaround Z then Y differs from 40o around (1, 1, 1). Lecture 11 Slide 13 6.837 Fall 2003 abcacbabc=abccbaabcabcabcGimballockGimballock:two or more axis align resulting in a loss of rotation degrees of freedom. http://www.fho-emden.de/~hoffmann/gimbal09082002.pdf Lecture 11 Slide 14 6.837 Fall 2003 Courtesy of Gernot Hoffmann. Used with permission.DemoBy Sobeitvoidfrom http://www.gamedev.net/reference/programming/features/qpowers/page7.aspSee alsohttp://www.cgl.uwaterloo.ca/GALLERY/image_html/gimbal.jpg.html Lecture 11 Slide 15 6.837 Fall 2003Euler angles in the real worldApollo inertial measurement unitTo prevent lock, they had to add a fourth Gimbal! Lecture 11 Slide 16 6.837 Fall 2003 http://www.hq.nasa.gov/office/pao/History/alsj/gimbals.htmlRecap: Euler angles3 angles along 3 axisPoor interpolation, lockBut used in flight simulation, etc. because naturalhttp://www.fho-emden.de/~hoffmann/gimbal09082002.pdf Lecture 11 Slide 17 6.837 Fall 2003 Courtesy of Gernot Hoffmann. Used with permission.OverviewInterpolation of rotations, quaternions􀂄Euler angles􀂄QuaternionsDynamics􀂄Particles􀂄Rigid body􀂄Deformable objects Lecture 11 Slide 18 6.837 Fall 2003Solution: Quaternion InterpolationInterpolate orientation on the unit sphereBy analogy: 1-, 2-, 3-DOF rotations as constrained points on 1, 2, 3-spheres Lecture 11 Slide 19 6.837 Fall 20031D sphere and complex planeInterpolate orientation in 2D1 angle􀂄But messy because modulo 2πUse interpolation in (complex) 2D planeOrientation = complex argument of the number Lecture 11 Slide 20 6.837 Fall 2003 θ0θ1Velocity issue & slerp Lecture 11 Slide 21 6.837 Fall 2003 linear interpolation (lerp) in the plane interpolates the straight line between the two orientations and not their spherical distance. => The interpolated motion does not have uniform velocity: it may speed up too much:()()()()()()0101101sin1sinslerp,,(), sinwhere costtttqqqqqqqωωωω−−+===0qq1()tq()tqkeyframeslerpslerpSolution: Spherical linear interpolation (slerp): interpolate along the arc lines by adding a sine term.()()0101lerp,,()1ttttqqqqq==−+2-angle orientationEmbed 2-sphere in 3D2 angles􀂄Messy because modulo 2πand poleUse linear interpolation in 3D spaceOrientation = projection onto the sphereSame velocity correction Lecture 11 Slide 22 6.837 Fall 20033 anglesUse the same principle􀂄interpolate in higher-dimensional space􀂄Project back to unit sphereProbably need the 3-sphere embedded in 4DMore complex, harder to visualizeUse the so-called Quaternions􀂄Due to Hamilton (1843); also Shoemake, Siggraph'85 Lecture 11 Slide 23 6.837 Fall 2003QuaternionsQuaternionsare unit vectors on 3-sphere (in 4D)Right-hand rotation of θradians about visq= {cos(θ/2); vsin(θ/2)}􀂄Often noted (s, v)􀂄What if we use –v ?What is the quaternion of Identity rotation?􀂄Is there exactly one quaternion per rotation?􀂄What is the inverse q-1of quaternion q {a, b, c, d}?􀂄θv Lecture 11 Slide 24 6.837 Fall 2003QuaternionsQuaternionsare unit vectors on 3-sphere (in 4D)Right-hand rotation of θradians about visq= {cos(θ/2); vsin(θ/2)}􀂄Often noted (s, v)􀂄Also rotation of –θaround -vWhat is the quaternion of Identity rotation?􀂄qi= {1; 0; 0; 0}Is there exactly one quaternion per rotation?􀂄No, q={cos(θ/2); vsin(θ/2)} is the same rotation as -q={cos((θ+2π)/2); vsin((θ+2π)/2)} 􀂄Antipodal on the quaternion sphereWhat is the inverse q-1of quaternion q {a, b, c, d}?􀂄{a, -b, -c, -d}θv Lecture 11 Slide 25 6.837 Fall 2003Quaternion AlgebraTwo general quaternionsare multiplied by a special rule:Sanity check : {cos(α/2); vsin(α/2)} {cos(β/2); vsin(β/2)} ()()121212122112,ssvvsvsvvvqq=−++×rrrrrr􀀀 Lecture 11 Slide 26 6.837 Fall 2003Quaternion AlgebraTwo general quaternionsare multiplied by a special rule:Sanity check : {cos(α/2); vsin(α/2)} {cos(β/2); vsin(β/2)} {cos(α/2)cos(β/2) -sin(α/2)v. sin(β/2)} v, cos(β/2) sin(α/2) v+ cos(α/2)sin(β/2) v+v×v}{cos(α/2)cos(β/2) -sin(α/2)sin(β/2), v(cos(β/2) sin(α/2) + cos(α/2) sin(β/2))}{cos((α+β)/2), v sin((α+β)/2) }()()121212122112,ssvvsvsvvvqq=−++×rrrrrr􀀀 Lecture 11 Slide 27 6.837 Fall 2003Quaternion recap 1 (wake up)4D representation of orientationq= {cos(θ/2); vsin(θ/2)}Inverse is q-1 =(s, -v)Multiplication rule􀂄Consistent with rotation compositionHow do we apply rotations?How do we interpolate?θv()()121212122112,ssvvsvsvvvqq=−++×rrrrrr Lecture 11 Slide 28 6.837 Fall 2003Quaternion AlgebraTwo general quaternionsare multiplied by a special rule:To rotate 3D point/vector pby q, compute􀂄q{0; p} q-1p= (x,y,z) q={ cos(θ/2), 0,0,sin(θ/2) } = {c, 0,0,s}q{0,p}= {c, 0, 0, s} {0, x, y, z}()()121212122112,ssvvsvsvvvqq=−++×rrrrrr= {c.0-zs, cp+0(0,0,s)+ (0,0,s) ×p}= {-zs, c p+ (-sy,sx,0) }q{0,p} q -1= {-zs, c p+ (-sy,sx,0) } {c, 0,0,-s}= {-zsc-(cp+(-sy,sx,0)).(0,0,-s), -zs(0,0,-s)+c(cp+(-sy, sx,0))+ (c p+ (-sy,sx,0) ) x (0,0,-s) }= {0, (0,0,zs2)+c2p+(-csy, csx,0)+(-csy, csx, 0)+(s2x, s2y, 0)}= {0, (c2x-2csy-s2x, c2y+2csx-s2y, zs2+sc2)}= {0, x cos(θ)-ysin(θ), x sin(θ)+y cos(θ), z } Lecture 11 Slide 29 6.837 Fall 2003Quaternion AlgebraTwo general quaternionsare multiplied by a special rule:To rotate 3D point/vector pby q, compute􀂄q{0; p} q-1Quaternionsare associative:􀂄(q1 q2) q3 = q1 (q2 q3)But not commutative:􀂄q1 q2 ≠q2 q1()()121212122112,ssvvsvsvvvqq=−++×rrrrrr Lecture 11 Slide 30 6.837 Fall 2003Quaternion Interpolation (velocity) Lecture 11 Slide 31 6.837 Fall 2003 The only problem with linear interpolation (lerp) of quaternionsis that it interpolates the straight line (the secant) between the two quaternionsand not their spherical distance. As a result, the interpolated motion does not have smooth velocity: it may speed up too much in some sections:Spherical linear interpolation (slerp) removes this problem by interpolating along the arc lines instead of the secant lines.0qq1()tq()tqkeyframeslerpslerp()()()()()()01011sin1sinslerp,,(), sinwhere costtttqqqqqqqωωω−−+==01ω=Quaternion InterpolationHigher-order interpolations: must stay on sphereSee Shoemakepaper for:􀂄Matrix equivalent of composition􀂄Details of higher-order interpolation􀂄More of underlying theoryProblems􀂄No notion of favored direction (e.g. up for camera)􀂄No notion of multiple rotations, needs more key points Lecture 11 Slide 32 6.837 Fall 2003QuaternionsCan also be defined like complex numbers a+bi+cj+dkMultiplication rules􀂄i2=j2=k2=-1􀂄ij=k=-ji􀂄jk=i=-kj􀂄ki=j=-ik… Lecture 11 Slide 33 6.837 Fall 2003Fun:Julia Sets in Quaternion spaceMandelbrot set: Zn+1=Zn2+Z0Julia set Zn+1=Zn2+Chttp://aleph0.clarku.edu/~djoyce/julia/explorer.htmlDo the same with Quaternions!Rendered by Skal(Pascal Massimino) http://skal.planet-d.net/See also http://www.chaospro.de/gallery/gallery.php?cat=Anim Lecture 11 Slide 34 6.837 Fall 2003 Images removed due to copyright considerations.Fun:Julia Sets in Quaternion spaceJulia set Zn+1=Zn2+CDo the same with Quaternions!Rendered by Skal(Pascal Massimino) http://skal.planet-d.net/This is 4D, so we need the time dimension as well Lecture 11 Slide 35 6.837 Fall 2003 Images removed due to copyright considerations.Recap: quaternionsθv3 angles represented in 4Dq= {cos(θ/2); vsin(θ/2)}Weird multiplication rulesGood interpolation using slerp()()121212122112,ssvvsvsvvvqq=−++×rrrrrr()tqslerp Lecture 11 Slide 36 6.837 Fall 2003OverviewInterpolation of rotations, quaternions􀂄Euler angles􀂄QuaternionsDynamics􀂄Particles􀂄Rigid body􀂄Deformable objects Lecture 11 Slide 37 6.837 Fall 2003Break: movie timePixarFor the Bird Lecture 11 Slide 38 6.837 Fall 2003