Array ( )
Вход:




Главная | OpenGL | GLSL | AI | Сеть | Примеры | Библиотека

OpenGL: Octree






Подразумевается, что вы уже прочитали и поняли уроки камеры и Frustum culling.
Если нет, лучше обратитесь к ним, чтобы понять дальнейший материал.

Этот урок демонстрирует, как создать и отрисовать octree. Что же такое этот самый octree?
Это некое дерево узлов, хранящее информацию о сцене/уровне/мире. Его смысл в разделении
пространства. У вас будет возможность проверить, куда направлена камера, и отрисовывать только
то, что нужно. Если у вас большой мир, вы не захотите передавать OpenGL для проверки все
его вершины каждый кадр, верно? Проверка сотен тысяч вершин приведут к жуткому падению
FPS. Чтобы решить эту проблему, нужно поделить имеющееся пространство на узлы, затем проверить
каждый из этих узлов, смотрим ли мы на него. Если да - нужно отрисовать узел, иначе -
проигнорировать. Прелесть Octree и в том, что вы сами можете указать, сколько вершин/обьектов
должно находится в каждом узле. Также убедитесь, что используете массивы вершин для ускорения
рендера. Этим вы сбережёте уйму процессорного времени, избежав вызовов glVertex*() тысячи
раз за кадр.


Узел в octree - это простой куб, внутри которого находится определённое количество вершин.
Если этот куб пересекается с нашей пирамидой взгляда, то рендерим вершины внутри этого куба.
Если же куб имеет дочерние узлы, находящиеся внутри него, то он не содержит вершин. Вершины
содержат либо его дочерние узлы, либо в свою очередь их дочерние узлы, и т.д. Эта рекурсия
может продолжатся сколько угодно, пока мы не достигнем максимального значения рекурсии, либо
число треугольников не станет меньше макс. числа треугольников для каждого узла. Достигнув
этих значений, нода (узел) прекращает деление. Теперь вы видите, что этот способ намного
быстрее, чем проверка каждой вершины/треугольника на нахождение в пирамиде взгляда.

Максимальное число треугольников в узле может зависеть от размера вашей сцены. Если сделать
его слишком маленьким, программа может тормозить, т.к. у вас будут тысячи узлов. Оптимально
начинать с 1000 или около того, а затем изменять значение, пока не найдётся лучший вариант.
Но поскольку наш урок "Карта высот" не содержит очень уж много треугольников, я решил выставить
значение 100, чтобы получить больше делений.

Этот урок - лишь первый из трёх уроков об Octree. В этом уроке мы пока ещё не будем делать
frustum culling, а лишь закрепим понятие Octree.

В этом уроке в качестве карты высот мы загрузим простой текстовый файл с вершинами. Я выбрал
этот способ, чтобы не усложнять урок. Файл .raw был создан простой загрузкой файла .3ds нашим
кодом из урока "загрузка 3DS", но вместо вызова glVertex3f() я сделал вызов fprintf(), чтобы
записать вершины в файл.


Итак, сперва напишем новый хидер для двух новых классов: CDebug и COctree.
Новый хидер, Octree.h:
#ifndef _OCTREE_H
#define _OCTREE_H

#include "Main.h"
#include <vector>
using namespace std;


// Максимальное число треугольников в ноде
extern int g_MaxTriangles;

// Макс. число делений (уровеней деления)
extern int g_MaxSubdivisions;

// Число нод в дереве
extern int g_EndNodeCount;

// Включение/выклчюение освещения
extern bool g_bLighting;

// Переменная определяет, рендерим ли нам линии или полигоны
extern bool g_bRenderMode;


// Эти значения (0-7) хранят ID индексов массива нод (m_pOctreeNodes)
enum eOctreeNodes
{
    TOP_LEFT_FRONT,         // 0
    TOP_LEFT_BACK,          // 1
    TOP_RIGHT_BACK,         // и т.д...
    TOP_RIGHT_FRONT,
    BOTTOM_LEFT_FRONT,
    BOTTOM_LEFT_BACK,
    BOTTOM_RIGHT_BACK,
    BOTTOM_RIGHT_FRONT
};

// Линии для отладки, с их помощью мы будем видеть наше дерево
class CDebug
{

public:

    // Добавляет линию в наш список
    void AddDebugLine(CVector3 vPoint1, CVector3 vPoint2);

    // Добавляет в список прямоугольних с переланным центром, шириной, высотой и глубиной
    void AddDebugRectangle(CVector3 vCenter, float width, float height, float depth);

    // Рендерит все линии
    void RenderDebugLines();

    // This clears all of the debug lines
    // Очищает все отладочные линии
    void Clear();

private:

    // Это STL список наших линий
    vector<CVector3> m_vLines;
};


// Это наш класс Octree
class COctree
{

public:

    // Конструктор и деструктор
    COctree();
    ~COctree();

    // Возвращает центр текущей ноды
    CVector3 GetCenter() {   return m_vCenter;  }

