Перейти к содержанию

Алгоритмы

SAT (Separating Axis Theorem)

Используется для box-box коллизий.

Принцип: два выпуклых тела не пересекаются тогда и только тогда, когда существует ось, на которой их проекции не перекрываются. Для двух OBB проверяются 15 осей: - 3 оси граней бокса A - 3 оси граней бокса B - 9 кросс-произведений осей A и B

Для каждой оси вычисляется overlap. Ось с минимальным положительным overlap определяет направление контакта и глубину пенетрации.

Реализация: BoxCollider::closest_to_box_impl() в box_collider.hpp.

GJK (Gilbert-Johnson-Keerthi)

Универсальный narrow-phase алгоритм для любых выпуклых форм, определённых support-функцией.

Используется для всех пар с участием ConvexHullCollider.

Support-функция

Каждый ColliderPrimitive реализует support(direction) — самая дальняя точка коллайдера в заданном направлении: - Box: выбор знака каждой оси по проекции direction - Sphere: center + direction.normalized() * radius - Capsule: выбор полусферы + смещение на radius - ConvexHull: линейный поиск среди вершин

Minkowski Difference

GJK работает в пространстве Минковского: support(A, B, d) = A.support(d) - B.support(-d). Коллизия <==> начало координат внутри Minkowski Difference.

Алгоритм

  1. Инициализация: одна support-точка по направлению между центрами.
  2. Итеративное уточнение симплекса (1→2→3→4 точки):
  3. Для каждого размера симплекса находим ближайшую точку v к началу координат.
  4. Новая support-точка в направлении -v.
  5. Критерий сходимости: v·v - v·w <= eps * v·v.
  6. Если симплекс 4 точки и начало координат внутри — пересечение.
  7. Если сходимость — вычисляем расстояние через барицентрическую интерполяцию.

Максимум итераций: 64. Барицентрические координаты используются для восстановления ближайших точек на исходных коллайдерах.

Реализация: gjk() в gjk.hpp.

EPA (Expanding Polytope Algorithm)

Вызывается когда GJK обнаружил пересечение — нужно найти глубину пенетрации и нормаль контакта.

Алгоритм

  1. Строим начальный тетраэдр из 14 support-направлений (6 осевых + 8 диагональных).
  2. Определяем правильный обход (winding) по знаку объёма тетраэдра.
  3. Итеративное расширение политопа:
  4. Находим грань с минимальным расстоянием до начала координат.
  5. Берём support-точку в направлении нормали этой грани.
  6. Если новая точка не улучшает расстояние (< EPA_TOLERANCE = 1e-6) — грань определяет результат.
  7. Иначе: удаляем видимые грани, строим новые через horizon edges.
  8. Контактные точки восстанавливаются через барицентрическую интерполяцию.

Максимум итераций: 64.

Реализация: epa() в gjk.hpp.

Quickhull

Алгоритм построения выпуклой оболочки из облака точек.

Алгоритм

  1. Начальный тетраэдр: находим 4 максимально разнесённые точки:
  2. Экстремумы по 6 осям → самая дальняя пара → точка дальше всего от прямой → точка дальше всего от плоскости.
  3. Ориентируем по объёму для внешних нормалей.
  4. Распределение: каждая оставшаяся точка назначается грани, выше которой она находится (outside set).
  5. Итеративное расширение (до 1000 итераций):
  6. Находим грань с самой дальней outside-точкой (eye point).
  7. Собираем видимые грани из eye point.
  8. Находим horizon edges (граница между видимыми и невидимыми гранями).
  9. Удаляем видимые грани, создаём новые от horizon edges к eye point.
  10. Перераспределяем orphaned points.

Реализация: quickhull::build() в convex_hull_collider.hpp.

Sutherland-Hodgman Clipping

Используется для генерации множественных контактных точек при box-box коллизиях.

Алгоритм

  1. Находим reference face на боксе A (грань, наиболее параллельная нормали контакта).
  2. Находим incident face на боксе B (грань, наиболее антипараллельная нормали reference face).
  3. Строим clip-плоскости из рёбер reference face (нормали направлены внутрь).
  4. Обрезаем полигон incident face по каждой clip-плоскости (Sutherland-Hodgman).
  5. Точки обрезанного полигона ниже reference plane — контактные точки (до 4 штук).

Реализация: CollisionWorld::generate_box_box_contacts() в collision_world.hpp.

Moller-Trumbore

Используется для raycast ConvexHullCollider — пересечение луча с каждым треугольником оболочки.

Реализация: ConvexHullCollider::closest_to_ray() в convex_hull_collider.hpp.

Аналитические методы

Для пар без ConvexHull используются прямые формулы:

Пара Метод
Sphere-Sphere Расстояние центров минус сумма радиусов
Sphere-Box Clamp центра сферы к box в локальном пространстве
Sphere-Capsule Проекция центра сферы на ось капсулы + радиусы
Capsule-Capsule Ближайшие точки между двумя отрезками + радиусы
Capsule-Box Итеративный closest-point (сэмплирование оси + уточнение)
Box-Box SAT 15 осей (см. выше)

Raycast для примитивов: - Box: Slab method в локальных координатах - Sphere: Квадратное уравнение луч-сфера - Capsule: Пересечение с цилиндром + полусферами