Course Informations

  • No textbook
  • Grading Schemes:
    • Assignment 1 (25%): Particle System
    • Assignment 2 (25%): Character Animation
    • Assignment 3 (20%): Paper Presentation or Case study on special effects
    • Final Projects (30%)
      • 2 students/team

Course Overview

  • Physics/Math background
    • 3D rotations
    • Rigid-body dynamics
    • Solving ordinary differential equation
    • Optimization
  • Character Animation
    • Keyframing
    • Motion Capture
    • Motion Editing
  • Physics-based animation
    • Cloth simulation
    • Fluid simulation
    • Biped simulation
    • Hair simulation
  • Behavior Animation
    • Flocking behavior
    • Crowds simulation

Introduction

Kinematics
  • The study or specification of motion, independent of the underlying physics that created the motion.
  • Articulated Figure: A figure made up of a series of links (bones) connected at joints.
  • Forward Kinematics: Given the character’s state, calculate its pose
  • Inverse Kinematice: Given the character’s pose, calculate its state
Motion Capture
  • Live action recording
  • track motion of reference points
  • convert to joint angles to drive an articulated 3D model
  • drive a deformable surface
Motion Editing
  • Get a specific motion
  • Want something else while preserving original

Ordinary Differential Equations

Differential Equations
  • describes the relation between an unknown function and its derivatives
  • solving a differential equation is to find a function that satisfies the relation
First-Ordinary Differential Equation (ODE)
  • All derivatives are with respect to a single independent variable, usually representing time
  • Higher ODE can be transformed into this 1st order system.
Higher-Order ODEs

Visualizing Solution of ODE
  • x(t): a moving point
  • f(x,t): x’s velocities
Vector Field
  • The differential equation x` = f(x,t), defines a vector field over x.
Initial Value Problem
  • Given x` = f(x,t) and x0 = x(t0), find x(t).
  • Given the starting point, follow the integral curve.
Numerical Solution of ODEs
  • Follow a polygonal path
  • By evaluating the derivative at discrete time steps
  • Bigger steps, bigger errors
Euler’s Method
  • Simplest numerical solution method
  • Bigger time step, bigger errors
  • x(t+h) = x(t) + h * f(x,t)
  • Drawbacks of Duler’s Method
    • Inaccurancy
    • Inefficiency
      • Need to use small time-steps to avoid divergence
  • Improvement using midpoint method: slope at midtime is used
The Midpoint Method
  • Accuracy of the Midpoint Method is O(h^3)
Notes
  • Don’t use Euler’s method
    • Inaccuracy
    • Inefficiency (or unstable)
