Broad-phase та narrow-phase виявлення зіткнень
Перевірка кожної пари з тисячі тіл на зіткнення — мільйон порівнянь за кадр. Справжні двигуни так ніколи не роблять: спершу фільтрують дешевим broad phase, і лише для тих кількох пар, що вижили, запускають точну геометричну математику.
1. Двофазний конвеєр
Кожен двигун твердих тіл ділить виявлення зіткнень на два дуже різні завдання. Broad phase дає дешеву, приблизну відповідь на питання: «які пари тіл потенційно можуть торкатися?», використовуючи швидкі перевірки обмежувальних об'ємів. Narrow phase потім дає дорогу, точну відповідь для кожної пари, що вижила: «чи ці дві конкретні форми справді торкаються, і якщо так, де саме і за якою нормаллю?»
Ця стаття — про першу задачу: алгоритмічні структури, що тримають її швидкою зі зростанням кількості тіл. Точні геометричні алгоритми, які narrow phase використовує, коли пара вижила — SAT, GJK і EPA — розглянуто у статтях Виявлення зіткнень: BVH, SAT, GJK і Фізика твердого тіла: SAT та EPA.
2. Груба сила O(N²)
Найпростіший broad phase: порівняти bounding box (AABB) кожного тіла з кожним іншим.
При N = 20 це 190 пар — тривіально. При N = 2000 це приблизно
2 мільйони перевірок пар за кадр, більшість з яких витрачені на
тіла у протилежних кінцях сцени. Наївний broadphase годиться для
малих сцен і саме для цього призначений
NaiveBroadphase у Cannon-es: прототипування й дебаг,
а не продуктивний масштаб.
3. Sweep and prune
Sweep-and-prune (SAP) сортує кінцеві точки AABB кожного тіла вздовж однієї осі (скажімо, X) в єдиний список. Два AABB можуть перетинатися у 3D лише якщо їхні проєкції перетинаються на всіх трьох осях — тож проходження вздовж X із відстеженням, які інтервали «відкриті», одразу відсіює більшість пар без будь-якої перевірки Y чи Z.
пройти зліва направо, тримати множину «активних»
коли інтервал відкривається: кандидат-пара з усіма активними
підтвердити кандидатів перевіркою перетину Y та Z
Оскільки більшість сцен змінюються поступово від кадру до кадру,
відсортований список майже завжди вже відсортований — сортування
вставками на майже відсортованих даних працює близько до O(N),
тому SAP і є broadphase за замовчуванням у Cannon-es
(SAPBroadphase) і у більшості інших продуктивних
двигунів фізики.
4. Рівномірні сітки та просторове хешування
Рівномірна сітка ділить простір на комірки фіксованого розміру й розкладає кожне тіло по комірках, що перетинає його AABB. Кандидати на зіткнення — просто інші тіла в тій самій комірці — без сортування, вставка/видалення O(1) на тіло.
- Найкраще працює, коли тіла приблизно однакового розміру й рівномірно розподілені — саме випадок симуляцій Сипкі матеріали та піщаних куп на цьому сайті, де тисячі схожих за розміром зерен взаємодіють локально.
- Погіршується, коли розміри тіл сильно відрізняються (величезна площина підлоги плюс крихітні уламки) — гігантський AABB торкається майже всіх комірок, і сітка перестає щось фільтрувати.
- Просторове хешування узагальнює ту саму ідею на необмежені, розріджені світи: координати комірок хешуються у таблицю фіксованого розміру замість щільного масиву, уникаючи витрат пам'яті на порожні регіони.
5. BVH та AABB-дерева
Bounding Volume Hierarchy організовує тіла в бінарне дерево, де бокс кожного вузла щільно охоплює бокси його дітей. Запит (наприклад, «що торкається цей промінь чи це рухоме тіло?») спускається деревом, пропускаючи цілі піддерева, чий bounding box не перетинає запит — перетворюючи лінійне сканування на логарифмічне.
спуск збалансованим BVH: O(log N)
BVH особливо добре себе показує для сцен із дуже різними розмірами тіл і для статичної чи напівстатичної геометрії, яку дорого перебудовувати щокадру — наприклад, шматки уламків зруйнованого меша у Руйнуванні твердих тіл, або статична геометрія траси у Фізиці автомобіля, для якої BVH потрібно побудувати лише раз при завантаженні.
Для сцен із багатьма рухомими тілами двигуни зазвичай refit BVH щокадру (підлаштовують бокси існуючих вузлів під нові позиції), а не перебудовують його з нуля — набагато дешевше, ціною поступово погіршуваної якості дерева, що зрештою вимагає повної перебудови.
6. Порівняння складності
| Структура | Вартість оновлення | Вартість запиту | Найкращий випадок |
|---|---|---|---|
| Груба сила O(N²) | — | O(N²) | < 50 тіл |
| Sweep & prune | O(N log N) найгірший, ~O(N) типовий | O(N + K) | Когерентні, помірно динамічні сцени |
| Рівномірна сітка | O(N) | O(N/комірки + K) | Однакові розміри тіл, щільно (сипкі матеріали, частинки) |
| Просторовий хеш | O(N) | O(1) в середньому на комірку | Розріджені, необмежені світи |
| BVH (збалансоване) | O(N log N) перебудова, O(N) refit | O(log N) | Змішані розміри, статична/напівстатична геометрія |
K = кількість справжніх кандидатних пар, зазвичай ≪ N².
7. Де підключається narrow phase
Коли broad phase передає короткий список кандидатних пар, narrow phase запускає точні перевірки: теорема розділяючої осі (SAT) для опуклих поліедрів, GJK для загальних опуклих запитів відстані, та EPA для видобування глибини проникнення після того, як GJK підтвердив перетин. Ці алгоритми коштують O(1)–O(ребра) на пару, але надто дорогі, щоб запускати на кожній можливій парі в сцені — саме тому й існує broad phase. Повна математика цієї половини конвеєра викладена у статті Виявлення зіткнень: BVH, SAT, GJK.
8. Як обрати стратегію
- Мала сцена, < 50 тіл: груба сила O(N²) — простота перемагає, вартість незначна.
- Загальне призначення, помірна кількість тіл: sweep and prune — за замовчуванням у Cannon-es, гарний перший вибір для більшості симуляцій.
- Тисячі схожих за розміром частинок: рівномірна сітка чи просторовий хеш — сипкі матеріали, SPH-рідини, самозіткнення тканини.
- Змішані розміри, переважно статичні сцени: BVH — рельєф, уламки руйнування, великі середовища з малими рухомими об'єктами.
Побачити broad phase у масштабі
Тисячі зерен використовують рівномірну сітку; демо руйнування нижче — BVH над опуклими уламками.
🪨 Сипкі матеріали 🧱 Руйнування твердих тіл