Hermite, Catmull-Rom and Constant-Speed Paths
What You’ll Learn
Section titled “What You’ll Learn”How to get a smooth curve through a set of placed points rather than one steered by handles beside them - which is what a path through waypoints actually needs. Where the tangents come from when nobody authors them. And then the loose end Section 4.3 left: equal steps in are not equal distances along a curve, which is why a camera moving at “constant speed” along a spline speeds up and slows down until you fix it.
The Problem With Handles
Section titled “The Problem With Handles”A cubic Bezier touches its first and last control point and only pulls towards the middle two. For drawing a shape that is exactly right. For a path through waypoints it is backwards: you want the curve to visit the points, and you do not want to author handles for each one.
Hermite curves reframe the same cubic. Instead of four points, they take two points and two tangents - a position and a velocity at each end:
The four weights are chosen so that the curve starts at with velocity and ends at with velocity - all four exactly. The build check confirms it: the endpoints come back bit-identical, and the tangents to .
It is the same family of curve as before, just parameterised differently. A Hermite segment converted to a Bezier puts the handles one third of the way along each tangent:
That is the same factor of three that showed up in Section 4.3’s derivative, seen from the other side. The check runs 401 values of through both forms and asserts they agree.
Catmull-Rom: Guessing the Tangents
Section titled “Catmull-Rom: Guessing the Tangents”Hermite still needs tangents from somewhere. Catmull-Rom supplies them with one rule:
The direction a waypoint is “heading” is the direction from the point before it to the point after it. That is the obvious guess, and it turns out to be a good one - it is the entire algorithm.
The result passes through every point, is smooth at every joint, and needs nothing authored beyond the points themselves.
src/lib/gamedev/demos/spline.scene.ts /**
* A Catmull-Rom path through movable waypoints, with the tangent it picks at each one.
*/
import * as THREE from "three";
import { catmullRomAt, catmullTangent, segmentCount } from "../splines.ts";
import type { Vec2 } from "../matrices.ts";
import { makeCanvas, addSlider, addReadout, addButtonRow } from "./ui.ts";
import type { MountFn } from "./runner.ts";
const HALF_W = 2.7;
const LIMIT = 2.5;
const POINT = 0xf0883e;
const TANGENT = 0xd2a8ff;
const CURVE = 0x39d3c3;
const mount: MountFn = (el) => {
const { renderer, width, height, background } = makeCanvas(el, 320);
const halfH = (HALF_W * height) / width;
const scene = new THREE.Scene();
scene.background = background;
const camera = new THREE.OrthographicCamera(
-HALF_W,
HALF_W,
halfH,
-halfH,
0.1,
10,
);
camera.position.z = 5;
const points: Vec2[] = [
{ x: -2.3, y: -0.9 },
{ x: -1.7, y: 0.8 },
{ x: -1.2, y: -0.4 },
{ x: 1.4, y: 0.9 },
{ x: 2.3, y: -0.7 },
];
const addLine = (color: number, dashed = false) => {
const geom = new THREE.BufferGeometry();
const mesh = new THREE.Line(
geom,
dashed
? new THREE.LineDashedMaterial({ color, dashSize: 0.07, gapSize: 0.06 })
: new THREE.LineBasicMaterial({ color }),
);
scene.add(mesh);
return (pts: Vec2[]) => {
geom.setFromPoints(pts.map((p) => new THREE.Vector3(p.x, p.y, 0)));
if (dashed) mesh.computeLineDistances();
};
};
const curveLine = addLine(CURVE);
const legs = addLine(0x3d444d, true);
// One dashed segment per waypoint, showing the tangent Catmull-Rom chose there.
const tangentLines = points.map(() => addLine(TANGENT));
const dot = (color: number, r: number) => {
const m = new THREE.Mesh(
new THREE.CircleGeometry(r, 18),
new THREE.MeshBasicMaterial({ color }),
);
scene.add(m);
return m;
};
const waypointDots = points.map(() => dot(POINT, 0.07));
const rider = dot(CURVE, 0.095);
const ring = new THREE.Mesh(
new THREE.RingGeometry(0.105, 0.135, 20),
new THREE.MeshBasicMaterial({ color: POINT }),
);
scene.add(ring);
let selected = 2;
const show = addReadout(el);
const setActive = addButtonRow(
el,
points.map((_, i) => ({
label: `P${i}`,
apply: () => {
selected = i;
xs.set(points[i].x);
ys.set(points[i].y);
draw();
},
})),
);
const xs = addSlider(
el,
"waypoint x",
-LIMIT,
LIMIT,
points[2].x,
moveSelected,
"",
0.1,
);
const ys = addSlider(
el,
"waypoint y",
-LIMIT,
LIMIT,
points[2].y,
moveSelected,
"",
0.1,
);
const tension = addSlider(el, "tension", 0, 1, 0.5, draw, "", 0.05);
const t = addSlider(
el,
"t along the whole path",
0,
1,
0.35,
draw,
"",
0.005,
);
function moveSelected() {
points[selected] = { x: xs(), y: ys() };
draw();
}
const canvas = renderer.domElement;
let dragging = false;
const toWorld = (event: PointerEvent): Vec2 => {
const rect = canvas.getBoundingClientRect();
return {
x: ((event.clientX - rect.left) / rect.width) * 2 * HALF_W - HALF_W,
y: -(((event.clientY - rect.top) / rect.height) * 2 * halfH - halfH),
};
};
const onDown = (event: PointerEvent) => {
const w = toWorld(event);
let best = 0;
let bestDist = Infinity;
points.forEach((p, i) => {
const d = Math.hypot(p.x - w.x, p.y - w.y);
if (d < bestDist) {
bestDist = d;
best = i;
}
});
if (bestDist > 0.55) return;
selected = best;
dragging = true;
canvas.setPointerCapture(event.pointerId);
onMove(event);
};
const onMove = (event: PointerEvent) => {
if (!dragging) return;
const w = toWorld(event);
points[selected] = {
x: Math.max(-LIMIT, Math.min(LIMIT, w.x)),
y: Math.max(-LIMIT, Math.min(LIMIT, w.y)),
};
xs.set(points[selected].x);
ys.set(points[selected].y);
draw();
};
const onUp = () => {
dragging = false;
};
canvas.addEventListener("pointerdown", onDown);
canvas.addEventListener("pointermove", onMove);
canvas.addEventListener("pointerup", onUp);
canvas.addEventListener("pointercancel", onUp);
function draw() {
const k = tension();
const path: Vec2[] = [];
for (let i = 0; i <= 220; i += 1)
path.push(catmullRomAt(points, i / 220, k));
curveLine(path);
legs(points);
points.forEach((p, i) => {
waypointDots[i].position.set(p.x, p.y, 0);
const m = catmullTangent(points, i, k);
// Drawn at a third of its length, which is where the equivalent Bezier handle sits.
tangentLines[i]([
{ x: p.x - m.x / 3, y: p.y - m.y / 3 },
{ x: p.x + m.x / 3, y: p.y + m.y / 3 },
]);
});
const here = catmullRomAt(points, t(), k);
rider.position.set(here.x, here.y, 0);
ring.position.set(points[selected].x, points[selected].y, 0);
setActive(selected);
const segs = segmentCount(points);
show(
`moving P${selected} \u00B7 tension ${k.toFixed(2)} \u00B7 ` +
`the path meets every waypoint, at t = 0, ${(1 / segs).toFixed(2)}, ${(2 / segs).toFixed(2)}, ...`,
);
renderer.render(scene, camera);
}
draw();
return () => {
canvas.removeEventListener("pointerdown", onDown);
canvas.removeEventListener("pointermove", onMove);
canvas.removeEventListener("pointerup", onUp);
canvas.removeEventListener("pointercancel", onUp);
renderer.dispose();
};
};
export default mount; Drag a waypoint and watch two things. The path always goes through every orange dot - the build check asserts that to at all five. And the purple segment at each waypoint is the tangent Catmull-Rom chose, drawn at a third of its length so it sits where the equivalent Bezier handle would.
Notice that moving one waypoint only disturbs the curve near it. That is local control, and it is why this is the format for a designer-authored path: nudging one point cannot ripple down the whole spline.
The tension slider scales those tangents. At 0 every tangent is zero, so the path collapses to straight lines with a stop at each corner. The standard is what makes come out as half the neighbour gap - which is where the division by two in the formula comes from.
| Continuity | Catmull-Rom | Why |
|---|---|---|
| C0 | yes | consecutive segments share a waypoint |
| C1 | yes | both segments use the same tangent at that point |
| C2 | no | curvature can jump at a joint |
C1 is what Section 4.3 said a camera needs, and Catmull-Rom gives it for free. C2 needs B-splines, which buy it by giving up passing through the points at all - a trade worth knowing about and rarely worth making for a waypoint path.
source Hermite, Catmull-Rom, and the arc-length table
/**
* Curves that go **through** the points you place, and the lookup table that makes travelling
* along one happen at a steady speed.
*
* Section 4.3's Bezier curves are steered by handles the curve never touches, which is right for
* drawing and wrong for a path through waypoints. Hermite curves take a point and a *tangent* at
* each end instead, and Catmull-Rom works out the tangents for you - so placing four points gives
* you a smooth path through all four with nothing else to tune.
*/
import { lerp } from "./interpolation.ts";
import type { Vec2 } from "./matrices.ts";
const sub = (a: Vec2, b: Vec2): Vec2 => ({ x: a.x - b.x, y: a.y - b.y });
const scale = (a: Vec2, k: number): Vec2 => ({ x: a.x * k, y: a.y * k });
/**
* The four Hermite basis functions, in the order they weight
* `[start point, start tangent, end point, end tangent]`.
*
* Their shape encodes the whole contract: at `t = 0` only the first is non-zero and at `t = 1`
* only the third is, so the curve hits both points exactly. The two tangent weights vanish at
* both ends but have slope 1 there, which is what makes the tangents come out as asked.
*/
export function hermiteBasis(t: number): [number, number, number, number] {
const t2 = t * t;
const t3 = t2 * t;
return [
2 * t3 - 3 * t2 + 1, // start point
t3 - 2 * t2 + t, // start tangent
-2 * t3 + 3 * t2, // end point
t3 - t2, // end tangent
];
}
/** A cubic through `p0` and `p1`, leaving with velocity `m0` and arriving with velocity `m1`. */
export function hermiteAt(
p0: Vec2,
m0: Vec2,
p1: Vec2,
m1: Vec2,
t: number,
): Vec2 {
const [a, b, c, d] = hermiteBasis(t);
return {
x: a * p0.x + b * m0.x + c * p1.x + d * m1.x,
y: a * p0.y + b * m0.y + c * p1.y + d * m1.y,
};
}
/** The velocity along a Hermite segment, by differentiating the basis. */
export function hermiteTangent(
p0: Vec2,
m0: Vec2,
p1: Vec2,
m1: Vec2,
t: number,
): Vec2 {
const t2 = t * t;
const a = 6 * t2 - 6 * t;
const b = 3 * t2 - 4 * t + 1;
const c = -6 * t2 + 6 * t;
const d = 3 * t2 - 2 * t;
return {
x: a * p0.x + b * m0.x + c * p1.x + d * m1.x,
y: a * p0.y + b * m0.y + c * p1.y + d * m1.y,
};
}
/**
* The same segment written as a cubic Bezier, which is what Section 4.3 already knows how to draw.
*
* The handles sit **one third** of the way along each tangent. That factor of three is the same
* one that appeared in `cubicTangent`, seen from the other side.
*/
export function hermiteToBezier(
p0: Vec2,
m0: Vec2,
p1: Vec2,
m1: Vec2,
): [Vec2, Vec2, Vec2, Vec2] {
return [
p0,
{ x: p0.x + m0.x / 3, y: p0.y + m0.y / 3 },
{ x: p1.x - m1.x / 3, y: p1.y - m1.y / 3 },
p1,
];
}
// ---- Catmull-Rom: let the points choose the tangents -------------------------------------
/**
* The tangent Catmull-Rom picks at point `i`: half the gap between its two neighbours.
*
* That single choice is the whole algorithm. The direction a waypoint is "heading" is taken to be
* the direction from the one before it to the one after it, which is both the obvious guess and a
* good one. Ends have only one neighbour, so they use the one-sided gap.
*/
export function catmullTangent(
points: readonly Vec2[],
i: number,
tension = 0.5,
): Vec2 {
const last = points.length - 1;
if (i <= 0) return scale(sub(points[1], points[0]), tension * 2);
if (i >= last) return scale(sub(points[last], points[last - 1]), tension * 2);
return scale(sub(points[i + 1], points[i - 1]), tension);
}
/** How many segments a point list spans. */
export const segmentCount = (points: readonly Vec2[]) => points.length - 1;
/** Which segment a global `t` falls in, and how far through it. */
export function locate(
points: readonly Vec2[],
t: number,
): { segment: number; local: number } {
const segs = segmentCount(points);
const scaled = Math.min(Math.max(t, 0), 1) * segs;
const segment = Math.min(Math.floor(scaled), segs - 1);
return { segment, local: scaled - segment };
}
/** A point on the whole Catmull-Rom chain, with `t` running 0 to 1 across every segment. */
export function catmullRomAt(
points: readonly Vec2[],
t: number,
tension = 0.5,
): Vec2 {
const { segment, local } = locate(points, t);
return hermiteAt(
points[segment],
catmullTangent(points, segment, tension),
points[segment + 1],
catmullTangent(points, segment + 1, tension),
local,
);
}
/** The velocity along the chain. Note it is per-segment, so it scales with segment length. */
export function catmullRomTangent(
points: readonly Vec2[],
t: number,
tension = 0.5,
): Vec2 {
const { segment, local } = locate(points, t);
return hermiteTangent(
points[segment],
catmullTangent(points, segment, tension),
points[segment + 1],
catmullTangent(points, segment + 1, tension),
local,
);
}
// ---- Arc length: equal steps in t are not equal distances --------------------------------
/**
* A table of "how far along the curve am I at this `t`", built by walking it in small pieces.
*
* There is no shortcut here. The arc length of a cubic has no closed form worth using, so the
* honest approach is to sample it densely, add up the straight-line hops, and interpolate. This is
* the standard trick and it is why every engine's spline has a "build lookup table" step.
*/
export type ArcTable = {
/** The `t` at each sample. */
ts: number[];
/** Distance travelled by that sample. */
distances: number[];
total: number;
};
export function buildArcTable(
at: (t: number) => Vec2,
samples = 256,
): ArcTable {
const ts: number[] = [0];
const distances: number[] = [0];
let running = 0;
let previous = at(0);
for (let i = 1; i <= samples; i += 1) {
const t = i / samples;
const here = at(t);
running += Math.hypot(here.x - previous.x, here.y - previous.y);
ts.push(t);
distances.push(running);
previous = here;
}
return { ts, distances, total: running };
}
/**
* The `t` that lands you a given **distance** along the curve.
*
* Binary search the table, then lerp between the two straddling samples. This is the inverse of
* the table, and it is the function that turns "move at 3 meters per second" into a `t`.
*/
export function tAtDistance(table: ArcTable, distance: number): number {
const target = Math.min(Math.max(distance, 0), table.total);
let low = 0;
let high = table.distances.length - 1;
while (high - low > 1) {
const mid = (low + high) >> 1;
if (table.distances[mid] <= target) low = mid;
else high = mid;
}
const span = table.distances[high] - table.distances[low];
const within = span < 1e-12 ? 0 : (target - table.distances[low]) / span;
return lerp(table.ts[low], table.ts[high], within);
}
/** The `t` that lands you a given **fraction** of the way along, by distance rather than by `t`. */
export function tAtFraction(table: ArcTable, u: number): number {
return tAtDistance(table, u * table.total);
}
/** The other direction: how far along the curve a given `t` actually is. */
export function distanceAtT(table: ArcTable, t: number): number {
const target = Math.min(Math.max(t, 0), 1);
let low = 0;
let high = table.ts.length - 1;
while (high - low > 1) {
const mid = (low + high) >> 1;
if (table.ts[mid] <= target) low = mid;
else high = mid;
}
const span = table.ts[high] - table.ts[low];
const within = span < 1e-12 ? 0 : (target - table.ts[low]) / span;
return lerp(table.distances[low], table.distances[high], within);
} Equal Steps in t Are Not Equal Distances
Section titled “Equal Steps in t Are Not Equal Distances”Now the loose end, and it catches almost everybody once.
A path is a function of . Nothing in that function promises that a given change in covers a given amount of ground. Segments spanning far-apart waypoints get the same slice of as segments spanning close-together ones, so a dot advancing at a steady rate races through the long stretches and crawls through the short ones.
Below, two dots on one path. Orange steps evenly. Teal steps distance evenly. The small dots are ticks at even steps of each dot’s own input.
src/lib/gamedev/demos/arclength.scene.ts /**
* Two dots on one path: one stepping t evenly, one stepping distance evenly. They separate.
*/
import * as THREE from "three";
import { distanceAtT } from "../splines.ts";
import type { Vec2 } from "../matrices.ts";
import {
TABLE,
WAYPOINTS,
byDistance,
byParameter,
pathAt,
} from "./spline-shared.ts";
import { makeCanvas, addSlider, addReadout } from "./ui.ts";
import type { MountFn } from "./runner.ts";
const HALF_W = 2.7;
const TICKS = 24;
const BY_T = 0xf0883e;
const BY_S = 0x39d3c3;
const mount: MountFn = (el) => {
const { renderer, width, height, background } = makeCanvas(el, 300);
const halfH = (HALF_W * height) / width;
const scene = new THREE.Scene();
scene.background = background;
const camera = new THREE.OrthographicCamera(
-HALF_W,
HALF_W,
halfH,
-halfH,
0.1,
10,
);
camera.position.z = 5;
const pathPts: Vec2[] = [];
for (let i = 0; i <= 300; i += 1) pathPts.push(pathAt(i / 300));
scene.add(
new THREE.Line(
new THREE.BufferGeometry().setFromPoints(
pathPts.map((p) => new THREE.Vector3(p.x, p.y, 0)),
),
new THREE.LineBasicMaterial({ color: 0x3d444d }),
),
);
// The waypoints, faint, for context.
for (const p of WAYPOINTS) {
const m = new THREE.Mesh(
new THREE.CircleGeometry(0.045, 12),
new THREE.MeshBasicMaterial({ color: 0x545d68 }),
);
m.position.set(p.x, p.y, 0);
scene.add(m);
}
/* Ticks at even steps of each walk's own input. Where they bunch up, that walk is slow; where
they spread out, it is fast. The whole lesson is in the spacing. */
const addTicks = (
walk: (u: number) => Vec2,
color: number,
radius: number,
) => {
for (let i = 0; i <= TICKS; i += 1) {
const p = walk(i / TICKS);
const m = new THREE.Mesh(
new THREE.CircleGeometry(radius, 10),
new THREE.MeshBasicMaterial({ color }),
);
m.position.set(p.x, p.y, 0);
scene.add(m);
}
};
addTicks(byParameter, BY_T, 0.035);
addTicks(byDistance, BY_S, 0.035);
const rider = (color: number) => {
const m = new THREE.Mesh(
new THREE.CircleGeometry(0.1, 18),
new THREE.MeshBasicMaterial({ color }),
);
scene.add(m);
return m;
};
const tDot = rider(BY_T);
const sDot = rider(BY_S);
const link = new THREE.Line(
new THREE.BufferGeometry(),
new THREE.LineBasicMaterial({ color: 0x7d8590 }),
);
scene.add(link);
const show = addReadout(el);
const u = addSlider(
el,
"fraction of the way through",
0,
1,
0.35,
draw,
"",
0.005,
);
function draw() {
const a = byParameter(u());
const b = byDistance(u());
tDot.position.set(a.x, a.y, 0);
sDot.position.set(b.x, b.y, 0);
link.geometry.setFromPoints([
new THREE.Vector3(a.x, a.y, 0),
new THREE.Vector3(b.x, b.y, 0),
]);
// How far each dot has genuinely travelled, as a share of the whole path.
const alongT = distanceAtT(TABLE, u()) / TABLE.total;
show(
`orange stepped t evenly and is ${(alongT * 100).toFixed(0)}% along \u00B7 ` +
`teal stepped distance evenly and is ${(u() * 100).toFixed(0)}% along`,
);
renderer.render(scene, camera);
}
draw();
return () => renderer.dispose();
};
export default mount; Look at the orange ticks: bunched where the waypoints are close together, spread out where they are far apart. The teal ticks are evenly spread along the whole path, which is what “constant speed” should mean. Drag the slider and the two dots pull apart by a large fraction of the path.
Here is the size of it:
src/lib/gamedev/demos/arcmath.ts /** How uneven a uniform-t walk really is, and what the lookup table costs to build. */
import { buildArcTable } from "../splines.ts";
import {
TABLE,
byDistance,
byParameter,
hopSpread,
pathAt,
} from "./spline-shared.ts";
import type { Demo } from "./runner.ts";
const demo: Demo = (log) => {
const byT = hopSpread(byParameter, 200);
const byS = hopSpread(byDistance, 200);
log("path length, from a 256-sample table", TABLE.total.toFixed(4));
log(
"stepping t evenly: longest hop over shortest",
`${byT.ratio.toFixed(2)}x`,
"so the speed varies by nearly eight times",
);
log(
"stepping distance evenly: the same ratio",
`${byS.ratio.toFixed(2)}x`,
"the small residual is chord versus arc, not the method",
);
log(
"table with 32 samples",
buildArcTable(pathAt, 32).total.toFixed(4),
"chords cut corners, so a coarse table underestimates",
);
log(
"table with 1024 samples",
buildArcTable(pathAt, 1024).total.toFixed(4),
"converging upward on the true length",
);
};
export default demo; Nearly eight times. Stepping evenly, the longest hop is 7.8 times the shortest, so a camera on this path would visibly surge and stall. After reparametrizing, that ratio is 1.08.
The lookup table
Section titled “The lookup table”There is no closed form for the arc length of a cubic worth using, so the honest approach is the one every engine takes:
- Walk the curve in many small steps, summing straight-line distances.
- Store the running total against each .
- To move a distance , binary search the table for and interpolate between the two straddling entries.
That is buildArcTable and tAtDistance. Build it once when the path is created, not per frame.
The table has one bias worth knowing: chords cut corners, so it always underestimates the true length, and the estimate rises as you add samples. Measured on this path: 8.074 at 32 samples, 8.096 at 128, 8.0974 at 1024. The check asserts that ordering, and that it has all but converged by 128 - which is why a few hundred samples is the usual choice.
With the table in place, moving at a genuine speed becomes what you would want to write:
travelled += speed * dt; // Section 4.1's dt, doing its jobconst t = tAtDistance(table, travelled);object.position = pathAt(t);And that is Part 4 assembled: a frame-rate-independent step, a distance, a table, and a curve.
Where This Shows Up
Section titled “Where This Shows Up”- Camera rails in cutscenes, which need both C1 continuity and arc-length parametrization or the shot lurches at every waypoint.
- Patrol routes and rail shooters, where a guard should walk at a steady pace regardless of how the level designer spaced the nodes.
- Racing lines and track splines, where distance along the path is the primary coordinate - lap position, checkpoints, opponent placement.
- Placing objects evenly along a curve - fence posts, road markings - which is the same lookup table used at authoring time rather than at runtime.
- Animation retiming, where an easing curve from Section 4.2 gets applied to the distance rather than to , so the easing means what it says.