Привет! Сегодня мы поговорим о графической стороне игрового движка, а именно об одном из способов оптимизации рендеринга 3D-окружения — quad-деревьях. Если ты играл в такие игры как, Tribes 1 и 2, Tread Marks, Myth 1 и 2 и HALO, то, наверное, обратил внимание на то, что в этих играх рисуются чертовски большие территории, показывая нам окружающие окрестности чуть-ли не до самого горизонта (согласен, в Myth ни какого горизонта нет, но это не принципиально :). Всей этой красотищи могло бы не быть совсем, если бы в чью-то светлую голову не пришла простая до гениальности идея построения quad-деревьев. Начну из далека.

Для того, чтобы представить в компьютере трехмерную модель ландшафта (речь пока идет только про землю, без деревьев, домиков и прочих посторонних объектов) очень часто пользуются «картами высот». Самая простая карта высот (heightmap) представляет из себя черно-белый битмап, в котором с помощью градации цвета указывается высота каждой точки, т.е. чем чернее точка, тем ниже ее положение относительно «уровня моря» (нулевой отметки), а чем белее, тем выше.

После построения карты высот (сделать это можно в любом графическом редакторе) ее следует преобразовать в 3D, для этого создается сетка из полигонов

в которой каждая вершина связывается с соответствующей точкой в битмапе и потом на эту сетку накладывается текстура 

(для всех доброжелателей, обвиняющих меня в необоснованных амбициях, сообщаю что здесь и далее приводятся скриншоты только из моих движков, сегодня им будет мой старенький Terrain Engine).

Теперь представь, что у нас имеется сетка размером 1024х1024 вершин, т.е. 1024х1024х2 = 2 097 152 треугольников чистой земли, без остальных in-game моделек, и если ты будешь бездумно рисовать все эти полигоны, то твоя игра превратится в эдакое слайд-шоу для
мазохистов, хотя очевидно, что бОльшая часть треугольников вообще не будет видна. Наша задача состоит в том, чтобы отбросить все те полигоны, которые лежат вне поля зрения нашей виртуальной камеры, и постараться сделать это как можно быстрее. Тут на помощь и приходят quad-деревья.

Общая идея и организация quad-деревьев

Quad-дерево представляет собой рекурсивное разбиение пространства на четыре части, т.е. кореневой узел дерева разбивает нашу сетку из полигонов на четыре части, затем каждый из четырех потомков корня делит свою часть еще на четыре части и так до тех пор, пока делить будет нечего.

Если ты уже имел дело с трехмерной графикой, то наверное знаешь, что такое bounding box или сокращенно bbox (би-бокс). Остальным же рассказываю, bbox — это всего лишь параллепипед, ограничивающий некоторый объем трехмерного пространства. Обычно bbox’ы используются для обработки коллизий. Например, в первокваке для каждой модельки определялся свой bbox и для того, чтобы выстрелом попасть в какого-нибудь шамблера, достаточно было попасть в такую вот невидимую коробку, поэтому попытки пропустить ракету между ног супостата всегда заканчивались попаданием в оного.

Разговор о bounding box’ах я завел потому что на этапе построения quad-дерева, для каждого узла необходимо определить размеры и координаты bbox’а, ограничивающего ту часть пространства, которая связана с данным узлом, т.е. для корневого узла мы сохраняем информацию о bbox’е в который заключена вся наша карта, когда мы будем делить карту на четыре части, то для каждого потомка создадим свой bbox, который будет ограничивать объем занимаемый каждым узлом, и т.д.

Когда quad-дерево будет построено, им можно воспользоваться для быстрого определения видимости того или иного участка земли. Делается это все тем же рекурсивным обходом дерева: заходим в корень дерева и смотрим, какие из 4-х потомков видны из текущего положения нашей виртуальной камеры, а какие нет; потом, проигнорировав невидимых потомков (а нафига они нам :), обходим видимых, в каждом из которых совершаем идентичную операцию, т.е. проверяем видимость их потомков и начинаем обход, тех, что оказались видимыми. В результате, когда мы закончим обход всего дерева, мы будем точно знать, что нам следует рисовать.

Определение видимости узла quad-дерева

Основной функцией при рендеринге quad-дерева является функция для определения видимости узла дерева, а точнее определение видимости bbox’а, ограничивающего данный узел. Делается это
довольно просто. Достаточно убедиться, что bbox не пересекает раструб камеры (видимый объем) и тогда можно считать его невидимым. 

