Computer Animation

Contents

• Introduction and overview
• 0. Refresher: ODEs, Taylor, rotations, energy
• 1. The animation pipeline: keyframes and splines
• 2. Numerical integration of ODEs
• 3. Stability: the oscillator theorem
• 4. Particles, forces, mass-spring systems
• 5. Rigid bodies and quaternions
• 6. Collisions and constraints
• 7. Skinning: LBS and its artifacts
• 8. Inverse kinematics
• 9. Crowds and behaviors
• 10. Procedural versus data-driven
• 11. Course research notes (Desbrun)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a graphics, games or simulation engineer who wants to animate without a black box. Empirical first: each topic starts from what goes wrong on screen — keyframes that pop, a mass-spring system that explodes when \Delta t is too large — and only then names the tools that fix it: splines, integrators, inverse kinematics, motion matching.

The course goes from physical simulation to learned motion, and in doing so it prepares the real-time and control-oriented modules of the program.

What you will be able to do

• Build a complete animation pipeline, from keyframe posing to spline interpolation.
• Choose a numerical integration scheme for an ODE and predict its stability thanks to the oscillator theorem.
• Model and simulate physical systems: particles, forces, mass-spring systems.
• Represent the orientation of rigid bodies with quaternions and integrate them correctly.
• Handle collisions and constraints in a stable simulation loop.
• Implement linear blend skinning (LBS) and diagnose its artifacts.
• Write an inverse kinematics solver and simulate crowd behaviors.
• Animate a face with blendshapes and simulate continuum models — elasticity, cloth — and fluids, with particles or on a grid.
• Compare procedural animation and data-driven animation, and situate neural-network approaches.

Official objectives and syllabus (2026-2027 catalog)

The official course description sets three objectives: master the “standard industry methods for real-time and interactive animation” (special effects, animated cinema, video games), complemented by research-oriented approaches; lay the “fundamentals of physical simulation and particle-based methods”; and be “able to implement several of these methods in C++/OpenGL in an interactive context”.

The official description (paraphrased) presents a module of 3D animation teaching the animation and deformation methods of 3D shapes used in special effects, video games and animated films, and more generally in animated, interactive virtual worlds; its content details procedural animation approaches and the simulation methods that model physical phenomena, prepares both for R&D engineering and for research in computer graphics, and illustrates them mostly with entertainment applications (animated film, games, virtual and augmented reality) and real-time physical simulation, the mechanisms carrying over to medicine, biology or aerodynamics.

The cases treated in lectures and labs are the interactive animation and deformation of an articulated character, the deformation of a garment with real-time collision handling, and the simulation of a moving fluid surface. The course is mostly practice-oriented, half lectures and half exercise/lab sessions programmed in C++ with OpenGL.

Official prerequisites: INF443 for the École Polytechnique engineering students, “C++ and basics of computer graphics” for exchange students; the sheet displays neither the teaching volume nor any assessment text. The table follows the sheet’s detailed course plan (the English syllabus of the sheet lists the same items).

All official topics are covered. Elastic deformation, cloth and fluids were only named in definitions 4.5 and 4.6, the production pipeline only in a note, and facial animation had no worked example: the section on elasticity, cloth and fluids in practice (def. 4.8–4.10, examples 4.7 and 4.11), the section on the production pipeline (def. 10.4–10.5, example 10.6) and example 7.6 were added against the 2026-2027 sheet.

Our extensions, beyond the official syllabus: chapters 0–3 (mathematical refreshers, numerical integration and stability theory — the tooling that distinguishes this course from a physics-engine tutorial), chapter 6 (collisions and constraints), chapter 9 (crowds and behaviors) and chapter 11 (research work).

Where this course fits in the program

Module of period 1 of M1 (36 h, 4.5 ECTS). These materials present it as an option outside the recommended track; the MSc&T brochure counts it among the period’s courses. It is taken at the very beginning of the year, with no prerequisites among the other modules of the master’s program.

