Код этого урока взят из урока «Коллизия линии и полигона». Теперь вместо проверки пересечения линии мы сделаем лучше — проверку пересечения со сферой. Эта техника отлично подойдет для расчета коллизий камеры в мире. Поскольку коллизия сферы как с плоскостью, так и с полигоном, очень просты, я объясню и то и другое. В этом уроке мы сможем двигать сферу вокруг полигона, и проверять, пересекается ли она с ним. При пересечении сфера будет закрашена зелёным цветом, иначе — фиолетовым.
Мы добавим 4 новых функции и 3 дефайна в нашу математическую «библиотеку».
Файл 3dmath.h:
#define BEHIND 0 // Если сфера позади плоскости
#define INTERSECTS 1 // Если сфера пересекает плоскость
#define FRONT 2 // Если сфера спереди плоскости// И прототипы новых функций:// Возвращает абсолютное значение переданного числа
float Absolute(float num);// Эта ф-я сообщает нам, находится ли сфера спереди, сзади, или пересекает плоскость. Принимаемые
// значения — центр сферы, нормаль плоскости, точку плоскости, радиус сферы и переменную для
// хранения дистанции.
int ClassifySphere(CVector3 &vCenter,CVector3 &vNormal, CVector3 &vPoint, float radius, float &distance);
// Возвращает true, если сфера пересекает ребро переданного треугольника. Принимает центр сферы,
// радиус, вершины полигона и их число. Функция вызывается только если не прошла следующая функция:
// ребра треугольника не пересекаются, но сфера ещё может быть внутри него.
bool EdgeSphereCollision(CVector3 &vPosition,CVector3 vPolygon[], int vertexCount, float radius);
// Возвращает true, если сфера пересекает переданный полигон. Параметры — вершины полигона,
// их число, центр и радиус сферы.
bool SpherePolygonCollision(CVector3 vPolygon[], CVector3 &vCenter,int vertexCount, float radius);
Реализуем эти функции в 3dmath.cpp:
/////
///// Новая функция: возвращает модуль переданного числа
/////
/////////////////////////////////////// ABSOLUTE \\\\\\\\\\\\\\\\\\\\\*
float Absolute(float num)
{
// Если число меньше нуля, возвращаем его модуль.
// Это просто. Можно или умножить число на -1, или вычесть его из нуля.
if(num < 0)
return (0 — num);// Вернём оригинальное число, т.к. оно итак полоэительно.
return num;
}////////////////////////////// SPHERE POLYGON COLLISION \\\\\\\\\\\\\\*
/////
///// Новая функция: возвращает true если сфера пересекает переданный полигон.
/////
////////////////////////////// SPHERE POLYGON COLLISION \\\\\\\\\\\\\\*bool SpherePolygonCollision(CVector3 vPolygon[],CVector3 &vCenter, int vertexCount, float radius)
{
// Для проверки пересечения мы будем вызывать только эту функцию. Остальные — только
// вспомогательные функции, вызываемые из неё. Теория немного сложна, но
// я постараюсь обьяснить всё как можно более доступно. Поехали!
// Мы пройдем следующие шаги:
//
// 1) Сначала нужно проверить, пересекается ли сфера с плоскостью, на которой находится
// полигон. Помните, что плоскости бесконечны, и сфера может быть хоть в пятистах
// единицах от полигона, если сфера пересекает его плоскость — триггер сработает.
// Нам нужно написать функцию, возвращающую положение сферы: либо она полностью
// с одной стороны плоскости, либо с другой, либо пересекает плоскость.
// Для этого мы создали функцию ClassifySphere(), которая возвращает BEHIND, FRONT
// или INTERSECTS. Если она вернёт INTERSECTS, переходим ко второму шагу, иначе — мы
// не пересекаем плоскость полигона.
//
// 2) Второй шаг — получить точку пересечения. Это одна из хитрых частей. Мы знаем,
// что имея точку пересечения с плоскостью, нужно просто вызвать функцию InsidePolygon(),
// чтобы увидеть, находится ли эта точка внутри полигона, точно так же, как мы делали
// в уроке «Коллизия линии и полигона». Итак, как получить точку пересечения? Это
// не так просто, как кажется. Поскольку на сфере может распологатся бесконечное
// число точек, могут быть миллионы точек пересечения. Мы попробуем немного другой путь.
// Мы знаем, что можем найти нормаль полигона, что скажет нам направление, куда
// он «смотрит». ClassifyPoly() кроме всего прочего вернёт дистанцию от центра сферы до
// плоскости. И если мы умножим нормаль на эту дистанцию, то получим некое смещение.
// Это смещение может затем быть вычтено из центра сферы. Хотите верьте, хотите нет,
// но теперь у нас есть точка на плоскости в направлении плоскости. Обычно эта точка
// пересечения работает хорошо, но если мы пересечем ребра полигона, она не сработает.
// То, что мы только что сделали, называется «проекция центра сферы на плоскость».
// Другой путь — «выстрелить» луч от центра сферы в направлении, противоположном
// нормали плоскости, тогда мы найдем точку пересечения линии (этого луча) и плоскости.
// Мой способ занимает 3 умножения и одно вычитание. Выбирайте сами.
//
// 3) Имея нашу псевдо-точку пересечения, просто передаём её в InsidePolygon(),
// вместе с вершинами полигона и их числом. Функция вернёт true, если точка
// пересечения находится внутри полигона. Запомните, одно то, что функция
// вернёт false, не значит, что мы на этом остановимся! Если мы ещё не «пересеклись»,
// переходим к шагу 4.
//
// 4) Если мы дошли досюда, значит, мы нашли точку пересечения, и она находится
// вне периметра полигона. Как так? Легко. Подумайте, если центр сферы находится
// вне треугольника, но есть пересечение — остаётся ещё её радиус. Последняя
// проверка нуждается в нахождении точка на каждом ребре полигона, которая
// ближе всего к центру сферы. У нас есть урок «ближайшая точка на линии», так что
// убедитесь, что вы его поняли, прежде, чем идти дальше. Если мы имеем дело
// с треугольником, нужно пройти три ребра и найти на них ближайшие точки к центру
// сферы. После этого рассчитываем дистанцию от этих точек до центра сферы. Если
// дистанция меньше, чем радиус, есть пересечение. Этот способ очень быстр.
// Вым не нужно рассчитывать всегда все три ребра, так как первая или вторая
// дистанция может быть меньше радиуса, и остальные рассчеты можно будет не производить.
//
// Это было вступление, *уфф!*. Надеюсь, вам ещё не хочется плакать от такого обилия
// теории, так как код на самом деле будет не слишком большим.
// 1) ШАГ ОДИН — Найдем положение сферы
// Сначала найдем нормаль полигона
CVector3 vNormal = Normal(vPolygon);
// Переменная для хранения дистанции от сферы
float distance = 0.0f;
// Здесь мы определяем, находится ли сфера спереди, сзади плоскости, или пересекает её.
// Передаём центр сферы, нормаль полигона, точку на плоскости (любую вершину), радиус
// сферы и пустой float для сохранения дистанции.
int classification = ClassifySphere(vCenter, vNormal, vPolygon[0], radius, distance);
// Если сфера пересекает плоскость полигона, нам нужно проверить, пересекает ли
// она сам полигон.
if(classification == INTERSECTS)
{
// 2) ШАГ ДВА — Находим псевдо точку пересечения.
// Теперь нужно спроецировать центр сфера на плоскость полигона, в направлении
// его номали. Это делается умножением нормали на расстояние от центра сферы
// до плоскости. Расстояние мы получили из ClassifySphere() только что.
// Если вы не понимаете суть проекции, представьте её примерно так:
// «я стартую из центра сферы и двигаюсь в направлении плоскости вдоль её нормали
// Когда я должен остановится? Тогда, когда моя дистанция от центра сферы станет
// равной дистанции от центра сферы до плоскости.»
CVector3 vOffset = vNormal * distance;
// Получив смещение «offset», просто вычитаем его из центра сферы. «vPosition»
// теперь точка, лежащая на плоскости полигона. Внутри ли она полигона — это
// другой вопрос.
CVector3 vPosition = vCenter — vOffset;
// 3) ШАГ ТРИ — Проверим, находится ли точка пересечения внутри полигона
// Эта функция использовалась и в нашем предыдущем уроке. Если точка пересечения внутри
// полигона, ф-я вернёт true, иначе false.
if(InsidePolygon(vPosition, vPolygon, vertexCount))
return true; // Есть пересечение!
else // Иначе
{
// 4) ШАГ ЧЕТЫРЕ — Проверим, пересекает ли сфера рёбра треугольника
// Если мы дошли досюда, центр сферы находится вне треугольника.
// Если хоть одна часть сферы пересекает полигон, у нас есть пересечение.
// Нам нужно проверить расстояние от центра сферы до ближайшей точки на полигоне.
if(EdgeSphereCollision(vCenter, vPolygon, vertexCount, radius))
{
return true; // We collided! «And you doubted me…» — Sphere
}
}
}
// Если мы здесь, пересечения нет
return false;
}
///////////////////////////////// CLASSIFY SPHERE \\\\\\\\\\\\\\\\*
/////
///// Новая функция: вычисляет положение сферы относительно плоскости, а так же расстояние
/////
///////////////////////////////// CLASSIFY SPHERE \\\\\\\\\\\\\\\\*
int ClassifySphere(CVector3 &vCenter,
CVector3 &vNormal, CVector3 &vPoint, float radius, float &distance)
{
// Сначала нужно найти расстояние плоскости от начала координат.
// Это нужно в дальнейшем для формулы дистанции.
float d = (float)PlaneDistance(vNormal, vPoint);
// Здесь мы используем знаменитую формулу дистанции, чтобы найти расстояние
// центра сферы от плоскости полигона.
// Напоминаю саму формулу: Ax + By + Cz + d = 0 with ABC = Normal, XYZ = Point
distance = (vNormal.x * vCenter.x + vNormal.y * vCenter.y + vNormal.z * vCenter.z + d);
// Теперь используем только что найденную информацию. Вот как работает коллизия
// сферы и плоскости. Если расстояние от центра до плоскости меньше, чем радиус
// сферы, мы знаем, что пересекли сферу. Берём модуль дистанции, так как если
// сфера находится за плоскостью, дистанция получится отрицательной.
// Если модуль дистанции меньше радиуса, сфера пересекает плоскость.
if(Absolute(distance) < radius)
return INTERSECTS;
// Если дистанция больше или равна радиусу, сфера находится перед плоскостью.
else if(distance >= radius)
return FRONT;
// Если и не спереди, и не пересекает — то сзади
return BEHIND;
}
///////////////////////////////// EDGE SPHERE COLLSIION \\\\\\\\\\\\\\\\*
/////
///// Новая ф-я: определяет, пересекает ли сфера какое-либо ребро треугольника
/////
///////////////////////////////// EDGE SPHERE COLLSIION \\\\\\\\\\\\\\\\*
bool EdgeSphereCollision(CVector3 &vCenter,
CVector3 vPolygon[], int vertexCount, float radius)
{
CVector3 vPoint;
// Эта ф-я принимает центр сферы, вершины полигона, их чичло и радиус сферы. Мы вернём
// true, если сфера пересекается с каким-либо ребром.
// Проходим по всем вершинам
for(int i = 0; i < vertexCount; i++)
{
// Это вернёт ближайшую к центру сферы точку текущего ребра.
vPoint = ClosestPointOnLine(vPolygon[i], vPolygon[(i + 1) % vertexCount], vCenter);
// Теперь нужно вычислить расстояние между ближайшей точкой и центром сферы
float distance = Distance(vPoint, vCenter);
// Если расстояние меньше радиуса, должно быть пересечение
if(distance < radius)
return true;
}
// Иначе пересечения не было
return false;
}
Если вы всё ещё не свихнулись от всей этой математики и читаете это — вы прошли все сложности, поздравляю! 😉 На самом деле это был не слишком лёгкий материал для быстрого усваивания. В следующем уроке мы рассмотрим, как всё это применить для расчета коллизий камеры в мире, а пока применим наши формулы на небольшом примере.
Файл main.cpp:
// Обьявим три глобальных переменных вверху файла:
// Массив из трех вершин для хранения координат треугольника
CVector3 g_vTriangle[3];
// Центр нашей сферы. Мы сможем перемещать его клавишами-стрелками.
CVector3 g_vPosition;
// Текущее вращение камеры (F1 & F2)
float g_rotateY = 0;
//////////////////////////////////////////////////////////////////////////////////
//
// Изменим функцию Init():
void Init(HWND hWnd)
{
g_hWnd = hWnd;
GetClientRect(g_hWnd, &g_rRect);
InitializeOpenGL(g_rRect.right, g_rRect.bottom); // Init OpenGL with the global rect
// Здесь мы инициализируем наш треугольник. Помните, имеет значение,
// в каком порядке вы инициализируете вершины. Это важно, поскольку
// исходя из этого будет рассчитыватся нормаль. Мы обьявим вершины
// против часовой стрелки — нижнюю-левую, нижнюю-правую, и наконец верхнюю.
g_vTriangle[0] = CVector3(—1, 0, 0);
g_vTriangle[1] = CVector3( 1, 0, 0);
g_vTriangle[2] = CVector3( 0, 1, 0);
// Теперь инициализируем позицию центра сферы.
g_vPosition = CVector3(0, 0.5f, 0);
}
///////////////////////////////////////////////////////////////////////////////////
//
// Изменим обработку клавиш. Блок WM_KEYDOWN функции WinProc():
case WM_KEYDOWN:
switch(wParam)
{
case VK_ESCAPE:
PostQuitMessage(0);
break;
case VK_UP: // Если нажата ВВЕРХ
g_vPosition.y += 0.01f; // Передвинем сферу вверх
break;
case VK_DOWN: // Если нажата ВНИЗ
g_vPosition.y -= 0.01f; // Передвинем сферу ВНИЗ
break;
case VK_LEFT: // Если нажата ВЛЕВО
g_vPosition.x -= 0.01f; // Передвинем влево
break;
case VK_RIGHT: // Если ВПРАВО
g_vPosition.x += 0.01f; // Передвинем вправо
break;
case VK_F3: // Если нажата F3
g_vPosition.z -= 0.01f; // Передвинем сферу вперед
break;
case VK_F4: // Если нажата F4
g_vPosition.z += 0.01f; // Передвинем сферу назад
break;
case VK_F1: // Если F1
g_rotateY -= 2; // Вращаем камеру влево
break;
case VK_F2: // Если F2
g_rotateY += 2; // То вправо
break;
}
//////////////////////////////////////////////////////////////////////////////////////////////////
//
// И наконец изменим функцию RenderScene():
void RenderScene()
{
int i=0;
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glLoadIdentity();
gluLookAt(—2.5f, 0.5, —0.1, 0, 0.5f, 0, 0, 1, 0);
// Врощаем камеру на угол g_rotateY
glRotatef(g_rotateY, 0, 1, 0);
// устанавливаем радиус сферы
float radius = 0.1f;
// Рисуем полигон
glBegin (GL_TRIANGLES);
glColor3ub(255, 0, 0);
glVertex3f(g_vTriangle[0].x, g_vTriangle[0].y, g_vTriangle[0].z);
glColor3ub(0, 255, 0);
glVertex3f(g_vTriangle[1].x, g_vTriangle[1].y, g_vTriangle[1].z);
glColor3ub(0, 0, 255);
glVertex3f(g_vTriangle[2].x, g_vTriangle[2].y, g_vTriangle[2].z);
glEnd();
// Вместо создания сферы вручную мы создадим quadric-обьект.
GLUquadricObj *pObj = gluNewQuadric();
// Чтобы лучше всё визуализировать, сделаем сферу каркасной
gluQuadricDrawStyle(pObj, GLU_LINE);
// Move the sphere to it’s center position
glTranslatef(g_vPosition.x, g_vPosition.y, g_vPosition.z);
// Теперь воспользуемся замечательной функцией, которая сделает всё за нас.
// Всё, что нам нужно сделать — передать в неё массив вершин треугольника,
// центр сферы и её радиус. Функция вернёт true/false в зависимости от
// факта пересечения.
bool bCollided = SpherePolygonCollision(g_vTriangle, g_vPosition, 3, radius);
// Если есть пересечение, делаем сферу зеленой, иначе — фиолетовой
if(bCollided)
glColor3ub(0, 255, 0);
else
glColor3ub(255, 0, 255);
// Рисуем сферу с радиусом .1 и детальностью 15х15.
gluSphere(pObj, radius, 15, 15);
gluDeleteQuadric(pObj);
SwapBuffers(g_hDC);
}