Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 octree

All I need - is correct version of LoopNodes, which can add all nodes for DivideNode.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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);
share|improve this answer
    
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
    
Thank for answer ! Its work –  ChaosDev Jul 6 '12 at 8:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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