4 ms·

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 "

by exDM69 11y ago

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.

shultays 11y ago
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.
nraynaud 11y ago
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/shaders/distance.frag 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_voronoi.html 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.
- exDM69 11y ago
  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.
mrec 11y ago
Heh, I remember this technique from the OpenGL Red Book, at least 15-20 years ago. http://www.glprogramming.com/red/chapter14.html#name19 http://www.glprogramming.com/red/chapter14.html#name19
- exDM69 11y ago
  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.
  - mrec 11y ago
    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.)
    - exDM69 11y ago
      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?
      - mrec 11y ago
        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.

by exDM69 11y ago

shultays 11y ago

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.

nraynaud 11y ago

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/shaders/distance.frag 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_voronoi.html 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.

exDM69 11y ago
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.

mrec 11y ago

Heh, I remember this technique from the OpenGL Red Book, at least 15-20 years ago. http://www.glprogramming.com/red/chapter14.html#name19 http://www.glprogramming.com/red/chapter14.html#name19

exDM69 11y ago
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.
- mrec 11y ago
  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.)
  - exDM69 11y ago
    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?
    - mrec 11y ago
      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.