Узкая фаза: алгоритм GJK и EPA

Oimo.js — это легковесная JavaScript-библиотека для реализации физики твердых тел, специализирующаяся на симуляции жестких тел с ограниченными ресурсами. Основной упор сделан на производительность в браузере и мобильных устройствах, что достигается оптимизацией алгоритмов столкновений и интеграцией упрощённых моделей жесткости. Библиотека использует детерминированные подходы к коллизиям, что важно для сетевых игр и симуляций с повторяемыми результатами.

Структура тел и их свойства

В Oimo.js каждое физическое тело (RigidBody) имеет ряд ключевых свойств:

  • Масса и центр масс — определяют динамику тела.
  • Инвертированная матрица инерции — используется для вычисления углового ускорения.
  • Форма коллайдера (Shape) — может быть куб, сфера, цилиндр, коническая или пользовательская.
  • Позиция и ориентация — задаются через векторы и кватернионы, обеспечивая точное вращение без глюков углов Эйлера.

Каждое тело может обладать статическим, динамическим или кинематическим режимом, что определяет, как оно реагирует на силы и столкновения.

Узкая фаза столкновений

Симуляция столкновений в Oimo.js делится на две фазы:

  1. Широкая фаза (Broad Phase) — предварительное определение потенциально сталкивающихся пар с использованием структур типа AABB (Axis-Aligned Bounding Box).
  2. Узкая фаза (Narrow Phase) — точное определение точки контакта и нормали столкновения. Здесь применяются алгоритмы GJK и EPA.

Алгоритм GJK (Gilbert–Johnson–Keerthi)

GJK служит для проверки пересечения двух выпуклых тел. Основная идея заключается в использовании convex hull каждой фигуры и вычислении разности множеств:

  • Minkowski Difference — разность двух выпуклых множеств форм, которая превращает задачу проверки столкновения в проверку прохождения начала координат через эту разность.
  • Simplex — множество точек, постепенно приближающихся к началу координат.

Процесс алгоритма:

  1. Выбирается начальная точка в пространстве Minkowski Difference.
  2. Итеративно строится simplex (точка, отрезок, треугольник, тетраэдр) и проверяется, содержит ли он начало координат.
  3. Если да — тела пересекаются; если после заданного числа итераций simplex не охватывает начало, тела не пересекаются.

Особенности реализации в Oimo.js:

  • Векторные операции оптимизированы для JS: минимизация создания новых объектов.
  • Функция support вычисляет экстремальные точки тела в заданном направлении.
  • Обработка коллизий сфер, коробок и конических форм адаптирована к особенностям браузерной симуляции.

Алгоритм EPA (Expanding Polytope Algorithm)

EPA применяется после того, как GJK обнаружил пересечение. Она вычисляет точку контакта, нормаль и глубину проникновения, что необходимо для корректного ответа столкновения:

  1. Начальный polytope создается из simplex, найденного GJK.
  2. Выбирается грань polytope, ближайшая к началу координат.
  3. Вычисляется новая опорная точка в направлении нормали этой грани.
  4. Грань расширяется с добавлением новой точки, корректируя полигон.
  5. Процесс повторяется до достижения точности, определяемой порогом ε.

Результатом работы EPA являются:

  • Глубина проникновения — scalar, показывающий, насколько глубоко второе тело вошло в первое.
  • Нормаль контакта — направление, вдоль которого необходимо приложить силу коррекции.
  • Точки контакта — могут быть один или несколько, используются для расчета импульсов реакции.

Применение GJK и EPA в симуляции

В Oimo.js узкая фаза реализована через объект CollisionDetector, который:

  • Использует GJK для определения пересечения.
  • При пересечении запускает EPA для вычисления контактной информации.
  • Результаты сохраняются в структуре ContactPoint, содержащей нормаль, точку, глубину и идентификаторы тел.

Эта информация затем передается системе импульсного разрешения столкновений, которая вычисляет корректирующие силы и моменты, учитывая массу и момент инерции тел.

Оптимизация производительности

Несмотря на высокую точность, алгоритмы GJK и EPA могут быть ресурсоемкими при большом количестве тел. В Oimo.js применяются следующие техники оптимизации:

  • Кеширование support-точек — уменьшение повторных вычислений.
  • Лимит итераций — предотвращает зависание симуляции на сложных формах.
  • Использование простых форм коллайдеров для большинства объектов сцены.
  • Параллельная широкая фаза — уменьшает количество вызовов узкой фазы.

Практические аспекты

  • Алгоритмы GJK и EPA работают только с выпуклыми телами; для вогнутых форм применяются разбиения на несколько выпуклых частей.
  • Малые погрешности могут возникать при точках касания на гранях; для сглаживания используется порог ε.
  • Корректная интеграция с временным шагом (timeStep) обеспечивает стабильность симуляции.

Эта комбинация GJK и EPA в Oimo.js обеспечивает высокую точность столкновений, минимальное проседание производительности и позволяет создавать интерактивные 3D-сценарии с реалистичной физикой твердых тел.

Оглавление