This chapter links to the course’s interactive demos and uses MathJax for its formulas. Read it through the course website (or download the file and open it in a browser); a Canvas inline preview will reach neither the demos nor the math. All chapters.

Scene Graphs and Hierarchical Modeling

Sketchpad (1963) already had master drawings and instances: change the master and every copy changes, which is the scene graph's instancing. Sutherland, Sketchpad, MIT PhD thesis, 1963

A robot arm, a character’s skeleton, a solar system: things built from jointed parts, where moving a parent must carry its children along. The scene graph is the structure that guarantees this. Every node stores one local transform, written in its parent’s frame, and every node’s world transform is the product of the local transforms along the path from the root. This chapter states that rule, derives it from the affine chapter’s composition of frames, works a two-node chain by hand and checks it against the library, and shows the recursion that computes a whole tree once per frame, first as a recursion and then as the explicit matrix stack an engine keeps. It then covers what the tree is used for beyond drawing: which world matrices a change invalidates, converting a point between any two nodes’ frames, hanging the camera on a node, a bounding box per subtree so a whole limb is culled with one test, and instancing one mesh under many nodes. It shows, with numbers, the one thing the tree cannot hold, a shear inherited from a non-uniformly scaled parent, and ends with the chain written as glTF nodes, where a pivot becomes an extra node and a rotation becomes a quaternion.

Contents
  1. Articulated things
  2. The composite rule
  3. A two-node chain, worked
  4. Joints: why a node’s local transform has a pivot
  5. The recursion
  6. The matrix stack, and a sibling
  7. Caching world matrices: dirty flags
  8. Local to world, and back
  9. Between any two nodes
  10. The camera as a node
  11. Bounding volumes up the tree
  12. Reuse: one mesh, many placements
  13. What a child cannot store: inherited shear
  14. Scene-graph files: glTF
  15. Hands-on
  16. Exercises

1 · Articulated things

Picture a base bolted to the floor, an arm hinged on the base, and a hand on the arm’s tip. Three rigid parts, three joints, and one constraint: they are attached. Yaw the base and the arm and hand must swing with it. Place each part with its own, independent world transform and the constraint is silently lost: yaw the base and nothing happens to the arm, because the arm’s transform never mentioned the base. Keeping the linkage together by hand would mean re-deriving every descendant’s world transform each frame, and the arithmetic that does that correctly is exactly the composition below. So build the tree, and get it for free.

Definition (scene graph) A scene graph is a tree whose nodes each carry a local transform \(L\), an affine matrix expressed in the parent’s coordinate frame, and optionally some geometry authored in the node’s own frame. The root’s parent is the world, whose transform is the identity. A node’s world transform \(W\) is derived, never authored.
A tree diagram: world (identity) above base, base above arm, arm above hand; each node box lists its local transform, and beside each the running product for its world transform.
The base-arm-hand tree of the course’s demo. The local transforms are what an author writes; the world transforms on the right are derived, never stored by hand.

The same tree is everywhere something is built from carried parts: a character is a tree of bones (the hand bone rides the forearm rides the upper arm; the animation chapter drives that tree with joint angles), a vehicle is a turret on a hull and wheels on axles, a solar system is moons about planets about a star. Whenever part B is attached to and carried by part A, B is a child of A. The word graph is historical (Open Inventor and VRML allowed shared subtrees, a directed acyclic graph); every engine in use today stores a tree, and shares geometry rather than nodes (Section 12).

2 · The composite rule

A node’s local transform \(L\) maps its own frame into its parent’s frame; the parent’s world transform \(W_{\text{parent}}\) maps the parent’s frame into the world. Composing two frame changes multiplies their matrices, in apply order:

The composite rule \[ W_{\text{child}} \;=\; W_{\text{parent}}\cdot L_{\text{child}}, \qquad W_{\text{root}} = L_{\text{root}} . \] Read right to left, as always for column vectors: \(L_{\text{child}}\) acts first and places a point in the parent’s frame, then \(W_{\text{parent}}\), which already contains every ancestor, carries it the rest of the way. Unrolled down a path, \[ W_{\text{hand}} = L_{\text{base}}\cdot L_{\text{arm}}\cdot L_{\text{hand}} , \] the running product of every local transform from the root to the node, root-most on the left.

That is “move the parent, the children follow” as arithmetic: because \(W_{\text{parent}}\) contains the base’s yaw, every descendant inherits it, and the author never touched the descendants. The discipline that makes it work is that a local transform is written in the parent’s frame, not the world’s. “Climb to the base’s top surface and hinge” stays true no matter where the base goes. The rule is also why the order of multiplication cannot be negotiated: a matrix product is not commutative (the affine chapter), and \(L_{\text{hand}}\,L_{\text{arm}}\,L_{\text{base}}\) would hinge the base about the hand.

3 · A two-node chain, worked

Worked example (a base that yaws, an arm one unit out) Let \(L_{\text{base}} = R_y(90^\circ)\), a base that has turned a quarter turn about the vertical, and \(L_{\text{arm}} = T(1, 0, 0)\), an arm that sits one unit out the base’s own \(x\) axis. By the block product of the affine chapter, the composite has linear part \(R_y(90^\circ)\) and translation \(R_y(90^\circ)\,(1,0,0)\): \[ W_{\text{arm}} = R_y(90^\circ)\cdot T(1,0,0) = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 1 \end{pmatrix}. \] The arm’s origin, at \((1, 0, 0)\) in the base’s frame, lands at world \((0, 0, -1)\): the base’s turn swung the child around. The arm’s local offset never changed; its world position is the parent’s rotation applied to that offset. The library computes the same matrix from matMul(makeTRS(0,0,0, 0,90,0, 1,1,1), makeTRS(1,0,0, …)).
Top view of the x-z plane: the base at the origin, its local x axis swung by the 90 degree yaw onto world minus z, the arm's origin at (0,0,-1) and its tip at (0,0,-2).
The chain seen from above (\(z\) runs down the page). The gray arrow is where the base’s \(x\) axis would point with no yaw; the green one is where it points after \(R_y(90^\circ)\), and the arm follows it.

4 · Joints: why a node’s local transform has a pivot

The demo’s real arm is not a single translation. Its box is modeled centered on its own origin, spanning \(y \in [-0.7, 0.7]\), but it must hinge about its lower end, the joint where it meets the base, and then sit on the base’s top surface. A single translate-rotate-scale cannot express a rotation about an end, so the local transform is a pivot sandwich:

\[ \begin{gathered} L_{\text{arm}} = T_{\text{joint}}\cdot T_{\text{lift}}\cdot R_{\text{bend}}\cdot T_{\text{pivot}}, \\[4pt] T_{\text{pivot}} = T(0, 0.7, 0),\quad R_{\text{bend}} = R_z(\text{bend}),\quad T_{\text{joint}} = T(0, 0.2, 0). \end{gathered} \]

Read right to left: \(T_{\text{pivot}}\) lifts the centered box so its lower end sits at the origin; \(R_{\text{bend}}\) hinges about that origin; \(T_{\text{joint}}\) (and an optional extra gap \(T_{\text{lift}}\)) carries the bent arm up to the base’s top surface, which is \(0.2\) above the base’s center. This is the affine chapter’s \(T(\mathbf{p})\,R\,T(-\mathbf{p})\), specialized to a joint at a box’s end. The base and the hand need only one makeTRS call each, because each turns about its own center.

Side view of the demo's base, arm and hand at bend angles 0, 40, 80 and 120 degrees; the black dot at the base's top surface stays fixed as the arm swings about it and the hand rides the arm's tip; the hand's position is printed under each pose.
Four bends of the demo’s arm with the base unyawed, every box drawn from its world matrix. The joint (black dot) never moves; the hand’s world position goes from \((0, 1.8)\) at bend 0 to \((-1.21, -0.3)\) at bend 120.
Worked example (the demo’s default pose) With base yaw \(30^\circ\) and bend \(40^\circ\) (the demo’s defaults) the chain gives \[ W_{\text{hand}} = \begin{pmatrix} 0.66 & -0.56 & 0.50 & -0.78 \\ 0.64 & 0.77 & 0.00 & 1.47 \\ -0.38 & 0.32 & 0.87 & 0.45 \\ 0 & 0 & 0 & 1 \end{pmatrix}, \] so the hand is at world \((-0.78, 1.47, 0.45)\), the arm’s center at \((-0.39, 0.94, 0.22)\) and the base’s at \((0, 0.2, 0)\). Yaw the base to \(90^\circ\) with the same bend and the hand moves to \((0, 1.47, 0.90)\): same height, swung a quarter turn about the vertical, exactly what the base’s rotation applied to the hand’s offset predicts. These are the numbers on the demo’s panel.
See it live Base, arm, hand: four sliders write the local transforms; the three world matrices are composed by the library’s own multiply and drive three flat boxes with no engine parenting anywhere. Drag the base yaw and everything swings; drag the bend and only the arm-and-hand subtree hinges at the joint.

