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

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

Изменено: 26.02.2007

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

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

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





Страницы: 1 2

Теперь рассмотрим класс COCTREE, который выглядит следующим образом:

class COCTREE
{
private:
    COCTREE *poChildOctree[8];         // 8 потомков
    BBOX bbNodeBox ;                   // Бокс данного узла
    vector<Object> vObjects ;          // Массив объектов на каждый узел
    void SetChildBox(BBOX *nodes);     // Создаем потомков и расставляем их по местам
    LPDIRECT3DVERTEXBUFFER9 VBOctree;  // VB для бокса
    void CreateVBForBox();             // Создаем и заполняем вершинный буфер для бокса
    void Release();                    // Освобождаем
    void RenderingObjects();           // Рисуем объекты листа
    void RenderingBoxWire();           // Рисуем бокс узла
public:
    // Создаем октри
    bool CreateOctree(vector<Object> &BBObjectArray, const BBOX &nodesize, int maxObjectInNode);
    COCTREE();                         // Конструктор
    ~COCTREE();                        // Деструктор
    void DrawObjects(FRUSTUM *fr);     // Направляем на RenderingObjects() все видимые камере листья
    void DrawBoxWire();                // Направляем на RenderingBoxWire() все существующие узлы
};
              
// Конструктор - обнуляем указатели на дочерние узлы и указатель на вершинный буфер
COCTREE::COCTREE()
{
    for (int i=0; i<8; i++) poChildOctree[i] = NULL; // создаем 8 потомков для узла
    VBOctree = NULL;
}

// Деструктор - вызываем функцию очистки памяти (описана далее)
COCTREE::~COCTREE()
{
    COCTREE::Release();                 //освобождаем ресурсы
}

bool COCTREE::CreateOctree(vector<Object> &BBObjectArray,   // Ссылка на vector объектов
                           const BBOX &nodesize,            // Размер узла
                           int maxObjectInNode)             // Лимит объектов на лист
{
    bbNodeBox = nodesize;                        // Объем узла
    CreateVBForBox();                            // Создаем вершинный буфер для узла
    int ObjectCount = (int)BBObjectArray.size(); //количество объектов
    // ЕСЛИ кол-во объектов в узле меньше допустимого, то заполняем vector ссылками на эти объекты
    if (ObjectCount <= maxObjectInNode)
    {
        for (int i=0; i<ObjectCount; i++)
        {
            vObjects.push_back(BBObjectArray[i]);
        }
        return true;
    }
    // Если функция все еще выполняется, то return true не было, а значит 
    // кол-во объектов в массиве превышает допустимое на лист => создаем дочерние узлы

    BBOX bbchildnodes[8];            // 8 боксов для дочерних узлов
    SetChildBox(bbchildnodes);       // Расставляем боксы доч. узлов по местам
    vector<Object> bbchildarray[8];  // 8 массивов с объектами для доч. узлов

    // Проходим по всем объектам (объем каждого объекта по всем дочерним узлам)
    for (int i=0; i<ObjectCount; i++)
    {
        for (int j=0; j<8; j++)
        {
            // Если объект попадает в один из дочерних боксов, то заносим его в вектор объектов дочернего узла
            if ( bbchildnodes[j].PointInBox(&BBObjectArray[i].pos)==true )
            {
                bbchildarray[j].push_back(BBObjectArray[i]);
            }
        }
    }

    // Распределяем объекты по дочерним узлам
    for (int i=0; i<8; i++)
    {
        // Если один из дочерних массивов объектов не пуст то создаем узел
        if (bbchildarray[i].size() != 0)
        {
            poChildOctree[i] = new COCTREE;
            if (poChildOctree[i] == NULL)
                return false; // Если не выделилась память -> false
            if (!poChildOctree[i]->CreateOctree(bbchildarray[i], bbchildnodes[i], maxObjectInNode)) 
                return false; // Если не построился узел -> false
        }
    }
    return true;
}

Функция CreateOctree() создает узел дерева. Рассмотрим ее поэтапно. Получает она ссылку на массив объектов, размер игрового мира, максимальное количество объектов на лист (повторю, что мы можем передавать ей вместо массива объектов - массив полигонов, а вместо максимального числа объектов – максимальное число полигонов на лист).

В ObjectCount записываем число объектов в массиве. Далее, если число объектов в массиве меньше допустимого, то записываем все объекты в данный узел; возвращаем true. Если число объектов в массиве больше допустимого, то необходимо разбить данный узел на восемь и создавать каждый из них рекурсивно этой же функцией. При этом, если в какой-либо из боксов дочерних узлов не попадает ни один объект, то этот узел мы не создаем.

