A Packed Memory Array to Keep Moving Particles Sorted

Marie Durand 1, * Bruno Raffin 1, * François Faure 2, *
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Jan Bender and Arjan Kuijper and Dieter W. Fellner and Eric Guérin. VRIPHYS - Ninth Workshop on Virtual Reality Interactions and Physical Simulations, Dec 2012, Darmstadt, Germany. The Eurographics Association, pp.69-77, 2012, Ninth Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS)
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-00762593
Contributeur : Marie Durand <>
Soumis le : vendredi 7 décembre 2012 - 14:19:24
Dernière modification le : jeudi 11 janvier 2018 - 06:23:42
Document(s) archivé(s) le : lundi 11 mars 2013 - 11:35:40

Fichiers

vriphys2012.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00762593, version 1

Citation

Marie Durand, Bruno Raffin, François Faure. A Packed Memory Array to Keep Moving Particles Sorted. Jan Bender and Arjan Kuijper and Dieter W. Fellner and Eric Guérin. VRIPHYS - Ninth Workshop on Virtual Reality Interactions and Physical Simulations, Dec 2012, Darmstadt, Germany. The Eurographics Association, pp.69-77, 2012, Ninth Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS). 〈hal-00762593〉

Partager

Métriques

Consultations de la notice

731

Téléchargements de fichiers

969