Lab 4.4 — Scenes, Culling & Instancing

← Course 4 syllabus · Module 4 · Prev: « Lab 4.3 · Next: Lab 5.1 »

Goal

Give the engine a scene layer — and make it flat. The object-oriented reflex is a graph of Node objects with virtual draw() methods; this lab builds the data-oriented alternative the whole module has been arguing for: flat arrays of transforms, bounds, and render keys, indexed by Lab 0.2’s generational handles — the pool benchmark from Module 0, now run at engine scale on a real frame (Course 3 Module 2’s cache ladder was the prediction; this is the payoff). On top of it: a transform hierarchy flattened once per frame, frustum culling with the six planes extracted straight from the view-projection matrix — pure Course 1 Section 1 material, since a plane test is one dot product — instanced draws for repeated meshes, sort keys (pipeline → material → depth) with a measured account of what each ordering buys, and a stats HUD on screen every frame from here to the capstone.

Scope note, stated up front: culling here is CPU-side — it is where the math and the data layout are learned. Moving it to the GPU (compute culling, indirect draws) is Lab 5.4’s whole subject, and this lab’s arrays are deliberately shaped so that port is a move, not a rewrite.

Recommended reading

• Lengyel — the frustum/plane and view-frustum-culling chapters (title-level reference; confirm against the copy in hand): plane extraction from the combined matrix, point/sphere/box against plane, normalization. Read for the application; the linear algebra is Course 1 Section 1, mastered.
• D&P — the geometric-tests and bounding-volume chapters, as the gentler second telling — particularly good on the AABB p-vertex trick.
• C&S — skim the GPU-driven-rendering chapter’s culling discussion (title-level) to see where this lab’s CPU version is headed in Lab 5.4; their per-object data layout is worth comparing against yours when you design the arrays.
• MbT — the instancing material in the later chapters (title-level; confirm against the copy in hand) for the Metal-side idiom: per-instance data in a buffer, instance_id in the vertex function.
• Course 3, Module 2 (syllabus) — your own cache-ladder notes; the culling loop is written to its conclusions (contiguous, predictable, branch-light).
• Lab 0.2 — your pool-vs-pointers benchmark and notes; this lab is the same experiment with a frame attached.

Prerequisites

• Lab 4.1–4.2: the frame loop and render graph — the scene layer feeds draw lists into graph passes.
• Lab 4.3: the job system — culling is embarrassingly parallel and becomes its second client.
• Lab 0.2: the generational pool — scene objects live in it.

Project & environment setup

• Scene layer in engine/render/ (target engine_render) with the math kept in engine/core/ (target engine_core) — plane extraction and the intersection tests are backend-free and unit-testable without a GPU.
• New lab executable labs/lab-4-4/ → scene_stress, with the experiment surface on flags:
  • --cull on|off · --instancing on|off · --sort key|none|random · --objects N (default 10000) · --seed S (reproducible layouts);
  • --stats-dump FILE writes the HUD counters per run for the benchmark tables.
• The stress scene, specified (the predictions below depend on it): 10,000 objects drawn from 8 unique meshes and 4 materials (so ≤ 32 pipeline/material combinations), positions uniform in a ball centered on the camera’s position, ball radius large against object size; camera 60° horizontal FOV, 16:9, free-orbit.
• Google Benchmark target cull_bench for per-object test costs, apart from the live frame.

Where results go:

Artifact	Path
Notes, plane-extraction derivation, sort-key experiment table, state-of-the-engine note	labs/lab-4-4/notes.md
Tracy traces (cull on/off, sort modes), GPU captures both backends, screenshots	labs/lab-4-4/captures/
cull_bench JSON, HUD stat dumps per configuration	labs/lab-4-4/benchmarks/

Background

Flat scene, flattened transforms. The scene is parallel arrays over pool indices — no virtual dispatch, no pointer chasing:

Array	Contents	Consumed by
local_transforms[]	per-object TRS, authoring-side	flatten pass
world_transforms[]	flattened world matrices, rebuilt per frame	instance-buffer fill
world_bounds[]	sphere (center, radius) and/or AABB, world space	the culling loop — its entire working set
render_keys[]	64-bit sort keys (layout below)	sort + batching
instance_of[]	mesh/material identity per object	batch discovery

Parent-child relationships live in a separate small structure ordered so that one linear pass (parents before children — a topological order maintained on edit, not recomputed) produces world_transforms[] per frame. The hierarchy is an authoring structure; the frame consumes only flat arrays. This is Course 3 M2’s lesson applied: the culling loop streams world_bounds[] once, contiguously, and touches nothing else.