• Prerequisites — official: INF443 for the École Polytechnique engineering students; “C++ and basics of computer graphics” for exchange students (PEI), consistent with the C++/OpenGL exercise sessions. Internally: the programming and algorithmic fluency of the Refresher in Computer Science, as well as solid foundations in linear algebra (vectors, matrices, rotations); the refresher chapter puts ODEs, Taylor expansions and energies back in place.
• Downstream modules — the meshes manipulated here are studied in depth in Digital Representation and Analysis of Shapes (another geometric module of P1); and physical simulation becomes a learning building block in Analysis and Deep Learning on Geometric Data (M2), the natural continuation of the neural-network animation discussed at the end of the course.

Course outline

• Refresher: ODEs, Taylor, rotations, energy — the simulator’s mathematical toolbox, reactivated from the very first section.
• The animation pipeline: keyframes and splines — how to interpolate poses cleanly between keyframes.
• Numerical integration of ODEs — discretize time without destroying the motion.
• Stability: the oscillator theorem — why explicit Euler blows up and how to choose a stable scheme.
• Particles, forces, mass-spring systems — the first complete physical system you will simulate, up to continuum models (elasticity, cloth) and fluids, with particles or on a grid.
• Rigid bodies and quaternions — representing and integrating rotations without watching them degenerate.
• Collisions and constraints — making objects interact with each other and with the world.
• Skinning: LBS and its artifacts — attaching a deformable skin to an animated skeleton, then animating a face with blendshapes.
• Inverse kinematics — automatically computing the poses of a character reaching a target.
• Crowds and behaviors — animating hundreds of agents with simple rules.
• Procedural versus data-driven — the modern debate: physical rules versus learned models (motion matching, neural networks).
• Course research notes (Desbrun) — a tour of Mathieu Desbrun’s research work related to the course, extended by a scientific landmark on the work of Marie-Paule Cani — the two coordinators of the course unit.
• Exercises and References — systematic training and sources to go further.

Session plan

36 h in class = 12 sessions of 3 h. The SynapseS 2026–2027 sheet displays no volume for this course (no hours in person, no lecture / small-class split), but the LLGA curriculum page of the programme wiki (msct.dix.polytechnique.fr/llga, last modified on 9 September 2026 by the programme director) states that “all subsequent M1 courses are 36h and will credit 4.5 ECTS”; the sheet only says that the course is half lectures, half exercise/lab sessions in C++ with OpenGL.

The sheet gives a course plan but no session-by-session programme, so the split below is our proposal for covering these notes in that time; it keeps the integration and stability tools (ch. 2–3) before the simulation topics that need them.

Level 1 = foundations (refreshers, definitions, first worked examples), 2 = core methods, 3 = advanced material (learned animation, open questions); the level never goes down from one session to the next.

Self-study, outside the 36 h (about 2 h in total): ch. 11 Course research notes (Desbrun) — smoothed particles, discrete exterior calculus and the landmark on animated implicit surfaces (≈ 2 h).

How to study this module

• First consolidate the refresher chapter: ODEs, Taylor and rotations come back in each of the following sections.
• Program small simulators (bouncing ball, mass-spring system) rather than only reading: stability is understood hands-on.
• Vary the time step and the stiffness of the springs to observe for yourselves the instabilities that theory predicts.
• Redo the exercises of each section before moving on to the next: they directly prepare the graded assignments.
• Keep in mind the guiding question: which part of this simulator could a neural network learn, and at what cost?
• Explore the research of the course instructors and the references if you are aiming for an internship or a PhD in animation and geometry.

0. Refresher: ODEs, Taylor, rotations, energy

This chapter puts back in place the mathematics a simulator runs on: ordinary differential equations, Taylor expansions, rotations and mechanical energy. Its most important object is the harmonic oscillator, on which every integrator of the course will be tested.

1. The animation pipeline: keyframes and splines

Concrete scene: a character walk that “floats” because the poses between the keyframes are interpolated without any control of the velocities. This chapter answers the first question of every animation system: given a few poses fixed by the animator, how do we fill in the frames between them smoothly?

2. Numerical integration of ODEs

Physical animation reduces to solving an ODE \dot{\mathbf{y}} = f(\mathbf{y}) one frame at a time, without access to its exact solution. This chapter defines the three integrators used throughout the course and measures their accuracy; their stability, which matters even more, is the subject of chapter 3.

3. Stability: the oscillator theorem

A small time step does not guarantee a sane simulation: some schemes add energy at every step, whatever the step. This chapter makes this precise on the harmonic oscillator and derives, for each scheme of chapter 2, the condition under which the simulation stays bounded.

