Array ( )
Вход:




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

OpenGL: Frustum Culling (Отрисовка только видимых полигонов)






frustum - это усеченная пирамида, образуемая шестью плоскостями. Её вершина -
"глаз" игрока, или позиция камеры. Плоскости её проходят через стороны экрана монитора.
Всё, что не попадает в эту пирамиду, отрисовывать не нужно: всё равно видно не будет.

Этот урок продемонстрирует вам способ узнать, находится ли обьект внутри пирамиды frustum.
Этот тест необходим каждой программе, особенно если в ней много обьектов. Без него программа
будет выполнятся заметно медленнее.

Этот урок основан на уроке "Камера - часть 5 - Стрейф".
Из main.cpp удалим лишние функции: CreatePyramid(), DrawSpiralTowers(), Draw3DSGrid(),
и очистим RenderScene();

Подредактируем файл main.h:
// Добавим некоторые новые структуры. По-хорошему их нужно вынести в отдельный хидер,
// но для одного урока сойдёт и так.

// Структура для наших сфер
struct Sphere
{
    float xPos, yPos, zPos, radius;             // Позиции XYZ и радиус
    BYTE  r, g, b;                              // Цвет сферы
};

///////////////////////////////////////////////////////////
//
//      Новый класс, описание его будет в Frustrum.cpp:
//
///////////////////////////////////////////////////////////
class CFrustum {

public:

    // Вызывается каждый раз при движении камеры, чтобы обновить пирамиду
    void CalculateFrustum();

    // Принимает 3D точку и возвращает TRUE, если она находится внутри frustum'a
    bool PointInFrustum(float x, float y, float z);

    // Принимает точку и радиус и возвращает TRUE, если она находится внутри frustum'a
    bool SphereInFrustum(float x, float y, float z, float radius);

    // Принимает центр и половину длинны куба
    bool CubeInFrustum( float x, float y, float z, float size );

private:

    // Хранит A B C и D переменные для каждой стороны пирамиды.
    float m_Frustum[6][4];
};
 



Теперь напишем реализацию самого важного класса для этого урока: файл Frustum.cpp
#include "main.h"

// Создадим enum-переменную для обозначения сторон:
enum FrustumSide
{
    RIGHT   = 0,        // Правая сторона пирамиды
    LEFT    = 1,        // Левая сторона пирамиды
    BOTTOM  = 2,        // Нижняя сторона пирамиды
    TOP     = 3,        // Верхняя сторона пирамиды
    BACK    = 4,        // Задняя сторона пирамиды
    FRONT   = 5         // Передняя
};

// Также создадим enum для обозначения переменных плоскости:
enum PlaneData
{
    A = 0,              // Значение X нормали плоскости
    B = 1,              // Значение Y нормали плоскости
    C = 2,              // Значение Z нормали плоскости
    D = 3               // Расстояние плоскости от начала координат
};


///////////////////////////////// NORMALIZE PLANE \\\\\\\\\\\\\\\\*
/////
/////   Нормализует плоскость (сторону) переданного frustum
/////
///////////////////////////////// NORMALIZE PLANE \\\\\\\\\\\\\\\\*

void NormalizePlane(float frustum[6][4], int side)
{
    // Вычисляем величину нормали плоскости (точку A B C)
    // Помните, что (A, B, C) плоскости - то же самое, что (X, Y, Z) для нормали.
    // Чтобы вычислить величину, используем формулу: sqrt(x^2 + y^2 + z^2)
    float magnitude = (float)sqrt( frustum[side][A] * frustum[side][A] +
                                   frustum[side][B] * frustum[side][B] +
                                   frustum[side][C] * frustum[side][C] );

    // Затем делим значения плоскости на её величину.
    // После этого с плоскостью будет легче работать.
    frustum[side][A] /= magnitude;
    frustum[side][B] /= magnitude;
    frustum[side][C] /= magnitude;
    frustum[side][D] /= magnitude;
}

