A GPU Approach to Voronoi Diagrams | Hacker News Reader

A GPU Approach to Voronoi Diagrams

nullprogram.com

39 pointsnkurz7 comments

http://iquilezles.org/www/articles/smoothvoronoi/smoothvoron... http://iquilezles.org/www/articles/voronoise/voronoise.htm http://iquilezles.org/www/articles/voronoilines/voronoilines...

More interesting articles about voronoi diagrams, for those who are interested.

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

[1] http://caldwell.github.io/mandelbrot-html

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.

Or you can use this gpu only technique https://www.shadertoy.com/view/ldl3W8

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

Or you can just draw cones into the screen centered on each vertex and let the z-buffer do the dirty work...

http://blog.alexbeutel.com/332/interactive-voronoi-diagrams-...

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.

Reply on news.ycombinator.com