4. Particles, forces, mass-spring systems

This chapter builds the first complete physical system of the course: a set of point masses subjected to gravity, drag and springs. It then shows how the stability results of chapter 3 dictate the time step, and how the same machinery extends to continuous materials, cloth and fluids.

import numpy as np

# ------------- Particle simulator: symplectic Euler -------------
# n particles, gravity, chain of springs, impenetrable ground (restitution 0.8)
def simulate(n=40, steps=1200, h=1/240, seed=0):
    rng = np.random.default_rng(seed)
    x = rng.uniform(-1, 1, (n, 3)); x[:, 2] += 1.5   # initial positions
    v = np.zeros((n, 3))
    m = np.full(n, 0.05)                             # 50 g per particle
    g = np.array([0, 0, -9.81]); mu = 0.7            # gravity, linear drag
    # springs (i, j, stiffness k, damping c, rest length r)
    edges = [(i, i + 1, 80.0, 0.4, 0.15) for i in range(n - 1)]
    for _ in range(steps):
        F = m[:, None] * g[None, :]                  # gravity
        for (i, j, k, c, r) in edges:                # spring + damper
            d = x[j] - x[i]; L = np.linalg.norm(d); u = d / L
            Fij = (k * (L - r) + c * np.dot(v[j] - v[i], u)) * u
            F[i] += Fij; F[j] -= Fij
        v += h * F / m[:, None]     # (1) velocity first   -- symplectic Euler
        v *= (1 - mu * h)           # global linear drag
        x += h * v                  # (2) position next
        hit = x[:, 2] < 0           # ground z = 0: projection + bounce
        x[hit, 2] = 0
        v[hit, 2] = -0.8 * v[hit, 2]
        yield x.copy(), v.copy()

# total mechanical energy = kinetic + gravity + springs (same m, k, r as above)
def energy(x, v, m=0.05, k=80.0, r=0.15):
    L = np.linalg.norm(np.diff(x, axis=0), axis=1)   # lengths of the chain springs
    return (0.5 * m * (v ** 2).sum() + m * 9.81 * x[:, 2].sum()
            + 0.5 * k * ((L - r) ** 2).sum())

# drag, dampers and restitution 0.8 only remove energy: E must decay
# (about 2800 J -> 0.03 J); any sustained growth means an unstable step
for step, (x, v) in enumerate(simulate()):
    if step % 240 == 0:
        print(f"t = {step/240:5.2f} s   E = {energy(x, v):9.3f} J")

Elasticity, cloth and fluids in practice

Definitions 4.5 and 4.6 name the models of the official syllabus (elastic deformation, cloth, fluids on grids and with particles). This section gives the equations a simulator actually implements, with one computation for each, and shows that the stability analysis of chapter 3 governs all of them.

5. Rigid bodies and quaternions

Particles have a position but no orientation; boxes, wheels and bones need both. This chapter describes the state of a rigid body, explains why orientations are stored as unit quaternions rather than angles, and gives the conservation law that a rotating body must respect.

6. Collisions and constraints

Simulated objects must not pass through each other or through the ground. This chapter splits the problem in two: finding the pairs that touch (detection), then changing velocities or positions so that the contact is respected (response).

Billiard balls hit head-on, so the impulse passes through their centers and nothing turns. A box landing on a corner, a rod hitting the ground with one end or a car door slamming all receive the impulse off-center: part of it goes into rotation, and the formula of Theorem 6.2 must account for it.

#include <glm/glm.hpp>
using glm::vec3; using glm::mat3;

struct RigidBody {
    float m;  mat3 Ibody_inv;        // mass, inverse inertia in the body frame
    vec3 c, V, L;  mat3 R;           // center, velocity, angular momentum, orientation
};

