Учебное пособие по физике видеоигр. Часть II: Обнаружение столкновений для твердых объектов

Это вторая часть нашей серии из трех статей о физике видеоигр. Для остальной части этой серии см.:

Часть I: Введение в динамику твердого тела
Часть III: Моделирование жесткого тела с ограничениями

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

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

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

Для обзора концепций линейной алгебры, упомянутых в этой статье, вы можете обратиться к ускоренному курсу линейной алгебры в Части I.

Физика столкновений в видеоиграх

В контексте моделирования твердого тела столкновение происходит, когда формы двух твердых тел пересекаются или когда расстояние между этими формами падает ниже небольшого допуска.

Если у нас есть n тел в нашей симуляции, вычислительная сложность обнаружения столкновений с попарными тестами составляет O ( n 2 ) , число, которое заставляет программистов съеживаться. Количество парных тестов увеличивается квадратично с количеством тел, и определение того, сталкиваются ли две формы в произвольных положениях и ориентациях, уже недешево. Чтобы оптимизировать процесс обнаружения столкновений, мы обычно разделяем его на две фазы: широкая фаза и узкая фаза .

Широкая фаза отвечает за поиск пар твердых тел, которые потенциально могут сталкиваться, и исключение пар, которые заведомо не сталкиваются, из всего набора тел, участвующих в моделировании. Этот шаг должен иметь возможность очень хорошо масштабироваться с количеством твердых тел, чтобы убедиться, что мы остаемся ниже временной сложности O ( n 2 ) . Чтобы достичь этого, на этом этапе обычно используется разделение пространства в сочетании с ограничивающими объемами , которые устанавливают верхнюю границу для столкновения.

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

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

Широкая фаза

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

Некоторыми популярными типами ограничивающих объемов являются ориентированные ограничивающие прямоугольники (OBB), круги в 2D и сферы в 3D. Давайте рассмотрим один из самых простых ограничивающих объемов: ограничивающие рамки, выровненные по осям (AABB) .

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

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

Поле min представляет расположение нижнего левого угла поля, а поле max представляет верхний правый угол.

Чтобы проверить, пересекаются ли две AABB, нам нужно только выяснить, пересекаются ли их проекции на всех осях координат:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Этот код имеет ту же логику, что и функция b2TestOverlap из движка Box2D (версия 2.3.0). Он вычисляет разницу между min и max обоих AABB по обеим осям в обоих порядках. Если какое-либо из этих значений больше нуля, AABB не пересекаются.

Несмотря на то, что тест на перекрытие AABB дешев, он не сильно поможет, если мы все еще будем проводить попарные тесты для каждой возможной пары, поскольку у нас все еще есть нежелательная временная сложность O ( n 2 ) . Чтобы свести к минимуму количество тестов перекрытия AABB, мы можем использовать некое разделение пространства , которое работает по тем же принципам, что и индексы базы данных, ускоряющие запросы. (Географические базы данных, такие как PostGIS, на самом деле используют аналогичные структуры данных и алгоритмы для своих пространственных индексов.) Однако в этом случае AABB будут постоянно перемещаться, поэтому, как правило, мы должны воссоздавать индексы после каждого шага моделирования.

Для этого можно использовать множество алгоритмов разделения пространства и структур данных, таких как равномерные сетки, деревья квадрантов в 2D, октодеревья в 3D и пространственное хэширование. Давайте подробнее рассмотрим два популярных алгоритма пространственного разбиения: сортировку и развертку и иерархию ограничивающих объемов (BVH).

Алгоритм сортировки и очистки

Метод сортировки и развертки (также известный как развертка и обрезка ) является одним из любимых вариантов среди программистов-физиков для использования в моделировании твердого тела. Движок Bullet Physics, например, имеет реализацию этого метода в классе btAxisSweep3 .

Проекция одного AABB на единственную ось координат — это, по существу, интервал [ b , e ] (то есть начало и конец). В нашем моделировании у нас будет много твердых тел и, следовательно, много AABB, а это означает много интервалов. Мы хотим выяснить, какие интервалы пересекаются.

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

В двух и трех измерениях выполнение сортировки и развертки, как описано выше, по одной оси координат уменьшит количество прямых тестов пересечения AABB, которые должны быть выполнены, но выигрыш может быть лучше по одной оси координат, чем по другой. Поэтому реализованы более сложные варианты алгоритма сортировки и развертки. В своей книге «Обнаружение столкновений в реальном времени» (стр. 336) Кристер Эриксон представляет эффективный вариант, в котором он хранит все AABB в одном массиве, и для каждого запуска сортировки и развертки выбирается одна координатная ось, а массив сортируется по min значение AABB на выбранной оси с использованием быстрой сортировки. Затем выполняется обход массива и выполняются тесты перекрытия AABB. Чтобы определить следующую ось, которую следует использовать для сортировки, вычисляется дисперсия центра AABB, и для следующего шага выбирается ось с большей дисперсией.

Динамические деревья ограничивающих объемов

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

Dbvt — это бинарное дерево, в котором каждый узел имеет AABB, ограничивающий все AABB его дочерних элементов. Сами ААББ твердых тел расположены в листовых узлах. Как правило, Dbvt «запрашивается», предоставляя AABB, для которого мы хотели бы обнаружить пересечения. Эта операция эффективна, потому что потомки узлов, которые не пересекаются с запрашиваемым AABB, не нужно проверять на перекрытие. Таким образом, запрос коллизии AABB начинается с корня и рекурсивно продолжается по дереву только для узлов AABB, которые пересекаются с запрошенным AABB. Дерево можно сбалансировать с помощью вращения дерева, как в дереве AVL.

Box2D имеет сложную реализацию Dbvt в классе b2DynamicTree . Класс b2BroadPhase отвечает за выполнение широкой фазы и использует экземпляр b2DynamicTree для выполнения запросов AABB.

Узкая фаза

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

Выпуклые и вогнутые формы

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

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

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

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

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

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

Алгоритмы выпуклой декомпозиции получают вогнутую форму и возвращают набор выпуклых форм, объединение которых идентично исходной вогнутой форме. Некоторые вогнутые формы могут быть представлены только большим количеством выпуклых фигур, и их вычисление и использование могут стать чрезмерно дорогостоящими. Однако аппроксимация часто бывает достаточно хорошей, поэтому такие алгоритмы, как V-HACD , ​​создают небольшой набор выпуклых многогранников из вогнутого многогранника.

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

Тестирование пересечений — Теорема о разделяющей оси

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

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

Механизмы игровой физики имеют несколько различных классов форм, таких как круги (сферы в 3D), ребра (один сегмент линии) и выпуклые многоугольники (многогранники в 3D). Для каждой пары типов фигур у них есть определенный алгоритм обнаружения столкновений. Самый простой из них, наверное, алгоритм круг-круг:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

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

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

Если какой-либо тест проходит, то есть если для любого ребра все вершины другого многоугольника находятся перед ним, то многоугольники не пересекаются. Линейная алгебра дает простую формулу для этого теста: если дано ребро первой фигуры с вершинами a и b и вершина v другой фигуры, если ( v - a ) · n больше нуля, то вершина находится впереди края.

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

Box2D использует SAT для проверки пересечения двух выпуклых многоугольников в своем алгоритме обнаружения столкновений между многоугольниками в b2CollidePolygon.cpp.

Вычисление расстояния — алгоритм Гилберта-Джонсона-Кирти

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

Функции поддержки

Опорная функция s A ( d ) возвращает точку на границе формы A , которая имеет самую высокую проекцию на вектор d . Математически он имеет самое высокое скалярное произведение с d . Это называется опорной точкой , и эта операция также известна как опорное отображение . Геометрически эта точка является самой дальней точкой формы в направлении d .

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

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Однако реальная сила опорной функции заключается в том, что она позволяет легко работать с такими формами, как конусы, цилиндры и эллипсы, среди прочих. Довольно сложно вычислить расстояние между такими фигурами напрямую, и без алгоритма, такого как GJK, вам обычно приходилось бы дискретизировать их в многоугольник или многогранник, чтобы упростить задачу. Однако это может привести к дополнительным проблемам, поскольку поверхность многогранника не такая гладкая, как поверхность, скажем, сферы, если только многогранник не очень детализирован, что может привести к снижению производительности при обнаружении столкновений. Также могут проявиться другие нежелательные побочные эффекты; например, «многогранная» сфера не может катиться плавно.

Чтобы получить опорную точку для сферы с центром в начале координат, нам просто нужно нормализовать d (то есть вычислить d / || d || , который является вектором длины 1 (единичная длина), который по-прежнему указывает в том же направлении d ), а затем умножаем на радиус сферы.

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

