Fast Voronoi Diagrams and Distance Field Textures on the GPU With the Jump Flooding Algorithm

Created: 2023-02-09T17:56:32-06:00

This card pertains to a resource available on the internet.

Creates voronoi diagrams from a set of "seeds."

Seeds can be individual points or entire shapes. Voronoi cells and distance transforms will be centered around whatever symbols are fed in to the algorithm but single pixels are common.

Jump filling is an approximation; it will make small errors compared to brute force but is very quick for GPUs to compute.

Algorithm

Steps: If you have an NxN output texture then there are log2(N) steps in total.

Step size: the step size for each group is 2^(log2(N) - pass - 1) calculated at the start of each pass

K: the step size

Initialize all pixels to some score representing no value (such as fully black.)
Write seeds to the pixel map. If you have floating point pixels then you can stuff the X coordinate in the Red channel and the Y coordinate in the Green channel.
For each pixel perform a sampling on all pixels of a 3x3 grid, determine which one has the lowest distance score, and assign the pixel to that value.
Repeat while going down step sizes each time. You go from N/2, N/4, N/8, eventually to 1, such that the step size decreases (halves) each pass.

Offset kernel:

(-K.0, -K.0), (0.0, -K.0), (K.0, -K.0),
(-K.0,  0.0), (0.0,  0.0), (K.0,  0.0),
(-K.0,  K.0), (0.0,  K.0), (K.0,  K.0)

The result is a texture map where each pixel has been replaced with coordinate pixels for the voronoi cell it belongs to.

This can be converted to a signed distance field by checking each pixel and replacing it with the pixel's distance to its seed coordinates.