26. Physics Simulation

Chapter 14 gave you the toolbox of physics-based animation: explicit and semi-implicit Euler, Verlet and Runge–Kutta, the spring that explodes, mass–spring cloth, rigid bodies with torque and the inertia tensor, broad and narrow phase, restitution and impulses, grids versus particles for fluids.
It named most of the methods that real engines use and stopped there.
This chapter opens them up.

We'll solve a stiff spring with implicit Euler and see why it never explodes; make rigid bodies tumble correctly, find box contacts with the separating axis test and resolve them with impulses and friction the way game engines do; then switch to position-based dynamics and XPBD, the method behind most real-time cloth.
For fluids we'll read the Navier–Stokes equations term by term, run Stable Fluids on a 2×2 grid by hand, compute an SPH density, and compare PIC, FLIP, APIC and MPM.
We'll end with hair, destruction, GPU physics and determinism.

This is Part 2, beyond the exam syllabus, but it grows directly out of the syllabus item physics-based animation (物理ベースアニメーション) of chapter 14, and the exam points at the end of section 26.5 say where it ties back.
Characters, skinning and ragdolls are chapter 25; rendering smoke and fire as participating media is chapter 28.
The math is the Linear Algebra series: the dot and cross products (chapters 4 and 5), matrix products and the transpose (chapter 7), inverses (chapter 10) and quaternions (chapter 13).

26.1 Time integration revisited

Stiffness

Section 14.2 ended with three escape routes from the exploding spring: smaller steps, damping, and implicit integration.
A simulation is stiff (硬い, スティッフ) when it contains motions on very different time scales: cloth that barely stretches (stretch vibrations of a few milliseconds) but swings slowly (seconds), a car suspension, a stack of heavy boxes.
An explicit method must resolve the fastest motion even when nobody can see it, so the stiffest spring in the scene dictates the time step for everything.

Take the spring of section 14.2 with k=100 N/m and m=1 kg, so ω=k/m=10 rad/s and the period is 2π/10≈0.63 s.
Semi-implicit Euler needs hω<2, that is h<0.2 s.
At h=0.25 s it explodes: x goes 1, −5.25, 21.3, −85.3, 341.3.
A 10 g cloth particle on the same spring has ω=100 rad/s and needs h<0.02 s; real fabric is much stiffer still.

Implicit Euler, worked

The implicit Euler method (陰的オイラー法, also 後退オイラー法, backward Euler) evaluates everything at the end of the step:

xn+1=xn+hvn+1,vn+1=vn+ha(xn+1)=vn−hω2xn+1

The unknowns appear on both sides, so each step means solving equations.
For one linear spring we can do it by hand: substitute the first equation into the second,

vn+1=vn−hω2(xn+hvn+1)⇒vn+1=vn−hω2xn1+h2ω2,xn+1=xn+hvn1+h2ω2

Worked example.
x0=1, v0=0, h=0.25, ω2=100, so hω2=25 and 1+h2ω2=1+6.25=7.25.

  • Step 1: v1=0−25⋅17.25=−3.44828, x1=1+0.25⋅07.25=0.13793.
  • Step 2: v2=−3.44828−25⋅0.137937.25=−0.95125, x2=0.13793+0.25⋅(−3.44828)7.25=−0.09988.

Check step 1 with the first equation: x1=x0+hv1=1−0.86207=0.13793.
The energy E=12mv2+12kx2 starts at 50 J and is 0.5⋅3.448282+50⋅0.137932=5.9453+0.9512=6.8966 J after one step: exactly 507.25.
Every step divides the energy by 1+h2ω2, the mirror image of explicit Euler, which multiplies it by the same number (section 14.2).
So implicit Euler can't explode, whatever the step.
The price is visible in the picture: it loses energy that the real spring keeps.

Two charts of the stiff spring with k = 100 and m = 1 over two seconds. Left, time step 0.1: explicit Euler leaves the chart after three steps, semi-implicit Euler oscillates with a slightly short period, implicit Euler decays to zero within about one second. Right, time step 0.25: explicit and semi-implicit Euler both leave the chart at once, implicit Euler stays bounded and decays to zero

At h=0.1 s (hω=1) the energy halves every step, so after one second (10 steps) only 0.510≈0.001 of it is left: the spring has stopped although it should swing forever.
At a 60 Hz step the loss is 11+100/3600=0.973 per step, still 0.97360≈0.19 after one second.
For cloth this artificial damping is often welcome (fabric is damped anyway); for a pendulum or an orbit it's wrong.
That's the trade: stable, but numerically damped (数値減衰).

Stability regions

Why does one method always grow and the other always shrink?
Numerical analysts study every integrator on the test equation (テスト方程式)

dydt=λy

with a complex number λ.
Its solution y0eλt decays for negative real part and oscillates for imaginary λ.
Applying a method gives yn+1=R(z)yn with z=hλ, and the method is stable when |R(z)|≤1.
The set of such z is the method's stability region (安定領域).

  • Explicit Euler: yn+1=yn+hλyn, so R(z)=1+z. Stable inside the disk of radius 1 around −1.
  • Implicit Euler: yn+1=yn+hλyn+1, so R(z)=11−z. Stable outside the disk of radius 1 around +1, which includes the whole left half-plane. A method with that property is called A-stable (A安定).

A spring with no damping behaves like two test equations with λ=±iω (the eigenvalues of the 2×2 matrix that maps (x,v) to (v,−ω2x)).
Then z=±ihω lies on the imaginary axis, and

|1+ihω|=1+h2ω2>1,|11−ihω|=11+h2ω2<1

Their squares are the energy factors we've seen; the imaginary axis touches the explicit disk only at 0, so explicit Euler is unstable for an undamped spring at every step size.

Two complex planes. Left: the stability region of explicit Euler, a disk of radius 1 centered at minus 1; the spring points plus and minus i lie outside it, and so does a damper at minus 3.33. Right: the stability region of implicit Euler, everything outside the disk of radius 1 centered at plus 1; all three points lie inside the stable region

