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();


        bool cont = true;           
        UINT d = 0;//additional recursive loop param (?)
        UINT g = 0;//additional recursive loop param (?)     


        //Divide resulting nodes
        for(UINT i = 0; i < dlist.size(); 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
            else //if no childs
                //add to split vector 

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 octree

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
        // not a leaf-node, so check all children
        for(UINT i = 0; i < 8; i++){
            LoopNodes(node->m_ChildsVector[i], dnodes);
    } else {

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

LoopNodes(mainNode, dnodes);
  • \$\begingroup\$ 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. \$\endgroup\$
    – ChaosDev
    Jul 6 '12 at 8:05
  • \$\begingroup\$ @ChaosDev. Ok, then just do: LoopNodes(mainNode, dnodes); as your initial call. Forget about the for-loop. Will edit my answer accordingly. \$\endgroup\$
    – bummzack
    Jul 6 '12 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.