OpenGL: Octree

// Макс. число делений (уровеней деления)
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

///////////////////////////////// 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