5 · The recursion

One method computes every node’s world matrix, by recursion down the tree: receive the parent’s world matrix, multiply in the local matrix, draw this node’s geometry with the result, and pass the result to each child. 

function compositeXform(node, parentWorld) {
  node.world = matMul(parentWorld, node.local);      // W = W_parent ยท L
  for (const child of node.children) compositeXform(child, node.world);
  for (const prim of node.primitives) prim.draw(node.world);
}
compositeXform(root, IDENTITY);
The call stack of the recursion on the three-node arm: base called with the identity computes its world matrix and calls arm with it; arm computes its world matrix and calls hand; each level draws its primitives with its own world matrix.
The call stack is the path from the root to the node; each frame of it multiplies one more local transform onto the accumulated product. Siblings receive the same parent matrix because it is passed by value.

This traversal runs once per frame in every engine. Sung’s SceneNode in the course’s Unity projects is exactly this method with a pivot offset and a translate-rotate-scale from the Inspector as the local matrix, and a list of primitives that each apply their own pivot sandwich before uploading the product to the shader. Unity’s own Transform hierarchy does the same composition invisibly; the course rebuilds it so the composition is visible in code.

6 · The matrix stack, and a sibling

The recursion’s call stack holds one matrix per level. Written out as a data structure, it is the matrix stack of classic OpenGL (glPushMatrix, glPopMatrix) and of every retained-mode renderer: a stack whose top is the world matrix of the node being visited. Entering a node pushes \(\text{top}\cdot L\); leaving it pops. The stack never holds more matrices than the tree is deep, and a sibling starts from exactly the matrix its brother started from, because the brother’s push has been popped. 

stack = [IDENTITY]
function visit(node) {
  stack.push(matMul(stack.top(), node.local));   // enter: top is now W_node
  for (const child of node.children) visit(child);
  draw(node, stack.top());
  stack.pop();                                   // leave: top is W_parent again
}
Worked example (the trace on a tree with a sibling) Give the demo’s base a second arm, mirrored: \(L_{\text{arm2}} = S(-1, 1, 1)\,L_{\text{arm}}\), with its own hand. At the default pose (yaw \(30^\circ\), bend \(40^\circ\)) the stack runs:
stepstack depthtop’s origin (world)
push base1\((0, 0.2, 0)\)
push arm2\((-0.39, 0.94, 0.22)\)
push hand; draw hand; pop3, then 2\((-0.78, 1.47, 0.45)\)
draw arm; pop1
push arm22\((0.39, 0.94, -0.22)\)
push hand2; draw hand2; pop3, then 2\((0.78, 1.47, -0.45)\)
draw arm2; pop; draw base; pop1, then 0
Five pushes, five matrix products, maximum depth three. The second hand lands at \((0.78, 1.47, -0.45)\), the first hand’s position reflected through the base’s own \(yz\) plane and then yawed with it: the mirror is applied in the base’s frame, before the base’s rotation, because that is where \(L_{\text{arm2}}\) lives. The determinant of \(W_{\text{arm2}}\) is \(-1\); Section 12 says what that costs.

The stack view also explains a common bug. Draw the arm2 subtree without popping the first hand’s matrix and the second arm hangs off the first hand instead of the base: every push must have its pop, which is why the recursive form, where the language’s own call stack does the popping, is the safer one to write.

7 · Caching world matrices: dirty flags

Recomputing every world matrix every frame is cheap for three nodes and wasteful for a scene of ten thousand, most of which did not move. Engines cache \(W\) on the node and mark it dirty when its local transform changes; a dirty node’s world matrix is recomputed on demand, and so is every descendant’s, because each of them contains the changed matrix in its product. Nothing above the node, and nothing in a sibling subtree, is touched.

