Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Julio Toss Connect in order to contact the contributor
Submitted on : Friday, September 12, 2014 - 8:59:46 PM
Last modification on : Monday, July 25, 2022 - 3:44:18 AM
Long-term archiving on: : Saturday, December 13, 2014 - 10:08:07 AM


Files produced by the author(s)


  • HAL Id : hal-01026159, version 1


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⟩



Record views


Files downloads