    // Возвращает число треугольников в этой ноде
    int GetTriangleCount()  {   return m_TriangleCount; }

    // Возвращает ширину этой ноды (т.к. это куб, ширина, высота и глубина равны)
    float GetWidth() {   return m_Width;    }

    // Определяет, имеет ли эта нода под-ноды, разделена ли она.
    bool IsSubDivided()  {   return m_bSubDivided;  }

    // Устанавливает начальные ширину, высоту и глубину для всей сцены.
    void GetSceneDimensions(CVector3 *pVertices, int numberOfVerts);

    // Принимает центр, ширину и ID предыдущей ноды, которая будет разделена
    CVector3 GetNewNodeCenter(CVector3 vCenter, float width, int nodeID);

    // Делит ноду в зависимости от того, сколько в ней треугольников, и её ширины
    void CreateNode(CVector3 *pVertices, int numberOfVerts, CVector3 vCenter, float width);

    // создает новую разделенную ноду
    void CreateNewNode(CVector3 *pVertices, vector<bool> pList, int numberOfVerts,
                       CVector3 vCenter,    float width,        int triangleCount, int nodeID);

    // Закончив деление, нужно привязать вершины к конечной ноде.
    void AssignVerticesToNode(CVector3 *pVertices, int numberOfVerts);

    // Функция проходит через все ноды и рисует вершины ноды.
    // Должна вызыватся начиная с корневой ноды.
    void DrawOctree(COctree *pNode);

    // Освобождает память, занятую под данные Octree.
    void DestroyOctree();

private:

    // Инициализирует данные
    void InitOctree();

    // Говорит нам, разделена ли нода на под-ноды
    bool m_bSubDivided;

    // Размер куба текущей ноды
    float m_Width;

    // Число треугольников в этой ноде.
    int m_TriangleCount;

    // Центр (X, Y, Z) этой ноды
    CVector3 m_vCenter;

    // Треугольники, находящиеся в этой ноде
    CVector3 *m_pVertices;

    // Это 8 последующих нод, происходящие из этой.
    COctree *m_pOctreeNodes[8];
};


// Возвращает cross product между 2 векторами
CVector3 Cross(CVector3 vVector1, CVector3 vVector2);

// Возвращает величину вектора
float Magnitude(CVector3 vNormal);

// Возвращает нормализованный вектор
CVector3 Normalize(CVector3 vVector);


#endif



Следующий файл содержит весь код классов Octree и Debug. Каждый раз при создании ноды в список точек
добавляется новый куб. Хотя в этом уроке изначально куб будет только один, вы сможете изменять их число нажатием
'+' и '-', что увеличит или уменьшит число нод в дереве.

Файл Octree.cpp:
// Хидер нужных классов
#include "Octree.h"

// Наш экземпляр класса Debug
extern CDebug g_Debug;

// Текущее число делений.
// Используется, чтобы не превысить макс. число
int g_CurrentSubdivision = 0;

///////////////////////////////// RENDER DEBUG LINES \\\\\\\\\\\\\\\\*
/////
/////   Проходит через все линии в списке и рисует их
/////
///////////////////////////////// RENDER DEBUG LINES \\\\\\\\\\\\\\\\*

void CDebug::RenderDebugLines()
{
    glDisable(GL_LIGHTING);     // Выключаем свет, чтобы все линии были ярко-желтыми

    glBegin(GL_LINES);      // Начинаем рендерить линии

        glColor3ub(255, 255, 0);    // Устанавливаем цвет в желтый

        // Проходим через список линий, хранящийся в vector m_vLines
        for(unsigned int i = 0; i < m_vLines.size(); i++)
        {
            // Передаём текущую точку для рендера как часть линии
            glVertex3f(m_vLines[i].x, m_vLines[i].y, m_vLines[i].z);
        }

    glEnd();            // Заканчиваем рендерить линии

    // Если глобальное освещение включено в сцене, включаем его после отрисовки линий.
    if(g_bLighting)
        glEnable(GL_LIGHTING);
}

///////////////////////////////// ADD DEBUG LINE \\\\\\\\\\\\\\\\*
/////
/////   Добавляет отладочную линию в стек
/////
///////////////////////////////// ADD DEBUG LINE \\\\\\\\\\\\\\\\*

void CDebug::AddDebugLine(CVector3 vPoint1, CVector3 vPoint2)
{
    // Добавляет 2 точки, составляющие очередную линию, в список.
    m_vLines.push_back(vPoint1);
    m_vLines.push_back(vPoint2);
}


///////////////////////////////// ADD DEBUG RECTANGLE \\\\\\\\\\\\\\\\*
/////
/////   Добавляет отладочный прямоугольник в стек линий
/////
///////////////////////////////// ADD DEBUG RECTANGLE \\\\\\\\\\\\\\\\*