// Расстановка дочерних боксов
void COCTREE::SetChildBox(BBOX *nodes)
{
    D3DXVECTOR3 center = bbNodeBox.calcCenter();       // Центр узла
    // Вычисляем место положение всех дочерних узлов
    // Верхний левый, ближний;
    nodes[0].min = D3DXVECTOR3(bbNodeBox.min.x, center.y, bbNodeBox.min.z);
    nodes[0].max = D3DXVECTOR3(center.x, bbNodeBox.max.y, center.z);
    // Верхний правый, ближний;
    nodes[1].min = D3DXVECTOR3(center.x, center.y, bbNodeBox.min.z);
    nodes[1].max = D3DXVECTOR3(bbNodeBox.max.x,	bbNodeBox.max.y,center.z);
    // Нижний левый, ближний;
    nodes[2].min = D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.min.z);
    nodes[2].max = D3DXVECTOR3(center.x, center.y, center.z);
    // Нижний правый, ближний;
    nodes[3].min = D3DXVECTOR3(center.x, bbNodeBox.min.y, bbNodeBox.min.z);
    nodes[3].max = D3DXVECTOR3(bbNodeBox.max.x, center.y, center.z);
    // Верхний левый, дальний;
    nodes[4].min = D3DXVECTOR3(bbNodeBox.min.x, center.y, center.z);
    nodes[4].max = D3DXVECTOR3(center.x, bbNodeBox.max.y, bbNodeBox.max.z);
    // Верхний правый, дальний;
    nodes[5].min = D3DXVECTOR3(center.x, center.y, center.z);
    nodes[5].max = D3DXVECTOR3(bbNodeBox.max.x,bbNodeBox.max.y, bbNodeBox.max.z);
    // Нижний левый, дальний;
    nodes[6].min = D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, center.z);
    nodes[6].max = D3DXVECTOR3(center.x, center.y, bbNodeBox.max.z);
    // Нижний правый, дальний;
    nodes[7].min = D3DXVECTOR3(center.x, bbNodeBox.min.y, center.z);
    nodes[7].max = D3DXVECTOR3(bbNodeBox.max.x, center.y, bbNodeBox.max.z);
}

В функции SetChildBox() мы просто корректируем координаты дочерних боксов узлов в зависимости от координат данного узла.

void COCTREE::DrawBoxWire()
{
    for (int i=0; i<8; i++)                   // Проверяем все узлы
    {
        if (poChildOctree[i] != NULL)         // Если дочерний узел существует, то рисуем его ребра
        {
            poChildOctree[i]->DrawBoxWire();
        }
    }
    COCTREE::RenderingBoxWire();
}

Функция DrawBoxWire() вызывает функцию RenderingBoxWire() для всех существующих узлов.

void COCTREE::DrawObjects(FRUSTUM *fr)
{
    bool bInFrustum = fr->BBoxInFrustum(&bbNodeBox);
    if (bInFrustum)
    {
        for (int i=0; i<8; i++)                      // Проверяем все узлы
        {
            if (poChildOctree[i] != NULL)
            {
                poChildOctree[i]->DrawObjects(fr);
            }
        }
    }
    if ( bInFrustum==true && vObjects.size()!=0 ) COCTREE::RenderingObjects();
}

Функция DrawObjects() вызывает функцию RenderingObjects() для всех видимых в данный момент камере листов.

void COCTREE::RenderingObjects()
{
    D3DXMATRIX World;
    extern int NumDrawObject;
    int count = vObjects.size();
    for (int i=0; i<count; i++)
    {
        D3DXMatrixTranslation(&World, vObjects[i].pos.x, vObjects[i].pos.y, vObjects[i].pos.z);
        D3DDevice->SetTransform(D3DTS_WORLD, &World);
        vObjects[i].pMesh->DrawSubset(0);
        NumDrawObject++;
    }
}

Функция RenderingObjects() рисует все объекты, хранящиеся в массиве данного листа. Но, так как мы вызываем ее только для листов, видимых камере, то ничего лишнего мы не рисуем.

