# Spatial data structures (prototype notes)
This crate includes **prototype-quality** spatial data structures behind the `spatial` feature:
- `UniformGrid2`: 2D uniform grid (broadphase candidate generator)
- `Quadtree2`: 2D AABB quadtree (broadphase candidate generator)
- `Bvh3`: 3D binary BVH built by median splits on centroid axis (query acceleration)
These are intended for **broadphase** workloads: quickly narrowing a large set down to a smaller set of candidates that then go through exact intersection tests.
## Feature / build constraints
- **Requires allocation**: these are `Vec`-backed, so they require `std` or `alloc`.
- **Feature flags**:
- Enable with `features = ["spatial"]` (default `full` includes it).
- Minimal build example (no `std`): `cargo test --no-default-features --features "libm,spatial,alloc"`
## Practical constraints / trade-offs
- **UniformGrid2**
- **Pros**: very fast rebuild; simple; great when object sizes are similar and spatial distribution is roughly uniform.
- **Cons**: “hot” cells can become very dense; memory can be high if many objects span multiple cells.
- **Tuning**: `cell_size` is the key parameter.
- **Quadtree2**
- **Pros**: adapts to spatial density; can reduce candidate explosion in clustered scenes.
- **Cons**: insertion/build is more complex; large objects that span child boundaries stay in higher nodes, increasing query cost.
- **Tuning**: `max_depth`, `max_items_per_node`.
- **Bvh3**
- **Pros**: good query performance for static-ish scenes; build is straightforward.
- **Cons**: the median split build is not SAH-optimized; dynamic updates would require rebuild/refit logic (not implemented in this prototype).
## Benchmarks
Run criterion benchmarks:
```bash
cargo bench --bench spatial_benchmarks
```
The benchmark compares broadphase-style query loops for:
- brute-force scanning (baseline)
- `UniformGrid2`
- `Quadtree2`
- `Bvh3`
Interpretation guidance:
- The goal is usually **fewer narrow-phase checks** and/or **lower total query time** than brute force.
- Expect results to vary significantly with object distribution and size variance.