Voronoi

F1 Voronoi output, raised to a power of 2.

Voronoi noise, also known as Cellular noise, or Worley noise is a type of noise based on cells, where each cell contains a single point offset by a random vector. For each pixel in the cell we obtain the distance to this point, and compare it with distances to the 8 other points in neighbouring cells. It usually outputs the smallest distance found, aka the distance to the closest point, known as F1 Voronoi. Outputting the distance to the second closest points would be referred to as F2 Voronoi, third closest would be F3, etc.

We can use different methods of computing distance, such as:

  • Euclidean (linear) distance, the “normal” straight line distance between two points, aka the distance function/node : sqrt(a*a + b*b)
  • Manhattan distance : abs(a) + abs(b)
  • Chebyshev distance, based on how a king moves in chess : max(abs(a), abs(b)
  • Minkowski distance, a generalised version of the above distances, which also allows blending between them : pow(pow(abs(a), n) + pow(abs(b), n)), 1 / n), where n=1 gives Manhattan, n=2 gives Euclidean, while higher values give Chebyshev (mathematically, as n approaches infinity, but in practice, anything above n=10 is basically indistinguishable, and too high values can cause artefacts).

In all of the above, a = ∆x = x2 – x1; b = ∆y = y2 – y1; where two points have the coordinates (x1, y1) and (x2, y2).

Shadergraph has a built-in Voronoi node, which outputs F1 Voronoi (the distance to the closest point, using the normal Euclidean distance). The generated code by this node looks as follows:

inline float2 unity_voronoi_noise_randomVector (float2 UV, float offset)
{
    float2x2 m = float2x2(15.27, 47.63, 99.41, 89.98);
    UV = frac(sin(mul(UV, m)) * 46839.32);
    return float2(sin(UV.y*+offset)*0.5+0.5, cos(UV.x*offset)*0.5+0.5);
}

void Unity_Voronoi_float(float2 UV, float AngleOffset, float CellDensity, out float Out, out float Cells)
{
    float2 g = floor(UV * CellDensity);
    float2 f = frac(UV * CellDensity);
    float3 res = float3(8.0, 0.0, 0.0);

    for(int y=-1; y<=1; y++)
    {
        for(int x=-1; x<=1; x++)
        {
            float2 lattice = float2(x,y);
            float2 offset = unity_voronoi_noise_randomVector(lattice + g, AngleOffset);
            float d = distance(lattice + offset, f);
            if(d < res.x)
            {
                res = float3(d, offset.x, offset.y);
                Out = res.x;
                Cells = res.y;
            }
        }
    }
}

Assuming this shader is being applied to a flat plane or quad, the UVs will span from 0 to 1 along the plane. By multiplying this by our CellDensity value and then taking the floor, we obtain the integer coordinates along the UVs producing a grid of cells, which is contained in the variable named g.

We also obtain a variable, f, which is similar to g but uses the frac function rather than floor. Where floor obtains the integer component, the frac function returns only the decimal component of the float.

We then use a loop between -1 and 1 for both the x and y axis, to loop through neighbouring cells, where the position of the cell is specified by lattice + g. The unity_voronoi_noise_randomVector function is used with this cell position along with a AngleOffset variable to produce a float2 offset vector pointing in random direction.

The lattice value (the cell offset) added with the random vector offset now obtains the local position of a random point inside that cell, which we can compare with f, the pixel’s local position inside the cell, to obtain the distance between them. We can then store this in res.x, checking whether it is smaller and replacing it to find the smallest distance in the loop.

For a more in-depth explanation of how Voronoi is produced, including some great interactive code examples, take a look at this book of shaders page.

Voronoi Edges

While the F1 output can be useful for some materials, such as ice, hammered metal, or using it for animated water caustics like in this Water Shader Breakdown, it would also be useful if we could obtain the harsh shapes or edges the Voronoi noise creates – for cracked ground textures for example.

This can’t be done using the Voronoi node though – In order to achieve this we need to write our own Voronoi function using the Custom Function node. (Note that this node is only available in newer versions of shadergraph. You may need to update the LWRP/HDRP package to obtain access to it. You can do this via the Package Manager, just click on the package and a “Show more versions” link should appear. Note that these versions may not be “verified” to work so you may encounter some bugs. There was also an older way of adding custom functions using the CodeFunctionNode method as explained here but this isn’t available in the newer 2019 versions).

If we place the Custom Function node and click the cog, we can set the Type to File or String. If set to String you are able to write the code directly in the source box – this is fine for short functions but I’d recommend using a file instead. The path to the source should be something along the lines of “Assets/Folder/file.hlsl”, depending on where the file is placed in your Assets folder.

The easiest way to achieve the edges of the Voronoi is to obtain F2 Voronoi and subtract F1 Voronoi from it. This method isn’t very accurate and can look a little strange for some cells – but it is faster. A more accurate approach is to use two loops, one where you calculate the closest cell, and the second where you calculate the closest edge between that closest cell and it’s neighbouring cells.

