Spatial Hashing

Spatial hashing accelerates neighbor queries from O(n²) to approximately O(n). It's automatically enabled when you use neighbor-based rules.

Why It's Needed

Without spatial hashing, checking every particle against every other particle is prohibitively slow:

How It Works

1. Morton Encoding (Z-Order Curve)

3D space is divided into a grid of cells. Each cell gets a unique ID using Morton encoding:

3D Position → Cell Coordinates → Morton Code (single u32)

Morton codes preserve spatial locality - nearby cells have similar codes.

2. Radix Sort

Particles are sorted by their Morton code using GPU radix sort:

• Dynamic pass count based on grid resolution (e.g., 32³ grid = 15 bits needed = 4 passes)
• Each pass processes 4 bits: histogram → prefix sum → scatter
• Result: particles ordered by spatial cell

3. Cell Table

After sorting, we build a lookup table:

cell_start[morton_code] = first particle index in this cell
cell_end[morton_code] = one past last particle index

4. Neighbor Iteration

To find neighbors, check the 27 adjacent cells (3×3×3 cube):

for offset in 0..27 {
    let neighbor_cell = get_neighbor_cell(my_cell, offset);
    for particle in cell_start[neighbor_cell]..cell_end[neighbor_cell] {
        // Check distance, apply rule
    }
}

Max Neighbors Limit

For dense clusters, you can cap how many neighbors each particle processes:

#![allow(unused)]
fn main() {
.with_max_neighbors(48)  // Stop after 48 neighbors
}

This provides an early-exit from the neighbor loop, trading accuracy for performance in pathological cases where particles cluster tightly.

Configuration

Configure spatial hashing with:

#![allow(unused)]
fn main() {
.with_spatial_config(cell_size, grid_resolution)
}

Cell Size

Should be at least as large as your largest interaction radius:

#![allow(unused)]
fn main() {
// If your largest rule has radius 0.15:
.with_spatial_config(0.15, 32)

// Or slightly larger for safety:
.with_spatial_config(0.2, 32)
}

If cell size is smaller than interaction radius, you might miss neighbors in non-adjacent cells.

Grid Resolution

Must be a power of 2 (16, 32, 64, 128, etc.):

#![allow(unused)]
fn main() {
.with_spatial_config(0.1, 32)  // 32³ = 32,768 cells
.with_spatial_config(0.1, 64)  // 64³ = 262,144 cells
}

The grid covers space from -resolution * cell_size / 2 to +resolution * cell_size / 2:

Ensure your bounds fit within the grid coverage.

When It's Used

Spatial hashing is automatically enabled when you use any of these rules:

• Rule::Separate
• Rule::Cohere
• Rule::Align
• Rule::Collide
• Rule::Convert
• Rule::Typed (wrapping a neighbor rule)

Non-neighbor rules (Gravity, Drag, BounceWalls, etc.) don't trigger spatial hashing.

Memory Usage

The spatial hash requires additional GPU buffers:

For 10,000 particles with 32³ grid:

• Morton/indices: 160 KB
• Cell tables: 256 KB
• Total: ~416 KB

Performance Tips

1. Match cell size to interaction radius - Too small wastes work checking empty cells; too large checks too many particles per cell.

2. Don't over-resolve - 32³ is usually enough. 64³ only helps if particles are very spread out.

3. Spatial hash runs every frame - It's fast, but the cost is proportional to particle count.

4. Combine interaction radii - If possible, use similar radii for all neighbor rules to optimize cell size.