OpenGL: Коллизия сферы и полигона

Код этого урока взят из урока «Коллизия линии и полигона». Теперь вместо проверки пересечения линии мы сделаем лучше — проверку пересечения со сферой. Эта техника отлично подойдет для расчета коллизий камеры в мире. Поскольку коллизия сферы как с плоскостью, так и с полигоном, очень просты, я объясню и то и другое. В этом уроке мы сможем двигать сферу вокруг полигона, и проверять, пересекается ли она с ним. При пересечении сфера будет закрашена зелёным цветом, иначе — фиолетовым.

Мы добавим 4 новых функции и 3 дефайна в нашу математическую «библиотеку».

Файл 3dmath.h:

// Сначала три константы. Они будут использоватся для возвращаемых значений ClassifySphere ().
#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 \\\\\\\\\\\\\\\\\\\\\*
/////
/////   Новая функция: возвращает модуль переданного числа
/////
/////////////////////////////////////// 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);
}

Исходные коды к уроку

Понравилась статья? Поделиться с друзьями: