@hatch:spatial v0.2.1

Spatial acceleration structures for 2D and 3D worlds. ClusterGrid for uniform-density buckets, Octree for adaptive 3D partitioning, Quadtree2D for sprite / UI hit-testing, and BVH over AABBs for ray casts and frustum culling. Pure Wren; composes with @hatch:gpu's Camera3D + Frustum for cull and LOD pipelines and with @hatch:noise for procedural density sampling.

stable system updated Jun 4, 2026 source ↗

README Changelog

$ hatch add @hatch:spatial

MOD spatial

CL ClusterGrid

NEW `ClusterGrid.new(minX, minY, minZ, maxX, maxY, maxZ, cellSize)`

GET `ClusterGrid.count → Num`

GET `ClusterGrid.cellsX → Num`

GET `ClusterGrid.cellsY → Num`

GET `ClusterGrid.cellsZ → Num`

FN `ClusterGrid.cellIndex_(x, y, z)`

FN `ClusterGrid.insert(id: Num, x: Num, y: Num, z: Num)`

FN `ClusterGrid.move(id: Num, x: Num, y: Num, z: Num)`

FN `ClusterGrid.remove(id: Num)`

FN `ClusterGrid.removeFromBucket_(ci, id)`

FN `ClusterGrid.queryRadius(cx: Num, cy: Num, cz: Num, radius: Num, cb: Fn)`

FN `ClusterGrid.queryAabb(minX: Num, minY: Num, minZ: Num, maxX: Num, maxY: Num, maxZ: Num, cb: Fn)`

FN `ClusterGrid.clear()`

CL Octree

NEW `Octree.new(minX: Num, minY: Num, minZ: Num, maxX: Num, maxY: Num, maxZ: Num, maxPerLeaf: Num)`

GET `Octree.count → Num`

FN `Octree.insert(id: Num, x: Num, y: Num, z: Num)`

FN `Octree.remove(id: Num)`

FN `Octree.queryRadius(cx: Num, cy: Num, cz: Num, radius: Num, cb: Fn)`

FN `Octree.queryAabb(minX, minY, minZ, maxX, maxY, maxZ, cb)`

FN `Octree.clear()`

CL OctreeNode_

NEW `OctreeNode_.new_(minX, minY, minZ, maxX, maxY, maxZ)`

GET `OctreeNode_.entries`

GET `OctreeNode_.children`

FN `OctreeNode_.insert_(id, x, y, z, maxPerLeaf)`

FN `OctreeNode_.subdivide_(maxPerLeaf)`

FN `OctreeNode_.childFor_(x, y, z)`

FN `OctreeNode_.descendForId_(id, x, y, z)`

FN `OctreeNode_.removeEntry_(id)`

FN `OctreeNode_.queryRadius_(cx, cy, cz, r2, r, cb)`

FN `OctreeNode_.queryAabb_(minX, minY, minZ, maxX, maxY, maxZ, cb)`

FN `OctreeNode_.intersectsSphere_(cx, cy, cz, r)`

FN `OctreeNode_.clear_()`

CL Quadtree2D

NEW `Quadtree2D.new(minX: Num, minY: Num, maxX: Num, maxY: Num, maxPerLeaf: Num)`

GET `Quadtree2D.count`

FN `Quadtree2D.insert(id, x, y)`

FN `Quadtree2D.remove(id)`

FN `Quadtree2D.queryRadius(cx, cy, radius, cb)`

FN `Quadtree2D.queryAabb(minX, minY, maxX, maxY, cb)`

FN `Quadtree2D.clear()`

CL Quadtree2DNode_

NEW `Quadtree2DNode_.new_(minX, minY, maxX, maxY)`

GET `Quadtree2DNode_.entries`

GET `Quadtree2DNode_.children`

FN `Quadtree2DNode_.insert_(id, x, y, maxPerLeaf)`

FN `Quadtree2DNode_.subdivide_(maxPerLeaf)`

FN `Quadtree2DNode_.childFor_(x, y)`

FN `Quadtree2DNode_.descendForId_(id, x, y)`

FN `Quadtree2DNode_.removeEntry_(id)`

FN `Quadtree2DNode_.queryRadius_(cx, cy, r2, r, cb)`

FN `Quadtree2DNode_.queryAabb_(minX, minY, maxX, maxY, cb)`

FN `Quadtree2DNode_.intersectsCircle_(cx, cy, r)`

FN `Quadtree2DNode_.clear_()`

CL BVH

NEW `BVH.new(items: List)`

GET `BVH.count → Num`

FN `BVH.updateAabb(id: Num, minX: Num, minY: Num, minZ: Num, maxX: Num, maxY: Num, maxZ: Num)`

FN `BVH.refit()`

