Зразкування за допомогою сітки Пойсона: Випадкові точки, які не скупчуються

Чому випадкове розміщення виглядає неправильно

Розкладіть n точок випадково та рівномірно по квадрату, і результат рідко схожий на те, що люди розуміють під "випадком" — замість цього видно скупчення, де кілька точок потрапили близько один до одного через випадковість, а також видимі порожні прогалини, де жодна точка не потрапила. Це кластерний ефект справжньої статистичної властивості рівномірного семплювання, а не помилка, і це саме те, чого ви не хочете, коли розкидаєте дерева по рельєфу, розміщуєте зірки в скі-бокс або обираєте позиції для семплінгу для антиаліasing. Poisson-disk семплювання вирішує цю проблему, додаючи одне правило: відстань між будь-якими двома точками не може бути меншою за мінімальну відстань r.

Алгоритм Брідона: розвинення за активної фронти

У 2007 році Роберт Брідон у своїй статті "Швидке обчислення дискретного семплювання Поассона в довільних вимірах" вирішує це з очікуваною часом O(n) — величезний стрибок вперед порівняно з наївним підходом, який передбачає кидання випадкових дроти та відкидання тих, що занадто близько розташовані, що сповільнюється до мізерної швидкості, коли шаблон заповнюється. Ключем є лише генерування кандидатів поблизу існуючих точок, а не бездумно на всій області:

розмір комірки сітки = r / sqrt(2) // гарантує щонайбільше 1 зразок на комірку розмістити один випадковий початковий пункт; додати його до зразків і до списку активних пунктів поки список активних пунктів не порожній: вибрати випадкову точку p зі списку активних пунктів повторити k разів (k ≈ 30): кандидат = випадкова точка в колі радіусом [r, 2r] навколо p якщо кандидат >= r від усіх зразків у сусідніх комірках сітки: прийняти кандидата: додати до зразків і до списку активних пунктів (спробувати ще одного кандидата з ТЕЖУ ЖЕ p наступного разу) якщо жоден із k кандидатів не був прийнятий: видалити p зі списку активних пунктів // p "окуточено", припинити спроби Фон сітки, розмір якої дозволяє кожній комірці вміщувати щонайбільше один прийнятий зразок, робить швидким перевірку відстані: перевірка, чи є кандидат достатньо віддаленим від усіх існуючих точок, вимагає лише розгляду невеликої, постійної кількості сусідніх комірок сітки, ніколи всього набору точок. Кожен прийнятий пункт виконує обмежену кількість роботи — генерує до k кандидатів, перевіряє невелику кількість комірок сітки на кандидата — отже, загальна вартість масштабується лінійно з кількістю розміщених точок, а не квадратично.

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

Синій шум: що робить результат вірним

Проаналізуйте просторовий частотний спектр закономірності Poisson-disk і ви побачите майже відсутню енергію на низьких частотах — жодних великих кластерів і жодних великих проміжків — але водночас залишається нерегулярним на високих частотах, на відміну від жорсткої сітки. Ця спектральна форма називається синім шумом, подібно до світла: блакитне світло знаходиться на високому кінці видимого спектру, так само як і синій шум концентрує свою енергію на високих просторових частотах. Людське зорово сприймаюче тіло особливо чутливе до кластеризації низької частоти, що точно те, що виробляє чистий рівномірний випадковий зразок, і синій шум уникає цього — велика частина того, чому дрейфування синього шуму виглядає плавніше, ніж звичайне випадкове дрейфування при однаковому щільності точок.

Де це зустрічається

Процедурні інструменти контенту використовують семплювання Poisson-дисків для розсіювання рослинності, скель і предметів над поверхнею, не створюючи характерних клаптиків наївного випадкового розподілу. Двигуни рендерингу використовують його для розміщення зразків для антизрізу, м'яких тіней та обчислення навколишнього освітлення, оскільки зразки, що розподіляються за розподілом синього шуму, збігаються з правильним рішенням із меншим видимим рівнем шуму, ніж однакові кількість чисто випадкових зразків. Програмне забезпечення для стіплінгу та напівтону використовує його безпосередньо для рендерингу гладких градієнтів за допомогою точок, а генератори сіток використовують варіації цього для початкового насіння точок перед трикутним методом Delaunay, оскільки добре розставлені точки-насінники дають краще утворені трикутники.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Poisson-Disk Sampling і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.