A Packed Memory Array to Keep Moving Particles Sorted

Durand, Marie; Raffin, Bruno; Faure, François

A Packed Memory Array to Keep Moving Particles Sorted

Files

069-077.pdf (465.71 KB)

Date

2012

Authors

Durand, Marie
Raffin, Bruno
Faure, François

Publisher

The Eurographics Association

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 dificult 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 effciently keep particles sorted according to their cell index. The PMA maintains gaps in the particle array that enable to keep particle sorted with O(log<sup>2</sup>(n)) amortized data moves. We further improve the original PMA data structure to support eficient batch data moves. Experiments show that the PMA can outperform a compact sorted array for up to 50% element moves.

        @inproceedings{:10.2312/PE/vriphys/vriphys12/069-077
,
booktitle = {Workshop on Virtual Reality Interaction and Physical Simulation
},
editor = {Jan Bender and Arjan Kuijper and Dieter W. Fellner and Eric Guerin
},
title = {{A Packed Memory Array to Keep Moving Particles Sorted
}},
author = {Durand, Marie and 
Raffin, Bruno and 
Faure, François
},
year = {2012
},
publisher = {The Eurographics Association
},
ISBN = {978-3-905673-96-8
},
DOI = {/10.2312/PE/vriphys/vriphys12/069-077
}
}