Обнаружение столкновений (KQugjr'yuny vmkltukfyunw)

Обнаруже́ние столкнове́ний (англ. Collision detection) — вычислительная проблема обнаружения пересечений между собой двух или более объектов. Тема чаще всего связана с её использованием в физических движках, компьютерной анимации и робототехнике. В дополнение к определению, столкнулись ли два объекта, системы обнаружения столкновений могут вычислить время воздействия и сообщить о коллекторе контакта (набор пересечения точек)^[1]. Реакция на столкновение (что происходит, когда столкновение обнаружено) зависит от конкретного моделируемого процесса. В алгоритмах обнаружения столкновений широко применяются понятия из линейной алгебры и вычислительной геометрии. Алгоритмы обнаружения столкновений являются одной из основных составляющих физики трёхмерных компьютерных игр.

Обзор

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

Компьютерные игры предъявляют к физическим движкам примерно те же требования, за исключением некоторых существенных отличий. В то время как моделирование физических опытов требует создания максимально точного математического аппарата, описывающего реальный мир, компьютерные игры нуждаются в физике лишь правдоподобно выглядящей, но при этом вычисляемой в режиме реального времени, пусть и грубо. Компромиссы допускаются, пока это устраивает игрока и имеет приемлемый визуальный реализм. Поэтому тело, которое проверяется на столкновение, — так называемый хитбокс или коллайдер — проще, чем трёхмерная модель персонажа.

Обнаружение столкновений в физических симуляциях

Физические движки отличаются способами, которыми они реагируют на столкновения. Некоторые используют гибкость материалов для вычисления силы, возникающей в результате столкновения и влияющей на результат столкновения в последующие временные интервалы, что достаточно затратно с точки зрения вычислительных ресурсов. Некоторые модели вычисляют аппроксимированное время столкновения с помощью линейной интерполяции, после чего «откатывают» состояние сцены на некоторый момент времени и просчитывают столкновение на основе законов сохранения энергии.

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

После неупругого столкновения возможно возникновение особых состояний скольжения или покоя, которые, например, в свободном физическом движке Open Dynamics Engine эмулируются с помощью ограничений. Ограничения исключают инерцию и, как следствие, нестабильность. Реализация покоя в понятиях графа сцены позволяет избежать смещений.

Другими словами, реализации физических моделей обычно делятся на два пути:

определение столкновения апостериори,
априорный подход (обнаружение до происхождения столкновения).

В дополнение к делению на апостериорные и априорные подходы практически все современные алгоритмы обнаружения столкновений делятся на иерархию алгоритмов.

Различия апостериорного и априорного подходов

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

При априорном подходе создаётся алгоритм обнаружения столкновений, способный предсказывать траекторию движений физических тел с высокой точностью. Случаи столкновений описываются этой моделью с высокой точностью, и физические тела в сущности никогда не оказываются в состоянии взаимного проникновения. Этот подход называется априорным, поскольку моменты столкновений тел определяются до изменения пространственной конфигурации объектов сцены.

Из апостериорного подхода проистекают его основные достоинства. Алгоритму не нужно манипулировать значительным количеством физических переменных — его исходными данными является простой список физических тел, результатом является подмножество тел пересекающихся. Алгоритму не приходится иметь дело с учётом сил трения, упругих или — ещё хуже — неупругих столкновений, а также просчитывать изменение внутреннего состояния деформируемых тел. Кроме того, апостериорный алгоритм по сути проще на одно измерение, так как в априорном подходе приходится иметь дело с дополнительной осью — временем, от чего избавлен подход апостериорный.

С другой стороны, апостериорные алгоритмы приводят к проблемам на этапе «исправления» произошедших взаимопроникновений тел, которые не происходят в реальной физической сцене.

Преимуществами априорного подхода являются точность и стабильность модели. Сложно (но теоретически возможно) полностью отделить физическую составляющую модели сцены от алгоритма обнаружения столкновений. В большинстве случаев, кроме самых простых, проблема предсказания момента времени столкновения двух тел по некоторым исходным данным не имеет общего абстрагированного от остальной модели решения. Применяется численный метод поиска корня.

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

Оптимизация

Очевидные подходы к обнаружению столкновений для всей сцены со множеством объектов весьма медлительны. Проверка на факт столкновения каждого объекта с каждым работоспособна, но крайне неэффективна с точки зрения вычислительной трудоёмкости для большого количества объектов. Проверка объектов со сложной геометрией на предмет наличия столкновения между собой очевидным методом проверки столкновения отдельных граней тел весьма затратна сама по себе. Таким образом, значительное число исследований в области направлено на решение проблем производительности.

Применение временно́й когерентности

Во многих приложениях конфигурация физических тел меняется на протяжении итерационного отрезка времени весьма незначительно. Многие объекты сцены не двигаются вообще. Алгоритмы создаются таким образом, что результаты вычислений, сделанные на предыдущей итерации, используются на следующей, что приводит к повышению производительности.

На уровне грубого определения столкновений целью является нахождение объектов, которые потенциально могут пересекаться. Эти пары потребуют дальнейшего анализа. Один из таких алгоритмов был разработан Минг Чье Лин (англ. Ming Chieh Lin) из Калифорнийского университета в Беркли^[2], предложившей применение метода ограничивающих параллелепипедов, направляющие вектора ребер которых коллинеарны векторам базиса декартовой системы координат, для всех N тел сцены. Позже эти ограничивающие параллелепипеды стали известны как Axis-aligned bounding box (AABB).

Каждый параллелепипед представляется тройкой отрезков, например $I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]$ . Распространённым алгоритмом для обнаружения столкновений ограничивающих параллелепипедов является алгоритм «Sweep and prune» (рус. охватить и отбросить; рус. охватить и обрезать)^[3]. Очевидно, что два таких параллелепипеда $I_{1}\times I_{2}\times I_{3}$ и $J_{1}\times J_{2}\times J_{3}$ пересекаются тогда и только тогда, когда $I_{1}$ пересекается с $J_{1}$ , $I_{2}$ пересекается с $J_{2}$ и $I_{3}$ пересекается с $J_{3}$ . Предполагается, что если от одной временной итерации до следующей $I_{k}$ и $J_{k}$ пересекаются, то весьма вероятно, что они будут по-прежнему пересекаться и на следующей итерации. Также, если они не пересекались на предыдущей итерации, весьма вероятно, что не будут пересекаться и на следующей.

