Animation in Computer Graphics

2 main ways to describe animation

Kinematics
Dynamics

Ways to genre animation

Descriptive animation
Motion tracking
Procedural generation
Physically based simulation
Leaning-based synthesis

Descriptive Animation

The artist/an algorithm fully describes the motion and deformation

Pros	Cons
Full control on the result	May introduce un-physical effects

History of CG Animation

First production of animated films (Disney)

Principle

Animator in chief: create key frames
Assistants: fill the in between (secondary drawings)

Principle of Key Framing:

Key framing in CG

Create manually a set of key frames
Interpolate positions

Production pipeline: Interpolate position

Given a set of key positions (pos + time), we want to find an interpolating space-time curve

Input: $(p_i, t_i)$

Linear Interpolation

Pros	Cons
Simple	Non smooth trajectory
Constant speed between keyframes	Generates straight segments

Smooth curve

$\alpha_i$ polynomial basis function of degree $d$

Which polynomial/degree choose ?

Lagrange polynomial interpolation

Interpolate all points at once

Degree of polynomial: $N-1$

Known solution: Lagrange polynomial

Comparison

En pratique, on n’utilise jamais cette interpolation

Spline

Idea

Define each part a polynomial
Smooth junctions between them

How to choose the polynomial

Sufficiently high degree to be smooth
Sufficiently low degree to avoid oscillations

In Graphics, cubic polynomials are often used

Allow up to $\mathcal C^2$ junctions

Hermite interpolation

Cubic curve interpolationg points and derivatives at extermities

Interpolating curve

Initial problem: set of multiple keyframes position+time

2 solutions:

Set explicitely derivatives for each keyframe - teadious
Compute automatically plausible derivatives from surrounding samples - often used

Cardinal spline:

Set:

\[d_i=\mu\frac{p_{i+1}-p_{i-1}}{t_{i+1}-t_{i-1}}\]

$\mu$ curve tension $\in[0,2]$
$\mu = 1$ is commonly used
- Catmull Rom Spline

Wrap-up algorithm

Compute $p(t)$ as a cubic spline interpolation

Given keyframes $(p_i, t_i)_{i\in[0,N-1]}$
Given time $t\in[t_1,t_{N-2}]$

find $i$ such that $t\in[t_i,t_{i+1}]$
Compute $d_i=\mu\frac{p_{i+1}-p_{i-1}}{t_{i+1}-t_{i-1}}$ and $d_{i+1}=\mu\frac{p_{i+2}-p_{i}}{t_{i+2}-t_{i}}$
Compute $p(t) = (2s^3-3s^2+1)p_i + (s^3-2s^2+s)d_i + (-2s^3+3s^3)p_{i+1} + (s^3-s^2)d_{i+1}$
- with $s=\frac{t-t_i}{t_{i+1}-t_i}$

Limitation of cubic curve interpolation

Only $\mathcal C^1$, but not $\mathcal C^2$ at junctions: curvature/acceleration discontinuity
Non-constant peed along each polynomial

Curve editing

Animation software (Maya, 3DSMax, Blender, etc) always come with a curve editor
Artists can manually ajust their position, time, and derivatives on curve editor
- One curve for each scalar parameter
  - position $(x,t,z)$
  - scaling $(s_x,s_y,s_z)$
  - rotation/quaternion
Can also use a wrapper function $w$ to change time $p(t) = f(w(t))$

Usage of keyframes interpolation

Interpolate every vertex of multiple meshes

Multi-target blending

Interpolate between multiple key poses

Interesting for facial animation
Per-vertez formulation $p_i(t)=\sum_{k}^{N_{poses}}$

Blend shapes

\[p_i(t) = b_i^0 + \sum_k^{N_{poses}}\omega_k(t)(\underbrace{b_{ki}-b_i^0})\]

Physically-based simulation

When physically based simulation is needed

Accurate dynamics
Teadious to model by hand or procedurally
- Multiple interacting elements
- Complex animated geometry

Material model

Elasticity
- Purely elastic models don’t loose energy when deformed
Plasiticity
- Ductile material: can allow large amout of plastic deformation without breaking (plastic)
- Brittle - Opposite (glass)
Viscosity
- Resistance to flow (usually for fluid, ex:honey)

In reality

Elasto-plastic materials
- Allow elastic behavior for small deformation, and plastic at larger one
Visco-elastic materials
- Elastic properties with delay

Rigid spheres

System modeling

Particles modeling the center of hard spheres

Spheres can collide with surrounding obstacles
Spheres can collide with each others

System: $N$ particles with position $p_i$, speed $v_i$, mass $m_i$, modeling a sphere of radius $r_i$

initial conditions: $p_i(0)=p_i^0,v_i(0)=v_i^0$

Forces: $F_i=$

\[v^{k+1} = v^k+hg\\ p^{k+1}=p^j+hv^{k+1}\]

Collision with a plane

Plane $\mathcal P$: parameterized using a point $a$ and its normal $n$

$\{p\in\mathbb R^3\in\mathcal P\Rightarrow (p-1)\cdot n =0\}$

Sphere above plane: $(p_i-1)\cdot n\gt r_i$
Sphere in collision: $(p_i-a)\cdot n\le r_i$

  
for (int i = 0; i < N; ++i) {
    float detection = dot(p[i]-a, n);
    if (detection <= r[i]) {
        // ... collision response
    }
}

