Computer Graphics (rasterisation, ray tracing, WebGPU) Module 5 – 3D transformations, rotations, cameras and projection

Scene graphs and hierarchical transforms

Compute world matrices down a scene graph, animate jointed figures with local transforms, cache them with dirty flags, and attach objects without a jump.

Intermediate
20 minutes
Examples run with Node.js 24.21.0 and quickjs 0.32.0
By MySmartCoPilot

Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

What you will learn

Compute world matrices from local transforms along a scene-graph hierarchy
Move an articulated figure by changing local transforms only
Convert between local and world space for picking and attaching objects
Explain why a non-uniformly scaled parent shears its turned children, and avoid it

Before you start

3D transformations, Euler angles and gimbal lock

What you’ll learn · Before you start

What you will learn

Compute world matrices from local transforms along a scene-graph hierarchy
Move an articulated figure by changing local transforms only
Convert between local and world space for picking and attaching objects
Explain why a non-uniformly scaled parent shears its turned children, and avoid it

Before you start

3D transformations, Euler angles and gimbal lock

On this page

Bend a robot arm’s elbow by 90° and its fingertip moves from (0, 5, 0) to (−2, 3, 0), although nobody touched the fingertip. A ring of twelve dancers turns, and 85 parts move together while every hand stays in its neighbour’s. Both work because each part stores only how it sits on its parent, and a tree of those local transforms, a scene graph, works out where everything is.

You will compute world matrices down a hierarchy, animate a jointed figure by changing joints only, cache world matrices with dirty flags and count what that saves, move between local and world space to pick and to attach objects, and see why a stretched parent bends its children out of shape. Every number comes from a program that runs on this page.

A node’s world matrix is its parent’s world matrix times its own

A scene graph: A tree of nodes in which each node stores a transform relative to its parent, so that moving a node moves everything below it. is a tree of nodes. Each node holds a local transform: A node's own placement in its parent's coordinates, as a matrix or as a translation, rotation and scale. Animation changes local transforms., which places it in its parent’s coordinates, and its world matrix: The matrix that takes a node's own coordinates to world coordinates: its parent's world matrix times its local transform, or its local transform for a root. follows from those alone:

W_{\text{child}} = W_{\text{parent}}\, L_{\text{child}}, \qquad W_{\text{root}} = L_{\text{root}}

In words: start at the root and multiply one more local transform on the right at every level. glTF’s specification defines a node’s global transformation exactly so, as the product of its parent’s global matrix and its own local one, and three.js keeps both on every object, matrix for the local transform and matrixWorld for the world one. The robot arm of this lesson has five nodes in a chain: a base that turns about the vertical, a shoulder 1 unit up, an elbow 2 further, a wrist 1.5 further and a fingertip 0.5 further, each joint turning about its own z axis. Step through its world matrices with the elbow bent 90°:

Interactive · step by step World matrices of the robot arm, from the root down Step down the arm. Each row multiplies the parent's world matrix by one more local transform; watch the elbow's turn carry everything below it.

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text

The root. The base has no parent, so its world matrix is its own local transform, a turn of 0° about the vertical. Its origin is the world's origin.
One level down. The shoulder's world matrix is the base's world matrix times the shoulder's local T(0, 1, 0). Its origin lands 1 unit up, at (0, 1, 0).
The bent joint. The elbow's local transform moves 2 up and then turns 90° about z. Its origin is at (0, 3, 0), and the turn is now part of its world matrix, so every node below inherits it.
Inherited turn. The wrist's local transform is only T(0, 1.5, 0), a move along its parent's y axis. That axis now points along world −x, so the wrist lands at (−1.5, 3, 0).
The fingertip. Another 0.5 along the same turned axis puts the fingertip at (−2, 3, 0), where the program printed it. Only the elbow's local transform changed; the wrist and the fingertip followed.

The elbow’s turn became part of its world matrix, so the wrist’s local move of 1.5 along y went along the turned axis, world −x. The program builds the arm, computes every world matrix by walking the tree, and checks the fingertip against the same product written out by hand, for the straight arm and three seeded poses:

A five-node robot arm, walked from the root JavaScript · arm/scene_graph.mjs

// A robot arm as a scene graph of five nodes: base → shoulder → elbow → wrist → fingertip. Each node keeps
// only its local transform, an offset from its parent and its own joint turn; its world matrix is the
// parent's world matrix times its local one. 4 x 4 matrices as lists of rows, acting on column vectors.

const rad = (degrees) => (degrees * Math.PI) / 180;
const mul = (a, b) => a.map((row) => [0, 1, 2, 3].map((c) => row.reduce((s, v, k) => s + v * b[k][c], 0)));
const T = (x, y, z) => [[1, 0, 0, x], [0, 1, 0, y], [0, 0, 1, z], [0, 0, 0, 1]];
const Ry = (a) => [[Math.cos(a), 0, Math.sin(a), 0], [0, 1, 0, 0], [-Math.sin(a), 0, Math.cos(a), 0], [0, 0, 0, 1]];
const Rz = (a) => [[Math.cos(a), -Math.sin(a), 0, 0], [Math.sin(a), Math.cos(a), 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]];
const origin = (m) => [m[0][3], m[1][3], m[2][3]];

// Each node: its parent, its offset from the parent's origin, and the axis its joint turns about.
const ARM = [
  { name: 'base', parent: null, offset: [0, 0, 0], joint: Ry },
  { name: 'shoulder', parent: 'base', offset: [0, 1, 0], joint: Rz },
  { name: 'elbow', parent: 'shoulder', offset: [0, 2, 0], joint: Rz },
  { name: 'wrist', parent: 'elbow', offset: [0, 1.5, 0], joint: Rz },
  { name: 'fingertip', parent: 'wrist', offset: [0, 0.5, 0], joint: null },
];

// Walk the tree from the root: world(child) = world(parent) × local(child).
function worldMatrices(pose) {
  const world = {};
  for (const node of ARM) {
    const local = node.joint ? mul(T(...node.offset), node.joint(rad(pose[node.name]))) : T(...node.offset);
    world[node.name] = node.parent ? mul(world[node.parent], local) : local;
  }
  return world;
}
// The same fingertip written out by hand as one product, root first.
function byHand(p) {
  return mul(Ry(rad(p.base)), mul(T(0, 1, 0), mul(Rz(rad(p.shoulder)), mul(T(0, 2, 0), mul(Rz(rad(p.elbow)), mul(T(0, 1.5, 0), mul(Rz(rad(p.wrist)), T(0, 0.5, 0))))))));
}

const num = (v) => {
  const r = Number(v.toFixed(3));
  return Object.is(r, -0) ? '0' : String(r);
};
const show = (v) => `(${v.map(num).join(', ')})`;

