Octree broadphase: depth pruning drops real collisions, and midpoint items are misfiled to the root

[obiot]

Two defects in the Octree broadphase, found while validating the Camera3d + Octree + SAT stack ahead of the 2.5D platformer example (#1476). Both affect Camera3d games only — a 2D game's broadphase is a QuadTree and never constructs an Octree.

Filed for the record; the fix is in #1580.

1. retrieve() pruned on depth and silently dropped real collisions

retrieve() descended only into the octant the query item classified into. But every consumer of it decides overlap in the XY plane:

consumer	call site
SAT collision detection	physics/builtin/detector.js:288
pointer picking / hit-testing	input/pointerevent.ts:327
2D raycast	physics/builtin/raycast.ts:213
adapter.queryAABB	physics/builtin/builtin-adapter.ts:572

Two bodies at different z that overlap in XY genuinely collide under 2D SAT — and were never offered to each other as candidates. Whether a given pair got tested came down to which side of an octant boundary each happened to fall on. ResponseObject.overlapV / overlapN are Vector2d (physics/response.js:20-21) and SAT_LOOKUP runs on 2D geometry, so depth has no say in the outcome and should have had none in the candidate walk.

Measured on a randomized 300-body scene: 12 of 20 genuinely overlapping pairs never surfaced.

This is a correctness bug: a missed collision announces itself only as a character walking through a wall, with nothing in any log.

It also means the "distant-Z parallax drops out of collision for free" behaviour the 2.5D Games wiki page described as best-effort was this defect seen from its good side. Parallax should be excluded deliberately — isKinematic = true, or collisionType / collisionMask — which is what the 2D path has always done. Wiki updated.

2. Items sitting exactly ON a midpoint were misfiled to the parent

-1 from getIndex means "straddles a midpoint, keep at this level". But items are point-z in the broadphase (octree.ts says so explicitly), and a point cannot straddle the depth midpoint. An item whose far edge merely touches a vertical midpoint likewise lies wholly inside the near child.

It matters because the root box is origin-centred at ±10000, so its midpoints are (0, 0, 0) — the default pos of every renderable, and the shared gameplay z that the 2.5D recipe prescribes.

Measured: 200 bodies on a z = 0 plane all stayed at the root, and retrieve() returned 200 of 200 — the broadphase degraded to a linear scan for exactly the layer holding the most bodies. The same 200 spread across z left only 10 at the root.

Performance rather than correctness (root-level items are visited by every query, so nothing is missed), but it silently removes the entire benefit of having a broadphase on the gameplay plane.

tests/octree.spec.js:247 asserted the old behaviour as correct, with the comment // not strictly < or > midpoint — the tie was noticed and codified rather than followed through. That is why it survived.

Notes

• queryAABB, querySphere, queryRay and queryFrustum were already correct and still prune on depth — confirmed by randomized differential testing against a brute-force scan. Only retrieve() was wrong.
• Defect 1 was found by that differential sweep; the investigation had started on defect 2 alone.