Does anyone know of an implementation in CUDA of a 3D Voronoi Diagram? If its a Delaunay diagram I will be happy to. As always, I do not want to reinvent the wheel (that is not funny at all ;) ).
I’ve been looking through some papers in the area and I found some, very nice, approaches but I am not sure they can be implemented properly -maximum performance- over CUDA (to many cases to be able to assure that every thread in one warp is executing the same instruction).
If anyone has any information or reference it will be actually very appreciated, it’s estrange that if so paper or program exists is not already into the Nvidia database since this is a very popular algorithm.
I’ve had a 2D case but implemented primitively, not with Delaunay triangulation or such. Just a per-pixel search for the closest point. So it had a O(N*P) time complexity where N is the number of pixels (resolution) and P the number of points/centroids.
It was fast though (about 100-120x faster than a dual-core CPU imlpementation on a GF 8800). Tell me if you’re interested.
Thanks for your offer, I will try to implement a 2D Voronoi/Delaunay as a first step but I was looking in a less image approach so the input will be a list of points and the output a graph. But sure if I have problems will doing it I will ask for your code ;)
The lack of answers mean that there is not such thing or that people just doesn’t care? hehe
After some weeks of work (I have a very boring life, so what?) I’ve found this paper A divide-and-conquer algorithm for computing 4-dimensional convex hulls at (http://www.springerlink.com/content/f876w08k2g063614/).
At my university do not have the paper version (1988!!) or access to the electronic content. Had anyone read it? Does anyone if this can be implemented in CUDA? (the DeWall algorithm is not very suitable for example).
I was wondering whether you have eventually come across an implementation in CUDA of a 3D Voronoi Diagram or a Delaunay Triangulation algorithm?
That would really be helpful for me…