///////////////////////////////// CALCULATE FRUSTUM \\\\\\\\\\\\\\\\*
/////
/////   Вычисляет frustum из матриц проекции и моделей
/////
///////////////////////////////// CALCULATE FRUSTUM \\\\\\\\\\\\\\\\*

void CFrustum::CalculateFrustum()
{
    float   proj[16];           // Матрица проекции
    float   modl[16];           // Матрица моделей
    float   clip[16];           // Плоскости обрезания

    // glGetFloatv() используется, чтобы извлечь информацию о нашем OpenGL мире.
    // мы передаём GL_PROJECTION_MATRIX чтобы получить информацию о матрице проекций.
    // Функция сохранит информацию в массиве [16].
    glGetFloatv( GL_PROJECTION_MATRIX, proj );

    // Передавая GL_MODELVIEW_MATRIX, мы запрашиваем информацию о матрице моделей.
    // Она также сохранится в массиве [16].
    glGetFloatv( GL_MODELVIEW_MATRIX, modl );

    // Теперь, имея матрицы проекции и моделей, если мы их скомбинируем, то получим плоскости
    // отсечения. Для этого мы умножим матрицы друг на друга.

    clip[ 0] = modl[ 0] * proj[ 0] + modl[ 1] * proj[ 4] + modl[ 2] * proj[ 8] + modl[ 3] * proj[12];
    clip[ 1] = modl[ 0] * proj[ 1] + modl[ 1] * proj[ 5] + modl[ 2] * proj[ 9] + modl[ 3] * proj[13];
    clip[ 2] = modl[ 0] * proj[ 2] + modl[ 1] * proj[ 6] + modl[ 2] * proj[10] + modl[ 3] * proj[14];
    clip[ 3] = modl[ 0] * proj[ 3] + modl[ 1] * proj[ 7] + modl[ 2] * proj[11] + modl[ 3] * proj[15];

    clip[ 4] = modl[ 4] * proj[ 0] + modl[ 5] * proj[ 4] + modl[ 6] * proj[ 8] + modl[ 7] * proj[12];
    clip[ 5] = modl[ 4] * proj[ 1] + modl[ 5] * proj[ 5] + modl[ 6] * proj[ 9] + modl[ 7] * proj[13];
    clip[ 6] = modl[ 4] * proj[ 2] + modl[ 5] * proj[ 6] + modl[ 6] * proj[10] + modl[ 7] * proj[14];
    clip[ 7] = modl[ 4] * proj[ 3] + modl[ 5] * proj[ 7] + modl[ 6] * proj[11] + modl[ 7] * proj[15];

    clip[ 8] = modl[ 8] * proj[ 0] + modl[ 9] * proj[ 4] + modl[10] * proj[ 8] + modl[11] * proj[12];
    clip[ 9] = modl[ 8] * proj[ 1] + modl[ 9] * proj[ 5] + modl[10] * proj[ 9] + modl[11] * proj[13];
    clip[10] = modl[ 8] * proj[ 2] + modl[ 9] * proj[ 6] + modl[10] * proj[10] + modl[11] * proj[14];
    clip[11] = modl[ 8] * proj[ 3] + modl[ 9] * proj[ 7] + modl[10] * proj[11] + modl[11] * proj[15];

    clip[12] = modl[12] * proj[ 0] + modl[13] * proj[ 4] + modl[14] * proj[ 8] + modl[15] * proj[12];
    clip[13] = modl[12] * proj[ 1] + modl[13] * proj[ 5] + modl[14] * proj[ 9] + modl[15] * proj[13];
    clip[14] = modl[12] * proj[ 2] + modl[13] * proj[ 6] + modl[14] * proj[10] + modl[15] * proj[14];
    clip[15] = modl[12] * proj[ 3] + modl[13] * proj[ 7] + modl[14] * proj[11] + modl[15] * proj[15];

    // Теперь нам нужно получить стороны frustum'а. Чтобы сделать это,
    // возьмём обрезающие плоскости, полученные выше, и из них получим стороны.

    // получаем ПРАВУЮ сторону frustum'а
    m_Frustum[RIGHT][A] = clip[ 3] - clip[ 0];
    m_Frustum[RIGHT][B] = clip[ 7] - clip[ 4];
    m_Frustum[RIGHT][C] = clip[11] - clip[ 8];
    m_Frustum[RIGHT][D] = clip[15] - clip[12];

    // Теперь, имея нормаль (A,B,C) и расстояние (D) к плоскости,
    // нам нужно нормализовать нормаль и дистанцию

    // Нормализуем правую сторону
    NormalizePlane(m_Frustum, RIGHT);

    // получаем ЛЕВУЮ сторону frustum'а
    m_Frustum[LEFT][A] = clip[ 3] + clip[ 0];
    m_Frustum[LEFT][B] = clip[ 7] + clip[ 4];
    m_Frustum[LEFT][C] = clip[11] + clip[ 8];
    m_Frustum[LEFT][D] = clip[15] + clip[12];

    // Нормализуем ЛЕВУЮ сторону
    NormalizePlane(m_Frustum, LEFT);

    // получаем нижнюю сторону frustum'а
    m_Frustum[BOTTOM][A] = clip[ 3] + clip[ 1];
    m_Frustum[BOTTOM][B] = clip[ 7] + clip[ 5];
    m_Frustum[BOTTOM][C] = clip[11] + clip[ 9];
    m_Frustum[BOTTOM][D] = clip[15] + clip[13];

    // Нормализуем нижнюю сторону
    NormalizePlane(m_Frustum, BOTTOM);

    // получаем верхнюю сторону frustum'а
    m_Frustum[TOP][A] = clip[ 3] - clip[ 1];
    m_Frustum[TOP][B] = clip[ 7] - clip[ 5];
    m_Frustum[TOP][C] = clip[11] - clip[ 9];
    m_Frustum[TOP][D] = clip[15] - clip[13];

    // Нормализуем верхнюю сторону
    NormalizePlane(m_Frustum, TOP);

    // получаем заднюю сторону frustum'а
    m_Frustum[BACK][A] = clip[ 3] - clip[ 2];
    m_Frustum[BACK][B] = clip[ 7] - clip[ 6];
    m_Frustum[BACK][C] = clip[11] - clip[10];
    m_Frustum[BACK][D] = clip[15] - clip[14];

    // Нормализуем заднююсторону
    NormalizePlane(m_Frustum, BACK);

    // получаем переднюю сторону frustum'а
    m_Frustum[FRONT][A] = clip[ 3] + clip[ 2];
    m_Frustum[FRONT][B] = clip[ 7] + clip[ 6];
    m_Frustum[FRONT][C] = clip[11] + clip[10];
    m_Frustum[FRONT][D] = clip[15] + clip[14];

    // Нормализуем переднюю сторону
    NormalizePlane(m_Frustum, FRONT);
}


