Array ( )
Вход:




Главная | OpenGL | GLSL | AI | Сеть | Примеры | Библиотека

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);
}
 






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




Комментарии:

Войдите, чтобы оставить комментарий:












Яндекс.Метрика
 Яндекс цитирования.