UK 
EnglishТипова
Polski🔘 Пуассонівська вибірка дисками
Алгоритм Брідсона для синього шуму в дії: активний список росте, приймаючи кандидатів на відстані r..2r — і відкидаючи усе ближче за r. Порівняйте з рівномірним випадковим і дивіться радіальний спектр.
Про цю симуляцію
Ця симуляція реалізує алгоритм Брідсона для пуассонівської вибірки дисками: швидкий спосіб, прискорений сіткою, розкидати точки так, щоб жодні дві не лежали ближче за обраний мінімальний радіус r, без скупчень і прогалин чисто випадкового розміщення. Кожна нова точка вирощується від активного батька, пробуючи до k кандидатів у кільці [r, 2r] навколо нього, а фонова сітка з розміром комірки r/√2 дозволяє перевірці відстані до сусідів виконуватися за O(1), тож увесь алгоритм масштабується як O(n). Отриманий набір точок має статистичну сигнатуру «синього шуму» — низькочастотне скупчення пригнічене, що видно на живому радіальному спектрі потужності.
🔬 Що показано
Три стратегії генерації точок поруч: синій шум Брідсона, рівномірне випадкове розміщення та регулярна сітка. Фіолетові крапки позначають точки, що досі в активному списку (кандидати ще можуть породжуватись від них); білі крапки — «мертві» точки, чий сусідній простір заповнений. Слабке кільце спалахує червоним або фіолетовим навколо кожного відхиленого чи прийнятого кандидата, доки працює алгоритм.
🎮 Як користуватись
Перемикайте режими радіокнопками, потім налаштуйте мінімальний радіус r (6–40px) та кількість спроб k (5–60) — вище k знаходить щільніші упаковки за рахунок більшої кількості відхилених кандидатів. Швидкість анімації керує кількістю точок, що генеруються за кадр. Увімкніть «Змінний радіус (щільність)» та «Малювати карту щільності», щоб перетягувати прямо на полотні й ліпити області щільнішого чи розрідженішого семплювання; перемкніть «Показати фонову сітку» та вставку «Радіальний спектр», щоб побачити структуру прискорення та сигнатуру синього шуму.
💡 Чи знали ви?
Набори точок пуассонівського диска (синій шум) цінуються в комп'ютерній графіці саме тому, що людський зір дуже чутливий до низькочастотного скупчення — тому синій шум використовується для дизерингу зображень, розміщення дерев чи трави в ігровому ландшафті, семплювання пікселів у трасувальниках променів, і навіть у розташуванні фоторецепторних клітин сітківки, які, як виявили біологи, слідують майже пуассонівсько-дисковому патерну.
Часті питання
Що таке пуассонівська вибірка дисками?
Пуассонівська вибірка дисками генерує набір випадкових точок у просторі так, що кожна пара точок розділена принаймні мінімальною відстанню r, при цьому виглядаючи нерегулярно й органічно, а не сітчасто. Вона розташована між повністю випадковим розкиданням (яке скупчується) і регулярною сіткою (яка виглядає штучно) і є стандартним способом отримання розподілів точок «синього шуму».
Як покроково працює алгоритм Брідсона?
Почніть з однієї випадкової зародкової точки й додайте її до «активного списку». Багаторазово обирайте випадкову точку з активного списку й пробуйте до k випадкових кандидатів у кільці між r і 2r навколо неї. Перший кандидат, що знаходиться щонайменше на відстані r від кожної існуючої точки, приймається й додається як до набору точок, так і до активного списку; якщо жодна з k спроб не вдалась, батьківська точка видаляється з активного списку. Процес завершується, коли активний список порожній.
Чому алгоритм використовує фонову сітку?
Перевірка нового кандидата проти кожної існуючої точки зайняла б час O(n) на кандидата, роблячи весь алгоритм O(n²). Ключовий трюк Брідсона — фонова сітка з розміром комірки r/√2, обраним так, щоб кожна комірка могла вмістити щонайбільше одну прийняту точку. Кандидату потрібно перевірити лише свою власну комірку та навколишні сусідні (невелику фіксовану кількість комірок), тож кожна перевірка виконується за O(1), а весь алгоритм працює за O(n) для n вихідних точок.
Що таке «синій шум» і чому це важливо?
Синій шум описує розподіл точок, спектр потужності якого має мало енергії на низьких просторових частотах — тобто немає великих скупчень або великих порожніх прогалин, лише дрібномасштабна, рівномірно розподілена варіація. Ця властивість візуально важлива, оскільки людське око надзвичайно чутливе до низькочастотних патернів, таких як скупчення чи артефакти муару. Саме тому семплювання синім шумом — стандартна техніка для стипплінгу, дизерингу, згладжування та процедурного розкидання об'єктів, таких як дерева, каміння чи трава, природним на вигляд способом.
Як семплювання зі змінним радіусом створює градієнти щільності?
Замість використання одного фіксованого радіуса r всюди, локальну мінімальну відстань можна отримати з карти щільності: малий радіус використовується в щільних областях (дозволяючи точкам розташовуватись ближче одна до одної), а більший радіус — у розріджених областях (розсіюючи точки далі одна від одної). Перевірка сусідства тоді використовує більший з радіусів кандидата й кожної наявної точки, тож упаковка залишається послідовною всюди. Це створює плавно змінювану щільність точок, зберігаючи гарантію відсутності перекриття всюди, що є саме тим, що дозволяє ліпити вручну інструмент «Малювати карту щільності».