// Код ниже будет проверять, находится ли обьект в нашей пирамиде. Например, нам
// нам нужно проверить, попадает ли во frustum точка, сфера или куб.
// Поскольку наши стороны пирамиды обращены нормалями внутрь, если точка (обьект) лежит
// ПЕРЕД каждой из плоскостей, он находится внутри пирамиды.

///////////////////////////////// POINT IN FRUSTUM \\\\\\\\\\\\\\\\*
/////
/////   Определяет, находится ли точка внутри frustum'а
/////
///////////////////////////////// POINT IN FRUSTUM \\\\\\\\\\\\\\\\*

bool CFrustum::PointInFrustum( float x, float y, float z )
{
    // Если вы помните формулу плоскости (A*x + B*y + C*z + D = 0), остальной код
    // будет понятен и очевиден. Если вы не знаете формулы плоскости, лучше вернитесь
    // к уроку "Коллизия плоскости".
    // (A,B,C) - это (X,Y,Z) нормали плоскости. Формула равна нулю, если точка лежит НА
    // плоскости. Если точка ПОЗАДИ плоскости, значение будет отрицательным, если же
    // ПЕРЕД плоскостью - значение будет положительным. Нам нужно проверить, находится
    // ли точка ПЕРЕД плоскостью, так что всё, что нам нужно сделать - пройти через
    // каждую точку и применить к ней формулу плоскости. Результат будет расстоянием
    // до плоскости.


    // Проходим через все стороны пирамиды.
    for(int i = 0; i < 6; i++ )
    {
        // Применяем формулу плоскости и проверяем, находится ли точка позади плоскости.
        // Если она позади хотя бы одной плоскости из всех, можно возвращать false.
        if(m_Frustum[i][A] * x + m_Frustum[i][B] * y + m_Frustum[i][C] * z + m_Frustum[i][D] <= 0)
        {
            // Точка находится позади стороны, так что она НЕ внутри пирамиды
            return false;
        }
    }

    // Иначе точка находится внутри пирамиды, возвращаем true
    return true;
}


