Обнаружение столкновений

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

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

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

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

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

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

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

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

Каждый параллелепипед представляется тройкой отрезков, например ${\displaystyle 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]. Очевидно, что два таких параллелепипеда ${\displaystyle I_{1}\times I_{2}\times I_{3}}$ и ${\displaystyle J_{1}\times J_{2}\times J_{3}}$ пересекаются тогда и только тогда, когда ${\displaystyle I_{1}}$ пересекается с ${\displaystyle J_{1}}$, ${\displaystyle I_{2}}$ пересекается с ${\displaystyle J_{2}}$ и ${\displaystyle I_{3}}$ пересекается с ${\displaystyle J_{3}}$. Предполагается, что если от одной временной итерации до следующей ${\displaystyle I_{k}}$ и ${\displaystyle J_{k}}$ пересекаются, то весьма вероятно, что они будут по прежнему пересекаться и на следующей итерации. Также, если они не пересекались на предыдущей итерации, то весьма вероятно, что не будут пересекаться и на следующей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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