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, the renderer’s frustum-culling pass, and ray queries against triangle geometry all share this implementation.

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:

Words	Content
0–2	AABB min (x0, y0, z0) as float32
3–5	AABB max (x1, y1, z1) as float32
6	Parent index (uint32)
7	Child 1 index (or NULL_NODE for a leaf)
8	Child 2 / user-data index (overlapping; leaf nodes store user data here)
9	Height (uint32)

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

Method	Description
node_get_aabb(id, result)	Read the node’s AABB into a 6-element array
node_set_aabb(id, aabb)	Write AABB from a 6-element array
node_set_aabb_primitive(id, x0,y0,z0, x1,y1,z1)	Write AABB from six scalars (avoids array construction)
node_move_aabb(id, aabb)	Update AABB and refit bounds up the tree
node_get_user_data(id) / node_set_user_data(id, v)	Read/write the leaf payload (non-negative integer)
node_is_leaf(id)	Returns true when child1 === NULL_NODE
node_get_surface_area(id)	SAH cost metric for this node’s AABB
node_get_child1(id) / node_get_child2(id)	Child indices (or NULL_NODE)
node_get_parent(id)	Parent index
node_get_height(id)	Subtree height

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_intersects_frustum_degree classifies an AABB against a frustum:

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

const degree = aabb3_intersects_frustum_degree(
    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

BVHQueryIntersectsFrustum wraps this for BVH traversal — construct it with a frustum plane array and attach it to a tree query. The frustum plane array is extracted from a projection matrix via frustum_from_projection_matrix_array or frustum_matrix4_project.

aabb3_array_intersects_frustum_degree operates on a flat AABB array (stride 6) without constructing AABB3 objects, which is what the renderer’s bulk culling pass uses.

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.