Spatial acceleration

Most spatial acceleration in the engine runs through a single data structure: a binary Bounding Volume Hierarchy (BVH) backed by a flat ArrayBuffer. The physics broadphase (one tree for static geometry, one for movers), Shade’s static scene index and shadow-cascade culling, picking, terrain, the navmesh, and ray queries against triangle geometry all share this implementation.

Per-frame culling of drawable geometry is not on this list: under Shade that runs on the GPU over meshlet clusters, against a WGSL twin of the same frustum test.

The BVH class

BVH lives at @woosh/meep-engine/src/core/bvh2/bvh3/BVH.js.

Each node occupies exactly 10 words × 4 bytes = 40 bytes:

NULL_NODE is 0xFFFFFFFF (Uint32 max). A node is a leaf when child1 === NULL_NODE, and its user-data slot then holds an opaque integer payload (typically a triangle or body index).

For comparison, a V8 JS object takes roughly 80 bytes. The engine comment in the source notes this explicitly.

Creating and populating a tree

import { BVH } from "@woosh/meep-engine/src/core/bvh2/bvh3/BVH.js";

const bvh = new BVH();

// Allocate a leaf, set its bounds and payload, then insert it.
const node = bvh.allocate_node();
bvh.node_set_aabb(node, [x0, y0, z0, x1, y1, z1]);
bvh.node_set_user_data(node, myId);
bvh.insert_leaf(node);

// Remove later; leaf is not released automatically.
bvh.remove_leaf(node);
bvh.release_node(node);

allocate_node pulls from a free-list first, then grows the backing buffer (by 1.2× or at least 64 nodes). No allocation occurs during insert_leaf or remove_leaf unless the buffer needs to grow.

release_all() resets the tree to empty in O(1) - useful for bulk rebuilds.

trim() shrinks the backing buffer to the exact occupied size.

Node accessors

Balancing strategy

On every insertion, insert_leaf calls bubble_up_update up the path to the root. Each internal node along the path is passed through balance_rotate - an SAH-reducing rotation adapted from Box2D v3 / Kensler 2008. For each internal node A with children B and C, the algorithm considers four child↔grandchild swaps and applies the one with the largest positive reduction in total surface area. This keeps the tree near the SAH optimum without a separate offline optimisation pass. The alternative balance_height (pure height-AVL) is retained in the source for reference.

Bulk Morton-sorted build

For static or semi-static triangle meshes, ebvh_build_for_geometry_morton builds a complete BVH in one pass using Morton-code sorting:

import { ebvh_build_for_geometry_morton } from
  "@woosh/meep-engine/src/core/bvh2/bvh3/ebvh_build_for_geometry_morton.js";

// indices: flat triangle index buffer (length = triangleCount * 3)
// positions: flat position buffer (x,y,z per vertex)
ebvh_build_for_geometry_morton(bvh, indices, positions);

The function:

1. Computes a 30-bit Morton code per triangle centroid (v3_morton_encode_normalized), normalised to the mesh’s own AABB.
2. Sorts triangle order by Morton code (radix/quicksort).
3. Calls allocate_linear to size the tree exactly (no per-node allocation overhead).
4. Assigns leaves in Morton order and builds the hierarchy bottom-up.

An optional quality parameter triggers additional SAH optimisation passes beyond the Morton sort.

ebvh_build_for_geometry_incremental is the alternative for dynamic geometry: it inserts leaves one at a time through the normal insert_leaf path, which is slower to build but supports per-frame updates without a full rebuild.

Morton encoding

v3_morton_encode_normalized(x, y, z) maps three floats in [0, 1] to a 30-bit Morton code (10 bits per axis). v3_morton_encode_bounded handles arbitrary world-space bounds. These codes are used both during BVH builds and in physics broad-phase sorting.

import { v3_morton_encode_normalized } from
  "@woosh/meep-engine/src/core/geom/3d/morton/v3_morton_encode_normalized.js";

const code = v3_morton_encode_normalized(0.25, 0.5, 0.75);

Ray intersection queries

AABB vs ray

aabb3_intersects_ray tests a single AABB against an infinite ray. It uses the separating-axis formulation from Graphics Gems with branchless projections:

import { aabb3_intersects_ray } from
  "@woosh/meep-engine/src/core/geom/3d/aabb/aabb3_intersects_ray.js";