Before going into the code on how to generate the Voronoi edges, here is a few images showing the results of these two methods. You can clearly see some inaccuracies in some of the cells in the F2-F1 version, and it produces more rounded cells when put into a Step function/node.

Voronoi Edges ( Fast, F2-F1 )
Voronoi Edges ( Accurate, 2 Loops )

Voronoi Edges (F2-F1)

In order to obtain F2 Voronoi, we can simply alter the Voronoi node slightly. In the original code they have a “float3 res” value (which I assume is short for result), where res.x keeps track of the current closest point in the loop. They use res.y and res.z to keep track of the random vector used to offset the point inside the cell. But res.z isn’t actually used as an output, so I’ve instead made res.y keep track of the second closest point, and res.z be the first component of that random vector.

I’ve also swapped the distance function out for a dot product instead – which is obtaining the distance squared, avoiding doing the sqrt part inside the loop for better performance.

inline float2 voronoi_noise_randomVector (float2 UV, float offset){
    float2x2 m = float2x2(15.27, 47.63, 99.41, 89.98);
    UV = frac(sin(mul(UV, m)) * 46839.32);
    return float2(sin(UV.y*+offset)*0.5+0.5, cos(UV.x*offset)*0.5+0.5);
}

void Voronoi_float(float2 UV, float AngleOffset, float CellDensity, out float2 Out, out float Cells) {
	float2 g = floor(UV * CellDensity);
	float2 f = frac(UV * CellDensity);
	float3 res = float3(8.0, 8.0, 8.0);

	for(int y=-1; y<=1; y++){
		for(int x=-1; x<=1; x++){
			float2 lattice = float2(x, y);
			float2 offset = voronoi_noise_randomVector(g + lattice, AngleOffset);
			float2 v = lattice + offset - f;
			float d = dot(v, v);
			
			if(d < res.x){
				res.y = res.x;
				res.x = d;
				res.z = offset.x;
			}else if (d < res.y){
				res.y = d;
			}
		}
	}

	Out = float2(sqrt(res.x), sqrt(res.y));
	Cells = res.z;
}

Voronoi Edges (2 Loops)

The more accurate method uses a second loop to obtain the smallest distance to the edge.

inline float2 voronoi_noise_randomVector (float2 UV, float offset){
    float2x2 m = float2x2(15.27, 47.63, 99.41, 89.98);
    UV = frac(sin(mul(UV, m)) * 46839.32);
    return float2(sin(UV.y*+offset)*0.5+0.5, cos(UV.x*offset)*0.5+0.5);
}

void Voronoi_float(float2 UV, float AngleOffset, float CellDensity, out float Out, out float Cells) {
	float2 g = floor(UV * CellDensity);
	float2 f = frac(UV * CellDensity);
	float2 res = float2(8.0, 8.0);
	float2 ml = float2(0,0);
	float2 mv = float2(0,0);

	for(int y=-1; y<=1; y++){
		for(int x=-1; x<=1; x++){
			float2 lattice = float2(x, y);
			float2 offset = voronoi_noise_randomVector(g + lattice, AngleOffset);
			float2 v = lattice + offset - f;
			float d = dot(v, v);

			if(d < res.x){
				res.x = d;
				res.y = offset.x;
				mv = v;
				ml = lattice;
			}
		}
	}

	Cells = res.y;

	res = float2(8.0, 8.0);
	for(int y=-2; y<=2; y++){
		for(int x=-2; x<=2; x++){
			float2 lattice = ml + float2(x, y);
			float2 offset = voronoi_noise_randomVector(g + lattice, AngleOffset);
			float2 v = lattice + offset - f;

			float2 cellDifference = abs(ml - lattice);
			if (cellDifference.x + cellDifference.y &gt; 0.1){
				float d = dot(0.5*(mv+v), normalize(v-mv));
				res.x = min(res.x, d);
			}
		}
	}

	Out = res.x;
}

The majority of this function is based on this article. However I also added the cellDifference part based on the example from here. (Technically if we are in the closest cell, then v-mv should be equal to 0, which causes normalize(0). I believe this returns infinity so due to the min check it should be ignored, but this kind of behaviour seems a bit sketchy to me. This could potentially lead to unexpected results on different platforms, so the added if statement is just to avoid this).

Check both of those articles for details on how this method works, they provide slightly different code but the general idea is the same. The main difference is the first article it has the second loop centered on the cell containing the closest point and values of -2 and 2 in the loop, while the other article has an identical second loop to it’s first, with values of -1 and 1. This is likely an accuracy vs performance thing.

Sources & Other Resources :
https://docs.unity3d.com/Packages/com.unity.shadergraph@6.7/manual/Voronoi-Node.html
https://thebookofshaders.com/12/
http://www.rhythmiccanvas.com/research/papers/worley.pdf
https://www.iquilezles.org/www/articles/voronoilines/voronoilines.htm
https://www.ronja-tutorials.com/2018/09/29/voronoi-noise.html
https://www.alanzucconi.com/2015/02/24/to-voronoi-and-beyond/
https://www.gamedev.net/forums/topic/576541-voronoi–worley-noise-knowlege-dump/

Advertisements