Scene Graphs: Structure, Traversal

A scene graph is a tree (sometimes a DAG) where each node represents an object in a scene and edges represent parent-child relationships. Transformations, visibility, and properties propagate down the hierarchy.

Simple but powerful. Most rendering engines, UI frameworks, and spatial systems use some form of it.

The Data Structure

Each node carries:

type SceneNode = {
  id: string
  type: string
  transform: Matrix4x4      // local transform relative to parent
  worldTransform: Matrix4x4 // accumulated from root
  children: SceneNode[]
  parent: SceneNode | null
  metadata: Record<string, unknown>
}

The tree itself:

type SceneGraph = {
  root: SceneNode
  index: Map<string, SceneNode>  // O(1) lookup by id
}

index is important — pure tree traversal for every lookup is O(n). A flat map alongside the tree gives the best of both worlds.

Building It

function addNode(graph: SceneGraph, node: SceneNode, parentId: string) {
  const parent = graph.index.get(parentId)
  if (!parent) throw new Error(`parent ${parentId} not found`)
  node.parent = parent
  parent.children.push(node)
  graph.index.set(node.id, node)
}

Transform Propagation

World transform = parent's world transform × local transform. Propagate on every update:

function propagateTransforms(node: SceneNode, parentWorld: Matrix4x4) {
  node.worldTransform = multiply(parentWorld, node.transform)
  for (const child of node.children) {
    propagateTransforms(child, node.worldTransform)
  }
}

This is a DFS pre-order traversal — parent must be resolved before children. O(n) over all nodes.

Traversal Algorithms

DFS pre-order — rendering, transform propagation. Parent before children.

DFS post-order — cleanup, bounds computation. Children before parent.

BFS — level-by-level processing, useful when depth matters.

function bfs(root: SceneNode, visit: (node: SceneNode) => void) {
  const queue: SceneNode[] = [root]
  while (queue.length) {
    const node = queue.shift()!
    visit(node)
    queue.push(...node.children)
  }
}

What You Can Extract

Once the graph is built and transforms are propagated, a lot becomes queryable:

Spatial queries — world position of any node in O(1) from worldTransform. Relative position between two nodes via inverse transform.

Subtree metadata — aggregate properties across a subtree with a post-order traversal. Count nodes, sum weights, collect types.

Ancestry and relationships — walk parent pointers to find common ancestors, depth, or path between two nodes.

Visibility culling — mark a parent invisible, propagate the flag down. One write, O(subtree) reads.

Change detection — dirty flag on nodes. Only re-propagate transforms for subtrees that changed.

function collectTypes(node: SceneNode): Record<string, number> {
  const counts: Record<string, number> = {}
  bfs(node, (n) => {
    counts[n.type] = (counts[n.type] || 0) + 1
  })
  return counts
}

The Interesting Part

The real value isn't the tree — it's the index plus the relationships. A flat list of objects tells nothing about context. A scene graph tells where something is, what it belongs to, and how it relates to everything else.

That relationship layer is what makes scene graphs useful beyond rendering.