Definition (dirty propagation) Setting a node’s local transform marks the node and all of its descendants dirty. A dirty node’s world matrix is recomputed as \(W_{\text{parent}}\cdot L\) the next time it is read (after its parent’s, recursively), and the flag cleared. The cost of an edit is the size of the edited node’s subtree.
Worked example (what an edit touches) In the demo, changing the hand’s yaw recomputes 1 matrix, the bend recomputes 2 (arm and hand), the base’s yaw recomputes 3. On a 59-bone skeleton built as a spine of five bones with a neck and head, two arms of three bones each ending in a hand with five three-bone fingers, and two legs of three bones with a foot and two toe bones:
edited bonematrices recomputed
the root (the character moves)59
the first spine bone46
the left upper arm19
the left hand16
a fingertip1
A walking character edits most bones every frame, so the cache saves little there; a static building with one turning door saves everything but the door and its handle. The engine does not know which case it is in, which is why the flag is per node and the recomputation is lazy.

The same mechanism is why a node’s world matrix must be read through an accessor that checks the flag, never from the cached field directly: the field may be stale. It is also why deep hierarchies recompute from the locals rather than incrementally updating world matrices: a chain of sixty products in single precision drifts, as the rotation chapter measures, and a fresh product from authored locals every frame does not accumulate.

8 · Local to world, and back

Once a node’s world matrix exists, any point authored in the node’s frame reaches the world by one multiply, and any world point comes back by the inverse:

\[ \mathbf{p}_{\text{world}} = W\,\mathbf{p}_{\text{local}}, \qquad \mathbf{p}_{\text{local}} = W^{-1}\,\mathbf{p}_{\text{world}} . \]

Since every factor in the chain is a translation, a rotation or a positive scale, the product is still of that form, and the affine chapter’s block inverse (invertTRS in the library) applies to it directly; no general inversion is needed. Forward is placement (vertices, attachment points); backward is inquiry (is this world point inside me; where on my arm did the mouse ray of the interaction chapter hit).

Worked example (a tip out, a point back) With the two-node chain of Section 3, the arm’s tip at local \((1, 0, 0)\) lands at \(W_{\text{arm}}\,(1,0,0,1)^{\mathsf T} = (0, 0, -2)\): one unit past the arm’s origin, which was already at \((0,0,-1)\), both swung onto world \(-z\). Inverting, \[ W_{\text{arm}}^{-1} = \begin{pmatrix} 0 & 0 & -1 & -1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}, \qquad W_{\text{arm}}^{-1}\,(0, 0, -1, 1)^{\mathsf T} = (0, 0, 0): \] the arm’s world origin comes home to local \((0,0,0)\). The inverse’s linear part is \(R_y(90^\circ)^{\mathsf T} = R_y(-90^\circ)\) and its translation \(-R^{\mathsf T}\mathbf{t} = (-1, 0, 0)\), the rigid inverse of the affine chapter with \(\mathbf{t} = (0, 0, -1)\).

Reading columns works here too: columns 1 and 2 of a node’s world matrix are the node’s world-space up and forward axes, which is how a frame is planted at a hierarchy’s tip without any further computation.

9 · Between any two nodes

World space is a way station. To express a point known in node A’s frame in node B’s frame, go up to the world and back down: \(\mathbf{p}_B = W_B^{-1}\,W_A\,\mathbf{p}_A\). The product \(W_B^{-1}W_A\) is itself a rigid transform, the frame of A as seen from B, and it is what an inverse-kinematics solver, a constraint (“keep the hand on the handle”), or a physics joint works with.

Worked example (the hand from three frames) At the demo’s default pose the hand’s origin is world \((-0.779, 1.472, 0.450)\). In the base’s frame, \(W_{\text{base}}^{-1}\) applied to it gives \((-0.900, 1.272, 0)\): the base’s yaw has been undone, so the hand sits in the base’s own \(xy\) plane, and \(1.272 = 0.2 + 1.4\cos40^\circ\), \(-0.900 = -1.4\sin40^\circ\), the arm’s full length of \(1.4\) bent by \(40^\circ\) above the joint. In the arm’s frame it is \((0, 0.7, 0)\) exactly, the translation of \(L_{\text{hand}}\), as it must be. Going the other way, the world point \((0, 1, 0)\) is \((0.386, -0.940, 0)\) in the hand’s frame: below the hand and to its side. And \(W_{\text{hand}}^{-1}W_{\text{arm}}\), the arm as seen from the hand, has translation \((0, -0.7, 0)\): the arm’s center is \(0.7\) below the hand along the hand’s own \(y\), which is the arm’s \(y\) since the hand is not yawed.

10 · The camera as a node

