<p><strong>1)</strong> 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.</p>

<pre class="lang-glsl prettyprint-override"><code>st *= 3.;
</code></pre>

<p><strong>2)</strong> Split the upscaled texture coordinates into the integer part and its float reminder.</p>

<pre class="lang-glsl prettyprint-override"><code>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)
</code></pre>

<p>Now <code>st == i_st + f_st</code> holds.</p>

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

<p>The main hack here is to have this regular 3x3 tiles grid with the same amount of <em>Voronoi points</em> 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.</p>

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

<pre class="lang-glsl prettyprint-override"><code>vec2 point = random2(i_st); //pick the Voronoi point, e.g. vec2(.6,.4)
</code></pre>

<p>The global position of the picked <em>Voronoi point</em> is in fact <code>i_st + point</code>.</p>

<p><strong>4)</strong> Take the distance to the <em>Voronoi point</em> inside of the current tile as the initial minimum distance.</p>

<pre class="lang-glsl prettyprint-override"><code>vec2 diff = point - f_st //e.g. vec2(.6,.4) - vec2(.1,.7) == vec2(.5,-.3)
float dist = length(diff); //e.g.0.583 
</code></pre>

<p><strong>5)</strong> So you know that there is exactly one <em>Voronoi point</em> 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 <em>Voronoi point</em> closer to the current fragment than the <em>Voronoi point</em> from <em>4)</em>. Two loops iterate over all 3x3 neighborhood of the current tile. It is much easier to do that relatively <code>{-1, 0, 1}x{-1, 0, 1}</code> instead of using absolute numbers {<code>i_st.x</code>-1, <code>i_st.x</code>, <code>i_st.x</code>+1}x{<code>i_st.y</code>-1, <code>i_st.y</code>, <code>i_st.y</code>+1}. Moreover, we know that each tile is 1x1 in size.</p>

<pre class="lang-glsl prettyprint-override"><code>for (int y= -1; y &lt;= 1; y++) {
    for (int x= -1; x &lt;= 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
</code></pre>

<p><strong>6)</strong> Now you will need to compute the absolute coordinates of neighboring tile to obtain its <em>Voronoi point</em> consistently across all fragments.</p>

<pre class="lang-glsl prettyprint-override"><code>        //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
</code></pre>

<p><strong>7)</strong> And now the most interesting step for you, computing the distance to the neighboring <em>Voronoi point</em></p>

<pre class="lang-glsl prettyprint-override"><code>        //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
</code></pre>

<p>The example values yield:</p>

<p><code>neighbor + point</code>: <code>vec2(-1.,1.) + vec2(0.9, 0.2) == vec2(-0.1, 1.2)</code></p>

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

<p><code>(neighbor + point) - f_st</code>: <code>vec2(-0.1, 1.2) - vec2(.1,.7) == vec2(-.2,.5)</code></p>

<p>This is shorter distance (<code>0.538</code> vs. previous <code>0.583</code>) so for the example positions the <em>Voronoi point</em> from the upper left cell is closer.</p>

<p><strong>8)</strong> The rest is pretty straight forward. Compute the magnitude of the <code>diff</code> vector and keep the minimum.</p>

<pre class="lang-glsl prettyprint-override"><code>        float dist = length(diff); //distance to the neighboring Voronoi point

        m_dist = min(m_dist, dist); //remember the minimum of distances
    }
}
</code></pre>

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

<ul>
<li><p>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 <code>dist</code> to <code>2*sqrt(2)</code> which is very roughly <code>3</code>. That is the length of the diagonal of two cells - the farthest distance the current fragment st could be from one of the neighboring <em>Voronoi points</em>.</p></li>
<li><p>Border tiles are handled in an elegant implicit way. <code>random2</code> generates a <em>Voronoi point</em> 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.</p></li>
</ul>

<p>Hope that helps, feel free to ask any further details.</p>

CC BY-SA 4.0
2020-05-18T05:45:50.707Z
That's a fantastic answer. There is a lot of subtlety that I had ignored. Your thorough treatment of what's relative and what is global was especially helpful.
raheel
CC BY-SA 4.0
2020-05-17T23:03:45.310Z
2020-05-17T23:03:45.310Z
Isolin
<p>I am trying to understand the voronoi shader implemented in the Book of Shaders in the Tiling and iteration section: <a href="https://thebookofshaders.com/12/" rel="nofollow noreferrer">https://thebookofshaders.com/12/</a></p>

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

<pre><code>// 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);
</code></pre>

<p>Specifically how is the <code>diff</code> calculation working? I would have expected <code>i_st</code> to reappear there.</p>

<shader><fragment-shader>
Help me understand the voronoi shader
raheel
# Help me understand the voronoi shader

(Asked by: username_0 on 2020-05-17)

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.

**Tags:** shader, fragment-shader


---

## 1 answers

### Answer by username_1 on 2020-05-17. Score: 4 | Accepted answer

**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.

```glsl
st *= 3.;

```

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

```glsl
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.

```glsl
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.

```glsl
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.

```glsl
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.

```glsl
        //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*

```glsl
        //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.

```glsl
        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.

> **Comments:**
> **username_0**: That's a fantastic answer. There is a lot of subtlety that I had ignored. Your thorough treatment of what's relative and what is global was especially helpful.  

---

