3D Voronoi diagram Do not want to reinvent the wheel

Hey,

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.

Thanks!

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

Thanks!!!

I just found this conference slides, [url=“http://moodle.sc-education.org/mod/resource/view.php?id=338”]http://moodle.sc-education.org/mod/resource/view.php?id=338[/url] as you can see they give a brute force approach to the Voronoi diagram building. Then at the last slide the speaker says: “And now Igor will tell us … …\… How to increment the speedups from 9 to 70”, anyone attend that conference called Workshop on Parallel Processing - GVSU ?

Does anyone know who Igor is, or where I can find information on that Workshop?

Thanks!

Here is one approach:
[url=“http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf”]http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf[/url]

Here is a parallel distance transform:
[url=“http://wwwcg.in.tum.de/Research/data/Publications/visapp09.pdf”]http://wwwcg.in.tum.de/Research/data/Publi...ns/visapp09.pdf[/url]

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).

Thanks!

Hi,

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…

Thanks.

Hey,

Not yet, I am working myself in doing one… is not a small or easy project because I think is doable… (I can only invest my “free” time on it).

Sorry, wish I could be more helpful (really).

Hi,

thanks! I guess I too will have to work on it myself then.

Hello,

I am about to start working on the same subject. Does anybody make any progress on this problem?

thanks

Hello,

I am about to start working on the same subject. Does anybody make any progress on this problem?

thanks