///////////////////////////////// SPHERE IN FRUSTUM \\\\\\\\\\\\\\\\*
/////
/////   Определяет, находится ли сфера внутри нашей плоскости, по центру и радиусу сферы.
/////
///////////////////////////////// SPHERE IN FRUSTUM \\\\\\\\\\\\\\\\*

bool CFrustum::SphereInFrustum( float x, float y, float z, float radius )
{
    // Эта функция почти идентична предыдущей. Отличие в том, что деперь нам придется
    // учесть ещё и радиус вокруг точки. Например, одно то, что центр сферы находится вне
    // пирамиды, ещё не значит, что и все её точки находятся снаружи. Поэтому вместо проверки,
    // меньше ли результат формулы нуля (<=0), нужно прибавить к нулю отрицательный радиус сферы.

    // Проходим через все стороны пирамиды
    for(int i = 0; i < 6; i++ )
    {
        // Если центр сферы дальше от плоскости, чем её радиус
        if( m_Frustum[i][A] * x + m_Frustum[i][B] * y + m_Frustum[i][C] * z +
                m_Frustum[i][D] <= -radius )
        {
            // То и вся сфера снаружи, возвращаем false
            return false;
        }
    }

    // Иначе сфера внутри
    return true;
}


///////////////////////////////// CUBE IN FRUSTUM \\\\\\\\\\\\\\\\*
/////
/////   Проверяет, находится ли куб внутри пирамиды, по его центру и 1/2 его длинны
/////
///////////////////////////////// CUBE IN FRUSTUM \\\\\\\\\\\\\\\\*

bool CFrustum::CubeInFrustum( float x, float y, float z, float size )
{
    // Тут работы немного больше, но тоже не слишком много.
    // Нам передаётся центр куба и половина его длинны. Думайте о длинне так же,
    // как о радиусе для сферы. Мы проверяем каждую точку куба на нахождение внутри
    // пирамиды. Если точка находится перед стороной, переходим к следующей сторону.

    for(int i = 0; i < 6; i++ )
    {
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][B] * (y - size) +
            m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][B] * (y - size) +
            m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][B] * (y + size) +
            m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][B] * (y + size) +
            m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][B] * (y - size) +
            m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][B] * (y - size) +
            m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][B] * (y + size) +
            m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][B] * (y + size) +
            m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;

        // Если мы дошли досюда, куб не внутри пирамиды.
        return false;
    }

    return true;
}






Наконец, изменим файл main.cpp:
// Для начала обьявим новые переменные.

// Переменные для наших сфер:
#define MAX_SPHERES 1000        // Максимальное число сфер
#define MAX_DISTANCE    30      // Расстояние, на котором сферы исчезают с обоих сторон
#define SPHERE_SPEED    0.2f        // Скорость движения сфер
#define MAX_RADIUS  5       // Радиус сфер * 10 (На самом деле он = 0.5)


