Algorithmus: Voronoi-Diagramm

Lesezeit: 5 Minuten

Um gradlinige Muster zu erzeugen, hilft meist das sogenannte Voronoi-Diagramm. Auch unter den Namen „Thiessen-Polygone“ oder „Dirichlet-Zerlegung“ findet man ähnliche Musterbildungen.

Speziell für getreppte Höhenmaps ist dies geeignet – daher hier meine PHP-Implementierung für den Server.

Im Blog Mission on Mars: UV-Map generieren benutze ich den Algorithmus, um ein Wolkenmuster aus Algorithmus: Diamond-square in eine Treppenstruktur umzuwandeln. Der Algorithmus basiert auf einem existierenden Bild, ist also im Grunde kein Generator, sondern ein Filter.

Die genaue Definition findet sich hier: https://de.wikipedia.org/wiki/Voronoi-Diagramm

Grundsätzliches

Meine Abwandlung des Algorithmus funktioniert nur auf einem existierenden Bild (ansonsten sieht man nix).

Er ist sehr Laufzeitintensiv.

Er basiert auf Pseudo-Zufallszahlen mit Seed, wobei gleiche Seeds wieder die selbe Struktur erzeugen.

Angewendet – auch auf eine seamless Textur – verliert die Textur diese Eigenschaft und wird zu einer nicht-nahtlosen Textur.

Ablauf

Über das Bild werden eine Anzahl von zufällig platzierten Anker-Punkten gelegt.

Für jeden Bildpunkt wird die Farbe gesetzt, die der nächstgelegene Anker-Punkt hat.

Implementierung

Für diesen Filter baue ich wieder eine eigene Klasse. Sinnvolle Parameter sind:

  • Seed
  • Detail – also die Anzahl der Ankerpunkte
  • Border – ein Rahmen innerhalb des Bildes, an dem keine Ankerpunkte sein dürfen
  • Zum Debuggen noch zwei Parameter, ob die Ankerpunkte visualisiert werden sollen inkl. der Farbe

Anwendung

Ich benutze diese Wolke mit Seed 6 für den Filter:

Voronoi – Seed = 2, Detail = 10, Border = 0 mit Ankervisualisierung

Voronoi – Seed = 2, Detail = 1000, Border = 0 mit Ankervisualisierung

Voronoi – Seed = 3, Detail = 1000, Border = 0 ohne Ankervisualisierung

Voronoi – Seed = 5, Detail = 3000, Border = 0 ohne Ankervisualisierung

Geht auch in farbig, z. B. mit diesem Bild mit 500×500:

Herauskommt nach einiger Zeit (> 30 Sekunden) das:

Und dann noch mal das selbe Beispiel mit Border = 50:

Man kann damit erahnen, wie vielseitig dieser Algorithmus einzusetzen ist.

Weiterführende Links

Dieser Filter ergänzt meine Materialgenerierung – das „Große-Ganze“ dann in einem späteren Blog. Ich fokussiere mich erst mal auf weitere Generatoren und Filter.

PHP-Code

Wie gewohnt, hier der gesamte Code:

 

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.