Parallel Voronoi Diagram computation on scaled distance planes using CUDA
Institute of Informatics – Federal University of Rio Grande do Sul (UFRGS), Av. Bento Gonalves 9500, Porto Alegre – RS – Brasil
11th Workshop on Parallel and Distributed Processing (WSPPD), 2013
Voronoi diagrams are fundamental data structures in computational geometry with several applications on different fields inside and outside computer science. This paper shows a CUDA algorithm to compute Voronoi diagrams on a 2D image where the distance between points cannot be directly computed in the euclidean plane. The proposed method extends an existing Dijkstra-based GPU algorithm to treat our 2D images as graph and then compute the shortest-paths to create each Voronoi cell. Experimental results report speed-ups up to almost 40x over current reference sequential method for Voronoi computation on non-euclidean space. This problem is a building block of the deformation engine in the SOFA physics simulation framework.
August 21, 2013 by hgpu
Your response
You must be logged in to post a comment.