// Наш глобальный frustum-обьект
CFrustum g_Frustum;


// Вкл/выкл обрезку примитивов по фруструму
bool g_bIgnoreFrustum = false;

// Изменяется клавишами +/-:
int g_MaxSpheres = MAX_SPHERES / 2;

// Структура, хранящая данные всех сфер:
Sphere g_Spheres[MAX_SPHERES];





///////////////////////////////////////////////////////////////////////////////
//
//         Изменим функцию RenderScene():
//
///////////////////////////////////////////////////////////////////////////////
void RenderScene()
{
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glLoadIdentity();

    int spheresRendered = 0;        // Число отрисовываемых в данный момент сфер
    char strText[255]={0};          // Текст для вывода

    // Устанавливаем позицию камеры
    g_Camera.Look();

    // В этом примере пирамида рассчитывается каждый кадр. Это не обязательно, это нужно делать
    // только при движении камеры, но в данном случае это не имеет значения.
    g_Frustum.CalculateFrustum();

    GLUquadricObj *pObj = gluNewQuadric();

    // Проходим циклом через все сферы и рендерим их, если они попали в конус
    for(int i = 0; i < g_MaxSpheres; i++)
    {
        g_Spheres[i].zPos += SPHERE_SPEED;  // Передвигаем сферу

        // Теперь проверяем, находится ли сфера в поле зрения. Если g_bIgnoreFrustum==true,
        // они всё равно будут отрисовыватся.

        if(g_bIgnoreFrustum || g_Frustum.SphereInFrustum(g_Spheres[i].xPos, g_Spheres[i].yPos,
            g_Spheres[i].zPos, g_Spheres[i].radius))
        {
            // Устанавливаем цвет сферы
            glColor3ub(g_Spheres[i].r, g_Spheres[i].g, g_Spheres[i].b);
            glPushMatrix();
            // Устанавливаем положение сферы
            glTranslatef(g_Spheres[i].xPos, g_Spheres[i].yPos, g_Spheres[i].zPos);
            // И рисуем сферу.
            gluSphere(pObj, g_Spheres[i].radius, 20, 20);
            glPopMatrix();

            // Увеличиваем счетчик
            spheresRendered++;
        }

        // Проверяем, не вышли ли сферы за пределы видимости. Если вышли, их нужно вернуть
        // к началу с новой рандомной позицией.
        if(g_Spheres[i].zPos > MAX_DISTANCE) {
            g_Spheres[i].xPos = (rand() % (MAX_DISTANCE * 10)) * 0.1f;
            g_Spheres[i].yPos = (rand() % (MAX_DISTANCE * 10)) * 0.1f;
            g_Spheres[i].zPos = -MAX_DISTANCE;

            if(rand() % 2) g_Spheres[i].xPos = -g_Spheres[i].xPos;
            if(rand() % 2) g_Spheres[i].yPos = -g_Spheres[i].yPos;
        }
    }

    sprintf(strText, "Spheres Rendered: %d / %d", spheresRendered, g_MaxSpheres);
    SetWindowText(g_hWnd, strText);
 
    SwapBuffers(g_hDC);
    gluDeleteQuadric(pObj);
}