Итак, проблема сводится к итерационному контролю от «кадра» к «кадру» за тем, которые из отрезков пересекаются. Имеются три списка интервалов (по одному на каждую из осей координат), и все три одинаковой длины, так как длина каждого равна $n$ , по числу объектов сцены и, соответственно, их ограничивающих параллелепипедов. Каждому из списков соответствует матрица $M_{n\times n}$ , элементы $m_{ij}$ которой равны 1 или 0. $m_{ij}=1$ — в случае, если отрезки $i$ и $j$ пересекаются, и $m_{ij}=0$ , если нет.

Допустим, матрица $M_{n\times n}$ остаётся практически неизменной от одной итерации к следующей. Чтобы это использовать, список отрезков содержится в виде помеченных крайних точек. Каждый элемент списка располагает координатами крайней точки и уникальным номером, идентифицирующим отрезок. Список сортируется по координатам, и матрица обновляется в соответствующем порядке. Несложно убедиться, что указанный алгоритм будет обеспечивать достаточно высокую производительность, если конфигурация ограничивающих параллелепипедов не меняется значительно за одну итерацию.

В случае деформируемых тел, например просчёта физической модели ткани, нет возможности использовать более специфичный метод — алгоритм парного исключения, описанный ниже, и лучшим методом становятся алгоритмы, использующие подход «n-body pruning».

Если на скорость физических тел сцены может быть наложено ограничение максимального значения, тогда пары объектов могут удаляться из списка кандидатов на столкновения, исходя из их начальной дистанции друг от друга и размера шага временной итерации $\Delta t$ .

Попарное сокращение

После того, как пара объектов сцены выбрана для дальнейшего изучения, требуется более детальная проверка на наличие факта столкновения. Во многих приложениях некоторые из объектов (если их геометрическая конфигурация относительно постоянна, то есть они не подлежат сильной деформации) описываются набором малоразмерных примитивов, в основном треугольников. То есть имеется два множества треугольников $S={S_{1},S_{2},\dots ,S_{n}}$ и $T={T_{1},T_{2},\dots ,T_{n}}$ (для простоты предполагается, что мощность множеств равна).

