@web-engine-dev/spatial

Spatial partitioning data structures with Quadtree, Octree, BVH, and spatial hashing for web-engine-dev.

Features

• Quadtree: 2D spatial partitioning
• Octree: 3D spatial partitioning
• BVH: Bounding Volume Hierarchy
• Spatial Hash: Grid-based hashing
• Frustum Culling: Camera visibility queries
• Range Queries: Find objects in area

Installation

npm install @web-engine-dev/spatial
# or
pnpm add @web-engine-dev/spatial

Quick Start

import { Quadtree, Octree, SpatialHashGrid2D, BVH, FrustumCuller } from '@web-engine-dev/spatial';

// Create quadtree for 2D
const quadtree = new Quadtree({
  bounds: { min: { x: 0, y: 0 }, max: { x: 1000, y: 1000 } },
  maxItemsPerNode: 10,
  maxDepth: 5,
});

// Insert objects
quadtree.insert({
  id: 1,
  bounds: { min: { x: 100, y: 100 }, max: { x: 120, y: 120 } },
  data: { name: 'A' },
});
quadtree.insert({
  id: 2,
  bounds: { min: { x: 150, y: 120 }, max: { x: 180, y: 150 } },
  data: { name: 'B' },
});

// Query range
const nearby = quadtree.queryRect({
  min: { x: 90, y: 90 },
  max: { x: 190, y: 190 },
});

API Overview

Quadtree (2D)

const tree = new Quadtree({
  bounds: { min: { x, y }, max: { x: x + width, y: y + height } },
  maxItemsPerNode: 10, // Before split
  maxDepth: 5, // Max depth
});

tree.insert(object);
tree.remove(object);
tree.update(object.id, newBounds); // Update after move
tree.queryRect(bounds); // Get overlapping
tree.queryRectUnique(bounds); // Deduplicated query
tree.clear();

Octree (3D)

const tree = new Octree({
  bounds: { min: { x, y, z }, max: { x: x + width, y: y + height, z: z + depth } },
  maxItemsPerNode: 8,
  maxDepth: 6,
  looseness: 1.0, // >1.0 enables loose octree bounds
});

tree.insert(object);
tree.queryBox(aabb);
tree.queryBoxUnique(aabb);
tree.raycast(origin, direction);

Spatial Hash

const hash = new SpatialHashGrid2D({
  cellSize: 50,
});

hash.insert(object);
hash.queryRect(bounds);
hash.queryPoint(x, y);
hash.clear();

BVH (Bounding Volume Hierarchy)

const bvh = new BVH();

// Build from objects
bvh.build(objects);

// Query
const hits = bvh.queryBox(aabb);
const rayHit = bvh.raycast(ray);

// Update single object
bvh.update(object.id, object.bounds);

// Refit after many changes
bvh.refit();

// Frustum culling (hierarchical)
const culler = new FrustumCuller();
const visibleFast = culler.cullBVH(bvh);

Frustum Culling

import { FrustumCuller } from '@web-engine-dev/spatial';

const culler = new FrustumCuller();
culler.setFromMatrix(viewProjection);

// Get visible objects
const visible = culler.cullOctree(octree);

KDTree (Nearest-Neighbor)

const tree = new KDTree({ dimensions: 2 });
tree.build(points);
const nearest = tree.nearest([x, y]);
const neighbors = tree.kNearest([x, y], 5);
const within = tree.rangeSearch([x, y], radius);

RTree (Database-like Index)

// Requires optional peer dependency: rbush
const rtree = new RTree();
rtree.insert(object);
const hits = rtree.search(bounds);

Performance Tips

Structure	Best For
Quadtree	2D games, sparse objects
Octree	3D games, sparse objects
Spatial Hash	Dense, uniform distribution
BVH	Static geometry, ray tracing

Peer Dependencies

• @web-engine-dev/math - Vector/AABB math
• rbush - Optional RTree acceleration