@zakkster/lite-bvh

Zero-GC dynamic Bounding Volume Hierarchy for 2D. A flat Structure-of-Arrays AABB tree with O(1) free-list allocation, Surface Area Heuristic insertion, and an iterative query that writes hits into a caller-provided buffer. No allocations after construction — not in insertLeaf, not in query, not in the fast-path updateLeaf. A Box2D-style dynamic tree, transplanted to plain JavaScript and Int32Array/Float32Array.

import { DynamicBVH2D } from '@zakkster/lite-bvh';

const tree = new DynamicBVH2D(4096);
const tight = new Float32Array(4);   // scratch — reused every frame
const hits  = new Int32Array(256);

// Insert each entity once at spawn time:
const nodeId = tree.insertLeaf(entityAABB, entityId);

// Per frame, per moving entity — fast path is zero-cost when no rebuild is needed:
setBoundsInto(tight, entity);
entity.nodeId = tree.updateLeaf(entity.nodeId, tight, MARGIN);

// Per frame, per query (viewport / mouse pick / explosion radius):
const n = tree.query(viewportAABB, hits);
for (let i = 0; i < n; i++) renderEntity(hits[i]);

Contents

• Why · Install · Quick start
• How it works
• The fat-bounds trick (why margin matters)
• API reference
• Sizing & memory
• Edge cases & guarantees
• Testing
• Limitations & roadmap
• License

Why

You have a few thousand moving things — sprites, particles, bullets, tiles, hit-tested overlay layers — and every frame you need to answer questions like:

• "Which entities overlap this viewport rectangle?"
• "Which entities are near the cursor?"
• "Which entities should I test for collision against this swept AABB?"

Naively iterating all N entities is O(N) per query. A flat spatial grid is great until your entities cluster or sizes vary widely. An octree allocates a node object per cell. A class-based BVH allocates a node object per insert.

@zakkster/lite-bvh allocates exactly five typed arrays at construction and never again. Inserts, queries, updates, removes — all operate on indices into those pre-allocated buffers. The free-list reuses node slots in O(1) so a steady-state simulation has zero allocator pressure forever.

It's what you'd write if you read Box2D's b2_dynamicTree.cpp and re-translated the techniques into JS:

• Flat SoA layout — five contiguous arrays, one slot per node, indexed by integer node id. No { left, right, bbox } object graph; the cache loves this.
• Surface Area Heuristic — inserts descend along the cheapest cost path, producing balanced trees even for irregular workloads.
• Fat-bounds + dirty-check update — moving entities take the O(1) fast path 90 %+ of the time; only when an object breaches its fat bounds does the tree restructure.
• Iterative query — explicit stack, no recursion, no closures, no per-hit object construction. Hits are integer ids written into your buffer.

What this is not

• Not a physics engine. No contact resolution, no impulses, no shape primitives beyond AABBs. Use this as the broadphase under your own physics.
• Not a raycaster. Only AABB-overlap queries today. Raycast/segment queries are a clean addition (see roadmap).
• Not a 3D BVH. This is 2D only. The savings on each node (4 floats vs 6) are real for the use cases this is built for.

Install

npm i @zakkster/lite-bvh

ESM only. Zero runtime dependencies. Pairs with @zakkster/lite-aabb (same flat-array AABB format) but does not depend on it.

import { DynamicBVH2D } from '@zakkster/lite-bvh';

Quick start

import { DynamicBVH2D } from '@zakkster/lite-bvh';
import { aabb2 } from '@zakkster/lite-aabb';     // optional but convenient

const MARGIN = 4;                     // world-units of fat to apply on insert/move
const tree = new DynamicBVH2D(4096);  // ~32 KB of buffers, room for ~2000 leaves

// ---- Spawn ----
const entities = new Map();           // entityId -> { x, y, w, h, nodeId }
function spawn(id, x, y, w, h) {
    const fat = aabb2.create();
    aabb2.set(fat, x - MARGIN, y - MARGIN, x + w + MARGIN, y + h + MARGIN);
    const nodeId = tree.insertLeaf(fat, id);
    entities.set(id, { x, y, w, h, nodeId });
}

// ---- Move ----
const tight = new Float32Array(4);    // reused across every entity, every frame
function move(id, newX, newY) {
    const e = entities.get(id);
    e.x = newX; e.y = newY;
    tight[0] = newX;       tight[1] = newY;
    tight[2] = newX + e.w; tight[3] = newY + e.h;
    e.nodeId = tree.updateLeaf(e.nodeId, tight, MARGIN);
}

// ---- Query ----
const hits = new Int32Array(256);     // sized for your worst-case batch
function visibleInViewport(viewportAABB) {
    const n = tree.query(viewportAABB, hits);
    return hits.subarray(0, n);       // view, not a copy
}

// ---- Despawn ----
function despawn(id) {
    const e = entities.get(id);
    tree.removeLeaf(e.nodeId);
    entities.delete(id);
}

How it works

Memory layout