Очевидным методом проверки тел на столкновение является проверка всех упорядоченных пар $(S_{j},T_{k})$ треугольников на столкновение. Однако сложность такой проверки составляет $\operatorname {O} (n^{2})$ , что крайне неэффективно. Возникает необходимость по возможности воспользоваться «отбрасывающим» алгоритмом для сокращения числа пар треугольников, нуждающихся в проверке.

Наиболее широко применяемым семейством алгоритмов является метод иерархических ограничивающих объёмов. В качестве предварительного шага для каждого объекта (в нашем примере это $S$ и $T$ ) вычисляется и ставится в соответствие иерархия ограничивающих объектов. После чего на каждой временно́й итерации, когда требуется проверить наличие столкновения между объектами $S$ и $T$ , ограничивающие объёмы используются для сокращения количества треугольников, попадающих под проверку. Одним из самых простых видов ограничивающего объёма является сфера.

Для множества треугольников $E$ можно вычислить ограничивающую сферу $B(E)$ . Существует несколько способов выбора $B(E)$ , принципиально лишь, что сфера $B(E)$ полностью охватывает множество треугольных примитивов $B(E)$ и одновременно мала настолько, насколько это возможно.

При определении наличия столкновения тел $S$ и $T$ возможно в первую очередь вычислить сферы $B(S)$ и $B(T)$ . Очевидно, что если эти сферы не пересечены, то не пересечены и $S$ и $T$ . Однако это ненамного более эффективно, нежели алгоритм «n-body pruning».

Пусть $E={E_{1},E_{2},\dots ,E_{m}}$ — множество треугольников. Тогда его можно разбить на две части: $L(E):={E_{1},E_{2},\dots ,E_{m/2}}$ и $R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}$ . Подобным образом можно разбить $S$ и $T$ и предварительно вычислить ограничивающие сферы $B(L(S)),B(R(S))$ и $B(L(T)),B(R(T))$ .

Расчёт на то, что эти ограничивающие сферы значительно меньше, нежели $B(S)$ и $B(T)$ . И, если, к примеру, $B(S)$ и $B(L(T))$ не пересекаются, то не имеют смысла проверки пересечений треугольников множества $S$ с треугольниками из $L(T)$ .

В ходе предварительных вычислений можно рассмотреть каждое физическое тело, представленное в виде множества треугольников, и декомпозировать его в виде двоичного дерева, в котором узлами (нодами) $N$ будут множества треугольников, а их потомками — $L(N)$ и $R(N)$ . Для каждого узла этого дерева можно предварительно рассчитать ограничивающую сферу $B(N)$ . В таком случае, когда настанет необходимость проверки столкновения очередной пары тел, их заранее рассчитанные бинарные деревья ограничивающих сфер могут быть использованы для исключения значительной части из подлежащих проверке множеств составляющих их треугольников.

Множество дополнительных реализаций «древовидных» алгоритмов получается при выборе других стереометрических объектов в качестве ограничивающих объёмов, нежели сфер. При выборе параллелепипеда, ориентированного параллельно осям системы измерений (англ. axis-aligned bounding box), получаются так называемые AABB-деревья (англ. AABB-Trees). OBB-деревья (или ОOBB-деревья) получаются при использовании параллелепипеда, ориентированного согласно собственной системе координат объекта. Некоторые из деревьев проще обновлять в случае изменений основного объекта. Некоторые деревья могут работать с примитивами более высокого порядка, такими как сплайны, вместо элементарных треугольников.

Точное попарное обнаружение столкновений

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

Основное наблюдение заключается в том, что для любых двух выпуклых не соприкасающихся между собой объектов существует такая плоскость, что один объект будет лежать полностью по одну сторону этой плоскости, а другой — по другую. Этот факт позволяет разрабатывать быстрые алгоритмы обнаружения столкновений для выпуклых объектов.

Ранние работы в этой области обозначили методы разделяющей плоскости. Два треугольника по существу сталкиваются только тогда, когда не могут быть разделены плоскостью, проходящей через три вершины. Это так, если треугольники ${v_{1},v_{2},v_{3}}$ и ${v_{4},v_{5},v_{6}}$ , где каждый $v_{j}$ вектор в $\mathbb {R} ^{3}$ , тогда можно выбрать три вершины — $v_{i},v_{j},v_{k}$ , провести плоскость через все три и проверить, является ли плоскость разделяющей. Если любая из таких плоскостей является разделяющей, значит, треугольники не пересекаются; и пересекаются, если, напротив, ни одна из них разделяющей не является. Всего таких плоскостей получается 20.

