Struct SpatialHashGrid 

pub struct SpatialHashGrid { /* private fields */ }

Spatial hash grid for broadphase pair generation. Replaces O(n^2) all-pairs with O(n) expected-case neighbour lookups.

Implementations

impl SpatialHashGrid

pub fn new(cell_size: f32) -> Self

pub fn cell_size(&self) -> f32

Cell size used for spatial hashing (debug/query introspection).

pub fn set_cell_size(&mut self, size: f32)

Update cell size. Call before populate() when body density changes.

pub fn inv_cell_size(&self) -> f32

Inverse cell size (for wave coherence broadphase access).

pub fn entries(&self) -> &[(u64, usize)]

Sorted entries (for wave coherence per-body regeneration).

pub fn populate(&mut self, bodies: &[RigidBody])

Populate the grid from body positions. Sorts entries by hash for fast lookup.

pub fn query_pairs(&self, bodies: &[RigidBody]) -> Vec<(usize, usize)>

Generate candidate pairs using half-neighborhood search.

Instead of querying all 27 neighbor cells (which produces duplicate pairs requiring O(P log P) sort + O(P) dedup), we query only the 14 “forward” cells: the self-cell plus 13 cells that are lexicographically greater in (dx, dy, dz) order. This guarantees each pair is discovered exactly once.

Mathematical proof: For bodies A in cell C_A and B in cell C_B where C_A and C_B are adjacent (differ by at most 1 on each axis):

• If C_A < C_B lexicographically: A’s forward search includes C_B → pair found by A
• If C_A > C_B lexicographically: B’s forward search includes C_A → pair found by B
• If C_A == C_B: same cell, j > i index guard → pair found once

This is the 3D analog of the causal attention mask: compute only the upper triangle of the spatial relevance matrix. Zero duplicates by construction. No sort. No dedup. O(N × 14 × log N) vs O(N × 27 × log N + P log P).

Reference: Allen & Tildesley, “Computer Simulation of Liquids” (1987), half-neighbor Verlet list construction.

Trait Implementations

impl Clone for SpatialHashGrid

fn clone(&self) -> SpatialHashGrid

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SpatialHashGrid

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.