6.837-11 Animation 2: Orientation and Quaternions

Computer Animation IIIQuaternionsDynamicsSome slides courtesy of Leonard McMillan and Jovan PopovicRecap: Euler angles3 angles along 3 axisPoor interpolation, lockBut used in flight simulation, etc. because naturalhttp://www.fho-emden.de/~hoffmann/gimbal09082002.pdfAssignment 5: OpenGLInteractive previsualization􀂄OpenGL API􀂄Graphics hardware􀂄Jusrsend rendering commands􀂄State machineSolid textures􀂄New Material subclass􀂄Owns two Material* 􀂄Chooses between them􀂄“Shadertree”Final projectFirst brainstorming session on ThursdayGroups of threeProposal due Monday 10/27􀂄A couple of pages􀂄Goals􀂄Progression Appointment with staffFinal projectGoal-based􀂄Simulate a visual effect 􀂄Natural phenomena􀂄Small animation􀂄Game􀂄Reconstruct an existing sceneTechnique-based􀂄Monte-Carlo Rendering􀂄Radiosity􀂄Fluid dynamicsOverviewInterpolation of rotations, quaternions􀂄Euler angles􀂄QuaternionsDynamics􀂄Particles􀂄Rigid body􀂄Deformable objectsQuaternion principleA quaternion = point on unit 3-sphere in 4D = orientation.We can apply it to a point, to a vector, to a rayWe can convert it to a matrixWe can interpolate in 4D and project back onto sphere􀂄How do we interpolate?􀂄How do we project?Quaternion 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=−++×rrrrrrQuaternion 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=−++×rrrrrrQuaternion 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 }Quaternion Interpolation (velocity)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ω=QuaternionsCan also be defined like complex numbers a+bi+cj+dkMultiplication rules􀂄i2=j2=k2=-1􀂄ij=k=-ji􀂄jk=i=-kj􀂄ki=j=-ik…Fun: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=AnimImages 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 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()tqslerpOverviewInterpolation of rotations, quaternions􀂄Euler angles􀂄QuaternionsDynamics􀂄Particles􀂄Rigid body􀂄Deformable objectsBreak: movie timePixarFor the BirdNowDynamicsParticleA single particle in 2-D moving in a flow field􀂄Position􀂄Velocity􀂄The flow field function dictatesparticle velocity12xx⎡⎤=⎢⎥⎣⎦x12,vdvdt⎡⎤==⎢⎥⎣⎦xvv()tx1x2x(),tgx(),t=vgxVector FieldThe flow field g(x,t) is a vector field that defines a vector for any particle position xat any time t.How would a particle move in this vector field?1x2x(),tgxDifferential EquationsThe equation v= g(x, t) is a first order differential equation:Position is computed by integrating the differential equation:Usually, no analytical solution(),dtdt=xgx()()()00,tttttdt=+∫xxgxNumeric IntegrationInstead we use numeric integration: 􀂄Start at initial point x(t0) 􀂄Step along vector field to compute the position at each timeThis is called an initial value problem.()0tx1x2x()1tx()2txEuler’s MethodSimplest solution to an initial value problem. 􀂄Starts from initial value 􀂄Take small time steps along the flow:Why does this work?()()(),ttttt+∆=+∆xxgxConsider Taylor series expansion of x(t):Disregarding higher-order terms and replacing the first derivative with the flow field function yields the equation for the Euler’s method.()()2222dtdttttdtdt∆+∆=+∆++xxxxLOther MethodsEuler’s method is the simplest numerical method. The error is proportional to . For most cases, it is inaccurate and unstable 􀂄It requires very small steps.Other methods:􀂄Midpoint (2ndorder Runge-Kutta)􀂄Higher order Runge-Kutta(4thorder, 6thorder)􀂄Adams􀂄Adaptive Stepsize2t∆1x2xParticle in a Force FieldWhat is a motion of a particle in a force field?The particle moves according to Newton’s Law:()22dmamdt==xffThe mass m describes the particle’s inertial properties: Heavier particles are easier to move than lighter particles. In general, the force field f(x, v, t) may depend on the time tand particle’s position xand velocity v.Second-Order Differential EquationsNewton’s Law => ordinary differential equation of 2ndorder:A clever trick allows us to reuse the numeric solvers for 1st-order differential equations. Define new phase vector y: 􀂄Concatenate position xand velocity v, Then construct a new 1st-order differential equation whose solution will also solve the 2nd-order differential equation.()()22,,dttmdt=xfxv/,//ddtddtddtm⎡⎤⎡⎤⎡⎤===⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦xxvyyvvfParticle AnimationAnimateParticles(n, y0, t0, tf){y = y0t= t0DrawParticles(n, y)while(t!= tf) {f= ComputeForces(y, t)dydt= AssembleDerivative(y, f){y, t } =ODESolverStep(6n, y, dy/dt)DrawParticles(n, y)}}Particle Animation [Reeves et al. 1983]Star Trek, The Wrath of Kahn [Reeves et al. 1983]Start Trek, The Wrath of KahnOverviewInterpolation of rotations, quaternions􀂄Euler angles􀂄QuaternionsDynamics􀂄Particles􀂄Rigid body􀂄Deformable objectsRigid-Body DynamicsCould use particles for all pointsBut rigid body does not deformFew degrees of freedomStart with only one particle at center of mass()tx()tv()()()??ttt⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦xyvNet Force()tx()tv()2tf()3tf()1tf()()iitt=∑ff)()(tfdttdMv=Net Torque()tx()tv()1btp()3btp()2btp()()()()biiittt=−×∑τpxf()2tf()3tf()1tfRigid-Body Equation of Motion()()()()()()()()()()()tttttddtMttdtdttttω⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦xvRRyvfIωτ􀀀()()()linear momentumangular momentumMttt→→vIωSimulations with CollisionsSimulating motions with collisions requires that we detect them (collision detection) and fix them (collision response).()0ty()1ty()2ty()3tyCollision ResponseThe mechanics of collisions are complicated Simple model: assume that the two bodies exchange collision impulseinstantaneously.nbpb−v+=?vFrictionless Collision Model()ε+−⋅=−⋅nnbvbvnbpb−vε=1ε=12ε=0+vOverviewInterpolation of rotations, quaternions􀂄Euler angles􀂄QuaternionsDynamics􀂄Particles􀂄Rigid body􀂄Deformable objectsDeformable modelsShape deforms due to contactDiscretizethe problemAnimation runs with smaller time steps than rendering (between 1/10,000s and 1/100s)Mass-Spring systemNetwork of masses and springsExpress forcesIntegrateDeformation of springs simulates deformation of objectsF[Dorsey 1996]Explicit FiniteElementsDiscretizethe problem Solve locallySimpler but less stable than implicitFiniteElementsIndependentmatricialsystemsObjectImplicitFiniteElementsDiscretizethe problem Express the interrelationshipSolve a big systemMore principled than mass-springObjectFiniteElementsLargematricialsystemFormally: FiniteElementsWe are trying to solve a continuous problem􀂄Deformation of all points of the object􀂄Infinite space of functionsWe project to a finite set of basis functions􀂄E.g. piecewise linear, piecewise constantWe project the equations governing the problemThis results in a big linear systemObjectFiniteElementsLarge matricialsystemCloth animationDiscretizecloth Write physical equationsIntegrateCollision detectionImage removed due to copyright considerations.Fluid simulationDiscretizevolume of fluid􀂄Exchanges and velocity at voxelboundaryWrite NavierStokes equations􀂄Incompressible, etc.Numerical integration􀂄Finite elements, finite differencesChallenges:􀂄Robust integration, stability􀂄Speed􀂄Realistic surface w v u Fedkiw, Ronald. Jos Stam, and Henrik Wann Jensen. “Visual Simulation of Smoke.” Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. pp.15-22, August 2001. Image adapted from: Image removed due to copyright considerations.How do they animate movies?KeyframingmostlyArticulated figures, inverse kinematicsSkinning 􀂄Complex deformable skin􀂄Muscle, skin motionHierarchical controls􀂄Smile control, eye blinking, etc. 􀂄Keyframesfor these higher-level controlsA huge time is spent building the 3D models, its skeleton and its controlsPhysical simulation for secondary motion􀂄Hair, cloths, water􀂄Particle systems for “fuzzy” objectsImages removed due to copyright considerations.Final projectFirst brainstorming session on ThursdayGroups of threeLarge programming contentProposal due Monday 10/27􀂄A couple of pages􀂄Goals􀂄Progression Appointment with staffFinal projectGoal-based􀂄Render some class of object (leaves, flowers, CDs) 􀂄Natural phenomena (plants, terrains, water)􀂄Weathering􀂄Small animation of articulated body, explosion, etc. 􀂄Visualization (explanatory, scientific)􀂄Game􀂄Reconstruct an existing sceneTechnique-based􀂄Monte-Carlo Rendering􀂄Radiosity􀂄Finite elements/differences (fluid, cloth, deformable objects)􀂄Display acceleration􀂄Model simplification􀂄Geometry processingBased on your ray tracerGlobal illumination􀂄Distribution ray tracing (depth of field, motion blur, soft shadows)􀂄Monte-Carlo rendering􀂄CausticsAppearance modeling􀂄General BRDFS􀂄Subsurface scattering