Collision detection (определение столкновений).

Автор: IvanVR1

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

Постановка задачи и подходы к решению
Проверка пересечения геометрических примитивов

Постановка задачи и подходы к решению

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

Рассмотрим некоторые задачи, возникающие при программировании игр.

Задача 1. Определить, случится ли столкновение ракеты с самолетом. Перемещение ракеты за время dt представим направленным отрезком R_begin R_end. Перемещение самолета представим капсулой (геометрической фигурой, образованной цилиндром и двумя полусферами). Радиус капсулы равен радиусу описывающей самолет сферы, а длина и положение цилиндра соответствуют начальному и конечному положению самолета P_begin P_end. Для решения этой задачи нужна функция, которая проверяет пересечение направленного отрезка с капсулой.

Задача 2. Определить попадет ли пуля в человека. Для этой задачи требуется высокая точность решения, поэтому тело надо аппроксимировать набором геометрических фигур: цилиндров, сфер, "боксов". А движение пули - направленным отрезком R_begin R_end. Если есть функции, проверяющие пересечение направленного отрезка с цилиндром, сферой и "боксом", задача вполне решаема.

Задача 3. Определить столкновение автомобилей, движущихся на высокой скорости. Подход с двумя капсулами, в данном случае, не дает необходимой точности. Уменьшение dt приведет к дополнительным вычислительным затратам. Аппроксимируем каждую машину "боксом". Элементарное перемещение машин за время dt назовем DP₀ и DP₁, элементарные скорости будут V₀= DP₀/dt и V₁= DP₁/dt. Надо иметь функцию, определяющую время первого касания двух "боксов", движущихся со скоростями V₀ и V₁.

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

Очень часто изложенные выше задачи усложняются большим количеством объектов, с которыми надо проверять пересечение. Здесь применяют различные способы поиска ближайших объектов, использующие BSP tree, quad tree, 2D решетки.

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

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

Проверка пересечения геометрических примитивов

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

Каждую фигуру удобно представить классом, например:

class BOX
{
public:
   class POINT3D Origin, Extents;
//:
};

class SPHERE
{
public:
  class POINT3D Center;
  float Radius;
// :
};

А функции проверки желательно оформить так, чтобы они отличались только типом принимаемых параметров (это неоценимое подспорье при использовании шаблонов), например:

bool TestIntersection( const class BOX& Box, const class SPHERE& Sphere );
bool TestIntersection( const class SPHERE& Sphere, const class FRUSTUM& Frustum );
bool TestIntersection( const class BOX& Box0, const class BOX& Box1 );
bool TestIntersection( const class RAY& Ray, const class SPHERE& Sphere );

Для проверки пересечения луча с другими фигурами сделаем дополнительную группу функций следующего вида:

bool TestIntersection( const class RAY& Ray, const class BOX& Box, 
                       class POINT3D& Position, class POINT3D& Normal );
bool TestIntersection( const class RAY& Ray, const class SPHERE& Sphere, 
                       class POINT3D& Position, class POINT3D& Normal );

Параметры Position и Normal нужны для получения точки касания и нормали к поверхности.

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

Рекомендуемая литература и ссылки:
David H. Eberly. 3D Game Engine Design. — замечательная книжка одного из основоположников известного движка NetImmerse, поставляется вместе с CD.
http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter0.htm
http://www.realtimerendering.com/intersections.html

#collision detection

21 июня 2002 (Обновление: 24 сен 2009)

Комментарии [6]