Nothing distinguishes the camera from any other node. Give it a local transform under the hand and it rides the arm; its world matrix \(W_{\text{cam}}\) is where it is and which way it faces, and the view matrix of the viewing chapter is that matrix’s inverse, \(V = W_{\text{cam}}^{-1}\). This is how a driver’s-seat camera, a shoulder camera and a camera on a crane are built: as nodes, so that the same traversal that places the geometry places the eye.

Worked example (a camera on the hand) Parent a camera to the hand with \(L_{\text{cam}} = T(0, 0.3, 0)\). Its world position is \(W_{\text{hand}}\,(0, 0.3, 0) = (-0.946, 1.702, 0.546)\), and its view matrix is \[ V = (W_{\text{hand}}\,L_{\text{cam}})^{-1} = \begin{pmatrix} 0.66 & 0.64 & -0.38 & -0.26 \\ -0.56 & 0.77 & 0.32 & -2.01 \\ 0.50 & 0.00 & 0.87 & 0.00 \\ 0 & 0 & 0 & 1 \end{pmatrix}, \] whose rows are the columns of \(W_{\text{hand}}\)’s rotation (the rigid inverse), and which sends the camera’s own world position to \((0, 0, 0)\). The camera looks down its local \(-z\), which is the hand’s \(-z\): sideways off the arm. A look-at built from the node’s position and a target replaces only the rotation rows.

11 · Bounding volumes up the tree

A renderer should not send the frustum a triangle it cannot see, and it should not test every triangle to find out. Each node keeps a bounding volume around its own geometry, and each subtree keeps one around all of its descendants’ volumes; the frustum test of the viewing chapter then runs on the tree: a subtree whose box is entirely outside is rejected with one test, one entirely inside is accepted with one test, and only a box that straddles a plane is opened and its children tested. It is the same idea as the ray-tracing chapter’s bounding-volume hierarchy, with the scene graph’s own tree as the hierarchy.

Definition (world-space AABB of a node) Transform the eight corners of the node’s local box by \(W\) and take the coordinate-wise minimum and maximum; a subtree’s box is the union (coordinate-wise min and max) of its node’s box and its children’s subtree boxes. A bounding sphere is the box’s center and half-diagonal, cheaper to test and looser.
Side view of the demo's base, arm and hand at the default pose with each part's world-space box dashed in its color, the arm-plus-hand subtree box in orange, the whole tree's box in black, and a dashed purple plane at x = minus 0.6.
World-space boxes at the demo’s default pose. The rotated arm has a loose box (a box around a tilted stick), which is the price of axis alignment; the subtree boxes nest.
Worked example (five tests instead of many) With the demo’s boxes (base \(0.35\times0.2\times0.35\) half-extents, arm \(0.12\times0.7\times0.12\), hand \(0.22\times0.12\times0.22\)) at the default pose, the world boxes are base \([-0.478, 0.478]\) in \(x\), arm \([-0.919, 0.140]\), hand \([-1.102, -0.457]\); the arm subtree spans \([-1.102, 0.140]\) and the whole tree \([-1.102, 0.478]\), with a bounding sphere of radius \(1.318\) about \((-0.312, 0.853, 0.143)\). Against a plane \(x = 1\) that keeps \(x < 1\), the tree’s box is entirely inside: one test accepts all three parts. Against a plane \(x = -0.6\) that keeps \(x < -0.6\), the tree’s box straddles, so the test descends: the base (\(x \ge -0.478\)) is rejected in one test, the arm subtree straddles, and its two children are tested and both straddle. Five box tests decide the whole tree, and only the arm’s and hand’s triangles go on to be clipped.

The boxes are recomputed when the world matrices are, so they ride the dirty flags of Section 7; an engine stores the local box once and the world box per frame. A character’s skeleton uses the same trick in reverse for the mesh it skins: one box around the whole character, grown by the extent of any pose, so the character is culled as a unit.

12 · Reuse: one mesh, many placements

Top view of a car body with one wheel mesh placed at four corners by four translations.
Geometry is separate from placement. One wheel mesh, four nodes that differ only by their local translations; a mirrored arm is the same mesh under a scale of \((-1, 1, 1)\), whose negative determinant flips its windings.

Because a primitive’s shape is fixed in its node’s frame and the node supplies the matrix, one mesh can be instanced across many nodes that share geometry but differ by transform: four wheels, five fingers, both shoulders. Fix the wheel once and every copy updates; the tree turns “place \(N\) copies” into “\(N\) local transforms on shared geometry”. On the GPU the same idea is instanced drawing: one vertex buffer, an array of world matrices, one draw call, and the vertex shader picks its matrix by instance index. A forest of ten thousand trees is one mesh and ten thousand matrices.