Plane extraction — a Section 1 exercise. A point is inside clip space when \(-w \le x \le w\), \(-w \le y \le w\), \(0 \le z \le w\) (the 0-to-1 near plane of Vulkan/Metal, pinned in Lab 0.2’s conventions header). Writing \(\mathbf{m}_1 \dots \mathbf{m}_4\) for the rows of the combined matrix \(M = P\,V\), each inequality becomes a half-space in world coordinates, giving the six planes as row combinations — the Gribb–Hartmann observation:

\[\boldsymbol{\pi}_{\text{left}} = \mathbf{m}_4 + \mathbf{m}_1, \qquad \boldsymbol{\pi}_{\text{right}} = \mathbf{m}_4 - \mathbf{m}_1, \qquad \boldsymbol{\pi}_{\text{near}} = \mathbf{m}_3, \qquad \dots\]

each \(\boldsymbol{\pi} = (\mathbf{n}, d)\) then normalized by \(\lVert\mathbf{n}\rVert\) so that \(\mathbf{n}\cdot\mathbf{p} + d\) is a true signed distance. Derive the left-plane case by hand in notes.md — it is three lines of Section 1 algebra, and doing it once forever demystifies the formula. Two convention traps: row-vs-column storage (GLM is column-major — extracting “rows” means reading across columns), and the 0-to-1 near plane, whose extraction differs from the GL-era \(-w \le z\) form that older texts (Lengyel included) assume.

The tests. Sphere with center \(\mathbf{c}\), radius \(r\): outside if for any plane

\[\mathbf{n}_i \cdot \mathbf{c} + d_i < -r,\]

otherwise drawn. AABB: test the p-vertex — the corner farthest along \(\mathbf{n}_i\), selected componentwise by the signs of \(\mathbf{n}_i\) — against each plane; one dot product per plane either way. Six dot products per object over a contiguous array: the shape SIMD loves, which is what makes the cull_bench numbers predictable. One honesty caveat for the HUD: the test is conservative — a large object near a frustum corner can pass all six half-space tests yet lie outside the frustum. False positives cost a draw, never correctness.

Sort keys. Each visible object gets a 64-bit key and the draw list is sorted before recording:

Bits (high → low)	Field	What ordering it buys
top	pipeline	fewest pipeline binds — the most expensive state change
middle	material	fewest descriptor/argument-buffer rebinds; makes instancing batches contiguous
low	depth (quantized)	opaques front-to-back: early-Z rejection — big on the immediate-mode Linux desktop GPU (RTX 4090), largely neutralized by the Mac’s TBDR hardware, a divergence Lab 5.2 explains and this lab’s numbers will already show

Transparents flip the depth field and sort back-to-front behind all opaques — blending is order-dependent and Module 2’s rules still bind.

Instancing. After sorting, runs of identical mesh + material collapse into one draw with per-instance data (world transform, material index) written to a per-frame buffer: vkCmdDrawIndexed with instanceCount > 1 indexing via gl_InstanceIndex on Vulkan; the equivalent instance_id-indexed buffer on Metal — one mechanism, both backends, fed by the same sorted array. The per-frame buffer’s lifetime is exactly the frame-slot story from Lab 4.1; nothing new to invent.

The stats HUD. Four counters, live and dumpable: visible (post-cull object count), culled, draws (submitted draw calls after batching), triangles (post-cull, pre-rasterization). Every experiment in this lab reads off this HUD, and the capstone’s report quotes it.

Tasks

1. Scene arrays + flatten. Build the flat scene structures over the Lab 0.2 pool; implement the per-frame hierarchy flatten (one linear pass, parents-first). Unit-test with a three-deep hierarchy against hand-multiplied matrices from Course 1 §1.
2. Planes + tests. Implement extraction from \(PV\) and the sphere and AABB tests — the math is stated above; the code is yours. Unit-test extraction against a hand-constructed frustum (axis-aligned camera, known FOV) and the tests against points placed just inside and outside each plane.
3. Benchmark the tests. cull_bench measures ns/object for the sphere and AABB variants over 10k contiguous bounds — and over the same bounds behind a vector<unique_ptr> indirection, closing the loop on Lab 0.2’s pool argument at engine scale.
4. The stress scene. Build scene_stress per the specification; wire the stats HUD and --stats-dump.
5. Culling on/off. Toggle --cull and capture both configurations in Tracy and one GPU capture each: CPU evidence (the cull zone’s cost vs. the recording time it saves) and GPU evidence (vertex work dropping with the culled fraction). Then parallelize the cull loop with Lab 4.3’s job system — its second client, as promised — and note the serial-fraction change in the frame.
6. Instancing. Implement the per-instance buffer path on both backends; verify the HUD’s draw count collapses to the batch count while triangles stay constant, and the image is unchanged.
7. The sort-key experiment. Render the stress scene with --sort key, none (stable submission order), and random (seeded worst case); record frame time and pipeline-bind counts (HUD counter) for each on both backends. This is the “what does ordering buy” table — fill it with numbers, not folklore.