// Contact with static ground at point p; n = unit normal from the body into the ground.
void contact_impulse(RigidBody& a, vec3 p, vec3 n, float e) {
    mat3 Iinv = a.R * a.Ibody_inv * glm::transpose(a.R);  // world inverse inertia
    vec3 r = p - a.c, w = Iinv * a.L;                      // lever arm, angular velocity
    float vn = -glm::dot(a.V + glm::cross(w, r), n);       // v_rel . n, ground at rest
    if (vn >= 0.0f) return;                                // separating: no impulse
    vec3 rn = glm::cross(r, n);
    float denom = 1.0f / a.m + glm::dot(rn, Iinv * rn);    // angular term >= 0
    float j = -(1.0f + e) * vn / denom;
    a.V -= (j / a.m) * n;                                  // linear update
    a.L -= j * rn;                                         // angular: L += r x (-j n)
}

7. Skinning: LBS and its artifacts

An animated character is a skeleton of a few dozen bones covered by a skin mesh of thousands of vertices. Skinning is the rule that moves each vertex of the skin when the bones move; this chapter studies the standard rule, its characteristic artifact and the remedies, then the face, which has no bones.

8. Inverse kinematics

Animators rarely want to set every joint angle by hand: they want a hand to reach a cup or a foot to rest on a step. Inverse kinematics computes joint angles from such goals; this chapter gives the closed-form solution for two segments and the iterative methods used for longer chains.

9. Crowds and behaviors

Animating hundreds of characters one by one is impossible, so crowds are animated by rules: each agent reacts to its neighbors and to its goal, and the collective behavior emerges. This chapter presents the two classical rule sets, for flocks and for pedestrians.

10. Procedural versus data-driven

The previous chapters produced motion either by hand (keyframes, IK) or by rules (physics, behaviors). This chapter compares these two approaches with a third one, learning motion from captured data, and shows how a production character combines all three.

The production pipeline (cinema, VFX)

The official syllabus lists the animation methods “in production”. In a film or visual-effects studio, the techniques of this course are not run by one person in one program: each shot flows through a chain of departments, and what passes from one to the next is data with a fixed format.

11. Course research notes (Desbrun)

Exercises

1. ★ Guided Hermite.

   • 1. Verify that the four polynomials h_{00}, h_{10}, h_{01}, h_{11} of Theorem 1.2 satisfy the conditions (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1) at s = 0 and s = 1.
   • 2. Recover h_{00} by solving the linear system by hand.
   • 3. Recompute Example 1.3 with \mathbf{v}_0 = 2, \mathbf{v}_1 = 0 — where is the maximum of the curve now?

2. ★ Implicit fall. For \dot{v} = g - \tfrac{c}{m}v, write the implicit Euler step, solve it exactly in v_{n+1}, and show that v_n \to v_\infty for every h > 0. What is the local error in O(h^2)? Compare with the table of Example 2.4 for h = 0.1.

3. ★ Guided 2-DoF network. Two masses m linked to each other and to the walls by three springs k (chain).

   • 1. Write M, K.
   • 2. Compute the natural frequencies \omega_{1,2} (one should correspond to the in-phase mode, the other to the opposite-phase one).
   • 3. Deduce the critical step of symplectic Euler for m = 0.1, k = 300, and verify it by simulating.

4. ★ Oblique impact. Two spheres of masses 1 and 3 kg, velocities (4, 0) and (-1, 2) m/s, contact with normal \mathbf{n} = (1, 0), e = 0.8, no friction. Compute the post-impact velocities by Theorem 6.2 and check: momentum, restitution, conservation of the tangential components.

5. ★★ Guided stability.

   • 1. Take up the proof of Theorem 3.5 and show that for exactly h\omega = 2, G_{ES} has a double eigenvalue -1 — what does the trajectory become?
   • 2. For \omega = 2, compute the critical step and verify numerically (30 lines of Python) that the energy remains bounded at h = 0.9 and diverges at h = 1.1.
   • 3. Compare the energy drift of EE at h = 0.01 over 1000 steps with the prediction \rho^{2000}.

6. ★★ Quaternions.

   • 1. Show that q and -q give the same rotation (write the conjugation action v \mapsto qvq^{-1}).
   • 2. Compose two 90° rotations about x then y with quaternions; recover the product matrix R_y R_x and its axis-angle.
   • 3. What happens if one naively averages q and -q — why must the signs be aligned before blending?

7. ★★ Guided LBS.

   • 1. Take up the proof of Theorem 7.2 with weights (w, 1-w) and show r'^2/r^2 = w^2 + (1-w)^2 + 2w(1-w)\cos\theta.
   • 2. Evaluate for \theta = 120°, w = 0.5 then w = 0.3.
   • 3. Implement LBS in NumPy on a 16-segment cylinder around an elbow and visualize the collapse; compare with DQS (normalized dual quaternion average).

