10362

Parallel Voronoi Diagram computation on scaled distance planes using CUDA

Julio Toss, Joao Comba
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}

}

Download Download (PDF)   View View   Source Source   

1145

views

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

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: