@zakkster/lite-overlap

Zero-GC persistent overlap events over a dynamic BVH (2D). Overlap is not a set -- it is a set of transitions. This turns "who overlaps now" into "who just started (enter), who is still touching (stay), who just left (exit)," and finds every pair exactly once in a single tree self-traversal. No allocations after construction, on any frame path.

import { createOverlap, narrow } from '@zakkster/lite-overlap';
import { DynamicBVH2D } from '@zakkster/lite-bvh';

const tree = new DynamicBVH2D(4096);
const ov   = createOverlap({ maxPairs: 8192 });

const enterA = new Int32Array(1024), enterB = new Int32Array(1024);
const exitA  = new Int32Array(1024), exitB  = new Int32Array(1024);

// Per frame:
ov.begin();
ov.collectPairs(tree);            // every overlapping pair, found once
ov.end();

const nEnter = ov.drainEnter(enterA, enterB);
for (let k = 0; k < nEnter; k++) onOverlapStart(enterA[k], enterB[k]);

const nExit = ov.drainExit(exitA, exitB);
for (let k = 0; k < nExit; k++) onOverlapEnd(exitA[k], exitB[k]);

Contents

• Why - Install - The frame cycle
• Two ways to feed a frame
• Fat vs tight: the one thing to get right
• Layers and filters
• Swept detection
• How it works
• API - Guarantees - License

Why

A spatial index answers "what overlaps box X, right now." Game logic needs two things it cannot give:

1. Transitions. Fire the pickup once when the player touches it; drop aggro when they leave. That is a frame-over-frame delta, and every JS implementation reaches for new Set(`${a},${b}`) -- 7.8 KB/frame at 1,543 pairs, 0.46 MB/s of string garbage at 60 fps, measured. In a library family whose whole identity is that it does not allocate, that is the number to erase.

2. All pairs, found once. "Everything overlapping everything" by looping query() per entity finds every pair twice and rebuilds a query box per entity -- 3,086 directed reports for 1,543 real pairs at N = 2000. A single tree descent finds each pair once and rebuilds nothing.

lite-overlap is the layer between the index and the logic, and it does both with zero allocation per frame. It is not a solver -- no contact normals, no MTV, no impulses. The answer to "did these overlap this frame" is a boolean and a transition, not a force.

Install

npm install @zakkster/lite-overlap

Pair it with @zakkster/lite-bvh for the tree and @zakkster/lite-aabb for the box math. All three share one FORMAT_VERSION buffer contract and none depends on the others at runtime -- format agreement only. ESM only; Node >= 18.

The frame cycle

begin()  ->  report pairs  ->  end()  ->  drainEnter / drainExit

begin() flips a 1-bit tag so every stored pair is now "stale." Each reported pair re-stamps its slot as "touched this frame." end() scans the table once: every slot still stale was not touched, so it exited -- staged and removed. What you drain after end() is the delta, and it holds until the next begin().

add(a, b) is order-invariant ((a,b) and (b,a) are one pair), idempotent within a frame (report the same pair twice, get one enter), and rejects a === b.

Two ways to feed a frame

Both feed the same table, so you can mix them in one frame for one unified delta:

// A) Traverse a BVH -- all pairs, one descent:
ov.begin();
ov.collectPairs(tree);
ov.end();

// B) Report pairs by hand -- from a non-BVH index, or extra trigger volumes:
ov.begin();
ov.collectPairs(tree);          // tree pairs...
ov.add(playerId, zoneId);       // ...plus a hand-fed pair, same frame
ov.end();

collectPairs owns no frame boundary -- you call begin() and end(). That is what lets the two sources share one delta.

Fat vs tight: the one thing to get right

A BVH keeps each box fattened (a margin, so small moves need no rebuild). So collectPairs reports the fat pairs the tree holds: a conservative broadphase. It never misses a real overlap -- but it can report a pair whose tight boxes are a hair apart.

If you act on geometry from the raw pair -- deal damage, grant a pickup -- gate it with a tight recheck first:

// tightA / tightB are YOUR tight boxes for a and b (Float32Array(4)),
// the ones you had before you fattened them into the tree.
if (narrow(tightA, tightB)) {
    dealDamage(a, b);
}

narrow takes your boxes, not the tree, on purpose: the tree does not store tight boxes -- only you have them. It is a pure [minX, minY, maxX, maxY] overlap test, zero allocation, zero dependency.

Layers and filters

A real trigger system wants "player against pickups, not pickups against each other." Put entities on layers and switch which layers interact -- the descent skips filtered pairs as it goes, so you never pay for a pair you then throw away:

const PLAYER = 0, PICKUP = 1, WALL = 2;
ov.setLayer(playerId, PLAYER);
ov.setLayer(coinId, PICKUP);
ov.setInteract(PICKUP, PICKUP, false);   // pickups ignore each other
ov.setInteract(PLAYER, WALL, false);     // walls are for something else

ov.setEnabled(deadEntityId, false);      // generates no pairs; its live pairs exit

ov.begin();
ov.collectPairs(tree);                   // filtered during the descent
ov.end();

Three properties make it safe to lean on:

