Sign in to follow this  
facedancer

octree implementation wanted :D

Recommended Posts

Hey gang Can anyone point me a nice octree implementation in c/c++ & ogl, commented code would be best... Mine problem is that I know the theory standing after it but have really no idea how to code it. cheers

Share this post


Link to post
Share on other sites
I don't know where my octree implementation is but here is a quad tree impementation.

QuadTree.H

#ifndef _MY_TREE_H
#define _MY_TREE_H

#include "OpenGLLinker.H"

// this is our tree class
class CTree
{
public:
CVector3 Min,Max; // Bounding Box Min and Maximums
bool EndNode;
//
int MyDepth;
int numChildren; // if 0 then it is end node
CTree *child;

void GenerateParent(); // Generates the Parent and sets it up and starts recursively
void GenerateChild(int CurrentDepth,CVector3 Min,CVector3 Max); // Generates The Children
void RenderTree(bool EndNodesOnly,int Depth); // Renders the Entire Tree
void SetVisibleTiles(int depth);
//////////
int CountChildren();
int FindMaxDepth();

~CTree()
{ // Destructor
if (child != NULL) delete [numChildren] child;
}
CTree()
{
child = NULL;
numChildren = 0;
};

};


#endif



QuadTree.cpp

#include "ViewTree.H"
#include "Map.H"
#include "Frustum.H"

extern CMap map; // Our map
extern CFrustum Frustum;


// Globals for the Tree
int MaxDepth = 9; // FAIL SAFE VALUE

// Okay Lets Start Generating the Tree
void CTree::GenerateParent()
{
// MaxDepth = (float(map.Width) / 512.0f) * MaxDepth;
EndNode = false;
// Okay So the Parents Min & Max bound is always the entire Map
Min = CVector3(0,0,0);
Max = CVector3(float(map.Width)-1.0f,float(map.Height)-1.0f,map.Resolution);
GenerateChild(0,Min,Max); // Generate the Parent

return;
};

void CTree::GenerateChild(int CurrentDepth,CVector3 MMin,CVector3 MMax)
{
Min = MMin;
Max = MMax;
MyDepth = CurrentDepth;
// Now for the Child we need to Go through from its Min to its max and workout its
// Z Height
Min.z = 16;
Max.z = 0;
for (int x=int(Min.x);x < Max.x;x++)
for (int y=int(Min.y);y < Max.y;y++)
{
if (map.GetHeight(float(x),float(y)) > Max.z) Max.z = map.GetHeight(x,y);
if (map.GetHeight(float(x),float(y)) < Min.z) Min.z = map.GetHeight(x,y);
}

if ((CurrentDepth >= MaxDepth) || (int(Max.x - Min.x) <= 2))
{
EndNode = true;
}
else
{
EndNode = false;

numChildren = 4;
child = new CTree[4];

CVector3 Middle = (Min+Max)/2.0f; // Get The Middle of the AABB

child[0].GenerateChild(CurrentDepth+1,Min,Middle);
child[1].GenerateChild(CurrentDepth+1,Middle,Max);
child[2].GenerateChild(CurrentDepth+1,CVector3(Middle.x,Min.y,Min.z),CVector3(Max.x,Middle.y,Middle.z));
child[3].GenerateChild(CurrentDepth+1,CVector3(Min.x,Middle.y,Min.z),CVector3(Middle.x,Max.y,Middle.z));
};
};


//////////////////////////////////////////////////////////////////
//// USES the View frustum and the Quad tree to flag all visible tiles //////////////
//////////////////////////////////////////////////////////////////
void CTree::SetVisibleTiles(int depth)
{/*
// New assesing method
for (int p =0;p < 6;p++)
{// Loop through all 6 planes
for (int g=0;g < 5;g++)
{ // Loop Through all 5 Points
switch (p)
{
case 0:
if (Frustum.FrustumPoint[g].x > Min.x) goto TEST_NEXT;
break;
case 1:
if (Frustum.FrustumPoint[g].x < Max.x) goto TEST_NEXT;
break;
case 2:
if (Frustum.FrustumPoint[g].y > Min.y) goto TEST_NEXT;
break;
case 3:
if (Frustum.FrustumPoint[g].y < Max.y) goto TEST_NEXT;
break;
case 4:
if (Frustum.FrustumPoint[g].z > Min.z) goto TEST_NEXT;
break;
case 5:
if (Frustum.FrustumPoint[g].z < Max.z) goto TEST_NEXT;
break;
}
}
// If it gets here it is completely outside of the Box/Not intersecting.
return;
TEST_NEXT:; // It was not completely isolated, test next side
}
*/

int result = Frustum.CubeInFrustumEvaluate(Min,Max);
if (result == TotallyOutside) return;

if ((result == TotallyInside) || (EndNode)) // Set all tiles in this AABBs Area to True IE Visible
for (int x=int(Min.x);x < int(Max.x);x++)
for (int y=int(Min.y);y < int(Max.y);y++)
map.visibleTiles[x+y * map.Width] = true;
else for (int g=0;g < 4;g++)
child[g].SetVisibleTiles(depth+1);
};

//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////
//////////// RENDERS THE TREE //////////////
//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////
void CTree::RenderTree(bool EndNodesOnly,int RenderDepth)
{
if (RenderDepth < MyDepth) return;
glLineWidth(2.0f/MyDepth);
if (!EndNode) glColor3f(1.0f,1.0f,1.0f);
else glColor3f(1,0,0.0f);
if ((EndNode) || (EndNodesOnly == false) || (MyDepth == RenderDepth)) RenderAABoundingBox(Min,Max);
for (int g=0;g < numChildren;g++)
child[g].RenderTree(EndNodesOnly,RenderDepth);
};



// Count the Number of Nodes on the Tree
int CTree::CountChildren()
{
int total = 1; // Count itself
for (int g=0;g < numChildren;g++)
{
total+= child[g].CountChildren();
}
return total;
}
// Find the Deepest the Tree goes
int CTree::FindMaxDepth()
{

if (numChildren == 0)
{ // Its an end node
return this->MyDepth;
}

int deepest = MyDepth,t;
for (int g=0;g < numChildren;g++)
{
t = child[g].FindMaxDepth();
if (t > deepest) deepest = t;
}
return deepest;
};


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this