Stability of Analytic Solution of ODE
  • Stable: if solutions resulting from perturbations of initial value remain close to original solution.
  • Unstable: if solutions diverges away from original solution without bound.
  • Neutrally Stable: if solutions are neither stable nor unstable
  • Simple Approach to determining stability and accuracy of numerical method:
    • Apply it to scalar ODE x`= Ax, where A is constant.
    • Example:
Propagated Error
  • Error made early in the process will also affect the late computations —- the early error will be propagated
  • Global error is the sum of propageted error and local error

Stiff Equations

  • Consider s simple ODE x` = -kx (Dampler System), k is a stiffness constant
  • Spring Force: Fs = -ks * x
  • Damping Force: reduce the amplitiude of oscillation
    • Fd = -c * v
    • ma = -c * v
    • v` = -(c/m) * v
  • Step size of Euler’s method is limited by k:
  • Systems that have some big k’s mixed in are called stiff equations
  • Remedy to stiff equations:
    • Using small step size -> inefficient
    • Implicit method
Implicit Method
  • Euler’s method is explicit: uses only information at tim t(n) to advance solution to time t(n+1)
  • Larger stability region can be achieved using information at time t(n+1) -> Implicit
    • x(n+1) = x(n) + h * f(x(n+1), t(n+1))
  • We must evaluate f with x(n+1) before we know its value.

Particle System

  • Particles are objects modeled as point masses
  • Particle properties:
    • mass
    • position
    • velocity
    • force accumulator
    • age, lifespan
    • rendering properties
  • x` = v
  • v` = f/m
  • x`` = f/m
Spatial Forces
  • Forces that depend on nearby particles within a local region
Unary Forces
  • Forces that only depend on 1 particle
n-ary Forces
  • Forces that depend on n particles
  • binary forces: spring and damper
Spring Force (彈力)

Damper Force (阻尼力)

Collision Detection and Response (For now, just simple point-plane collisions)

Collision Response

  • A less accurate but easier alternative is to just modify positions and velocities

Constraint Particles

Constraint Force

Single implicit constraint

  • Constraints:
    • Implicit: C(x) = |x| - r = 0
    • Parametric
  • Legal Acceleration
  • Constraint Force
    • Use the legal condition to compute the constraint force: f^
    • We have one equation and two variables -> need more condition to solve the constraint force
Virtual Work (虛功)
  • Constraint force is passive (no energy gain or loss)
  • Kinetic energy (動能) of the system: T = 1/2 * m * x·x
    • T= 1/2 * m (x``·x+x·x``) = m * x·x`` = x(f + f^) -> f and f^ 所作的虛功
      • 因為是光滑面，所以系統對物體作功為0
      • 故只有正向力，且正向力與x垂直
  • Constraint Force:
    • If the system is at rest: v = 0
      • Only the tangent component of the applied force is kept

Multiple implicit constraint

  • Apply the idea of a bead on a wire on a constrained particle system
  • Particles: each particle represents a point in the phase space
  • Forces: each force affects the acceleration of certain particles
  • Constraints:
    • Each is a function Ci(x1, x2, x3, …)
    • Legal state: Ci(x1, x2, x3, …) = 0, for all i
    • Constraint Force: linear combination of constraint gradients:
  1. system of constraint equation C(q) = 0
  2. To compute the legal acceleration:
  3. To ensure the constraint force does not produce Work
  4. All vectors satisfy the condition can be expressed as:
  5. Constraint forces obtained by solving the linear system
  • Constraint Gradients:
    • Legal states: the intersection of two planes
    • Normal of legal states:
    • Constraint forces are aligned with the normal of legal states
    • Work done by constraint forces is zero

Parametric contraint

  • Parametic:
  • 1 degree of freedom:
    • Solve for θ``
  • This type of method is called Lagrangian Dynamics
    • Instead of working on unconstrained q
    • We work on a constrained space u and solve for u`` through the parametric function q(u)
  • Advantages
    • Fewer degrees of freedom
    • Constraints are always met
  • Disadvantages
    • Hard to find a parametric function that captures the desired constraints

Rigid Body Dynamics

Problems:

  • Unconstraint system
    • No contact
  • Constraint
    • Collision detection and contact
  • Computational efficiency is important
  • Controllable is desired

Rigid Body Concepts

Translation -> Rotation

  • Translation
    • Position
    • Linear velocity
    • Mass
    • Linear momentum
    • Force
  • Rotation
    • Orientation
    • Anguler velocity
    • Inertia tensor (轉動慣量)
    • Angular momentum
    • Torque

Particle State

Particle

Rigid Body

Position and Orientation
  • Translation of body
    • From the origin of the world coordinate
  • Orientation of body
  • Body space (局部座標系統)
    • A fixed and unchanged space where the shape of a rigid body is defined
    • The geometric center of rigid body lies at the origin of body space
    • Aoso called object space or local space
  • World space (世界座標系統)
  • Use x(t) and R(t) to tranform the body space into world space
  • The world coordinate of an arbitrary point on the body
    • R(t) represents the directions of x, y, z axes of the body space in world space at time t
  • so x(t) and R(t) define the position and the orientation of the body at time t
Linear Velocity and Angular Velocity
  • Linear Velocity
    • x`(t) = v(t) is the velocity of the center of mass in world space
  • Angular Velocity
    • we describe the spin as a vector
    • How are R(t) and w(t) related?
    • Consider a vector r(t) at time t specified in world space, how do we represent r`(t) in terms of w(t)?
    • Given the physical meaning of R(t), what does each column change over time?
      1. Consider two 3 by 1 vectors: a and b, the cross product of them:
      2. Given am we can define a matrix a* such that:

    Perspective of Particles: * Imagine a rigid body is composed of a large number of small particles * particles indexed from 1 to N * each particles have a constant location in body space * the location of i-th particle in world space at time t is:

    • Velocity of a particle
Mass and inertia (轉動慣量)
  • The mass of the i-th particle is m(i), the mass is:
  • The center of mass defined in world space is:
  • Inertia Tensor:
    • Inertia tensor describes how the mass of a rigid body is distributed relative to the center of mass
    • I(t) depends on the orientation of a body , but not the translation
    • Inertia tensors vary in world space over time, but are constant in body space
      • Precompute the integral part in body space to save time
    • Derivation:
  • Inertia Tensor in Body Space:
    • 把initial tensor變成三個矩陣相乘
Force and Torque
  • Net Force (淨力)
  • Net Torque (力矩)

Cloth Animation

Challenges of Cloth Simulation

  • Realistic cloth
  • Interactive cloth
  • Stable cloth
  • Complex cloth
  • Collision detection / handling

Particle-based Approaches

  • Macroscopic behavior arises from modeling microscopic structure
  • Particle based on thread-level interactions

Extend to include dynamics

  • Add cloth springs to model
    • Stretch
    • Shearing
    • Bending

Baraff and Witkin (1998)

  • “Large steps in cloth simulation” SIGGRAPH’98
  • Exploit sparseness of Jacobian
  • Used in Maya Cloth
Newton’s 2nd Law of Motion
  • n particles
Explicit Euler (review)

Implicit Euler

Approximation using Taylor Series
  • Recall that a Taylor series of a real function in two variables is given by:
  • We can approximate f(x,v) as:
    • partial f / partial x is a matrix evaluated at (x0, v0)

Solving the Implicit Integration:

Triangle-based Cloth Model

  • Particles are linked like a trangular mesh
  • Energy defined over finite regions
  • How do we determine streetch and shear on triangles?
    • C(x) = ?
Basic Idea
  • Represent cloth surface as a triangular surface embedded in 3D
    • Locally linear mapping w(u,v)
Forces as Energy Functions
  • Damping Forces
    • Instead of deriving form E, Baraff and Witkin differentiate C:
    • Propotional to the velocity in that direction

Constraints

  • May choose
    • penalty method
      • stiff system
    • Lagrange multipliers
      • need compute constraint force
    • Parametric constraint (reduced coordinate)
      • infeasible for dynamic contact constraints
  • Baraff & Witkin introduced a new approach by modifying mass matrix
Zero-acceleration Constraints
  • Basic Idea
    • Enforcing constraint by mass modification
    • e.g. zero acceleration along z-axis
Non-axis zero acceleration constraints
  • For the i-th particle

Higher-order implicit methods

  • implicit Euler has only forst-order accuracy
  • 2nd-order implicit method is used in:
    • Ko & Choi, SIGGRAPH’02
    • Bridson, Marino, & Fedkiw, SCA’03 (mixed explicit / implicit method)

Representing Rotations

3-D Transformations

  • Translate: P` = P + T
  • Scale: P` = SP
  • Rotate: P` = RP
  • Representing P in a homogeneous coordinate: P` = MP
    • M can be used for animation, viewing, or modeling

Homogeneous Coordinate

  • In graphics, we use homogeneous coordinate for transformation.
  • 4x4 matrix can represent translation, scaling and rotation and other transformations
    • Translation
    • Scaling
    • Rotation
  • Compounding Transformations
    • Transformations can be treated as a series of matrix multiplications
  • Two ways of Interpreting a Rotation Matrix
    • Rotating a vector:
    • Rotating a coordinate:

Rotation Matrix

  • Rows / Columns of Matrix must be orthonormal (Unit length and orthogonal)
  • Interpolating the components of two matrices doesn’t maintain the orthonormality
    • The generated matrix is not a rotation matrix

Representing 3D rotations

  • Rotation Matrix
    • orthonormal columns / rows
    • bad for interpolation(內插)
  • Fixed Angle
    • rotate about global axes
    • bad for interpolation, gimbal lock
  • Euler Angle
    • rotate about local axes
    • same problem as Fixed Angle
  • Axis Angle
    • good interpolation, no gimbal lock
    • bad for compounding rotations
  • Quaternion
    • similar to axis angle but in different form
    • q = [s, v]
    • good for compounding rotations

Fixed Angle Representation

  • Ordered triple of rotations about global axes
  • Any triple can be used that doesn’t repeat an axis immediately, e.g., x-y-z is fine, so is x-y-x. But x-x-z is not.

Euler Angle

  • Ordered triple of rotations about local axes
  • Any triple can be used that doesn’t repeat an axis immediately, e.g., x-y-z is fine, so is x-y-x. But x-x-z is not.
  • Euler angle ordering is equivalent to reverse ordering in fixed angles

Gimbal Lock

  • a mechanical device allowing the rotation of an object in multiple dimensions
  • Gimbal Lock occurs when two of the rotation axes align
  • Gimbal Lock is a basic problem with 3D representations using fixed of Euler angles

Axis Angle Representation

  • Euler’s rotation theorem
    • Any 3D rotation can ve described by 4 parameters
Axis Angle Interpolation
  • Interpolate axis and angle separately
Axis Angle v.s. Quaternion
  • Axis Angle
    • Can interpolate the axis and angle separately
    • No gimbal lock
    • Cannot compose rotations efficiently
  • Quaternion
    • Good interpolation
    • No gimbal lock
    • Can be composed

Quaternion

  • 4-tuple of real numbers
    • q = (s, x, y, z) or [s, v]
    • s is a scalar; v is a vector
  • Same information as axis/angle but in a different form
Quaternion Math

* a point in space is represented as [0, x, y, z] * Multiplicative identity: q·[1, 0, 0, 0] = q * Inverse:

Quaternion Rotation
  • To ratate a vector v using quaternion
    • Represent the vector as [0, v]
    • Represent the rotation as a quaternion q
  • q and -q represent the same orientation
  • Why q and -q represent same rotation?
  • Compose Rotations

Visualizing Rotations

  • View rotations as points lying on an n-D sphere
  • Interpolating rotation means moving on n-D sphere
  • Quaternion Interpolation
    • A quaternion is a point on a 4D unit sphere
    • Unit quaternion: q = (s, x, y, z), ||q|| = 1
  • Linear Interpolation
    • Linear Interpolation generates unequal spacing of points after projecting to circle

Spherical Linear Interpolation (slerp)

  • 是四元數的一種線性插值運算，主要用於在兩個表示旋轉的四元數之間平滑差值。
  • Poof of Slerp Equation
  • Pick Shortest path
    • Recall that q and -q represent the same rotation
    • Have to go the short way

Subdivision Scheme

  • Defines a curve by breaking a simpler curve into smaller pieces
  • The limit curve (obtained by subdividing infinitely many times) will be a smooth curve

Kinematics

  • The branch of mechanics concerned with the motions of objects without regard to the forces that cause the motion
  • Degrees of Freedom (DOF): The minimum number of coordinates required to specify completely the motion of an object.
    • 3 DOF joint
      • gimbal
      • ball and socket
    • 2 DOF joint
      • universal
Joint Space v.s. Cartesian Space
  • Joint Space
    • space formed by joint angles
    • position all joints: fine level control
  • Cartesian Space
    • 3D space
    • specify environment interactions
Forward and Inverse Kinematics
  • Forward Kinematics
    • mapping from joint space to cartesian space
  • Inverse Kinematics
    • mapping from cartesian space to joint space
Notations

Acclaim Format

  • Skeletal animation file format including
    • .ASF: Skeleton file
    • .AMC: Motion file
  • All information in ASF file is specified with respect to the global coordinate, while all information in AMC file is specified with respect to the local coordinate.

ASF File

  • Describe the local frame of each bone of a neutral (zero) pose in the global coordinate, e.g. Euler angle in xyz order.
Why is IK hard?
  • Redundancy
  • Natural motion
    • joint limits
    • minimum jerk
  • Singularities

Solving inverse Kinematics

  • Analytic method
  • Inverse-Jacobian method
  • Optimization-based method
  • Example-based method

Analytic Method

Inverse-Jacobian method

  • When linkage is complicated
  • Iteratively change the joint angles to approach the goal position and orientation
Jacobian

* Example: Jacobian for a 2D arm * Computing Jacobian analytically (A small example)

Rotational DOFs

3-DOF Rotational Joints
  • handle as three 1-DOF joints, so we can use the same formula for computing the derivative as we did earlier.
    • we repeat this for each of the three axis
Iterative IK Using Inverse Jacobian

* Jacobian may not be invertible! * Non-square matrix * pseudo inverse * Singularity * causes infinite joint velocities * occurs when any angle cannot achieve V that is not perpendiculat to the arm

Remedy to Singularity Problem
  • Add redundancy
    • add nore joints to the original joint chain (more DOFs are added)
    • Jacobian matrix is not square
  • Use pseudo inverse of Jacobian!
Adding more control to IK
  • Pseudo inverse computes one of many possible solutions that minimize joint angle velocities
  • IK using pseudo inverse Jacobian may not provide natural poses
  • A control term can be added to the pseudo inverse Jacobian solution
    • The control term should not add anything to the velocities, that is:
Null space