void CDebug::AddDebugRectangle(CVector3 vCenter, float width, float height, float depth)
{
    // Чтобы оптимизировать свой код, разделим размеры куба на 2.
    // Таким образом мы сможем создавать куб из центра наружу.
    width /= 2.0f;  height /= 2.0f; depth /= 2.0f;

    // Создаём все 8 точек.
    CVector3 vTopLeftFront( vCenter.x - width, vCenter.y + height, vCenter.z + depth);
    CVector3 vTopLeftBack(  vCenter.x - width, vCenter.y + height, vCenter.z - depth);
    CVector3 vTopRightBack( vCenter.x + width, vCenter.y + height, vCenter.z - depth);
    CVector3 vTopRightFront(vCenter.x + width, vCenter.y + height, vCenter.z + depth);

    CVector3 vBottom_LeftFront( vCenter.x - width, vCenter.y - height, vCenter.z + depth);
    CVector3 vBottom_LeftBack(  vCenter.x - width, vCenter.y - height, vCenter.z - depth);
    CVector3 vBottomRightBack( vCenter.x + width, vCenter.y - height, vCenter.z - depth);
    CVector3 vBottomRightFront(vCenter.x + width, vCenter.y - height, vCenter.z + depth);

    ////////// ВЕРХНИЕ ЛИНИИ //////////

    m_vLines.push_back(vTopLeftFront);      m_vLines.push_back(vTopRightFront);

    m_vLines.push_back(vTopLeftBack);       m_vLines.push_back(vTopRightBack);

    m_vLines.push_back(vTopLeftFront);      m_vLines.push_back(vTopLeftBack);

    m_vLines.push_back(vTopRightFront);     m_vLines.push_back(vTopRightBack);

    ////////// НИЖНИЕ ЛИНИИ //////////

    m_vLines.push_back(vBottom_LeftFront);  m_vLines.push_back(vBottomRightFront);

    m_vLines.push_back(vBottom_LeftBack);   m_vLines.push_back(vBottomRightBack);

    m_vLines.push_back(vBottom_LeftFront);  m_vLines.push_back(vBottom_LeftBack);

    m_vLines.push_back(vBottomRightFront);  m_vLines.push_back(vBottomRightBack);

    ////////// SIDE LINES //////////

    m_vLines.push_back(vTopLeftFront);      m_vLines.push_back(vBottom_LeftFront);

    m_vLines.push_back(vTopLeftBack);       m_vLines.push_back(vBottom_LeftBack);

    m_vLines.push_back(vTopRightBack);      m_vLines.push_back(vBottomRightBack);

    m_vLines.push_back(vTopRightFront);     m_vLines.push_back(vBottomRightFront);
}


///////////////////////////////// CLEAR \\\\\\\\\\\\\\\\*
/////
/////   Очищает все отладочные линии
/////
///////////////////////////////// CLEAR \\\\\\\\\\\\\\\\*

void CDebug::Clear()
{
    // Уничтожаем список с пом. функции clear()
    m_vLines.clear();
}


//-------------------------------------------------------------------------\


///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\*
/////
/////   Конструктор класса COctree
/////
///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\*

COctree::COctree()
{
    // Мы не помещаем код инициализации сюда, чтобы иметь возможность
    // уничтожить и инициализировать Octree без создания нового экземпляра.
    // То же самое и с деструктором.

    // Инициализируем данные
    InitOctree();
}


///////////////////////////////// ~OCTREE \\\\\\\\\\\\\\\\*
/////
/////   Деструктор COctree
/////
///////////////////////////////// ~OCTREE \\\\\\\\\\\\\\\\*

COctree::~COctree()
{
    // Вызываем очищающую функцию
    DestroyOctree();
}


///////////////////////////////// INIT OCTREE \\\\\\\\\\\\\\\\*
/////
/////   Инициализация данных дерева
/////
///////////////////////////////// INIT OCTREE \\\\\\\\\\\\\\\\*

void COctree::InitOctree()
{
    // Устанавливаем флаг деления в false
    m_bSubDivided = false;

    // Устанавливаем размеры куба в 0
    m_Width = 0;

    // Число треугольников
    m_TriangleCount = 0;

    // Устанавливаем центр куба в 0
    m_vCenter = CVector3(0, 0, 0);

    // Устанавливаем список треугольников в NULL
    m_pVertices = NULL;

    // Устанавливаем под-ноды в NULL
    memset(m_pOctreeNodes, 0, sizeof(m_pOctreeNodes));
}


///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\*
/////
/////   Устанавливает начальные размеры сцены и центральную точку
/////
///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\*