Five typed arrays, one slot per node, all allocated up front.

flowchart TB
    subgraph SoA["Pre-allocated buffers — one slot per node id"]
        direction TB
        BB["bboxes : Float32Array(maxNodes × 4)<br/>node 0: [minX, minY, maxX, maxY]<br/>node 1: [minX, minY, maxX, maxY]<br/>node 2: …"]
        PA["parents : Int32Array(maxNodes)<br/>node 0: parent id (-1 for root)<br/>node 1: parent id<br/>…"]
        CH["children : Int32Array(maxNodes × 2)<br/>node 0: [leftId, rightId] (-1 for leaves)<br/>node 1: [leftId, rightId]<br/>…"]
        HT["heights : Int32Array(maxNodes)<br/>subtree height; 0 for leaves"]
        UD["userData : Int32Array(maxNodes)<br/>ECS entity id on leaves; -1 internal"]
    end
    subgraph FL["Free-list allocator"]
        NF["nextFree : Int32Array(maxNodes)<br/>chains unused slots"]
        FH["freeHead : int<br/>head of the chain (-1 = full)"]
    end
    SoA -.-> FL

Every operation either looks up a slot by integer id (single typed-array load) or writes through one (single typed-array store). There's no method dispatch, no property access through this into a Map or Object — the JIT sees plain indexed array math.

Insert: Surface Area Heuristic descent

Inserting a leaf has to pick a sibling node — an existing node that the new leaf will share a parent with. Picking randomly produces deep, unbalanced trees that destroy query performance. Picking optimally is exponential. SAH is the principled heuristic: descend toward the child whose change in surface area (perimeter, in 2D) would be smallest, plus an inheritance-cost term that accounts for the bounding box growth that propagates up to the root.

flowchart TD
    Start[New leaf with bbox L]
    Root[Begin at root]
    Eval{At current node:<br/>compare cost of<br/>stopping here vs<br/>descending L or R}
    StopHere["Stop. This node is sibling."]
    GoL[Descend to left child]
    GoR[Descend to right child]
    Make[Create new internal parent.<br/>Make leaf + sibling its children.<br/>Refit AABBs up to root.]
    Start --> Root --> Eval
    Eval -->|stop is cheapest| StopHere --> Make
    Eval -->|left is cheapest| GoL --> Eval
    Eval -->|right is cheapest| GoR --> Eval

The cost function compares the perimeter of the merged box at each step, plus an inheritance cost for box growth that propagates to ancestors. This produces the balanced, low-area trees that make queries cheap.

Query: iterative DFS over the tree

No recursion — recursion in V8 creates a stack frame per call, and for trees of depth 20+ that's measurable cost on a 60 fps budget. The query reuses a single Int32Array stack across every call.

sequenceDiagram
    participant App
    participant Q as query(qBox, out)
    participant Tree

    App->>Q: query(queryAABB, outBuffer)
    Note over Q: push root onto stack
    loop while stack not empty
        Q->>Tree: pop node id, read its bbox
        alt bbox overlaps queryAABB
            alt node is a leaf
                Q->>App: write userData into out
                alt out full
                    Q-->>App: return hit count (early stop)
                end
            else node is internal
                Q->>Tree: push left and right children
            end
        end
    end
    Q-->>App: return hit count

The stack auto-grows on pathological tree depths (it doubles when full), but for any practical tree it never reallocates after the first frame.

The fat-bounds trick (why margin matters)

The big insight that makes a dynamic AABB tree fast under motion: every leaf stores a "fat" AABB, slightly larger than the entity's actual bounds. As long as the tight bounds stay inside the fat bounds, the tree topology doesn't need to change at all — the leaf's bbox in the tree is still valid as an over-approximation. Only when an entity moves outside its fat bounds does the leaf get removed, re-fattened, and re-inserted.

flowchart LR
    subgraph F[updateLeaf fast path]
        F1[Tight bounds still<br/>inside fat bounds?]
        F2[Done. O(1)<br/>Tree unchanged.]
        F1 -->|YES| F2
    end
    subgraph S[updateLeaf slow path]
        S1[Tight bounds<br/>breached fat bounds]
        S2[removeLeaf]
        S3[fatten new bounds by margin]
        S4[insertLeaf]
        S1 --> S2 --> S3 --> S4
    end

For a typical particle / sprite workload with a sensible margin, the fast path hits >95 % of frames per entity. Only when something teleports or starts moving fast does the tree restructure.

Picking a margin

