#️⃣ Spatial Hashing: O(1) Nearest-Neighbor Search for Particle Simulations

The Naive O(n²) Problem

For n particles, naively finding all pairs within distance h requires n(n-1)/2 distance checks. For n = 1000, that's 499,500 checks. For n = 10,000, it's 50 million. At 60 fps, each frame has about 16 ms — 50 million distance computations (each a square root or at least three multiplications and an addition) will take hundreds of milliseconds. The simulation stalls at sub-10 fps.

The key insight is that particles only interact within a radius h. If we can quickly find which particles are within distance h of a given particle without checking all others, we can reduce work from O(n²) to O(n·k) where k is the average number of neighbors — typically a small constant (5–50 for typical SPH simulations).

The Grid Approach: Spatial Subdivision

Divide the simulation domain into a grid with cell size equal to the interaction radius h. A particle at position (x, y) belongs to cell (⌊x/h⌋, ⌊y/h⌋). Because particles only interact within distance h, any particle interacting with a particle in cell (cx, cy) must be in one of the 9 neighboring cells (in 2D) — the cell itself plus the 8 surrounding cells. In 3D, this is 27 cells.

If the grid has G = (W/h) × (H/h) cells (for simulation box W × H), and n particles are distributed roughly uniformly, each cell contains about n/G particles on average. Looking up 9 cells containing n/G particles each costs O(9 · n/G) = O(n · h²/(WH)) work — proportional to the fraction of area covered by the interaction radius.

Spatial Hashing: No Grid Allocation

A fixed grid requires allocating W/h × H/h cells — fine for known domain sizes, but wasteful if particles cluster in a small region or if the domain is large. Spatial hashing avoids the explicit grid by hashing cell coordinates to a fixed-size flat array:

class SpatialHash {
  constructor(cellSize, tableSize) {
    this.cellSize = cellSize;
    this.tableSize = tableSize;
    this.table = new Array(tableSize).fill(null).map(() => []);
  }

  hash(cx, cy) {
    // Large primes to spread grid coordinates evenly
    return ((cx * 92837111) ^ (cy * 689287499)) % this.tableSize;
  }

  cellCoords(x, y) {
    return [Math.floor(x / this.cellSize), Math.floor(y / this.cellSize)];
  }

  insert(particle) {
    const [cx, cy] = this.cellCoords(particle.x, particle.y);
    const key = this.hash(cx, cy);
    this.table[key].push(particle);
  }

  query(x, y) {
    const [cx, cy] = this.cellCoords(x, y);
    const neighbors = [];
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        const key = this.hash(cx + dx, cy + dy);
        neighbors.push(...this.table[key]);
      }
    }
    return neighbors;
  }
}

The hash function maps arbitrary (cx, cy) integer pairs to [0, tableSize). Using large coprime primes prevents systematic collisions between nearby cells. The table must be cleared and rebuilt each frame as particles move — clearing the entire table array takes O(tableSize) time, so tableSize should be chosen as a small multiple of n, not exponentially larger.

Hash Function Design

Hash collisions (different cells mapping to the same table slot) don't cause correctness errors — we check actual distances to filter false positives — but they increase work. A poor hash function (e.g., (cx + cy) % tableSize) causes many collisions between cells along diagonals. The product of large primes distributes cell coordinates quasi-randomly across the table.

For WebGL compute shaders where integer arithmetic is limited, a common alternative uses a single large integer key key = cx * MAX_Y + cy and stores particles in a sorted array by key, enabling binary search. This avoids dynamic memory allocation (no JavaScript arrays), which is essential for GPU memory.

Choosing tableSize: with n particles and average k neighbors, each cell contains about k/9 particles. Setting tableSize = 2n gives load factor 0.5 and acceptable collision rate. Smaller tables risk many collisions (degrading to O(n²) in the worst case); larger tables waste memory bandwidth during clearing.

Prefix Sum Approach for GPU Parallelism

JavaScript hash tables use dynamic arrays and can't run in parallel on the GPU. WebGL implementations use a prefix sum (scan) approach:

1. Counting pass: Each particle atomically increments a counter for its cell (compute shader).
2. Prefix sum: Compute cumulative sums to find each cell's start index in a sorted array.
3. Filling pass: Write each particle to its cell's slot in the sorted array using the prefix sum as a write pointer.
4. Query: For any cell, read particles from index prefixSum[cell] to prefixSum[cell+1].

This creates a perfectly packed, sorted array of particles by cell — no linked lists, no dynamic allocation, fully coalesced memory access on the GPU. The prefix sum pass itself runs in O(log n) parallel steps using a parallel scan algorithm. Combined, the full spatial hash rebuild costs O(n) work but only O(log n) parallel steps — essentially free compared to the neighbor computation itself.

Spatial Hashing vs BVH: When to Use Each

• Spatial hashing: Best for same-size particles (uniform cell size is optimal), dynamic scenes (rebuild every frame is O(n)), large particle counts (10k–1M), uniform distributions. Used in SPH fluid, sand, boid flocks.
• BVH: Best for variable-size objects (BVH adapts to object sizes), static or slowly-changing scenes (rebuild is expensive), ray intersection queries, scenes with large empty regions. Used in ray tracing, rigid body physics with complex shapes.