Deliverable & expected results

• scene_stress at 10k objects with culling, instancing, and sorted draws on both backends; validation silent; HUD live; traces, captures, and counter dumps archived.
• notes.md carries the left-plane derivation, the unit-test summary, the sort-key table, and the reconciliations.

Quantity	Predicted	Measured
Visible fraction, stress scene (camera at ball center, 60° h-FOV, 16:9)	solid-angle ratio \(\Omega/4\pi\) with \(\Omega = 4\arcsin\!\big(\sin\tfrac{\theta_h}{2}\,\sin\tfrac{\theta_v}{2}\big)\) — work it out by hand for \(\theta_h = 60°\) (≈ 5% before near/far clipping trims further); the HUD’s visible count should sit near it, frame after frame, orbit or no orbit	…
Draw calls after instancing	from scene composition: ≤ 8 meshes × 4 materials = ≤ 32 batches for the visible set, vs. one draw per visible object (~500 at the predicted fraction) without — a > 10× reduction, derivable before running	…
Sphere-test cost per object (cull_bench)	qualitative: single-digit to low-tens of ns — six dot products over contiguous data, SIMD-friendly; if the disassembly shows scalar code (Course 3 Module 5 NEON eyes), that’s a flag worth chasing	…
Contiguous bounds vs. pointer-chased bounds (cull_bench)	integer-factor gap, the Lab 0.2 pool benchmark’s factor reproduced at engine scale — cite your own Module 0 number as the prediction	…
Sorted vs. random submission — pipeline binds & frame time	binds collapse from ~visible-count to ≤ 32; frame-time delta larger on the 4090 than the Mac (early-Z and bind costs differ by architecture) — direction predicted, magnitude measured	…
Cull cost vs. recording saved (cull zone vs. record zone, 10k objects)	culling costs tens of µs (10k × ns-scale tests); recording ~95% fewer draws saves more — net win, itemized from the two Tracy zones	…

Profiling & performance

Tracy: flatten, cull, sort, record zones — the frame’s new CPU anatomy, kept for the rest of the course — plus Tracy plots wired to the HUD counters (visible, draws) so scene dynamics are readable in the trace timeline. Take one GPU capture per backend at the final configuration (cull + instancing + sorted) and confirm from the capture, not the HUD, that draw and vertex counts match the CPU-side story. cull_bench runs under the benchmark discipline of Lab 0.2 — pinned repetitions, medians — and its JSON is archived alongside the frame data.

Analysis & reconciliation

Reconcile the visible fraction against the solid-angle prediction — residuals come from near/far clipping and bound conservatism; estimate each separately. Check the instancing arithmetic exactly; the HUD makes it checkable to the draw. Reconcile ns/object against a hand model from the Course 3 M2 ladder: 16–32 bytes of bounds per object streamed once, six fused multiply-add dot products — is the loop bandwidth-bound or ALU-bound at your measured number, and does the disassembly agree? For the sort experiment, explain the Mac/4090 asymmetry in one paragraph using the TBDR-vs-immediate-mode distinction the syllabus promised Module 5 would keep meeting. Then close the module: the engine now has a spine (4.1), a compiler (4.2), workers (4.3), and a scene (4.4) — write the half-page “state of the engine” note, including what each lab’s abstraction cost when measured, that the capstone’s performance report will one day quote.

Going further

• Add a coarse spatial pre-pass — a uniform grid or loose octree culled before per-object tests — and find the object count where hierarchy beats brute force over flat arrays; the honest answer at 10k may be “not yet,” which is itself the data-oriented lesson.
• Hand-vectorize the sphere test (NEON intrinsics, four spheres per iteration, Course 3 Module 5 style) and race the compiler’s autovectorized version in cull_bench.
• Instrument bound tightness: log the screen-space area of culled-but-drawn false positives over one orbit; decide with numbers whether tighter bounds (OBB, convex hull) would pay their cost here.
• Sort with a radix pass instead of std::sort and measure at 10k and (synthetically) 1M keys — foreshadowing Lab 5.4, where sorting moves to the GPU.
• Read ahead to Lab 5.4 and note in notes.md exactly which of this lab’s arrays move into GPU buffers unchanged — the port plan, written while the design is fresh.