2D и 3D Collision Detection

Quake (1996) был первым 3D шутером с настоящей физикой - и первым, столкнувшимся с проблемой: при наивной проверке всех пар объектов O(n²) даже 50 движущихся врагов убивали FPS. Решение - иерархия алгоритмов от грубых к точным, которую используют все современные движки.

• **Bullet Physics / PhysX:** GJK для narrow phase + BVH для broad phase во всех AAA-играх
• **Автономные роботы:** collision detection для планирования траектории манипуляторов
• **CAD/CAM системы:** проверка допусков при виртуальной сборке деталей

AABB: быстрая проверка без тригонометрии

Два прямоугольника не пересекаются, если между ними есть хотя бы один зазор по любой оси. **AABB (Axis-Aligned Bounding Box)** использует именно это: проверяет перекрытие проекций на X и Y оси. Никакой тригонометрии - только сравнение четырёх чисел.

• **O(1) на пару объектов** - четыре сравнения числел
• **Проблема:** работает только для box-aligned объектов. Повёрнутый прямоугольник на 45° выдаст ложное срабатывание
• **Применение:** первый этап broad phase - быстро отсечь явно непересекающиеся пары

**Практика:** Unity и Unreal используют AABB как broad phase для каждого объекта. Только пары с перекрывающимися AABB передаются в более точный narrow phase (SAT или GJK).

SAT: теорема о разделяющей гиперплоскости

Два выпуклых многоугольника не пересекаются тогда и только тогда, когда существует ось, на которой их проекции не перекрываются. **SAT (Separating Axis Theorem)** проверяет все потенциальные разделяющие оси - нормали к каждому ребру обоих многоугольников.

• **Работает для любых выпуклых форм** - полигонов, боксов, треугольников
• **Сложность:** O(n+m) где n,m - число вершин
• **Ограничение:** только выпуклые формы. Вогнутый меч - нужно разбить на выпуклые части
• **Бонус:** даёт глубину проникновения (MTV - Minimum Translation Vector) для физического response

GJK: разность Минковского и симплекс

Два выпуклых тела не пересекаются тогда и только тогда, когда их **разность Минковского** не содержит начало координат. GJK (Gilbert-Johnson-Keerthi, 1988) итеративно строит симплекс внутри разности Минковского, приближаясь к началу координат.

Алгоритм строит симплекс (отрезок → треугольник → тетраэдр в 3D) внутри A-B, каждый раз добавляя точку ближе к началу координат. Если симплекс содержит начало - коллизия. Если не может приблизиться - нет коллизии.

• **O(1) итераций на практике** - обычно 3-5 шагов для типичных игровых форм
• **Работает для любых выпуклых форм** без хранения явной разности Минковского
• **Используется в:** Bullet Physics, Box2D, PhysX, Havok
• **EPA (Expanding Polytope Algorithm)** - расширение GJK для глубины проникновения

GJK особенно эффективен для форм с дешёвой support function: сферы (O(1)), капсулы (O(1)), выпуклые оболочки (O(n) вершин). Bullet использует кэш результатов GJK между кадрами - warm start ускоряет до 1-2 итераций.

Пространственное разбиение: BVH и Octree

Проверять каждую пару объектов в сцене - O(n²). При 10000 объектах это 50 миллионов проверок за кадр. Пространственные структуры данных сокращают это до O(n log n), группируя объекты по регионам пространства.

**BVH (Bounding Volume Hierarchy)** строит дерево: каждый узел - AABB, содержащий все объекты поддерева. Для проверки коллизии двух BVH рекурсивно опускаемся: если AABB-узлов не пересекаются - всё поддерево пропускается.

**Quake (1996)** использовал BSP-дерево (Binary Space Partitioning) для статичной геометрии уровней. Динамические объекты (игроки) проверялись O(n²) - при 16 игроках это терпимо. Современные движки используют BVH для всего, с inkremental rebuild при движении объектов.

Иерархия collision detection

• **AABB:** 4 сравнения, O(1), только для axis-aligned форм - broad phase быстрого отсечения
• **SAT:** проверка нормалей рёбер, точен для любых выпуклых форм, даёт глубину проникновения
• **GJK:** разность Минковского + симплекс, O(1) итераций, используется в Bullet/PhysX
• **BVH/Octree:** сокращают O(n²) до O(n log n) за счёт пространственного разбиения

Связанные темы

Collision detection - основа физической симуляции и игровой логики.

• Физические движки: Rigidbody динамика — Collision response - что делать после обнаружения коллизии
• Game AI: FSM и Behavior Trees — AI использует collision data для навигации и уклонения

Вопросы для размышления

• Как изменится стратегия выбора алгоритма коллизий при переходе от 2D платформера к 3D шутеру с деформируемой геометрией?
• Какие инварианты должны сохраняться при инкрементальном обновлении BVH при движении объектов?
• Почему GJK требует выпуклости форм, и какие способы обработки невыпуклых объектов существуют в production движках?

Связанные уроки

• la-01-vectors-intro