void COctree::GetSceneDimensions(CVector3 *pVertices, int numberOfVerts)
{
    // Передаём список вершин и их число, чтобы получить центральную точку и ширину всей
    // сцены. Эта информация будет нужна для деления Octree. В следующем уроке
    // жто будет не простой список вершин, а некая структура, хранящая информацию
    // о текстурах и нормалях.

    // Инициализируем временные переменные для хранения макс. значений
    float maxWidth = 0, maxHeight = 0, maxDepth = 0;

    // Завершаем работу, если переданы неверные данные
    if(!pVertices || numberOfVerts <= 0) return;

    // Рассчитываем центральную точку сцены. Всё, что для этого нужно сделать -
    // сложить ВСЕ вершины, затем разделить итоговое значение на их число.
    // То есть будут сложены все X с X, Y с Y, и т.д... То есть получится не одно
    // значение, а 3: totalX, totalY, totalZ.
    // Обратите внимание, мы складываем 2 вектора. Если вы помните класс CVector,
    // я перегрузил операторы сложения и вычитания для их корректной работы.

    // Проходим через все вершины и складываем их значения
    for(int i = 0; i < numberOfVerts; i++)
    {
        // Прибавляем текущую вершину к итоговой переменной.
        m_vCenter = m_vCenter + pVertices[i];
    }

    // Делим результат на число вершин, чтобы получить центр сцены.
    m_vCenter.x /= numberOfVerts;
    m_vCenter.y /= numberOfVerts;
    m_vCenter.z /= numberOfVerts;

    // Теперь, имея центральную точку, нужно найти точки с самым большим от неё расстоянием.
    // Это скажет нам, какими должны быть размеры корневой ноды. Получив точки с наибольшей высотой,
    // шириной и глубиной, мы проверим, какое из них наибольшее, и установим размер ребра куба.

    // Проходим через все вершины, чтобы найти наибольшее расстояние от центра.
    for(i = 0; i < numberOfVerts; i++)
    {
        // Получаем расстояние от текущей вершины. Используем функцию fabfs()
        // для получения модуля от float, так как значение может быть отрицательным.
        float currentWidth  = fabsf(pVertices[i].x - m_vCenter.x);
        float currentHeight = fabsf(pVertices[i].y - m_vCenter.y);
        float currentDepth  = fabsf(pVertices[i].z - m_vCenter.z);

        // Проверяем, больше ли текущее значение максимальной сохранённой ширины
        if(currentWidth  > maxWidth)    maxWidth  = currentWidth;

        // Проверяем, больше ли текущее значение максимальной сохранённой высоты
        if(currentHeight > maxHeight)   maxHeight = currentHeight;

        // Проверяем, больше ли текущее значение максимальной сохранённой глубины
        if(currentDepth > maxDepth)     maxDepth  = currentDepth;
    }

    // Устанавливаем значение переменной-члена класса в максимальное
    // найденное значение. Умножаем макс. значение на 2, т.к. расстояние от
    // центра - это только половина размера стороны куба.
    maxWidth *= 2;      maxHeight *= 2;     maxDepth *= 2;


    // Из трёх значений находим наибольшее, и устанавливаем в него
    // длинну ребра куба.
    if(maxWidth > maxHeight && maxWidth > maxDepth)
        m_Width = maxWidth;
    else if(maxHeight > maxWidth && maxHeight > maxDepth)
        m_Width = maxHeight;
    else
        m_Width = maxDepth;
}


///////////////////////////////// GET NEW NODE CENTER \\\\\\\\\\\\\\\\*
/////
/////   Возвращает центральную точку новой разделённой ноды, в зависимости от её ID
/////
///////////////////////////////// GET NEW NODE CENTER \\\\\\\\\\\\\\\\*

CVector3 COctree::GetNewNodeCenter(CVector3 vCenter, float width, int nodeID)
{
    // Функция принимает ID ноды, центр которой нужно найти. Найдя его, нужно
    // разделить ноду - найти центр для 8 новых нод.

    // Инициализируем новый центр ноды
    CVector3 vNodeCenter(0, 0, 0);

    // Создаём временную переменную, чтобы уменьшить обьем кода
    CVector3 vCtr = vCenter;

    // В зависимости от ID рассчитываем центр разделенной ноды
    switch(nodeID)
    {
        case TOP_LEFT_FRONT:
            vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y + width/4,
                vCtr.z + width/4);
            break;

        case TOP_LEFT_BACK:
            vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y + width/4,
                vCtr.z - width/4);
            break;

        case TOP_RIGHT_BACK:
            vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y + width/4,
                vCtr.z - width/4);
            break;

        case TOP_RIGHT_FRONT:
            vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y + width/4,
                vCtr.z + width/4);
            break;

        case BOTTOM_LEFT_FRONT:
            vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y - width/4,
                vCtr.z + width/4);
            break;

        case BOTTOM_LEFT_BACK:
            vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y - width/4,
                vCtr.z - width/4);
            break;

        case BOTTOM_RIGHT_BACK:
            vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y - width/4,
                vCtr.z - width/4);
            break;

        case BOTTOM_RIGHT_FRONT:
            vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y - width/4,
                vCtr.z + width/4);
            break;
    }

    // Return the new node center
    // Возвращаем центр новой ноды
    return vNodeCenter;
}


