Game Engine своими руками #8: Коллизии

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

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

Сфера - Сфера

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

Расстояние между двумя точками находится по школьной формуле:

Сфера - Плоскость

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

где (x0, y0, z0) - координаты точки (центра сферы), а A, B, C, D - коэффициенты уравнения плоскости.

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

Ax + By + Cz + D = 0;

где (A, B, C) - это координаты нормали (вектора перпендикулярного плоскости), ну а коэффициент D определяется подстановкой в это уравнение координат любой точки принадлежащей плоскости, т.е.

D = -(A*x0 + B*y0 + C*z0);

Подставив в первое уравнение, получаем:

A(x - x0) + B(y - y0) + C(z - z0) = 0;

Для упрощения вычислений бывает удобно заранее нормировать уравнение плоскости, т.е. поделить все коэффициенты (A, B, C, D) на длину нормали, т.е. на sqrt(A^2 + B^2 + C^2), тогда расстояние от точки до плоскости превратится в скалярное произведение:

Сфера - Прямая линия

Аналогично двум предыдущим случаям, для определения пересечения прямой и сферы нам нужно найти расстояние от центра сферы до прямой и сравнить его с радиусом сферы.

Зная координаты (x0, y0, z0) точки лежащей на прямой и радиус-вектор (l, m, n) задающий направление прямой, можно записать параметрические уравнения прямой:

x = x0 + lt; y = y0 + mt; z = z0 + nt;

Очевидно, что расстояние от точки M(x*, y*, z*) до прямой есть расстояние от точки М до точки N пересечения прямой и перпендикулярной ей плоскости проведенной через
M. 

Плоскость перпендикулярная прямой и проходящая через точку M задается уравнением:

l(x - x*) + m(y - y*) + n(z - z*) = 0;

Подставив параметрические уравнения прямой в уравнение плоскости, найдем значение параметра t определяющего координаты точки N пересечения прямой и плоскости:

t = (lx* + my* + nz* - (lx0 + my0 + nz0)) / (l*l + m*m + n*n);

Если заранее нормировать вектор (l, m, n), то уравнение примет вид:

t = lx* + my* + nz* - (lx0 + my0 + nz0);

Подставив теперь это значение параметра t в параметрические уравнения прямой, найдем координаты точки N. После чего будет нетрудно найти расстояние между точками M и N.

Сфера - Отрезок прямой

Очевидно, что для определения пересечения сферы и отрезка недостаточно найти расстояние от центра сферы до прямой, которой принадлежит отрезок (см. рис.) нужно еще убедиться, что точка N принадлежит самому отрезку.