• Results-preserving. Filtering changes cost, never results: the filtered set is exactly the unfiltered set with the disabled pairs removed. It cannot invent or reorder a pair.
• Rotation-proof. State is keyed by userData (the entity id you assigned), never by a tree node id -- so it stays correct when the BVH rotates to rebalance. A per-node cached "subtree layer mask" would silently go stale on the next refit and drop real collisions; this package deliberately keeps none. (decisions/0003-filters.md.)
• Exits fire. Disable an entity, or turn off a layer interaction, and the pairs that should end do -- each fires an exit exactly once, on that frame, through the same mark-sweep everything else uses. No phantom live pairs, no "my exit never fired."

The 32x32 interaction matrix is symmetric by construction (setInteract(a, b, …) also sets (b, a)) and starts all-on, so an instance you never call these on behaves exactly as it did before layers existed. Filter state is sampled inside collectPairs -- set it before the frame's collect. maxEntityId is an optional constructor cap for the layer arrays; omit it and they grow on demand.

Swept detection: a trigger you can shoot through is a bug

A projectile moving faster than its own width is in front of a thin trigger at frame N and behind it at frame N+1. It overlapped at no sampled instant, so discrete detection never fires -- the projectile tunnels straight through. This is the bug every discrete-sampling trigger system has, and it is a broadphase question, not a physics one.

addSwept (by hand) and collectSweptPairs (bulk, over a BVH) test the swept volume -- the AABB union(prev, curr) -- instead of the instantaneous box:

import { createOverlap } from '@zakkster/lite-overlap';

const ov = createOverlap({ maxPairs: 4096 });

ov.begin();
// projectile's box last frame vs this frame; the wall is static (prev === curr)
ov.addSwept(bulletId, bulletPrev, bulletCurr, wallId, wallBox, wallBox);
ov.end();
ov.drainEnter(outA, outB);   // the crossing fires ENTER, like any other pair

The committed tunneling fixture -- a 6-wide projectile crossing a wall in one frame (test/OverlapSwept.test.mjs, decision S6):

| projectile speed (px/frame) | wall thickness (px) | discrete | swept | | ---: | ---: | :---: | :---: | | 40 | 60 | ✅ hit | ✅ hit | | 120 | 8 | ❌ tunnels | ✅ hit | | 400 | 6 | ❌ tunnels | ✅ hit | | 1500 | 2 | ❌ tunnels | ✅ hit |

Three properties, all tested:

• Superset, never a loss. The swept set always contains the discrete set (the union contains curr); with zero motion (prev === curr) it is byte-identical to collectPairs.
• Enter fires through the ordinary channel. A pass-through fires enter on the crossing frame and exit the next -- the same drainEnter / drainExit you already read. There is no separate event to wire, so a caller cannot forget it and silently miss a hit.
• Conservative, not exact. The axis-aligned union over-reports diagonal motion (it is the bounding rectangle of a thin diagonal sweep). Never a missed pair; gate geometry with your own tight boxes via narrow or the exact swept recheck sweptOverlapExact (below), as after any broadphase.

collectSweptPairs(tree, prevPacked, currPacked, count) has one contract: build the tree's leaf boxes to bound the motion -- fatten(union(prev, curr)) -- or the descent prunes the tunneling pair before the tight-union refinement can see it. The packed prev/curr boxes are indexed by userData; a leaf id >= count fails closed.

The exact recheck: sweptOverlapExact

The union over-reports on diagonal motion, and a bench measured how much: on fast diagonal motion it reports up to ~55% more pairs than actually sweep through each other (two entities crossing opposite corners of a shared bounding rectangle, their thin diagonal ribbons never meeting). When that matters, sweptOverlapExact(prevA, currA, prevB, currB) tests the true swept ribbons -- the convex hull of each box's eight swept corners -- instead of their unions:

import { createOverlap, sweptOverlapExact } from '@zakkster/lite-overlap';

// collectSweptPairs / sweptOverlap flagged this pair with the cheap union.
// Recheck the exact ribbons before you act on it -- like narrow, but swept:
if (sweptOverlapExact(aPrev, aCurr, bPrev, bCurr)) {
    // their swept ribbons genuinely overlap
}

It is the exact analog of narrow: a strict subset of sweptOverlap (it never reports a pair the union would not), equal to sweptOverlap under axis-aligned motion, and reduces to narrow under zero motion. It costs ~4-5x the union per pair (a bench decided this), so it ships opt-in -- the union stays the never-miss broadphase default in collectSweptPairs, and you call sweptOverlapExact by hand on the pairs you care about. Like narrow, it fails closed on any non-finite or malformed box. Zero allocation, no import. Design of record: decisions/0005-swept-exact.md.

How it works

• Pair identity is two parallel Int32Arrays, never one packed number. Two int32 ids are 62 bits; a JS number is exact only to 2^53, so a packed key either caps ids at ~2^26 or loses precision silently. Pairs are stored canonically (a < b), hashed from both ids with Math.imul (stays int32).
• The table is open-addressed over typed arrays, power-of-two capacity, bitmask index, backward-shift deletion (not tombstones -- a trigger set churns every frame, the one load tombstones degrade under).
• Exit detection is a 1-bit alternating tag, not a wide epoch counter. Because a pair is removed the moment it exits, no slot survives a frame untouched, so the tag cannot wrap into a false "current." No 414-day wraparound bug.
• collectPairs descends node-pairs on a fixed Int32Array stack. It recurses a node against itself (splitting into both children and the cross term), descends the taller node of a cross-pair, and prunes on a box miss -- so each pair is found once. The stack is sized from the tree's maxNodes; an impossible overflow throws fail-closed rather than allocating mid-frame.
• Capacity is fixed and every overflow is atomic. A pair past maxPairs throws before mutating -- the table is left unchanged and usable, and the message names the remedy. Size it from stats().highWaterMark.
• collectSweptPairs shares that one descent. It is collectPairs with a tight-union(prev, curr) recheck spliced in at each leaf-leaf candidate before add -- so the tunneling fix inherits the same zero-alloc stack, the same fail-closed corruption checks, and the same 94-vs-1,543 correctness proof, and feeds the identical lifecycle. The swept unions are computed in registers; the union is inlined, so there is still no runtime dependency on @zakkster/lite-aabb.

API

| Member | What it does | | --- | --- | | createOverlap({ maxPairs, maxEntityId? }) | Allocate an instance and its table. The only allocating call. maxEntityId optionally caps the filter arrays. | | begin() | Open a frame. O(1). | | add(a, b) | Report a pair by hand. Order-invariant, idempotent, throws atomically past maxPairs. Unfiltered (the raw door). | | collectPairs(tree) | Report every overlapping pair in a BVH, once. Fat-bound; filtered during the descent; feeds add. | | collectSweptPairs(tree, prevPacked, currPacked, count) | Swept broadphase: catches tunneling. Tree leaves must bound the motion; refines each pair with the tight union(prev, curr). Superset of collectPairs. | | addSwept(a, prevA, currA, b, prevB, currB) | Report a swept pair by hand -- records it iff the two swept volumes overlap. The oracle for collectSweptPairs. Unfiltered. | | end() | Close the frame; emit and remove exits. O(capacity). | | setLayer(id, layer) | Put entity id on a layer [0, 31] (default 0). Keyed by userData; cold path. | | setInteract(a, b, on) | Turn the layer pair (a, b) on/off. Symmetric; all-on by default. Cold path. | | setEnabled(id, on) | Enable/disable an entity. Disabled = no pairs; its live pairs exit once. Cold path. | | drainEnter(outA, outB) / drainExit(outA, outB) | Copy this frame's enter / exit ids into your buffers; return the count. | | pairCount() / stayCount() | Live pairs / live pairs that did not enter this frame. | | stats() | pairCount, stayCount, capacity, loadFactor, probeHighWater, highWaterMark, stackHighWater, epoch. Cold path. | | clear() | Empty the table without reallocating and without emitting exits. | | narrow(boxA, boxB) | Tight AABB overlap on two of your boxes. Pure boolean, zero alloc. | | sweptOverlap(prevA, currA, prevB, currB) | The swept analog of narrow: do the two swept volumes (unions) overlap? Pure boolean, zero alloc. | | sweptOverlapExact(prevA, currA, prevB, currB) | The exact opt-in swept recheck: do the true swept ribbons (hulls) overlap? A subset of sweptOverlap, ~4-5x its cost. Pure boolean, zero alloc. | | VERSION / FORMAT_VERSION | Package semver / shared buffer-contract version (= 1). |

Full types and per-method contracts are in Overlap.d.ts.

Guarantees

• Zero runtime dependencies. Single ESM file, sideEffects: false.
• Zero allocation on every frame path -- add, collectPairs, collectSweptPairs, end, the drains, narrow, sweptOverlap, sweptOverlapExact. Proven by a node --expose-gc torture gate at maxMajor: 0 and maxArrayBuffersGrowth: 0 (including 200k swept collects), with a Set<string> control that must fail the gate, so the gate is falsifiable rather than decorative.
• Fail closed on every unverified state -- capacity exhaustion, traversal stack overflow, and a corrupt tree (leaf signals that disagree) each throw with a remedy in the message, never a silent mis-report. null is not zero.
• Correctness pinned against an oracle -- the traversal's pair set is asserted identical to a brute-force O(N^2) check and to the caller-fed query() path over a seeded fuzz corpus, including degenerate trees (empty, single leaf, all identical, all at one point, single row).
• Filtering changes cost, not results -- the filtered set is asserted equal to the unfiltered set post-filtered in JS over the corpus, and equal to the brute filtered oracle every frame through rotation-provoking motion (so no cached node-keyed mask can go stale). Disabling an entity or a layer fires each affected exit exactly once. Filtering active keeps the alloc gate at zero.
• Swept catches what discrete misses, and never loses a pair -- the committed tunneling fixture proves discrete detection misses every fast/thin row and swept catches it; the swept set is asserted a superset of the discrete set, and byte-identical to it at zero motion. A world-scale ULP check (finding A-01) pins the swept union strictly larger than its endpoints at coordinates up to 1e7.

License

MIT (c) 2026 Zahary Shinikchiev. See LICENSE.