The mirrored arm of Section 6 is instancing with a catch. \(S(-1, 1, 1)\) has determinant \(-1\), so every product below it does too (\(\det W_{\text{arm2}} = -1\)), and a determinant of \(-1\) reverses the winding of every triangle (the affine chapter): the mirrored arm’s front faces become back faces and the renderer culls the outside of the mesh and shows its inside. The fix is to flip the cull mode for nodes whose world determinant is negative, which every engine does by tracking the sign down the tree.

13 · What a child cannot store: inherited shear

Engines store a node’s local transform as translation, rotation and scale, the TRS of the affine chapter, and hand back a node’s world transform in the same three parts. The product of two TRS matrices is not always a TRS matrix. A rotated child under a non-uniformly scaled parent has a world matrix with a shear, and there is no rotation and scale that reproduce it.

A unit square rotated 45 degrees, drawn dashed gray; the same square under the parent's scale of 2 in x, a blue parallelogram; and the rectangle a TRS read-back of that matrix would draw, dashed red, which does not match.
The child’s square under \(W = S(2, 1, 1)\,R_z(45^\circ)\) is a parallelogram. The read-back rectangle has the right column lengths and the right first axis, and the wrong shape.
Pitfall (reading a world scale off a sheared matrix) Parent \(S(2, 1, 1)\), child \(R_z(45^\circ)\). The world matrix’s first two columns are \((1.414, 0.707, 0)\) and \((-1.414, 0.707, 0)\): both of length \(1.581\), and \(126.9^\circ\) apart instead of \(90^\circ\). A read-back that takes the column lengths as the scale (\(1.581, 1.581\)) and the first column’s direction as the rotation (\(26.6^\circ\), not \(45^\circ\)) rebuilds \(R_z(26.6^\circ)\,S(1.581, 1.581)\), whose largest entry differs from \(W\) by \(0.707\). The composed matrix is correct and draws the parallelogram; the reported world scale and rotation are wrong, and anything that consumes them (a physics collider sized from the world scale, a child re-parented with “keep world transform”) is wrong by that much. Two rules follow: keep non-uniform scale on leaf nodes with no rotated children, and never read a world TRS back when the world matrix is available.

The same shear breaks normals, which is why the normal matrix is the inverse transpose of the world matrix, not the world matrix itself, and why the animation chapter interpolates the three parts separately and never the composed matrix.

14 · Scene-graph files: glTF

A scene graph on disk is a list of nodes with parent links, and glTF, the format every engine and tool reads today, stores exactly the structure of this chapter: an array of nodes, each with an optional translation, rotation (a unit quaternion, the rotation chapter’s \((x, y, z, w)\)), scale and children (indices into the same array), and optionally a mesh index. The world matrix is not stored; a reader recomputes it by the composite rule. A node may instead carry a full 16-entry matrix, but a node with a matrix cannot be animated, precisely because of Section 13.

Worked example (the demo’s chain as glTF nodes) The arm’s pivot sandwich is not one TRS, so it becomes two nodes: a joint node that carries the translation to the base’s top and the bend rotation, and the arm node under it that carries the half-length offset and the mesh. The base’s yaw of \(30^\circ\) about \(y\) is the quaternion \((0, 0.2588, 0, 0.9659)\) (\(\sin 15^\circ, \cos 15^\circ\)) and the bend of \(40^\circ\) about \(z\) is \((0, 0, 0.3420, 0.9397)\): 
"nodes": [
  { "name": "base",  "translation": [0, 0.2, 0], "rotation": [0, 0.2588, 0, 0.9659], "children": [1] },
  { "name": "joint", "translation": [0, 0.2, 0], "rotation": [0, 0, 0.3420, 0.9397], "children": [2] },
  { "name": "arm",   "translation": [0, 0.7, 0], "mesh": 0, "children": [3] },
  { "name": "hand",  "translation": [0, 0.7, 0], "mesh": 1 }
]
Read the joint node’s local as \(T(0, 0.2, 0)\,R_z(40^\circ)\) and the arm’s as \(T(0, 0.7, 0)\): their product is \(T_{\text{joint}}\,R_{\text{bend}}\,T_{\text{pivot}}\), the sandwich of Section 4 with the lift folded into the joint. An animation in the file targets the joint node’s rotation with keyframed quaternions, and a skin lists which nodes are the bones of a skinned mesh, with one inverse bind matrix each: the \(B_i^{-1}\) of the animation chapter.