8. ★★ Damped IK. For the two-segment arm of Example 8.3, implement \Delta\theta = J^\top(JJ^\top + \lambda I)^{-1}\mathbf{e} ; plot the effector trajectory for a target moving on a circle of radius 2.4 (unreachable, since the arm reaches at most L_1 + L_2 = 2); where does it stop and why? Test \lambda \in \{10^{-4}, 10^{-2}, 1\}.

9. ★★ Crowd. Implement the three boids forces (Definition 9.1) with a grid-based neighborhood; tune the weights to observe (a) a coherent flock, (b) fragmentation into subgroups, (c) the instability when separation dominates. Which force corresponds to which stability term of chapter 3?

10. ★★★ Project — mini-garment. A 16 \times 16 grid of masses, structural/shear/bend springs, symplectic then implicit integrator by conjugate gradient, collision with a moving sphere; measure the critical step of each scheme and the achievable real time (frame < 16 ms); conclude on the PBD versus implicit choice for a game.

Projects and assessment

The course sheet summarized above records the official assessment as not displayed: “the 2026-2027 sheet gives no assessment text, and its LLGA section is empty; for the other listed degrees it shows the grade format (out of 20, or letter grade) and that a resit is allowed”. The sheet describes the course as half lectures and half C++/OpenGL lab sessions. The subjects below are proposals of these notes, not official rules: a project can stand for lab or project marks, and the exam proposal for a final written test.

The projects exercise mainly O7 (simulators written from the equations and measured against the theory) and O6 (motion as a generated modality: text-to-motion, faces tracked from video). O4 enters with the mesh-graph surrogate, O1 with the learned components and O3 with the language model that drafts keyframes.

Solo projects

1. [Solo · ≈ 20 h] Integrator zoo: the oscillator theorem on chains and cloth. Do the critical steps predicted from the spectrum of M^{-1}K match the ones a simulator actually shows?
   • Work: explicit, symplectic and implicit Euler, Verlet and RK4 (ch. 2) on 1D chains and on anchored N \times N cloth grids with structural, shear and 2-hop bending springs (ch. 4). Compute \omega_{\max} from the eigenvalues of M^{-1}K (scipy.sparse.linalg.eigsh), predict the critical step (Proposition 4.2), and measure it by bisection on the energy growth of a small-amplitude start over 2000 steps.
   • Data: synthetic only; Examples 4.3 and 4.7 serve as test cases (the zigzag bound 2\sqrt{k/m}, the factor of about 2.3 brought by bending springs five times stiffer).
   • Success criterion: measured critical steps within 2 % of the predictions for symplectic Euler and Verlet at three grid sizes; the RK4 limit h\omega_{\max} \approx 2.83 recovered; energy-drift curves that match the table of chapter 3.
   • Deliverables: code, a 4–6 page report, a 10-minute talk; chapters 2–4, Exercises 3 and 5.
2. [Solo · ≈ 20 h] Paper study: dual quaternion skinning (Kavan, Collins, Žára and O’Sullivan, 2008). How much volume does LBS lose at a twisting and at a bending joint, and what does DQS trade to fix it?
   • Work: LBS (Definition 7.1) and DQS (Definition 7.3) in NumPy on a cylinder of 32 rings around a two-bone joint with smooth weights. Measure the minimum radius against the twist angle, compared with the r\cos(\theta/2) of Theorem 7.2; the enclosed volume (divergence theorem on the closed mesh) in twist and in bend; the bulge of DQS at a 90° bend.
   • Data: the synthetic cylinder; optionally a free Mixamo character driven by a clip of the CMU Graphics Lab Motion Capture Database.
   • Success criterion: the LBS radius within 1 % of r\cos(\theta/2) at weights ½–½; the DQS radius constant under pure twist; the DQS bulge measured, and the paper’s comparison figures reproduced qualitatively.
   • Deliverables: code, report, talk; chapters 5 and 7, Exercises 6 and 7.