////////////////////////////////////////////////////////////////////////////////
//
//      В функции Init() проинициализируем необходимые переменные:
//

    ShowCursor(false);

    //                      Позиция          Напр-е     верт. вектор
    g_Camera.PositionCamera(0, 1, 6,   0, 0.5f, 0,   0, 1, 0);

    // Включаем освещение и оставляем его со значениями по умолчанию
    glEnable(GL_LIGHT0);
    glEnable(GL_LIGHTING);

    // Т.к. освещение включено, нужно разрешить наложение цветов на поверхность
    glEnable(GL_COLOR_MATERIAL);

    srand(GetTickCount());

    // Инициализируем все сферы, со случайным цветом и расположением
    for(int i = 0; i < MAX_SPHERES; i++)
    {
        // Присваиваем радиус и позицию - не далее 30 единиц от камеры
        g_Spheres[i].radius = (rand() % MAX_RADIUS) * 0.1f;
        g_Spheres[i].xPos = (rand() % (MAX_DISTANCE * 10)) * 0.1f;
        g_Spheres[i].yPos = (rand() % (MAX_DISTANCE * 10)) * 0.1f;
        g_Spheres[i].zPos = (rand() % (MAX_DISTANCE * 10)) * 0.1f;

        if(rand() % 2) g_Spheres[i].xPos = -g_Spheres[i].xPos;
        if(rand() % 2) g_Spheres[i].yPos = -g_Spheres[i].yPos;
        if(rand() % 2) g_Spheres[i].zPos = -g_Spheres[i].zPos;

        // Присваиваем случайный цвет
        g_Spheres[i].r = rand() % 256;
        g_Spheres[i].g = rand() % 256;
        g_Spheres[i].b = rand() % 256;
    }







///////////////////////////////////////////////////////////////////////////////////
//
//            И наконец напишем обработку нужных нам клавиш в функции WinProc():
//

    case WM_KEYDOWN:
        switch(wParam)
        {
            case VK_ESCAPE:
                PostQuitMessage(0);                     // Выходим
                break;
            case VK_ADD:
                g_MaxSpheres += 10;

                if(g_MaxSpheres > MAX_SPHERES)
                {
                    g_MaxSpheres = MAX_SPHERES;
                }
                break;

            case VK_SUBTRACT:
                g_MaxSpheres -= 10;

                if(g_MaxSpheres < 0)
                {
                    g_MaxSpheres = 0;
                }
                break;

            case 'c': case 'C': case VK_SPACE:
                g_bIgnoreFrustum = !g_bIgnoreFrustum;
                break;
        }
        break;
 




Frustum culling - ОЧЕНЬ полезная вещь в 3D-графике. Если вы создадите более-менее
большой мир, нельзя просто отправлять его на рендер, предоставив обо всём заботится OpenGL.
Так у вас в итоге получится 0.001 FPS.
Нажимая "+", вы можете поднять количество сфер до 1000. Отключите frustum culling и сравните.
Значительная разница будет заметна даже на мощном компьютере.
Конечно, обычно сцена состоит не из простого потока сфер. В таком случае вам нужно просто
задать обьекту некое значение, "радиус", и проверять это значение так же, как и в случае со сферой
или кубом.

Этот урок - хорошее вступление к понятию OCtree. Скорее всего в ближайшее время я напишу урок на
эту тему.

Итак, давайте пробежимся по уроку ещё раз.
1) Сначала нам нужно получить виртуальную пирамиду взгляда. Для этого нам нужны матрицы проекции и
моделей. Для получения матрицы проекции используем:
glGetFloatv( GL_PROJECTION_MATRIX, /* массив float[16] */ );

Точно так же для получения матрицы моделей используем:
glGetFloatv( GL_MODELVIEW_MATRIX, /* массив float[16] */ );

2) Затем нам нужно скомбинировать эти две матрицы. Делаем это путём их перемножения.

3) Теперь мы можем получить виртуальные стороны пирамиды взгляда. Это даст нам нормаль и расстояние
до начала координат (ABC и D).

4) После абстрагирования стороны нормализуем данные плоскости (A, B, C и D).

5) Теперь у нас есть наша пирамида, и мы можем проверять обьекты на нахождение внутри неё, используя
формулу плоскости. Ещё раз, формула плоскости: (A*x + B*y + C*z + D = 0). Если результат = 0, точка
лежит на плоскости; если меньше 0 - точка лежит позади плоскости; если больше 0 - перед ней.

Много чего ещё можно сказать о frustum-culling'е, но я не хочу усложнять этот урок. Возможно, вскоре я напишу
более подробный урок на эту тему.






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




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

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












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