Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Статьи / Физика «на пальцах»: Обнаружение столкновений для выпуклых геометрий

Физика «на пальцах»: Обнаружение столкновений для выпуклых геометрий

Автор:

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

Введение
В каких случаях алгоритм применим
Суть алгоритма
Дальнейшие усовершенствования алгоритма
Заключение

Введение

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

В одной из своих статей (Collision Detection для геометрий, заданных SupportMapping'ом) я уже рассказывал о подобном алгоритме для двумерного случая. К сожалению, расширить его на трёхмерный случай вовсе не тривиально, и именно о том, как это сделать, пойдёт речь в данной статье.

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

В каких случаях алгоритм применим

Алгоритм ищет точки контакта только для выпуклых геометрий. На одной из фаз используется support mapping, или, как его ещё называют, механизм геометрий Минковского. О том, что это такое, можно почитать на любом другом ресурсе, либо в вышеозвученной статье про двумерный collision detection. Расширение support mapping'а с 2д на 3д проводится достаточно легко. Алгоритм никак не учитывает движение тел и ищет точки контакта только для квазистатического случая: считается, что тела передвигаются дискретными временными шагами. В остальном серьёзных ограничений нет, алгоритм может строить контактные точки для сфер, эллипсоидов, цилиндров, многогранников и любых других выпуклых геометрий, для которых вам удастся задать support mapping в любых сочетаниях.

Суть алгоритма

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

1) Фаза первая — обнаружение вектора проникновения. Penetration depth или, как его иногда не совсем точно называют, separating axis. Это вектор, в проекции на который геометрии пересекаются на наименьшую величину. Если находится такая ось, в проекции на которую геометрии вообще не пересекаются, то контактные точки не генерируются, алгоритм заканчивает свою работу. Одним из следствий теоремы о разделяющих осях (Separating Axis Theorem, SAT) является то, что для случая контактирующих многогранников этой осью всегда будет либо нормаль одного из фейсов, либо вектороное произведение направляющих пары рёбер, где одно ребро принадлежит одному многограннику, а другое — другому. То есть для случая контактирующих многогранников, если опустить все оптимизации, алгоритм поиска SAT сводится к следующей паре действий:
  a) построить массив потенциальных разделяющих осей, состоящий из всех нормалей фейсов и всех возможных пар рёбер,
  б) посчитать величину пересечения проекций обеих геометрий на каждую из осей. Ось, на которую проекция окажется минимальной, назовём разделяющей (опять же, это не совсем верно, так как геометрии пересекаются), а векторную величину пересечения проекций назовём penetration depth или PD. Заметим, что если первое тело сдвинуть на вектор PD, то пересечение нейтрализуется. К сожалению, физично это сделать невозможно и единственный способ раздвинуть тела — сгенерировать контактные точки и расталкивать тела в каждой контактной точке отдельно, этим будет заниматься солвер.

К концу этой фазы нам известен вектор PD, направление которого на рисунке обозначено красным цветом, назовём его axis. Пусть он будет указывать от первого тела (обозначено зелёным) в сторону второго (обозначено синим):

SAT | Физика «на пальцах»: Обнаружение столкновений для выпуклых геометрий

2) Фаза вторая

В этой фазе мы построим контактирующие площадки каждой из геометрий. Для случая многогранников эти площадки называются частями или фичами (features). Например, для случая контакта ребро-фейс между двумя боксами, контактная фича первого бокса — ребро, контактная фича второго — фейс. Для этого построим семейство дополнительных осей auxAxes[ i ], несколько отклонённых от основной найденной в предыдущей фазе оси. Количество этих осей произвольно, чем больше, тем выше точность алгоритма, но тем медленнее он будет работать. Я обычно использую от четырёх до нескольких десятков. Определим координаты этих осей следующим образом:

for(int i = 0; i < axesCount; i++)
{
  float ang = 2.0f * pi / float(axesCount) * float(i);
  auxAxes[i] = (axis + n0 * cos(ang) * eps + n1 * sin(ang) * eps).Normalize();
}

Здесь n0 и n1 — два вектора, перпендикулярные друг другу и вектору axis. eps — некоторая малая величина, подбираемая экспериментально. Чем она больше, тем шире будут контактные площадки для случая контакта гладких геометрий вроде эллипсоидов. Для случая многогранников её можно выбрать сколь угодно малой, отличной от нуля, лишь бы хватило точности вычислений с плавающей точкой.