Допустим точка A расположена по координатам (x1, y1, x1, а точка B - (x2, y2, z2), тогда чтобы составить уравнение прямой, которой принадлежит наш отрезок AB, найдем координаты направляющего вектора как разность координат точек B и A, тогда получим:

x = x1 + lt; y = y1 + mt; z = z1 + nt;

где l = x2 - x1; m = y2 - y1; n = z2 - z1;

Далее ищем расстояние от центра сферы до этой прямой как показано в предыдущем случае, и если это расстояние будет больше радиуса сферы, то отрезок однозначно не пересекает сферу, иначе нужно убедиться, что точка N лежит между концами отрезка - точками A и B. Для этого можно воспользоваться параметрическими уравнениями прямой линии, в которых параметр t показывает, на каком расстоянии от базовой точки лежит та или иная точка прямой. В нашем случае базовой точкой параметрических уравнений является точка A, поэтому для нее параметр t = 0. Для точки B параметр t = 1, т.к. направляющий вектор определялся разностью B и A. Ну а параметр t для точки N мы находили при поиске самой точки N, и если этот параметр получился больше 0 и меньше 1, то точка N принадлежит отрезку AB и следовательно сфера и отрезок пересекаются.

Отрезок - Плоскость

Это один из самых простых для обнаружения видов коллизий. Допустим у нас есть отрезок MN заданный двумя точками: M(x1, y1, z1) и N(x2, y2, z2) и плоскость заданная точкой (x0, y0, z0) и единичной нормалью (l, m, n), нужно охарактеризовать их взаимное расположение.

Уравнение плоскости запишется в виде:

l(x - x0) + m(y - y0) + n(z - z0) = 0;

lx + my + nz = lx0 + my0 + nz0

Найдем расстояние от каждого из концов отрезка до плоскости, по вышеописанной формуле, опустив знак модуля, получим для расстояние от M до плоскости:

dist1 = l*x1 + m*y1 + n*z1 - lx0 - my0 - nz0;

Расстояние от N до плоскости:

dist2 = l*x2 + m*y2 + n*z2 - lx0 - my0 - nz0;

Мы не стали учитывать знак модуля по следующим соображениям. Если принять, что направление нормали плоскости определяет внешнюю сторону плоскости, то знак этих выражений позволяет сказать по какую сторону от плоскости лежит точка. Например, если dist1 больше 0, то точка M лежит перед плоскостью, а если меньше 0, то позади. Таким образом, учитывая все вышесказанное, можно сделать следующий вывод: если знаки выражений dist1 и dist2 равны, то оба конца отрезка лежат по одну сторону от плоскости и следовательно отрезок плоскость не пересекает. Если же знаки различны, т.е. dist1*dist2 < 0, то отрезок пересекает плоскость.

AABB - AABB

Аббревиатура AABB расшифровывается как "Axis-Aligned Bounding Box", что значит "выровненная по осям ограничивающая коробка" (немного коряво, но суть верна). Про би-боксы - "ограничивающие коробки", я уже неоднократно рассказывал. "Выровненный по осям" означает, что би-бокс всегда ориентирован так, что его стороны перпендикулярны координатным осям.

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

Пусть у нас имеется два AABB'а (интересно как ты это прочитал :), которые заданы положением своих центров в пространстве и размерами. Чтобы определить пересекаются ли эти AABB'ы или нет, нужно спроецировать их на каждую из координатных осей (X, Y, Z) и проверить пересекаются ли полученные проекции.

vec3_t A; // координаты центра первого AABB'а
vec3_t ASize; // и его размеры

vec3_t B; // координаты центра второго AABB'а
vec3_t BSize; // и его размеры

bool AABBsOverlap (void)
{
int i;

// перебираем все координатные оси
for (i=0 ; i<3 ; i++) {

// если проекции пересекаются, то возращаем FALSE
if (fabs(A[i] - B[i]) > ASize[i]/2 + BSize[i]/2)
return 0;
}

// вроде еще не вышли, значит возвращаем TRUE
return 1;
}

OBB - OBB

Более общим случаем является пересечение ориентированных би-боксов - OBB'ов (Oriented Bounding Box). Этот тест, на мой взгляд, самый полезный, т.к. позволяет определить пересечение трехмерных моделей, а точнее их би-боксов. OBB'ы описываются координатами центра, размерами и ортонормальным базисом, т.е. направлением локальных координатных осей. 

Чтобы определить пересекаются ли OBB'ы или нет, мы должны спроецировать их на некоторую ось и проверить пересекаются ли проекции. Теорема о "разделяющих осях" (Separating Axis Theorem)гласит, что существует только 15 потенциальных разделяющих осей, спроецировав OBB'ы на которые можно однозначно выявить наличие коллизии. Этими осями являются шесть локальных осей (по три для каждого OBB'а) и девять их векторных произведений. Чтобы нам было легче проецировать OOB'ы на оси, преобразуем один из OBB'ов в координатную систему другого с помощью матрицы преобразований (см. листинг)

typedef struct {
vec3_t pos; // координаты центра
vec3_t size; // размеры
vec3_t axis[3]; // локальные оси
} obb_t;

// если до сих пор не вышли, то боксы пересекаются
return 1;
}

Продолжение следует.