МЕТОДЫ СТОЛКНОВЕНИЯ С ПОЛИГОНАЛЬНОЙ СЕТКОЙ

Введение

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

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

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

Для достижения цели необходимо решить следующие задачи:

• Изучить существующие методы столкновений;
• Изучить структуру игрового движка Unity 3D и реализацию столкновений в нем;
• Реализовать один из изученных методов столкновения, который мог бы устранить недостатки метода в Unity;
• Создать плагин для возможности использования его в других проектах.

В статье рассмотрены основные существующие методы и подробно описаны методы, использующиеся в Unity, и методы, реализованные в работе.

1.Изученные методы

Рассмотрим все основные методы столкновений. В широкой фазе обнаружения можно использовать алгоритм грубой силы, Spatial Hashing или Sweep-and-Prune. Во всех перечисленных алгоритмах объекты представляются в виде ограничивающих параллелепипедов со сторонами, параллельными осям координат (англ. Axis-Aligned Bonding Boxes – AABB). Алгоритм грубой силы производит проверку на пересечение каждого AABB с каждым. В алгоритме Spatial Hashing пространство разбивается на ячейки и определяется, в каких ячейках располагаются объекты. Алгоритм Spatial Hashing эффективен для объектов с одинаковым размером, то есть, например,  для системы частиц. Алгоритм Sweep-and-Prune – это метод сортировки AABB по координатам. Сортировка позволяет не рассматривать далеко расположенные друг от друга объекты.

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

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

В алгоритмах Гилберта-Джонсона-Керти (GJK) и расширенных политопов (EPA) используется понятие опорной функции (Support mapping). Опорная функция позволяет найти экстремальную точку объекта в направлении некоторого вектора p. Для многогранников экстремальной точкой будет вершина, для которой скалярное произведение координат этой точки на координаты вектора p будет максимально.

Алгоритмы V-Clip и Lin-Canny используют понятие областей Вороного. Пространство вокруг фигур разбивается на области, точки в каждой такой области располагаются наиболее близко к какой-либо одной вершине, одному ребру или одной грани фигуры.

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

2.Реализация столкновений в движке Unity 3D

В Unity используется физический движок PhysX, поэтому и методы столкновения в нем используются те же, что и в PhysX. В широкой фазе обнаружения это метод Sweep-and-Prune [2].

Итак, в широкой фазе объекты представляются в виде AABB. Удобно представлять AABB в виде минимальной и максимальной точек с координатами (minX; minY; minZ) и (maxX; maxY; maxZ) соответственно. В алгоритме Sweep-and-Prune производится сортировка объектов по положению минимальной точки по одной из осей (x, y или z). После сортировки достаточно проверить условие minX_j ≤ maxX_i для всех объектов j, расположенных в отсортированном списке позже i. Причем, как только встречается первый объект, не удовлетворяющий этому условию, для остальных объектов это условие можно не проверять.

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

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

В фазе разрешения столкновения используется метод расчета импульсов. В этом методе по формуле (1) вычисляются скорости точки контакта объектов.

                                            ,                                               (1)

где v_p – скорость точки контакта, v – линейная скорость тела, p – точка контакта, c_m – положение центра масс объекта, ω – угловая скорость объекта.

Далее в методе вычисляются импульсы λ, необходимые для того, чтобы проекции скоростей на ось проникновения равнялись нулю – это будет импульс для неупругого удара. В случае упругого удара импульс будет равен (1+bounce)*λ, где bounce – коэффициент упругости.

3.Алгоритмы GJK и EPA

В работе был сделан упор на недостаток метода Unity в узкой фазе обнаружения столкновения – плохая работа на сложных полигональных сетках. Поэтому были изучены и реализованы алгоритмы Гилберта-Джонсона-Кёрти (GJK) [3, c. 401] и расширенных политопов (EPA) [4].

Оба алгоритма работают с конфигурационным пространством препятствий (англ. Configuration Space Obstacle – CSO) двух объектов A и B – суммой Минковского, то есть суммой всех возможных векторов, объектов A и (–B). Основное свойство CSO заключается в том, что если оно содержит начало координат, то объекты A и B пересекаются. Пример CSO для двух объектов представлен на рисунке 1.

Рисунок 1. Конфигурационное пространство препятствий.

Итак, в алгоритме GJK берется произвольный симплекс CSO и определяется, содержит ли он начало координат. Если содержит, то пересечение найдено и алгоритма завершает работу. Если нет, то вычисляется экстремальная точка (с помощью support mapping) CSO в направлении –p, где p – точка CSO, ближайшая к началу координат. Вычисленная точка добавляется в симплекс, а дальняя от начала координат точка из него удаляется. Если вновь добавленная точка уже присутствовала в симплексе, то пересечения нет, и алгоритм завершает работу. Если все точки симплекса различны, то вновь осуществляется проверка на содержание симплексом начала координат. Пример работы алгоритма GJK в двумерном случае представлен на рисунках 2 и 3.

Алгоритм EPA используется для вычисления вектора проникновения объектов после обнаружения факта пересечения объектов в алгоритме GJK. Инициализируется он конечным симплексом алгоритма GJK. Далее определяется ближайшая плоскость симплекса к началу координат, и в направлении нормали этой плоскости в сторону удаления от начала координат вычисляется экстремальная точка и добавляется к симплексу. В итоге получен политоп, содержащий на одну вершину больше. Если вновь добавленная вершина уже содержится в итоговом политопе, то вектор проникновения объектов – это нормаль к плоскости, а глубина проникновения – расстояние от этой плоскости до начала координат. Далее полученные данные используются в фазе разрешения столкновения.

Выводы

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

Список литературы:

1. Собинов Д.И. Алгоритмы обнаружения столкновений // Математические структуры и моделирование. 2010, вып. 21. С. 82-95.
2. Tracy D. Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal // Proceedings of the 2009 IEEE Virtual Reality Conference. 2009. P. 191-198.
3. Ericson C. Real-time Collision Detection. San Francisco: Morgan Kaufmann Publishers, 2005. 593 p.
4. van den Bergen G. Proximity Queries and Penetration Depth Computation on 3D Game Objects // Game Developers Conference. 2001. P. 821-837.