const hit = aabb3_intersects_ray(
    x0, y0, z0, x1, y1, z1,       // AABB
    ox, oy, oz,                    // ray origin
    dx, dy, dz                     // ray direction (need not be normalised)
);

aabb3_intersects_ray_segment and aabb3_near_distance_to_intersection_ray_segment provide bounded-segment and nearest-hit-distance variants.

BVH leaf traversal

bvh_query_leaves_ray traverses the tree and collects all leaf node indices whose AABBs the ray intersects:

import { bvh_query_leaves_ray } from
  "@woosh/meep-engine/src/core/bvh2/bvh3/query/bvh_query_leaves_ray.js";

const candidates = [];
const count = bvh_query_leaves_ray(
    bvh, bvh.root,
    candidates, 0,
    ox, oy, oz,
    dx, dy, dz
);
// candidates[0..count-1] are leaf node ids

Nearest triangle hit

ebvh_geometry_query_nearest_triangle_ray combines BVH traversal with per-triangle Möller–Trumbore intersection and early-out pruning by squared AABB distance:

import { ebvh_geometry_query_nearest_triangle_ray } from
  "@woosh/meep-engine/src/core/bvh2/bvh3/ebvh_geometry_query_nearest_triangle_ray.js";

const output = [0, 0, 0, 0];
// ray = [ox, oy, oz, dx, dy, dz]
const hit = ebvh_geometry_query_nearest_triangle_ray(
    output, 0,
    bvh, bvh.root,
    ray, minDist, maxDist,
    indexBuffer, positionBuffer
);
if (hit) {
    // output[0] = triangle index
    // output[1] = barycentric u
    // output[2] = barycentric v
    // output[3] = distance t
}

The traversal skips any subtree whose AABB squared distance from the ray origin exceeds the current best t, so it finds the nearest hit without examining all candidates.

Frustum classification

Frustums are represented as six planes in a flat array of stride 4 (nx, ny, nz, offset per plane, 24 floats total).

aabb3_classify_against_frustum classifies an AABB against a frustum:

import { aabb3_classify_against_frustum } from
  "@woosh/meep-engine/src/core/geom/3d/aabb/aabb3_classify_against_frustum.js";

const degree = aabb3_classify_against_frustum(
    x0, y0, z0, x1, y1, z1,
    frustumPlanes   // Float32Array of 24 values
);
// 0 = fully outside
// 1 = partially inside (frustum plane intersects the AABB)
// 2 = fully inside

aabb3_classify_against_frustum_array is the same test over a flat AABB array (stride 6), without constructing AABB3 objects. aabb3_intersects_frustum_degree and aabb3_array_intersects_frustum_degree are their deprecated aliases. Shade’s meshlet-filtering compute pass runs a WGSL twin of the same classification on the GPU.

Extract the frustum plane array from a projection matrix with frustum_from_projection_matrix_array(frustum_planes, m4) - which is how the directional-light shadow map culls each cascade. (frustum_matrix4_project is a deprecated alias of frustum3_matrix4_project.)

BVHQueryIntersectsFrustum.from(frustum) is the BVHQuery wrapper for traversal; it evaluates each node’s AABB against the plane set with aabb3_array_intersects_clipping_volume_array, so it accepts a general clipping volume rather than only a six-plane frustum.

Visualising a tree

BVHGeometry(bvh) turns every leaf box of a tree into drawable triangle geometry - twelve triangles and eight vertices per box, with no vertex shared between boxes. Internal nodes are descended rather than drawn, so what comes out is the set of boxes the tree actually bounds things with.

import BVHGeometry from "@woosh/meep-engine/src/core/bvh2/visual/BVHGeometry.js";

const geometry = BVHGeometry(bvh);   // a Shade Geometry, named "BVH"

Two things to note: it is a default export, and it returns a Shade Geometry (shade/renderer/geometry/Geometry.js) with position and index attributes and its bounding shapes already computed - hand it to meshlet_geometry_build_from_geometry and a ShadedGeometry like any other authored geometry. Its input is the flat BVH above.

Where to go next

• Spatial queries - the physics engine’s raycasts and shape casts build on the BVH and AABB intersection primitives documented here.
• Math & geometry - the vector and matrix primitives the BVH internals use.