Skip to Main content Skip to Navigation
New interface
Journal articles

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.
Complete list of metadata
Contributor : Julio Toss Connect in order to contact the contributor
Submitted on : Saturday, October 22, 2016 - 3:11:01 PM
Last modification on : Friday, July 8, 2022 - 10:10:46 AM
Long-term archiving on: : Friday, February 3, 2017 - 12:16:42 PM


Files produced by the author(s)



Julio Toss, João Comba, Bruno Raffin. Parallel Voronoi Computation for Physics-Based Simulations. Computing in Science and Engineering, 2016, Visualization Corner, 18 (3), pp.88. ⟨10.1109/MCSE.2016.52⟩. ⟨hal-01317549v2⟩



Record views


Files downloads