| Margin | Behavior | |---|---| | Too small (≈ 0) | Almost every move triggers a re-insert. The tree stays tight, but updates are slow and the query results contain only the strictly-overlapping leaves. | | Too large (≫ entity size) | Re-inserts are rare and cheap, but queries return many false-positive hits — the caller has to filter them out with a second tight-bounds check. | | Sweet spot (≈ 1–4× one frame's expected movement) | ~95 % fast-path updates, modest query bloat. Tune by profiling. |

margin is the single most important parameter you'll tune. A common rule of thumb: set it to expected velocity × 2 frames in world units.

API reference

new DynamicBVH2D(maxNodes)

| Arg | Type | Description | |---|---|---| | maxNodes | number | Hard cap on total nodes (leaves + internal). Sized for the lifetime of the tree. |

A tree holding N leaves uses at most 2N - 1 total nodes (when fully populated). Rule of thumb: maxNodes = 4 × expectedEntities gives plenty of headroom.

Instance members

| Member | Type | Description | |---|---|---| | maxNodes | number | As constructed. | | nodeCount | number | Live nodes (leaves + internal). Useful for telemetry. | | root | number | Root node id, or -1 if empty. | | bboxes parents children heights userData | TypedArray | The SoA backing arrays. Read-only in practice; exposed for debug visualization and unit tests. |

Methods

| Method | Returns | Description | |---|---|---| | insertLeaf(leafAABB, data) | number (node id) | Inserts a leaf. Store the returned id. Throws when nodeCount === maxNodes. | | removeLeaf(leaf) | void | Removes a leaf, heals the gap, returns nodes to the free list. | | updateLeaf(leaf, newAABB, margin) | number (node id) | Fast path: returns leaf unchanged if still contained. Slow path: removes, fattens by margin, re-inserts; returns a (possibly new) id. Always reassign your stored handle from the return value. | | query(queryAABB, outBuffer) | number (hit count) | Writes intersecting leaves' userData into outBuffer. Stops early when the buffer fills. |

Conventions

• AABB format: Float32Array of length 4, [minX, minY, maxX, maxY]. Identical to @zakkster/lite-aabb format.
• userData: any int32. Negative values are legal but -1 is reserved internally for "no data" on internal nodes — don't use -1 as a leaf id if you plan to read raw userData[id].
• outBuffer: caller-owned Int32Array. The library never holds a reference past the call.

Sizing & memory

Each node consumes:

| Field | Bytes | |---|---:| | bboxes slice | 16 | | parents slice | 4 | | children slice | 8 | | heights slice | 4 | | userData slice | 4 | | nextFree slice | 4 | | Total | 40 bytes / node |

A DynamicBVH2D(4096) is therefore ~160 KB of backing buffers, comfortably below the Twitch Extension 1 MB bundle cap and trivial for any other deployment. A million-leaf tree is ~80 MB — still feasible, but at that scale you should look at chunking / paging strategies above the BVH.

Edge cases & guarantees

• Capacity exhaustion throws synchronously at insertLeaf — at the boundary, never partway through. The tree is left in a valid state.
• updateLeaf's fast path is truly O(1). Four typed-array reads and four <=/>= comparisons. Nothing else.
• Removing the root transitions the tree to empty cleanly (root = -1, nodeCount = 0).
• Removing one of two leaves promotes the surviving sibling directly to the root, freeing the internal parent.
• query is reentrant-safe within a single thread — the stack is per-instance state but each call reads it from stackPtr = 0 to stackPtr = 0, so back-to-back queries don't interfere. Don't share an instance across Workers.
• Float32 precision (~7 decimal digits) is fine for typical world bounds; for million-unit scenes consider chunking or swapping the type.
• No tree rebalancing yet. The SAH descent produces well-balanced trees in steady-state for typical game workloads. Pathological insertion sequences could still produce a tree that's deeper than ideal; see roadmap.

Testing

npm test
# or: node --expose-gc Bvh.test.js

Runs 24 deterministic assertions covering:

| Group | What's tested | |---|---| | Construction | SoA sizes, free-list chain, initial state | | Insert | single leaf, internal parent creation, distinct ids, capacity throw | | Query | empty tree, single leaf, miss, multiple hits, enclosing query, touching edges, early stop on full buffer | | Remove | only leaf, sibling promotion, unfindability, capacity reusability | | Update | fast path (same id), slow path (new id at new position), user-data preservation, margin correctness | | Stress | 500-leaf scatter + exhaustive queries + bulk removal + 10-frame update cycling | | Zero-allocation guarantee | 100 000 mixed query+update ops → heap growth < 512 KB under --expose-gc |

A clean run ends with 24 passed, 0 failed and exit code 0.

Limitations & roadmap

This is a v1 release. Planned additions, in rough order:

| Feature | Why | Difficulty | |---|---|---| | Tree rotations during _refit | Box2D-style left/right rotations to keep height bounded even under adversarial insert orders. The // TODO is already marked in Bvh.js. | Medium | | raycast(p0, p1, callback) | Returns hits along a segment in near-order. Common need for vision/laser/projectile checks. | Medium | | queryPoint(x, y, outBuffer) | Specialized fast path for picking — saves the AABB construction. | Easy | | closestPoint(p, outBuffer) | Nearest-leaf to a point with optional max-distance cap. | Hard |

PRs welcome. If you adopt this for a shipping product and have a feature on the list above, get in touch.

License

MIT © Zahary Shinikchiev