3. [Solo · ≈ 20 h] Blendshape weights from video landmarks. Does a bounded least-squares fit on split and corrective targets (Example 7.6) track a face as well as a learned regressor?
   • Data: the open ICT FaceKit face model (USC Institute for Creative Technologies, MIT licence for its light model), whose 53 expression blendshapes follow the ARKit naming, map to FACS action units and are mostly split left and right; landmarks and ARKit-style blendshape scores from MediaPipe Face Landmarker, run on a self-recorded one-minute video.
   • Work: 40–60 landmark–vertex correspondences chosen once; head pose by a similarity (Procrustes) fit; then the weights by scipy.optimize.lsq_linear with bounds [0, 1] and a small temporal smoothness term. Compare with MediaPipe’s own scores, which come from a learned regressor (Definition 7.5).
   • Success criterion: landmark error and frame-to-frame jitter of the fitted weights against those of the regressor’s scores, on frames not used to tune the smoothness weight (the fit minimizes landmark error by construction, so jitter decides); the gain of split and corrective targets over a symmetric basis, measured as in Example 7.6.
   • Deliverables: code, report, talk; chapter 7 (Definition 7.5, Example 7.6) and chapter 1 for temporal filtering.

Group projects

1. [Group of 3 · ≈ 30 h each] Paper study: a learned cloth surrogate (Pfaff, Fortunato, Sanchez-Gonzalez and Battaglia, 2021). Can a mesh-graph network trained on the mini-garment of Exercise 10 replace the semi-implicit step, and at what time step does its rollout stay stable?
   • Data: trajectories from the group’s own simulator — Baraff–Witkin energies and semi-implicit step (Definitions 4.4 and 4.8), collisions with a moving sphere (ch. 6) — over varied sphere paths; the flag_simple dataset released with the MeshGraphNets paper as a second benchmark.
   • Work: an encode–process–decode GNN that predicts per-node accelerations from mesh-space and world-space edges, by the message passing of Graph ML, ch. 5, trained with noise injection; rollouts compared with the reference simulator and with PBD (Definition 6.6).
   • Split: simulator and data generation; GNN and training; evaluation (rollout error, energy, collisions, speed).
   • Success criterion: position RMSE over a 100-step rollout on held-out sphere paths; the largest step at which rollouts stay bounded, against the 2/\omega_{\max} of Proposition 4.2 and the implicit step; wall-clock time per frame.
   • Deliverables: code, an 8–10 page joint report, a 20-minute talk; chapters 3, 4 and 6, Exercise 10.
2. [Group of 3 · ≈ 30 h each] Text-to-motion with physical cleanup. Generated motions often slide their feet and jitter: how much of that can the classical tools of this course remove, without changing what the motion means?
   • Data: HumanML3D (Guo, Zou, Zuo, Wang, Ji, Li and Cheng, 2022), text descriptions of AMASS and HumanAct12 motions (AMASS needs a free research registration), with its standard evaluator.
   • Work: motions from a pretrained text-to-motion diffusion model (MDM, Tevet et al., 2023) and, as a baseline, keyframes (root path, foot contacts, a few joint targets) proposed by an instruction-tuned LLM and interpolated by splines (ch. 1). Then foot-contact detection, damped least-squares IK (Proposition 8.2) to pin the feet, and skinning by LBS or DQS (ch. 7).
   • Split: generation (diffusion model and LLM prompts); cleanup (contacts, IK, filtering); skinning, metrics and figures.
   • Success criterion: foot skating (mean horizontal speed of a foot during contact) cut by at least half, without raising the mean jerk; the HumanML3D text–motion R-precision unchanged within its confidence interval.
   • Deliverables: code, joint report, talk; chapters 1, 7, 8 and 10. It continues Multimodal Generative AI, ch. 8 and the motion priors of Proposition 10.3.
