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

В физическом движке процесс обнаружения столкновений разделяется на две ключевые стадии:

  1. Broad Phase (широкая фаза) — грубая фильтрация потенциально пересекающихся тел.
  2. Narrow Phase (узкая фаза) — точное вычисление факта столкновения и его характеристик.

В библиотеке Ammo.js узкая фаза реализована на основе алгоритмов, унаследованных из Bullet Physics. Основную роль здесь играют алгоритмы GJK (Gilbert–Johnson–Keerthi) и EPA (Expanding Polytope Algorithm).

Именно на этом этапе вычисляются:

  • факт пересечения тел,
  • точки контакта,
  • нормаль столкновения,
  • глубина проникновения,
  • контактный импульс.

Архитектура узкой фазы в Ammo.js

Внутри движка за обработку узкой фазы отвечает подсистема btCollisionDispatcher. Она выбирает соответствующий алгоритм на основе типов коллайдеров.

Основные компоненты:

  • btCollisionAlgorithm
  • btConvexConvexAlgorithm
  • btGjkPairDetector
  • btManifoldResult
  • btPersistentManifold

Для выпуклых тел используется связка GJK + EPA, поскольку она универсальна и численно устойчива для большинства геометрических форм.

Выпуклые множества и функция поддержки

GJK работает исключительно с выпуклыми объектами. В Ammo.js к таким формам относятся:

  • btBoxShape
  • btSphereShape
  • btCapsuleShape
  • btCylinderShape
  • btConvexHullShape

Ключевым элементом алгоритма является функция поддержки (support function):

S(d) = точка формы, максимально удалённая в направлении d

В терминах Ammo.js это метод:

shape.localGetSupportingVertex(direction)

Эта операция выполняется чрезвычайно быстро и позволяет алгоритму обходиться без явного перебора граней.

Алгоритм GJK

Геометрическая идея

Задача GJK — определить, содержит ли разность Минковского двух тел начало координат.

Разность Минковского:

A ⊖ B = { a - b | a ∈ A, b ∈ B }

Если начало координат принадлежит этой разности, значит тела пересекаются.

Основные шаги алгоритма

  1. Выбирается произвольное направление.

  2. Получается support-точка разности Минковского.

  3. Строится симплекс (точка, отрезок, треугольник или тетраэдр).

  4. Проверяется, окружает ли симплекс начало координат.

  5. Итерации продолжаются до:

    • обнаружения пересечения,
    • доказательства отсутствия пересечения.

Симплекс в 3D

В трёхмерном пространстве используются:

  • 1 точка — начальное состояние
  • 2 точки — отрезок
  • 3 точки — треугольник
  • 4 точки — тетраэдр

Алгоритм постепенно приближается к началу координат.

Реализация GJK в Ammo.js

Внутренне используется класс:

btGjkPairDetector

Он работает совместно с:

  • btVoronoiSimplexSolver
  • btConvexPenetrationDepthSolver

GJK в Ammo.js выполняет две задачи:

  1. Проверка факта пересечения.
  2. Вычисление минимального расстояния между телами (если пересечения нет).

Это позволяет использовать его не только для столкновений, но и для триггеров и proximity-запросов.

Ограничения GJK

Алгоритм определяет только:

  • пересекаются ли объекты,
  • минимальное расстояние.

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

Алгоритм EPA

EPA применяется после GJK, если обнаружено пересечение.

Назначение

Определить:

  • точную глубину проникновения,
  • нормаль столкновения,
  • контактную точку.

Основная идея

Если GJK завершился тетраэдром, содержащим начало координат, то EPA:

  1. Берёт полученный тетраэдр.
  2. Расширяет его в многогранник.
  3. Итеративно ищет грань, ближайшую к началу координат.
  4. Расширяет многогранник в направлении нормали этой грани.
  5. Повторяет процесс до достижения численной стабильности.

Результатом становится:

  • нормаль проникновения,
  • глубина (расстояние от начала до ближайшей грани).

Связка GJK + EPA

В Ammo.js последовательность выглядит так:

  1. btGjkPairDetector определяет факт пересечения.
  2. Если пересечение есть — вызывается btGjkEpaPenetrationDepthSolver.
  3. Полученные данные передаются в btManifoldResult.
  4. Создаётся или обновляется btPersistentManifold.

Этот manifold хранит контактные точки между кадрами, что важно для устойчивости симуляции.

Численные аспекты

Алгоритмы GJK и EPA чувствительны к:

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

В Ammo.js используются:

  • ε-пороги,
  • ограничение числа итераций,
  • fallback-методы.

При неправильном масштабе сцены (например, объекты размером 0.0001 или 1e6) возможны:

  • нестабильные контакты,
  • «дрожание»,
  • потеря столкновений.

Рекомендуемый масштаб — объекты порядка 0.1–10 единиц.

Производительность

GJK имеет сложность, зависящую от числа итераций, обычно:

  • 5–20 итераций для непересекающихся тел,
  • до 30–40 при пересечении.

EPA работает дольше, так как строит выпуклый многогранник, но применяется только при фактическом пересечении.

Оптимизация достигается за счёт:

  • кэширования манifold’ов,
  • warm starting,
  • раннего выхода при достижении порога.

Пример использования в Ammo.js

Создание двух выпуклых тел:

const shapeA = new Ammo.btBoxShape(new Ammo.btVector3(1, 1, 1));
const shapeB = new Ammo.btSphereShape(1);

const transformA = new Ammo.btTransform();
transformA.setIdentity();
transformA.setOrigin(new Ammo.btVector3(0, 0, 0));

const transformB = new Ammo.btTransform();
transformB.setIdentity();
transformB.setOrigin(new Ammo.btVector3(1.5, 0, 0));

После добавления тел в мир, узкая фаза автоматически выполнит:

  • broad phase проверку AABB,
  • GJK проверку,
  • при необходимости EPA,
  • генерацию контакта.

Получение контактов:

const dispatcher = physicsWorld.getDispatcher();
const numManifolds = dispatcher.getNumManifolds();

for (let i = 0; i < numManifolds; i++) {
    const manifold = dispatcher.getManifoldByIndexInternal(i);
    const numContacts = manifold.getNumContacts();

    for (let j = 0; j < numContacts; j++) {
        const contactPoint = manifold.getContactPoint(j);
        const distance = contactPoint.getDistance();
    }
}

Если distance < 0, имеется проникновение, вычисленное через EPA.

Поддержка невыпуклых форм

GJK применяется только к выпуклым телам. Для невыпуклых:

  • используется разбиение на выпуклые части,
  • применяется SAT,
  • используются специализированные алгоритмы (btBvhTriangleMeshShape).

Однако даже при работе с мешами большинство проверок сводится к выпуклым примитивам, что делает GJK центральным элементом системы.

Роль узкой фазы в устойчивости симуляции

Корректность работы GJK/EPA напрямую влияет на:

  • стабильность stacking-сцен,
  • корректность расчёта импульсов,
  • отсутствие «туннелирования»,
  • реалистичность реакции тел.

Ошибки на этом уровне приводят к:

  • вибрации объектов,
  • залипанию,
  • сквозному прохождению,
  • взрывным импульсам.

Поэтому реализация GJK/EPA в Ammo.js максимально близка к оригиналу Bullet Physics и проверена многолетней практикой в игровых и инженерных приложениях.

Оглавление