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 metadatas

https://hal.inria.fr/hal-01317549
Contributor : Julio Toss <>
Submitted on : Saturday, October 22, 2016 - 3:11:01 PM
Last modification on : Thursday, October 11, 2018 - 8:48:05 AM
Long-term archiving on : Friday, February 3, 2017 - 12:16:42 PM

Files

VizCorner.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

313

Files downloads

470