Jump to content
  • Advertisement
Sign in to follow this  

octree implementation wanted :D

This topic is 2201 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!