Если ты работаешь с Direct3D или с OpenGL, а не занимаешься самодеятельностью (что мне, на самом деле, намного ближе :), то для преобразования координат пользуешься двумя матрицами: видовой матрицей, с помощью которой выполняются сдвиг, вращение и масштабирование, и матрицей проекций, с помощью которой выполняется проецирование вершин на экран, а зная эти матрицы можно легко получить уравнения шести плоскостей, ограничивающих видимый объем для данного положения камеры. В листинге 2.1 приведен пример кода, извлекающего все шесть плоскостей раструба камеры для OpenGL-приложения.

Листинг 2.1

// структура для хранения уравнения плоскости: Ax + By + Cz = D
typedef struct {
float normal[3]; // нормаль к плоскости (A, B, C)
float dist; // коэфициент D 
} plane_t;

// шесть плоскостей, ограничивающих видимый объем
plane_t frustum[6];

/*
=================
UpdateFrustum

функция для извлечения плоскостей.
Length () должна возвращать длину вектора.
=================
*/
void UpdateFrustum (void)
{
float proj[16]; // матрица проекций
float view[16]; // видовая матрица
float clip[16]; // результат перемножения матриц
float t;

// сохраняем текущую матрицу
glPushMatrix ();

// получаем видовую матрицу
glGetFloatv(GL_MODELVIEW_MATRIX, view);

// получаем матрицу проекций
glGetFloatv(GL_PROJECTION_MATRIX, proj);

// перемножаем матрицы
glLoadMatrixf (proj);
glMultMatrixf (view);

// получаем результат перемножения view*proj
glGetFloatv(GL_MODELVIEW_MATRIX, clip);

восстанавливаем первоначальную матрицу
glPopMatrix ();

// извлекаем уравнение правой плоскости
frustum[0].normal[0] = clip[ 3] — clip[ 0];
frustum[0].normal[1] = clip[ 7] — clip[ 4];
frustum[0].normal[2] = clip[11] — clip[ 8];
frustum[0].dist = clip[15] — clip[12];

// нормализуем результат
t = 1/Length(frustum[0].normal);
frustum[0].normal[0] *= t;
frustum[0].normal[1] *= t;
frustum[0].normal[2] *= t;
frustum[0].dist *= t;

// извлекаем левую плоскость
frustum[1].normal[0] = clip[ 3] + clip[ 0];
frustum[1].normal[1] = clip[ 7] + clip[ 4];
frustum[1].normal[2] = clip[11] + clip[ 8];
frustum[1].dist = clip[15] + clip[12];

// нормализуем результат
t = 1/Length(frustum[1].normal);
frustum[1].normal[0] *= t;
frustum[1].normal[1] *= t;
frustum[1].normal[2] *= t;
frustum[1].dist *= t;

// извлекаем нижнюю плоскость
frustum[2].normal[0] = clip[ 3] + clip[ 1];
frustum[2].normal[1] = clip[ 7] + clip[ 5];
frustum[2].normal[2] = clip[11] + clip[ 9];
frustum[2].dist = clip[15] + clip[13];

// нормализуем результат
t = 1/Length(frustum[2].normal);
frustum[2].normal[0] *= t;
frustum[2].normal[1] *= t;
frustum[2].normal[2] *= t;
frustum[2].dist *= t;

// извлекаем верхнюю плоскость
frustum[3].normal[0] = clip[ 3] — clip[ 1];
frustum[3].normal[1] = clip[ 7] — clip[ 5];
frustum[3].normal[2] = clip[11] — clip[ 9];
frustum[3].dist = clip[15] — clip[13];

// нормализуем результат
t = 1/Length(frustum[3].normal);
frustum[3].normal[0] *= t;
frustum[3].normal[1] *= t;
frustum[3].normal[2] *= t;
frustum[3].dist *= t;

// извлекаем уравнение дальней плоскости
frustum[4].normal[0] = clip[ 3] — clip[ 2];
frustum[4].normal[1] = clip[ 7] — clip[ 6];
frustum[4].normal[2] = clip[11] — clip[10];
frustum[4].dist = clip[15] — clip[14];

// нормализуем результат
t = 1/Length(frustum[4].normal);
frustum[4].normal[0] *= t;
frustum[4].normal[1] *= t;
frustum[4].normal[2] *= t;
frustum[4].dist *= t;

// извлекаем ближнюю плоскость
frustum[5].normal[0] = clip[ 3] + clip[ 2];
frustum[5].normal[1] = clip[ 7] + clip[ 6];
frustum[5].normal[2] = clip[11] + clip[10];
frustum[5].dist = clip[15] + clip[14];

// нормализуем результат
t = 1/Length(frustum[5].normal);
frustum[5].normal[0] *= t;
frustum[5].normal[1] *= t;
frustum[5].normal[2] *= t;
frustum[5].dist *= t;
}

