Skip to Main content Skip to Navigation
New interface
Conference papers

A Packed Memory Array to Keep Moving Particles Sorted

Marie Durand 1, * Bruno Raffin 1, * François Faure 2, * 
* Corresponding author
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 IMAGINE - Intuitive Modeling and Animation for Interactive Graphics & Narrative Environments
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
Abstract : Neighbor identification is the most computationally intensive step in particle based simulations. To contain its cost, a common approach consists in using a regular grid to sort particles according to the cell they belong to. Then, neighbor search only needs to test the particles contained in a constant number of cells. During the simulation, a usually small amount of particles are moving between consecutive steps. Taking into account this temporal coherency to save on the maintenance cost of the acceleration data structure is difficult as it usually triggers costly dynamics memory allocations or data moves. In this paper we propose to rely on a Packed Memory Array (PMA) to efficiently keep particles sorted according to their cell index. The PMA maintains gaps in the particle array that enable to keep particle sorted with O(log2(n)) amortized data moves. We further improve the original PMA data structure to support efficient batch data moves. Experiments show that the PMA can outperform a compact sorted array for up to 50% element moves.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Marie Durand Connect in order to contact the contributor
Submitted on : Friday, December 7, 2012 - 2:19:24 PM
Last modification on : Tuesday, August 2, 2022 - 4:24:43 AM
Long-term archiving on: : Monday, March 11, 2013 - 11:35:40 AM


Files produced by the author(s)


  • HAL Id : hal-00762593, version 1


Marie Durand, Bruno Raffin, François Faure. A Packed Memory Array to Keep Moving Particles Sorted. VRIPHYS 2012 - 9th Workshop on Virtual Reality Interaction and Physical Simulation, Dec 2012, Darmstadt, Germany. pp.69-77. ⟨hal-00762593⟩



Record views


Files downloads