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

Starts when it scrolls into view
Open in /edit ↗
▸Change i < 8 to i < 20 for more points. Change 7.0 to another number to get a different layout

Near 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

Starts when it scrolls into view
Open in /edit ↗
▸Change the 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

Starts when it scrolls into view
Open in /edit ↗
▸The breaks are gone and we have a clean Voronoi pattern. Raise 3.0 to 8.0 for a finer one — it is still just 9 distances per pixel
  • o is the offset to a neighboring cell. float(x) turns the integer x into a decimal (ints and floats cannot be mixed directly)
  • id + o is the neighbor's cell index, and hash22(id + o) is its point's position inside that cell (0–1). Adding o gives the point's position as seen from our cell
  • f is our position inside our cell, so length(pt - f) is the distance from here to that point
  • d1 starts at a large number, 8.0, and min keeps the smaller value each time. After all 9 cells, d1 is 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

Starts when it scrolls into view
Open in /edit ↗
▸Set the 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 colors

The 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

}

It works like a race: when a new runner takes first place, the old leader drops to second

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

Starts when it scrolls into view
Open in /edit ↗
▸Remove the // from // col = vec3(edge); to see F2 - F1 itself. Change 0.02, 0.06 to 0.0, 0.2 for softer edges

Showing 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

Starts when it scrolls into view
Open in /edit ↗
▸Use 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 places

Watch 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

Starts when it scrolls into view
Open in /edit ↗
▸Change 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 scheme

08Cracks 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

Starts when it scrolls into view
Open in /edit ↗
▸Set the 0.25 in 0.25 * (…) to 0.0 and the lines turn straight again. Try 0.6 for a melted, wavy look

Here 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

Starts when it scrolls into view
Open in /edit ↗
▸Change 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 out

09Exercises

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.

Exercise 1

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

Starts when it scrolls into view
Open in /edit ↗
Exercise 2

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

Starts when it scrolls into view
Open in /edit ↗
Exercise 3

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

Starts when it scrolls into view
Open in /edit ↗

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