Parallel Shortest Path Algorithm for Voronoi Diagrams with Generalized Distance Functions

Abstract : Voronoi diagrams are fundamental data structures in computational geometry with applications on different areas. Recent soft object simulation algorithms for real time physics engines require the computation of Voronoi diagrams over 3D images with non-Euclidean distances. In this case, the computation must be performed over a graph, where the edges encode the required distance information. But excessive computation time of Voronoi diagrams prevent more sophisticated deformations that require interactive topological changes, such as cutting or stitching used in virtual surgery simulations. The major bottleneck in the Voronoi computation in this case is a shortest-path algorithm that must be computed multiple times during the deformation. In this paper, we tackle this problem by proposing a GPU algorithm of the shortest-path algorithm from multiple sources using generalized distance functions. Our algorithm was designed to leverage the grid-based nature of the underlying graph used in the simulation. Experimental results report speed-ups up to 65x over a current reference sequential method.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01026159
Contributor : Julio Toss <>
Submitted on : Friday, September 12, 2014 - 8:59:46 PM
Last modification on : Thursday, October 11, 2018 - 8:48:03 AM
Long-term archiving on : Saturday, December 13, 2014 - 10:08:07 AM

File

sibgrapi_2014.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01026159, version 1

Collections

Citation

Julio Toss, João Luiz Dihl Comba, Bruno Raffin. Parallel Shortest Path Algorithm for Voronoi Diagrams with Generalized Distance Functions. XXVII SIBGRAPI, Conference on Graphics Patterns and Images, Aug 2014, Rio de Janerio, Brazil. ⟨hal-01026159⟩

Share

Metrics

Record views

302

Files downloads

961