Split a map into regions, shatter a pane of glass, give every patch of ground a biome: it always starts the same way. You scatter a few points, and every spot belongs to the point nearest to it. The result is called a Voronoi diagram, and in a fragment shader it takes surprisingly few lines.
A click adds a point (up to 48), dragging moves it, a right click deletes the nearest one (at least 3 stay). The points drift slowly on their own. The chips switch between points and Worley noise, set the metric and toggle edges, isolines and drifting. relax moves every point to the middle of its cell, R rolls a new layout.
Brute force
The points sit in the shader as vec4 uSites[48], xy is the position. Per pixel a loop runs over all of them and remembers the nearest and the second nearest:
for (int i = 0; i < 48; i++) {
if (i >= uCount) break;
float d = metricDist(uSites[i].xy, p);
if (d < d1) { d2 = d1; d1 = d; first = i; }
else if (d < d2) { d2 = d; }
}
960 times 540 pixels times 48 points is a good 25 million distances per frame. That is nothing for a graphics card, on my machine it runs at the full 60 fps. The < is strict, so on exactly equal distances the smaller index wins. A test covers it.
The z in the uniform is a stable id. A cell's color comes from a hash of that id and not from the index, otherwise every color jumps when you delete a point and the indices shift.
The points are moved on the CPU, in fixed steps with the accumulator from Update Loop, 60 per second. They bounce off the walls. bounce() folds the position into the range like a ball between two walls:
inline float bounce(float x, float size, bool& flipped) {
const float period = 2.0F * size;
flipped = (static_cast<long long>(std::floor(x / size)) % 2) != 0;
float m = std::fmod(x, period);
if (m < 0.0F) m += period;
return m > size ? period - m : m;
}
After an odd number of wall hits the direction is reversed. Even a step of 1000 units in a box of size 10 ends up inside, the test checks it.
Border: distance instead of difference
On the edge between two cells d2 - d1 is 0. Turning that into a line is the cheap way, but the difference does not grow at the same speed everywhere. On the axis through both points (d2 - d1) / 2 is exactly the distance to the edge, off the axis it is not. For the points (0,0) and (4,0) and the pixel (1,3) the difference gives 0.54, the real distance to the bisector is 1.0. Far from the points the line gets thick and ends in wedges. Switch exact off in the demo and you can see it.
The exact border distance is the smallest distance to the perpendicular bisectors between your own point and all the others. That is a second loop, twice the iterations, and the line gets the same thickness everywhere:
edge = min(edge, dot(0.5 * (a + b) - p, b - a) / length(b - a));
Other metrics
The metric is just the distance function. Manhattan adds the axis distances, Chebyshev takes the larger one. On the 3-4-5 triangle: Euclidean 5, Manhattan 7, Chebyshev 4. The cells get angular.
Trouble is: the bisector is no longer a straight line there, the formula above does not fit, exact is greyed out and the edge stays at (d2 - d1) / 2. With Manhattan the bisector can even be an area. If two points sit on a diagonal, say (0,0) and (4,4), every pixel behind them has the same Manhattan distance to both. The test checks four such pixels. The dark patches in the demo are these tie areas.
Lloyd relaxation
Random points make some cells fat and some tiny. Lloyd tidies up: every point moves to the centroid of its cell. The CPU does that on a coarse grid of 120 by 54 fields. Every field belongs to the nearest point, every point gets the mean of its fields:
const int k = nearest(sites, center, metric).first; sums[k].x += center.x; sums[k].y += center.y; ++sums[k].count;
Two points at (4,5) and (6,5) in a 10 by 10 area move apart to (2.5; 5) and (7.5; 5) and stay there, worked out by hand and in the test. The demo shows the mean distance of the points to their cell centers in the top left. After four clicks on relax it dropped from 22 to 11 pixels on my machine, even though the points kept drifting meanwhile.
Fortune, Delaunay or just try everything
Brute force fits when you want to know per pixel who it belongs to and the points move. If you need the cells as polygons, for navigation, collision or fragments as meshes, you use the Fortune sweep (O(n log n)) or a Delaunay triangulation. Its triangles show which cells are neighbors, the circumcenters are the cell corners. With hundreds of points the per-pixel loop gets expensive, and Jump Flooding helps.
Worley: no point list
The Worley mode has no list. The plane is a lattice, every lattice cell owns exactly one point, and an integer hash of the cell coordinates decides where it sits. A pixel only looks at the 3 by 3 cells around it:
for (int j = -1; j <= 1; j++) {
for (int i = -1; i <= 1; i++) {
ivec2 cell = c + ivec2(i, j);
vec2 f = vec2(cell) + featureOffset(hashCell(cell), uTime);
float d = metricDist(f, q);
if (d < f1) { f2 = f1; f1 = d; owner = cell; }
else if (d < f2) { f2 = d; }
}
}
That costs the same per pixel no matter how far you zoom out. The mouse wheel zooms, dragging pans. F1 is the distance to the nearest point, F2 to the second nearest, and F2 - F1 gives the edges again.
Why are 9 cells enough? The point of the own cell is at most √2 away, which is the bound in the test. It is not strictly guaranteed as long as points may sit right at the cell border. Mine stay between 0.15 and 0.85 of the cell, plus a wobble of 0.15. I also measured it: 20,000 random points, F1 from 3 by 3 and from 5 by 5 cells, not a single difference.
Pitfalls
The hash is PCG, with the same constants in C++ and GLSL. The test values (pcg(0), hashCell(-1, 2, 7) and a few more) were cross-checked with an independent Python version. Negative cell coordinates go through uint(int) the same way in both languages. I did not compare CPU and GPU pixel by pixel.
The points wobble with a sine of the time. The time is reset at 20π, where both frequencies repeat, so the sine stays accurate on the GPU.
What it is good for
Shattering: scatter points on a pane, the cells are the shards. Biomes and countries: spread seeds, every field takes the type of the nearest seed, Lloyd evens the regions out. Map generation: cells as provinces or rooms. Procedural textures: cell noise as stone, skin or water light, without an image file.
You can find the code in the repo under voronoi. The project Game Dev Snippets collects all demos of the series.