Наши объекты, конечно же, будут смещены и повернуты относительно начала координат в пространстве симуляции, поэтому нам необходимо вычислить опорные точки для преобразованной формы. Мы используем аффинное преобразование T ( x ) = Rx + c для смещения и вращения наших объектов, где c — вектор смещения, а R — матрица вращения . Это преобразование сначала поворачивает объект вокруг начала координат, а затем перемещает его. Опорная функция для преобразованной формы A :

Суммы Минковского

Сумма Минковского двух форм A и B определяется как:

Это означает, что мы вычисляем сумму для всех точек, содержащихся в A и B . Результат похож на раздувание A с помощью B .

Точно так же мы определяем разность Минковского как:

которую мы также можем записать как сумму Минковского A с -B :

Для выпуклых A и B ⊕B также выпукло.

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

Еще одна приятная особенность разности Минковского заключается в том, что если она не содержит начало координат, минимальное расстояние между началом координат и разностью Минковского равно расстоянию между фигурами.

Расстояние между двумя фигурами определяется как:

Другими словами, расстояние между A и B — это длина кратчайшего вектора, идущего из A в B. Этот вектор содержится в A⊖B и является вектором наименьшей длины, который, следовательно, является ближайшим к началу координат.

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

Симплексы

Алгоритм GJK итеративно ищет точку на разности Минковского, ближайшую к началу координат. Это достигается путем построения серии симплексов , которые ближе к началу координат на каждой итерации. Симплекс — или, точнее, k-симплекс для целого числа k — это выпуклая оболочка k + 1 аффинно независимых точек в k-мерном пространстве. То есть если у двух точек они не должны совпадать, то у трех точек они дополнительно не должны лежать на одной прямой, а если у нас четыре точки, то они тоже не должны лежать в одной плоскости. Следовательно, 0-симплекс — это точка, 1-симплекс — это отрезок, 2-симплекс — это треугольник, а 3-симплекс — это тетраэдр. Если мы удаляем точку из симплекса, мы уменьшаем его размерность на единицу, а если мы добавляем точку в симплекс, мы увеличиваем его размерность на единицу.

ГЖК в действии

Давайте соберем все это вместе, чтобы увидеть, как работает GJK. Чтобы определить расстояние между двумя фигурами A и B , мы начнем с их разности Минковского A⊖B . Мы ищем ближайшую точку к началу координат на получившейся фигуре, так как расстояние до этой точки равно расстоянию между двумя исходными фигурами. Мы выбираем некоторую точку v в A ⊖ B , которая будет нашей аппроксимацией расстояния. Мы также определяем пустое множество точек W , которое будет содержать точки текущего тестового симплекса.

Затем входим в петлю. Начнем с получения опорной точки w = s A⊖B (- v ) , точки на A⊖B , проекция которой на v является ближайшей к началу координат.

Если || ш || не сильно отличается от || в || и угол между ними не сильно изменился (согласно некоторым предопределенным допускам), значит алгоритм сошелся и можно вернуть || в || как расстояние.

В противном случае мы добавляем w к W . Если выпуклая оболочка W (то есть симплекс) содержит начало координат, формы пересекаются, и это также означает, что мы закончили. В противном случае мы находим точку в симплексе, ближайшую к началу координат, а затем устанавливаем v в качестве этого нового ближайшего приближения. Наконец, мы удаляем все точки из W , которые не участвуют в вычислении ближайшей точки. (Например, если у нас есть треугольник, и ближайшая к началу координат точка лежит на одном из его ребер, мы можем удалить из W точку, не являющуюся вершиной этого ребра.) Затем повторяем эти же шаги до тех пор, пока алгоритм сходится.

На следующем изображении показан пример четырех итераций алгоритма GJK. Синий объект представляет разность Минковского A⊖B, а зеленый вектор — это v . Здесь вы можете увидеть, как v оттачивает ближайшую точку к началу координат.

Подробное и подробное объяснение алгоритма GJK см. в статье Джино ван ден Бергена «Быстрая и надежная реализация GJK для обнаружения столкновений выпуклых объектов ». В блоге физического движка dyn4j также есть отличный пост о GJK.

Box2D имеет реализацию алгоритма GJK в b2Distance.cpp, в функции b2Distance . Он использует GJK только во время расчета удара в своем алгоритме непрерывного обнаружения столкновений (тема, которую мы обсудим ниже).

