Parallel Shortest Path Algorithm for Voronoi Diagrams with Generalized Distance Functions

Julio Toss, Joao Comba, Bruno Raffin
Institute of Informatics, Federal University of Rio Grande do Sul, UFRGS, Porto Alegre – RS, Brazil
XXVII SIBGRAPI, Conference on Graphics Patterns and Images, 2014




   title={Parallel Shortest Path Algorithm for Voronoi Diagrams with Generalized Distance Functions},

   author={Toss, Julio and Comba, Jo{\~a}o, Luiz Dihl and Raffin, Bruno},

   keywords={Voronoi Diagram; GPGPU; Parallel Programming; Physics Based Simulation},


   affiliation={Instituto de Inform{‘a}tica da UFRGS – UFRGS , MOAIS – INRIA Grenoble Rh{^o}ne-Alpes / LIG Laboratoire d’Informatique de Grenoble},

   booktitle={XXVII SIBGRAPI, Conference on Graphics Patterns and Images},

   address={Rio de Janerio, Br{‘e}sil},

   audience={internationale },





Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: