Picking and Culling Spatial Hierarchies: BVH for Document Scenes

Software 4 Senses LLC · Last updated 2026-10-01

A 3D Spatial Web Interface has to answer two spatial questions constantly: which object is under the cursor, and which objects each rendering ray actually needs to test. The Software 4 Senses 3D Spatial Web Studio answers the first with CPU ray marching against JavaScript twins of the renderer's own distance functions — no GPU readback — and the second with a scene-wide bounding volume hierarchy (BVH) whose gains are graded in a deterministic census unit, offers per ray, rather than in milliseconds. Both share the renderer's camera model, so the object you pick is exactly the object you see.

Both questions belong to the Scene Document Model, which gives pure 3D elements (solids, lights, groups) DOM-like structure and hit-testing.

Screen space to world space, exactly

Converting a click into a world-space ray means inverting the same projection the renderer draws with, rather than approximating it with a second camera. The Studio's camera model is small and shared: the eye sits at view-space (0, 0, 1), the projection plane is the z = 0 view plane, and the plane's extents come from the tangent of the field-of-view half-angle. The WGSL compute shader marches primary rays through it, and the picker runs it in reverse — canvas CSS pixel to normalized device coordinates, NDC to a point on the z = 0 plane, then the inverse view matrix carries eye and plane point into world space, and the pick ray runs from one through the other.

The reason for one model is drift. Independently derived projections agree at screen centre and disagree at the edges, and those fractions of a pixel become a picker selecting the object next to the one rendered under the cursor. Because the unprojection is the exact algebraic inverse of the projection the shader uses, a computed hit lands on the surface the marcher shaded — by construction, not by tolerance.

Picking without a GPU readback

The Studio picks 3D objects by re-marching the pointer's ray on the CPU against JavaScript twins of the same signed distance functions (SDFs) the WGSL shader renders — it never reads pixels or object IDs back from the GPU. A readback scheme — render object IDs to a buffer, map it, read the pixel under the cursor — costs a GPU round trip and a frame of latency; the twin scheme is synchronous, works while the engine is paused, and intersects the exact rendered surface. Twins exist for four shapes — sphere, box, torus, capsule — and are exact: the ray is carried into object space through the record's inverse model matrix (rigid transforms preserve distance), then sphere-traced for at most 128 steps with an epsilon of 1e-3, out to 200 units.

Every other primitive type picks against a bounds proxy: a conservative bounding box, deliberately larger than the shape's silhouette, entering the same single nearest-hit comparison as the exact twins — never a second-class tier behind them. Two proxy details are measured, not stylistic. The box excludes glow: included, one scene lamp at glow 0.72 claimed a proxy 3.2× its real frame per axis and stole 122 sampled hit pixels from exact hits; excluded, 3 over-reach samples and zero steals (sampled-pixel comparison, flagship starter scene, 2026-08-17). And a proxy that contains the camera abstains instead of answering: the march starts at t = 0, so a box the eye sits inside would report the minimum distance and win every pixel — one cage-like frame around a scene would make picking unusable.

When several candidates are hit, an explicit arbitration stack decides — each rule ruled after a field failure, not assumed:

Nearest hit wins. Among all candidates — exact twins and bounds proxies in one comparison — the smallest ray distance t takes the event.
A group is never a candidate. An enclosing group's box face is always nearer than the primitive inside it, so a group would win by construction and swallow every click. Before the rule landed, BVH cull nodes claimed 30 of 41 sampled hit pixels (73%) on the real starter scene (hit-pixel sample, 2026-08-17).
Fitted-box retarget (editing only). Groups are retarget destinations instead: in the Studio's editing path, after a primitive is hit, the selection climbs to the outermost enclosing group whose box exactly fits it, within a 2e-3 per-axis tolerance — so clicking one part of an authored assembly selects the assembly, without groups ever competing on depth. The scene picker a published scene uses reports the record the ray hit.
One sanctioned override. The single object a user has explicitly activated under a transform gizmo wins any pick sweep whose ray hits it at all, however far back it sits — because depth ordering is the wrong arbitration for the one object the user has already declared they are manipulating.

The stack mirrors how a document treats containers. A group never steals its child's click — that is what "never a candidate" enforces — and the fitted-box retarget then climbs from the hit child to its enclosing container, the way event delegation targets a container from a click on one of its children.

One honest gap: triangle-mesh interiors have no ray-pick candidate. A triangle mesh's thousands of facets would cost a march each, so it picks as its root group through the editor's path — imported models and distance-field text are not triangle meshes and pick through bounds proxies like any other primitive. Cost stays bounded by design: full sweeps run only on pointer-down, a human-rate event, hover is a per-registration opt-in, and with nothing opted in a pointer move costs one comparison regardless of scene size.

