Próbkowanie z Dyskiem Poissona: Losowe Punkty, Które Nie Chcą Zbijać Się

Dlaczego czysto losowe rozmieszczenie wygląda źle

Rozsypując n punktów losowo na kwadrat, rzadko otrzymujemy efekt, który ludzie rozumieją przez "losowość" – zamiast tego obserwujemy widoczne skupiska, gdzie kilka punktów przypadkiem znalazło się blisko siebie, oraz równie widne puste przestrzenie, w których żaden punkt nie trafił.

To zgrupowanie jest rzeczywistym statystycznym zjawiskiem wynikającym z losowego próbkowania, a nie błędem. To właśnie czego nie chcemy, kiedy rozrzucamy drzewa na terenie, umieszczamy gwiazdy w skrzynce niebieskiej lub wybieramy pozycje próbek do antyaliasingu. Próbkowanie dyskretne oparte o Poissona rozwiązuje to problem dzięki jednej dodatkowej regule: żadne dwa punkty nie mogą znajdować się bliżej niż minimalna odległość r.

Algorytm Bridsona: rozwijaj wzorzec z aktywnej fronty

W 2007 roku Robert Bridson w artykule "Fast Poisson Disk Sampling in Arbitrary Dimensions" rozwiązał to w oczekiwanej złożoności O(n) czasowej – ogromny postęp w stosunku do naiwnego podejścia, polegającego na rzucaniu losowych strzał i odrzucaniu tych, które są zbyt blisko siebie, co spowalniało proces do zera, gdy wzorzec wypełniał się. Kluczem jest generowanie kandydatów tylko w pobliżu istniejących punktów, zamiast myśleć o tym bezwzględnie na całym obszarze:

rozmiar komórki siatki = r / sqrt(2) // gwarantuje maksymalnie 1 próbkę na komórce podaj jeden losowy punkt początkowy; dodaj go do próbek i listy aktywnej while lista aktywna nie jest pusta: wybierz losowy punkt p z listy aktywnej powtórz k razy (k ≈ 30): kandydat = losowy punkt w pierścieniu [r, 2r] wokół p jeśli kandydat jest >= r od każdego próbki w pobliskiej komórce siatki: zaakceptuj kandydata: dodaj do próbek i listy aktywnej (spróbuj jeszcze innego kandydata z TEGO samego p za każdym razem) jeśli żaden z k kandydatów nie został zaakceptowany: usuń p z listy aktywnej // p jest "otoczony", przestań próbować Siatka tła, o wymiarach tak dużych, że każda komórka może pomieścić maksymalnie jedną zaakceptowaną próbkę, to właśnie ona sprawia, że szybkie sprawdzanie odległości jest możliwe: sprawdzanie, czy kandydat jest wystarczająco daleko od każdego istniejącego punktu, wymaga jedynie sprawdzenia niewielkiej, stałej liczby sąsiednich komórek siatki, nigdy całego zbioru punktów. Każda zaakceptowana próbka wykonuje ograniczoną ilość pracy – generuje do k kandydatów, sprawdza kilka komórek siatki na kandydata – więc całkowsty koszt skaluje się liniowo wraz z liczbą umieszczonych punktów, a nie kwadratowo.

grid cell size = r / sqrt(2)            // guarantees at most 1 sample per cell

place one initial random point; add it to samples and to the active list

while active list is not empty:
    pick a random point p from the active list
    repeat k times (k ≈ 30):
        candidate = random point in the annulus [r, 2r] around p
        if candidate is >= r from every sample in nearby grid cells:
            accept candidate: add to samples and to active list
            (try another candidate from the SAME p next time too)
    if none of the k candidates were accepted:
        remove p from the active list      // p is "surrounded", stop trying

Szary szum: co sprawia, że wynik wygląda poprawnie

Analizując spektrum częstotliwości przestrzennej wzoru Poisson-disk, zauważy się niemal brak energii na niskich częstotliwościach – brakuje dużych skupień i dużych przerw – a jednocześnie zachowuje się on w sposób nieregularny na wysokich częstotliwościach, w przeciwieństwie do sztywnej siatki. Taki kształt spektralny nazywany jest szarym szumem, analogicznie do światła: niebieskie światło znajduje się na końcu ostrej częstotliwości widma światła widzialnego, podobnie jak szary szum koncentruje swoją energię na wysokich częstotliwościach przestrzennych. Ludzki system wizualny jest szczególnie wrażliwy na grupowanie o niskiej częstotliwości, co dokładnie produkuje czysty, jednorodny losowy próbkowanie i którego unika szary szum – ważny element tego, dlaczego dithering szarego szumu wygląda bardziej gładko niż zwykły dithering przy tej samej gęstości punktów.

Gdzie to się pojawia

Narzędzia tworzące zawartość proceduralnie wykorzystują próbkowanie dysków Poissona do rozrzutu roślinności, skał i elementów wyposażenia na terenie, bez charakterystycznych zlepków wynikających z naiwnego losowania. Silniki renderingu wykorzystują to do umieszczania próbek w celu wygładzania obrazu, tworzenia miękkich cieni i okluzji otoczenia, ponieważ próbki rozłożone według rozkładu szarego (blue-noise) gromadzą się wokół prawidłowego rozwiązania z mniejszym widocznie poziomem szumu niż w przypadku tego samego zbioru próbek całkowicie losowych. Oprogramowanie do stipplingowania i haltonizacji wykorzystuje to bezpośrednio do renderowania gładkich gradientów za pomocą punktów, a generatory siatek używają jego wariantów do inicjalnego osiewania punktów przed triangulacją Delaunaja, ponieważ dobrze rozmieszczone punkty wyjściowe dają lepszą kształt trójkąc.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Poisson-Disk Sampling i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.