Boost.Spatial - Sparse Spatial Hash Grid¶

Overview¶

sparse_spatial_hash is a production-ready, Boost-quality C++20 library providing high-performance spatial indexing through sparse hash-based grids. Extracted from the DigiStar physics engine where it enables efficient collision detection and force calculations for 10M+ particle simulations.

Key Features¶

Performance¶

Capabilities¶

• N-Dimensional Support: Works with 2D, 3D, 4D, or any dimension count
• Sparse Storage: Memory-efficient hash-based storage (only occupied cells)
• Multiple Topologies: Bounded, toroidal (periodic), and infinite spaces
• Incremental Updates: O(k) updates where k ≈ 1% of entities (typical)
• STL-Compatible: Works with ranges, concepts, and standard algorithms
• Header-Only: Single include, no linking required
• Zero-Overhead: Generic programming with compile-time polymorphism
• Morton Hashing: Cache-friendly Z-order curve for spatial locality

Quick Example¶

#include <boost/spatial/sparse_spatial_hash.hpp>
#include <vector>

struct Particle {
    float x, y, z;
    float vx, vy, vz;
};

// Customize position extraction (one-time setup)
template<>
struct boost::spatial::position_accessor<Particle, 3> {
    static float get(const Particle& p, std::size_t dim) {
        switch(dim) {
            case 0: return p.x;
            case 1: return p.y;
            case 2: return p.z;
            default: return 0.0f;
        }
    }
};

int main() {
    using namespace boost::spatial;

    // Create 3D toroidal grid (1000³ world, 10-unit cells)
    grid_config<3> cfg{
        .cell_size = {10.0f, 10.0f, 10.0f},
        .world_size = {1000.0f, 1000.0f, 1000.0f},
        .topology_type = topology::toroidal
    };

    sparse_spatial_hash<Particle, 3> grid(cfg);

    // Create and index particles
    std::vector<Particle> particles(10000);
    // ... initialize particles ...

    grid.rebuild(particles);

    // Query neighbors within 50 units
    auto neighbors = grid.query_radius(50.0f, 100.0f, 200.0f, 300.0f);

    // Process all pairs within 20 units
    grid.for_each_pair(particles, 20.0f,
        [&](std::size_t i, std::size_t j) {
            // Compute interaction between particles[i] and particles[j]
        });

    // Efficient incremental update (40x faster than rebuild!)
    grid.update(particles);
}

Performance Highlights¶

Memory Comparison¶

For 10 million particles in a 10,000³ world:

Time Complexity¶

Real-World Performance¶

From DigiStar physics engine (10M particles, 10000³ world):

• Rebuild: ~80ms (full grid reconstruction)
• Incremental Update: ~2ms (when 1% of particles change cells) - 40x speedup!
• Collision Detection: ~150ms (20-unit interaction radius)
• Memory: 100MB grid + 80MB particle tracking

Use Cases¶

Game Development¶

• Collision Detection (broad-phase spatial partitioning)
• AI Pathfinding (efficient neighbor queries)
• Rendering Culling (frustum-based entity filtering)
• Particle Systems (fast neighbor searches)

Scientific Computing¶

• N-body Simulations (gravity/electrostatics neighbor lists)
• Molecular Dynamics (bonded/non-bonded interactions)
• SPH Fluids (smoothed particle hydrodynamics)
• Atmospheric Modeling (grid-based weather simulations)

Robotics¶

• SLAM (spatial mapping and localization)
• Obstacle Detection (real-time collision avoidance)
• Multi-Agent Systems (swarm coordination)

GIS and Spatial Databases¶

• Proximity Queries (find nearby points of interest)
• Spatial Indexing (large-scale geographic data)
• Clustering (identify spatial groups)

Why Sparse Hash?¶

vs. R-tree (Boost.Geometry)¶

✓ Faster insertions (O(1) vs O(log n)) ✓ Simpler incremental updates (no tree rebalancing) ✓ Better for dynamic scenes ✓ First-class toroidal topology support

vs. Octree¶

✓ More memory efficient (sparse storage vs tree nodes) ✓ Faster queries (direct hash lookup vs tree traversal) ✓ Simpler to implement

vs. Dense Grid¶

✓ 60,000x memory reduction for large sparse worlds ✓ Scalable to huge worlds

vs. kd-tree¶

✓ Dynamic updates (kd-tree requires rebuild) ✓ Consistent performance (no worst-case tree imbalance)

Compare Data Structures

Design Principles¶

Built to Boost quality standards with focus on:

• Zero-overhead abstractions through generic programming
• STL compatibility (ranges, concepts, algorithms)
• Exception safety with documented guarantees
• Comprehensive testing (31 tests, 197 assertions)
• Production-proven (extracted from real physics engine)

Getting Started¶

Project Status¶

• Version: 1.0.0
• Status: Production-ready, battle-tested
• License: Boost Software License 1.0
• Requirements: C++20 (GCC 10+, Clang 12+, MSVC 2019+)
• Dependencies: None (header-only, standard library only)

Community¶

• GitHub: spinoza/sparse_spatial_hash
• Issues: Report bugs or request features
• Discussions: Ask questions
• Boost Submission: Learn about submission process

Acknowledgments¶

Extracted from the DigiStar physics engine.

Inspired by:

• Teschner et al. "Optimized Spatial Hashing for Collision Detection" (2003)
• Boost.Geometry spatial indexing
• Morton encoding for cache-friendly iteration