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
@article{toss2013parallel,
title={Parallel Voronoi Diagram computation on scaled distance planes using CUDA},
author={Toss, Julio and Comba, Joao},
year={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