Получившиеся векторы (всего их axesCount штук) будут лежать на основании конуса с радиусом eps, высотой axis и с вершиной в начале координат.

Чтобы это представить, посмотрим на рисунок:

axis rotation | Физика «на пальцах»: Обнаружение столкновений для выпуклых геометрий

Красным обозначена исходная ось axis, оранжевым — семейство дополнительных осей auxAxes[ i ]

Теперь возьмём support point'ы первой геометрии в направлениях auxAxes[ i ], а для второй — в направлениях -auxAxes[ i ]. Так как осей много, то для случая многогранников многие точки будут совпадать. Для случая гладких геометрий будем считать совпадающими точки, находящиеся ближе некоторого порога. Таким образом для каждого тела будет найдено множество точек, определяющее контактирующую площадку. На рисунке контактная площадка для первого тела обозначена жирным светло-зелёным, для второго — жирным тёмно-синим:

Contact surfaces | Физика «на пальцах»: Обнаружение столкновений для выпуклых геометрий

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

Алгоритм построения контактных площадок путём отклонения разделяющей оси называется axis rotation.

3) Фаза третья

Спроецируем обе контактные площадки в плоскость, перпендикулярную направлению axis. Получаем два плоских многоугольника. Далее мы должны выделить многоугольник пересечения. Так как площадки выпуклые, вершинами многоугольника пересечения будут вершины первой контактной площадки, лежащие внутри второй, вершины второй контактной площадки, лежащие внутри первой и все точки пересечения их рёбер. На рисунке площадка пересечения обозначена красным:

Clipping | Физика «на пальцах»: Обнаружение столкновений для выпуклых геометрий

Эта операция называется 2d clipping.

4) Фаза четвёртая

Последняя фаза алгоритма особенно сложна для объяснения, так как требует от меня незаурядных изобразительных навыков, которыми я, ясное дело, не обладаю. Тем не менее постараюсь объяснить. В этой фазе мы должны перевести двумерную площадку пересечения, полученную на предыдущей фазе, обратно в три измерения. Вершины этой площадки будут кандидатами на контактные точки. Чтобы это сделать, нужно построить две вспомогательные плоскости: одна плоскость проходит через центр масс первой контактной площадки, вторая — через центр масс второй. Нормаль обеих плоскостей практически* совпадает с направлением penetration depth, или, как я его назвал, axis. Теперь каждую точку пересечения контактных площадок нужно спроецировать в направлении axis со второй плоскости на первую. Рисунок:

3d clipping | Физика «на пальцах»: Обнаружение столкновений для выпуклых геометрий

Синими точками обозначены точки на второй плоскости, зелёными — соответствующие им точки на первой плоскости, серыми стрелками — направления проекции. Чёрный пунктир — линия пересечения плоскости треугольника с плоскостью четырёхугольника(они имеют право пересекаться, так как их нормали могут отличаться на eps).

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

* Практически - потому что точки контактных полигонов, вообще говоря, не всегда лежат строго в одной плоскости, а если и лежат, то её нормаль должна совпадать с axis лишь с выбранной погрешностью eps. Поэтому при проецировании точек одной контактной площадки на другую я бы советовал у каждой контактной площадки найти центр и усреднённую нормаль и проецирование точек вести именно на эти усреднённые плоскости. Если же коллизии ищутся для многогранников вроде боксов, то контактные площадки совпадают с гранями/рёбрами, точки которых и так лежат в одной плоскости и эти действия излишни.

Дальнейшие усовершенствования алгоритма

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

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

Ещё один достаточно важный вопрос, который я опустил — поиск PD для трёхмерных геометрий, заданных support mapping'ом. Детали реализации этого алгоритма я пока раскрывать не готов, но желающие могут самостоятельно попытаться алгоритм, описанный для 2д (ссылки выше), расширить до 3д. Это существенно проще, чем гененрировать контактные точки.

Заключение

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

9 октября 2012

#collision detection, #contact manifold generation, #polyhedra, #SAT, #separating axis theorem


Обновление: 21 декабря 2012

2001—2017 © GameDev.ru — Разработка игр