let seed = 2; // mulberry32
const random = () => {
  seed = (seed + 0x6d2b79f5) | 0;
  let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
const poses = [{ base: 0, shoulder: 0, elbow: 0, wrist: 0 }];
for (let i = 0; i < 3; i++) poses.push({ base: Math.round(random() * 360 - 180), shoulder: Math.round(random() * 120 - 60), elbow: Math.round(random() * 150 - 75), wrist: Math.round(random() * 90 - 45) });

for (const p of poses) {
  const world = worldMatrices(p);
  const tip = origin(world.fingertip);
  const hand = origin(byHand(p));
  const same = tip.every((v, i) => Math.abs(v - hand[i]) < 1e-12);
  console.log(`base ${p.base}°, shoulder ${p.shoulder}°, elbow ${p.elbow}°, wrist ${p.wrist}°`);
  console.log(`  elbow at ${show(origin(world.elbow))}, wrist at ${show(origin(world.wrist))}, fingertip at ${show(tip)}`);
  console.log(`  the hand-written product agrees within 1e-12: ${same}`);
}

// Change one local transform: only the nodes below it move.
const bent = { ...poses[0], elbow: 90 };
const before = worldMatrices(poses[0]);
const after = worldMatrices(bent);
console.log('');
console.log('elbow from 0° to 90°, every other joint at 0°:');
for (const node of ARM) console.log(`  ${node.name.padEnd(10)} ${show(origin(before[node.name]))} -> ${show(origin(after[node.name]))}`);

Output

base 0°, shoulder 0°, elbow 0°, wrist 0°
  elbow at (0, 3, 0), wrist at (0, 4.5, 0), fingertip at (0, 5, 0)
  the hand-written product agrees within 1e-12: true
base 84°, shoulder -21°, elbow -32°, wrist 3°
  elbow at (0.075, 2.867, -0.713), wrist at (0.2, 3.77, -1.904), fingertip at (0.24, 4.091, -2.285)
  the hand-written product agrees within 1e-12: true
base 135°, shoulder 16°, elbow 0°, wrist -13°
  elbow at (0.39, 2.923, 0.39), wrist at (0.682, 4.364, 0.682), fingertip at (0.701, 4.864, 0.701)
  the hand-written product agrees within 1e-12: true
base 101°, shoulder -46°, elbow 43°, wrist -27°
  elbow at (-0.275, 2.389, -1.412), wrist at (-0.289, 3.887, -1.489), fingertip at (-0.337, 4.32, -1.735)
  the hand-written product agrees within 1e-12: true

elbow from 0° to 90°, every other joint at 0°:
  base       (0, 0, 0) -> (0, 0, 0)
  shoulder   (0, 1, 0) -> (0, 1, 0)
  elbow      (0, 3, 0) -> (0, 3, 0)
  wrist      (0, 4.5, 0) -> (-1.5, 3, 0)
  fingertip  (0, 5, 0) -> (-2, 3, 0)

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node scene_graph.mjs

The straight arm puts the fingertip at (0, 5, 0), and in every pose the walk agrees with the hand-written product within 10⁻¹². The last block bends the elbow alone: the base, the shoulder and the elbow keep their origins, the wrist moves from (0, 4.5, 0) to (−1.5, 3, 0) and the fingertip from (0, 5, 0) to (−2, 3, 0). The order of the product is the whole rule: W(parent) L, never L W(parent).

Multiplying in the wrong order

Writing local × parent instead of parent × local turns each child about its own origin by the parent’s turn and then moves it by the parent’s offset as if in world space. On the arm the fingertip stays at (0, 5, 0) when the elbow bends, and a parent at (5, 0, 0) turned 90° sends a child 1 unit along its x axis to (6, 0, 0) instead of (5, 1, 0).

Checkpoint

Check: World matrices from local transforms

Question 1 of 2 Which product gives a child's world matrix?
Choose one answer.

L(child) alone, once the parent is set W(parent) × L(child) W(parent) + L(child) L(child) × W(parent)

Show the answer: Question 1 of 2

Answer: W(parent) × L(child)

glTF defines a node's global matrix as its parent's global matrix times its own local matrix.
Question 2 of 2 The arm is straight, with the wrist at (0, 4.5, 0). The elbow, at (0, 3, 0), bends 90° about z. Where is the wrist now?
Choose one answer.

(−2, 3, 0) (1.5, 3, 0) (−1.5, 3, 0) (0, 4.5, 0)

A hint

The wrist's local move of 1.5 along y goes along the elbow's turned y axis.

Show the answer: Question 2 of 2

Answer: (−1.5, 3, 0)

The program printed the wrist moving from (0, 4.5, 0) to (−1.5, 3, 0) and the fingertip to (−2, 3, 0).

Animate a jointed figure by changing local transforms only

A figure with joints is animated by its joints. Twelve dancers hold hands in a ring: the ring is one node, each dancer hangs from it at its place round the circle, and each dancer has a body, a head, and two arms with a hand at the end of each, 1 + 12 × 7 = 85 nodes. The arms leave the neck and bend 15° in towards the centre, along the line to the neighbour, and each is 3 sin 15° = 0.776 long, half the gap between two dancers on a ring of radius 3. Here is the ring the program builds:

The ring of twelve dancers, one scene graph of 85 nodes

Text description of the diagram

A ring of twelve dancers, seen from in front and a little above, so the ring on the ground appears as a dashed ellipse. Each dancer is a figure of a circle for the head and two triangles for the body, an inverted triangle from the shoulders down to the waist and an upright one from the waist down to the hips, with lines for the legs.

Every dancer stands facing the centre of the ring. Its two arms leave the neck and reach out to each side, bent a little towards the centre, and each hand meets the hand of the neighbour on that side, so the arms form a closed ring of their own at shoulder height. The dancers at the front of the ring are drawn darker and slightly larger than those at the back.

The caption under the drawing says that each hand meets its neighbour's within 10⁻¹², however far the ring has turned.

The animation changes two kinds of local transform and nothing else: the ring’s turn, and each dancer’s small bob up and down. The program runs three frames and measures, every time, the widest gap between hands that should be holding:

Twelve dancers on a turning ring JavaScript · ring/ring_dance.mjs

// Twelve dancers holding hands in a ring, as one scene graph of 85 nodes: the ring, and for each dancer a
// placement on the ring, a body, a head, and two arms with a hand at the end of each. The animation changes
// two kinds of local transform only, the ring's turn and every dancer's bob, and the hands of neighbours
// keep meeting. 4 x 4 matrices as lists of rows, acting on column vectors.

const rad = (degrees) => (degrees * Math.PI) / 180;
const mul = (a, b) => a.map((row) => [0, 1, 2, 3].map((c) => row.reduce((s, v, k) => s + v * b[k][c], 0)));
const T = (x, y, z) => [[1, 0, 0, x], [0, 1, 0, y], [0, 0, 1, z], [0, 0, 0, 1]];
const Ry = (a) => [[Math.cos(a), 0, Math.sin(a), 0], [0, 1, 0, 0], [-Math.sin(a), 0, Math.cos(a), 0], [0, 0, 0, 1]];
const origin = (m) => [m[0][3], m[1][3], m[2][3]];

const DANCERS = 12;
const RADIUS = 3;
const ARM = RADIUS * Math.sin(rad(180 / DANCERS)); // half the gap between neighbours: 0.776

// Build the tree. Each node has a name, a function of the frame that gives its local transform, and children.
function node(name, local, children = []) {
  return { name, local, children };
}
function dancer(i) {
  // Placed on the ring, turned to face the centre (its own +z points inwards, its own +x to its left).
  const place = (f) => mul(Ry(rad((360 / DANCERS) * i)), mul(T(0, 0.15 * Math.sin(rad(f.bob)), RADIUS), Ry(rad(180))));
  return node(`dancer ${i + 1}`, place, [
    node(`body ${i + 1}`, () => T(0, 0.9, 0), [
      node(`head ${i + 1}`, () => T(0, 0.75, 0)),
      // Each arm leaves the neck and bends 15° in towards the centre, along the line to the neighbour.
      node(`left arm ${i + 1}`, () => mul(T(0, 0.55, 0), Ry(rad(-180 / DANCERS))), [node(`left hand ${i + 1}`, () => T(ARM, 0, 0))]),
      node(`right arm ${i + 1}`, () => mul(T(0, 0.55, 0), Ry(rad(180 / DANCERS))), [node(`right hand ${i + 1}`, () => T(-ARM, 0, 0))]),
    ]),
  ]);
}
const ring = node('ring', (f) => Ry(rad(f.spin)), Array.from({ length: DANCERS }, (_, i) => dancer(i)));

// One pass from the root: world(child) = world(parent) × local(child).
function update(root, frame) {
  const world = new Map();
  const visit = (n, parentWorld) => {
    const w = parentWorld ? mul(parentWorld, n.local(frame)) : n.local(frame);
    world.set(n.name, w);
    for (const c of n.children) visit(c, w);
  };
  visit(root, null);
  return world;
}

const num = (v) => {
  const r = Number(v.toFixed(3));
  return Object.is(r, -0) ? '0' : String(r);
};
const show = (v) => `(${v.map(num).join(', ')})`;
const gap = (a, b) => Math.hypot(...a.map((v, i) => v - b[i]));

console.log(`${DANCERS} dancers on a ring of radius ${RADIUS}, arms ${num(ARM)} long`);
for (const frame of [{ spin: 0, bob: 0 }, { spin: 10, bob: 90 }, { spin: 20, bob: 180 }]) {
  const world = update(ring, frame);
  let widest = 0;
  for (let i = 1; i <= DANCERS; i++) {
    const neighbour = ((i + DANCERS - 2) % DANCERS) + 1; // the dancer on this one's left, one place back round the ring
    widest = Math.max(widest, gap(origin(world.get(`left hand ${i}`)), origin(world.get(`right hand ${neighbour}`))));
  }
  console.log(`ring turned ${frame.spin}°, bob phase ${frame.bob}°: ${world.size} world matrices`);
  console.log(`  dancer 1's head at ${show(origin(world.get('head 1')))}, left hand at ${show(origin(world.get('left hand 1')))}`);
  console.log(`  widest gap between hands that hold each other: ${widest < 1e-12 ? 'below 1e-12' : num(widest)}`);
}

Output

12 dancers on a ring of radius 3, arms 0.776 long
ring turned 0°, bob phase 0°: 85 world matrices
  dancer 1's head at (0, 1.65, 3), left hand at (-0.75, 1.45, 2.799)
  widest gap between hands that hold each other: below 1e-12
ring turned 10°, bob phase 90°: 85 world matrices
  dancer 1's head at (0.521, 1.8, 2.954), left hand at (-0.253, 1.6, 2.887)
  widest gap between hands that hold each other: below 1e-12
ring turned 20°, bob phase 180°: 85 world matrices
  dancer 1's head at (1.026, 1.65, 2.819), left hand at (0.253, 1.45, 2.887)
  widest gap between hands that hold each other: below 1e-12

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node ring_dance.mjs

Each frame recomputes 85 world matrices from two numbers, the ring’s turn and the bob, and in every frame the hands of neighbours meet within 10⁻¹². Dancer 1’s head moves from (0, 1.65, 3) to (0.521, 1.8, 2.954) and (1.026, 1.65, 2.819) as the ring turns 10° and 20° and the dancers bob, yet no hand was ever placed by hand. The hierarchy keeps the joint constraint with no extra work, because each hand’s position is computed from the same ring and the same geometry as its neighbour’s.

Dancers in the manner of Warli painting

The dancers are drawn from a circle and two triangles, after Warli painting from Maharashtra, which, as the Ministry of Tourism’s Incredible India describes it, builds scenes of Warli life from lines, dots, triangles, circles and squares. Warli painting is a Geographical Indication, the intellectual legacy of the Warli community; the figure here is an original drawing in that spirit, made to exercise a hierarchy, and copies no painting.

Checkpoint

Check: Animating joints, not parts

Question 1 of 2 The ring has 12 dancers, each a placement node, a body, a head, two arms and two hands. How many nodes does the scene graph have?
Type a number.
Your answer nodes

Show the answer: Question 1 of 2

Answer: 85 nodes

One ring plus 12 dancers of 7 nodes each, 1 + 12 × 7 = 85; the program updated 85 world matrices a frame.
Question 2 of 2 As the ring turns, what keeps every dancer's hand in its neighbour's?
Choose one answer.

The program moves each hand to its neighbour's every frame A physics solver joins the hands Rounding keeps them close Each hand is placed by the same ring and the same arm geometry as its neighbour's, so the turn moves both alike

Show the answer: Question 2 of 2

Answer: Each hand is placed by the same ring and the same arm geometry as its neighbour's, so the turn moves both alike

A constraint built into local transforms, here arms of 0.776 bent 15° towards each neighbour, holds in every pose the parent nodes produce.

Dirty flags recompute only what changed

Recomputing all 85 world matrices every frame is simple, and it is wasted work whenever most of the scene is still. A dirty flag: A mark that a cached value is out of date. In a scene graph, changing a local transform marks the node and every node below it, and only marked world matrices are recomputed. fixes that: each node caches its world matrix and a flag that says it is out of date. Changing a node’s local transform marks that node and everything below it dirty, and reading a world matrix recomputes it only when its node is dirty. Here is the dance as a tree, with the two nodes a move of one arm marks:

The 85 nodes of the dance, with dancer 5 opened up

Text description of the diagram

A tree drawn from the top. The ring is the root. Below it are three boxes: dancers 1 to 4, dancer 5, and dancers 6 to 12; together they stand for the 12 dancer nodes.

Dancer 5 is opened up. Below it is its body, and below the body are its head, its left arm and its right arm. Below the left arm is the left hand, and below the right arm the right hand. With the dancer node itself, that is 7 nodes per dancer, and 1 + 12 × 7 = 85 in all.

The left arm and the left hand are drawn with dashed blue outlines: they are the two nodes marked dirty when the left arm's local transform changes, so a frame after that change recomputes 2 of the 85 world matrices.

The program gives every node a cache and a flag and counts, frame by frame, how many world matrices a renderer that reads all 85 has to recompute:

Cached world matrices with dirty flags JavaScript · dirty/dirty_flags.mjs

// The ring of dancers again, now with a cached world matrix and a dirty flag on every node. Changing a local
// transform marks that node and everything below it dirty; reading a world matrix recomputes it only when it
// is dirty. A renderer reads every world matrix once a frame; the program counts how many it had to recompute.

const rad = (degrees) => (degrees * Math.PI) / 180;
const mul = (a, b) => a.map((row) => [0, 1, 2, 3].map((c) => row.reduce((s, v, k) => s + v * b[k][c], 0)));
const T = (x, y, z) => [[1, 0, 0, x], [0, 1, 0, y], [0, 0, 1, z], [0, 0, 0, 1]];
const Ry = (a) => [[Math.cos(a), 0, Math.sin(a), 0], [0, 1, 0, 0], [-Math.sin(a), 0, Math.cos(a), 0], [0, 0, 0, 1]];

const nodes = new Map();
let recomputed = 0;
function add(name, local, parent = null) {
  const n = { name, local, parent, children: [], world: null, dirty: true };
  if (parent) parent.children.push(n);
  nodes.set(name, n);
  return n;
}
function markDirty(n) {
  if (n.dirty) return; // already dirty, and so is everything below it
  n.dirty = true;
  for (const c of n.children) markDirty(c);
}
function setLocal(name, local) {
  const n = nodes.get(name);
  n.local = local;
  markDirty(n);
}
function worldOf(n) {
  if (n.dirty) {
    n.world = n.parent ? mul(worldOf(n.parent), n.local) : n.local;
    n.dirty = false;
    recomputed++;
  }
  return n.world;
}
function frame() {
  recomputed = 0;
  for (const n of nodes.values()) worldOf(n);
  return recomputed;
}

const ARM = 3 * Math.sin(rad(15));
const place = (i, bob) => mul(Ry(rad(30 * i)), mul(T(0, bob, 3), Ry(rad(180))));
const ring = add('ring', Ry(0));
for (let i = 1; i <= 12; i++) {
  const dancer = add(`dancer ${i}`, place(i - 1, 0), ring);
  const body = add(`body ${i}`, T(0, 0.9, 0), dancer);
  add(`head ${i}`, T(0, 0.75, 0), body);
  add(`left hand ${i}`, T(ARM, 0, 0), add(`left arm ${i}`, mul(T(0, 0.55, 0), Ry(rad(-15))), body));
  add(`right hand ${i}`, T(-ARM, 0, 0), add(`right arm ${i}`, mul(T(0, 0.55, 0), Ry(rad(15))), body));
}

const report = (what, count) => console.log(`${what.padEnd(40)} ${String(count).padStart(3)} of ${nodes.size}`);
console.log(`${'this frame'.padEnd(40)} world matrices recomputed`);
report('the first frame', frame());
report('nothing changed', frame());
setLocal('left arm 5', mul(T(0, 0.55, 0), Ry(rad(10))));
report("dancer 5's left arm moves", frame());
for (let i = 1; i <= 12; i++) setLocal(`dancer ${i}`, place(i - 1, 0.15));
report('every dancer bobs', frame());
setLocal('ring', Ry(rad(10)));
report('the ring turns 10°', frame());

// The cached matrices must equal a recomputation of every node from the root.
const fresh = (n) => (n.parent ? mul(fresh(n.parent), n.local) : n.local);
let worst = 0;
for (const n of nodes.values()) {
  const f = fresh(n);
  n.world.forEach((row, r) => row.forEach((v, c) => (worst = Math.max(worst, Math.abs(v - f[r][c])))));
}
console.log('');
console.log(`cached world matrices against a full recomputation: largest difference ${worst === 0 ? '0' : worst.toExponential(1)}`);

Output

this frame                               world matrices recomputed
the first frame                           85 of 85
nothing changed                            0 of 85
dancer 5's left arm moves                  2 of 85
every dancer bobs                         84 of 85
the ring turns 10°                        85 of 85

cached world matrices against a full recomputation: largest difference 0

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node dirty_flags.mjs

The first frame computes all 85, a frame in which nothing changed computes none, dancer 5’s arm costs 2, the arm and its hand, and every dancer bobbing costs 84, all but the ring. Turning the ring costs all 85, because everything hangs from it. The cached matrices match a recomputation from the root exactly. three.js has the same flag: in updateMatrixWorld, a node whose matrixWorldNeedsUpdate is set recomputes its world matrix from its parent’s, and every child below it is then recomputed too. With matrixAutoUpdate on, the default, every object sets that flag each frame, so the saving starts once objects that stay still have it turned off.

Key idea

A world matrix depends on every local transform above it, so a change marks one node and its whole subtree dirty, and nothing else needs recomputing.

Checkpoint

Check: Dirty flags and cached world matrices

Question 1 of 2 With dirty flags, every dancer bobs in one frame and nothing else changes. How many of the 85 world matrices are recomputed?
Type a number.
Your answer

Show the answer: Question 1 of 2

Answer: 84

Each dancer's placement node and its 6 nodes below it are dirty, 12 × 7 = 84; only the ring keeps its cached matrix.
Question 2 of 2 A node's local transform changes. Which world matrices must be recomputed?
Choose one answer.

That node's and those of every node below it Every node's in the scene Its parent's Only that node's

Show the answer: Question 2 of 2

Answer: That node's and those of every node below it

three.js's updateMatrixWorld reaches the same result in one pass: once a node's world matrix is recomputed, it forces every node below it to be recomputed too.

Local and world space: picking and attaching

Two everyday jobs move between the spaces. Picking turns a world point into a node’s own coordinates: a ray hits the world point (3, 2.6, −1.5) near the arm’s hand, and the hand’s code wants it relative to the hand. That is the inverse of the hand’s world matrix applied to the point. Attaching moves a node under another parent without moving it in the world: the arm grabs a cup from the table. The cup must keep its world matrix, so its new local transform has to satisfy W(hand) L = W(cup), which gives

L_{\text{cup}} = W_{\text{hand}}^{-1}\, W_{\text{cup}}

computed before the cup changes parent. Step through the grab, the carry and the release:

Interactive · stage by stage Grabbing a cup without making it jump Step down the flow. Each stage changes which node the cup hangs from; its world position only changes when the arm moves.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

On the table. The cup is a child of the world at (2.9, 2.3, −1.6), just below the fingertip, which the arm's pose puts at (2.845, 2.532, −1.643).
Read before moving. Before the cup changes parent, read the world matrices of the cup and of its new parent, the hand. Afterwards the cup's world matrix would already depend on the hand.
Solve for the local transform. The cup must satisfy world(hand) × local = its world matrix as it is now, so local = inverse(world(hand)) × world(cup): the position (0.232, 0.026, 0.064) in the hand's coordinates.
Re-parent. Hung under the hand with that local transform, the cup's world position is still (2.9, 2.3, −1.6). Keeping its old local numbers instead would have thrown it to (4.037, −0.368, −4.178).
Carried. The arm turns and lifts. Nothing about the cup changes, yet its world position moves to (−0.799, 4.533, −1.513), still 0.242 from the fingertip.
Let go. Releasing is the same move the other way, onto the world, whose world matrix is the identity, so the local transform becomes the cup's world matrix and it stays where it was dropped.

The program does both jobs on the arm, with the inverse of a rigid transform from the matrices lesson:

Picking a point and grabbing a cup JavaScript · attach/attach.mjs

// Local and world space on the robot arm: where a world point lies in the hand's own coordinates, and moving
// a cup from the table into the hand without it jumping. 4 x 4 matrices as lists of rows, column vectors.

const rad = (degrees) => (degrees * Math.PI) / 180;
const mul = (a, b) => a.map((row) => [0, 1, 2, 3].map((c) => row.reduce((s, v, k) => s + v * b[k][c], 0)));
const T = (x, y, z) => [[1, 0, 0, x], [0, 1, 0, y], [0, 0, 1, z], [0, 0, 0, 1]];
const Ry = (a) => [[Math.cos(a), 0, Math.sin(a), 0], [0, 1, 0, 0], [-Math.sin(a), 0, Math.cos(a), 0], [0, 0, 0, 1]];
const Rz = (a) => [[Math.cos(a), -Math.sin(a), 0, 0], [Math.sin(a), Math.cos(a), 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]];
const point = (m, [x, y, z]) => [0, 1, 2].map((r) => m[r][0] * x + m[r][1] * y + m[r][2] * z + m[r][3]);
// The inverse of a rigid transform [R t; 0 1] is [Rᵀ, −Rᵀ t; 0 1].
function invertRigid(m) {
  const rt = [0, 1, 2].map((r) => [0, 1, 2].map((c) => m[c][r]));
  const t = [m[0][3], m[1][3], m[2][3]];
  const back = rt.map((row) => -(row[0] * t[0] + row[1] * t[1] + row[2] * t[2]));
  return [[...rt[0], back[0]], [...rt[1], back[1]], [...rt[2], back[2]], [0, 0, 0, 1]];
}
// The arm's hand, from the base to the wrist and on to the fingertip, for one pose.
const hand = (p) => mul(Ry(rad(p.base)), mul(T(0, 1, 0), mul(Rz(rad(p.shoulder)), mul(T(0, 2, 0), mul(Rz(rad(p.elbow)), mul(T(0, 1.5, 0), mul(Rz(rad(p.wrist)), T(0, 0.5, 0))))))));

const num = (v) => {
  const r = Number(v.toFixed(3));
  return Object.is(r, -0) ? '0' : String(r);
};
const show = (v) => `(${v.map(num).join(', ')})`;

const reach = { base: 30, shoulder: -40, elbow: -50, wrist: 0 };
const handWorld = hand(reach);
console.log(`the hand reaches down to ${show(point(handWorld, [0, 0, 0]))}`);

// A picking ray hits the world point (3, 2.6, -1.5). Where is that in the hand's own coordinates?
const hit = [3, 2.6, -1.5];
const inHand = point(invertRigid(handWorld), hit);
console.log(`the world point ${show(hit)} is ${show(inHand)} in the hand's coordinates, and back: ${show(point(handWorld, inHand))}`);

// The cup stands on the table at (2.9, 2.3, -1.6), just below the fingertip, a child of the world. Grab it,
// keeping it where it is: its new local transform is inverse(world of the hand) × its old world transform.
const cupWorld = T(2.9, 2.3, -1.6);
const cupInHand = mul(invertRigid(handWorld), cupWorld);
console.log('');
console.log(`grabbed: the cup's local position in the hand is ${show(point(cupInHand, [0, 0, 0]))}`);
console.log(`its world position is still ${show(point(mul(handWorld, cupInHand), [0, 0, 0]))}`);
// Re-parenting without that correction keeps the old local numbers, which now mean "relative to the hand".
console.log(`kept its old local numbers instead, it would jump to ${show(point(mul(handWorld, cupWorld), [0, 0, 0]))}`);

// The arm lifts; the cup rides along, because only the arm's local transforms changed.
const lift = { base: 120, shoulder: -10, elbow: -30, wrist: 20 };
const lifted = mul(hand(lift), cupInHand);
console.log('');
console.log(`the arm lifts and turns: the hand is at ${show(point(hand(lift), [0, 0, 0]))}, the cup at ${show(point(lifted, [0, 0, 0]))}`);
console.log(`the cup is still ${num(Math.hypot(...point(cupInHand, [0, 0, 0])))} from the fingertip, as when it was grabbed`);
// Let go: back to the world, keeping where it is now.
console.log(`released, it becomes a child of the world at ${show(point(lifted, [0, 0, 0]))}`);

Output

the hand reaches down to (2.845, 2.532, -1.643)
the world point (3, 2.6, -1.5) is (-0.068, 0.063, 0.201) in the hand's coordinates, and back: (3, 2.6, -1.5)

grabbed: the cup's local position in the hand is (0.232, 0.026, 0.064)
its world position is still (2.9, 2.3, -1.6)
kept its old local numbers instead, it would jump to (4.037, -0.368, -4.178)

the arm lifts and turns: the hand is at (-0.741, 4.589, -1.284), the cup at (-0.799, 4.533, -1.513)
the cup is still 0.242 from the fingertip, as when it was grabbed
released, it becomes a child of the world at (-0.799, 4.533, -1.513)

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node attach.mjs

The picked point is (−0.068, 0.063, 0.201) in the hand’s coordinates, close to the hand’s own origin at the fingertip, and it maps back to (3, 2.6, −1.5). Grabbed with the corrected local transform, the cup stays at (2.9, 2.3, −1.6); hung under the hand with its old local numbers it would have jumped to (4.037, −0.368, −4.178), below the floor. When the arm lifts and turns, the cup rides to (−0.799, 4.533, −1.513), still 0.242 from the fingertip, and letting it go is the same move onto the world. three.js offers both: worldToLocal and localToWorld convert points, and attach adds a child “while maintaining the object’s world transform”, where add keeps its local one.

Checkpoint

Check: Picking and attaching between spaces

Question 1 of 2 A cup with world matrix W(cup) is moved under the hand. Which local transform keeps it where it is?
Choose one answer.

W(hand)⁻¹ W(cup), computed before it changes parent Its old local transform W(hand) W(cup) W(cup) W(hand)⁻¹

Show the answer: Question 1 of 2

Answer: W(hand)⁻¹ W(cup), computed before it changes parent

three.js's attach() keeps the world transform in exactly this way, where add() keeps the local one.
Question 2 of 2 A ray hits the world point p. How do you get p in the hand's own coordinates?
Choose one answer.

Apply the hand's local matrix to p Subtract the hand's world position from p Apply the hand's world matrix to p Apply the inverse of the hand's world matrix to p

Show the answer: Question 2 of 2

Answer: Apply the inverse of the hand's world matrix to p

three.js calls this worldToLocal; localToWorld goes the other way with the world matrix itself.

A non-uniform scale on a parent shears its turned children

An artist stretches a table to twice its length with S(2, 1, 1), and a lamp that sits on it as its child is turned 45° about the vertical. The lamp’s world matrix is S(2, 1, 1) Ry(45°), and the stretch now acts along the table’s axes, which run diagonally across the turned lamp. Look at the lamp’s square base from above under three parents:

The lamp's square base under no parent scale, S(2, 2, 2) and S(2, 1, 1)

Text description of the diagram

Three panels, one above the other, each with the table's own x and z axes drawn as grey lines. The lamp is a child of the table and is turned 45° about the vertical, so its square base appears as a diamond.

With no scaled parent, the base is a square, a diamond with right-angled corners. Under a table scaled uniformly by S(2, 2, 2) it is the same diamond twice the size, still with right angles. Under a table stretched along x by S(2, 1, 1) it becomes a rhombus, twice as wide as it is deep, with corners of 53.13° and 126.87°: the stretch along the table's x axis has sheared the turned lamp.

Only the stretched table distorts it, and the program measures how:

A turned lamp under a stretched table JavaScript · shear/nonuniform.mjs

// A table stretched to twice its length by S(2, 1, 1), with a lamp parented to it and turned 45° about the
// vertical. The lamp's world matrix then holds a shear that no translation, rotation and scale can express.
// 3 x 3 parts only, as lists of rows; the columns are where the lamp's own axes x, y, z go.

const rad = (degrees) => (degrees * Math.PI) / 180;
const deg = (radians) => (radians * 180) / Math.PI;
const mul = (a, b) => a.map((row) => [0, 1, 2].map((c) => row[0] * b[0][c] + row[1] * b[1][c] + row[2] * b[2][c]));
const S = (x, y, z) => [[x, 0, 0], [0, y, 0], [0, 0, z]];
const Ry = (a) => [[Math.cos(a), 0, Math.sin(a)], [0, 1, 0], [-Math.sin(a), 0, Math.cos(a)]];
const column = (m, c) => [m[0][c], m[1][c], m[2][c]];
const dot = (a, b) => a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
const length = (v) => Math.sqrt(dot(v, v));
const angle = (a, b) => deg(Math.acos(dot(a, b) / (length(a) * length(b))));
const num = (v) => {
  const r = Number(v.toFixed(3));
  return Object.is(r, -0) ? '0' : String(r);
};
const show = (v) => `(${v.map(num).join(', ')})`;

function report(title, m) {
  const [x, , z] = [column(m, 0), column(m, 1), column(m, 2)];
  console.log(title);
  console.log(`  the lamp's x axis goes to ${show(x)}, its z axis to ${show(z)}`);
  console.log(`  lengths ${num(length(x))} and ${num(length(z))}, ${num(angle(x, z))}° apart`);
  // Try to split it as a rotation times a scale: scales from the column lengths, rotation from the columns.
  const scales = [0, 1, 2].map((c) => length(column(m, c)));
  const R = m.map((row) => row.map((v, c) => v / scales[c]));
  const off = Math.abs(dot(column(R, 0), column(R, 2)));
  console.log(`  rotation × scale ${off < 1e-12 ? 'fits exactly' : `cannot fit: the axes it would rotate are ${num(off)} from perpendicular (dot product)`}`);
}

const lamp = Ry(rad(45));
report('table S(2, 1, 1), lamp turned 45° as its child:', mul(S(2, 1, 1), lamp));
report('table S(2, 2, 2), the same lamp:', mul(S(2, 2, 2), lamp));
report('table scale moved to a child mesh node, lamp under the unscaled table:', lamp);

// A square tile on the lamp's base, corners in the lamp's x-z plane: what shape does it become?
const tile = [[1, 0, 1], [1, 0, -1], [-1, 0, -1], [-1, 0, 1]];
const M = mul(S(2, 1, 1), lamp);
const corners = tile.map((p) => M.map((row) => dot(row, p)));
console.log('');
console.log(`a square tile on the lamp's base becomes ${corners.map(show).join(', ')}`);
const edge = (a, b) => b.map((v, i) => v - a[i]);
console.log(`its corners are ${num(angle(edge(corners[0], corners[1]), edge(corners[0], corners[3])))}° and ${num(angle(edge(corners[1], corners[0]), edge(corners[1], corners[2])))}°: a rhombus`);

Output

table S(2, 1, 1), lamp turned 45° as its child:
  the lamp's x axis goes to (1.414, 0, -0.707), its z axis to (1.414, 0, 0.707)
  lengths 1.581 and 1.581, 53.13° apart
  rotation × scale cannot fit: the axes it would rotate are 0.6 from perpendicular (dot product)
table S(2, 2, 2), the same lamp:
  the lamp's x axis goes to (1.414, 0, -1.414), its z axis to (1.414, 0, 1.414)
  lengths 2 and 2, 90° apart
  rotation × scale fits exactly
table scale moved to a child mesh node, lamp under the unscaled table:
  the lamp's x axis goes to (0.707, 0, -0.707), its z axis to (0.707, 0, 0.707)
  lengths 1 and 1, 90° apart
  rotation × scale fits exactly

a square tile on the lamp's base becomes (2.828, 0, 0), (0, 0, -1.414), (-2.828, 0, 0), (0, 0, 1.414)
its corners are 53.13° and 126.87°: a rhombus

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node nonuniform.mjs

Under S(2, 1, 1) the lamp’s own x and z axes come out 1.581 long and 53.13° apart instead of 90°: the base tile becomes a rhombus with corners of 53.13° and 126.87°. That is a shear. A rotation times a scale along the lamp’s own axes, R S, which is the 3 × 3 part of every translation, rotation and scale, keeps those axes perpendicular, so no such product can produce it: the program’s attempt to split the matrix that way finds the axes 0.6 from perpendicular as a dot product. A uniform S(2, 2, 2) keeps everything square. This is why glTF’s specification notes that its transformation matrices cannot skew or shear, why three.js says attach and lookAt do not support non-uniformly scaled parents, and why its Matrix4.decompose warns that a world matrix under such a parent may not be decomposable into position, rotation and scale.

Keep stretches on the leaves

Put a non-uniform scale on a node that has no children, such as a separate mesh node under the table, and hang the lamp from the unscaled table node. The program’s third case does exactly that, and the lamp’s axes stay 1 long and 90° apart.

Checkpoint

Check: Shear from a non-uniformly scaled parent

Question 1 of 2 Under the table S(2, 1, 1), how many degrees apart are the turned lamp's own x and z axes?
Type a number.
Your answer degrees

Show the answer: Question 1 of 2

Answer: 53.13 degrees (anything from 53.12 to 53.14 counts)

The axes come out as (1.414, 0, −0.707) and (1.414, 0, 0.707), each 1.581 long; their angle is 53.13°, not 90°.
Question 2 of 2 The table must look twice as long, and the lamp on it must keep its shape. What do you change?
Choose one answer.

Use S(2, 2, 2) on the table instead Put the table's S(2, 1, 1) on a child mesh node and hang the lamp from the unscaled table node Scale the lamp by S(0.5, 1, 1) to cancel the table's stretch Nothing; the shear is a rounding error

Show the answer: Question 2 of 2

Answer: Put the table's S(2, 1, 1) on a child mesh node and hang the lamp from the unscaled table node

Non-uniform scales belong on leaves. glTF matrices cannot shear, and three.js's attach and lookAt do not support non-uniformly scaled parents.

Practise: world matrices, then attaching

Two exercises build a small scene graph, and their sample tests run here on the page. The first computes world matrices with dirty flags and is held to the lesson’s arm and to counts of the products it computes; the second picks points and attaches nodes without moving them, on 200 seeded moves:

Code lab · 2 steps

Build a scene graph

Compute world matrices down a tree with dirty flags, then convert points between spaces and re-parent nodes without moving them.

World matrices with dirty flags To do
Pick and attach without a jump To do

Exercise · Medium · JavaScript

World matrices with dirty flags

graph.mjs holds a small scene graph. Matrices are 16 numbers in column-major order and act on column vectors; the helpers identity, multiply, translation and rotationZ are given and correct, and so are createNode, addChild and setLocal. Write:

markDirty(node): mark the node dirty, and every node below it, because their world matrices all depend on it.
worldMatrix(node): the node's world matrix, world(parent) × local (just the local matrix for a root). Keep it in node.world and recompute it only when the node is dirty; count every call of multiply you make in stats.multiplies.

The starter multiplies the two matrices the wrong way round, and its markDirty marks only the node itself, so a child keeps an old world matrix after its parent moves. The sample tests use the lesson's robot arm, whose fingertip must move from (0, 5, 0) to (−2, 3, 0) when the elbow bends 90°, count the multiplications a cached read and a change of the wrist cost, and compare a chain of 20 seeded nodes with its product written out from the root.

Starter code · graph.mjs

/**
 * A scene graph with cached world matrices. Matrices are column-major arrays of 16 (entry (r, c) at c * 4 + r).
 * The helpers and createNode, addChild and setLocal are correct. markDirty must mark a node and all its descendants;
 * worldMatrix must return world(parent) × local, recomputed only when dirty, counting multiplies in stats. This first
 * version multiplies in the wrong order and marks only the node itself.
 */
export const stats = { multiplies: 0 };

export const identity = () => [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1];
export function multiply(a, b) {
  const m = new Array(16).fill(0);
  for (let r = 0; r < 4; r++) for (let c = 0; c < 4; c++) for (let k = 0; k < 4; k++) m[c * 4 + r] += a[k * 4 + r] * b[c * 4 + k];
  return m;
}
export const translation = (x, y, z) => [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, x, y, z, 1];
export const rotationZ = (a) => [Math.cos(a), Math.sin(a), 0, 0, -Math.sin(a), Math.cos(a), 0, 0, 0, 0, 1, 0, 0, 0, 0, 1];

export function createNode(local = identity()) {
  return { local, parent: null, children: [], world: null, dirty: true };
}
export function addChild(parent, child) {
  child.parent = parent;
  parent.children.push(child);
  markDirty(child);
}
export function setLocal(node, local) {
  node.local = local;
  markDirty(node);
}

export function markDirty(node) {
  node.dirty = true;
}

export function worldMatrix(node) {
  if (node.dirty) {
    if (node.parent) {
      node.world = multiply(node.local, worldMatrix(node.parent));
      stats.multiplies++;
    } else {
      node.world = node.local.slice();
    }
    node.dirty = false;
  }
  return node.world;
}

The sample tests · graph.test.mjs

import { test, assert } from 'mysmartcopilot:test';
import { addChild, createNode, identity, multiply, rotationZ, setLocal, stats, translation, worldMatrix } from './graph.mjs';

const rad = (d) => (d * Math.PI) / 180;
const position = (m) => [m[12], m[13], m[14]];
function near(got, want, label, eps = 1e-9) {
  const ok = got.length === want.length && got.every((v, i) => Math.abs(v - want[i]) < eps);
  assert.ok(ok, `${label}: got (${got.map((v) => Number(v.toFixed(4)) + 0).join(', ')}), expected (${want.map((v) => Number(v.toFixed(4)) + 0).join(', ')})`);
}
// The lesson's arm in the x-y plane: base, shoulder 1 up, elbow 2 further, wrist 1.5 further, fingertip 0.5 further.
function arm() {
  const base = createNode();
  const shoulder = createNode(translation(0, 1, 0));
  const elbow = createNode(translation(0, 2, 0));
  const wrist = createNode(translation(0, 1.5, 0));
  const tip = createNode(translation(0, 0.5, 0));
  addChild(base, shoulder);
  addChild(shoulder, elbow);
  addChild(elbow, wrist);
  addChild(wrist, tip);
  return { base, shoulder, elbow, wrist, tip };
}

test('the straight arm puts the fingertip at (0, 5, 0)', () => {
  const a = arm();
  near(position(worldMatrix(a.tip)), [0, 5, 0], 'the fingertip');
  near(position(worldMatrix(a.wrist)), [0, 4.5, 0], 'the wrist');
});

test('bending the elbow 90° moves the wrist and the fingertip', () => {
  const a = arm();
  worldMatrix(a.tip); // the cached matrices must not survive the change
  setLocal(a.elbow, multiply(translation(0, 2, 0), rotationZ(rad(90))));
  near(position(worldMatrix(a.tip)), [-2, 3, 0], 'the fingertip after the bend');
  near(position(worldMatrix(a.wrist)), [-1.5, 3, 0], 'the wrist after the bend');
  near(position(worldMatrix(a.shoulder)), [0, 1, 0], 'the shoulder does not move');
});

test('a parent turns its child about the parent, not the other way round', () => {
  const parent = createNode(multiply(translation(5, 0, 0), rotationZ(rad(90))));
  const child = createNode(translation(1, 0, 0));
  addChild(parent, child);
  near(position(worldMatrix(child)), [5, 1, 0], 'world(parent) × local(child)');
});

test('cached reads cost nothing; a change costs one product per node below it', () => {
  const a = arm();
  stats.multiplies = 0;
  worldMatrix(a.tip);
  assert.equal(stats.multiplies, 4, 'the first read of the fingertip computes 4 products, one per node below the base');
  stats.multiplies = 0;
  worldMatrix(a.tip);
  worldMatrix(a.wrist);
  assert.equal(stats.multiplies, 0, 'reading again computes nothing');
  setLocal(a.wrist, multiply(translation(0, 1.5, 0), rotationZ(rad(30))));
  worldMatrix(a.tip);
  assert.equal(stats.multiplies, 2, 'a new wrist recomputes the wrist and the fingertip only');
});

test('a chain of 20 seeded nodes matches its product written out', () => {
  let seed = 6; // mulberry32
  const random = () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
  const locals = Array.from({ length: 20 }, () => multiply(translation(random() * 2 - 1, random() * 2, 0), rotationZ((random() * 2 - 1) * Math.PI)));
  const nodes = locals.map((m) => createNode(m));
  for (let i = 1; i < nodes.length; i++) addChild(nodes[i - 1], nodes[i]);
  let product = identity();
  for (let i = 0; i < nodes.length; i++) {
    product = multiply(product, locals[i]);
    near(worldMatrix(nodes[i]), product, `node ${i + 1}`);
  }
  setLocal(nodes[3], multiply(locals[3], rotationZ(0.5)));
  const changed = locals.map((m, i) => (i === 3 ? multiply(m, rotationZ(0.5)) : m)).reduce((p, m) => multiply(p, m), identity());
  near(worldMatrix(nodes[19]), changed, 'the last node after node 4 changes');
});

A hint

In worldMatrix, compute the parent's world matrix first, through worldMatrix(node.parent), and put it on the left: multiply(parentWorld, node.local). In markDirty, return at once when the node is already dirty (everything below it is dirty too), otherwise set the flag and call markDirty on every child.

The sample tests run on this device, in your browser (QuickJS): nothing is sent to mysmartcopilot.com. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Exercise · Medium · JavaScript

Pick and attach without a jump

attach.mjs holds a scene graph whose nodes have a parent, children and a local matrix (16 numbers, column-major, acting on column vectors). The helpers multiply, invertAffine, translation, rotationY and scaling, createNode, addChild and worldMatrix are given and correct. Write:

localToWorld(node, point): a point [x, y, z] given in the node's own coordinates, in world coordinates.
worldToLocal(node, point): the reverse, with the inverse of the node's world matrix.
attach(node, newParent): move node under newParent and change its local matrix so that its world matrix stays exactly what it was: the new local matrix is inverse(world(newParent)) × world(node), computed before the move.

The starter's worldToLocal multiplies by the world matrix instead of its inverse, and its attach keeps the old local matrix, so the attached object jumps. The sample tests pick a point on a turned and scaled hand, grab a cup and let it go again, and attach 200 seeded nodes in hierarchies of turns, moves and uniform scales without one of them moving.

Starter code · attach.mjs

/**
 * A scene graph without caching: worldMatrix walks up to the root every time. Matrices are column-major arrays of 16.
 * The helpers, createNode, addChild and worldMatrix are correct. Write localToWorld, worldToLocal and attach (keep
 * the world matrix while re-parenting). This first version's worldToLocal uses the world matrix itself, and its attach
 * keeps the old local matrix, so the node jumps.
 */
export function multiply(a, b) {
  const m = new Array(16).fill(0);
  for (let r = 0; r < 4; r++) for (let c = 0; c < 4; c++) for (let k = 0; k < 4; k++) m[c * 4 + r] += a[k * 4 + r] * b[c * 4 + k];
  return m;
}
// The inverse of an affine matrix: the inverse of its 3 × 3 part, and −A⁻¹ t as its translation.
export function invertAffine(m) {
  const a = (r, c) => m[c * 4 + r];
  const det = a(0, 0) * (a(1, 1) * a(2, 2) - a(1, 2) * a(2, 1)) - a(0, 1) * (a(1, 0) * a(2, 2) - a(1, 2) * a(2, 0)) + a(0, 2) * (a(1, 0) * a(2, 1) - a(1, 1) * a(2, 0));
  const inv = [
    [a(1, 1) * a(2, 2) - a(1, 2) * a(2, 1), a(0, 2) * a(2, 1) - a(0, 1) * a(2, 2), a(0, 1) * a(1, 2) - a(0, 2) * a(1, 1)],
    [a(1, 2) * a(2, 0) - a(1, 0) * a(2, 2), a(0, 0) * a(2, 2) - a(0, 2) * a(2, 0), a(0, 2) * a(1, 0) - a(0, 0) * a(1, 2)],
    [a(1, 0) * a(2, 1) - a(1, 1) * a(2, 0), a(0, 1) * a(2, 0) - a(0, 0) * a(2, 1), a(0, 0) * a(1, 1) - a(0, 1) * a(1, 0)],
  ].map((row) => row.map((v) => v / det));
  const t = [a(0, 3), a(1, 3), a(2, 3)];
  const out = new Array(16).fill(0);
  for (let r = 0; r < 3; r++) {
    for (let c = 0; c < 3; c++) out[c * 4 + r] = inv[r][c];
    out[12 + r] = -(inv[r][0] * t[0] + inv[r][1] * t[1] + inv[r][2] * t[2]);
  }
  out[15] = 1;
  return out;
}
export const translation = (x, y, z) => [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, x, y, z, 1];
export const rotationY = (a) => [Math.cos(a), 0, -Math.sin(a), 0, 0, 1, 0, 0, Math.sin(a), 0, Math.cos(a), 0, 0, 0, 0, 1];
export const scaling = (s) => [s, 0, 0, 0, 0, s, 0, 0, 0, 0, s, 0, 0, 0, 0, 1];
const point = (m, [x, y, z]) => [0, 1, 2].map((r) => m[r] * x + m[4 + r] * y + m[8 + r] * z + m[12 + r]);

export function createNode(local) {
  return { local, parent: null, children: [] };
}
export function addChild(parent, child) {
  child.parent = parent;
  parent.children.push(child);
}
export function worldMatrix(node) {
  return node.parent ? multiply(worldMatrix(node.parent), node.local) : node.local;
}

export function localToWorld(node, p) {
  return point(worldMatrix(node), p);
}

export function worldToLocal(node, p) {
  return point(worldMatrix(node), p);
}

export function attach(node, newParent) {
  if (node.parent) node.parent.children = node.parent.children.filter((c) => c !== node);
  addChild(newParent, node);
}

The sample tests · attach.test.mjs

import { test, assert } from 'mysmartcopilot:test';
import { addChild, attach, createNode, localToWorld, multiply, rotationY, scaling, translation, worldMatrix, worldToLocal } from './attach.mjs';

const rad = (d) => (d * Math.PI) / 180;
function near(got, want, label, eps = 1e-9) {
  const ok = got.length === want.length && got.every((v, i) => Math.abs(v - want[i]) < eps);
  assert.ok(ok, `${label}: got (${got.map((v) => Number(v.toFixed(4)) + 0).join(', ')}), expected (${want.map((v) => Number(v.toFixed(4)) + 0).join(', ')})`);
}
// A world with an arm whose hand is moved to (1, 2, 0), turned 90° about y and scaled by 2.
function scene() {
  const world = createNode(translation(0, 0, 0));
  const arm = createNode(translation(1, 0, 0));
  const hand = createNode(multiply(translation(0, 2, 0), multiply(rotationY(rad(90)), scaling(2))));
  addChild(world, arm);
  addChild(arm, hand);
  return { world, arm, hand };
}

test('picking: a world point in the hand’s own coordinates, and back', () => {
  const { hand } = scene();
  near(localToWorld(hand, [1, 0, 0]), [1, 2, -2], "the hand's x axis, 2 long, points along world −z");
  near(worldToLocal(hand, [1, 2, -2]), [1, 0, 0], 'and back');
  near(worldToLocal(hand, [3, 2, 0]), [0, 0, 1], 'a point 2 along world x is 1 along the hand’s z');
  near(localToWorld(hand, worldToLocal(hand, [0.3, -4, 7])), [0.3, -4, 7], 'a round trip');
});

test('grabbing a cup keeps it where it is, and it then follows the hand', () => {
  const { world, arm, hand } = scene();
  const cup = createNode(translation(3, 2, 1));
  addChild(world, cup);
  attach(cup, hand);
  assert.ok(cup.parent === hand && hand.children.includes(cup) && !world.children.includes(cup), 'the cup must move under the hand');
  near(localToWorld(cup, [0, 0, 0]), [3, 2, 1], 'the cup did not move when grabbed');
  near(cup.local.slice(12, 15), [-0.5, 0, 1], "its new local position, in the hand's scaled, turned coordinates");
  arm.local = translation(5, 0, 0);
  near(localToWorld(cup, [0, 0, 0]), [7, 2, 1], 'the arm moves 4 along x, and the cup with it');
  attach(cup, world);
  near(localToWorld(cup, [0, 0, 0]), [7, 2, 1], 'let go, the cup stays where it was dropped');
  near(cup.local.slice(12, 15), [7, 2, 1], 'under the world, its local position is its world position');
});

test('200 seeded nodes keep their world matrices when attached elsewhere', () => {
  let seed = 10; // mulberry32
  const random = () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
  // A turn about x, built here in column-major order, so that the turns are not all about one axis.
  const rotationX = (a) => [1, 0, 0, 0, 0, Math.cos(a), Math.sin(a), 0, 0, -Math.sin(a), Math.cos(a), 0, 0, 0, 0, 1];
  const randomLocal = () =>
    multiply(
      translation(random() * 4 - 2, random() * 4 - 2, random() * 4 - 2),
      multiply(rotationY((random() * 2 - 1) * Math.PI), multiply(rotationX((random() * 2 - 1) * Math.PI), scaling(0.5 + random() * 1.5))),
    );
  const root = createNode(randomLocal());
  const nodes = [root];
  for (let i = 0; i < 30; i++) {
    const n = createNode(randomLocal());
    addChild(nodes[Math.floor(random() * nodes.length)], n);
    nodes.push(n);
  }
  for (let n = 0; n < 200; n++) {
    const node = nodes[1 + Math.floor(random() * (nodes.length - 1))];
    // Never attach a node below itself.
    const below = new Set();
    const collect = (x) => {
      below.add(x);
      x.children.forEach(collect);
    };
    collect(node);
    const targets = nodes.filter((x) => !below.has(x));
    const target = targets[Math.floor(random() * targets.length)];
    const before = worldMatrix(node);
    attach(node, target);
    near(worldMatrix(node), before, `move ${n + 1}: the world matrix changed`);
    assert.ok(node.parent === target, `move ${n + 1}: the node is not under its new parent`);
  }
});

A hint

Compute both world matrices before you touch the tree: const keep = worldMatrix(node) and const parentWorld = worldMatrix(newParent). The new local matrix is multiply(invertAffine(parentWorld), keep). Then take the node out of its old parent's children, set node.parent, and push it into newParent.children.

Matrix Calculator Multiply the arm's local matrices from the root down, T(0, 1, 0), then T(0, 2, 0) Rz(90°), and so on, and read the fingertip's position from the last column.

The self-check covers the five ideas of the lesson, from the order of the product to the shear. It opens where your earlier answers were weakest, and a question you miss returns before the round is over:

Interview questions

Warm-up (fresher to 2-5 years): How is a node’s world matrix computed in a scene graph, and why is it the parent’s world matrix times the local one?

Each node stores a local transform that places it in its parent’s coordinates. Its world matrix is the parent’s world matrix times that local transform, W = W(parent) L, and a root’s world matrix is its local transform. The order follows from what the local transform means: it first takes a point from the node’s coordinates into the parent’s, and the parent’s world matrix then takes it the rest of the way into the world. With column vectors that is W(parent) applied after L, so W(parent) stands on the left. On the lesson’s arm, bending the elbow by 90° moves the wrist to (−1.5, 3, 0), because its local move of 1.5 along y is carried out along the elbow’s turned axis. Reversed, local × parent leaves the fingertip at (0, 5, 0) as if nothing had bent.

Two questions of this module work through two scene-graph bugs, a grabbed object that jumps and a stretched parent that bends its child. A row’s link opens the question page, with the first step of an answer and the follow-ups an interviewer may add:

Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.

Choose a pass

Fresher to senior

In a VR app, when the player grabs a cup it jumps to another place in their hand, and when they let go it jumps again. The grab code makes the hand node the cup's parent and keeps the cup's transform values. Explain the jumps and fix the code.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

An artist stretches a table along its length with a scale of (2, 1, 1). A lamp parented to the table and turned 45° now looks slanted, and after export to glTF it looks different again. Explain both with numbers and fix the scene.

Model answer, Pro. First step and follow-ups

Key takeaways

A node stores only its local transform, and its world matrix is W(parent) L, computed from the root down: bending the arm’s elbow by 90° moved the fingertip from (0, 5, 0) to (−2, 3, 0).
A jointed figure is animated through its joints: two numbers moved all 85 nodes of the ring, and every hand stayed within 10⁻¹² of its neighbour’s.
Dirty flags recompute only the changed subtree: one arm cost 2 of 85 world matrices, a still frame none.
To attach a node without a jump, set its local transform to W(new parent)⁻¹ W(node) before re-parenting; picking uses the inverse of a node’s world matrix the same way.
A non-uniform scale on a parent shears turned children, 53.13° instead of 90° for the lamp, so keep such scales on nodes without children.

Terms in this lesson

dirty flag: A mark that a cached value is out of date. In a scene graph, changing a local transform marks the node and every node below it, and only marked world matrices are recomputed.
local transform: A node's own placement in its parent's coordinates, as a matrix or as a translation, rotation and scale. Animation changes local transforms.
scene graph: A tree of nodes in which each node stores a transform relative to its parent, so that moving a node moves everything below it.
world matrix: The matrix that takes a node's own coordinates to world coordinates: its parent's world matrix times its local transform, or its local transform for a root.

References

glTF 2.0 Specification: 3.5.3 Transformations (Khronos Group)
three.js documentation: Object3D (three.js authors)
three.js documentation: Matrix4 (decompose) (three.js authors)
three.js r186 source: Object3D.updateMatrixWorld (three.js authors)
The enduring tribal artistry of Maharashtra: Warli Paintings (Incredible India, Ministry of Tourism, Government of India)

Report a problem with this lesson

In this module: 3D transformations, rotations, cameras and projection

3D transformations, Euler angles and gimbal lock Free lesson, Pro answers: 25 minutes
Quaternions and rotation interpolation Free lesson, Pro answers: 25 minutes
Scene graphs and hierarchical transforms Free lesson, Pro answers: 20 minutes
Cameras, view matrices and projections Free lesson, Pro answers: 25 minutes
Clipping in clip space and the viewport transform Free lesson, Pro answers: 20 minutes

Your country

Scene graphs and hierarchical transforms

What you will learn

Before you start

What you will learn

Before you start

A node’s world matrix is its parent’s world matrix times its own

Animate a jointed figure by changing local transforms only

Dirty flags recompute only what changed

Local and world space: picking and attaching

A non-uniform scale on a parent shears its turned children

Practise: world matrices, then attaching

World matrices with dirty flags

Results of the sample tests

Pick and attach without a jump

Results of the sample tests

Interview questions

In a VR app, when the player grabs a cup it jumps to another place in their hand, and when they let go it jumps again. The grab code makes the hand node the cup's parent and keeps the cup's transform values. Explain the jumps and fix the code.

An artist stretches a table along its length with a scale of (2, 1, 1). A lamp parented to the table and turned 45° now looks slanted, and after export to glTF it looks different again. Explain both with numbers and fix the scene.

Key takeaways

References

Related tools