2
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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);
\$\endgroup\$
2
  • \$\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, 2012 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, 2012 at 8:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .