💥 Виявлення зіткнень: від AABB до алгоритму GJK

Двофазна архітектура

Кожна практична система виявлення зіткнень використовує двофазну архітектуру. Широка фаза швидко відсіює пари об'єктів, які точно не можуть зіткнутися, використовуючи консервативні, але дешеві наближення. Вузька фаза потім виконує точні геометричні тести для невеликого набору пар-кандидатів, що пройшли широку фазу. Цей поділ є ключовим: широка фаза не повинна нічого пропускати (жодних хибнонегативних результатів), але може мати хибнопозитивні; вузька фаза мусить бути точною.

Обмежувальні паралелепіпеди, вирівняні по осях (AABB)

Найпростіший обмежувальний обʼєм — це обмежувальний паралелепіпед, вирівняний по осях (Axis-Aligned Bounding Box, AABB): найменший прямокутний паралелепіпед зі сторонами, паралельними осям координат, що повністю містить об'єкт. Для сітки (меша) AABB визначається мінімальними й максимальними координатами x, y, z серед усіх вершин.

Перевірка перетину двох AABB — це одне порівняння на кожну вісь, тобто шість порівнянь загалом:

bool aabbOverlap(AABB a, AABB b) {
  return a.min.x <= b.max.x && a.max.x >= b.min.x
      && a.min.y <= b.max.y && a.max.y >= b.min.y
      && a.min.z <= b.max.z && a.max.z >= b.min.z;
}

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

Просторове хешування для широкої фази

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

function cellKey(x, y, cellSize) {
  const cx = Math.floor(x / cellSize);
  const cy = Math.floor(y / cellSize);
  // Великі прості числа для зменшення колізій хешу
  return (cx * 92837111) ^ (cy * 689287499);
}

Для рівномірно розподілених об'єктів просторове хешування досягає складності O(1) на пошук об'єкта. Розмір комірки має відповідати середньому розміру об'єкта — надто маленькі комірки означають багато комірок на об'єкт; надто великі — багато об'єктів на комірку. Просторове хешування чудово підходить для симуляцій частинок і гідродинаміки, де взаємодіють тисячі однакових за розміром частинок.

Ієрархії обмежувальних об'ємів (BVH)

BVH — це дерево обмежувальних об'ємів. Листові вузли містять окремі примітиви (трикутники, форми). Внутрішні вузли містять AABB, що обмежують усіх своїх нащадків. Щоб перевірити об'єкт A відносно сцени, дерево BVH обходиться так: якщо AABB об'єкта A не перетинається з AABB вузла, пропускається все піддерево; інакше відбувається рекурсивний спуск у дочірні вузли. Це зводить задачу складності O(n²) до O(n log n) або кращої для типових сцен.

Побудова BVH використовує евристики розбиття. Евристика площі поверхні (Surface Area Heuristic, SAH) мінімізує очікувану кількість тестів на перетин, розбиваючи в позиції, що мінімізує SA(left)·N(left) + SA(right)·N(right), де SA — площа поверхні, а N — кількість трикутників. Побудовані за SAH дерева BVH використовуються в трасуванні променів (Embree, OptiX) і фізичних рушіях ігор (Bullet, PhysX). Динамічні сцени потребують перебудови або переприлягання BVH щокадру — сучасні GPU-будівники BVH роблять це за мілісекунди, використовуючи паралельні низхідні підходи або сортування за кодами Мортона.

Теорема про розділювальну вісь (SAT)

Для опуклих форм теорема про розділювальну вісь (Separating Axis Theorem, SAT) дає точний тест: дві опуклі форми не перетинаються тоді й лише тоді, коли існує розділювальна вісь — напрямок, уздовж якого їхні проєкції не перетинаються. Для многокутників/многогранників достатньо перевірити нормалі граней і (у 3D) векторні добутки ребер як кандидатські осі.

Для двох опуклих многокутників з n та m ребрами SAT вимагає n + m тестів осей, кожен зі складністю O(1). Якщо хоча б одна вісь розділяє їх, форми не зіткнулися. Якщо всі осі показують перетин — форми зіткнулись. Вісь з мінімальним перекриттям дає нормаль зіткнення й глибину проникнення для розрахунку відповіді. SAT точний, швидкий і надає багату контактну інформацію — це алгоритм вузької фази, який обирають для опуклих многогранників у таких рушіях, як Box2D.

Алгоритм GJK

Алгоритм Гілберта-Джонсона-Кірті (Gilbert-Johnson-Keerthi, 1988) визначає, чи перетинаються дві опуклі форми, ітеративно обчислюючи найближчу точку різниці Мінковського до початку координат. Різниця Мінковського A ⊖ B = {a − b | a ∈ A, b ∈ B} містить початок координат тоді й лише тоді, коли A і B перетинаються.

GJK використовує опорні функції: для напрямку d, support(A, d) = argmax_{a ∈ A} d·a — точка на A, найвіддаленіша в напрямку d. Для опуклих форм з аналітичними опорними функціями (сфери, капсули, паралелепіпеди) це має складність O(1). GJK ніколи явно не обчислює різницю Мінковського; він семплує її через виклики опорної функції та будує симплекс (точка, ребро, трикутник, тетраедр), що збігається до найближчого елемента.

GJK «розігрівається» симплексом з попереднього кадру, що робить його надзвичайно швидким для повільно рухомих об'єктів — зазвичай збігається за 2–4 ітерації. У поєднанні з EPA (Expanding Polytope Algorithm) для обчислення глибини проникнення при виявленому перетині, GJK+EPA є стандартом вузької фази для довільних опуклих форм у сучасних фізичних рушіях.