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

// Вызывается каждый раз при движении камеры, чтобы обновить пирамиду
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];
};

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

// Для начала обьявим новые переменные.

// Переменные для наших сфер:
#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;