Particle-based simulation

"Particle-based simulation" is a generic term used to designate any type of simulation in which the solution process involves keeping track of moving discrete points (or particles) in space. This includes mesh-free Lagrangian approaches such as smoothed particle hydrodynamics as well as discrete element method and N-body simulation.

Our objective is to develop computationally efficient algorithms for determining the interaction status of each pair of particles: whether the position and properties of one of them has an impact on the dynamics of the other at a given time.

More precisely, if we can define a finite "interaction volume" for a particle A such that the dynamics of any particle B outside this volume will not be affected by A, then we can efficiently generate an accordingly reduced subset of particle pairs that may lead to an interaction.

Linear kd-trees

Geometrically, our method is a space partitioning technique based on a specific class of kd-trees. The key aspect of the implementation is the particular representation of the tree as a linear associative array, sharing some basic concepts with linear octrees.

A description of the algorithm: technical report (older version)

See our downloads section for library source code. See the bechmarks and videos section for some numerical results and visualizations.

ChangeLog