3. [Group of 3 · ≈ 30 h each] Paper study: escape panic and faster-is-slower (Helbing, Farkas and Vicsek, 2000). Does the social-force model of Definition 9.2 reproduce clogging at a narrow exit, and can a learned desired speed beat the best hand-tuned one?
   • Work: social forces with body radii, body compression and sliding friction as in the paper; walls; navigation by A* on a grid or a navmesh (Real-time AI for video games, ch. 2); RVO avoidance as a comparison. Then a policy that sets each agent’s desired speed, trained by policy gradient (Reinforcement Learning, ch. 5) to maximize the evacuation flow.
   • Data: synthetic rooms with a single 1 m exit and about 200 agents; lane formation in a corridor with two opposing flows (Helbing and Molnár, 1995).
   • Split: simulator and integrator (time step chosen from ch. 3); navigation and RVO; RL environment and training.
   • Success criterion: evacuation time against desired speed, with the faster-is-slower minimum reproduced (confidence intervals over 20 seeds); the learned policy’s flow against the best constant speed.
   • Deliverables: code, joint report, talk; chapters 2–3 and 9. The simulator can serve as an extra RL environment in the Y1.2 fleet-dispatch project.

Written exam (proposal)

Two hours, one handwritten A4 sheet and a simple calculator allowed; four exercises: a course question, two computations and a short proof.

1. Question (4 points). A mass m hangs on a spring of stiffness k, with \omega = \sqrt{k/m}. Explain what explicit, symplectic and implicit Euler do to its energy, give the stability condition of each in terms of h\omega, and say which scheme you would choose for effects particles and which for a stiff garment.
   • Expected: explicit Euler has \rho = \sqrt{1 + h^2\omega^2} > 1: the energy grows by the factor 1 + h^2\omega^2 per step, for every h (Theorem 3.2).
   • Symplectic Euler has \det G = 1 and is stable if and only if h\omega < 2, with an energy that oscillates (Theorem 3.5); implicit Euler has \rho = 1/\sqrt{1 + h^2\omega^2}: stable for every h, but damped (Theorem 3.4).
   • Symplectic Euler for cheap particles at frame-rate steps; the semi-implicit step of Definition 4.4 for a stiff garment, where 2/\omega_{\max} would force tiny steps.
2. Question (6 points). A thin rod of mass 2 kg and length 1.2 m falls horizontally, without rotating, at 3 m/s. Only one end lands on a rigid ledge, the rest of the rod overhanging it; restitution e = 0. Using I = Ml^2/12, compute the impulse, the velocity of the center and the angular velocity just after impact, and the energy lost. Compare with a point mass of 2 kg.
   • Expected: I = 0.24 kg·m², lever arm 0.6 m, angular term 0.6^2/0.24 = 1.5 kg⁻¹, denominator 0.5 + 1.5 = 2 (Proposition 6.4), so j = 3/2 = 1.5 N·s.
   • V^+ = -3 + 1.5/2 = -2.25 m/s and |\omega^+| = 1.5 \times 0.6/0.24 = 3.75 rad/s. The end that hit stops, since -2.25 + 3.75 \times 0.6 = 0, as e = 0 requires.
   • Energy: 9 J before, 5.06 + 1.69 = 6.75 J after, so 2.25 J lost, which is \tfrac12 m_{\text{eff}} v_n^2 with m_{\text{eff}} = 0.5 kg. A point mass would receive 6 N·s and lose all 9 J.
3. Question (5 points). Prove that symplectic Euler applied to \ddot{x} = -\omega^2 x is stable, in the sense of Definition 3.1, if and only if 0 < h\omega < 2.
   • Expected: \det G_{ES} = 1 and \mathrm{tr}\,G_{ES} = 2 - h^2\omega^2, so the eigenvalues are the roots of \lambda^2 - 2c\lambda + 1 with c = 1 - h^2\omega^2/2.
   • If |c| < 1, the roots are two distinct conjugates of modulus 1: G_{ES} is diagonalizable and every component stays bounded.
   • If h\omega > 2, then c < -1 and one real root has modulus |c| + \sqrt{c^2 - 1} > 1.
   • If h\omega = 2, the eigenvalue -1 is double but G_{ES} \neq -I, so it is defective: linear growth, unstable.
