Voronoi Diagrams on the GPU (2016)

Jumping Flooding Algorithm (JFA) gives very good results but you need to do a multi-pass render. If you want a single pass solution and let the GPU handle most of the work you can render cones[1] using an Orthographic view matrix. It is also super fast thanks to depth buffer optimizations.<p>[1] - <a href="https:&#x2F;&#x2F;nullprogram.com&#x2F;blog&#x2F;2014&#x2F;06&#x2F;01&#x2F;" rel="nofollow">https:&#x2F;&#x2F;nullprogram.com&#x2F;blog&#x2F;2014&#x2F;06&#x2F;01&#x2F;</a>

A really straightforward way to generate Voronoi diagrams on the GPU which works for pretty much any GPU since the late 90s is to simply draw a cone facing the viewer for each point and enable depth testing.<p>No shaders needed at all.<p><a href="https:&#x2F;&#x2F;www.researchgate.net&#x2F;figure&#x2F;PSM-2D-bitmap-truncated-Voronoi-cells-created-by-a-top-view-orthogonal-projection-of-3D_fig3_353404577" rel="nofollow">https:&#x2F;&#x2F;www.researchgate.net&#x2F;figure&#x2F;PSM-2D-bitmap-truncated-...</a>

You can compute Voronoi diagrams for each pixel of an image with distance fields in O(N) where N is the number of pixels. This is faster than the shown jump flooding algorithm, which is only O(N log N).<p>Here is an example for a CPU-based implementation: <a href="https:&#x2F;&#x2F;github.com&#x2F;983&#x2F;df" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;983&#x2F;df</a><p>It is not difficult to implement for the GPU because the algorithm can be run in parallel for each image row and column, assuming general GPU compute capability, which admittedly is still lacking in some browsers.

What are the .sk files in the repo (<a href="https:&#x2F;&#x2F;github.com&#x2F;ryankaplan&#x2F;gpu-voronoi" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;ryankaplan&#x2F;gpu-voronoi</a>)?

You can also use a similar algorithm for smoothing, but it&#x27;s rarely used because how simple it is to write a axis separated Gaussian.

Thanks, this will be useful, we voronoi chart to display faiss ivf index. <a href="https:&#x2F;&#x2F;github.com&#x2F;zilliztech&#x2F;feder" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;zilliztech&#x2F;feder</a>