Если треугольники компланарны, этот тест не будет полностью успешным. Однако можно добавить плоскостей, например, перпендикулярных граням треугольника, чтобы решить задачу в общем случае. В других случаях объекты, которые, например, соприкасаются своими гранями, обязательно так же должны встречаться углами где-либо, а следовательно общий способ обнаружения столкновения должен быть в состоянии разрешить вопрос столкновения.

С тех пор были разработаны лучшие методы. На данный момент доступны очень быстрые алгоритмы на нахождения ближайших точек поверхности двух выпуклых многогранных тел. В 1993 г. М. Ч. Лин в своей диссертации^[4] использовала вариацию симплекс-метода из линейного программирования. В дальнейшем алгоритм Гилберта—Джонсона—Кёрти сменил этот подход. Эти алгоритмы приближаются к постоянному времени вычисления при последовательном применении к парам неподвижных или медленно движущихся тел, когда используются с начальными данными из предыдущей итерации обнаружения столкновений.

Следствием всех этих достижений стала возможность эффективного обнаружения столкновений в реальном времени для тысяч движущихся тел на типовом персональном компьютере или игровой консоли.

Априорное отсечение

В тех случаях, когда бо́льшая часть объектов на сцене является неподвижной, как это часто бывает в компьютерных играх, для ускорения вычислений могут быть использованы априорные методы, использующие предварительные обсчёты.

В данных ситуациях желательно сокращение (отбрасывание): как «n-body pruning», так и попарное сокращение. Однако этим алгоритмам требуется время для вычислений и учёт типов движений, используемых в базовой физической системе.

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

В качестве примера рассмотрим два треугольника, движущихся во времени: ${v_{1}(t),v_{2}(t),v_{3}(t)}$ и ${v_{4}(t),v_{5}(t),v_{6}(t)}$ . В любой момент времени эти два треугольника могут быть проверены на пересечение с использованием двадцати плоскостей, о которых говорилось выше. Тем не менее процесс можно улучшить, так как эти двадцать плоскостей могут быть отслежены во времени. Если $P(u,v,w)$ является плоскостью, которая проходит сквозь точки $u,v,w$ в $\mathbb {R} ^{3}$ , то это значит, что доступны двадцать плоскостей для отслеживания. Каждая плоскость должна быть отслежена по отношению к трём вершинам, это даёт шестьдесят значений для отслеживания. Использование корневого поиска для этих шестидесяти функций вычисляет точное время столкновения для двух заданных треугольников и для двух заданных траекторий. Если траектории вершин считаются линейными полиномами (многочленами) в $t$ , то тогда окончательные шестьдесят функций являются кубическими полиномами, и в этом исключительном случае является возможным найти точное время столкновения, используя формулу для кубических корней. Некоторые специалисты в численном анализе полагают, что использование формулы для кубических корней не является численно столь устойчивым, как использование поиска корней для полиномов.

Пространственное разбиение

Альтернативные алгоритмы можно сгруппировать по факту использования ими пространственного разбиения (англ. Space partitioning), к которому относятся BSP-деревья, октодеревья и другие подобные подходы. Если применяемый алгоритм пространственного разбиения разделяет сцену с объектами на набор областей и если два объекта находятся в разных областях, то они не проверяются на пересечения. Так как BSP-деревья могут быть предварительно обсчитанными, этот подход хорошо подходит для обработки стен и других неподвижных препятствий в играх. Эти алгоритмы разбиения пространства, как правило, старее описанных выше алгоритмов.

Обнаружение столкновений в компьютерных играх

Компьютерные игры, особенно консольные игры, должны распределять многие свои задачи между очень ограниченными аппаратными ресурсами и очень ограниченным временем выполнения игровых процессов. Несмотря на эти ограничения и на использование относительно примитивных и неточных алгоритмов обнаружения столкновений, разработчики игр смогли создать визуально правдоподобные и относительно реалистичные физические подсистемы.

Довольно долгое время в компьютерных играх присутствовало очень ограниченное количество физически взаимодействующих между собой объектов, и поэтому проверка всех объектов на пересечения не была проблемой. В двухмерных играх в некоторых случаях аппаратное обеспечение было способно эффективно выявлять и сообщать о пересекающихся пикселях между спрайтами на экране. В остальных случаях эффективное отбрасывание (сокращение) обеспечивалось путём простого тайлинга (разбиения на фрагменты — тайлы) экрана и привязки каждого спрайта к тайлу, с которым он пересекается. Для проверки попарных пересечений использовались ограничивающие прямоугольники и/или окружности, что считалось достаточно точным.