A scene-wide BVH graded in offers-per-ray

The Studio's scene-wide BVH re-parents a scene's top-level records into hierarchy nodes so each rendering ray can skip whole subtrees, and its benefit is graded in a deterministic census unit — offers per ray — never in raw milliseconds.

Offers per ray — the number of candidate records each ray is offered for intersection testing, averaged over a frame's rays. It is the unit hierarchy gains are quoted in because marching cost scales with the product of rays dispatched and candidates offered per ray; a millisecond depends on resolution, machine, and thermal state, while the census is deterministic, reproducible, and pairs with an image-diff oracle proving the cheaper frame is the same frame.

The motivating census made the flat scan's cost legible: with no scene-level hierarchy, a 9-record demo scene offered 7.9 candidates per ray (88% of its records tested by every single ray), a 275-record showroom offered 54.0 (19.6%), and the 793-record starter offered only 28.5 (3.6%) — because its text meshes already sat behind a working triangle-level BVH. The demo scene also escaped 98.1% of its marches: every ray fully marched roughly 2.3 primitives it never hit, which is precisely the work a bounding hierarchy exists to skip (offers/ray census, 2026-08-14). Live frame timing independently showed cost linear in top-level record count; a hierarchy makes it logarithmic.

Three design decisions distinguish this BVH from a textbook one:

Structural dirtiness only. The tree rebuilds only on structural mutation — add, remove, re-parent, or a changed clip definition — and deliberately ignores the engine's general change counter. Animated scenes bump that counter every frame, which would hold the rebuild's 120 ms settle window open forever (field-caught 2026-08-15). Full rebuilds measured 12–51 ms on the development machine during the 2026-08-15 default-on certification (engine-mutation dominated), and are settle-windowed (120 ms) and throttled (800 ms).
Per-frame refit for poses. Animation never rebuilds topology. A per-frame refit pass recomputes node dimensions bottom-up from current poses with centres fixed — linear in the number of top-level members — so tight bounds stay valid while objects move.
A gate that declines, audibly. A surface-area-heuristic (SAH) gate builds the tree only where splitting is measured to beat staying flat. Where it cannot — typically a few overlapping, scene-spanning bounds — the planner declines and says so through an info-severity diagnostic carrying the rule, the consequence (the scene marches flat, correctly), and the reason. Declining is the mechanism working; the failure mode is declining silently.

Two hygiene rules complete the design. Bounds are conservative by rule: a too-small bound silently culls visible geometry — view-dependent holes a casual look misses, the worst failure mode a renderer has — so every per-type extent may err larger, never smaller. And BVH nodes are mechanism, not content: saved scenes and scene-state reads never see them; a teardown ledger restores the authored structure whenever the document is serialized.

Measured results

The BVH shipped enabled by default on 2026-08-15, on a four-scene offers-per-ray census where every arm carried an image-diff oracle counting changed pixels against the flat-scan render:

Scene	Offers/ray delta	Image oracle	Note
Gallery	−77.0%	1 px changed	The headline scene; live-verified below.
Add-primitives	−37.1%	0 px changed	Small scene, bit-identical image.
Showroom	−14.1%	9 px changed	275 records, mesh-heavy.
Starter (flagship)	a wash: 25.75 → 25.77	0 px changed	Honestly gated — the SAH gate declined at a knife-edge score of 6.7 vs 7; full marches still fell 5%.

Deterministic offers/ray census with per-scene image-diff oracles, 2026-08-15; certified against a full unit-test suite at 1,439 passed / 0 failed.

The census is the primary record, cross-checked live: when the tree auto-built on the gallery scene, the running story went from 25 to 48 fps on the development machine (live story session, same machine and viewport, 2026-08-15). The two numbers are kept separate on purpose: the census transfers across machines, the frame rate does not. And the starter row is published as deliberately as the gallery row — a culling structure that claims to win everywhere is hiding its gate; this one builds only where measured to win, and says so when it declines.

No ray-tracing hardware involved

None of the results above touch ray-tracing hardware, because none is reachable: WebGPU exposes no ray-tracing API surface in any browser today, and the Studio's engine requests zero optional device features and emits zero WGSL enable directives. The scene BVH and the triangle-level mesh BVH are ordinary engine records — group nodes with bounds, never document elements — traversed by a hand-written stack-based depth-first search inside the single compute kernel that renders the frame. Every census delta and frame-rate observation above was achieved on general-purpose shader cores — which is why the technique transfers: any WebGPU-capable device runs the same traversal, with no dependency on the intersection units only some GPU generations carry.