LearnPatterns and noise
Lesson 15 of 30 · 55 min
Cellular patterns (Voronoi)
Use the distance to nearby points for cells, cracks and stained glass
In this lesson you will
- Place one point per cell with
hash22, and find the distance to the nearest point (F1) with a double loop over the 3×3 neighborhood - Remember which cell the nearest point belongs to, and give every cell its own color
- Draw the borders between cells with the difference to the second-nearest point (F2 - F1)
- Animate the points, and turn the pattern into stained glass, cracks, living cells and bubbles
01Coloring by the nearest point
Scatter a few points on the plane and color every place by its nearest point, and you get regions like paving stones. This is called a Voronoi diagram, and each region is a cell. The shape shows up all over nature: giraffe skin, cracks in dried mud, soap bubbles, the cells of a leaf.
A shader answers the question "what color is this place?". For Voronoi, that becomes "how far is this place from the nearest point?". Let's start the most direct way: measure the distance to all 8 points and keep the smallest.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
i < 8 to i < 20 for more points. Change 7.0 to another number to get a different layoutNear a point (red) the distance is small, so it is dark; it gets brighter as you move away. Can you see the lines where the brightness folds like a mountain ridge? Those are the places exactly as far from two points, which is to say the borders between cells.
This approach has a weakness. Every pixel measures the distance to every point, so with 200 points, each pixel does 200 calculations. On top of that, this site limits loops to 64 iterations. To fill the screen with a fine pattern, we need something smarter.
02One point per cell
This is where the grid from Repetition and tiles comes in. Split the screen into cells and put exactly one point in every cell. To decide where, pass the cell index to hash22 from Making randomness. It returns two numbers between 0 and 1, which we can use directly as "somewhere inside the cell".
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
3.0 in p * 3.0 to 6.0: the cells shrink, but each still has one point. Did you notice how the brightness jumps at the blue lines?The points are scattered, but this is not Voronoi yet. We only measure the distance to our own cell's point. A place near the right edge of a cell may actually be closer to the point in the cell to the right, and since we never look there, the brightness breaks at every cell border. It's the same problem we met in Repetition and tiles, where shapes poking out of their cell got cut off in a straight line: each cell only knows about itself.
03Searching the 3×3 neighborhood
So how far do we need to look? Every point stays inside its own cell. That means the nearest point is almost always in our own cell or one of the 8 cells around it, because a point two or more cells away is at least one whole cell away. It is like searching from your window: your own house and the 8 houses around it are enough.
We visit the 9 cells with a double loop over x and y. Each takes the values -1, 0 and 1, which gives the 9 combinations from (-1, -1) to (1, 1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
3.0 to 8.0 for a finer one — it is still just 9 distances per pixelois the offset to a neighboring cell.float(x)turns the integerxinto a decimal (ints and floats cannot be mixed directly)id + ois the neighbor's cell index, andhash22(id + o)is its point's position inside that cell (0–1). Addingogives the point's position as seen from our cellfis our position inside our cell, solength(pt - f)is the distance from here to that pointd1starts at a large number,8.0, andminkeeps the smaller value each time. After all 9 cells,d1is the distance to the nearest point
This distance to the nearest point is called F1 (the first distance). It is 0 on a point and grows toward the cell borders. Because it is measured in cell units, F1 stays roughly between 0 and 0.8 even when you change 3.0 and resize the cells.
Watch out
As we saw in Time and motion, the site's publishing check requires every for loop to be bounded by a number no larger than 64. Loops starting at -1 are no different: write for (int y = -1; y < 2; y++). y <= 1 means the same thing, but stick to the y < 2 form so the check can read it.
Tip
If points bunch up near cell corners, a point two cells away can, very rarely, be the nearest one, and the 3×3 search misses it. The result is almost never visible, so 3×3 is plenty for making patterns.
Tip
This "look at the neighbors too" approach also solves the clipping problem from Repetition and tiles. Measure the distance to the shapes in the 8 neighboring cells as well and take the min, and shapes that straddle cell borders are drawn without being cut off.
04A color for every cell
F1 is just a distance; it doesn't tell us which cell we are in. So inside the loop, whenever we find a new nearest point, we also remember its cell index, id + o. Every place in the same cell ends up with the same index, so a color made from the index fills the whole cell evenly.
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
40
0.6 in 1.0 - 0.6 * d1 to 0.0 for a flat mosaic. Change vec3(0.0, 0.33, 0.67) to vec3(0.0, 0.1, 0.2) to shift the colorsThe key is that if (d < d1) updates the distance and the index together. min alone can't tell you which point won, so we use if here. The index cell becomes a 0–1 number through hash21 from Making randomness, and then a color through palette from Mixing colors.
The cell index is good for much more than color. Vary brightness, size, rotation or speed per cell, and the same shape repeats without ever looking monotonous.
05Drawing the borders (F2 - F1)
To draw the lead lines of stained glass or the lines of a crack, we need to know where the borders are. This is where the distance to the second-nearest point, F2, helps. As we saw in the first playground, a border is a place equally far from two points. There F1 equals F2, so F2 - F1 is 0. Toward the middle of a cell the nearest point wins clearly, and the difference grows.
1
2
3
4
5
6
7
if (d < d1) {
d2 = d1; // the old winner drops to second place
d1 = d;
cell = id + o;
} else if (d < d2) {
d2 = d; // not the nearest, but closer than second place
}
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
40
41
42
43
44
45
// from // col = vec3(edge); to see F2 - F1 itself. Change 0.02, 0.06 to 0.0, 0.2 for softer edgesShowing vec3(edge) reveals black lines along the borders that brighten toward the inside of each cell. smoothstep(0.02, 0.06, edge) gives 0 (black) where the difference is below 0.02 and 1 where it is above 0.06, which leaves a dark line along every border.
Tip
F2 - F1 is not the true distance to the border, so the line width varies a little from place to place. That hand-drawn feel often suits patterns, but if you need exact widths, Inigo Quilez describes a method in this article.
06Moving the points
Move the points over time and the cells jostle and reshape like something alive. Replace the point position hash22(id + o) with this:
1
vec2 pt = o + 0.5 + 0.4 * sin(time + TAU * hash22(id + o));
sin(…) goes from -1 to 1, so multiplying by 0.4 gives -0.4 to 0.4, and adding 0.5 gives 0.1 to 0.9. The point wanders around the middle of its cell and never leaves it. TAU * hash22(id + o) gives each point its own phase (an offset in the wave), so they all move out of step. Since x and y get different phases, each point circles along a tilted, squashed ellipse instead of sliding back and forth on a line.
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
40
41
42
43
44
sin(time * 3.0 + …) to speed it up. Raise 0.4 to 0.9 and the points leave their cells, so the borders break up in placesWatch out
The 3×3 search assumes that each point stays inside its own cell. Push the points out of their cells and the nearest one may sit in a cell we never check, so borders snap and cells get chipped. Keep the motion within roughly 0.1–0.9.
07Stained glass
From here on we use the same F1, F2 and cell index to build different looks. First, stained glass. Pick a deep color per cell and put a thick dark frame on the borders. To make it look lit from behind, brighten the area near each point (where F1 is small) and the middle of the screen.
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
40
41
42
43
44
45
46
47
48
0.06, 0.1 to 0.02, 0.04 for a thinner frame. Play with the numbers in vec3(0.6, 0.1, 0.0) to choose the window's color scheme08Cracks and living cells
For cracks in dry earth, make the border lines very thin and paint the rest in soil colors. But Voronoi borders are straight, which looks artificial. So, just as in Domain warping, we add a little smooth noise to the grid coordinate g to make the borders jagged.
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
0.25 in 0.25 * (…) to 0.0 and the lines turn straight again. Try 0.6 for a melted, wavy lookHere the points sit at 0.2 + 0.6 * hash22(…), nearer the middle of each cell (0.2–0.8). Since no point hugs an edge, the cells come out similar in size and the crack network looks tidy. Also, smoothstep(0.0, 0.25, edge) darkens the soil near the cracks, so the edges of each clod seem to sink a little, which adds depth.
The same ingredients give you cells under a microscope. Draw a nucleus where F1 is small (around each point) and a membrane where F2 - F1 is small (on the borders). Use a translucent green and move the points slowly, and it looks alive.
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
40
41
42
43
44
45
46
47
48
r = 0.1 + 0.05 * h to r = 0.05 + 0.15 * h for nuclei of all sizes. Change p * 3.5 to p * 6.0 to zoom the microscope out09Exercises
The craft lies in how you combine three ingredients: F1, F2 and the cell index. In every exercise the neighbor-search loop is already written for you.
Giraffe pattern
Make brown patches separated by thick cream-colored borders. Vary the brown slightly from cell to cell to make it look real.
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
Twinkling cells
A grid of colorful cells sits on a dark background. Make each cell brighten and dim at its own pace. The goal is a scattered twinkle, not every cell flashing at once.
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
40
41
42
43
44
45
Rising bubbles
Draw bubbles of different sizes slowly rising through blue water. Draw each bubble as a ring centered on its cell's point. A small highlight on the upper left of each bubble makes them much more convincing.
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
10Recap
- Voronoi colors the plane by the nearest point. Put one point per cell with
hash22 - Each point stays in its own cell, so checking the 3×3 block — our cell and its 8 neighbors — is enough
- F1 is the distance to the nearest point: use it for round shapes around points and for shading
- Remember the nearest point's cell index to vary color or motion per cell
- F2 - F1 is 0 on the borders: use it for frames, cracks and membranes
- When moving points, keep them within about 0.1–0.9 so they never leave their cells
Next time we take a careful second look at the distances we have been using since Circles and distance and Combining shapes. Give a distance a sign, and smoothly merging shapes or adding shadows and glow becomes much easier.
Finished lessons get a mark in the course contents