Девлог #89 – Хвиля 68: Барнс-Гат, метод рухомих квадратів, вибірка Пуассонового диска, нерівність Белла, схема Чуа та натовп пішоходів

Нові симуляції

Гравітація N тіл за Барнсом-Гатом: квадродерево

Пряма гравітація N тіл прекрасна, але жорстока: кожна частинка повинна взаємодіяти з кожною іншою, що дає O(n²) обчислень сили на крок часу — n(n−1)/2 пар для n=2000 означає майже 2 мільйони обчислень на кадр при 60 fps. Барнс-Гат скорочує це до O(n log n) за допомогою рекурсивного квадродерева (октодерева у 3D).

θ-критерій

Кожен внутрішній вузол зберігає загальну масу і центр мас усіх частинок, що містяться в ньому. При обчисленні сили на частинку, замість рекурсивного заглиблення у вузол, ви замінюєте його агрегатом, якщо співвідношення s/d задовольняє умову s² < θ²d² — де s — довжина сторони вузла, а d — відстань від частинки до центру мас вузла. Менше θ означає більшу точність, але більше обчислень; θ = 0.5 — стандартний компроміс.

Інтегрування Velocity-Verlet

Позиції та швидкості просуваються за схемою Velocity-Verlet: x(t+dt) = x(t) + v(t)dt + ½a(t)dt², потім сили перераховуються, і нарешті v(t+dt) = v(t) + ½(a(t)+a(t+dt))dt. Це симплектичний інтегратор — він зберігає тіньовий гамільтоніан, запобігаючи штучному дрейфу енергії протягом довгих прогонів. Дерево перебудовується щокадру, оскільки частинки рухаються безперервно.

• 4 пресети: гаусова хмара, зіткнення двох галактик, кільце + центральна маса, центральний притягувач + хмара
• Клік по будь-якій частинці підсвічує шлях її декомпозиції у квадродереві
• Живий лічильник: обчислення BH проти наївних n(n−1)/2
• Повзунок N до 2000 частинок

Метод рухомих квадратів: таблиця пошуку ізоконтурів

Метод рухомих квадратів витягує ізоконтури зі скалярного поля 2D, обробляючи кожну комірку сітки незалежно. Кожна комірка має чотири кути — кожен або вище, або нижче ізозначення, що дає 2⁴ = 16 різних топологічних випадків.

Таблиця з 16 випадків і лінійна інтерполяція

Попередньо обчислена таблиця пошуку зіставляє 4-бітну маску кутів з парами перетину ребер. Для кожного активного ребра перетин розміщується за допомогою лінійної інтерполяції: t = (iso − v₀) / (v₁ − v₀) вздовж ребра, що дає гладкі контури замість зубчастих пікселізованих меж.

Розв'язання сідлових точок

Випадки 5 і 10 неоднозначні — діагональна зв'язність не визначена. Симуляція розв'язує їх, вибираючи білінійне центральне значення: якщо центр вище порогу, контур з'єднується одним чином; якщо нижче — іншим. Це запобігає топологічним артефактам, таким як фантомні розриви в полях метаболів.

• Чотири скалярні поля: метаболи (сума 1/(r²+ε)), fBm-шум (6 октав), анімована синусоїда, мальоване користувачем
• Багаторівневе контурування: малюйте до 8 одночасних ізозначень з різними кольорами
• Білінійний оверлей теплокарти показує сире поле під контурами

Вибірка Пуассонового диска: алгоритм Бріджсона

Вибірка Пуассонового диска створює набори точок, де жодні дві точки не розташовані ближче за мінімальну відстань r, при цьому заповнюючи простір максимально щільно. Результат — «блакитний шум»: спектр потужності, плаский у середньочастотному діапазоні, що робить його перцептивно ідеальним для дизерингу, штрихування та генерації рельєфу.

Фонова сітка O(n)

Алгоритм Бріджсона 2007 року досягає O(n) (лінійно від розміру виводу) за допомогою фонової сітки з розміром комірки r/√2. Кожна комірка містить не більше однієї вибірки; пошук сусідів вимагає перевірки лише фіксованого вікна 5×5. Список активних точок зростає, оскільки кожна прийнята вибірка породжує до k=30 кандидатських кільцевих спроб у діапазоні [r, 2r].

Перевірка блакитного шуму

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

• Анімуйте генерацію крок за кроком або завершіть пакетно миттєво
• Налаштуйте мінімальний радіус r від 8 до 40 пікселів
• До ~2000 вибірок на полотні 800×600
• Перемикайте оверлей радіального спектра потужності для порівняння якості шуму

Нерівність Белла: квантові кореляції перевершують класичні межі

Теорема Джона Белла 1964 року довела, що жодна локальна теорія прихованих змінних не може відтворити всі квантово-механічні передбачення. Нерівність CHSH (Клаузер-Горн-Шимоні-Голт) робить це експериментально перевірюваним: вимірюється комбінація S = |E(a,b) − E(a,b') + E(a',b) + E(a',b')|.

Квантова та класична межі

Для синглетного стану |ψ⁻⟩ = (|01⟩ − |10⟩)/√2 квантова функція кореляції — E(a,b) = −cos(a − b). З оптимальними кутами вимірювання a=0°, a'=45°, b=22.5°, b'=67.5°, це дає S = 2√2 ≈ 2.828 — межу Цирельсона, максимум, дозволений квантовою механікою. Будь-яка класична модель прихованих змінних обмежена |S| ≤ 2.

Живий експеримент

Симуляція вибирає випадкові значення λ для класичної моделі та квантові випадкові обертання для квантової моделі. Обидва значення S відстежуються протягом N випробувань і сходяться до своїх теоретичних меж зі зростанням N, наочно демонструючи розрив, який жодна класична модель не може подолати.

• Повзунок для зміни кутів вимірювання зі спостереженням зміни S у реальному часі
• Гістограма добутків E = A·B по парах накопичується протягом випробувань
• Класичне й квантове значення S відображаються з поточним середнім

Схема Чуа: найпростіша хаотична схема

Схема Леона Чуа 1983 року — канонічна лабораторія для електронного хаосу. Вона утворює дивний атрактор подвійної спіралі — дві переплетені спіралі у фазовому просторі — лише з трьох пасивних компонентів та одного нелінійного резистора (діода Чуа).

Диференціальні рівняння та діод Чуа

Динаміка керується трьома пов'язаними диференціальними рівняннями:

dV_C1/dt = (1/C1) · [G(V_C2 − V_C1) − f(V_C1)]
dV_C2/dt = (1/C2) · [G(V_C1 − V_C2) + I_L]
dI_L/dt  = −(1/L) · V_C2

де f(V) — кусково-лінійна вольт-амперна характеристика діода Чуа: f(V) = m₁V + ½(m₀−m₁)(|V+1|−|V−1|). Симуляція інтегрує за допомогою RK4 з фіксованим кроком часу, рендерячи траєкторії безпосередньо на полотно.

Показник Ляпунова та біфуркація

Найбільший показник Ляпунова λ₁ оцінюється методом двох траєкторій Бенеттіна: друга траєкторія стартує з нескінченно малим зсувом, а її логарифмічне розходження усереднюється й періодично перенормовується. λ₁ > 0 підтверджує хаос. У міру сканування параметра C1 симуляція показує перехід період-1 → період-2 → період-4 → хаос (каскад подвоєння періоду).

• Фазові портрети: площини (V_C1, V_C2) і (V_C1, I_L) поруч
• Показник Ляпунова в реальному часі
• Повзунок сканування параметра для спостереження подвоєння періоду

Натовп пішоходів: модель соціальної сили

Модель соціальної сили Гельбінга-Мольнара (1995) розглядає рух пішоходів як ньютонівську динаміку з психосоціальними силами. Кожен агент має бажану швидкість руху до мети та відчуває відштовхування від інших пішоходів і стін.

Компоненти сили

Загальна сила на агента i — сума трьох доданків:

• Мотивація: F_motivation = m·(v₀·ê − v) / τ — спонукає агента до бажаної швидкості v₀ у бажаному напрямку ê з часом релаксації τ
• Соціальне відштовхування: експоненційний спад A·exp((r_ij − d_ij)/B)·n̂_ij — м'яке відштовхування з поправкою жорсткого контакту при перекритті агентів
• Відштовхування від стін: та сама експоненційна форма, застосована до найближчої точки стіни

Емерджентні явища

Магія моделі соціальної сили в тому, що з'являється без явних правил. У двонапрямленому коридорі зустрічні потоки спонтанно розділяються на стабільні смуги — мінімізуючи лобові зіткнення. У вузькому вузькому місці на виході формується аркова структура під тиском, що періодично випускає порції людей. У режимі паніки збільшення бажаної швидкості (ефект «швидше — значить повільніше») зменшує пропускну здатність, оскільки арка стає серйознішою, а агенти сильніше блокують одне одного.

• До 200 пішоходів; просторова хеш-сітка для запитів сусідів O(n)
• Три пресети сценаріїв: коридор, вузьке місце, відкрита кімната
• Перемикання режиму паніки для демонстрації ефекту «швидше — значить повільніше»
• Лічильник потоку: агентів за секунду через вихід

Що далі

Хвиля 69 прийде з алгоритмами опуклої оболонки (порівняння сканування Грехема, маршу Джарвіса й Quickhull поруч), квантовим пошуком Гровера з геометричною візуалізацією амплітуди, динамікою меандрування річки з формуванням старичних озер, фізикою мотузки Verlet, класичним перцептроном Розенблатта та орбітальним резонансом Кеплера зі скупченням з'єднань.