Interaktive Demo
Blue Noise
Rein zufällige Punkte bilden Haufen und lassen Lücken. Blue-Noise-Punkte sind immer noch zufällig, halten aber einen Mindestabstand zueinander, wie Bäume im Wald oder Zellen in der Netzhaut. Robert Bridsons Algorithmus erzeugt sie in linearer Zeit.
Jeder Schritt wählt einen aktiven Punkt (korallenrot) und probiert bis zu k zufällige Stellen im Ring um ihn. Grün wird übernommen, Kreuze lagen zu nah an einem anderen Punkt.
Steuerung
Anzeige
- Punkte
- –
- Aktive Punkte
- –
Legende
- Punkt
- Aktiver Punkt (kann noch Nachbarn bekommen)
- Aktueller Punkt und verworfene Versuche
- Übernommener neuer Punkt
1. Versuche um aktive Punkte
- Beginne mit einem zufälligen Punkt und markiere ihn als aktiv.
- Wähle einen zufälligen aktiven Punkt und probiere bis zu k zufällige Stellen im Ring zwischen r und 2r um ihn.
- Übernimm die erste Stelle, die von jedem Punkt mindestens r entfernt ist, und markiere sie als aktiv.
- Scheitern alle k Versuche, wird der Punkt stillgelegt. Schluss ist, wenn kein aktiver Punkt mehr übrig ist.
2. Ein Gitter für die Nachbarn
Damit eine Stelle schnell geprüft werden kann, gibt es ein Hintergrundgitter mit Zellen der Größe r/√2. Jede Zelle enthält höchstens einen Punkt, deshalb müssen nur die 5 × 5 Zellen um eine Stelle geprüft werden, egal wie viele Punkte es gibt.
3. Warum „blau“
Das Spektrum zufälliger Punkte ist flach, wie bei weißem Rauschen. Poisson-Disk-Punkte haben bei tiefen Frequenzen fast keine Leistung, die dunkle Scheibe in der Mitte ihres Spektrums, weil sie nie Haufen bilden. Das ist das Kennzeichen von Blue Noise und der Grund, warum es zum Abtasten, Dithering und Stippling verwendet wird.
Quellen
- Der Algorithmus ist Fast Poisson Disk Sampling in Arbitrary Dimensions von Robert Bridson (SIGGRAPH 2007).