A Packed Memory Array to Keep Moving Particles Sorted (English)

How to get this document?

Download
Commercial Copyright fee: €14.50 Basic fee: €4.00 Total price: €18.50
Academic Copyright fee: €4.50 Basic fee: €2.00 Total price: €6.50

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(log2(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.

  • Title:
    A Packed Memory Array to Keep Moving Particles Sorted
  • Author / Creator:
  • Published in:
  • Publisher:
    The Eurographics Association
  • Place of publication:
    Postfach 2926, 38629 Goslar, Germany
  • Year of publication:
    2012
  • Size:
    9 pages
  • ISBN:
  • DOI:
  • Type of media:
    Conference paper
  • Type of material:
    Electronic Resource
  • Language:
    English
  • Source:
  • Export:
  • Share:
  • ORKG:

Table of contents conference proceedings

The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.

1
An Implicit Tensor-Mass Solver on the GPU for Soft Bodies Simulation
Faure, Xavier / Zara, Florence / Jaillet, Fabrice / Moreau, Jean-Michel | 2012
11
Mapping Volumetric Meshes to Point-based Motion Models
Jund, Thomas / Allaoui, Ali / Darles, Emmanuelle / Skapin, Xavier / Meseure, Philippe / Luciani, Annie | 2012
21
Efficient Cloth Simulation Using an Adaptive Finite Element Method
Bender, Jan / Deul, Crispin | 2012
31
Physics-based Augmented Reality for 3D Deformable Object
Haouchine, Nazim / Dequidt, Jérémie / Kerrien, Erwan / Berger, Marie-Odile / Cotin, Stéphane | 2012
39
Fast Simulation of Inextensible Hair and Fur
Müller, Matthias / Kim, Tae-Yong / Chentanez, Nuttapong | 2012
45
Real-time Hair Simulation with Efficient Hair Style Preservation
Han, Dongsoo / Harada, Takahiro | 2012
53
High-Resolution Simulation of Granular Material with SPH
Ihmsen, Markus / Wahl, Arthur / Teschner, Matthias | 2012
61
An Efficient Surface Reconstruction Pipeline for Particle-Based Fluids
Akinci, Gizem / Akinci, Nadir / Ihmsen, Markus / Teschner, Matthias | 2012
69
A Packed Memory Array to Keep Moving Particles Sorted
Durand, Marie / Raffin, Bruno / Faure, François | 2012
79
Real-Time Motion Synthesis for Multiple Goal-Directed Tasks Using Motion Layers
Mousas, Christos / Newbury, Paul | 2012
87
Synthesizing Balancing Character Motions
Kenwright, Ben | 2012
97
Generic Spine Model with Simple Physics for Life-Like Quadrupeds and Reptiles
Karim, Ahmad Abdul / Meyer, Alexandre / Gaudin, Thibaut / Buendia, Axel / Bouakaz, Saida | 2012
107
Bézier Shell Finite Element for Interactive Surgical Simulation
Golembiovský, Tomá¹ / Duriez, Christian | 2012
117
Efficient Breast Deformation Simulation
Harz, Markus T. / Georgii, Joachim / Wang, Lei / Schilling, Kathy / Peitgen, Heinz-Otto | 2012
127
OCTAVIS: An Easy-to-Use VR-System for Clinical Studies
Dyck, Eugen / Zell, Eduard / Kohsik, Agnes / Grewe, Philip / Winter, York / Piefke, Martina / Botsch, Mario | 2012
137
Policies for Goal Directed Multi-Finger Manipulation
Andrews, Sheldon / Kry, Paul G. | 2012
147
3D Mobility Learning and Regression of Articulated, Tracked Robotic Vehicles by Physics-based Optimization
Papadakis, Panagiotis / Pirri, Fiora | 2012
Feedback