Непрерывное обнаружение столкновений: принципы и ограничения

В физическом движке дискретная проверка столкновений выполняется в фиксированные моменты времени — на каждом шаге симуляции. Если объект за один шаг перемещается на значительное расстояние, возможна ситуация «туннелирования», при которой быстро движущееся тело проходит сквозь другое без фиксации контакта. Непрерывное обнаружение столкновений (CCD) решает эту проблему путём анализа движения тела в пределах временного интервала шага.

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

Дискретная и непрерывная модели

Дискретная проверка

В дискретной модели:

  • положение тел обновляется;
  • выполняется проверка пересечения объёмов;
  • создаются контакты.

Если объект переместился от точки A к точке B и за время шага полностью пересёк другое тело, пересечения в дискретных точках может не оказаться.

Основной недостаток — зависимость точности от величины timeStep.

Непрерывная проверка

В CCD рассматривается траектория движения тела за интервал времени dt. Проверяется не только конечное положение, но и весь путь.

Ключевая идея — вычисление Time of Impact (TOI) — момента времени внутри шага, когда происходит первое касание.

Time of Impact (TOI)

TOI — это параметр t ∈ [0, 1], отражающий долю шага симуляции, на которой тела впервые соприкасаются.

Алгоритм включает:

  1. Представление движения тела как линейной интерполяции:

    position(t) = p0 + v * t

  2. Формирование “swept volume” — объёма, охватывающего движение.

  3. Поиск минимального t, при котором расстояние между телами становится равным нулю (или меньше допустимого порога).

В Oimo.js используется упрощённая модель CCD, ориентированная на линейное движение, без полноценной обработки сложных вращательных сценариев.

Подходы к реализации CCD

1. Swept Sphere / Swept AABB

Для упрощённых форм (сфера, AABB) можно аналитически вычислить пересечение вдоль траектории.

  • Сфера → решение квадратного уравнения.
  • AABB → проверка интервалов по осям.

Метод быстрый, но ограничен типами геометрии.

2. Conservative Advancement

Алгоритм постепенно «продвигает» объект вперёд во времени:

  • вычисляется расстояние между телами;
  • определяется максимально допустимый шаг по времени;
  • процесс повторяется до нахождения контакта.

Преимущества:

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

Недостатки:

  • высокая вычислительная сложность;
  • возможные численные погрешности.

CCD в архитектуре Oimo.js

В Oimo.js система столкновений состоит из двух этапов:

Broad Phase

  • Быстрое определение потенциально пересекающихся пар.
  • Использование AABB.
  • Оптимизация через пространственное разбиение.

CCD частично влияет на Broad Phase, поскольку AABB расширяется с учётом движения (swept AABB).

Narrow Phase

  • Точная проверка геометрии.
  • Вычисление точки контакта.
  • Расчёт нормали и глубины проникновения.

При включённом CCD используется:

  • прогнозирование позиции;
  • вычисление TOI;
  • коррекция положения тела до момента контакта.

Когда необходима непрерывная проверка

CCD критически важна в следующих случаях:

  • пули и снаряды;
  • мелкие объекты с большой скоростью;
  • тонкие статические поверхности;
  • малый timeStep недоступен из-за производительности.

Если скорость объекта превышает его размер за один шаг:

velocity * dt > objectSize

риск туннелирования резко возрастает.

Ограничения CCD в Oimo.js

1. Ограниченная поддержка вращения

Непрерывная проверка преимущественно учитывает линейное движение. Быстрое вращение тонких объектов может привести к неточностям.

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

CCD требует:

  • дополнительных вычислений расстояний;
  • итеративного поиска TOI;
  • повторной обработки контактов.

В сложных сценах с большим количеством динамических тел нагрузка возрастает экспоненциально.

3. Численные ошибки

Возможны:

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

Поэтому вводятся:

  • минимальный порог расстояния;
  • ограничение числа итераций;
  • epsilon-коррекции.

4. Ограниченная применимость к сложным формам

Для сложных мешей CCD часто не применяется напрямую. Используются:

  • выпуклые аппроксимации;
  • примитивные формы (Box, Sphere);
  • compound-объекты.

Настройка и управление поведением

В конфигурации тела можно задавать:

  • тип (dynamic, static, kinematic);
  • флаг включения непрерывной проверки;
  • параметры скорости;
  • коэффициенты упругости.

Практическая стратегия:

  • включать CCD только для быстрых тел;
  • ограничивать максимальную скорость;
  • использовать фиксированный timeStep;
  • избегать чрезмерно тонких геометрий.

Связь CCD с шагом симуляции

Уменьшение timeStep снижает вероятность туннелирования, но:

  • увеличивает количество вычислений;
  • не гарантирует отсутствие пропусков при экстремальных скоростях.

CCD позволяет сохранить разумный timeStep, обеспечивая при этом корректную обработку столкновений.

Оптимальная конфигурация:

  • фиксированный шаг (например, 1/60);
  • субшаги при высокой нагрузке;
  • CCD для критичных объектов.

Взаимодействие с решателем ограничений

После определения TOI:

  1. Позиция объекта корректируется до момента касания.
  2. Формируется контактное ограничение.
  3. Импульсный решатель устраняет проникновение.
  4. Продолжается симуляция оставшейся части шага.

Такой процесс может повторяться несколько раз за один кадр, что влияет на стабильность и производительность.

Практические сценарии

Быстро движущийся снаряд

  • Малый радиус.
  • Высокая скорость.
  • Статическая цель.

Без CCD объект проходит сквозь цель. С CCD вычисляется точный момент столкновения.

Падающий тонкий объект

Если толщина объекта меньше возможного перемещения за шаг, дискретная проверка не гарантирует обнаружения касания поверхности.

CCD предотвращает проникновение в плоскость.

Баланс точности и производительности

Непрерывное обнаружение столкновений — компромисс между:

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

В интерактивных приложениях, веб-играх и визуализациях на базе Oimo.js целесообразно применять гибридный подход:

  • базовая дискретная проверка для большинства объектов;
  • выборочная активация CCD для критически быстрых тел;
  • контроль скорости и геометрической сложности.

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

Оглавление