AN3D: Interpolate position

Animation in Computer Graphics

2 main ways to describe animation

1. Kinematics
2. Dynamics

Ways to genre animation

1. Descriptive animation
2. Motion tracking
3. Procedural generation
4. Physically based simulation
5. 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}]$

1. find
   $i$ such that
   $t\in [t_i,t_{i+1}]$
2. 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}$$
3. 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=$

$$\begin{gathered} v^{k+1}=v^k+hg \\ {p}^{k+1}=p^j+h{v}^{k+1} \end{gathered}$$

Collision with a plane

Plane

$\mathcal{P}$: parameterized using a point

$a$ and its normal

$n$

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

• Sphere above plane:
  $(p_i-1)\cdot n>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

$$\begin{gathered} \overrightarrow{v}\{\begin{array}{ll}{v}_n\to & -v_n\\ & +\\ v_r\to & v_t\end{array} \\ \text{composante normale: }(\overrightarrow{v}\cdot \overrightarrow{n})=v_n \\ \text{composante tangente: }\overrightarrow{v}-v_n\overrightarrow{n} \end{gathered}$$

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:

1. Correct position in projecting on the constraint
   • Pros: simple to implement
   • Cons: Physically incorrect position
2. Approximate the correct position
3. 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

1. Detect collision
   $\Vert p_1-p_2\Vert \le r_1+r_2$
2. if collision (relative speed
   $>ϵ$)
   • Elastic collision (bouncing)
     $v_{1/2}=\alpha v_{1/2}\pm \beta \frac{J}{m_{1/2}}$
   • If static contact (relative speed
     $\le ϵ$)
     • Friction
       $v_{1/2}=\mu v_{1/2},\mu \in [0,1]$
     • Avoids jittering
3. 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_{i}g-\underset{\text{facteur d'attenuation}}{\underbrace{\mu v_i(t)}}+\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

$$\mathrm{\forall }i\{\begin{array}{l}{p}_i^{\prime }(t)=v_i(t)\\ v_i^{\prime }(t)=F_i(p,v,t)\end{array}$$