I recently showed some Voronoi experiments stuff on twitter, so here is a write up off what’s happening here

Voronoi 101

A voronoi diagram describes the partition of space by a set of seeds. Each seed expands it’s boundaries, until it reaches the boundary of another seed.

There are many ways to compute a Voronoi diagram. Usually you can get an exact geometric result with Fortunes algorithm or by exploiting the hidden links between the convex hull, the Delaunay-Triangulation and the Voronoi diagramm.

But I will use a simple 64x64 grid, further called Voronoi map. This will not lead to an actual precise geometric representation, but something that is (hopefully) understandable and easier to modify.

Before we go into detail, a little primer on Burst and Jobs.

Burst and Job-System

For our Voronoi map, we are going to iterate over every pixel. Most straightforward is a for loop:

for(int i = 0; i < vornoiMap.Length; i++){
    // compute Voronoi
}

But we are dealing with lots of pixels here. Even at a resolution of 64x64, this means 4096 pixels, multiplied by the number of sites. Therefore, are going to use Burst and Jobs. The Unity Job system allows us to split our for-loop across multiple threads.

In pseudocode:

for batch in allBatches
    new Thread() {
        for(int i = 0; i < batch.Length; i++){
            // compute voronoi
        }
    }

On a machine with 4 CPU-Cores, this can mean a performance improvement of up to 4x.

The second thing we are going to use is the Burst Compiler. Very roughly speaking, it optimizes the bytecode generated by the C# compiler even further by utilizing special CPU instructions and deeper analysis of the code.

Burst however is not applied onto our whole code. Instead, it is meant to be applied on single Jobs. A further requirement is the absence of any managed variables. In practice, that means we can only use structs and basic variable types such as float or int.

Here is an (incomplete) table for the correct equivalent:

Also, we must manage some memory on our own. This means that we have to call .Dispose() on NativeArray/List<> struct once we don’t need it anymore.

The Algorithm

Let’s jump back into Voronoi land and code the job that generates the Voronoi Map. For this section I will let the code comments speak, as I’ve already explained the basic idea of the Voronoi diagram. Also note here that I explicitly tell Unity if a variable is read/write only, which makes the purpose clearer for both the compiler and any potential reader. 😉

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

[BurstCompile]
struct RenderVoronoi : IJobParallelFor{
    // the data that we are going to use
    [ReadOnly] public int2 resolution; // the resolution in cells/pixels
    [ReadOnly] public float2 cellsMinWs, cellsMaxWs; // world space boundaries
    [ReadOnly] public NativeArray<float3> sites; // list of the position of all sites
    [ReadOnly] public float ExpandLimit; //limits the expansion of sites, good for visualizations
    // the data that we are going to put out
    [WriteOnly] public NativeArray<int> VoronoiMap; // output position map
    // how we are going to compute the data
    public void Execute(int pixelIndex){
        // figure out the location of the cell in world space
        float2 pixelPositionWs;
        // first, we turn the pixelIndex into a 2D space coordinate...
        pixelPositionWs.x = pixelIndex % resolution.x;
        pixelPositionWs.y = pixelIndex / resolution.x;
        //note: it would be actually faster to stay in pixel coordinates from here on and convert the sites into pixel coordinates
        // ...now normalized position into a range [0,1], so that 0 = cellsMinWs and 1 = cellsMaxWs...
        pixelPositionWs.x /= resolution.x; 
        pixelPositionWs.y /= resolution.y;
        // ...and transform into world space
        pixelPositionWs = math.lerp(cellsMinWs, cellsMaxWs, pixelPositionWs);

        // keep track of the shortest distance
        float closestSiteDistance = ExpandLimit; // if you don't want to limit, use float.PositiveInfinty
        int closestSiteId = -1;
        for (int siteId = 0; siteId < sites.Length; siteId++){
            float2 sitePosition = sites[siteId].xy; 
            float siteDistance = math.distance(sitePosition, pixelPositionWs); // compute the distance between cell and site
            if (siteDistance < closestSiteDistance) {
                // if the curret site is closer than the previous one, remember it
                closestSiteDistance = siteDistance; 
                closestSiteId = siteId;
            }
        }
        VoronoiMap[pixelIndex] = closestSiteId; // write the result back
    }
}

You can find the entire implementation in the gist at the very end of this post (version without noise).

Bring in the Noise

In the second tweet, I added noise to make the whole thing more interesting.

Anyway, Noise in our case is applied like this (inside the RenderVoronoi Job):

float noise = math.abs(Unity.Mathematics.noise.snoise((sitePosition + pixelPositionWs) * NoiseTiling));
noise *= NoiseScale;
siteDistance += noise;

Note that I use the sum of sitePosition and pixelPositionWs. This is important, because if we just use the pixel position, the noise would be the same for all site and therefore would have no effect.

Source Code