🎮 Розробка ігор · Фізичні рушії
📅 Березень 2026⏱ ≈ 12 хв читання🔴 Просунутий · Останнє оновлення: 28 травня 2026 р.

Виявлення зіткнень

Щоб об'єкти відскакували правильно, треба розв'язати дві задачі: які пари об'єктів можуть торкатися (широка фаза) і як саме вони торкаються (вузька фаза). Алгоритми, що стоять за AABB, деревами BVH, SAT, GJK та EPA, є основою кожного фізичного рушія.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Двофазний конвеєр

За N об'єктів наївна перевірка пар O(N²) надто повільна. Сучасні рушії розбивають виявлення зіткнень на дві фази:

Фаза 1
Широка фаза
Знаходить пари-кандидати, що перекриваються, за допомогою дешевих обмежувальних об'ємів. Результат: короткий список кандидатів.
Фаза 2
Вузька фаза
Перевіряє точний перетин форм для кожної пари-кандидата. Знаходить точки контакту, нормаль, глибину проникнення.
Фаза 3
Реакція
Застосовує імпульси / корекцію положення, щоб усунути взаємне проникнення й обчислити швидкості після зіткнення.

2. Широка фаза — дерева BVH та AABB

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

Кожна форма загортається в паралелепіпед, вирівняний за осями світу. Два AABB перекриваються тоді й лише тоді, коли вони перекриваються одночасно за всіма 3 осями — перевіряється 6 порівняннями.

Перевірка перекриття AABB overlap = (aMin.x <= bMax.x && aMax.x >= bMin.x) && (aMin.y <= bMax.y && aMax.y >= bMin.y) && (aMin.z <= bMax.z && aMax.z >= bMin.z);

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

BVH — це двійкове дерево, де кожен вузол зберігає AABB, що охоплює всіх його нащадків. Стратегія побудови (низхідна SAH):

  1. Оберіть вісь розбиття (найдовша вісь поточного AABB).
  2. Відсортуйте примітиви вздовж цієї осі.
  3. Знайдіть позицію розбиття, що мінімізує евристику площі поверхні (SAH): вартість = N_left · Area_left + N_right · Area_right.
  4. Рекурсивно повторюйте для кожної половини, доки розмір листа ≤ порогу (~4 трикутники).

Обхід: починаємо з кореня. Якщо немає перекриття з AABB вузла, відсікаємо все піддерево. Інакше рекурсивно заходимо в нащадків. У середньому O(log N) на запит; результат — O(K) пар-кандидатів, де K — фактична кількість перекриттів.

Динамічний BVH: для рухомих об'єктів перебудовуйте вузли знизу вгору або використовуйте інкрементальне дерево «вставлення/видалення» з потовщенням AABB (розширте AABB на буфер швидкості, щоб їх не треба було оновлювати щокадру). Bullet Physics і Jolt використовують цей підхід.

3. Вузька фаза — SAT

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

Для двох опуклих багатокутників A і B кандидатами на розділювальні осі є нормалі до ребер обох форм. Алгоритм:

  1. Для кожної нормалі до ребра A спроєктуйте всі вершини A і B на цю вісь.
  2. Якщо спроєктовані інтервали не перекриваються → форми розділені → повертаємо false (немає зіткнення).
  3. Повторіть для нормалей до ребер B.
  4. Якщо за всіма осями є перекриття → форми ЗІШТОВХУЮТЬСЯ. Відстежуйте вісь мінімального перекриття → нормаль проникнення.
Інтервал проєкції project(shape, axis) → [min, max] where min = min_i(dot(vertex_i, axis)) max = max_i(dot(vertex_i, axis)) overlap = min(maxA, maxB) - max(minA, minB) separated = overlap < 0

Для 3D опуклих багатогранників: перевіряйте нормалі граней обох форм ПЛЮС векторні добутки пар ребер (ребро з A × ребро з B). Усього осей = F_A + F_B + E_A × E_B. Дострокове завершення на першій розділювальній осі робить це швидким на практиці.

Обмеження SAT: працює лише для опуклих форм. Для увігнутих сіток розкладіть їх на опуклі оболонки (наприклад, алгоритмом VHACD) і перевіряйте кожну пару оболонок.

4. Алгоритм GJK

Алгоритм Гілберта-Джонсона-Кірті є галузевим стандартом для зіткнень опуклих форм у 3D. Ключова ідея: дві опуклі форми A і B не перетинаються тоді й лише тоді, коли початок координат не міститься в різниці Мінковського A ⊕ (−B).

Різниця Мінковського M = {a − b | a ∈ A, b ∈ B} також опукла. GJK знаходить точку в M, найближчу до початку координат, використовуючи лише опорну функцію: для напрямку d повертає вершину M, що сягає найдалі в цьому напрямку.

Опорна функція GJK support(A, B, d) = furthestPoint(A, d) − furthestPoint(B, −d) // Немає потреби явно будувати M

GJK будує симплекс (точка → відрізок → трикутник → тетраедр у 3D), що наближається до початку координат. На кожному кроці він запитує: чи містить поточний симплекс початок координат? Якщо так — зіткнення. Якщо ні — знаходить наступний напрямок пошуку до початку координат і додає нову опорну точку. Збігається за O(1) ітерацій для більшості форм.

Опорні функції тривіально швидкі для сфери (r·d̂), капсули, паралелепіпеда (sign(d)·halfExtents) та опуклої оболонки (сходження на пагорб за O(√N)). Саме тому GJK обробляє довільні опуклі форми без попереднього обчислення різниці Мінковського.

5. EPA — контактні многовиди

GJK каже вам, чи форми зіштовхуються, але не глибину проникнення й не контактну нормаль. Алгоритм розширення політопа спирається на симплекс GJK, коли виявлено зіткнення:

  1. Почніть із симплекса від GJK (тетраедр, що містить початок координат).
  2. Знайдіть грань політопа, найближчу до початку координат (напрямок мінімального проникнення).
  3. Розширте політоп, знайшовши опорну точку в напрямку зовнішньої нормалі грані.
  4. Замініть грань двома новими трикутниками, що з'єднуються з новою точкою.
  5. Повторюйте, доки жодна нова опорна точка не виходить далі → збіжність. Найближча грань дає нормаль і глибину проникнення.

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

Порада щодо продуктивності: GJK+EPA виконується за ~мікросекунди для типових ігрових об'єктів. Теплий старт (повторне використання симплекса з минулого кадру) різко скорочує кількість ітерацій для форм, що рухаються повільно.

6. Неперервне виявлення зіткнень

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

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

7. Нотатки щодо реалізації