Particle Simulation · Projects

A C++ simulator for fluids and particle systems. Fluids follow the Navier-Stokes equations, discretized with smoothed-particle hydrodynamics (SPH); a uniform spatial hash keeps neighbor search and collision detection near-linear as particle counts grow.

SPH represents a fluid as particles that each carry mass and sample the field around them. Any field quantity $A$ at a point is a kernel-weighted sum over nearby particles,

A (r) = j \sum m_{j} \frac{A _{j}}{ρ _{j}} W (r - r_{j}, h),

where $W$ is a smoothing kernel of support radius $h$ and $ρ_{j}$ the density at particle $j$ . Density is the same sum applied to mass, $ρ_{i} = \sum_{j} m_{j} W (r_{i} - r_{j}, h)$ ; pressure and viscosity forces come from the gradient and Laplacian of $W$ .

Each particle obeys the momentum form of Navier-Stokes,

ρ \frac{D v}{D t} = - \nabla p + μ \nabla^{2} v + ρ g,

a balance of pressure, viscosity, and gravity. Pressure follows an equation of state from density, $p = k (ρ - ρ_{0})$ , which resists compression and keeps the fluid roughly incompressible.

Every kernel sum ranges only over particles within $h$ , but finding them naively is $O (n^{2})$ , and that search dominates the cost. Positional indexing hashes each particle into a grid of cell size $h$ ; then only the particle's own cell and the cells bordering it can hold interactions, so each query touches a constant number of cells:

A query particle (center) interacts only with particles inside its support radius

h

, and those lie in its own grid cell or the eight bordering it, so a neighbor search touches nine cells, not the whole domain.

Algorithm:

\textsc{Neighbors}(i)

— spatial-hash query for particles within

h

i

1
input: particle $i$ , cell size $h$ , table $G$ mapping cell $\to$ particles
2
$c \gets \lfloor \mathbf r_i / h \rfloor$ ; $\$ result $\gets \varnothing$
3
for each cell $c'$ bordering $c$ , and $c$ itself, do
4
for each particle $j \in G[c']$ do
5
if $\lVert \mathbf r_i - \mathbf r_j \rVert < h$ then add $j$ to result
6
return result

The spatial-hash neighbor query, live over a real collision sim: particles bounce off each other through contacts found by the same hash — overlapping pairs separate and exchange an impulse along the contact normal. The query particle's 3-by-3 cell block is shaded and its kernel radius drawn; green particles are true neighbors inside the radius, yellow ones were scanned and rejected. The cell-size select shows the trade in how many candidates each query touches.

Spatial-hash neighbor query

querytrue neighborcandidatecolliding

The same grid detects particle collisions and propagates contact forces: particles that share or border a cell are the only ones close enough to touch, so contact resolution never compares far-apart pairs. A contact between two particles of radius $r$ is an overlap; resolution separates the pair and, if they are still approaching, reflects the normal component of their relative velocity with restitution $e$ :

Algorithm:

\textsc{ResolveContacts}()

— collisions through the same hash

1
input: particles with radius $r$ , restitution $e$ , cell table $G$
2
rebuild $G$ : insert every particle into its cell
3
for each particle $i$ do
4
for each $j \in \textsc{Neighbors}(i)$ with $j > i$ do
5
$d \gets \lVert \mathbf r_i - \mathbf r_j \rVert$
6
if $d < 2r$ then
7
$\mathbf n \gets (\mathbf r_i - \mathbf r_j) / d$
8
move $i$ and $j$ apart by $(2r - d)/2$ along $\pm\mathbf n$
9
$v_n \gets (\mathbf v_i - \mathbf v_j) \cdot \mathbf n$
10
if $v_n < 0$ then
11
apply impulse $-(1 + e)\,v_n / 2$ along $\pm\mathbf n$ to $i$ and $j$

References

Project repository
Reference notes: Spatial Data Structures
Reference notes: Hash Tables

╌╌ END ╌╌