///////////////////////////////// CREATE NEW NODE \\\\\\\\\\\\\\\\*
/////
/////   This figures out the new node information and then passes it into CreateNode()
/////   Инициализирует данные новой ноды и передаёт их в CreateNode()
/////
///////////////////////////////// CREATE NEW NODE \\\\\\\\\\\\\\\\*

void COctree::CreateNewNode(CVector3 *pVertices, vector<bool> pList, int numberOfVerts,
    CVector3 vCenter,    float width,        int triangleCount, int nodeID)
{
    // Эта функция помогает нам установить данные новосозданной ноды. Создавать
    // новую ноду мы хотим только если в её зоне есть полигоны. Если их нет,
    // нода создаватся не должна.

    // Проверяем, нашлись ли треугольники внутри ноды
    if(triangleCount)
    {
        // Выделяем память для треугольниково в этой ноде (треуг. * 3 для вершин)
        CVector3 *pNodeVertices = new CVector3 [triangleCount * 3];

        // Создаем счетчик для индекса вершин в новой ноде
        int index = 0;

        // Проходим через все вершины и привязываем их к ноде
        for(int i = 0; i < numberOfVerts; i++)
        {
            // Если треугольник в ноде, привязываем его к ней
            if(pList[i / 3])
            {
                pNodeVertices[index] = pVertices[i];
                index++;
            }
        }

        // Ниже идет инициализация ноды. Сначала выделяем память под неё, затем
        // получаем её центральную точку. В зависимости от nodeIDm
        // GetNewNodeCenter() узнает, какую именно точку нужно вернуть
        // (TOP_LEFT_FRONT, и т.д...)

        // Создаем новую ноду
        m_pOctreeNodes[nodeID] = new COctree;

        // Получаем центр новой ноды
        CVector3 vNodeCenter = GetNewNodeCenter(vCenter, width, nodeID);

        // Теперь, прежде, чем продолжать рекурсию вниз или вверх по дереву,
        // нужно учесть уровень деления.

        // Увеличиваем текущий счетчик делений
        g_CurrentSubdivision++;

        // Рекурсируем через эту ноду и делим её, если нужно
        m_pOctreeNodes[nodeID]->CreateNode(pNodeVertices, triangleCount * 3,
                vNodeCenter, width / 2);

        // Уменьшаем счетчик делений
        g_CurrentSubdivision--;

        // Освобождаем память под вершины этой ноды
        delete [] pNodeVertices;
    }
}


///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\*
/////
/////   Это рекурсивная функция, проходящая через ноды и делящая их
/////
///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\*

