Бесплатная реклама

Автор: Артем Мерец «Scart»

Опубликовано: 26.02.2007

Изменено: 26.02.2007

Постоянная ссылка

Комментарии [5]

Алгоритм Octree - теория и практика на DirectX


Рассматривается популярный метод сортировки - октарное дерево (Octree) для оптимизации скорости работы вашего 3D приложения. Приведен пример практической реализации на DirectX API, который легко можно подключить к вашему проекту.



Страницы: 1 2

От автора

Что побудило меня написать эту статью? То, что на русском языке информации об Octree довольно мало, тем более практической, с примерами реализации под API (в данном случае - DirectX), хотя эта технология очень часто ипользуется для оптимизации в трехмерных приложениях, особенно в играх.

Введение

Например мы загрузили в приложение наш меш. Он красиво отображается, крутиться по трем осям, но чего-то не хватает. Мы подгружаем еще десяток объектов - куда лучше, но пока что-то не то. Теперь мы грузим целый виртуальный мир – выглядет отлично, то, что нужно, но ... наше приложение с трудом показывает 2 кадра в секунду!

В чем же дело? А дело в том, что мы слишком много данных отправляем на отрисовку видео карте - данных, которые и рисоваться не должны - их просто не видно виртуальной камере. Что делать? Тут на помощь приходят методы сортировки. В частности деревья. Мы с вами будем рассматривать один из случаев деревьев - октарное дерево.

Игровая сцена octree из 10 000 объектов
Рис. 1. Пример реализации Octree на игровой сцене, состоящей из 10 000 объектов

Октарное Дерево (Octree). Теория

Итак, как мы добьемся того, что будем рисовать только видимые объекты? Все очень просто. На этапе инициализации мы вписываем игровой мир в куб, делим получившийся бокс надвое по каждой оси (X,Y,Z), таким образом, получается, что мир разбит на восемь кубов (отсюда и название Octree – восьмеричное дерево).

Далее эти восемь кубов делятся еще на восемь, те еще на восемь и так далее. Останавливать процесс деления мы можем по разным причинам. Можно делить до тех пор, пока в каждом боксе не будет определенного количества полигонов, или объектов, или пока бокс не достигнет нужных нам объемов (ширины, высоты, длины), а можно совместить эти и какие-либо другие условия для создания одного - комплексного.

Самый большой бокс - исходный (обычно размером с игровой мир) называется корень (root). Все боксы дерева, в том числе и корень – это узлы (node). Узлы, находящиеся в самом низу дерева, хранящие объекты - листья.

Ребра корня и восьми дочерних узлов Octree
Рис. 2. На рисунке видны ребра корня и восьми дочерних узлов Octree

Схематичное изображение дерева octree тройной глубины
Рис. 3. Схематичное изображение дерева тройной глубины. Красные – узлы,
содержащие по восемь дочерних узлов; зеленые – узлы, в объемах (боксах)
которых нет объектов; синие – узлы, которые хранят в себе объекты, то есть листья

Также тесно связана с восьмеричным деревом и пирамида видимости (viewing frustum). Она представляет из себя усеченную пирамиду, основания которой – это ближняя и дальняя плоскости отсечения, а боковые грани – плоскости, определяющиеся в зависимости от матрицы проекции (projection) и матрицы вида (view) камеры.

Пирамида видимости (viewing frustum)
Рис. 4. Пирамида видимости

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

Пирамида видимости (viewing frustum)
Рис. 5. Сейчас видны только 5 узлов, причем из них только два являются листьями.
Нам не нужно рисовать объекты всех листьев, рисуются объекты только этих 2-х
(так как другие видимые узлы объектов не содержат, а другие листья камере не видны)

Реализация Octree

Что нам нужно для реализации Octree? Для начала давайте разберем весь алгоритм построения. Мы задаем размеры игрового мира и массив объектов (под объектом понимается структура, которая содержит ограничивающий тело объем и ссылку на тело, где телом может быть как полигон, так и меш).

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

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

Следует помнить, что выигрыш в быстродействии при использовании Octree зависит от трех основных параметров: 1)размера мира; 2)общего количества объектов и 3)количества объектов на один лист.

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

Если максимальное количество объектов на лист будет слишком большим (при этом узел будет большим по объему), то мы, даже в случае частичного попадания листа в пирамиду видимости, будем рисовать все объекты, которые за данным листом закреплены. Этот подход больше подходит для малополигональных объектов.

Обратите внимание: в конце статьи расположена небольшая таблица со сравнительными результатами производительности при различных параметрах, вы можете опираться на нее при выборе параметров для своего приложения.

Теперь рассмотрим простейшую реализацию восьмеричного дерева.

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

Итак, теперь можно приступать к созданию класса. Первым делом подготовим несколько структур:

#define OCTREE_FVF (D3DFVF_XYZ|D3DFVF_DIFFUSE)
struct LineVertex
{
     D3DXVECTOR3 pos;
     DWORD col;
};

Структура LineVertex и макрос OCTREE_FVF определяют формат вершин для отрисовки контуров нашего дерева (отрисовка контуров будет использоваться только разработчиками для отладки, так как в готовом приложении у нас не будет необходимости рисовать его ребра).