15 · Hands-on

Hands-on Run these from the css551/ directory; each prints the numbers of this chapter.
  1. The two-node chain of Section 3: the world matrix, the tip, and the round trip. 
    node -e "import('./lib/core/xform.js').then(x=>{
  const W = x.matMul(x.makeTRS(0,0,0, 0,90,0, 1,1,1), x.makeTRS(1,0,0, 0,0,0, 1,1,1));
  console.log(W.map(v=>+v.toFixed(2)));                                     // [0,0,-1,0, 0,1,0,0, 1,0,0,0, 0,0,-1,1]
  console.log(x.applyMat4(W, [1,0,0]).map(v=>+v.toFixed(2)));               // [0, 0, -2, 1]   the tip
  console.log(x.applyMat4(x.invertTRS(W), [0,0,-1]).map(v=>+v.toFixed(2))); // [0, 0, -0, 1]   the origin comes home
})"
    The 16 numbers are the matrix of Section 3 stored column by column; the fourth column \((0, 0, -1, 1)\) is the translation.
  2. The inherited shear of Section 13: the two columns and their dot product. 
    node -e "import('./lib/core/xform.js').then(x=>{
  const W = x.matMul(x.makeTRS(0,0,0, 0,0,0, 2,1,1), x.makeTRS(0,0,0, 0,0,45, 1,1,1));
  const c0 = [W[0],W[1],W[2]], c1 = [W[4],W[5],W[6]];
  console.log(c0.map(v=>+v.toFixed(3)), c1.map(v=>+v.toFixed(3)), 'dot', +x.dot(c0,c1).toFixed(3));
})"
    Prints [1.414, 0.707, 0] [-1.414, 0.707, 0] dot -1.5. A rotation-and-scale matrix has orthogonal columns; a dot product of \(-1.5\) says this one is not.
  3. The quaternions of the glTF example. 
    node -e "import('./lib/core/xform.js').then(x=>console.log(
  x.quatFromAxisAngle(0,1,0,30).map(v=>+v.toFixed(4)), x.quatFromAxisAngle(0,0,1,40).map(v=>+v.toFixed(4))))"
    Prints [0, 0.2588, 0, 0.9659] [0, 0, 0.342, 0.9397].
  4. In the scene-graph demo, set the base yaw to \(90^\circ\) and the bend to \(40^\circ\), and read the hand’s position off the panel: \((0.00, 1.47, 0.90)\). Then set the yaw back to \(30^\circ\) and change only the hand’s yaw: the hand’s position does not move (only its orientation does), which is Section 7’s claim that an edit touches only the edited subtree.

16 · Exercises