FN `BVH.queryFrustum(planes: Float32Array, out: Int32Array) → Num`

FN `BVH.queryRay(originX: Num, originY: Num, originZ: Num, dirX: Num, dirY: Num, dirZ: Num, out: Int32Array, maxResults: Num) → Num`

FN `BVH.queryAabb(minX: Num, minY: Num, minZ: Num, maxX: Num, maxY: Num, maxZ: Num, out: Int32Array) → Num`

FN `BVH.indexList_()`

FN `BVH.buildNode_(lo, hi, indices)`

FN `BVH.computeAabb_(node, lo, hi, indices)`

FN `BVH.longestAxis_(node)`

FN `BVH.sortByCentroid_(indices, lo, hi, axis)`

FN `BVH.centroid_(idx, axis)`

FN `BVH.refitNode_(node)`

FN `BVH.classifyFrustum_(node, planes)`

FN `BVH.queryFrustumNode_(node, planes)`

FN `BVH.rayHitsAabb_(node, ox, oy, oz, invX, invY, invZ)`

FN `BVH.queryRayNode_(node, ox, oy, oz, invX, invY, invZ)`

FN `BVH.queryAabbNode_(node, qMinX, qMinY, qMinZ, qMaxX, qMaxY, qMaxZ)`

CL BVHNode_

NEW `BVHNode_.new_()`

GET `BVHNode_.minX`

GET `BVHNode_.minY`

GET `BVHNode_.minZ`

GET `BVHNode_.maxX`

GET `BVHNode_.maxY`

GET `BVHNode_.maxZ`

GET `BVHNode_.left`

GET `BVHNode_.right`

GET `BVHNode_.itemIndex`

GET `BVHNode_.isLeaf`

FN `BVHNode_.setAabb_(minX, minY, minZ, maxX, maxY, maxZ)`

FN `BVHNode_.bindLeaf_(idx)`

FN `BVHNode_.bindInternal_(left, right)`

@hatch:spatial v0.2.1

MOD spatial

CL ClusterGrid

NEW ClusterGrid.new(minX, minY, minZ, maxX, maxY, maxZ, cellSize)

GET ClusterGrid.count → Num

GET ClusterGrid.cellsX → Num

GET ClusterGrid.cellsY → Num

GET ClusterGrid.cellsZ → Num

FN ClusterGrid.cellIndex_(x, y, z)

FN ClusterGrid.insert(id: Num, x: Num, y: Num, z: Num)

FN ClusterGrid.move(id: Num, x: Num, y: Num, z: Num)

FN ClusterGrid.remove(id: Num)

FN ClusterGrid.removeFromBucket_(ci, id)

FN ClusterGrid.queryRadius(cx: Num, cy: Num, cz: Num, radius: Num, cb: Fn)

FN ClusterGrid.queryAabb(minX: Num, minY: Num, minZ: Num, maxX: Num, maxY: Num, maxZ: Num, cb: Fn)

FN ClusterGrid.clear()

CL Octree

NEW Octree.new(minX: Num, minY: Num, minZ: Num, maxX: Num, maxY: Num, maxZ: Num, maxPerLeaf: Num)

GET Octree.count → Num

FN Octree.insert(id: Num, x: Num, y: Num, z: Num)

FN Octree.remove(id: Num)

FN Octree.queryRadius(cx: Num, cy: Num, cz: Num, radius: Num, cb: Fn)

FN Octree.queryAabb(minX, minY, minZ, maxX, maxY, maxZ, cb)

FN Octree.clear()

CL OctreeNode_

NEW OctreeNode_.new_(minX, minY, minZ, maxX, maxY, maxZ)

GET OctreeNode_.entries

GET OctreeNode_.children

FN OctreeNode_.insert_(id, x, y, z, maxPerLeaf)

FN OctreeNode_.subdivide_(maxPerLeaf)

FN OctreeNode_.childFor_(x, y, z)

FN OctreeNode_.descendForId_(id, x, y, z)

FN OctreeNode_.removeEntry_(id)

FN OctreeNode_.queryRadius_(cx, cy, cz, r2, r, cb)

FN OctreeNode_.queryAabb_(minX, minY, minZ, maxX, maxY, maxZ, cb)

FN OctreeNode_.intersectsSphere_(cx, cy, cz, r)

FN OctreeNode_.clear_()

CL Quadtree2D

NEW Quadtree2D.new(minX: Num, minY: Num, maxX: Num, maxY: Num, maxPerLeaf: Num)

GET Quadtree2D.count

FN Quadtree2D.insert(id, x, y)

FN Quadtree2D.remove(id)

FN Quadtree2D.queryRadius(cx, cy, radius, cb)

FN Quadtree2D.queryAabb(minX, minY, maxX, maxY, cb)

FN Quadtree2D.clear()