Collision response with plane

What should we do when a collision is detected ?

On peut changer la vitesse

On decompose la vitesse selon 2 composantes: la tangente et la normale

\[\vec v\begin{cases} v_n\to &-v_n\\ &+\\ v_r\to &v_t \end{cases}\\ \text{composante normale: } (\vec v\cdot\vec n)=v_n\\ \text{composante tangente: }\vec v-v_n\vec n\]

Collision response = Update speed

Result

Applying collision response on speed only

Les boules tombent en-dessous du plan

Quand notre sphere rebondit, il est possible qu’une partie passe au travers du plan, donc on considere en collision, donc on inverse sa vitesse, donc en collision, etc

Comment on contre ca ?

Si ma sphere est dans le sol, on s’arrange pour qu’elle ne soit pas dans le sol On la “repousse” pour qu’elle soit en contact avec la surface

Collision response with a plane: position

Three possibilities:

Correct position in projecting on the constraint
- Pros: simple to implement
- Cons: Physically incorrect position
Approximate the correct position
Go backward in time to find exact instant of collision
- Continuouse collision detectino
- Pros: physically correct
- Cons: Computationally heavy

Result

Ca marche !

\[p_i^{new} = p_i+d_n\]

Collision between speheres

Given 1 spheres $(p_1, v_1, r_2, m_2), (p_2, v_2, r_2, m_2)$

Collision when

\[\Vert p_1-p_2\Vert\le r_1+r_2\]

What will happen with speeds ?

$v_1\to v_1^{new}, v_2\to v_2^{new}$

Notion of impulse

An impulse $J$ is the integrted force over time

\[J=\int_{t_1}^{t_2}F(t)dt\]

Result in a sudden change of speed (momentum) in a discrete case

For a particle with a constant mass

\[\int_{t_1}^{t_2} F(t)dt=\int_{t_1}^{t_2} ma(t)dt\]

2 spheres in collision

J’ecris pas ca vous etes fous

Summary

Detect collision $\Vert p_1-p_2\Vert\le r_1+r_2$
if collision (relative speed$\gt\epsilon$)
- Elastic collision (bouncing) $v_{1/2}=\alpha v_{1/2}\pm\beta \frac{J}{m_{1/2}}$
- If static contact (relative speed $\le\epsilon$)
  - Friction $v_{1/2}=\mu v_{1/2},\mu\in[0,1]$
  - Avoids jittering
Correct position (project on contact surface)
- $p=p+\frac{d}{2u}$
- $d=r_1+r_2-\Vert p_1-p_2\Vert$: collision depth
- For small impacts, can use position based dynamics
  - $v^{new} = \frac{(p^{new}-p^{prev})}{\delta t}$

Note on collision stack

Optimiser ne pas avoir a simuler les spheres sur le sol et immobiles

Faire des graphes des solides et les traiter comme des solides rigides

Modeling elastic shapes with particles

Spring mass systems

Particles: samples on shape
Springs: link closed-by particles in the reference shape

Spring structure

How to model spring connectivity ?

Structutal springs
- 1-ring neighbors springs ($\simeq$ mesh edges)
- Pros: limit elongation/contraction
- Cons: Allows shearing, and bending
- Add extra springs connectivity
Shearing springs
- Diagonal links
Bending springs
- 2-ring neighborhood

Cloth simulation

Mass-spring cloth simulation

Particles are sampled on a $N\times N$ grid
- Each particle has a mass $m$
Set structural, shearing and bending springs

Forces

On each particle: gravity + drag + spring forces

$F_i(p,v,t)=m_ig-\underbrace{\mu v_i(t)}_{\text{facteur d'attenuation}}+\sum_{j\in\nu_i}K_{ij}(\Vert p_j(t)-p_i(t)\Vert-L_{ij}^0)\frac{p_i(t)-p_i(t)}{\Vert p_j(t) -p_i(t)\Vert}$

$\nu_i$: neighborhood of particle $i$
$L_{ij}^0$: rest length of spring $ij$

Associated ODE

\[\forall i \begin{cases} p_i'(t) = v_i(t)\\ v_i'(t)=F_i(p,v,t) \end{cases}\]

AN3D: Interpolate position

Animation in Computer Graphics

Descriptive Animation

History of CG Animation

Key framing in CG

Production pipeline: Interpolate position

Linear Interpolation

Smooth curve

Lagrange polynomial interpolation

Comparison

Spline

Hermite interpolation

Interpolating curve

Cardinal spline:

Wrap-up algorithm

Limitation of cubic curve interpolation

Curve editing

Usage of keyframes interpolation

Multi-target blending

Blend shapes

Physically-based simulation

When physically based simulation is needed

Material model

Rigid spheres

System modeling

Collision with a plane

Collision response with plane

Result

Collision response with a plane: position

Result

Collision between speheres

Notion of impulse

2 spheres in collision

Summary

Note on collision stack

Modeling elastic shapes with particles

Spring structure

Cloth simulation

Mass-spring cloth simulation

Forces

Further Reading

AN3D: Bases du rendu graphique

IMED2: TP3

IMED2: Project