Damping is a real negative λ: a damper with c=200 N·s/m on 1 kg has λ=−c/m=−200, so at 60 Hz z=−3.33.
Explicit Euler multiplies the velocity by 1+z=−2.33 per step, a damper that adds energy (it would need h≤2m/c=0.01 s); implicit Euler multiplies it by 11+3.33=0.23, a calm decay.
(Semi-implicit Euler's step matrix for the spring has eigenvalues of length exactly 1 while hω<2: the bounded energy of section 14.2.)

The implicit midpoint rule (陰的中点法), R(z)=1+z/21−z/2, is stable on exactly the left half-plane and has |R|=1 on the imaginary axis: it keeps a linear spring's energy exactly, for the same solving cost.

Implicit integration in practice

A real scene has thousands of particles and nonlinear forces (a spring's force depends on the direction between its ends).
Then 𝐯n+1=𝐯n+h𝐌−1𝐟(𝐱n+1,𝐯n+1) is a large nonlinear system, solved with Newton's method (ニュートン法): linearize the forces around the current state and solve the linear system, once or a few times.
Baraff and Witkin (1998, cited in section 14.2) take one Newton step per time step:

(𝐌−h∂𝐟∂𝐯−h2∂𝐟∂𝐱)Δ𝐯=h(𝐟0+h∂𝐟∂𝐱𝐯0)

𝐌 is the (diagonal) mass matrix, ∂𝐟∂𝐱 the stiffness matrix (剛性行列): how every force changes when every position moves a little.
For our 1D spring (∂f∂x=−100, ∂f∂v=0) it gives 7.25Δv=−25, the same v1 as above.
For a cloth, the matrix has one 3×3 block per spring end, so it's huge but sparse (疎), and it's solved iteratively with the conjugate gradient method (共役勾配法).
Film cloth and hair solvers work this way; games mostly use the cheaper position-based methods of section 26.3.

26.2 Rigid bodies in depth

The state, and the inertia tensor in world space

Section 14.5 gave a rigid body a position 𝐱, a velocity 𝐯, an orientation and an angular velocity 𝝎, and related torque to angular acceleration through the inertia tensor (慣性テンソル) 𝐈.
Two details make or break a rigid-body simulator.

First, 𝐈 is constant only in the body's own coordinates.
For a box of mass m with side lengths w, h, d along its local x, y, z axes, it's diagonal:

𝐈body=m12[h2+d2000w2+d2000w2+h2]

When the body rotates by the matrix 𝐑, its inertia seen from the world changes:

𝐈world=𝐑𝐈body𝐑⊤,𝐈world−1=𝐑𝐈body−1𝐑⊤

(Read it right to left: rotate a world vector into body space, apply the body inertia, rotate back. The inverse is cheap because 𝐑−1=𝐑⊤ for a rotation, Linear Algebra chapter 10.)
Engines store 𝐈body−1 once and rebuild 𝐈world−1 every step.

Worked example.
A box of m=12 kg, 2×1×1 m: 𝐈body=diag(1⋅(1+1),1⋅(4+1),1⋅(4+1))=diag(2,5,5) kg·m².
Rotate it by 45° about z; with c=s=22, the upper-left 2×2 block becomes

[2c2+5s2(2−5)cs(2−5)cs2s2+5c2]=[3.5−1.5−1.53.5]

and Izz=5 is unchanged.
Now give it the angular momentum (角運動量) 𝐋=(1,0,0), a spin about the world x axis.
The angular velocity is 𝝎=𝐈world−1𝐋; the inverse of the 2×2 block is 13.52−1.52[3.51.51.53.5]=[0.350.150.150.35], so

𝝎=(0.35,0.15,0)

The box doesn't spin about the axis you pushed it around: 𝝎 is 23° away from 𝐋.
Only about the three principal axes (慣性主軸), the body's own x, y and z here, are 𝐋 and 𝝎 parallel.
That's why a thrown book wobbles.

Second, with 𝐈 changing, the rotational version of 𝐅=m𝐚 gets an extra term (Euler's equations):

𝝉=𝐈𝝎˙+𝝎×(𝐈𝝎)

The gyroscopic term (ジャイロ項) 𝝎×(𝐈𝝎) makes a spinning racket tumble.
It's quadratic in 𝝎, and semi-implicit Euler can pump energy into it until a fast, elongated body blows up, so engines either drop it (stable but "too stable") or integrate it implicitly with one Newton step, as Erin Catto showed in his GDC 2015 talk on numerical methods.

Integrating the orientation

Section 14.5 updated the orientation quaternion with 𝐪←𝐪+h2(0,𝝎)𝐪 and renormalized it.
This is explicit Euler applied to the quaternion derivative 𝐪˙=12(0,𝝎)𝐪, with 𝝎 in world space and the Hamilton product of Linear Algebra chapter 13.

Worked example.
Start at the identity 𝐪=(1,0,0,0) (written (w,x,y,z)) and spin about z with 𝝎=(0,0,2) rad/s for h=0.1 s.
(0,0,0,2)(1,0,0,0)=(0,0,0,2), so 𝐪+0.05⋅(0,0,0,2)=(1,0,0,0.1).
Its length is 1.01=1.004988; normalized it's (0.995037,0,0,0.099504).
A unit quaternion (cosθ2,sinθ2𝐚^) rotates by θ, so this is θ=2arctan0.0995040.995037=0.19934 rad, where the exact answer is ωh=0.2 rad.
The body spins 0.3% too slowly, and without the normalization the length would grow by 1.004988 per step.
The exact alternative is the exponential map: multiply 𝐪 from the left by the rotation by ‖𝝎‖h about 𝝎^, here (cos0.1,0,0,sin0.1).

Contact generation: the separating axis test

Chapter 14 named the narrow phase's job: find the contact points, the contact normal and the penetration depth.
For convex polygons and polyhedra the classic tool is the separating axis theorem (分離軸定理, SAT): two convex shapes don't overlap if and only if there is an axis on which their projections (their "shadows") don't overlap.
For polygons in 2D, it's enough to test the edge normals of both shapes; for boxes that means the two axes of each box.

Projecting a box with center 𝐜, unit axes 𝐮, 𝐯 and half-extents eu, ev onto a unit axis 𝐧 gives an interval centered at 𝐜⋅𝐧 with the radius

r=eu|𝐮⋅𝐧|+ev|𝐯⋅𝐧|

and two boxes overlap on that axis by rA+rB−|(𝐜B−𝐜A)⋅𝐧|; a negative value is a gap.

Worked example.
Box A sits at the origin, axis-aligned, with half-extents (2,1).
Box B has half-extents (1,0.5) and is rotated so that its axes are 𝐮B=(0.8,0.6) and 𝐯B=(−0.6,0.8) (an angle of about 36.9°).
On the four axes, A's radii are 2, 1, 2⋅0.8+1⋅0.6=2.2 and 2⋅0.6+1⋅0.8=2.0; B's are 1⋅0.8+0.5⋅0.6=1.1, 1⋅0.6+0.5⋅0.8=1.0, 1 and 0.5.

Axis rA rB B at (3, 1.8): distance, overlap B at (2.5, 1.5): distance, overlap
(1,0) 2 1.1 3, 0.1 2.5, 0.6
(0,1) 1 1.0 1.8, 0.2 1.5, 0.5
𝐮B 2.2 1 3.48, −0.28 2.9, 0.3
𝐯B 2.0 0.5 0.36, 2.14 0.3, 2.2

With B centered at (3,1.8), the distance along 𝐮B is 3⋅0.8+1.8⋅0.6=3.48, more than 2.2+1=3.2: a gap of 0.28, so the boxes are separate, although they overlap on both of A's axes (which is all an AABB test would look at).
With B at (2.5,1.5), all four axes overlap, so the boxes collide.
The axis of smallest overlap is the contact normal, 𝐧=𝐮B=(0.8,0.6) (pointing from A to B because (𝐜B−𝐜A)⋅𝐮B>0), and the overlap 0.3 is the penetration depth: moving B by 0.3𝐧 separates them.

Two panels with an axis-aligned box A and a rotated box B. Left: B at 3, 1.8; the projections of both boxes on the x axis overlap by 0.1, but their projections on B&

The normal and depth aren't enough for a box resting on a box: a single contact point would let it rock.
Engines build a contact manifold (接触点の集合, コンタクトマニフォールド) of up to 2 points in 2D (4 in 3D) by clipping.
The axis came from B, so the face of B facing A is the reference face (参照面), with outward normal −𝐮B.
The face of A most anti-parallel to it, A's right edge from (2,−1) to (2,1) (its normal (1,0) has the largest dot product with 𝐮B, 0.8), is the incident face (入射面).
Clip the incident edge to the side planes of the reference face, exactly like Sutherland–Hodgman clipping in chapter 6, section 6.3: in B's coordinates a point (2,y) has v=(𝐩−𝐜B)⋅𝐯B=0.8y−0.9, and the side plane v≥−0.5 cuts the edge at y=0.5.
Keep the clipped points that lie behind the reference face: (2,1) has u=(𝐩−𝐜B)⋅𝐮B=−0.7, so it's 1−0.7=0.3 deep; (2,0.5) has u=−1.0, depth 0, just touching.
Two contact points, one deep and one touching: enough to keep B from rotating into A.

In 3D, two boxes have 15 candidate axes: 3 face normals of each box plus the 9 cross products of an edge of A with an edge of B (two edges can hit each other without any face being involved).

GJK and EPA

SAT needs the list of candidate axes, which is fine for boxes and convex polygons but not for spheres, capsules or arbitrary convex hulls.
The Gilbert–Johnson–Keerthi algorithm (GJK; Gilbert, Johnson and Keerthi, 1988) works with any convex shape that can answer one question, its support function (サポート関数): which point of the shape lies farthest in a given direction 𝐝?
For a sphere it's 𝐜+r𝐝^; for a box, the corner on the side of 𝐝.

The trick is the Minkowski difference (ミンコフスキー差) A−B={𝐚−𝐛}, the set of all differences of a point of A and a point of B.
A and B overlap exactly when some 𝐚=𝐛, that is, when the origin lies inside A−B.
Its support function is sA−B(𝐝)=sA(𝐝)−sB(−𝐝), so we never build A−B.
GJK grows a simplex (a point, a segment, a triangle, a tetrahedron) of support points of A−B towards the origin; if it encloses the origin, the shapes overlap; if a support point can't get past the origin, they're separate and the closest simplex feature gives the distance.
When they overlap, the expanding polytope algorithm (EPA, van den Bergen, 2001) inflates the final simplex into a polytope until it finds the face of A−B closest to the origin: its normal is the contact normal and its distance the penetration depth.

For our colliding boxes and 𝐝=𝐮B: sA⋅𝐝=(2,1)⋅𝐮B=2.2 and sB(−𝐝)⋅𝐝=(𝐜B−𝐮B)⋅𝐮B=1.9, so A−B reaches 0.3 past the origin in that direction: the depth SAT found, which EPA finds as the minimum over all directions.

Contact constraints and impulses

Section 14.6 resolved a head-on collision with one impulse along the normal.
With rotation, the velocity that matters is the velocity of the contact point, 𝐯+𝝎×𝐫, where 𝐫 is the offset from the center of mass to the contact.
A contact constraint (接触拘束) says that this point must not move into the other object, vn=(𝐯+𝝎×𝐫)⋅𝐧≥0, and that the contact may push but never pull: the normal impulse λn≥0.
An impulse λ along a direction 𝐧 at 𝐫 changes both velocities:

Δ𝐯=λm𝐧,Δ𝝎=λ𝐈−1(𝐫×𝐧)

and so changes vn by λ/meff with the effective mass (有効質量)

1meff=1m+(𝐫×𝐧)⋅𝐈−1(𝐫×𝐧)

(plus the same terms for the second body when it isn't static).
To stop the approach completely (e=0), apply λn=−meffvn.

Friction follows Coulomb's law (クーロン摩擦): the tangential impulse may be at most μ times the normal one, |λt|≤μλn.
In 3D, the allowed contact impulses form the friction cone (摩擦円錐) around the normal, with half-angle arctanμ; engines usually approximate it with two tangent directions, a four-sided pyramid.
Inside the cone the contact sticks; on its surface it slides.

Worked example.
A crate (2D, a unit square with m=1 kg and I=m(12+12)12=16 kg·m²) falls with 𝐯=(0,−2) m/s onto a thin post that catches it under its bottom-right corner, 𝐫=(0.5,−0.5), 𝐧=(0,1), 𝐭=(1,0), μ=0.5, e=0.
In 2D the cross product 𝐫×𝐧=rxny−rynx is a number, here 0.5, and 𝝎×𝐫=ω(−ry,rx)=ω(0.5,0.5).

A square crate with its center marked, falling with velocity 0, minus 2 onto a thin post under its bottom-right corner. The offset r from the center to the contact is 0.5, minus 0.5, the normal n points up and the tangent t to the right

  • Effective masses: 1meff=1+0.52⋅6=2.5 for the normal, and the same for the tangent (𝐫×𝐭=0−(−0.5)(1)=0.5).
  • Normal: vn=−2, so λn=2/2.5=0.8. Then 𝐯=(0,−1.2) and ω=6⋅0.5⋅0.8=2.4 rad/s. The corner now has vn=−1.2+2.4⋅0.5=0: stopped.
  • Friction: the corner slides with vt=0+2.4⋅0.5=1.2 m/s. Stopping it would need λt=−1.2/2.5=−0.48, but Coulomb allows only μλn=0.4, so λt=−0.4: the corner keeps sliding. Then 𝐯=(−0.4,−1.2) and ω=2.4+6⋅0.5⋅(−0.4)=1.2.

But now the corner moves into the post again: vn=−1.2+1.2⋅0.5=−0.6.
The friction impulse took away spin that the normal impulse relied on: solving one constraint broke the other, so we iterate.

Sequential impulses and projected Gauss–Seidel

Game engines visit the constraints one at a time, apply the impulse that fixes the current one, and sweep over all of them several times.
Erin Catto popularized it as sequential impulses (シーケンシャルインパルス) in his GDC talks ("Iterative Dynamics with Temporal Coherence", 2005; "Fast and Simple Physics using Sequential Impulses", 2006), the solver of Box2D.
Mathematically it's the projected Gauss–Seidel method (射影ガウス=ザイデル法, PGS): Gauss–Seidel iteration on the linear system of all contacts, with each unknown projected back into its allowed range after its update.

The key rule: keep an accumulated impulse per contact for the whole step and clamp the accumulated value, not each increment.
An increment may be negative (taking back some of an impulse that turned out too large); only the total must stay ≥0 for the normal and inside ±μλn for friction.
Continuing the crate:

Iteration λn total λt total 𝐯 ω vn after
1 0.8 −0.4 (−0.4, −1.2) 1.2 −0.6
2 1.04 −0.52 (−0.52, −0.96) 1.56 −0.18
3 1.112 −0.556 (−0.556, −0.888) 1.668 −0.054
4 1.1336 −0.5668 (−0.5668, −0.8664) 1.7004 −0.0162
exact 8/7 ≈ 1.1429 −4/7 ≈ −0.5714 (−0.5714, −0.8571) 12/7 ≈ 1.7143 0

The error shrinks by the factor 0.3 per iteration.
The exact answer comes from solving both conditions together: the contact slides, so λt=−μλn=−0.5λn; then ω=6⋅0.5(λn+λt)=1.5λn and vn=−2+λn+0.5⋅1.5λn=−2+1.75λn=0 gives λn=87.
The corner then slides at vt=−47+0.5⋅127=27 m/s to the right, and friction pushes left, as it should.

With many contacts convergence is slower (in a tall stack the top box's weight must travel down through every contact), so engines run a fixed number of iterations, typically 4 to 20, and accept the remaining error.

#include <algorithm>
#include <cstdio>
#include "linalg.hh"

// 2D cross products: r x n is a scalar, w x r is a vector.
float cross2(Vec2 a, Vec2 b) { return a.x * b.y - a.y * b.x; }
Vec2 crossW(float w, Vec2 r) { return {-w * r.y, w * r.x}; }

struct Body {
  float invMass, invInertia;
  Vec2 v;
  float w;  // angular velocity (rad/s, counter-clockwise)
};

// One contact point at offset r from the center, normal n, tangent t, against a static object.
struct Contact {
  Vec2 r, n, t;
  float mu;
  float Pn = 0.0f, Pt = 0.0f;  // accumulated impulses (keep them for warm starting)
};

void applyImpulse(Body &b, Vec2 r, Vec2 dir, float lambda) {
  b.v = b.v + (lambda * b.invMass) * dir;
  b.w += b.invInertia * cross2(r, dir) * lambda;
}

void solveContact(Body &b, Contact &c) {
  // normal: effective mass 1 / (1/m + (r x n)^2 / I)
  float rn = cross2(c.r, c.n);
  float kn = b.invMass + rn * rn * b.invInertia;
  float vn = dot(b.v + crossW(b.w, c.r), c.n);
  float old = c.Pn;
  c.Pn = std::max(old - vn / kn, 0.0f);  // clamp the accumulated impulse: never pull
  applyImpulse(b, c.r, c.n, c.Pn - old);
  // friction: Coulomb, |Pt| <= mu * Pn
  float rt = cross2(c.r, c.t);
  float kt = b.invMass + rt * rt * b.invInertia;
  float vt = dot(b.v + crossW(b.w, c.r), c.t);
  old = c.Pt;
  c.Pt = std::clamp(old - vt / kt, -c.mu * c.Pn, c.mu * c.Pn);
  applyImpulse(b, c.r, c.t, c.Pt - old);
}

int main() {
  Body crate{1.0f, 6.0f, {0.0f, -2.0f}, 0.0f};  // m = 1 kg, I = 1/6 kg m^2
  Contact c{{0.5f, -0.5f}, {0.0f, 1.0f}, {1.0f, 0.0f}, 0.5f};
  for (int it = 1; it <= 5; ++it) {
    solveContact(crate, c);
    float vn = dot(crate.v + crossW(crate.w, c.r), c.n);
    printf("iteration %d: Pn %.4f  Pt %.4f  v (%.4f, %.4f)  w %.4f  vn %.4f\n", it, c.Pn, c.Pt,
           crate.v.x, crate.v.y, crate.w, vn);
  }
  return 0;
}

It prints iterations 1 to 4 of the table above and a fifth one with λn=1.1401, vn=−0.0049.

Joints and motors

The ragdolls of chapter 25, section 25.6 are rigid bodies held together by joints (ジョイント), constraints solved in the same sweeps as the contacts.
A ball joint keeps an anchor point of each body together: the anchor velocities 𝐯A+𝝎A×𝐫A and 𝐯B+𝝎B×𝐫B must be equal, three equations along x, y and z, each with the effective mass above but without clamping, because a joint may pull as well as push.
A hinge adds two angular constraints that leave one rotation axis free; a joint limit is an inequality like a contact, active only at the limit.
A motor (モーター) is a velocity constraint with a target, such as "the relative angular velocity about the hinge axis is ωtarget", whose accumulated impulse is clamped to ±τmaxh so that it has a finite strength; a PD controller acts instead as a soft spring towards the target angle, like the compliance of section 26.3.

Penetration, warm starting, stacking and sleeping

Velocity impulses stop bodies from moving further into each other, but existing penetration stays and accumulates.
The classic fix, Baumgarte stabilization (バウムガルテ安定化), asks for a small separating velocity proportional to the depth instead of vn=0:

vn≥βhmax(d−dslop,0)

The slop (許容めり込み, スロップ) dslop lets a few millimeters of overlap stay, so resting contacts don't flicker between touching and not touching; β around 0.1 to 0.3 corrects the rest gently over several steps.
With β=0.2, h=160 s, a depth of 2 cm and a slop of 0.5 cm, the target is 0.2⋅60⋅0.015=0.18 m/s.
The bias adds energy (boxes "pop" apart), so many engines correct positions in a separate pass or use soft constraints like the compliance of section 26.3.

Warm starting (ウォームスタート): contacts persist between frames (matched by feature IDs such as "vertex 2 of A against face 1 of B"), so each step starts by applying last step's accumulated impulses; in a resting stack they barely change, so the iteration starts almost at the answer.
Stable stacking (積み重ね), the classic benchmark of a rigid-body engine, also needs a good contact manifold, enough iterations and solving from the ground up.

Sleeping (スリープ): bodies whose linear and angular speeds stay below a small threshold for some time (for example about half a second) are frozen and skipped until something touches them.
Touching bodies form an island (アイランド) that sleeps and wakes together; in a typical level almost everything sleeps almost all the time, which makes thousands of bodies affordable.

Against tunneling (section 14.6), continuous collision detection finds the time of impact, for example by conservative advancement: repeatedly advance by a step that the GJK distance proves safe.

26.3 Position-based dynamics

The idea

Forces and impulses change velocities and let positions follow.
Position-based dynamics (位置ベース動力学, PBD; Müller, Heidelberger, Hennix and Ratcliff, VRIPHYS 2006, journal version 2007) turns this around: it moves the positions directly so that the constraints hold, and derives the velocities from how far the positions moved.
It systematizes the Verlet cloth and ragdolls of Thomas Jakobsen's "Advanced Character Physics" (2001, for IO Interactive's Hitman: Codename 47).
Each step:

  1. Predict: 𝐯i←𝐯i+hwi𝐟ext,i, then 𝐩i=𝐱i+h𝐯i. Here wi=1/mi is the inverse mass (逆質量); a pinned particle has wi=0.
  2. Project the constraints: for a fixed number of iterations, visit every constraint (distances, bending, collisions) and move its particles 𝐩i so that it holds, Gauss–Seidel style.
  3. Update: 𝐯i=(𝐩i−𝐱i)/h and 𝐱i=𝐩i; then apply friction and restitution to colliding particles.

Nothing can explode: a projection never moves a particle farther than the constraint error, and the velocity is whatever motion actually happened.
That robustness is why PBD took over game cloth, ropes, soft bodies and particles.

Projecting a distance constraint

A constraint (拘束) is a function C(𝐩1,…,𝐩n) that should be 0.
For two particles that must stay d apart, C=‖𝐩1−𝐩2‖−d.
PBD moves the particles along the gradient of C (the direction that changes C fastest), weighted by inverse mass so that heavy particles move less and momentum is conserved:

Δ𝐩i=−swi∇𝐩iC,s=C∑jwj‖∇𝐩jC‖2

For the distance constraint, ∇𝐩1C=𝐧^=𝐩1−𝐩2‖𝐩1−𝐩2‖ and ∇𝐩2C=−𝐧^, both of length 1, so

Δ𝐩1=−w1w1+w2C𝐧^,Δ𝐩2=+w2w1+w2C𝐧^

Worked example (the spring of section 14.4 as a rigid rod).
𝐩1=(0,0), 𝐩2=(3,4), rest length d=4: the distance is 5, C=1, 𝐧^=(−0.6,−0.8).

  • Equal masses, w1=w2=1: Δ𝐩1=−0.5⋅1⋅(−0.6,−0.8)=(0.3,0.4) and Δ𝐩2=(−0.3,−0.4). New positions (0.3,0.4) and (2.7,3.6), distance 2.42+3.22=4.
  • 𝐩1 pinned, w1=0: only 𝐩2 moves, by the full (−0.6,−0.8), to (2.4,3.2).
  • w1=1, w2=3 (the second particle is three times lighter): 𝐩1 moves a quarter of the correction, to (0.15,0.2), 𝐩2 three quarters, to (2.55,3.4), and the center of mass stays put.

Three panels with the segment from 0, 0 to 3, 4 and its corrected version. Left, equal masses: both ends move toward each other, to 0.3, 0.4 and 2.7, 3.6. Middle, p1 pinned: only p2 moves, to 2.4, 3.2. Right, XPBD with compliance: the ends move only to 0.2, 0.267 and 2.8, 3.73

One constraint is solved exactly in one projection; a cloth has thousands that share particles, and fixing one breaks its neighbors, so PBD sweeps over all of them several times, exactly like the sequential impulses above (it's a nonlinear Gauss–Seidel iteration).

Stiffness depends on the iteration count

To make a constraint soft, PBD multiplies each correction by a stiffness k∈[0,1].
But the correction is applied in every iteration, so after n iterations the remaining error is (1−k)n: with k=0.5 that's 0.5 after one iteration, 0.0625 after 4, and 0.000015 after 16.
The same material gets stiffer when you raise the iteration count, and it also changes with the time step.
The PBD paper compensates with k′=1−(1−k)1/n (for k=0.5 and n=4, k′=0.159, and (1−0.159)4=0.5), which fixes the iteration dependence but not the time-step dependence.
The cloth below shows the effect: the same simulation (a 1.2 m cloth of 13×13 particles hanging from two corners, structural and shear distance constraints with k=1, three seconds at 60 Hz) with 1, 4 and 16 iterations per step.

The same PBD cloth hanging from its two top corners after three seconds, with 1, 4 and 16 iterations per step. With 1 iteration it stretches to about 1.5 m and its springs up to 105 percent; with 4 iterations to about 1.28 m and 28 percent; with 16 iterations to about 1.22 m and 7 percent. The color of each edge shows its stretch, from green for none to red for 15 percent or more

Even with "rigid" constraints, an iterative solver that stops early leaves the cloth stretchy, most of all near the pins, which carry the weight of everything below them.
Few iterations make rubber, many make cotton, and the result also depends on the resolution.

XPBD: compliance

XPBD (extended position-based dynamics; Macklin, Müller and Chentanez, Motion in Games 2016) fixes this by giving each constraint a physical compliance (コンプライアンス) α, the inverse of its stiffness (α=1/k in m/N for a spring; 0 for a rigid rod), and by accumulating a Lagrange multiplier (ラグランジュ乗数) λ per constraint, which is the constraint's impulse.
With α~=α/h2, each projection computes

Δλ=−C−α~λ∑jwj‖∇𝐩jC‖2+α~,λ←λ+Δλ,Δ𝐩i=wi∇𝐩iCΔλ

and λ is reset to 0 at the start of each step.
With α=0 this is exactly the PBD projection.

Worked example.
The same two particles, now joined by a spring with k=100 N/m, so α=0.01 m/N; with h=0.1 s, α~=0.01/0.01=1.
First iteration: Δλ=−1−02+1=−13, so Δ𝐩1=1⋅(−0.6,−0.8)⋅(−13)=(0.2,0.2667) and Δ𝐩2=(−0.2,−0.2667).
The new length is 4.3333, so C=13.
Second iteration: Δλ=−13−1⋅(−13)3=0: nothing changes, however many iterations follow.
The answer is a balance, not a projection: each particle was pulled 13 m away from where inertia wanted it, which takes the force m⋅1/3h2=33.3 N, and the spring stretched by 13 m pulls with kC=100⋅13=33.3 N.
That's one implicit Euler step of the spring, solved by projection, and its result no longer depends on the iteration count: more iterations only bring a large system closer to the same answer.

Macklin and coworkers later showed ("Small Steps in Physics Simulation", SCA 2019) that many substeps with one iteration each beat few steps with many iterations at the same cost.

#include <cstdio>
#include "linalg.hh"

// XPBD distance constraint C = |p1 - p2| - d between two particles with inverse masses w1, w2.
// alpha is the compliance (1 / stiffness), h the time step, lambda the accumulated multiplier.
// With alpha = 0 this is exactly the PBD projection.
void solveDistance(Vec3 &p1, Vec3 &p2, float w1, float w2, float d, float alpha, float h,
                   float &lambda) {
  Vec3 delta = p1 - p2;
  float len = length(delta);
  if (len < 1e-9f || w1 + w2 == 0.0f) return;
  Vec3 n = delta / len;             // gradient of C with respect to p1
  float C = len - d;
  float alphaTilde = alpha / (h * h);
  float dLambda = (-C - alphaTilde * lambda) / (w1 + w2 + alphaTilde);
  lambda += dLambda;
  p1 = p1 + (w1 * dLambda) * n;
  p2 = p2 - (w2 * dLambda) * n;
}

int main() {
  const float alphas[] = {0.0f, 0.01f};  // rigid (PBD) and a spring of k = 100 N/m
  for (float alpha : alphas) {
    Vec3 p1{0, 0, 0}, p2{3, 4, 0};
    float lambda = 0.0f;
    for (int it = 1; it <= 2; ++it) {
      solveDistance(p1, p2, 1.0f, 1.0f, 4.0f, alpha, 0.1f, lambda);
      printf("alpha %.2f, iteration %d: p1 (%.4f, %.4f)  p2 (%.4f, %.4f)  "
             "length %.4f  lambda %.4f\n",
             alpha, it, p1.x, p1.y, p2.x, p2.y, length(p2 - p1), lambda);
    }
  }
  return 0;
}

With α=0 it prints the PBD result (length 4.0000, λ=−0.5), with α=0.01 the XPBD result (length 4.3333, λ=−0.3333), and the second iteration changes nothing in either case.

Cloth with PBD

A PBD cloth uses the same particle grid as the mass–spring cloth of section 14.4, with constraints instead of springs:

  • Stretch (伸び): distance constraints along the structural edges (and shear edges or a triangle area constraint against shearing).
  • Bending (曲げ): either distance constraints that skip a particle, like bend springs, or a constraint on the dihedral angle (二面角) between neighboring triangles, which is independent of stretching.
  • Collisions: inequality constraints C≥0 that are projected only while violated, for example C=(𝐩−𝐪)⋅𝐧−thickness against a body surface or a signed distance field (chapter 21), and particle–triangle constraints for self-collision.

A Verlet cloth is the same thing written with Verlet integration: the velocity hides in 𝐱n−𝐱n−1, so relaxing the constraints by moving positions updates it by itself.

Long before PBD, Provot (Graphics Interface 1995) fixed stretchy mass–spring cloth with strain limiting (ひずみ制限): after each step, any spring stretched by more than a critical rate (10% for his hanging sheet) has its ends moved back to exactly that limit, both ends if both are free, only the free one if the other is pinned.
That's a PBD projection of the inequality ‖𝐩1−𝐩2‖≤1.1d, and cloth solvers still combine soft springs with such hard limits.

Shape matching

For soft objects that should spring back to a rest shape (jelly, cartoon squash and stretch), shape matching (シェイプマッチング; Müller, Heidelberger, Teschner and Gross, "Meshless Deformations Based on Shape Matching", SIGGRAPH 2005) needs no mesh at all.
Each step it finds the rigid motion (rotation 𝐑 and translation) that best matches the rest positions 𝐪i to the current positions 𝐱i, and pulls every particle a fraction α of the way towards its goal position 𝐠i:

𝐜=∑mi𝐱i∑mi,𝐀=∑imi(𝐱i−𝐜)(𝐪i−𝐜0)⊤,𝐠i=𝐑(𝐪i−𝐜0)+𝐜

where 𝐜0 is the rest center of mass and 𝐑 the rotation part of 𝐀 (its polar decomposition (極分解) 𝐀=𝐑𝐒).
In 2D the rotation angle is simply θ=atan2(A21−A12,A11+A22).

Worked example.
A square of four unit masses rests at 𝐪=(−1,−1),(1,−1),(1,1),(−1,1), so 𝐜0=(0,0).
It has rotated by 90° and been dented: 𝐱=(1,−1),(1,1),(−0.4,0.4),(−1,−1).
The center is 𝐜=(0.6,−0.6)4=(0.15,−0.15), and the offsets 𝐱i−𝐜 are (0.85,−0.85), (0.85,1.15), (−0.55,0.55), (−1.15,−0.85).
Summing the outer products with the 𝐪i:

A11=−0.85+0.85−0.55+1.15=0.6,A12=−0.85−0.85−0.55−1.15=−3.4
A21=0.85+1.15+0.55+0.85=3.4,A22=0.85−1.15+0.55−0.85=−0.6

so θ=atan2(6.8,0)=90°: the dent didn't fool it.
The goals are the rest square rotated by 90° and moved to 𝐜: (1.15,−1.15), (1.15,0.85), (−0.85,0.85), (−0.85,−1.15).
With α=0.5, the dented corner moves from (−0.4,0.4) halfway to its goal, to (−0.625,0.625).

A dashed rest square with corners q1 to q4, the current dented quadrilateral x1 to x4 that is the rest square turned by 90 degrees with x3 pushed in, and the goal square g, the rest square rotated by 90 degrees and centered on the current center c. An arrow pulls x3 back out to its goal

Matching with the full matrix 𝐀 instead of 𝐑 allows stretching modes, and overlapping clusters give local wobble.

The finite element method, briefly

Mass–spring systems and PBD are fast, but their stiffness depends on the mesh, and it's hard to say "this is rubber".
The finite element method (有限要素法, FEM) starts from continuum mechanics instead.
The material is split into tetrahedra (in 2D, triangles), and inside each element the deformation is assumed to be linear, described by the deformation gradient (変形勾配)

𝐅=𝐃s𝐃m−1

where the columns of 𝐃m are the element's edge vectors at rest and those of 𝐃s the same edges now.
Strain (ひずみ) measures the deformation, stress (応力) the internal force per area, and linear elasticity connects them with Hooke's law in matrix form, using Young's modulus (ヤング率; roughly 0.01 to 0.1 GPa for rubber, 200 GPa for steel) and Poisson's ratio (ポアソン比; how much the material thins when stretched, near 0.5 for rubber).

Worked example.
A 2D triangle with rest corners (0,0), (1,0), (0,1) has 𝐃m=𝐈.
Stretched to (1.1,0) in x, 𝐅=diag(1.1,1) and the linear strain 𝜺=12(𝐅+𝐅⊤)−𝐈=diag(0.1,0).
Now only rotate it by 90°, to (0,0), (0,1), (−1,0): 𝐅=[0−110] and 𝜺=diag(−1,−1), a 100% compression for a triangle that isn't deformed at all.
Linear FEM therefore produces ghost forces for spinning objects.
Corotational FEM (共回転FEM) removes the rotation first with the polar decomposition of shape matching (𝐅=𝐑𝐒, strain from 𝐒−𝐈); nonlinear models use the Green strain 12(𝐅⊤𝐅−𝐈), which is 0 for any rotation.
The element forces assemble into the sparse stiffness matrix of section 26.1 and are integrated implicitly; film uses FEM for muscles and flesh, and at the time of writing PhysX offers GPU FEM soft bodies.

26.4 Fluids in depth

The Navier–Stokes equations, term by term

For a fluid with velocity field 𝐮(𝐱,t), pressure p, constant density ρ and kinematic viscosity ν, the incompressible Navier–Stokes equations (ナビエ・ストークス方程式) of section 14.7 read

∂𝐮∂t=−(𝐮⋅∇)𝐮−1ρ∇p+ν∇2𝐮+𝐟,∇⋅𝐮=0

∇ ("nabla") is the vector of partial derivatives (∂∂x,∂∂y,∂∂z), and each term is one physical effect:

  • −(𝐮⋅∇)𝐮, advection (移流): the fluid carries its own velocity along. It's the reason for swirls and the hard, nonlinear part.
  • −1ρ∇p, pressure (圧力): fluid is pushed from high to low pressure. Pressure is whatever it must be to keep the fluid incompressible.
  • ν∇2𝐮, viscosity (粘性): velocity diffuses to the neighbors; ∇2 (the Laplacian, ラプラシアン) is "the average of the neighbors minus me". Honey has a large ν, air a tiny one.
  • 𝐟: external forces such as gravity, buoyancy or a stirring hand.
  • ∇⋅𝐮=0: the divergence (発散), the net outflow per volume, is zero. What flows into a cell must flow out: incompressibility (非圧縮性).

Every quantity the fluid carries (smoke density, temperature, dye) follows the advection part alone: ∂s∂t=−(𝐮⋅∇)s.

Stable Fluids

Jos Stam's Stable Fluids (SIGGRAPH 1999), named in section 14.7, solves these equations on a grid by operator splitting (演算子分割): one step applies the terms one after another, each with a method that is stable for any time step.

  1. Add forces: 𝐮←𝐮+h𝐟.
  2. Advect with the semi-Lagrangian method (セミラグランジュ法): to find the new value at a grid point, trace backwards along the velocity to where the fluid came from, 𝐱−h𝐮(𝐱), and interpolate the old field there.
  3. Diffuse implicitly: solve (𝐈−νh∇2)𝐮new=𝐮 (implicit Euler again, so any ν and h are fine). Smoke and water often skip this step, because the numerical diffusion of step 2 is already more than enough.
  4. Project: remove the divergence by solving a Poisson equation (ポアソン方程式) for the pressure and subtracting its gradient. This uses the Helmholtz–Hodge decomposition (ヘルムホルツ・ホッジ分解): any vector field is a divergence-free part plus a gradient, and the projection keeps only the first.

Worked example: semi-Lagrangian advection.
A 1D row of cells with spacing 1 holds the smoke density s=(0,0,1,1,0,0) at x=0,…,5, and the velocity is u=0.6 everywhere, with h=1.
For the cell at x=4, the fluid came from 4−0.6=3.4, between s3=1 and s4=0: 0.6⋅1+0.4⋅0=0.6.
At x=3: from 2.4, 0.6⋅1+0.4⋅1=1; at x=2: from 1.4, 0.6⋅0+0.4⋅1=0.4.
The new row is (0,0,0.4,1,0.6,0): the block moved 0.6 cells to the right, its total is still 2, and its edges got blurred.
With a much larger step, uh=2.6, on a longer row (0,0,1,1,0,0,0,0,0), the result is (0,0,0,0,0.4,1,0.6,0,0): still sensible.
Every new value is an interpolation of old values, so it can never leave the old range: that's why this step can't blow up.
A naive explicit difference scheme ("upwind", si←si−uh(si−si−1)) gives the same (0,0,0.4,1,0.6,0) at uh=0.6, but at uh=2.6 it produces (0,0,−1.6,1,2.6,0,…): negative smoke and a growing spike.
Explicit schemes need uh/Δx≤1, the CFL condition (CFL条件, after Courant, Friedrichs and Lewy).
The price of the semi-Lagrangian step is numerical dissipation (数値散逸): the blurring repeats every step, swirls fade, and smoke looks thick and syrupy.

On the GPU, advection is one texture lookup per cell, the bilinear interpolation done by the sampler (you'll meet compute shaders in the GLSL series, chapter 15):

Texture2D<float2> velocity;
Texture2D<float4> source;
SamplerState linearClamp;

// Semi-Lagrangian advection: fetch the value from where the fluid came from.
// uv: this cell's texture coordinate, h: time step, u is stored in cells per second.
float4 advect(float2 uv, float h, float2 invGridSize) {
  float2 u = velocity.SampleLevel(linearClamp, uv, 0);
  float2 back = uv - h * u * invGridSize;
  return source.SampleLevel(linearClamp, back, 0);
}
layout(set = 0, binding = 0) uniform sampler2D velocity;
layout(set = 0, binding = 1) uniform sampler2D source;

// Semi-Lagrangian advection: fetch the value from where the fluid came from.
// uv: this cell's texture coordinate, h: time step, u is stored in cells per second.
vec4 advect(vec2 uv, float h, vec2 invGridSize) {
  vec2 u = textureLod(velocity, uv, 0.0).xy;
  vec2 back = uv - h * u * invGridSize;
  return textureLod(source, back, 0.0);
}
Texture2D<float2> velocity;
Texture2D<float4> source;
SamplerState linearClamp;

// Semi-Lagrangian advection: fetch the value from where the fluid came from.
// uv: this cell's texture coordinate, h: time step, u is stored in cells per second.
float4 advect(float2 uv, float h, float2 invGridSize) {
  float2 u = velocity.SampleLevel(linearClamp, uv, 0);
  float2 back = uv - h * u * invGridSize;
  return source.SampleLevel(linearClamp, back, 0);
}

Pressure projection on a 2×2 grid

Grid solvers usually store velocities on the cell faces and pressure at the cell centers, the MAC grid (MAC格子, a staggered grid, スタッガード格子), because the divergence of a cell and the pressure difference across a face then fall out naturally.
With grid spacing 1, ρ=1 and h=1:

  • The divergence of a cell is (right face u − left face u) + (top face v − bottom face v).
  • The projection subtracts the pressure difference across each face: uface←uface−(pright−pleft), and the same for v with top and bottom.
  • For the result to have zero divergence, the pressure must satisfy, in every cell, ∑fluid neighbors(pnb−p)=divergence. Wall faces have velocity 0 and add no term.

Worked example.
Four cells in a box with solid walls; only the face between the two bottom cells has a velocity, u=1 (fluid pushed to the right).
The bottom-left cell loses fluid (divergence +1), the bottom-right one gains it (−1), the top cells are 0.
Each cell has two fluid neighbors, so the update for one cell is p=sum of neighbor pressures−divergence2.
One Gauss–Seidel sweep, starting from all zeros, in the order bottom-left, bottom-right, top-left, top-right:

  • p00=0+0−12=−0.5
  • p10=p00+p11−(−1)2=−0.5+0+12=0.25
  • p01=p00+p11−02=−0.25
  • p11=p10+p01−02=0

A second sweep changes nothing, so this tiny system is solved (pressure is only defined up to a constant; only differences matter).
The new face velocities: bottom 1−(0.25−(−0.5))=0.25, top 0−(0−(−0.25))=−0.25, left column 0−(−0.25−(−0.5))=−0.25, right column 0−(0−0.25)=0.25.
Check the bottom-left cell: out through the right face 0.25, out through the top face −0.25 (that's inflow): divergence 0, and the other three cells balance the same way.

Two 2 by 2 grids. Left, before the projection: one arrow of velocity 1 across the face between the bottom cells, and the divergences plus 1, minus 1, 0 and 0. Right, after: the pressures minus 0.5, 0.25, minus 0.25 and 0, and four arrows of size 0.25 that circulate counter-clockwise

The push to the right became a small counter-clockwise vortex: in a closed box the fluid has nowhere to go but around.
Only a quarter of the original speed survives, because the projection keeps the divergence-free part and throws the rest away.
Real grids have 105 to 108 cells, and the Poisson solve (preconditioned conjugate gradients, multigrid, or on the GPU a fixed number of Jacobi iterations) dominates the cost.
On this particular grid plain Jacobi (all cells updated from the old values at once) actually oscillates between two states forever; weighted Jacobi, which moves only two thirds of the way each time, converges (the bottom face goes 0.333, 0.333, 0.259, 0.259, 0.251, … towards 0.25).

Smoke and fire

Smoke adds two fields that are advected with the flow, the smoke density s and the temperature T, and a buoyancy (浮力) force (Fedkiw, Stam and Jensen, "Visual Simulation of Smoke", SIGGRAPH 2001):

𝐟buoy=(−as+b(T−Tamb))𝐲^

Heavy smoke sinks, hot gas rises.
The same paper introduced vorticity confinement (渦度閉じ込め): measure the swirl (the vorticity, the curl of 𝐮), and add a force that spins the small vortices back up, to give back the detail that numerical dissipation removes.
Fire adds a fuel or reaction field, expansion where fuel burns, and a color from the temperature (the blackbody colors of chapter 3).

Four frames of a small smoke simulation on a 72 by 112 grid: a hot source at the bottom emits smoke that rises as a plume, rolls up into a mushroom head and breaks into swirls, after 60, 120, 180 and 240 steps

The run above is a toy version (72×112 cells, semi-Lagrangian advection, buoyancy, a little vorticity confinement, 60 Jacobi iterations per step) that shows the density as brightness; rendering smoke with light scattering inside it is volume rendering, chapter 28.

SPH: kernels and density

In SPH (section 14.7) every quantity at a point is a weighted sum over nearby particles, with a smoothing kernel (平滑化カーネル) W(r,h) that is largest at distance 0 and falls to 0 at the support radius h (here h is a radius, not the time step).
Müller, Charypar and Gross (2003) chose a different kernel for each job:

Wpoly6(r,h)=31564πh9(h2−r2)3,Wspiky(r,h)=15πh6(h−r)3(0≤r≤h)

Both integrate to 1 over the ball of radius h.
Poly6 is used for density, because it only needs r2 (no square root).
But its slope is 0 at the center, so two particles very close together feel no pressure force and clump; the pressure force therefore uses the spiky kernel, whose slope is largest at the center.
(A third kernel with a positive Laplacian is used for viscosity.)

Left: the poly6 and spiky kernels W of r for h equal to 1; poly6 starts at 1.57 with a flat top, spiky starts at 4.77 with a sharp peak, both fall to 0 at r equal to h. Right: their slopes; poly6&

Worked example: density.
With h=1 (in units of the kernel radius), Wpoly6(r)=31564π(1−r2)3, and 31564π=1.5667.
A particle has neighbors at distances 0.5, 0.5 and 0.8; all masses are 1.
It counts itself too (r=0):

ρ=1.5667+2⋅1.5667⋅0.753+1.5667⋅0.363=1.5667+2⋅0.6609+0.0731=2.9617

The equation of state (状態方程式) p=k(ρ−ρ0) turns density into pressure: with k=2 and a rest density ρ0=2, p=1.923, so this crowded particle pushes its neighbors away.
The pressure force is 𝐟i=−∑jmjpi+pj2ρj∇Wspiky(𝐱i−𝐱j), symmetric so that two particles push each other equally.

This "weakly compressible" SPH needs a large k to keep water from compressing, which makes it stiff.
Later methods enforce incompressibility with a solver (PCISPH, IISPH, DFSPH), and position-based fluids (Macklin and Müller, SIGGRAPH 2013) make ρi/ρ0−1=0 a PBD constraint per particle, as PhysX's GPU fluids do at the time of writing.
Neighbors are found with a uniform grid of cell size h.

PIC, FLIP and APIC

Grids are good at pressure and bad at advection; particles are the opposite, so hybrid methods (ハイブリッド法) use both every step:

  1. P2G: transfer the particle velocities to the grid (a kernel-weighted average onto the nearby faces).
  2. Solve forces and the pressure projection on the grid.
  3. G2P: transfer the velocities back, then move the particles through the grid velocity field.

The question is how to transfer back.
PIC (particle-in-cell) gives each particle the interpolated new grid velocity, which averages away everything finer than the grid: smooth, stable and very dissipative.
FLIP (fluid-implicit-particle; Brackbill and Ruppel, 1986) adds only the change of the grid velocity to the particle's own velocity, which keeps the particle's detail but also its noise.
Zhu and Bridson ("Animating Sand as a Fluid", SIGGRAPH 2005) adapted both to incompressible flow and brought them into graphics, suggesting a weighted average to tune the numerical viscosity (PIC for sand, FLIP for water).

Worked example.
A particle carries 2.4 m/s.
At its position, the grid velocity was 2.0 m/s after P2G and is 1.5 m/s after the pressure solve.
PIC: the particle gets 1.5.
FLIP: 2.4+(1.5−2.0)=1.9.
A blend of, for example, 95% FLIP and 5% PIC: 0.95⋅1.9+0.05⋅1.5=1.88.

APIC (the affine particle-in-cell method; Jiang, Schroeder, Selle, Teran and Stomakhin, SIGGRAPH 2015) gives each particle a small matrix describing how the velocity varies around it (a locally affine velocity), and transfers it both ways.
This keeps rotation, conserves angular momentum exactly across the transfers, and removes PIC's dissipation without FLIP's noise.

MPM (the material point method, 物質点法), from computational mechanics in the 1990s, takes the hybrid idea to solids.
Particles carry mass, velocity and a deformation gradient 𝐅 like the FEM of section 26.3; the grid computes the stress forces each step; nothing ever has to be meshed or remeshed, so the material can tear, flow, merge and pile up.
Stomakhin, Schroeder, Chai, Teran and Selle ("A Material Point Method for Snow Simulation", SIGGRAPH 2013) used it for the snow of Disney's Frozen, and MPM is now used for sand, mud, foam and other materials that are half solid and half fluid.

Rendering water

The simulation only gives particles or a grid; the picture needs a surface and a material:

  • Surface: an implicit function built from the particles, polygonized with marching cubes (chapter 9, section 9.3), or a level set (a signed distance field, chapter 21) on the grid; games often splat particles into a depth buffer and shade it in screen space.
  • Shading: Fresnel reflection (chapter 22), refraction, absorption that tints deep water (chapter 28), caustics, and spray, foam and bubbles as extra particles.
  • Oceans are usually not simulated: a sum of many waves with a measured spectrum, computed with an FFT, gives a tileable height field.

26.5 Hair, destruction and simulation in practice

Hair

Section 14.4 described a strand as a chain of particles with stretch and bend springs, with guide hairs and interpolation for the rest.
Hair is almost inextensible, the worst case for stiff springs, and it twists.
Two directions dominate:

  • Position-based chains. "Follow the leader" (Müller, Kim and Chentanez, VRIPHYS 2012) projects each particle to the right distance from its predecessor in one pass from root to tip, so the strand is exactly inextensible, and corrects the velocities to hide the resulting bias.
  • Rods. Film hair uses elastic rod models that include twist, solved implicitly.

Destruction with Voronoi fracture

Section 14.7 described destruction as pre-fractured pieces glued with breakable constraints.
The pieces usually come from a Voronoi diagram (ボロノイ図): scatter seed points (more near the expected impact point, for small splinters there and large chunks far away), and give every point of the object to the nearest seed.
Each Voronoi cell is the intersection of half-spaces, one per other seed, bounded by the perpendicular bisector (垂直二等分線) of the two seeds, so every piece is convex: perfect for convex collision shapes and GJK.

Worked example.
Seeds 𝐬1=(0,0) and 𝐬2=(4,2).
A point is equally far from both when x2+y2=(x−4)2+(y−2)2, which simplifies to 8x+4y=20, or 2x+y=5.
The point (1,1) has 2+1=3<5, so it belongs to 𝐬1 (check: squared distances 2 and 9+1=10).
To cut a cell, clip the object's polygon (or mesh) against each bisector with exactly the half-plane clipping of chapter 6.

A 2D slab cut into Voronoi pieces: seed points cluster around an impact star in the upper right, where the pieces are small, and the pieces get larger with distance from it

Physics on the GPU

GPUs need thousands of independent tasks (chapter 29).
Particles, grid fluids (advection is one lookup per cell, Jacobi is one stencil per cell), SPH and PBD map well; rigid bodies with their branchy narrow phase and sequential constraint solving are harder.
The Gauss–Seidel solvers of this chapter are sequential by nature (each constraint uses its neighbors' newest values), and the GPU uses two answers:

  • Jacobi (ヤコビ法): every constraint computes its correction from the old positions, and the corrections are averaged per particle. Fully parallel, but slower to converge.
  • Graph coloring (グラフ彩色): split the constraints into groups (colors) in which no two share a particle, run each group in parallel and the groups in sequence: still exact Gauss–Seidel. The cloth of section 26.3 used 8 colors (horizontal, vertical, diagonal and anti-diagonal constraints, each split in two by the parity of the column, or of the row for the vertical ones).

At the time of writing, engines such as NVIDIA PhysX run rigid bodies, PBD particles (fluids, granular material) and FEM soft bodies on CUDA GPUs, and many games run cloth, hair and particle effects in compute shaders.

Determinism and networking

A simulation is deterministic (決定的) when the same inputs give bit-for-bit the same result.
That sounds automatic, but floating-point arithmetic isn't associative.
In single precision, (108−108)+1=1 but 108+(−108+1)=0, because −108+1 rounds back to −108.
A different summation order (thread schedule, SIMD width), a compiler that fuses a multiply and an add into one FMA instruction, or a different sin can change the last bit, and chaotic systems (a falling stack, a breaking wall) amplify that into different outcomes within seconds.

Determinism on one machine needs a fixed time step (section 14.8), a fixed order of bodies and contacts (sort them, don't rely on hash-table order) and no uninitialized data.
Determinism across platforms also needs control of the compiler's floating-point settings; at the time of writing, Jolt Physics, for example, has a build option that aims to give the same results on all platforms.

Multiplayer games choose between two strategies:

  • Lockstep (ロックステップ): every machine runs the full simulation and only the inputs are sent. Little bandwidth (popular in strategy games with thousands of units), but it needs perfect determinism.
  • State synchronization (状態同期): a server runs the authoritative simulation and sends object states. Clients predict their own player (client-side prediction, クライアント側予測) and, when the server disagrees, rewind and replay their inputs (rollback, ロールバック). More bandwidth, but small differences don't matter.

Exam points

These tie back to the syllabus item physics-based animation (chapter 14) and are worth being sure about for the exam:

  • Explicit Euler uses the current state and is unstable for an undamped spring at every step size; implicit (backward) Euler uses the end of the step, needs equation solving, is stable for any step and damps artificially; semi-implicit Euler is stable while hω<2.
  • Collision detection is broad phase then narrow phase; two convex shapes are separate exactly when some axis separates their projections (SAT); the response is an impulse along the contact normal, with friction limited by μ times the normal impulse.
  • Mass–spring cloth with stiff springs needs small steps or implicit integration; position-based methods move positions to satisfy constraints directly.
  • Fluids: Eulerian grids (Stable Fluids: advection, diffusion, pressure projection) vs Lagrangian particles (SPH), and hybrids that use both.

26.6 Summary

  • Implicit Euler divides a spring's energy by 1+h2ω2 per step: stable for any step (A-stable), but damped; explicit Euler's stability region |1+z|≤1 misses the imaginary axis.
  • Rigid bodies need the world inertia tensor 𝐑𝐈body𝐑⊤, a normalized quaternion update and care with the gyroscopic term.
  • SAT gives separation, normal and depth (4 axes for 2D boxes, 15 for 3D); clipping builds the contact manifold; GJK and EPA work for any convex shape through support functions.
  • Sequential impulses (projected Gauss–Seidel) clamp accumulated impulses (λn≥0, |λt|≤μλn) and rely on warm starting, Baumgarte bias with slop, and sleeping; joints and motors are solved in the same sweeps.
  • PBD projects positions onto constraints; XPBD's compliance α~=α/h2 makes stiffness independent of the iteration count. Strain limiting, shape matching and corotational FEM build on the same ideas.
  • Stable Fluids: forces, semi-Lagrangian advection, implicit diffusion, pressure projection. SPH: poly6 for density, spiky for pressure. PIC, FLIP and APIC transfer velocities between particles and grid; MPM handles snow and sand.
  • Hair uses inextensible chains or rods, destruction convex Voronoi pieces, GPUs Jacobi or graph coloring; determinism needs a fixed step, a fixed order and controlled floating point.

26.7 Key terms

English 日本語
stiff system 硬い系(スティッフな系)
implicit (backward) Euler method 陰的オイラー法(後退オイラー法)
stability region 安定領域
A-stable A安定
stiffness matrix 剛性行列
conjugate gradient method 共役勾配法
angular momentum 角運動量
principal axes of inertia 慣性主軸
gyroscopic term ジャイロ項
separating axis theorem (SAT) 分離軸定理(SAT)
contact manifold 接触点の集合(コンタクトマニフォールド)
reference face, incident face 参照面、入射面
support function サポート関数
Minkowski difference ミンコフスキー差
GJK, EPA GJK法、EPA
effective mass 有効質量
Coulomb friction, friction cone クーロン摩擦、摩擦円錐
sequential impulses シーケンシャルインパルス
projected Gauss–Seidel (PGS) 射影ガウス=ザイデル法(PGS)
joint, motor ジョイント、モーター
Baumgarte stabilization, slop バウムガルテ安定化、許容めり込み(スロップ)
warm starting ウォームスタート
sleeping, island スリープ、アイランド
position-based dynamics (PBD) 位置ベース動力学(PBD)
compliance (XPBD) コンプライアンス(XPBD)
strain limiting ひずみ制限
shape matching シェイプマッチング
polar decomposition 極分解
finite element method (FEM) 有限要素法(FEM)
deformation gradient 変形勾配
strain, stress ひずみ、応力
Young's modulus, Poisson's ratio ヤング率、ポアソン比
corotational FEM 共回転FEM
advection 移流
divergence, incompressibility 発散、非圧縮性
semi-Lagrangian method セミラグランジュ法
pressure projection 圧力投影
Poisson equation ポアソン方程式
Helmholtz–Hodge decomposition ヘルムホルツ・ホッジ分解
MAC grid (staggered grid) MAC格子(スタッガード格子)
CFL condition CFL条件
numerical dissipation 数値散逸
buoyancy 浮力
vorticity confinement 渦度閉じ込め
smoothing kernel 平滑化カーネル
PIC, FLIP, APIC PIC法、FLIP法、APIC法
material point method (MPM) 物質点法(MPM)
Voronoi diagram ボロノイ図
Jacobi method, graph coloring ヤコビ法、グラフ彩色
determinism 決定性
lockstep, state synchronization ロックステップ、状態同期
client-side prediction, rollback クライアント側予測、ロールバック

26.8 Challenges

  1. ★ A mass m=1 kg hangs on a spring with k=400 N/m, x0=0.1 m, v0=0. Compute two steps of implicit Euler with h=0.05 s and the energy after each. By what factor does each step change the energy, and what would explicit Euler's factor be?
  2. ★ A box of 6 kg has the sides 1, 2 and 3 m along its local x, y and z axes. Compute 𝐈body, then 𝐈world after a rotation by 90° about z, and the angular velocity for 𝐋=(1,1,0). Is it parallel to 𝐋?
  3. ★★ Box A is axis-aligned at the origin with half-extents (1.5,1); box B has half-extents (1,0.5), axes 𝐮B=(0.6,0.8), 𝐯B=(−0.8,0.6) and its center at (2.3,0.5). Run SAT on all four axes, give the contact normal and the depth, then move B to (2.8,0.5) and say which axis separates them.
  4. ★★ A rope of three particles hangs straight down: 𝐩1=(0,0) pinned, 𝐩2=(0,−1.5), 𝐩3=(0,−3), all other w=1, rest lengths 1. Do two PBD sweeps (constraint 1–2, then 2–3) and give the lengths after each. Then do one sweep with XPBD and α~=1 for both constraints. Which one is closer to the rest lengths, and why is that not a flaw?
  5. ★★ In the 2×2 box of section 26.4, start instead with only the face between the two top cells moving, u=−1 (to the left). Compute the divergences, one Gauss–Seidel sweep for the pressure (same order), and the four new face velocities. Check that every cell has zero divergence, and say which way the vortex turns.
  6. ★★★ A tower of ten boxes jitters and slowly sinks into the ground. Explain the role of solver iterations, warm starting, the Baumgarte factor and slop, the contact order and sleeping, which you'd change first, and the side effects you'd expect.

Multiple choice

Q1 ★ Which of the following statements about integrating a stiff spring is correct?

A Implicit Euler stays stable for an undamped spring at any time step, but it removes energy every step, so the oscillation dies out faster than it should.
B Explicit Euler is stable for an undamped spring as long as hω<2.
C Implicit Euler needs no equation solving, so it costs the same as explicit Euler for a cloth with thousands of springs.
D The stability region of explicit Euler contains the whole left half of the complex plane.
E The stiffer the spring, the larger the time step that explicit methods can use.

Q2 ★★ Which of the following statements about rigid-body contact is correct?

A For two boxes in 3D, SAT only has to test the six face normals of the two boxes.
B In sequential impulses, the accumulated normal impulse of each contact is clamped to be non-negative, and the friction impulse is clamped to at most μ times the normal impulse in size.
C GJK is a broad-phase method that sorts the bounding boxes of all bodies along one axis.
D Warm starting means running more solver iterations in the first frame of a simulation.
E The inertia tensor in world space is the same for every orientation of a body, so it is computed once.

Q3 ★★ Which of the following statements about simulation methods is correct?

A Semi-Lagrangian advection traces particles forward in time and is stable only when the CFL number is below 1.
B The pressure projection of Stable Fluids adds divergence to the velocity field so that the fluid can expand.
C FLIP transfers only the change of the grid velocity back to the particles, which keeps detail but adds noise, while PIC copies the grid velocity, which is smooth but dissipative.
D In XPBD, the stiffness of a constraint depends more strongly on the iteration count than in PBD.
E SPH computes the density of a particle by solving a Poisson equation on a grid.

26.9 Practical assignment

A crate, a rope and a puff of smoke, by hand.
You need graph paper, a pencil, a ruler and a calculator; you'll take one step of each kind of solver in this chapter.

  1. Explicit vs implicit. A spring with k=100 N/m and m=1 kg starts at x0=0.2 m, v0=0. Take one step with h=0.1 s with explicit Euler and one with implicit Euler (use the closed form of section 26.1), and compute the energy before and after each.
  2. SAT. On graph paper, draw box A (center (0,0), axis-aligned, half-extents (1.5,1)) and box B (center (1,1.8), half-extents (1,0.5), axes 𝐮B=(0.6,0.8), 𝐯B=(−0.8,0.6)). Compute the overlap on all four axes, choose the contact normal and depth, and draw the normal on your sketch.
  3. Impulse with friction. Repeat the crate of section 26.2 (m=1, I=16, 𝐯=(0,−2), 𝐫=(0.5,−0.5), 𝐧=(0,1)) with μ=0.2. Do two sequential-impulse iterations by hand (normal, then friction, clamping the accumulated values), then solve the sliding case exactly as in the text.
  4. PBD rope. Three particles hang at (0,0) (pinned), (0,−1) and (0,−2), at rest, with rest lengths 1. With g=10 m/s² and h=0.1 s, predict the positions, do two sweeps of distance projections (1–2, then 2–3), and compute the new velocities from the position change.
  5. Pressure projection. In the 2×2 box of section 26.4, the face between the two left cells has v=1 (up), all others 0. Compute the divergences, one Gauss–Seidel sweep for the pressure, and the new face velocities. Draw the result as arrows.
  6. SPH density. With h=1 and unit masses, compute the poly6 density at (0,0) for particles at (0,0), (0.5,0), (0,0.5) and (0.6,0.8).

How to check yourself:

  • Step 1: the energy starts at 2 J; explicit Euler doubles it and implicit Euler halves it (hω=1), and the implicit result satisfies x1=x0+hv1.
  • Step 2: all four overlaps are positive; the smallest is on A's y axis, so the normal is (0,1) and the depth is less than 0.5.
  • Step 3: after iteration 1 the friction impulse sits at its limit −μλn, the remaining vn shrinks each iteration, and the exact λn lies between 0.8 and 1 with the contact still sliding.
  • Step 4: after each sweep the second length is exactly 1 and the first is slightly too long, half as much after the second sweep; both moving particles get the same small downward velocity.
  • Step 5: every face has speed 0.25, all four cells have zero divergence, and the arrows form a loop (it turns clockwise this time).
  • Step 6: the particle at (0.6,0.8) is exactly at distance h and contributes nothing; the density is a little below 2.9.


コメント(0)

まだコメントはありません。