void COCTREE::CreateVBForBox()
{
    D3DDevice->CreateVertexBuffer(19*sizeof(LineVertex), D3DUSAGE_WRITEONLY, OCTREE_FVF, 
                                                                    D3DPOOL_MANAGED, &VBOctree, NULL);
    LineVertex v[] =
    {
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.min.z),0x11ffdd, },
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.min.z),0x40f0dd, },
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),0x607fdd, }, 
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.min.z),0x60ff5d, },
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.min.z),0x80f4dd, }, 
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.max.z),0xaaefdd, }, 
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.max.z),0x00eedd, }, 
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.min.z),0xe0ffdd, },
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),0x060fdd, }, 
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),0x00ffdd, },
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),0x00ffdd, }, 
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.max.z),0x32ffdd, },
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.max.z),0x07ff4d, }, 
        { D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.max.z),0x44ffdd, },
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.max.z),0x555fdd, }, 
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.min.z),0x20afdd, }, 
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),0x20ff7d, }, 
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.max.z),0x10f5dd, },
        { D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.max.z),0x10ffdd, },
    };
    
    void * pBuf;
    VBOctree->Lock( 0, 19 * sizeof(LineVertex), &pBuf, 0 );
    memcpy( pBuf, v, 19 * sizeof(LineVertex));
    VBOctree->Unlock();
}

Функция CreateVBForBox() просто создает вершинный буфер для узла. Координаты известны, цвет берем такой, какой больше нравится.

void COCTREE::RenderingBoxWire()
{
    D3DXMATRIX MATRIX_WORLD;
    D3DXMatrixTranslation(&MATRIX_WORLD, 0.0f, 0.0f, 0.0f);
    D3DDevice -> SetTransform(D3DTS_WORLD,&MATRIX_WORLD);
    D3DDevice -> SetTexture(0, NULL);
    D3DDevice -> SetStreamSource(0, VBOctree, 0, sizeof(LineVertex) );
    D3DDevice -> SetFVF(OCTREE_FVF );
    D3DDevice -> DrawPrimitive(D3DPT_LINESTRIP, 0, 18);
}

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

void COCTREE::Release()
{
    for (int i=0; i<8; i++)
    {
        if (poChildOctree[i] != NULL)
        {
            poChildOctree[i]->Release();
            delete (poChildOctree[i]);
            poChildOctree[i] = NULL;
        }
    }
    vObjects.clear();
    if (VBOctree != NULL) VBOctree=NULL;
}

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

  • Во-первых, если положение объектов не имеет принципиального значения, то их можно несколько смещать.
  • Во-вторых, мы можем привязывать объект только одному листу путем удаления уже принадлежащих к какому-либо листу объектов из общего массива.
  • В-третьих, можно привязывать объект только к одному листу изменив нашу функцию определения попадания точки в куб (с >= и <= на > и < соответственно), но тогда объект лежащий точно на ребре просто не будет рисоваться.
  • И, наконец, наиболее грамотный вариант – запоминать уже отрисованные объекты в массиве. Таким образом, объект будет рисоваться при попадании бокса одного из листьев, содержащих объект, в пирамиду видимости, но рисоваться только один раз.

Объектов в сцене Размер корня (игрового мира) Макс. кол-во объектов в листе FPS при min кол-ве объектов (0) FPS при max кол-ве объектов
10 000 500 1 19 13
10 000 500 5 55 18
10 000 500 10 66 18
10 000 500 20 111 19
10 000 500 100 300 20
10 000 2 000 1 18 13
10 000 2 000 5 53 17
10 000 2 000 10 68 18
1 000 300 1 160 105
1 000 300 5 270 115
1 000 300 10 350 124
Таблица со сравнительными результатами производительности при различных параметрах Octree

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

Чтобы использовать Octree в своем приложении нужно всего лишь изменить ID3DXMesh в структуре Object на ваш тип объектов (если таковой имеется); изменить размер Octree на размер вашего игрового мира и, создав объекты типа COCTREE и FRUSTUM, вызвать пару функций.

COCTREE Octree;
vector<Object> Objects;
FRUSTUM Frustum;

На этапе инициализации:

Инициализировать_объекты();
Octree.CreateOctree(Objects, БОКС_ОГРАНИЧИВАЮЩИЙ_МИР, ЧИСЛО_ОБЪЕКТОВ_НА_ЛИСТ);

В функции отрисовки:

Frustum.RefreshFrustum();
Octree.DrawObjects(&Frustum);
D3DDevice -> SetRenderState(D3DRS_LIGHTING, false);
Octree.RenderBoxWire();	                            //для рисования ребер узлов рекоменд. выкл. освещение
D3DDevice -> SetRenderState(D3DRS_LIGHTING, true);

В функции удаления:

Octree.~COCTREE(); 
Удалить_массив_объектов();

Вот и все!
Надеюсь, у вас все получится!

 
   Скачать исходный код к статье
 

 

Страницы: 1 2