Eine Karte in Regionen aufteilen, ein Glas in Scherben zerlegen, jedem Fleck ein Biom geben: Das fängt immer gleich an. Man streut ein paar Punkte, und jeder Ort gehört dem Punkt, der ihm am nächsten ist. Das Ergebnis heißt Voronoi-Diagramm, und im Fragment-Shader sind es erstaunlich wenige Zeilen.
Klick setzt einen Punkt (bis 48), Ziehen bewegt ihn, Rechtsklick löscht den nächsten (mindestens 3 bleiben). Die Punkte driften langsam von allein. Die Chips wechseln zwischen Punkten und Worley-Rauschen, stellen die Metrik ein und schalten Kanten, Höhenlinien und das Driften um. relax rückt jeden Punkt in die Mitte seiner Zelle, R würfelt neu.
Brute Force
Die Punkte liegen als vec4 uSites[48] im Shader, xy ist die Position. Pro Pixel läuft eine Schleife über alle und merkt sich den nächsten und den zweitnächsten:
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 mal 540 Pixel mal 48 Punkte sind gut 25 Millionen Abstände pro Frame. Für eine Grafikkarte ist das nichts, bei mir läuft es mit den vollen 60 fps. Das < ist strikt, bei exakt gleichem Abstand gewinnt also der kleinere Index. Dafür gibt es einen Test.
Das z im Uniform ist eine stabile ID. Die Zellfarbe kommt aus einem Hash dieser ID und nicht aus dem Index, sonst springen alle Farben, wenn du einen Punkt löschst und die Indizes nachrutschen.
Bewegt werden die Punkte auf der CPU, in festen Schritten mit dem Accumulator aus Update Loop, 60 pro Sekunde. An den Wänden prallen sie ab. bounce() faltet die Position wie eine Kugel zwischen zwei Wänden in den Bereich:
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;
}
Bei ungerader Zahl von Wandberührungen dreht sich die Richtung um. Selbst ein Schritt von 1000 Einheiten in einer Box der Größe 10 endet drinnen, der Test prüft das.
Rand: Abstand statt Differenz
An der Kante zwischen zwei Zellen ist d2 - d1 gleich 0. Eine Linie daraus zu machen ist die billige Variante, aber die Differenz wächst nicht überall gleich schnell. Auf der Achse durch beide Punkte ist (d2 - d1) / 2 genau der Abstand zur Kante, daneben nicht. Bei den Punkten (0,0) und (4,0) und dem Pixel (1,3) liefert die Differenz 0,54, der echte Abstand zur Mittelsenkrechten ist 1,0. Weit weg von den Punkten wird die Linie dadurch breit und läuft in Keilen aus. Schalte in der Demo exact aus, dann siehst du es.
Der exakte Randabstand ist der kleinste Abstand zu den Mittelsenkrechten zwischen dem eigenen Punkt und allen anderen. Das ist eine zweite Schleife, doppelt so viele Durchläufe, und die Linie ist dafür überall gleich dick:
edge = min(edge, dot(0.5 * (a + b) - p, b - a) / length(b - a));
Andere Metriken
Die Metrik ist nur die Abstandsfunktion. Manhattan addiert die Achsenabstände, Chebyshev nimmt den größeren. Auf dem 3-4-5-Dreieck: euklidisch 5, Manhattan 7, Chebyshev 4. Die Zellen werden eckig.
Dumm nur: Die Mittelsenkrechte ist dort keine Gerade mehr, die Formel von oben passt nicht, exact ist ausgegraut und die Kante bleibt bei (d2 - d1) / 2. Bei Manhattan kann die Mittelsenkrechte sogar eine Fläche sein. Liegen zwei Punkte auf einer Diagonale, etwa (0,0) und (4,4), haben alle Pixel dahinter denselben Manhattan-Abstand zu beiden. Der Test prüft vier solche Pixel. Die dunklen Flecken in der Demo sind diese Gleichstandsflächen.
Lloyd-Relaxation
Zufällige Punkte ergeben mal fette, mal winzige Zellen. Lloyd räumt auf: Jeder Punkt wandert in den Schwerpunkt seiner Zelle. Das rechnet die CPU auf einem groben Raster aus 120 mal 54 Feldern. Jedes Feld gehört dem nächsten Punkt, jeder Punkt bekommt den Mittelwert seiner Felder:
const int k = nearest(sites, center, metric).first; sums[k].x += center.x; sums[k].y += center.y; ++sums[k].count;
Zwei Punkte bei (4,5) und (6,5) in einem Gebiet von 10 mal 10 rücken auf (2,5; 5) und (7,5; 5) auseinander und bleiben dort stehen, von Hand gerechnet und im Test. Oben links zeigt die Demo den mittleren Abstand der Punkte zu ihrer Zellmitte. Nach vier Klicks auf relax fiel er bei mir von 22 auf 11 Pixel, obwohl die Punkte nebenher weiterdrifteten.
Fortune, Delaunay oder alles durchprobieren
Brute Force passt, wenn du pro Pixel wissen willst, wem er gehört, und sich die Punkte bewegen. Brauchst du die Zellen als Polygone, für Navigation, Kollision oder Bruchstücke als Meshes, nimmst du den Fortune-Sweep (O(n log n)) oder eine Delaunay-Triangulierung. Deren Dreiecke zeigen, welche Zellen Nachbarn sind, ihre Umkreismittelpunkte sind die Zellecken. Bei Hunderten Punkten wird die Pixelschleife irgendwann teuer, dann hilft Jump Flooding.
Worley: ohne Punktliste
Der Worley-Modus hat keine Liste. Die Ebene ist ein Gitter, jede Gitterzelle besitzt genau einen Punkt, und ein Integer-Hash der Zellkoordinaten bestimmt, wo er liegt. Ein Pixel schaut nur in die 3 mal 3 Zellen um sich herum:
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; }
}
}
Das kostet pro Pixel immer gleich viel, egal wie weit du herauszoomst. Mausrad zoomt, Ziehen verschiebt. F1 ist der Abstand zum nächsten Punkt, F2 zum zweitnächsten, F2 - F1 ergibt wieder die Kanten.
Warum reichen 9 Zellen? Der Punkt der eigenen Zelle ist höchstens √2 weit weg, das steht als Grenze im Test. Streng garantiert ist es nicht, solange Punkte bis an den Zellrand dürfen. Meine bleiben deshalb zwischen 0,15 und 0,85 der Zelle, plus ein Schwingen von 0,15. Nachgemessen habe ich auch: 20 000 zufällige Punkte, F1 aus 3 mal 3 und aus 5 mal 5 Zellen, kein einziger Unterschied.
Stolperfallen
Der Hash ist PCG, mit denselben Konstanten in C++ und GLSL. Die Testwerte (pcg(0), hashCell(-1, 2, 7) und ein paar mehr) habe ich mit einer unabhängigen Python-Version gegengerechnet. Negative Zellkoordinaten gehen als uint(int) in beiden Sprachen gleich durch. Dass CPU und GPU Pixel für Pixel dasselbe liefern, habe ich nicht verglichen.
Die Punkte schwingen mit einem Sinus der Zeit. Die Zeit wird bei 20π zurückgesetzt, dort wiederholen sich beide Frequenzen, und der Sinus bleibt auf der GPU genau.
Wofür man das braucht
Zerbrechen: Punkte auf eine Scheibe streuen, die Zellen sind die Scherben. Biome und Länder: Seeds verteilen, jedes Feld übernimmt den Typ des nächsten Seeds, Lloyd macht die Regionen gleichmäßiger. Kartengenerierung: Zellen als Provinzen oder Räume. Prozedurale Texturen: Zellrauschen als Stein, Haut oder Wasserlicht, ganz ohne Bilddatei.
Den Code findest du im Repo unter voronoi. Alle Demos der Serie sammelt das Projekt Game Dev Snippets.