struct BBOX
{
     BBOX(){}
     BBOX(D3DXVECTOR3 _min, D3DXVECTOR3 _max) {min = _min; max = _max;}
     D3DXVECTOR3 min;
     D3DXVECTOR3 max;
     D3DXVECTOR3 CalcCenter()
     {
          float tmpx = (max.x-min.x)/2.0f;
          float tmpy = (max.y-min.y)/2.0f;
          float tmpz = (max.z-min.z)/2.0f;
          return D3DXVECTOR3(min.x+tmpx,min.y+tmpy,min.z+tmpz);
     }
     bool PointInBox(D3DXVECTOR3 *pos)
     {
          if (min.x <= pos->x && max.x >= pos->x)
          {
               if (min.z <= pos->z && max.z >= pos->z)
               {
                    if (min.y <= pos->y && max.y >= pos->y)
                    {
                         return true;
                    }
                    else
                    {
                         return false;
                    }
               }
          }
     return false;
     }
};

Структура BBOX описывает объемный куб. В такие кубы мы будем заключать узлы дерева. min и max хранят позиции, ограничивающие бокс; CalcCenter() – вычисляет центр бокса; PointInBox() – определяет пересечение бокса с ограничивающим тело объемом, в данном случае бокса с точкой (мы будем считать объекты материальными точками, поэтому и проверять будем находится точка-объект в боксе или нет).

struct Object
{
     ID3DXMesh* pMesh;
     D3DXVECTOR3 pos;
};

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

struct FrustumPlane
{ D3DXVECTOR3 normal; float distance; inline void Normalize() { float tmp =1/sqrtf((normal.x*normal.x)+normal.y*normal.y) + (normal.z*normal.z); normal.x = normal.x * tmp; normal.y = normal.y * tmp; normal.z = normal.z * tmp; distance = distance * tmp; } inline float DistanceToPoint(D3DXVECTOR3 *pnt) { return D3DXVec3Dot(&normal, pnt) + distance; } };

Структура FrustumPlane описывает плоскость, как видно, плоскости у нас будут использоваться для пирамиды видимости. Normalize() – нормализует вектор, обозначающий нормаль плоскости (для тех, кто не знает, плоскость в пространстве можно представлять нормалью и расстоянием от этой плоскости до определенной токи, как правило до начала координат). DistanceToPoint() определяет расстояние от плоскости до точки pnt.

struct FRUSTUM
{
    FrustumPlane frustumPlanes[6];	//6 плоскостей фрустума
    bool BBoxInFrustum(BBOX *box)
    {
        D3DXVECTOR3 min = box->min, max = box->max;
        int p;
        for ( p = 0; p < 6; p++ )
        {
            if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(min.y) +
                        frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
            if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(min.y) +
                        frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
            if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(max.y) +
                        frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
            if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(max.y) +
                        frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
            if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(min.y) +
                        frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
            if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(min.y) +
                        frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
            if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(max.y) +
                        frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
            if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(max.y) +
                        frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
            return false;
        }
        return true;
    }

    void RefreshFrustum()
    {
        D3DXMATRIX Matrix, _invViewMatrix, MatrixView, MatrixProjection;
        D3DDevice->GetTransform(D3DTS_PROJECTION, &MatrixProjection);
        D3DDevice->GetTransform(D3DTS_VIEW, &MatrixView);
        D3DXMatrixInverse(&_invViewMatrix, 0, &MatrixView);
        D3DXMATRIXA16 matComb;
        D3DXMatrixMultiply(&matComb, &MatrixView, &MatrixProjection);

        frustumPlanes[0].normal.x = matComb._14 + matComb._11;
        frustumPlanes[0].normal.y = matComb._24 + matComb._21;
        frustumPlanes[0].normal.z = matComb._34 + matComb._31;
        frustumPlanes[0].distance = matComb._44 + matComb._41;
        frustumPlanes[1].normal.x = matComb._14 - matComb._11;
        frustumPlanes[1].normal.y = matComb._24 - matComb._21;
        frustumPlanes[1].normal.z = matComb._34 - matComb._31;
        frustumPlanes[1].distance = matComb._44 - matComb._41;
        frustumPlanes[2].normal.x = matComb._14 - matComb._12;
        frustumPlanes[2].normal.y = matComb._24 - matComb._22;
        frustumPlanes[2].normal.z = matComb._34 - matComb._32;
        frustumPlanes[2].distance = matComb._44 - matComb._42;
        frustumPlanes[3].normal.x = matComb._14 + matComb._12;
        frustumPlanes[3].normal.y = matComb._24 + matComb._22;
        frustumPlanes[3].normal.z = matComb._34 + matComb._32;
        frustumPlanes[3].distance = matComb._44 + matComb._42;
        frustumPlanes[4].normal.x = matComb._13;
        frustumPlanes[4].normal.y = matComb._23;
        frustumPlanes[4].normal.z = matComb._33;
        frustumPlanes[4].distance = matComb._43;
        frustumPlanes[5].normal.x = matComb._14 - matComb._13;
        frustumPlanes[5].normal.y = matComb._24 - matComb._23;
        frustumPlanes[5].normal.z = matComb._34 - matComb._33;
        frustumPlanes[5].distance = matComb._44 - matComb._43;
    }
};

Структура FRUSTUM описывает нашу пирамиду видимости. frustumPlanes[6] – шесть плоскостей, ограничивающих пирамиду видимости (верхняя, нижняя, левая, правая, передняя, дальняя). BoxInFrustum() – определяет находится ли бокс box в пирамиде видимости, другими словами – виден ли бокс камере (способ нахождения очень прост – мы просто проверяем все ли точки бокса расположены с внешней стороны от плоскостей пирамиды, то есть за ее пределами - не внутри). RefreshFrustum() – функция обновляет (необходимо вызывать каждый кадр) нашу пирамиду видимости, данные берутся из матриц вида и проекции. Для более удобной интеграции FRUSTUM это отдельная структура, однако ее можно переместить в класс вашей камеры.

Страницы: 1 2