void COctree::CreateNode(CVector3 *pVertices, int numberOfVerts, CVector3 vCenter, float width)
{
    // Это наша главная функция, создающая Octree. Она будет работат рекурсивно
    // до окончания деления. Завершит работу она либо когда мы достигнем предела
    // уровней деления, либо охватим все треугольники.

    // Переменная для хранения числа треугольников
    int numberOfTriangles = numberOfVerts / 3;

    // Инициализируем центральную точку ноды.
    m_vCenter = vCenter;

    // Инициализируем размер ребра куба ноды.
    m_Width = width;

    // Добавляем эту ноду к списку отладочных треугольников, чтобы можно было
    // визуализировать её.
    g_Debug.AddDebugRectangle(vCenter, width, width, width);

    // Проверяем, не достигли ли мы предельного значения треугольников в ноде, и не
    // достигли ли мы макс. числа делений ноды. Если так, нужно разбить эту ноду
    // ещё на 8.
    if( (numberOfTriangles > g_MaxTriangles) && (g_CurrentSubdivision < g_MaxSubdivisions) )
    {
        // Устанавливаем флаг деления ноды в true. Это будет означать, что нода
        // не содержит в себе вершин - только дочерние ноды.
        m_bSubDivided = true;

        // Создаем список для каждой новой ноды, если в ней есть треугольники.

        // Создаем список bool для каждого индекса треугольников
        vector<bool> pList1(numberOfTriangles);     // TOP_LEFT_FRONT node list
        vector<bool> pList2(numberOfTriangles);     // TOP_LEFT_BACK node list
        vector<bool> pList3(numberOfTriangles);     // TOP_RIGHT_BACK node list
        vector<bool> pList4(numberOfTriangles);     // TOP_RIGHT_FRONT node list
        vector<bool> pList5(numberOfTriangles);     // BOTTOM_LEFT_FRONT node list
        vector<bool> pList6(numberOfTriangles);     // BOTTOM_LEFT_BACK node list
        vector<bool> pList7(numberOfTriangles);     // BOTTOM_RIGHT_BACK node list
        vector<bool> pList8(numberOfTriangles);     // BOTTOM_RIGHT_FRONT node list

        // Создаем эту переменную для уменьшения обьема кода (легче читать)
        CVector3 vCtr = vCenter;

        // Проходим через все вершины и проверяем, какой ноде они принадлежат.
        // Делаем это, используя центр текущей ноды: проверяем, где лежит
        // точка относительно него.
        for(int i = 0; i < numberOfVerts; i++)
        {
            CVector3 vPoint = pVertices[i];

            if( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z))
                pList1[i / 3] = true;

            if( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z))
                pList2[i / 3] = true;

            if( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z))
                pList3[i / 3] = true;

            if( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z))
                pList4[i / 3] = true;

            if( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z))
                pList5[i / 3] = true;

            if( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z))
                pList6[i / 3] = true;

            if( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z))
                pList7[i / 3] = true;

            if( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z) )
                pList8[i / 3] = true;
        }

        // Here we create a variable for each list that holds how many triangles
        // were found for each of the 8 subdivided nodes.
        int triCount1 = 0;  int triCount2 = 0;  int triCount3 = 0;  int triCount4 = 0;
        int triCount5 = 0;  int triCount6 = 0;  int triCount7 = 0;  int triCount8 = 0;

        // Go through each of the lists and increase the triangle count for each node.
        for(i = 0; i < numberOfTriangles; i++)
        {
            // Increase the triangle count for each node that has a "true" for the index i.
            if(pList1[i])   triCount1++;    if(pList2[i])   triCount2++;
            if(pList3[i])   triCount3++;    if(pList4[i])   triCount4++;
            if(pList5[i])   triCount5++;    if(pList6[i])   triCount6++;
            if(pList7[i])   triCount7++;    if(pList8[i])   triCount8++;
        }

        // Next we do the dirty work.  We need to set up the new nodes with the triangles
        // that are assigned to each node, along with the new center point of the node.
        // Through recursion we subdivide this node into 8 more nodes.

        // Create the subdivided nodes if necessary and then recurse through them.
        // The information passed into CreateNewNode() are essential for creating the
        // new nodes.  We pass the 8 ID's in so it knows how to calculate it's new center.
        CreateNewNode(pVertices, pList1, numberOfVerts, vCenter, width, triCount1, TOP_LEFT_FRONT);
        CreateNewNode(pVertices, pList2, numberOfVerts, vCenter, width, triCount2, TOP_LEFT_BACK);
        CreateNewNode(pVertices, pList3, numberOfVerts, vCenter, width, triCount3, TOP_RIGHT_BACK);
        CreateNewNode(pVertices, pList4, numberOfVerts, vCenter, width, triCount4, TOP_RIGHT_FRONT);
        CreateNewNode(pVertices, pList5, numberOfVerts, vCenter, width, triCount5, BOTTOM_LEFT_FRONT);
        CreateNewNode(pVertices, pList6, numberOfVerts, vCenter, width, triCount6, BOTTOM_LEFT_BACK);
        CreateNewNode(pVertices, pList7, numberOfVerts, vCenter, width, triCount7, BOTTOM_RIGHT_BACK);
        CreateNewNode(pVertices, pList8, numberOfVerts, vCenter, width, triCount8, BOTTOM_RIGHT_FRONT);
    }
    else
    {
        // If we get here we must either be subdivided past our max level, or our triangle
        // count went below the minimum amount of triangles so we need to store them.

        // Assign the vertices to this node since we reached the end node.
        // This will be the end node that actually gets called to be drawn.
        // We just pass in the vertices and vertex count to be assigned to this node.
        AssignVerticesToNode(pVertices, numberOfVerts);
    }
}


//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\*
/////
/////   This allocates memory for the vertices to assign to the current end node
/////
//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\*

void COctree::AssignVerticesToNode(CVector3 *pVertices, int numberOfVerts)
{
    // Since we did not subdivide this node we want to set our flag to false
    m_bSubDivided = false;

    // Initialize the triangle count of this end node (total verts / 3 = total triangles)
    m_TriangleCount = numberOfVerts / 3;

    // Allocate enough memory to hold the needed vertices for the triangles
    m_pVertices = new CVector3 [numberOfVerts];

    // Initialize the vertices to 0 before we copy the data over to them
    memset(m_pVertices, 0, sizeof(CVector3) * numberOfVerts);

    // Copy the passed in vertex data over to our node vertice data
    memcpy(m_pVertices, pVertices, sizeof(CVector3) * numberOfVerts);

    // Increase the amount of end nodes created (Nodes with vertices stored)
    g_EndNodeCount++;
}

// *Note* The code below was thrown in to calculate the normals of the triangles
// that we are displaying.  Instead of complicating the tutorial with separating
// the normals too, I decided to just calculate face normals on the fly so we can
// the depth of the terrain better when we have lighting turned on.


/////////////////////////////////////// CROSS \\\\\\\\\\\\\\\\\\\\\*
/////
/////   This returns a perpendicular vector from 2 given vectors by taking the cross product.
/////
/////////////////////////////////////// CROSS \\\\\\\\\\\\\\\\\\\\\*

