Every collision so far has treated the two sides as equals, or one of them as a wall. Chapter 19's balls swapped their speeds when they met, which is right only when they weigh the same. Real objects have mass. A bowling ball barely notices a marble, while the marble flies off. This chapter gives bodies mass, and answers a collision between any two of them with one formula, which comes from the momentum they share. It adds forces, adds them up, and settles a pile of seventy balls, which is harder than it looks.
Then it ties up the last loose end in the book's motion: the step. Most demos so far have moved by each frame's dt, so a game behaved a little differently at every frame rate. A fixed timestep steps the physics by the same short time, again and again, as many times as real time asks for. The world then comes out the same on every machine, and survives a frame that takes far too long. And drawing between the steps keeps the motion smooth.
In this chapter, we will:
- Give bodies mass, and see what momentum and an impulse are
- Work out the impulse that answers a collision between two masses
- Add up forces each step: gravity, and a spring to the mouse
- Settle a pile of seventy balls, with passes and short steps
- Step the physics at a fixed rate, with an accumulator
- Draw between the steps, so that the motion stays smooth
- Build Impulse, a pile of seventy balls to throw, stall and slow down
We'll start with mass.
Mass and Momentum
Mass decides how a body answers a push, and momentum decides how two bodies share a collision. They're the two ideas that the rest of the chapter builds on.
Mass
Mass is how hard something is to get moving, or to stop. Push an empty shopping cart and a car with the same force, and the cart speeds up far more. That rule is Newton's second law: a force gives a body an acceleration of the force divided by its mass.
acceleration = force / massChapter 9's critters steered with forces, but each had a mass of 1, so the force and the acceleration were the same number. In this chapter, each body has a mass of its own:
// A body: a ball with mass. The force on it is added up each step, and its
// inverse mass is stored, since that's what the response divides by. Its
// place before the last step is kept, for drawing between steps.
struct Body
{
Vec2 pos;
Vec2 vel;
Vec2 force;
float radius;
float mass;
float invMass;
Vec2 prevPos;
SDL_Color color;
};The force adds up every force on the body during a step, as Forces explains. The prevPos, its place before the last step, is for drawing, in Drawing Between Steps. And the mass is stored twice: as mass, and as invMass, which is 1 divided by the mass. The response to a collision divides by the mass, and multiplying by invMass does the same. It also lets a body be infinitely heavy, with an invMass of 0, so that nothing can move it. That's a wall.
A ball's mass is the square of its radius:
// A ball of a radius, whose mass is its radius squared, as if every ball
// were a disc cut from the same sheet, so that mass grows with area.
Body makeBody(Vec2 pos, float radius, SDL_Color color)
{
float mass = radius * radius;
return { pos, { 0, 0 }, { 0, 0 }, radius, mass, 1.0f / mass, pos, color };
}So a ball twice as wide is four times as heavy. Its area grows the same way, so it's as if every ball were cut from the same sheet. The units don't matter, as long as every mass uses the same ones.
Momentum
A moving body's momentum is its mass times its velocity:
momentum = mass × velocityA ball of 1 kilogram moving at 4 meters a second has a momentum of 4. So does a ball of 2 kilograms at 2 meters a second. Momentum is a vector, which points the way the body moves. So two equal balls rushing toward each other at the same speed have a total momentum of zero.
Momentum matters because a collision can't change the total. When two balls collide, each pushes on the other, and Newton's third law says that the two pushes are equal and opposite. They last exactly as long as each other, since they're the same contact. So whatever momentum one ball gains, the other loses, and the total after is the same as before. That's the conservation of momentum, the first of the two facts that decide a collision.
Impulse
A real collision is a very large force for a very short time: a few thousandths of a second, while the two balls squash and spring back. A game can't follow that, and doesn't need to. It treats the collision as instant, and changes the velocities at once. An instant change of momentum is an impulse, and its size is written j. Since momentum is mass times velocity, an impulse changes a body's velocity by j over its mass:
change in velocity = j / massThe same impulse changes a light ball's velocity a lot, and a heavy ball's a little. In a collision, the two balls get the same impulse in opposite directions, which is exactly what the conservation of momentum asks for.
Resolving a Collision
Two balls touch, and they're moving toward each other. The question is what their velocities should be afterward, and the two facts answer it.
The Closing Speed
Call the balls A and B. Chapter 18's normal, n, is the unit vector from A's center toward B's. What matters for the collision is how fast they're moving toward each other along it, their closing speed:
closing = (vB - vA) · nIt's B's velocity, seen from A, measured along the normal, as Chapter 10 measured a velocity across a surface. It's negative while the balls approach, and positive once they're moving apart. Only the motion along the normal takes part in the collision. The rest, along the surfaces where they touch, carries on unchanged, since smooth balls can't push sideways on each other.
The restitution e decides how fast the balls come apart, as it did for Chapter 10's bounces. They separate at e times the speed at which they approached:
closing after = -e × closing beforeWith e at 1, they leave as fast as they came. With e at 0, they stop approaching, and neither bounces away. That's the second fact.
Working Out the Impulse
Now the two facts give the impulse. B gets j along the normal, and A gets the same impulse in the opposite direction, so their velocities change like this:
vA after = vA - n × j / mA
vB after = vB + n × j / mBMeasure the closing speed with those velocities. B's velocity along the normal goes up by j / mB, and A's goes down by j / mA, so the closing speed goes up by both:
closing after = closing + j × (1/mA + 1/mB)The restitution says that the closing speed after must be −e times the closing speed before. Set the two equal:
closing + j × (1/mA + 1/mB) = -e × closingTake closing over to the right-hand side, then divide by the sum of the inverse masses. That gives the impulse:
j = -(1 + e) × closing / (1/mA + 1/mB)That one line is the heart of a physics engine. The closing speed is negative when the balls approach, so j comes out positive. B is pushed along the normal, away from A, and A is pushed back the other way. Each one's velocity changes by j times its inverse mass, so the heavier ball's changes less.
A Worked Example
A ball of 1 kilogram, moving right at 4 meters a second, hits a ball of 3 kilograms at rest, head on. The normal points right, from A to B, so the closing speed is 0 − 4, which is −4. The inverse masses add up to 1 + 1/3, which is 4/3.
With e at 1, j is 2 × 4 / (4/3), which is 6. The light ball's velocity changes by −6 / 1, from 4 to −2, so it comes back at 2 meters a second. The heavy ball's changes by 6 / 3, from 0 to 2. The momentum before was 1 × 4, which is 4. After, it's 1 × −2 + 3 × 2, which is 4 again.
With e at 0.35, Impulse's restitution, j is 1.35 × 4 / (4/3), which is 4.05. The light ball ends at 4 − 4.05, which is −0.05, so it nearly stops. The heavy ball ends at 4.05 / 3, which is 1.35. The momentum is −0.05 + 3 × 1.35, which is 4 once more. The next image shows all three moments.
The momentum is kept every time, but the energy of motion isn't. A body's kinetic energy is half its mass times the square of its speed. Before the collision, it's half of 1 × 4², which is 8 joules. After the bounce with e at 1, it's half of 1 × 2² plus half of 3 × 2², which is 8 again, so a perfect bounce keeps all of it. With e at 0.35, it's 2.74 joules. The rest, nearly two-thirds, went into the squash, which in the real world becomes heat and sound. In a game, it simply goes, and that's what lets a pile come to rest.
Walls
A wall is a body that nothing moves. Give B an inverse mass of 0 and no velocity, and the closing speed is just −(vA · n), the speed of A into the wall, made negative. Put that into the impulse, and A's mass cancels out of A's change:
vA after = vA - n × ((1 + e) × (vA · n))That's Chapter 18's bounce. Chapter 18's normal pointed out of the wall, the opposite way to this one. But n appears in the formula twice, and turning it around flips both, which changes nothing. Like Chapters 10 and 18, it changes only the part of the velocity across the wall. So a wall needs no code of its own: Impulse answers a ball against a wall with the same function, passing a wall as a body with an inverse mass of 0.
Pushing Apart by Mass
Before the impulse, the overlap has to go. Chapter 18 pushed a ball out of a wall by the whole depth, and Chapter 19 pushed two equal balls apart by half the depth each. With masses, the push is shared as the impulse is. Each body moves in step with its inverse mass, so the lighter one moves further:
A moves back by depth × (1/mA) / (1/mA + 1/mB)
B moves on by depth × (1/mB) / (1/mA + 1/mB)For equal masses, that's half each, as in Chapter 19. Against a wall, it's the whole depth for the ball, as in Chapter 18. A ball four times as heavy as its neighbor moves a fifth of the depth, and its neighbor four-fifths.
The Response
Here's the response to one contact, with the push first and the impulse second:
// The response to one contact between a and b, where n is the unit normal
// from a toward b, and depth is their overlap. The push moves each out in
// step with its inverse mass, so the heavier moves less. The impulse, only
// if they're closing, changes their velocities by the same amount of
// momentum, in opposite directions.
void respond(Body& a, Body& b, Vec2 n, float depth)
{
float invSum = a.invMass + b.invMass;
if (invSum <= 0.0f) return;
float push = depth / invSum;
a.pos -= n * (push * a.invMass);
b.pos += n * (push * b.invMass);
float closing = (b.vel - a.vel).dot(n);
if (closing >= 0.0f) return;
float j = -(1.0f + RESTITUTION) * closing / invSum;
a.vel -= n * (j * a.invMass);
b.vel += n * (j * b.invMass);
}The push moves each ball in step with its inverse mass, as Pushing Apart by Mass worked out. If both bodies are walls, there's nothing to move, so the function returns at once. The impulse is applied only while the balls are closing. Two balls that already move apart, even while they still overlap, are left to separate, since an impulse then would pull them back together. Unlike Bouncy, Impulse has no rest speed. Its restitution is lower and its steps are shorter, and its pile measured just as still without one.
Forces
An impulse changes a velocity at once. A force changes it gradually, step by step, through the acceleration it gives: the force over the mass.
Adding Up the Forces
Gravity is a force, and so are a spring, a rocket's thrust and the wind. A body can feel several at once, and their effects simply add. So each body keeps a force, which starts every step at zero. Each force adds itself to it, without knowing about the others. Then one function turns the total into motion, and sets it back to zero. That's a force accumulator. A new kind of force is one more line in the sum, and nothing else changes.
Impulse has two forces. Gravity pulls each ball with a force of its mass times g, the acceleration of a fall. That looks like a step backward, since Chapter 10 simply added g to every velocity. But divide the force by the mass, as the integrator does, and the acceleration is g again, whatever the mass. That's why a heavy ball and a light one fall side by side. As a force, gravity is one force among others, and the integrator treats them all alike.
A Spring to the Mouse
The other force moves a ball with the mouse. While a ball is held, a spring pulls it toward the mouse, in step with how far away the mouse is. That's Hooke's law: a spring pulls with its stiffness times its stretch. A spring alone would swing the ball past the mouse and back forever. So a second force, damping, pushes against the ball's velocity, and the swings die away:
force = SPRING × (mouse - pos) - DAMPING × velBoth forces are added, with gravity, in one function:
// The forces for one step, added up: gravity on every ball, its mass times
// g, and on the ball being held, a spring toward the mouse. The spring
// pulls in step with how far it's stretched, and its damping pushes back
// against the ball's speed, so that it settles rather than swings forever.
void addForces(std::vector<Body>& bodies, int held, Vec2 mouse)
{
for (Body& b : bodies) b.force += Vec2{ 0.0f, GRAVITY } * b.mass;
if (held >= 0)
{
Body& b = bodies[held];
b.force += (mouse - b.pos) * SPRING - b.vel * DAMPING;
}
}Since the spring's pull is a force, it moves a heavy ball more slowly than a light one, and a drag shows it at once. A small ball snaps to the mouse, while a large one swings along behind it. Even when it's still, a held ball hangs a little below the mouse, since the spring must hold up its weight. The stretch that does it is the weight over the stiffness. The largest ball the demo makes has a radius of 28, so a mass of 784, and it hangs 784 × 900 / 40,000 pixels below the mouse: about 18.
A held ball keeps its mass, too, so a heavy one shoves the pile aside, and a light one gets shoved. When you let go, the ball keeps the velocity the spring gave it, so a flick of the mouse throws it. There's no need to measure how fast the mouse moved.
Semi-Implicit Euler
Once the forces are added up, each body moves:
// One step of semi-implicit Euler, as in Chapter 7: the force changes the
// velocity, by the force over the mass, and then the new velocity moves the
// body. The force is used up, ready for the next step's.
void integrate(std::vector<Body>& bodies, float h)
{
for (Body& b : bodies)
{
b.vel += b.force * (b.invMass * h);
b.prevPos = b.pos;
b.pos += b.vel * h;
b.force = { 0, 0 };
}
}This is Chapter 7's semi-implicit Euler, with the force over the mass in place of the acceleration. The velocity changes first, and then the body moves with the new velocity. Chapter 7 chose that order because it keeps a spring steady, where the other order adds energy to every swing, and the mouse's spring is the book's first. Multiplying by invMass divides by the mass. So a body with an inverse mass of 0 isn't moved by any force, as a wall shouldn't be.
Piles
One collision, the impulse solves exactly. A pile is dozens of contacts at once, and they disturb each other.
Why a Pile Is Hard
Push two balls apart, and one of them moves into a third. Gravity pulls every ball down on every step, so every step starts with the whole pile sunk a little into itself. Chapter 18 met the same trouble in a corner, and cured it with passes, going over every contact again. Impulse does the same:
// Every contact, in passes: each pair of balls, then each ball against
// each wall. A wall is a body with no velocity and an inverse mass of 0,
// infinitely heavy, so the same response bounces a ball off it.
void resolveContacts(std::vector<Body>& bodies, const Surface walls[4])
{
Body wall = {};
for (int pass = 0; pass < PASSES; ++pass)
{
for (size_t i = 0; i < bodies.size(); ++i)
for (size_t j = i + 1; j < bodies.size(); ++j)
{
Body& a = bodies[i];
Body& b = bodies[j];
Vec2 d = b.pos - a.pos;
float dist = d.length();
float reach = a.radius + b.radius;
if (dist <= reach && dist > 0.0001f)
respond(a, b, d / dist, reach - dist);
}
for (Body& b : bodies)
for (int w = 0; w < 4; ++w)
{
Vec2 off = b.pos - walls[w].point;
float depth = b.radius - off.dot(walls[w].normal);
if (depth >= 0.0f) respond(b, wall, -walls[w].normal, depth);
}
}
}In the preceding code, each pass answers every pair of balls that touch, then every ball against each of the four walls. The wall is a body with no velocity and an inverse mass of 0, made once and handed to respond as the second body. Its normal is the wall's normal turned around, since respond wants the normal from the ball toward the wall. A pair whose centers are in the same place is skipped, since there's no direction to push them in. Touching counts as overlapping, as it has since Chapter 15.
Passes and Short Steps
A simple engine gets piles wrong in two ways. They jitter, when the balls tremble and never come to rest. Or they sink, when the balls squash into each other until the pile is too low. Two things cure both. The first is more passes, and Impulse makes four each step, as its constant PASSES says. The second is shorter steps, since every step starts with gravity's pull already sinking the pile, and a longer step sinks it further.
To see what each is worth, Impulse's own functions dropped twenty different piles of seventy balls, let each settle for eight seconds, then watched it for two. The deepest overlap is between the deepest pair of balls, or a ball and a wall. The wander is how far a typical ball moved back and forth, which measures the jitter. Each number is the typical one, the median of the twenty piles:
steps a second passes deepest overlap wander
120 4 0.95 px 0.05 px
120 1 5.5 px 0.28 px
30 4 6.5 px 0.33 px
30 1 25.5 px 4.1 pxWith four passes at 120 steps a second, a typical pile's deepest overlap is under a pixel, and its balls are still to a twentieth of a pixel. One pass, or steps four times as long, leaves overlaps six or seven times deeper, and the pile trembles. With both, the pile sinks, until a typical one stands 111 pixels high, where the others stand 134 to 139. Real engines, such as Box2D, solve their contacts in passes too. None of them makes a pile exact, but a pile only has to look still and stay up.
One Step
One whole step puts it all together. It adds up the forces, moves every body, and then resolves every contact:
// One whole step of the physics, h seconds long.
void step(std::vector<Body>& bodies, const Surface walls[4], int held,
Vec2 mouse, float h)
{
addForces(bodies, held, mouse);
integrate(bodies, h);
resolveContacts(bodies, walls);
}That's the whole engine, in a handful of short functions. The rest of Impulse is about when to call it, and how to draw what it does.
The Fixed Timestep
Every number in Piles came from steps of a set length, and the length changed the answer. At 30 steps a second, the piles' overlaps were nearly seven times deeper than at 120.
The Step Decides the Answer
That's true of anything stepped by Euler integration. Chapter 7 showed it for a ship. Accelerating from rest at 320 pixels a second, every second, it went 165.3 pixels in its first second at 30 frames a second, and 161.1 at 144. Chapter 17's ball went through a wall only when its step was long enough.
So a game that steps by each frame's dt gives every machine a slightly different answer. With a pile, it isn't slightly. A pile is chaotic: a tiny difference in one step grows, until the balls lie somewhere else entirely. With one step a frame, Impulse's own functions dropped the same seventy balls at 60 frames a second and at 144. Ten seconds later, a typical ball was 17 to 25 pixels from its place in the other pile, and the furthest were 52 to 95 pixels away.
The Accumulator
A fixed timestep steps the physics by the same time, every time, whatever the frame rate, as Bullet Time did in Chapter 17. Each frame's time goes into an accumulator. While it holds a whole step, the physics takes one, and a step's time comes out. Whatever is left, less than a step, waits for the next frame.
Impulse takes 120 steps a second. On a screen that shows 60 frames a second, every frame takes two steps. On one that shows 144, most frames take one, and one frame in six takes none, since 144 frames share 120 steps. The next image follows seven frames at 144 a second.
The physics never sees a step that isn't a 120th of a second. So every machine takes the same steps, in the same order, and comes to the same answer. Chapter 7's ship, stepped this way, goes 161.3 pixels in its first second at any frame rate. And Impulse's seventy balls settle into the same pile, step for step, at 60 frames a second and at 144.
Long Frames
Sometimes a frame takes far too long: the game loads a file, or the computer is busy with something else. Chapter 7's clamp cuts any frame to a twentieth of a second, and the pile survives that, even with one step a frame. One step of a twentieth sinks the settled pile only about 2 pixels into itself. A longer frame is another matter. L makes the next frame a fifth of a second long, past the clamp. That's what a game with a looser clamp, or none, would see.
With one step a frame, that's one huge step. Every ball falls for a fifth of a second, about 36 pixels, before any contact is answered, so the bottom row ends up deep in the floor. The floor pushes it back up into the balls above, leaving overlaps of about 17 to 26 pixels. Four passes can't push that out cleanly, so the pile jumps, and settles somewhere new, with some balls 40 to 65 pixels from where they were. With fixed steps, the same fifth of a second is 24 ordinary steps, taken one after another in a single frame. No ball in the settled pile moves by more than a third of a pixel.
The Spiral of Death
There's a catch. A step takes time to compute. If a step took longer to compute than the time it covers, every frame would owe more steps than the one before. Each frame would take longer still, and the game would grind to a halt. That's the spiral of death.
The clamp stops it. No frame can add more than a twentieth of a second to the accumulator, which is six steps at 120 a second. A machine too slow for the physics then runs it in slow motion, rather than freezing. Impulse is nowhere near that. One of its steps takes about 19 microseconds in a Release build, and about 105 in Debug, where a 120th of a second is 8,333 microseconds.
Drawing Between Steps
Fixed steps bring one new problem, and it's in Figure 20.2. Frames 1 and 7 take no step, so they draw exactly what the frame before them drew.
The Hitch
At 120 steps a second on a 144 Hz screen, that's 24 frames every second in which nothing moves. Motion that should glide hitches, 24 times a second. At 30 steps a second, which R switches to, a ball moves in jumps, and stands still for four or five frames between them.
The leftover time in the accumulator says how far real time has got past the last step. The share of a step it makes is called alpha:
alpha = accumulator / stepTimeIt runs from 0, just after a step, to nearly 1, just before the next. So each ball is drawn by Chapter 8's lerp, from its place before the last step to its place after it, by alpha:
drawn = lerp(prevPos, pos, alpha)That moves it on every frame, whether or not the frame took a step. The next image shows a ball moving steadily, drawn both ways, with 30 steps a second on a 144 Hz screen.
Drawn at its last step's place, the ball climbs a staircase. Drawn between its last two places, it moves along a straight line, as steadily as the real ball does. The price is that it's drawn one step behind where it really is. At Impulse's usual rate, that's a 120th of a second, which is less than one frame on a 60 Hz screen. The physics never uses the drawn place, which is only for the eye.
Building Impulse
Impulse drops seventy balls into a box, and they settle into a pile. Drag a ball to throw it. Space switches between fixed steps and one variable step a frame, and L makes one frame a fifth of a second long. R switches between 120 and 30 steps a second, I turns interpolation on and off, and Enter drops a new pile. The readout gives the frames and steps in the last second, and the deepest overlap in the pile.
Get the code. The complete project is in the
Impulsefolder of the book's repository.
Impulse starts from the skeleton, with its timing and its mouse. It reuses fillCircle, with fmt2 and setColor, Chapter 9's generator and randRange, and Chapter 15's rectOf. Its Vec2.h is 10000 Balls', since this chapter adds nothing to it. Here are its includes and its colors:
#include <algorithm>
#include <cmath>
#include <random>
#include <string>
#include <vector>
#include "Vec2.h"
constexpr int WINDOW_WIDTH = 1000;
constexpr int WINDOW_HEIGHT = 700;
constexpr SDL_Color TEXT = { 235, 238, 242, 255 };
constexpr SDL_Color GREY = { 90, 100, 112, 255 };
constexpr SDL_Color BLUE = { 47, 111, 235, 255 };
constexpr SDL_Color AMBER = { 232, 89, 12, 255 };
constexpr SDL_Color GREEN = { 47, 158, 68, 255 };
constexpr SDL_Color RED = { 224, 49, 49, 255 };
constexpr SDL_Color VIOLET = { 150, 102, 230, 255 };
constexpr SDL_Color SILVER = { 150, 158, 170, 255 };
constexpr SDL_Color BALL_COLORS[] = { BLUE, GREEN, RED, AMBER, VIOLET };The five colors in BALL_COLORS take turns among the balls. Then come the constants:
// Gravity, as in Chapter 10, in pixels a second, every second, and how
// bouncy a collision is.
constexpr float GRAVITY = 900.0f;
constexpr float RESTITUTION = 0.35f;
// The passes over every contact that each step makes.
constexpr int PASSES = 4;
// The mouse's spring: its pull for each pixel of stretch, and its damping
// for each pixel a second of speed.
constexpr float SPRING = 40000.0f;
constexpr float DAMPING = 3000.0f;
// How many balls make the pile.
constexpr int BALL_COUNT = 70;Gravity is Bouncy's, and a restitution of 0.35 makes the balls bounce a little. Four passes are what Piles measured. The spring's stiffness and damping were tuned by hand, so that a light ball follows the mouse closely and a heavy one swings a little, then settles. Seventy balls make a pile three or four deep.
Next come Chapter 11's box, Chapter 10's surface, and the box the balls are in:
// An axis-aligned box: its smallest and largest corners. Neither of min's
// coordinates is ever more than max's.
struct AABB
{
Vec2 min;
Vec2 max;
};
// A flat surface: a point on it, and its normal, a unit vector that points
// out of it, to the side the balls are on.
struct Surface
{
Vec2 point;
Vec2 normal;
};
// The box the balls are in.
const AABB BOX = { { 60, 90 }, { 940, 640 } };The box runs from (60, 90) to (940, 640), which leaves room above it for the readout and below it for the controls. The Body struct comes next in the file, as Mass showed it. The random numbers come from Chapter 9's generator, with its randRange, unchanged:
// A random float from lo to hi. The generator is made once, and seeded
// from the system, so that every run is different.
std::mt19937 rng{ std::random_device{}() };After makeBody, which Mass also showed, one function drops a new pile:
// A new pile, dropped from the top of the box: balls of random sizes, at
// random places that don't overlap.
std::vector<Body> dropBalls()
{
std::vector<Body> bodies;
while ((int)bodies.size() < BALL_COUNT)
{
float r = randRange(12.0f, 28.0f);
Vec2 p = { randRange(BOX.min.x + r, BOX.max.x - r),
randRange(BOX.min.y + r, 380.0f) };
bool clear = true;
for (const Body& b : bodies)
if (distance(p, b.pos) < r + b.radius + 2.0f) clear = false;
if (clear)
{
SDL_Color color = BALL_COLORS[bodies.size() % 5];
bodies.push_back(makeBody(p, r, color));
}
}
return bodies;
}In the preceding code, each ball gets a random radius from 12 to 28, and a random place in the top part of the box, no lower than y = 380. A place closer than 2 pixels to a ball already placed is thrown away, and another is tried, until there are seventy. The colors take turns, by the ball's number in the list.
The functions from Resolving a Collision, Forces and Piles come next. After them, one more measures what the passes leave, for the readout:
// The deepest overlap left between any two balls, or a ball and a wall.
float deepestOverlap(const std::vector<Body>& bodies, const Surface walls[4])
{
float deepest = 0.0f;
for (size_t i = 0; i < bodies.size(); ++i)
{
for (size_t j = i + 1; j < bodies.size(); ++j)
{
float reach = bodies[i].radius + bodies[j].radius;
float gap = distance(bodies[i].pos, bodies[j].pos);
deepest = std::max(deepest, reach - gap);
}
for (int w = 0; w < 4; ++w)
{
Vec2 off = bodies[i].pos - walls[w].point;
float depth = bodies[i].radius - off.dot(walls[w].normal);
deepest = std::max(deepest, depth);
}
}
return deepest;
}In the preceding code, every pair of balls and every ball against every wall is measured again, and the deepest overlap is kept. It's a second trip over every pair, just for the readout, but seventy balls make only 2,415 pairs.
The State
The state goes after the font is loaded:
// The box's four walls, each a surface whose normal points in. Then the
// pile, the ball being held, or -1, and the settings: fixed steps or
// one a frame, how long a fixed step is, and whether to interpolate.
const Surface walls[4] = { { BOX.min, { 1, 0 } }, { BOX.min, { 0, 1 } },
{ BOX.max, { -1, 0 } }, { BOX.max, { 0, -1 } } };
std::vector<Body> bodies = dropBalls();
int held = -1;
bool fixedStep = true;
float stepTime = 1.0f / 120.0f;
bool interpolate = true;The walls are the box's four sides. The left and the top go through its top-left corner, and the right and the bottom through its bottom-right corner, each with its normal pointing in. The ball on the mouse's spring is held, its number in the list, or −1 when there's none. The demo starts with fixed steps, 120 a second, drawn between steps.
Then come the accumulator, the lag spike and the counts for the readout:
// The time not yet stepped, a lag spike waiting for the next frame, and
// the frames and steps in the last second, for the readout.
float accumulator = 0.0f;
bool spike = false;
float secondSum = 0.0f;
int frames = 0;
int steps = 0;
int shownFrames = 0;
int shownSteps = 0;The readout counts the frames and steps in each second, then shows the counts, and starts again. For that, the skeleton's timing gains one line, just after previous = now;, as in 10000 Balls:
float frameSeconds = dt; // Before the clamp, for the readout.The readout's second is measured with it, before the clamp, while the physics gets the clamped dt.
The Events
Space, R, I and L change the settings, and Enter drops a new pile. The left mouse button picks up a ball:
// Events: quitting, and the keys and clicks that happen once.
SDL_Event event;
while (SDL_PollEvent(&event))
{
if (event.type == SDL_EVENT_QUIT) running = false;
else if (event.type == SDL_EVENT_KEY_DOWN)
{
if (event.key.key == SDLK_ESCAPE) running = false;
else if (event.key.key == SDLK_L) spike = true;
else if (event.key.key == SDLK_I) interpolate = !interpolate;
else if (event.key.key == SDLK_SPACE ||
event.key.key == SDLK_R)
{
// A new kind of step starts with no time saved up.
if (event.key.key == SDLK_SPACE) fixedStep = !fixedStep;
else stepTime = (stepTime < 0.01f) ? 1.0f / 30.0f
: 1.0f / 120.0f;
accumulator = 0.0f;
}
else if (event.key.key == SDLK_RETURN)
{
bodies = dropBalls();
held = -1;
}
}
else if (event.type == SDL_EVENT_MOUSE_BUTTON_DOWN &&
event.button.button == SDL_BUTTON_LEFT)
{
// The ball under the mouse, the last drawn if two overlap.
Vec2 press = { event.button.x, event.button.y };
for (int i = 0; i < (int)bodies.size(); ++i)
if (distance(press, bodies[i].pos) <= bodies[i].radius)
held = i;
}
else if (event.type == SDL_EVENT_MOUSE_BUTTON_UP) held = -1;
}In the preceding code, L only asks for a spike, which the next frame uses. Space and R both empty the accumulator, so that the new kind of step starts fresh, with nothing saved up from the old one. A click picks the ball whose circle holds the mouse. If two overlap there, the last in the list wins, since it's drawn on top. Letting go of the button lets go of the ball, which keeps its velocity.
Each Frame's Work
The mouse's position is read once a frame:
// The mouse's position, read once a frame.
float mx, my;
SDL_GetMouseState(&mx, &my);Next, the frame's time is settled, with a lag spike if L asked for one:
// A lag spike makes this one frame a fifth of a second long, past
// the skeleton's clamp, as if the game had stalled.
float frameTime = spike ? 0.2f : dt;
spike = false;The spike is used once, then forgotten, so L makes exactly one long frame. Then comes the physics:
// The physics: fixed steps, as many as the time saved up holds, as
// in Bullet Time, or one step as long as the frame.
Vec2 mouse = { mx, my };
if (fixedStep)
{
accumulator += frameTime;
while (accumulator >= stepTime)
{
step(bodies, walls, held, mouse, stepTime);
accumulator -= stepTime;
++steps;
}
}
else
{
step(bodies, walls, held, mouse, frameTime);
++steps;
}With fixed steps, the frame's time goes into the accumulator, and the physics takes as many steps as it holds, just as Bullet Time's did. With variable steps, it takes one step, as long as the frame. Either way, every step this frame pulls toward the mouse's place in this frame. Last come the counts:
// The frames and steps in each second, counted for the readout.
++frames;
secondSum += frameSeconds;
if (secondSum >= 1.0f)
{
shownFrames = frames;
shownSteps = steps;
secondSum -= 1.0f;
frames = steps = 0;
}Every second, the frames and steps are shown, and the counts start again.
Drawing
After the skeleton clears the screen, the box and the balls are drawn:
// Each ball is drawn between its last two places, the share of a
// step the leftover time makes, when interpolating.
bool between = fixedStep && interpolate;
float alpha = between ? accumulator / stepTime : 1.0f;
setColor(renderer, SILVER);
SDL_FRect box = rectOf(BOX);
SDL_RenderRect(renderer, &box);
for (const Body& b : bodies)
{
setColor(renderer, b.color);
fillCircle(renderer, lerp(b.prevPos, b.pos, alpha), b.radius);
}With fixed steps and interpolation on, alpha is the share of a step that the accumulator holds. Otherwise, it's 1, and lerp gives each ball's place after its last step. The spring comes next, if a ball is held:
// The spring, from the ball being held to the mouse.
if (held >= 0)
{
Vec2 at = lerp(bodies[held].prevPos, bodies[held].pos, alpha);
setColor(renderer, TEXT);
SDL_RenderLine(renderer, at.x, at.y, mouse.x, mouse.y);
}It runs from the ball, where it's drawn, to the mouse. Last come the readout and the controls:
// The readout: the steps and the interpolation, then the last second's
// frames and steps, and the deepest overlap.
std::string mode = "variable steps, one a frame";
if (fixedStep)
{
long rate = std::lround(1.0f / stepTime);
mode = "fixed steps, " + std::to_string(rate) + " a second, " +
(interpolate ? "interpolated" : "not interpolated");
}
drawText(renderer, font, mode, 12, 10, fixedStep ? TEXT : AMBER);
drawText(renderer, font,
"last second: " + std::to_string(shownFrames) + " frames, " +
std::to_string(shownSteps) + " steps deepest overlap " +
fmt2(deepestOverlap(bodies, walls)) + " px",
12, 30, SILVER);
drawText(renderer, font,
"[Drag] a ball to throw it [Space] fixed or variable "
"steps [L] lag spike", 12, WINDOW_HEIGHT - 46, GREY);
drawText(renderer, font,
"[R] 120 or 30 steps a second [I] interpolate "
"[Enter] new pile [Esc] quit", 12, WINDOW_HEIGHT - 26, GREY);In the preceding code, the first line gives the kind of step, in amber for variable steps. The step's length becomes steps a second by std::lround, which rounds to the nearest whole number. The second line gives the last second's frames and steps, and the deepest overlap.
Trying It Out
Run the demo. The balls fall into the box and settle into a pile within a couple of seconds. The readout shows 120 steps a second, whatever your screen, with as many frames as your screen shows. The deepest overlap settles at about a pixel.
The next image shows a pile nine seconds in, with its largest ball held on the mouse's spring, while the mouse moves in a loop.
The heavy ball swings around behind the mouse, on a stretched spring. The readout gives 144 frames and 120 steps in the last second, and a deepest overlap of about 2 pixels. In the twenty piles that Piles measured, the deepest pair was nearly always a small ball on the floor, pressed by a bigger neighbor.
Then try it, step by step:
- Throw a ball. Drag a small ball up out of the pile, and swing it around. It follows the mouse closely. Let go mid-swing, and it flies on, and lands in the pile. Then try the largest ball you can find. It hangs further below the mouse, swings wider, and shoves the pile aside when it lands.
- Stall the fixed steps. Press L. Nothing seems to happen, though the physics just caught up a fifth of a second in one frame.
- Stall the variable steps. Press Space, and the readout turns amber. Then press L. The pile jumps, and settles into a new shape.
- Slow the steps. Press Space for fixed steps again, then R, for 30 steps a second. Drag a ball around, and it still moves smoothly. Press I to turn interpolation off, and the same ball moves in jerks.
- Watch the pile sink. At 30 steps a second, the deepest overlap rises to about 6 or 7 pixels. Press R to go back to 120, and it falls back to about a pixel.
The next image shows step 3, just after the spike.
The balls are crushed into each other, with a deepest overlap of 17.54 pixels, and a typical ball moved about 15 pixels in that one step. A moment later, the passes push them apart again, into a different heap. The fixed steps took the same fifth of a second in their stride. That's a small physics engine at work: mass, impulses, forces and a pile, on a clock that keeps it the same everywhere.
FAQ
Q) Why 120 steps a second, and not 60?
A) It's a trade between cost and accuracy. Each step costs the same to compute, so 120 cost twice as much as 60. But a pile settles better with shorter steps, as Piles measured, and fast things tunnel less. Many games step less often: Unity, for one, steps its physics 50 times a second unless it's told otherwise. Measure your own game, with the deepest overlap and the time a step takes.
Q) Other engines leave a little of each overlap alone, and push out only part of the rest. Why doesn't Impulse?
A) Those are common in engines that answer contacts through velocities and keep each contact from one step to the next, and the little overlap left alone is called slop. Impulse moves positions apart directly, and finds its contacts afresh in every pass. Tried on Impulse's twenty piles, the two made no pile stiller, so Impulse leaves them out.
Q) Is a variable step always wrong?
A) No. Small, steady steps of dt work well for most motion, and Part 2's demos used them. The trouble comes with long steps, and with piles and stiff springs. It comes too whenever two machines, or two runs, must come to the same answer.
Q) Will two different computers give exactly the same answer?
A) The same program, built the same way, on the same kind of processor, will. But floating-point arithmetic can round differently with another compiler, other build settings or another kind of processor. In a pile, a difference in the last digit grows until the balls lie somewhere else. Games that must agree to the last bit take great care over it, and some use whole numbers instead. Networked strategy games that send each other only the players' commands are one example.
Q) Why draw one step behind, rather than guess ahead?
A) Drawing ahead, at the last place plus the velocity times the leftover time, is called extrapolation, and it has no lag. But it guesses, and it guesses wrong whenever something changes during the step. A ball drawn ahead into a collision is drawn inside its neighbor, then jumps back. Drawing between two places that really happened is never wrong, only late, and a step late is less than a frame on a 60 Hz screen.
Exercises
The first three exercises need only a pencil. The others change Impulse.
- An impulse by hand (paper). A ball of 2 kilograms, moving at 3 meters a second, hits a ball of 1 kilogram at rest, head on. Find both velocities afterward, with a restitution of 1, and with 0.5. Check that the momentum is the same each time, and find how much of the kinetic energy each bounce keeps.
- The accumulator by hand (paper). The physics steps 60 times a second, and the screen shows 50 frames a second. For the first five frames, how many steps does each frame take, and what's alpha after it?
- A hanging ball (paper). How far below the mouse does a held ball of radius 20 hang, once it's still? And a ball of radius 14?
- A peg (code). Give one ball an inverse mass of 0, and put it in the middle of the box. What happens to the balls that land on it? Can you drag it with the mouse, and why?
- Slow motion (code). Add a key that runs the world at half speed, by putting only half of each frame's time into the accumulator. Why are the steps just as accurate as before? What happens if you put in twice the frame's time instead?
For the code exercises, work on a copy of the demo's folder, so that the original stays as the chapter describes it.
AI Exercise (Optional)
A pile is a fine thing to knock over. With an AI's help, you can turn Impulse into a small siege, with a tower of balls and a cannon that fires balls of different masses at it. Open your AI chatbot of choice, and try a prompt like this:
"I have a C++ demo using SDL3, with a Vec2 struct and a small physics engine. A Body struct holds pos, vel, force, radius, mass, invMass and prevPos. The function addForces() adds gravity, integrate() uses semi-implicit Euler, and respond(a, b, n, depth) pushes two bodies apart by their inverse masses and applies the impulse j = -(1 + e) × closing / (1/mA + 1/mB). The physics takes fixed steps of 1/120 s, with an accumulator. Please build a tower of 28 balls of radius 14, stacked in a triangle on the floor of a 1000 by 700 window. Add a cannon at the left that fires a ball of radius 14 toward the mouse when I click. Keys 1, 2 and 3 make the cannonball 1, 10 or 100 times as heavy as a tower ball, and its color shows which. Keep the walls as bodies with an inverse mass of 0. Explain why the heaviest cannonball hardly slows down as it goes through the tower."
That prompt describes your engine, so the AI builds on it, rather than writing an engine of its own. It changes only the cannonball's mass, so that what you see is mass at work. And it asks for the reason, which you can check against this chapter's worked example.
Then give the cannonball an inverse mass of 0, and see what happens to something nothing can stop. Then set the restitution to 1, and watch the tower fall in a different way.
Summary
Mass is how hard a body is to move, and momentum is its mass times its velocity. A collision can't change the total momentum, and the restitution decides how fast the bodies come apart. Together, those two facts give the impulse, j = −(1 + e) × closing / (1/mA + 1/mB). It changes each body's velocity by j over its mass, in opposite directions. So a heavy body moves less, and a wall, with an inverse mass of 0, turns the formula into Chapter 18's bounce. The push out of an overlap is shared by inverse mass in the same way. Forces add up in an accumulator each step: gravity as mass times g, which still gives every body the same fall, and a damped spring to the mouse, which shows the mass at once. Chapter 7's semi-implicit Euler turns them into motion. A pile needs several passes over its contacts and short steps, and with four passes at 120 steps a second, seventy balls settle with their deepest overlap under a pixel. The step's length changes the answer, so a fixed timestep steps the physics by the same time, again and again, from an accumulator. Every machine then takes the same steps, and a long frame becomes many ordinary steps. The clamp keeps a slow machine in slow motion, rather than a spiral of death. Drawing each body between its last two places, by alpha, keeps the motion smooth, one step behind. Chapter 21 turns to randomness, and to noise, the smooth kind of randomness that shapes terrain and clouds.