News for hackers. Stuff that matters.
Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @04:07AM (#11495008)
There's a much faster O(n) method for doing Voronoi diagrams on the GPU by taking advantage of the depth buffer. It's so simple that it gives you one of those "why didn't I think of this earlier" moments. I learned it from the old school demoscene guys at work...

    0. Set up orthographic projection
    1. Enable depth testing
    2. For each "seed" point, draw an "infinite" cone all the way from the near to the far clipping plane
    3. Shade with solid colors.
That's it.

The depth testing will only leave fragments of the cone that the corresponding pixel is closest to. If you need better precision, draw the "cone" by making a full screen quad and use the fragment shader to set depth (gl_FragDepth) according to distance from seed point (or just use enough vertices in the cones).

If you change the circular cone to a rectangular-based pyramid shape, you'll get Voronoi-type diagrams but with a different metric (manhattan distance?). Turn the rectangle 45 degrees to make a diamond shaped base and you have yet another metric.

Re:Voronoi Diagrams on the GPU by mrec on Thursday April 14, 2016 @07:42AM (#11495786)
Heh, I remember this technique from the OpenGL Red Book, at least 15-20 years ago.

http://www.glprogramming.com/red/chapter14.html#name19

Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @08:25AM (#11496032)
Cool! I've of course read the Redbook back in the day (I think I still have it printed out in my shelf) but for some reason I've missed that chapter.

I didn't quite get what you need the stencil buffer for in that technique.

Re:Voronoi Diagrams on the GPU by mrec on Thursday April 14, 2016 @09:39AM (#11496555)
The stencil buffer provides a boolean mask for the regions you care about, making it easy to draw them in flat color with a subsequent pass. I can't see a way to do that easily with depth information only.

(Plus, it was traditional to combine 24-bit depth with 8-bit stencil in the same buffer, so stencil writes were basically free if you're writing depth anyway.)

Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @02:16PM (#11499149)
Yeah, that's pretty similar to the stenil-then-cover technique used in vector graphics.

But what advantage does a two pass stencil technique have over just writing to the color buffer in the first pass?

Re:Voronoi Diagrams on the GPU by mrec on Thursday April 14, 2016 @07:02PM (#11500943)
Oh, I see what you mean. Good question. I suppose it might have been more efficient to avoid multiple colour buffer overdraws (since you're drawing a fullscreen quad for each seed point, albeit a depth-tested one). And you could render the depth+stencil buffer once then reuse it to highlight different regions, e.g. on mouseover.

But you're right, it doesn't sound massively compelling. And the traditional 24depth+8stencil buffer format would limit you to a maximum of 256 regions, which could easily cramp your style.

Re:Voronoi Diagrams on the GPU by shultays on Thursday April 14, 2016 @10:02AM (#11496748)
Article just does logn (n is dimension of input texture) passes on the render target and that is it. complexity is independent of number of seeds.
Re:Voronoi Diagrams on the GPU by nraynaud on Thursday April 14, 2016 @04:16AM (#11495037)
well, if you're doing that, then just use the distance function, at least you've got a perfectly circular cone, and you don't get tricked by the maximum distance of the cone.

the complexity is num pixels*num entities.

implementation here: https://github.com/nraynaud/webgcode/blob/gh-pages/webapp/sh...

I would gladly show the result here: http://nraynaud.github.io/webgcode/various_tests/test_vorono... but it looks like Chrome removed PathSegList that the SVG library was using internally

edit: it still works in firefox, it extracts the voronoi diagram, the medial axis, then does a subtraction on the medial axis (internal offset of the original polygon), then a minimum threshold (mickey ears for pocketting in milling), then a reconstruction of the polygon from the altered medial axis.

Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @06:25AM (#11495470)
Your pixel shader implementation is quite clean and simple. But the method I described doesn't rely on shaders at all, it uses the fixed function triangle rasterization and depth testing. It has different performance characteristics. That method is also of historical interest because it works (and is fast) also on pre-shader graphics accelerators.