Skip to Main content Skip to Navigation
Journal articles

Parallel Voronoi Computation for Physics-Based Simulations

Julio Toss 1, 2 João Comba 1 Bruno Raffin 2
2 DATAMOVE [2016-2019] - Data Aware Large Scale Computing [2016-2019]
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 : Tuesday, October 6, 2020 - 4:20:05 PM
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. ⟨10.1109/MCSE.2016.52⟩. ⟨hal-01317549v2⟩

Share

Metrics

Record views

402

Files downloads

822