Parallel Voronoi Computation for Physics-Based Simulations

Julio Toss 1, 2 João Comba 1 Bruno Raffin 2
2 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Voronoi diagrams are fundamental data structures in computational geometry, with applications in such areas as physics-based simulations. For non-Euclidean distances, the Voronoi diagram must be performed over a grid-graph, where the edges encode the required distance information. Th e major bottleneck in this case is a shortest path algorithm that must be computed multiple times during the simulation. We present a GPU algorithm for solving the shortest path problem from multiple sources using a generalized distance function. Our algorithm was designed to leverage the grid-based nature of the underlying graph that represents the deformable objects. Experimental results report speed-ups up to 65× over a current reference sequential method.
Type de document :
Article dans une revue
Computing in Science and Engineering, Institute of Electrical and Electronics Engineers, 2016, Visualization Corner, 18 (3), pp.88. 〈http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7478505〉. 〈10.1109/MCSE.2016.52〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01317549
Contributeur : Julio Toss <>
Soumis le : samedi 22 octobre 2016 - 15:11:01
Dernière modification le : jeudi 9 août 2018 - 14:42:02
Document(s) archivé(s) le : vendredi 3 février 2017 - 12:16:42

Fichiers

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

Identifiants

Citation

Julio Toss, João Comba, Bruno Raffin. Parallel Voronoi Computation for Physics-Based Simulations. Computing in Science and Engineering, Institute of Electrical and Electronics Engineers, 2016, Visualization Corner, 18 (3), pp.88. 〈http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7478505〉. 〈10.1109/MCSE.2016.52〉. 〈hal-01317549v2〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

288