4. Question (5 points). A planar arm has two segments of length 1. Find both joint configurations that reach the target (0, 1.6) and check one by forward kinematics. Give the Jacobian at that pose and its determinant, and explain why damped least squares (Proposition 8.2) is needed near a fully extended arm.
   • Expected: \cos\theta_2 = (2.56 - 2)/2 = 0.28, so \theta_2 = \pm 73.74° and \sin\theta_2 = \pm 0.96.
   • For \theta_2 = +73.74°: \theta_1 = 90° - \mathrm{atan2}(0.96, 1.28) = 53.13°; the other solution is (126.87°, -73.74°). Forward kinematics: x = 0.6 - 0.6 = 0 and y = 0.8 + 0.8 = 1.6 ✓.
   • At the first pose, J = \begin{pmatrix} -1.6 & -0.8 \\ 0 & -0.6 \end{pmatrix}, \qquad \det J = L_1 L_2 \sin\theta_2 = 0.96 .
   • As the arm straightens, \theta_2 \to 0 and \det J \to 0: the undamped inverse produces huge steps, and the damping \lambda > 0 keeps them bounded.

Grading rubric (proposal)

References

• M. Desbrun, M.-P. Cani (Gascuel), Smoothed Particles: A New Paradigm for Animating Highly Deformable Bodies, EG Workshop on Computer Animation and Simulation, 1996.
• M. Desbrun, M.-P. Cani, Active Implicit Surface for Animation, Graphics Interface, 1998.
• M.-P. Cani, Interactive Sculpting with Implicit Surfaces, Shape Modeling International, 2002; profile People of ACM.
• M. Desbrun, A. Hirani, M. Leok, J. Marsden, Discrete Exterior Calculus, arXiv 2005; M. Desbrun, E. Kanso, Y. Tong, Discrete Differential Forms for Computational Modeling, Springer; K. Crane, F. de Goes, M. Desbrun, P. Schröder, Digital Geometry Processing with Discrete Exterior Calculus, SIGGRAPH Asia Courses 2013 — open notes: DDG.
• C. Reynolds, Flocks, Herds and Schools: A Distributed Behavioral Model, SIGGRAPH 1987 (boids).
• D. Baraff, A. Witkin, Large Steps in Cloth Simulation, SIGGRAPH 1998 (the implicit approach for stiff springs); M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff, Position Based Dynamics, JVCIR 2007 (and XPBD, M. Macklin, M. Müller, N. Chentanez, 2016).
• J. Stam, Stable Fluids, SIGGRAPH 1999 (semi-Lagrangian advection, implicit diffusion, pressure projection).
• L. Kavan, S. Collins, J. Žára, C. O’Sullivan, Geometric Skinning with Approximate Dual Quaternion Blending, ACM TOG 27(4), 2008 (DQS); A. Jacobson, Z. Deng, L. Kavan, J. P. Lewis, Skinning: Real-time Shape Deformation, SIGGRAPH 2014 Courses (skinning survey).
• A. Aristidou, J. Lasenby, FABRIK: A Fast, Iterative Solver for the Inverse Kinematics Problem, Graphical Models 2011; L.-C. T. Wang, C. C. Chen, A Combined Optimization Method for Solving the Inverse Kinematics Problem of Mechanical Manipulators, IEEE Transactions on Robotics and Automation 7(4), 1991 (CCD).
• D. Helbing, P. Molnár, Social Force Model for Pedestrian Dynamics, Physical Review E 51, 1995; D. Helbing, I. Farkas, T. Vicsek, Simulating Dynamical Features of Escape Panic, Nature 407, 2000 (the parameters of Definition 9.2).
• S. Clavet, Motion Matching and The Road to Next-Gen Animation, GDC 2016 (talk; see also M. Büttner, S. Clavet, nucl.ai 2015, and K. Zadziuk, GDC 2016); D. Holden, T. Komura, J. Saito, Phase-Functioned Neural Networks for Character Control, ACM TOG 36(4), SIGGRAPH 2017.
• Project papers: T. Pfaff, M. Fortunato, A. Sanchez-Gonzalez, P. Battaglia, Learning Mesh-Based Simulation with Graph Networks, ICLR 2021; C. Guo et al., Generating Diverse and Natural 3D Human Motions from Text (HumanML3D), CVPR 2022; G. Tevet et al., Human Motion Diffusion Model, ICLR 2023.
• E. Hairer, C. Lubich, G. Wanner, Geometric Numerical Integration, Springer (symplecticity, stability regions); the course notes Discrete Differential Geometry for the geometry/simulation bridge.
• Lab tools: NumPy, Matplotlib, libigl (geometry), engines: Bullet, XPBD/Jolt (open source).