Физический движок Chimpunk использует GJK для обнаружения всех столкновений, и его реализация находится в cpCollision.c, в функции GJK . Если алгоритм GJK сообщает о пересечении, ему все равно необходимо знать точки контакта, а также глубину проникновения. Для этого он использует алгоритм расширяющегося многогранника, который мы рассмотрим далее.

Определение глубины проникновения — алгоритм расширяющегося многогранника

Как указано выше, если формы A и B пересекаются, GJK создаст симплекс W , который содержит начало координат внутри разности Минковского A⊖B . На данном этапе мы знаем только, что фигуры пересекаются, но при проектировании многих систем обнаружения столкновений желательно иметь возможность вычислять, сколько у нас пересечений и какие точки мы можем использовать в качестве точек соприкосновения, чтобы мы обрабатываем столкновение реалистично. Алгоритм расширяющегося многогранника (EPA) позволяет нам получить эту информацию, начиная с того места, где остановился GJK: с симплекса, содержащего начало координат.

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

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

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

Используя GJK в сочетании с EPA, мы получаем подробное описание столкновения, независимо от того, пересекаются ли объекты уже или достаточно близко, чтобы считаться столкновением.

Алгоритм EPA описан в статье Proximity Queries and Penetration Depth Computation on 3D Game Objects , также написанной Джино ван ден Бергеном. В блоге dyn4j также есть сообщение об EPA.

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

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

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

Момент удара (или время контакта) t c — это момент времени, когда расстояние между двумя телами равно нулю. Если мы можем написать функцию для расстояния между двумя телами во времени, мы хотим найти наименьший корень этой функции. Таким образом, время вычисления удара является проблемой нахождения корня .

Для времени расчета удара рассматривается состояние (положение и ориентация) тела на предыдущем шаге в момент времени t i -1 и на текущем шаге в момент времени t i . Чтобы упростить задачу, мы предполагаем линейное движение между шагами.

Давайте упростим задачу, предположив, что фигурами являются круги. Для двух окружностей C 1 и C 2 с радиусами r 1 и r 2 , где их центры масс x 1 и x 2 совпадают с их центроидами (т. е. они естественным образом вращаются вокруг своего центра масс), мы можем написать функцию расстояния так как:

Рассматривая линейное движение между шагами, мы можем написать следующую функцию для положения C 1 от t i -1 до t i

Это линейная интерполяция от x 1 ( t i -1 ) до x 1 ( t i ) . То же самое можно сделать для x 2 . Для этого интервала мы можем написать другую функцию расстояния:

Приравняв это выражение к нулю, вы получите квадратное уравнение относительно t . Корни можно найти непосредственно по квадратичной формуле. Если окружности не пересекаются, квадратичная формула не будет иметь решения. Если они это сделают, это может привести к одному или двум корням. Если он имеет только один корень, это значение является временем воздействия. Если у него два корня, то наименьший из них — это время удара, а другой — время, когда окружности расходятся. Обратите внимание, что время удара здесь представляет собой число от 0 до 1. Это не время в секундах; это просто число, которое мы можем использовать для интерполяции состояния тел до точного места, где произошло столкновение.

Непрерывное обнаружение столкновений для некругов

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

Консервативный алгоритм продвижения перемещает тела вперед (и поворачивает их) итеративно. На каждой итерации вычисляется верхняя граница смещения. Оригинальный алгоритм представлен в докторской диссертации Брайана Миртича (раздел 2.3.2), в которой рассматривается баллистическое движение тел. В этой статье Эрвина Куманса (автора Bullet Physics Engine) представлена ​​более простая версия, в которой используются постоянные линейные и угловые скорости.

Алгоритм вычисляет ближайшие точки между фигурами A и B , рисует вектор от одной точки к другой и проецирует скорость на этот вектор, чтобы вычислить верхнюю границу движения. Это гарантирует, что ни одна точка тела не выйдет за пределы этой проекции. Затем он продвигает тела вперед на эту величину и повторяется до тех пор, пока расстояние не упадет ниже небольшого значения допуска.

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

Разрешение конфликтов

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

использованная литература

Если вы хотите получить более глубокое представление о физике столкновений, например, об алгоритмах и методах обнаружения столкновений, книга Кристера Эриксона «Обнаружение столкновений в реальном времени » является обязательной.

Поскольку обнаружение столкновений в значительной степени зависит от геометрии, статья Toptal « Вычислительная геометрия в Python: от теории к применению» является отличным введением в эту тему.