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 \\\\\\\\\\\\\\\\*
/////
/////   Проверяет, находится ли куб внутри пирамиды, по его центру и ½ его длинны
/////
///////////////////////////////// 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'е, но я не хочу усложнять этот урок. Возможно, вскоре я напишу более подробный урок на эту тему.

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

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