CVector3 Cross(CVector3 vVector1, CVector3 vVector2)
{
    CVector3 vNormal;

    // Calculate the cross product with the non communitive equation
    vNormal.x = ((vVector1.y * vVector2.z) - (vVector1.z * vVector2.y));
    vNormal.y = ((vVector1.z * vVector2.x) - (vVector1.x * vVector2.z));
    vNormal.z = ((vVector1.x * vVector2.y) - (vVector1.y * vVector2.x));

    // Return the cross product
    return vNormal;
}


/////////////////////////////////////// MAGNITUDE \\\\\\\\\\\\\\\\\\\\\*
/////
/////   This returns the magnitude of a vector
/////
/////////////////////////////////////// MAGNITUDE \\\\\\\\\\\\\\\\\\\\\*

float Magnitude(CVector3 vNormal)
{
    // Here is the equation:  magnitude = sqrt(V.x^2 + V.y^2 + V.z^2) : Where V is the vector
    return (float)sqrt( (vNormal.x * vNormal.x) +
                        (vNormal.y * vNormal.y) +
                        (vNormal.z * vNormal.z) );
}


/////////////////////////////////////// NORMALIZE \\\\\\\\\\\\\\\\\\\\\*
/////
/////   This returns a normalize vector (A vector exactly of length 1)
/////
/////////////////////////////////////// NORMALIZE \\\\\\\\\\\\\\\\\\\\\*

CVector3 Normalize(CVector3 vVector)
{
    // Get the magnitude of our normal
    float magnitude = Magnitude(vVector);

    // Now that we have the magnitude, we can divide our vector by that magnitude.
    // That will make our vector a total length of 1.
    vVector = vVector / magnitude;

    // Finally, return our normalized vector
    return vVector;
}


//////////////////////////////// DRAW OCTREE \\\\\\\\\\\\\\\*
/////
/////   This function recurses through all the nodes and draws the end node's vertices
/////
//////////////////////////////// DRAW OCTREE \\\\\\\\\\\\\\\*

void COctree::DrawOctree(COctree *pNode)
{
    // We should already have the octree created before we call this function.
    // This goes through all nodes until it reaches their ends and draws the
    // vertices stored in those end nodes.  Before we draw a node we check to
    // make sure it is a subdivided node (from m_bSubdivided).  If it is, then
    // we haven't reaches the end and we need to keep recursing through the tree.
    // Once we get to a node that isn't subdivided we draws it's vertices.

    // Make sure a valid node was passed in, otherwise go back to the last node
    if(!pNode) return;

    // Check if this node is subdivided. If so, then we need to recurse and draw it's nodes
    if(pNode->IsSubDivided())
    {
        // Recurse to the bottom of these nodes and draw the end node's vertices
        // Like creating the octree, we need to recurse through each of the 8 nodes.
        DrawOctree(pNode->m_pOctreeNodes[TOP_LEFT_FRONT]);
        DrawOctree(pNode->m_pOctreeNodes[TOP_LEFT_BACK]);
        DrawOctree(pNode->m_pOctreeNodes[TOP_RIGHT_BACK]);
        DrawOctree(pNode->m_pOctreeNodes[TOP_RIGHT_FRONT]);
        DrawOctree(pNode->m_pOctreeNodes[BOTTOM_LEFT_FRONT]);
        DrawOctree(pNode->m_pOctreeNodes[BOTTOM_LEFT_BACK]);
        DrawOctree(pNode->m_pOctreeNodes[BOTTOM_RIGHT_BACK]);
        DrawOctree(pNode->m_pOctreeNodes[BOTTOM_RIGHT_FRONT]);
    }
    else
    {
        // Make sure we have valid vertices assigned to this node
        if(!pNode->m_pVertices) return;

        // Render using triangles
        glBegin(GL_TRIANGLES);

        // Turn the polygons green
        glColor3ub(0, 255, 0);

        // Store the vertices in a local pointer to keep code more clean
        CVector3 *pVertices = pNode->m_pVertices;

        // Go through all of the vertices (the number of triangles * 3)
        for(int i = 0; i < pNode->GetTriangleCount() * 3; i += 3)
        {
            // Before we render the vertices we want to calculate the face normal
            // of the current polygon.  That way when lighting is turned on we can
            // see the definition of the terrain more clearly.  In reality you wouldn't do this.

            // Here we get a vector from each side of the triangle
            CVector3 vVector1 = pVertices[i + 1] - pVertices[i];
            CVector3 vVector2 = pVertices[i + 2] - pVertices[i];

            // Then we need to get the cross product of those 2 vectors (The normal's direction)
            CVector3 vNormal = Cross(vVector1, vVector2);

            // Now we normalize the normal so it is a unit vector (length of 1)
            vNormal = Normalize(vNormal);

            // Pass in the normal for this triangle so we can see better depth in the scene
            glNormal3f(vNormal.x, vNormal.y, vNormal.z);

            // Render the first point in the triangle
            glVertex3f(pVertices[i].x, pVertices[i].y, pVertices[i].z);

            // Render the next point in the triangle
            glVertex3f(pVertices[i + 1].x, pVertices[i + 1].y, pVertices[i + 1].z);

            // Render the last point in the triangle to form the current triangle
            glVertex3f(pVertices[i + 2].x, pVertices[i + 2].y, pVertices[i + 2].z);
        }

        // Quit Drawing
        glEnd();
    }
}


