Обнаруже́ние столкнове́ний () — вычислительная проблема обнаружения пересечений между собой двух или более объектов. Тема чаще всего связана с её использованием в физических движках, компьютерной анимации и робототехнике. В дополнение к определению, столкнулись ли два объекта, системы обнаружения столкновений могут вычислить время воздействия и сообщить о коллекторе контакта (набор пересечения точек)Ericson, Christer. Real-time Collision Detection. Elsevier, 2005, p. 13.. Реакция на столкновение (что происходит, когда столкновение обнаружено) зависит от конкретного моделируемого процесса. В алгоритмах обнаружения столкновений широко применяются понятия из линейной алгебры и вычислительной геометрии. Алгоритмы обнаружения столкновений являются одной из основных составляющих физики трёхмерных компьютерных игр.
Обзор
Функционирование физической модели подразумевает проведение физических экспериментов, например игры в бильярд. Физика сталкивающихся бильярдных шаров хорошо описана физикой твёрдого тела и теорией абсолютно упругого удара. Начальные условия задаются абсолютно точными физическими характеристиками бильярдного стола и шаров, а также изначальными координатами шаров. Имея заданное ускорение шара «битка» (предположительно появившегося в результате удара игрока кием по битку), мы хотим вычислить точные траектории движения, скорости и места остановки всех шаров с помощью компьютерной программы. Физический движок, моделирующий бильярд, будет состоять из нескольких компонентов, один из которых будет отвечать за точное вычисление столкновений между шарами. Этот компонент является примером нестабильной части модели — небольшие ошибки в вычислениях столкновений будут приводить к значительным изменениям в результатах — конечных положениях шаров на столе.
Компьютерные игры предъявляют к физическим движкам примерно те же требования, за исключением некоторых существенных отличий. В то время как моделирование физических опытов требует создания максимально точного математического аппарата, описывающего реальный мир, компьютерные игры нуждаются в физике лишь правдоподобно выглядящей, но при этом вычисляемой в режиме реального времени, пусть и грубо. Компромиссы допускаются, пока это устраивает игрока и имеет приемлемый визуальный реализм. Поэтому тело, которое проверяется на столкновение, — так называемый хитбокс или коллайдер — проще, чем трёхмерная модель персонажа. Обнаружение столкновений в физических симуляциях Физические движки отличаются способами, которыми они реагируют на столкновения. Некоторые используют гибкость материалов для вычисления силы, возникающей в результате столкновения и влияющей на результат столкновения в последующие временные интервалы, что достаточно затратно с точки зрения вычислительных ресурсов. Некоторые модели вычисляют аппроксимированное время столкновения с помощью линейной интерполяции, после чего «откатывают» состояние сцены на некоторый момент времени и просчитывают столкновение на основе законов сохранения энергии.
Некоторые используют итеративную линейную интерполяцию (метод Ньютона) для вычисления времени столкновения с гораздо более высокой точностью, чем остальную часть вычислений. Метод обнаружения столкновений нарушает принцип когерентности времени с целью возможности повышения точности временных промежутков без повышения общей нагрузки на вычислительные ресурсы системы.
После неупругого столкновения возможно возникновение особых состояний скольжения или покоя, которые, например, в свободном физическом движке Open Dynamics Engine эмулируются с помощью ограничений. Ограничения исключают инерцию и, как следствие, нестабильность. Реализация покоя в понятиях графа сцены позволяет избежать смещений.
Другими словами, реализации физических моделей обычно делятся на два пути:
определение столкновения апостериори, априорный подход (обнаружение до происхождения столкновения).
В дополнение к делению на апостериорные и априорные подходы практически все современные алгоритмы обнаружения столкновений делятся на иерархию алгоритмов.
Различия апостериорного и априорного подходов В случае апостериорного подхода просчёт модели реализуется через просчёт состояний сцены через небольшие промежутки времени, в каждый из которых происходит проверка на наличие пересекающихся объектов или располагающихся столь близко, что можно их считать пересекающимися. На каждом шаге моделирования создаётся список пересекающихся тел, позиции и траектории этих тел «корректируются» с учётом факта произошедшего столкновения. Этот подход называется апостериорным, поскольку по сути непосредственный точный момент столкновения упускается и обнаруживается уже через некоторое время после того, как он произошёл (или за некоторое время до того, в зависимости от алгоритма).
При априорном подходе создаётся алгоритм обнаружения столкновений, способный предсказывать траекторию движений физических тел с высокой точностью. Случаи столкновений описываются этой моделью с высокой точностью, и физические тела в сущности никогда не оказываются в состоянии взаимного проникновения. Этот подход называется априорным, поскольку моменты столкновений тел определяются до изменения пространственной конфигурации объектов сцены.
Из апостериорного подхода проистекают его основные достоинства. Алгоритму не нужно манипулировать значительным количеством физических переменных — его исходными данными является простой список физических тел, результатом является подмножество тел пересекающихся. Алгоритму не приходится иметь дело с учётом сил трения, упругих или — ещё хуже — неупругих столкновений, а также просчитывать изменение внутреннего состояния деформируемых тел. Кроме того, апостериорный алгоритм по сути проще на одно измерение, так как в априорном подходе приходится иметь дело с дополнительной осью — временем, от чего избавлен подход апостериорный.
С другой стороны, апостериорные алгоритмы приводят к проблемам на этапе «исправления» произошедших взаимопроникновений тел, которые не происходят в реальной физической сцене.
Преимуществами априорного подхода являются точность и стабильность модели. Сложно (но теоретически возможно) полностью отделить физическую составляющую модели сцены от алгоритма обнаружения столкновений. В большинстве случаев, кроме самых простых, проблема предсказания момента времени столкновения двух тел по некоторым исходным данным не имеет общего абстрагированного от остальной модели решения. Применяется численный метод поиска корня.
Некоторые тела находятся в состоянии покоящегося контакта, то есть формально находятся в постоянном столкновении, не приводящем к отталкивающимся движениям тел или к взаимопроникновению (например, ваза, стоящая на столе). Во всех случаях покоящийся контакт требует исключительного подхода: если два тела столкнулись («апостериори») или скользят («априори») и их относительное движение ниже определённого порога — трение трактуется как прилипание, и оба объекта объединяются в единую ветвь графа сцены.
Оптимизация Очевидные подходы к обнаружению столкновений для всей сцены со множеством объектов весьма медлительны. Проверка на факт столкновения каждого объекта с каждым работоспособна, но крайне неэффективна с точки зрения вычислительной трудоёмкости для большого количества объектов. Проверка объектов со сложной геометрией на предмет наличия столкновения между собой очевидным методом проверки столкновения отдельных граней тел весьма затратна сама по себе. Таким образом, значительное число исследований в области направлено на решение проблем производительности.
Применение временно́й когерентности Во многих приложениях конфигурация физических тел меняется на протяжении итерационного отрезка времени весьма незначительно. Многие объекты сцены не двигаются вообще. Алгоритмы создаются таким образом, что результаты вычислений, сделанные на предыдущей итерации, используются на следующей, что приводит к повышению производительности.
На уровне грубого определения столкновений целью является нахождение объектов, которые потенциально могут пересекаться. Эти пары потребуют дальнейшего анализа. Один из таких алгоритмов был разработан из Калифорнийского университета в Беркли, предложившей применение метода ограничивающих параллелепипедов, направляющие вектора ребер которых коллинеарны векторам базиса декартовой системы координат, для всех N тел сцены. Позже эти ограничивающие параллелепипеды стали известны как Axis-aligned bounding box (AABB).
Каждый параллелепипед представляется тройкой отрезков, например . Распространённым алгоритмом для обнаружения столкновений ограничивающих параллелепипедов является алгоритм «Sweep and prune» (; ). Очевидно, что два таких параллелепипеда и пересекаются тогда и только тогда, когда пересекается с , пересекается с и пересекается с . Предполагается, что если от одной временной итерации до следующей и пересекаются, то весьма вероятно, что они будут по-прежнему пересекаться и на следующей итерации. Также, если они не пересекались на предыдущей итерации, весьма вероятно, что не будут пересекаться и на следующей.
Итак, проблема сводится к итерационному контролю от «кадра» к «кадру» за тем, которые из отрезков пересекаются. Имеются три списка интервалов (по одному на каждую из осей координат), и все три одинаковой длины, так как длина каждого равна , по числу объектов сцены и, соответственно, их ограничивающих параллелепипедов. Каждому из списков соответствует матрица , элементы которой равны 1 или 0. — в случае, если отрезки и пересекаются, и , если нет.
Допустим, матрица остаётся практически неизменной от одной итерации к следующей. Чтобы это использовать, список отрезков содержится в виде помеченных крайних точек. Каждый элемент списка располагает координатами крайней точки и уникальным номером, идентифицирующим отрезок. Список сортируется по координатам, и матрица обновляется в соответствующем порядке. Несложно убедиться, что указанный алгоритм будет обеспечивать достаточно высокую производительность, если конфигурация ограничивающих параллелепипедов не меняется значительно за одну итерацию.
В случае деформируемых тел, например просчёта физической модели ткани, нет возможности использовать более специфичный метод — алгоритм парного исключения, описанный ниже, и лучшим методом становятся алгоритмы, использующие подход «n-body pruning».
Если на скорость физических тел сцены может быть наложено ограничение максимального значения, тогда пары объектов могут удаляться из списка кандидатов на столкновения, исходя из их начальной дистанции друг от друга и размера шага временной итерации .
Попарное сокращение После того, как пара объектов сцены выбрана для дальнейшего изучения, требуется более детальная проверка на наличие факта столкновения. Во многих приложениях некоторые из объектов (если их геометрическая конфигурация относительно постоянна, то есть они не подлежат сильной деформации) описываются набором малоразмерных примитивов, в основном треугольников. То есть имеется два множества треугольников и (для простоты предполагается, что мощность множеств равна).
Очевидным методом проверки тел на столкновение является проверка всех упорядоченных пар треугольников на столкновение. Однако сложность такой проверки составляет , что крайне неэффективно. Возникает необходимость по возможности воспользоваться «отбрасывающим» алгоритмом для сокращения числа пар треугольников, нуждающихся в проверке.
Наиболее широко применяемым семейством алгоритмов является метод иерархических ограничивающих объёмов. В качестве предварительного шага для каждого объекта (в нашем примере это и ) вычисляется и ставится в соответствие иерархия ограничивающих объектов. После чего на каждой временно́й итерации, когда требуется проверить наличие столкновения между объектами и , ограничивающие объёмы используются для сокращения количества треугольников, попадающих под проверку. Одним из самых простых видов ограничивающего объёма является сфера.