Получив уравнения плоскостей раструба камеры, легко выполнить тест на пересечение bbox’а с видимым объемом (см. листинг 2.2).

Листинг 2.2

// новый тип — «вершина»
typedef float vertex[3];

// макрос для вычисления скалярного произведения
#define DotProduct(x,y) (x[0]*y[0]+x[1]*y[1]+x[2]*y[2])

/*
====================
PointInFrustum

Возвращает true, когда данная точка лежит внутри видимого объема,
т.е. когда расстояния от точки до всех плоскостей раструба больше 0.
====================
*/
bool PointInFrustum(vertex point)
{
int i;

for (i=0 ; i<6 ; i++)
// если расстояние от точки до плоскости меньше 0,
// то возвращаем false
if (DotProduct(frustum[i].normal, point) + frustum[i].dist <= 0)
return false;

return true;
}

/*
==============
BoxVisible

Возвращает false если параллепипед не пересекает видимый объем,
т.е. является невидимым.
verts — это массив восьми вершин задающих параллепипед.
==============
*/
bool BoxVisible(vertex verts[8]) //TODO: optimization
{
int i, j;

for (i=0 ; i<6 ; i++) {
for (j=0 ; j<8 ; j++) {

// если расстояние от вершины до плоскости >= 0, то
// переходим к следующей плоскости
if (DotProduct(frustum[i].normal, verts[j]) + frustum[i].dist >= 0)
break;
}

// если расстояния от всех вершин до плоскости были < 0,
// то значит параллепипед невидим, возвращаем false
if (j == 8)
return false;
}

// все тесты прошли успешно, возвращаем true
return true;
}

Куча разных полезностей

Изходя из описанной выше концепции (как говорил мой лектор по матану) «легко видеть», что quad-деревья предоставляют нам не только способ быстрого рендеринга больших открытых пространств, но и еще кучу разных полезностей.

Во-первых, это трассировка лучей. При трассировке лучей, чаще всего мы должны определить пересекается ли прямая или отрезок с каким-нибудь шальным полигоном. Проверять пересечение прямой с каждым треугольником из которых состоит наша земля безполезно, потому что на это уйдет уйма дорогого процессорного времени, поэтому пользуемся опять quad-деревом. Опять рекурсивно обходим дерево и смотри пересекается ли данный луч с узлом дерева, если да, то идем дальше к потомкам, если нет, то здесь ловить больше нечего.

Во-вторых, терраморфинг в реальном времени. Однажды построив quad-дерево для ландшафта, ты можешь делать с ним все, что угодно, т.е. поднимать и опускать вершины как тебе вздумается, реализуя различные интересные эффекты: воронки от взрывов,
землетрясение, волны на воде (смотрится потрясно).

И в-третьих, тебе не придется ломать голову над тем, какой объект в игровом мире сейчас видим, а какой нет. Просто все объекты заранее привязываются к соответствующим вершинам quad-дерева и рисуются только, если данная вершина пройдет тест на видимость.

И напоследок, хочу сказать пару слов об использовании quad-деревьев при реализации динамического LOD’а (LOD — Level Of Detail, уровень детализации), который служит для того, чтобы уменьшить детализацию (количество полигонов) участков ландшафта, расположенных далеко от точки наблюдения. Делается это очень просто: для всех вершин quad-дерева задается несколько уровней детализации, и потом, когда придет время рисовать участок земли связанный с заданной вершиной мы выберем тот уровень детализации, который нам больше всего для данного случая подходит.

На сегодня это все. Доzzzвидания!

Оставить мнение

Check Also

Ручная распаковка. Вскрываем кастомный пакер на примере вымогателя GlobeImposter 2.0

При реверсе вирусов зачастую обнаруживается, что малварь накрыта какой-нибудь «навесной» з…