//////////////////////////////// DESTROY OCTREE \\\\\\\\\\\\\\\*
/////
/////   This frees the memory allocated in the octree
/////
//////////////////////////////// DESTROY OCTREE \\\\\\\\\\\\\\\*

void COctree::DestroyOctree()
{
    // Free the triangle data if it's not NULL
    if( m_pVertices )
    {
        delete[] m_pVertices;
        m_pVertices = NULL;
    }

    // Go through all of the nodes and free them if they were allocated
    for(int i = 0; i < 8; i++)
    {
        // Make sure this node is valid
        if(m_pOctreeNodes[i])
        {
            // Free this array index.  This will call the deconstructor which will
            // free the octree data correctly.  This allows us to forget about it's clean up
            delete m_pOctreeNodes[i];
            m_pOctreeNodes[i] = NULL;
        }
    }

    // Initialize the octree data members
    InitOctree();
}


/////////////////////////////////////////////////////////////////////////////////
//
// * QUICK NOTES *
//
// At first an octree (or any space partitioning) can be intimidating.  Once you
// sit down and start coding it, you become to fully understand the wonderful
// benefits and it's simplicity.  If you can create a tree with nodes, you can
// create an octree.  The only complicated part at first might be the splitting
// of polygons that intersect more than one node.  We don't do that in this tutorial
// so it didn't get to complicated and overhauled with code.  It's way to frustrating
// to learn a ton of things at once, instead of the main idea and basic functionality.
// This octree will work fine, except there will possibly be some doubling of vertices
// because we don't split them into separate one.  That is fine, but not idea for a real
// product.  Eventually you want to fix this.  The last octree tutorial will read in
// a fully textured world that will be split correctly.  Also a more modular octree class
// will be created because we are missing UV coordinates, normals, material ID's, and
// more importantly frustum culling.  The next tutorial will tackle the frustum culling.
//
// Let me explain once more briefly the intent of an octree is.  If you have a huge world
// with 10's of thousands of triangles, you don't want to do a for loop and pass those
// all into OpenGL to be rendered.  You only want to pass in the triangles that you can
// see (the camera's view).  To do this, you want to subdivide your world into cubes
// that holds the triangle data for that area/region of the world.  Then, instead of
// checking if every triangle is in your view, you can just check if a cube intersects
// your frustum, meaning it's in the view of your camera.  This is one of the fastest
// way to do this type of space partitioning.  Just one subdivision puts the world
// into 8 cubes which could cut your triangle rendered count down to 1/8 of what it was.
// If just one subdivision could do that, think about 2, 3 or 4 levels of subdivision?
//
// Let's go over the steps to using this octree class.  Once you have your list of vertices
// you can begin.  The first thing you want to do is call this function:
//
// GetSceneDimensions(g_pVertices, g_NumberOfVerts);
//
// This passes in the list of vertices and the vertex count.  This function calculates
// the center point of the world, as well as the width of the cube that is needed to
// create the first node.  Once we have these values stored, we want to create our tree.
// We can call CreateNode() and pass in the starting data for the first node:
//
// CreateNode(g_pVertices, g_NumberOfVerts, g_Octree.GetCenter(), g_Octree.GetWidth());
//
// This takes the vertices, the vertex count, then the starting center and width.
// This will recurse through and create the whole tree, while assigning the vertices
// to the end nodes.  That's it!  You just created the octree.  The last part is drawing
// the octree.  This is simple, you just call:
//
// DrawOctree();
//
// This should be called in your RenderScene() function.  This goes through all the
// nodes until it gets to the end, then it draws the vertices assigned to those end nodes.
// The deconstructor takes care of the clean up by calling DestroyOctree().
//
// The CDebug class has nothing to do with the octree other than the fact that we use
// it to display the nodes visually.  I suggest you keep something like this around so
// you can visualize your subdivided world and get a better idea of how efficient it is.
//
// Be sure to check out the HTML tutorial on the concept of an octree.  It will give
// good visuals on the whole subdivision process so you can get a better grasp of the
// concepts.  That's about it, so enjoy this tutorial and please let us know what you
// do with it.  We are always curious to know where the knowledge goes. :)
//
// Remember, this tutorial is 1 of a 3 part series.  We still have not delved into the
// frustum culling and polygon splitting part of the octree.  Right now your octree does
// you no good.  This just explains on how to create an octree.  Check out the second
// tutorial which focuses on the frustum culling.
//
// Ben Humphrey
// Game Programmer
// DigiBen@GameTutorials.com
// www.GameTutorials.com
//
// © 2001 GameTutorials










Комментарии:

Войдите, чтобы оставить комментарий:












Яндекс.Метрика
 Яндекс цитирования.