Exercise 1 (the rule, three levels) \(L_{\text{base}} = T(0, 1, 0)\), \(L_{\text{arm}} = R_z(90^\circ)\), \(L_{\text{hand}} = T(2, 0, 0)\). Where is the hand’s origin in the world?
Solution \(W_{\text{hand}} = T(0,1,0)\,R_z(90^\circ)\,T(2,0,0)\). Apply right to left to the origin: \(T(2,0,0)\) gives \((2,0,0)\); \(R_z(90^\circ)\) sends \(x\) to \(y\), giving \((0,2,0)\); \(T(0,1,0)\) gives \((0, 3, 0)\).
Exercise 2 (order) Swap the base and arm locals of Exercise 1 (\(L_{\text{base}} = R_z(90^\circ)\), \(L_{\text{arm}} = T(0,1,0)\)). Where is the hand now, and why does it differ?
Solution \((2,0,0)\to T(0,1,0)\to(2,1,0)\to R_z(90^\circ)\to(-1, 2, 0)\). The rotation is now applied after the arm’s translation and swings it; in Exercise 1 the base’s translation came last and was untouched by any rotation. The composite rule is not commutative because matrix products are not.
Exercise 3 (a joint at an end) A box spans \(y\in[-1, 1]\) about its origin. Write the local transform that hinges it by \(\theta\) about its lower end and places that end at \((0, 3, 0)\) in the parent.
Solution \(L = T(0,3,0)\,R_z(\theta)\,T(0,1,0)\): lift the box so its lower end is at the origin, hinge, carry to \((0,3,0)\). Its translation column is \((0,3,0) + R_z(\theta)(0,1,0)\), so the box’s center sits one unit from the joint in the bent direction, as it should.
Exercise 4 (inverse) In the two-node chain of Section 3, a world point \((1, 0, -1)\) lies near the arm. Express it in the arm’s local frame.
Solution \(W_{\text{arm}}^{-1}\) has linear part \(R_y(-90^\circ)\), whose columns send \(\hat{\mathbf{x}}\to(0,0,1)\) and \(\hat{\mathbf{z}}\to(-1,0,0)\), so \((1,0,-1)\mapsto 1\cdot(0,0,1) + (-1)\cdot(-1,0,0) = (1, 0, 1)\); add the translation \((-1,0,0)\): \((0, 0, 1)\). In the arm’s frame the point is one unit along its local \(z\), beside the arm’s origin. Check forward: \(W_{\text{arm}}(0,0,1) = R_y(90^\circ)(0,0,1) + (0,0,-1) = (1,0,0) + (0,0,-1) = (1, 0, -1)\).
Exercise 5 (cost) A character has 60 bones. How many \(4\times4\) products does the traversal cost per frame, and why is that not a concern?
Solution One product per node, 60; at 64 multiply-adds each, under 4,000 operations, negligible beside the tens of thousands of vertices each bone will then transform. The tree’s cost is in its depth (a chain of 60 multiplies accumulates floating-point error), which is why engines recompute from the locals every frame rather than incrementally updating world matrices.
Exercise 6 (the stack) Trace the matrix stack for a root with three children, the second of which has two children of its own. How many pushes, and what is the maximum depth? Which nodes see the same parent matrix?
Solution Six pushes (root, three children, two grandchildren), one per node; maximum depth three (root, second child, a grandchild). The three children all start from the root’s matrix, and the two grandchildren from the second child’s: siblings share a parent matrix because the sibling before them was popped.
Exercise 7 (dirty flags) In the 59-bone skeleton of Section 7, an animation edits the top spine bone and everything below it (neck, head, both arms and hands) but not the legs. How many matrices are recomputed, and does the cache help?
Solution The first spine bone’s subtree is 46 bones; the top spine bone’s subtree is four fewer, 42. The root, the four lower spine bones and the two legs (\(2\times6 = 12\)) are skipped: 42 of 59 recomputed, 17 saved, about a quarter. The cache helps in proportion to how much of the tree holds still.
Exercise 8 (between nodes) At the demo’s default pose, express the base node’s origin (world \((0, 0.2, 0)\)) in the hand’s frame, using the numbers of Section 9.
Solution The hand’s origin in the base’s frame is \((-0.900, 1.272, 0)\), so the base’s origin relative to the hand, still in base coordinates, is \((0.900, -1.272, 0)\); the hand’s frame is the base’s turned by the bend, \(R_z(40^\circ)\), so apply \(R_z(-40^\circ)\): \((0.900\cos40^\circ - 1.272\sin40^\circ,\; -0.900\sin40^\circ - 1.272\cos40^\circ,\; 0) = (-0.129, -1.553, 0)\). Almost straight down the hand’s own \(-y\), \(1.4\) of arm plus \(0.2\) of base away, and slightly to one side. The library agrees: applyMat4(invertTRS(W_hand), [0, 0.2, 0]) prints \((-0.129, -1.553, 0)\).
Exercise 9 (shear, in code) Using the library, compose \(S(1, 3, 1)\) as a parent with \(R_z(30^\circ)\) as a child and report the angle between the first two columns of the product. Then swap the order (rotated parent, scaled child) and report it again. Which order is safe?
Solution matMul(makeTRS(0,0,0,0,0,0,1,3,1), makeTRS(0,0,0,0,0,30,1,1,1)) has columns \((0.866, 1.5, 0)\) and \((-0.5, 2.598, 0)\); their dot product is \(3.464\) and the angle \(\arccos(3.464/(1.732\cdot2.646)) = 40.9^\circ\): sheared. Swapped, \(R_z(30^\circ)\,S(1,3,1)\) has columns \((0.866, 0.5, 0)\) and \((-1.5, 2.598, 0)\), dot product \(0\): a rotation of a scaled square, still a TRS. A scale below a rotation is safe; a rotation below a non-uniform scale is not.