# Octree subdivision problem

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
{
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.

I think you're overcomplicating things. If I understood correctly, you want to find all leaf-nodes within your octree and add these to a list of nodes that should be subdivided.

I have no clue what you need the d and g parameter for.. something like this should work:

void LoopNodes(gOctreeNode* node, std::vector<gOctreeNode*>& dnodes)
{
// check if it's a leaf-node
if(node->isSplitted()){
// not a leaf-node, so check all children
for(UINT i = 0; i < 8; i++){
LoopNodes(node->m_ChildsVector[i], dnodes);
}
} else {
dnodes.push_back(node);
}
}


Then start the search by passing in your "main" (outermost) cube as node to the function, like this:

LoopNodes(mainNode, dnodes);

• I want divide basic node and its subnodes in one pass. If node already subdivided - than divide their childs.. Every pass increase number of nodes. What is mainNodes.size() ? This function intended to use with one basic node and its subnodes. – ChaosDev Jul 6 '12 at 8:05
• @ChaosDev. Ok, then just do: LoopNodes(mainNode, dnodes); as your initial call. Forget about the for-loop. Will edit my answer accordingly. – bummzack Jul 6 '12 at 8:09