Skip to Main content Skip to Navigation
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 [2007-2015] - Laboratoire d'Informatique de Grenoble [2007-2015]
2 IMAGINE [2011-2015] - Intuitive Modeling and Animation for Interactive Graphics & Narrative Environments [2011-2015]
Inria Grenoble - Rhône-Alpes, LJK [2007-2015] - Laboratoire Jean Kuntzmann [2007-2015], Grenoble INP [2007-2019] - Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019]
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 metadatas

Cited literature [11 references]  Display  Hide  Download


https://hal.inria.fr/hal-00762593
Contributor : Marie Durand <>
Submitted on : Friday, December 7, 2012 - 2:19:24 PM
Last modification on : Monday, July 20, 2020 - 9:44:02 AM
Long-term archiving on: : Monday, March 11, 2013 - 11:35:40 AM

Files

vriphys2012.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00762593, version 1

Citation

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⟩

Share

Metrics

Record views

1188

Files downloads

1919