Re:A GPU Approach to Voronoi Diagrams
by __david__ on Tuesday June 03, 2014 @06:26AM
(#7839170)
> There's no way to bail out of the loop early, at least with OpenGL ES 2.0 (WebGL) shaders. We can't break or do any sort of branching on the loop variable.
Is this true? I was recently playing around with a webgl Mandelbrot [1] and the core algorithm escapes with a break. I wrote it without thinking and it worked on my computer and the computers of the people to whom I showed it. Was this just luck that it works?
Re:A GPU Approach to Voronoi Diagrams
by jacquesm on Tuesday June 03, 2014 @07:01AM
(#7839286)
It likely just causes a rendez-vous so the threads that hit the 'break' will stop executing until those that did not hit the 'break' have reached the same point. Depending on what architecture you use this included a smaller or larger portion of the active cores.
This is the usual way in which thread divergence is dealt with in GPU land.
Re:A GPU Approach to Voronoi Diagrams
by submersible on Tuesday June 03, 2014 @07:11AM
(#7839325)
Cool. I wrote an implementation of fortune's algorithm in Unity a month or two ago and was pretty impressed at how fast some flash implementations were compared to mine. For instance, this one: http://blog.controul.com/2009/05/speedy-voronoi-diagrams-in-...
Re:A GPU Approach to Voronoi Diagrams
by nkurz on Tuesday June 03, 2014 @02:22AM
(#7838419)
It's a nifty technique, but I think that's the same approach that is discussed in the article?
That's when it hit me! Render each seed as cone pointed towards the camera in an orthographic projection, coloring each cone according to the seed's color. The Voronoi diagram would work itself out automatically in the depth buffer. That is, rather than do all this distance comparison in the shader, let OpenGL do its normal job of figuring out the scene geometry.
More interesting articles about voronoi diagrams, for those who are interested.
Is this true? I was recently playing around with a webgl Mandelbrot [1] and the core algorithm escapes with a break. I wrote it without thinking and it worked on my computer and the computers of the people to whom I showed it. Was this just luck that it works?
[1] http://caldwell.github.io/mandelbrot-html
This is the usual way in which thread divergence is dealt with in GPU land.
http://blog.alexbeutel.com/332/interactive-voronoi-diagrams-...
That's when it hit me! Render each seed as cone pointed towards the camera in an orthographic projection, coloring each cone according to the seed's color. The Voronoi diagram would work itself out automatically in the depth buffer. That is, rather than do all this distance comparison in the shader, let OpenGL do its normal job of figuring out the scene geometry.