spatial_hash.hpp File Reference

SPH neighbour search – now powered by num::CellList2D. More...

#include "particle.hpp"
#include "spatial/cell_list.hpp"
#include <vector>

Go to the source code of this file.

Classes
class	physics::SpatialHash

Namespaces
namespace	physics

Detailed Description

SPH neighbour search – now powered by num::CellList2D.

Replaces the original chained hash table with the counting-sort cell list from src/spatial/cell_list.hpp. The public interface is unchanged so that heat.cpp keeps working without modification.

Improvements over the old chained-list hash:

Old (chained hash table) build : O(n) – fill table[] + next[] via random writes query : O(9 * avg_bucket) – pointer-chase linked list in each of 9 cells

New (counting sort cell list) build : O(n + C) – two sequential passes + one prefix sum query : O(k) sequential reads – particles in same cell are contiguous pairs : iterate_pairs() – visits each (i,j) pair once (Newton 3rd law)

The key cache-behaviour difference: the old next_[] array creates a random walk through the particle array. sorted_[] in CellList2D is laid out so that all particles in a cell sit next to each other in memory.

Definition in file spatial_hash.hpp.