Help me understand the voronoi shader

Question

I am trying to understand the voronoi shader implemented in the Book of Shaders in the Tiling and iteration section: https://thebookofshaders.com/12/

Specifically how do these lines calculate the distance from a point to its neighboring tile's point:

// Random position from current + neighbor place in the grid
vec2 point = random2(i_st + neighbor);
vec2 diff = neighbor + point - f_st;

// Distance to the point
float dist = length(diff);

// Keep the closer distance
m_dist = min(m_dist, dist);

Specifically how is the diff calculation working? I would have expected i_st to reappear there.

Answer 1

1) Scale the texture coordinates from [0,1]x[0,1] -> [0,3]x[0,3]. It works with higher integer scales as well. This creates an imaginary 3x3 tiles grid.

st *= 3.;

2) Split the upscaled texture coordinates into the integer part and its float reminder.

vec2 i_st = floor(st); //the tile coords of the fragment - an integer pair {0,1,2}x{0,1,2}
vec2 f_st = fract(st); //fragment coords within the tile - a float vec2 [0,1]x[0,1]

//e.g. let's take
//  st == vec2(1.1,1.7)
//  i_st == vec2(1.,1.)
//  f_st == vec2(.1,.7)

Now st == i_st + f_st holds.

3) In order to avoid terms confusion I will call the points that build the Voronoi cells Voronoi points. Each of the 9 tiles has one Voronoi point inside to produce a Voronoi cell. So there will be 9 Voronoi cells visible in the resulting texture.

The main hack here is to have this regular 3x3 tiles grid with the same amount of Voronoi points and randomize their positions only within the respective tile. So the distribution will be pseudo-even. You give up irregular distributions by this assumption, e.g. all points grouped in the upper-left corner, but such arrangements are highly unlikely to result from biologic processes that the cellular noise tries to mimic.

Since random2 is deterministic, it will return the same vec2 each time you enter the same i_st, so for a fixed i_st it will stay constant across all fragments.

vec2 point = random2(i_st); //pick the Voronoi point, e.g. vec2(.6,.4)

The global position of the picked Voronoi point is in fact i_st + point.

4) Take the distance to the Voronoi point inside of the current tile as the initial minimum distance.

vec2 diff = point - f_st //e.g. vec2(.6,.4) - vec2(.1,.7) == vec2(.5,-.3)
float dist = length(diff); //e.g.0.583 

5) So you know that there is exactly one Voronoi point in each cell, thus by simple geometric means you can prove that you need to check only the direct neighbors. You need to test if any of the neighboring tiles has a Voronoi point closer to the current fragment than the Voronoi point from 4). Two loops iterate over all 3x3 neighborhood of the current tile. It is much easier to do that relatively {-1, 0, 1}x{-1, 0, 1} instead of using absolute numbers {i_st.x-1, i_st.x, i_st.x+1}x{i_st.y-1, i_st.y, i_st.y+1}. Moreover, we know that each tile is 1x1 in size.

for (int y= -1; y <= 1; y++) {
    for (int x= -1; x <= 1; x++) {
        // relative neighbor coordinates will be sufficient
        // this is the integer part indicating the neighboring tile coordinates
        vec2 neighbor = vec2(float(x),float(y)); //e.g. vec2(-1., 1)

        //to be continued

6) Now you will need to compute the absolute coordinates of neighboring tile to obtain its Voronoi point consistently across all fragments.

        //the global neighbor tile coordinates are neighbor + i_st 
        vec2 point = random2(i_st + neighbor); //note that this is a local scope variable

        //to be continued

7) And now the most interesting step for you, computing the distance to the neighboring Voronoi point

        //neighbor: relative tile coords, e.g. vec2(-1., 1.)
        //point:    Voronoi point inside of the neighboring tile e.g. vec2(0.9, 0.2)
        //f_st:     current fragment position within its home tile,
        //          e.g. when st == vec2(1.1, 1.7) then f_st == vec2(.1,.7)

        vec2 diff = neighbor + point - f_st;

        //to be continued

The example values yield:

neighbor + point: vec2(-1.,1.) + vec2(0.9, 0.2) == vec2(-0.1, 1.2)

That is the relative position of the neighboring tile Voronoi point. Relative means **with respect to the lower-left corner of the current fragment's tile. The same relative coordinates apply to f_st and also to point from 3).

(neighbor + point) - f_st: vec2(-0.1, 1.2) - vec2(.1,.7) == vec2(-.2,.5)

This is shorter distance (0.538 vs. previous 0.583) so for the example positions the Voronoi point from the upper left cell is closer.

8) The rest is pretty straight forward. Compute the magnitude of the diff vector and keep the minimum.

        float dist = length(diff); //distance to the neighboring Voronoi point

        m_dist = min(m_dist, dist); //remember the minimum of distances
    }
}

I hope this will help you to understand that. The main simplification is the switch to relative coordinates as described in 7).

• Looking at the code I see that the middle tile (current fragment tile) will be evaluated twice. This can be reduced by omiting step 4) initializing dist to 2*sqrt(2) which is very roughly 3. That is the length of the diagonal of two cells - the farthest distance the current fragment st could be from one of the neighboring Voronoi points.

• Border tiles are handled in an elegant implicit way. random2 generates a Voronoi point for them as well and involves it in the minimal distance computation. So You will see 9 complete and possibly up to 16 more incomplete Voronoi cells.

Hope that helps, feel free to ask any further details.