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!
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!

#1
Posted 09/23/2009 09:20 PM   
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.
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.

#2
Posted 09/24/2009 09:39 AM   
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!!!!!!
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!!!!!!

#3
Posted 09/24/2009 06:21 PM   
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 [b]Workshop on Parallel Processing - GVSU [/b]?

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

Thanks!
I just found this conference slides, http://moodle.sc-education.org/mod/resource/view.php?id=338 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!

#4
Posted 09/25/2009 05:19 PM   
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]
Here is one approach:

http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf



Here is a parallel distance transform:

http://wwwcg.in.tum.de/Research/data/Publi...ns/visapp09.pdf

#5
Posted 09/25/2009 05:47 PM   
After some weeks of work (I have a very boring life, so what?) I've found this paper [i]A divide-and-conquer algorithm for computing 4-dimensional convex hulls[/i] 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!
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!

#6
Posted 10/02/2009 05:49 PM   
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.
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.

#7
Posted 03/01/2010 10:08 AM   
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).

[quote name='ClaudiaS' post='1010003' date='Mar 1 2010, 04:08 AM']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.[/quote]
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).



[quote name='ClaudiaS' post='1010003' date='Mar 1 2010, 04:08 AM']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.

#8
Posted 03/01/2010 04:16 PM   
Hi,

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


[quote name='fcsc' post='1010159' date='Mar 1 2010, 05:16 PM']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).[/quote]
Hi,



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





[quote name='fcsc' post='1010159' date='Mar 1 2010, 05:16 PM']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).

#9
Posted 03/02/2010 12:21 PM   
[quote name='ClaudiaS' post='1010754' date='Mar 2 2010, 02:21 PM']Hi,

thanks! I guess I too will have to work on it myself then.[/quote]

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

thanks
[quote name='ClaudiaS' post='1010754' date='Mar 2 2010, 02:21 PM']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

#10
Posted 10/24/2010 07:18 AM   
[quote name='ClaudiaS' post='1010754' date='Mar 2 2010, 02:21 PM']Hi,

thanks! I guess I too will have to work on it myself then.[/quote]

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

thanks
[quote name='ClaudiaS' post='1010754' date='Mar 2 2010, 02:21 PM']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

#11
Posted 10/24/2010 07:18 AM   
Scroll To Top