Трёхмерные игры используют методы пространственного разбиения для «n-body pruning» и долгое время использовали для проверки попарных пересечений одну или несколько ограничивающих сфер для одного трёхмерного объекта. Точные проверки проводились очень редко, за исключением игр, пытающихся относительно точно имитировать реальность. Но даже в этих случаях точные проверки на пересечение проводятся не всегда, а лишь в самых важных с точки зрения игры местах и/или ситуациях.

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

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

Надёжный симулятор обнаружения и решения столкновений — это такой симулятор, который будет реагировать на любые входные данные разумно. Исходя из апостериорного подхода к обнаружению столкновений, можно предположить, что в гоночной игре игрок, разогнавшись на большой скорости на автомобиле, врежется в препятствие типа стены и система обнаружения столкновений обнаружит столкновение уже после того, как оно произошло, а в это время автомобиль уже будет «погружен» в стену или будет даже «падать в бесконечную пустоту», называемую «чёрный ад», «синий ад» либо «зелёный ад», в зависимости от доминантного цвета в графическом движке. Поэтому механизм апостериорного обнаружения столкновений должен корректным образом решать подобные ситуации. Одним из решений подобных ситуаций является концепция «непрерывного обнаружения столкновений» (англ. Continuous Collision Detection).^[5]

Примечания

↑ Ericson, Christer. Real-time Collision Detection. Elsevier, 2005, p. 13.
↑ Минг Чье Лин (англ. Ming Chieh Lin). Lin-Canny Closest Features Algorithm (англ.). Калифорнийский университет в Беркли (31 января 1996). Дата обращения: 29 июля 2011. Архивировано 10 марта 2012 года.
↑ Sweep And Prune (рус.). GameDev.ru (30 августа 2007). — Описание алгоритма с примерами программного кода. Дата обращения: 8 июля 2009. Архивировано 15 октября 2012 года.
↑ Минг Чье Лин (англ. Ming Chieh Lin). Efficient Collision Detection for Animation and Robotics (thesis) (англ.) : journal. — Калифорнийский университет в Беркли, 1993. (недоступная ссылка)
↑ Erwin Coumans. Continuous Collision Detection and Physics (англ.) (PDF). Sony Computer Entertainment (август 2005). Дата обращения: 30 июля 2011. Архивировано из оригинала 10 марта 2012 года.

Ссылки

OZCollide — свободная, быстрая и кроссплатформенная библиотека обнаружения столкновений
Веб-сайт University of North Carolina at Chapel Hill, посвящённый исследованию обнаружения столкновений
Статья на сайте профессора Стивена Кэмерона (англ. Steven Cameron) из Оксфордского университета, посвящённая обнаружениям столкновений
How to Avoid a Collision — статья Джорджа Бека (англ. George Beck), Wolfram Demonstrations Project
IvanVR1. Collision detection (определение столкновений) (неопр.). GameDev.ru (21 июня 2002). Дата обращения: 29 июля 2011.

[1] Ericson, Christer. Real-time Collision Detection. Elsevier, 2005, p. 13.

[2] Минг Чье Лин (англ. Ming Chieh Lin). Lin-Canny Closest Features Algorithm (англ.). Калифорнийский университет в Беркли (31 января 1996). Дата обращения: 29 июля 2011. Архивировано 10 марта 2012 года.

[3] Sweep And Prune (рус.). GameDev.ru (30 августа 2007). — Описание алгоритма с примерами программного кода. Дата обращения: 8 июля 2009. Архивировано 15 октября 2012 года.

[4] Минг Чье Лин (англ. Ming Chieh Lin). Efficient Collision Detection for Animation and Robotics (thesis) (англ.) : journal. — Калифорнийский университет в Беркли, 1993. (недоступная ссылка)

[5] Erwin Coumans. Continuous Collision Detection and Physics (англ.) (PDF). Sony Computer Entertainment (август 2005). Дата обращения: 30 июля 2011. Архивировано из оригинала 10 марта 2012 года.

[1]

[2]

[3]

[4]

[5]