Octree subdivision problem
- by ChaosDev
Im creating octree manually and want function for effectively divide all nodes and their subnodes - For example - I press button and subnodes divided - press again - all subnodes divided again.
Must be like - 1 - 8 - 64. The problem is - i dont understand how organize recursive loops for that.
OctreeNode in my unoptimized implementation contain pointers to subnodes(childs),parent,extra vector(contains dublicates of child),generation info and lots of information for drawing.
class gOctreeNode
{
//necessary fields
gOctreeNode* FrontBottomLeftNode;
gOctreeNode* FrontBottomRightNode;
gOctreeNode* FrontTopLeftNode;
gOctreeNode* FrontTopRightNode;
gOctreeNode* BackBottomLeftNode;
gOctreeNode* BackBottomRightNode;
gOctreeNode* BackTopLeftNode;
gOctreeNode* BackTopRightNode;
gOctreeNode* mParentNode;
std::vector<gOctreeNode*> m_ChildsVector;
UINT mGeneration;
bool mSplitted;
bool isSplitted(){return m_Splitted;}
.... //unnecessary fields
};
DivideNode of Octree class fill these fields, set mSplitted to true, and prepare for correctly drawing. Octree contains basic nodes(m_nodes). Basic node can be divided, but now I want recursivly divide already divided basic node with 8 subnodes. So I write this function.
void DivideAllChildCells(int ix,int ih,int id)
{
std::vector<gOctreeNode*> nlist;
std::vector<gOctreeNode*> dlist;
int index = (ix * m_Height * m_Depth) + (ih * m_Depth) + (id * 1);//get index of specified node
gOctreeNode* baseNode = m_nodes[index].get();
nlist.push_back(baseNode->FrontTopLeftNode);
nlist.push_back(baseNode->FrontTopRightNode);
nlist.push_back(baseNode->FrontBottomLeftNode);
nlist.push_back(baseNode->FrontBottomRightNode);
nlist.push_back(baseNode->BackBottomLeftNode);
nlist.push_back(baseNode->BackBottomRightNode);
nlist.push_back(baseNode->BackTopLeftNode);
nlist.push_back(baseNode->BackTopRightNode);
bool cont = true;
UINT d = 0;//additional recursive loop param (?)
UINT g = 0;//additional recursive loop param (?)
LoopNodes(d,g,nlist,dlist);
//Divide resulting nodes
for(UINT i = 0; i < dlist.size(); i++)
{
DivideNode(dlist[i]);
}
}
And now, back to the main question,I present LoopNodes, which must do all work for giving dlist nodes for splitting.
void LoopNodes(UINT& od,UINT& og,std::vector<gOctreeNode*>& nlist,std::vector<gOctreeNode*>& dnodes)
{
//od++;//recursion depth
bool f = false;
//pass through childs
for(UINT i = 0; i < 8; i++)
{
if(nlist[i]->isSplitted())//if node splitted and have childs
{
//pass forward through tree
for(UINT j = 0; j < 8; j++)
{
nlist[j] = nlist[j]->m_ChildsVector[j];//set pointers to these childs
}
LoopNodes(od,og,nlist,dnodes);
}
else //if no childs
{
//add to split vector
dnodes.push_back(nlist[i]);
}
}
}
This version of loop nodes works correctly for 2(or 1?) generations after - this will not divide neightbours nodes, only some corners. I need correct algorithm.
Screenshot
All I need - is correct version of LoopNodes, which can add all nodes for DivideNode.
