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, INPG - Institut National Polytechnique de Grenoble
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 : Thursday, October 11, 2018 - 8:48:03 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 - Ninth Workshop on Virtual Reality Interactions and Physical Simulations, Jan Bender and Arjan Kuijper and Dieter W. Fellner and Eric Guérin, Dec 2012, Darmstadt, Germany. pp.69-77. ⟨hal-00762593⟩

Share

Metrics

Record views

1119

Files downloads

1633