Show
Ignore:
Timestamp:
06/06/08 15:21:27 (6 years ago)
Author:
robert
Message:

Introduce a lower overhead data structure for leaves.

Files:
1 modified

Legend:

Unmodified
Added
Removed
  • OpenSceneGraph/trunk/examples/osgkdtree/osgkdtree.cpp

    r8414 r8415  
    4545{ 
    4646 
     47typedef int value_type; 
     48typedef std::vector< value_type >   Indices; 
     49 
     50//#define LEAF_OBJECT 
     51//#define VERBOSE_OUTPUT 
     52 
     53#ifdef LEAF_OBJECT 
    4754class KDNode 
    4855{ 
     
    5057     
    5158        KDNode(): 
    52             _leftChild(0), 
    53             _rightChild(0) {} 
     59            first(0), 
     60            second(0) {} 
    5461     
    5562        KDNode(const KDNode& rhs): 
    56             _leftChild(rhs._leftChild), 
    57             _rightChild(rhs._rightChild) {} 
     63            first(rhs.first), 
     64            second(rhs.second) {} 
    5865 
    5966        KDNode& operator = (const KDNode& rhs) 
    6067        { 
    61             _leftChild = rhs._leftChild; 
    62             _rightChild = rhs._rightChild; 
     68            first = rhs.first; 
     69            second = rhs.second; 
    6370            return *this; 
    6471        } 
    6572 
    66         typedef short value_type; 
    67  
    68         value_type _leftChild; 
    69         value_type _rightChild; 
     73        value_type first; 
     74        value_type second; 
    7075}; 
    7176 
     
    7580     
    7681        KDLeaf() {} 
    77      
    78         typedef unsigned int index_type; 
    79         typedef std::vector< index_type > Indices; 
    8082 
    8183        Indices _vertexIndices;         
     
    8688}; 
    8789 
     90#else 
     91    typedef std::pair< value_type, value_type> KDNode; 
     92    typedef std::pair< value_type, value_type> KDLeaf; 
     93#endif 
     94 
     95 
    8896class KDTree : public osg::Shape 
    8997{ 
     
    97105 
    98106        META_Shape(osg, KDTree) 
     107         
    99108     
    100109        typedef std::vector< unsigned int > AxisStack; 
    101         typedef std::vector< KDNode > KDNodeList; 
     110        typedef std::vector< KDNode >       KDNodeList; 
     111 
     112#ifdef LEAF_OBJECT 
    102113        typedef std::vector< osg::ref_ptr<KDLeaf> > KDLeafList; 
    103          
    104          
     114 
    105115        /// note, leafNum is negative to distinguish from nodeNum 
    106116        int addLeaf(KDLeaf* leaf) { int num = _kdLeaves.size(); _kdLeaves.push_back(leaf); return -(num+1); } 
     
    131141            return _kdLeaves[num].get(); 
    132142        } 
     143 
     144#else 
     145        typedef std::vector< KDLeaf > KDLeafList; 
     146 
     147        /// note, leafNum is negative to distinguish from nodeNum 
     148        int addLeaf(const KDLeaf& leaf) { int num = _kdLeaves.size(); _kdLeaves.push_back(leaf); return -(num+1); } 
     149 
     150        int replaceLeaf(int leafNum, const KDLeaf& leaf) 
     151        { 
     152            int num = -leafNum-1;  
     153             
     154            if (num>_kdLeaves.size()-1) 
     155            { 
     156                osg::notify(osg::NOTICE)<<"Warning: replaceChild("<<leafNum<<", leaf), num = "<<num<<" _kdLeaves.size()="<<_kdLeaves.size()<<std::endl; 
     157                return leafNum; 
     158            } 
     159             
     160            _kdLeaves[num] = leaf; return leafNum; 
     161        } 
     162 
     163        /// note, leafNum is negative to distinguish from nodeNum 
     164        KDLeaf& getLeaf(int leafNum) 
     165        { 
     166            int num = -leafNum-1; 
     167            if (num<0 || num>_kdLeaves.size()-1) 
     168            { 
     169                osg::notify(osg::NOTICE)<<"Warning: getLeaf("<<leafNum<<", num = "<<num<<") _kdLeaves.size()="<<_kdLeaves.size()<<std::endl; 
     170            } 
     171 
     172            return _kdLeaves[num]; 
     173        } 
     174#endif         
     175         
    133176         
    134177        int addNode(const KDNode& node) 
     
    156199        AxisStack                       _axisStack; 
    157200        KDNodeList                      _kdNodes; 
    158         KDLeafList                      _kdLeaves;  
     201        KDLeafList                      _kdLeaves; 
     202        Indices                         _vertexIndices; 
    159203}; 
    160204 
     
    174218     
    175219 
    176         void traverse(KDLeaf& leaf, unsigned int level) 
     220        void traverse(KDTree& tree, KDLeaf& leaf, unsigned int level) 
    177221        { 
    178222            output(level)<<"leaf("<<level<<") { "; 
    179223 
     224#ifdef LEAF_OBJECT 
    180225            for(unsigned int i=0; i<leaf._vertexIndices.size(); ++i) 
    181226            { 
     
    183228                else osg::notify(osg::NOTICE)<<", "<<leaf._vertexIndices[i];                 
    184229            } 
    185  
     230#else 
     231            unsigned int end = leaf.first+leaf.second; 
     232            for(unsigned int i=leaf.first; i<end; ++i) 
     233            { 
     234                if (i==leaf.first) osg::notify(osg::NOTICE)<<tree._vertexIndices[i]; 
     235                else osg::notify(osg::NOTICE)<<", "<<tree._vertexIndices[i];                 
     236            } 
     237#endif 
    186238            osg::notify(osg::NOTICE)<<"}"<<std::endl;; 
    187239             
    188240        } 
    189241 
    190         void traverse(KDTree& tree, KDNode::value_type nodeIndex, unsigned int level) 
     242        void traverse(KDTree& tree, value_type nodeIndex, unsigned int level) 
    191243        { 
    192244            output(level)<<"traverse("<<nodeIndex<<", "<< level<<") { "<<std::endl; 
     
    195247            {         
    196248                KDNode& node = tree._kdNodes[nodeIndex]; 
    197                 if (node._leftChild) traverse(tree,node._leftChild,level+1); 
     249                if (node.first) traverse(tree,node.first,level+1); 
    198250                else output(level+1)<<"empty left child()"<<std::endl; 
    199251                 
    200                 if (node._rightChild) traverse(tree,node._rightChild,level+1); 
     252                if (node.second) traverse(tree,node.second,level+1); 
    201253                else output(level+1)<<"empty right child()"<<std::endl; 
    202254            } 
    203255            else  
    204256            { 
    205                 KDNode::value_type leafIndex = -nodeIndex-1; 
     257                value_type leafIndex = -nodeIndex-1; 
     258#ifdef LEAF_OBJECT 
    206259                KDLeaf& leaf = *(tree._kdLeaves[leafIndex]); 
    207                 traverse(leaf, level); 
     260#else 
     261                KDLeaf& leaf = tree._kdLeaves[leafIndex]; 
     262#endif 
     263                traverse(tree, leaf, level); 
    208264            } 
    209265 
     
    221277            else if (!tree._kdLeaves.empty()) 
    222278            { 
    223                 traverse(*tree._kdLeaves.front(), 0); 
     279#ifdef LEAF_OBJECT 
     280                traverse(tree, *tree._kdLeaves.front(), 0); 
     281#else 
     282                traverse(tree, tree._kdLeaves.front(), 0); 
     283#endif 
    224284            } 
    225285        } 
     
    269329KDTree* KDTreeBuilder::createKDTree(osg::Geometry* geometry) 
    270330{ 
    271 #if VERBOSE_OUTPUT     
     331#ifdef VERBOSE_OUTPUT     
    272332    osg::notify(osg::NOTICE)<<"osg::KDTreeBuilder::createKDTree()"<<std::endl; 
    273333#endif 
     
    283343    unsigned int estimatedSize = (unsigned int)(float(vertices->size())/float(_targetNumVerticesPerLeaf)*1.5); 
    284344 
    285 #if VERBOSE_OUTPUT     
     345#ifdef VERBOSE_OUTPUT     
    286346    osg::notify(osg::NOTICE)<<"kdTree->_kdNodes.reserve()="<<estimatedSize<<std::endl<<std::endl; 
    287347#endif 
     
    295355    _numVerticesProcessed += vertices->size(); 
    296356 
     357#ifdef LEAF_OBJECT 
    297358    // create initial leaf list     
    298359    KDLeaf* leaf = new KDLeaf; 
     
    302363        leaf->_vertexIndices.push_back(i); 
    303364    } 
    304  
     365#else 
     366 
     367    kdTree->_vertexIndices.reserve(vertices->size()); 
     368    for(unsigned int i=0; i<vertices->size(); ++i) 
     369    { 
     370        kdTree->_vertexIndices.push_back(i); 
     371    } 
     372    KDLeaf leaf(0, kdTree->_vertexIndices.size()); 
     373 
     374#endif 
     375 
     376    int leafNum = kdTree->addLeaf(leaf); 
    305377    osg::BoundingBox bb = kdTree->_bb; 
    306      
    307     int leafNum = kdTree->addLeaf(leaf); 
    308378    int nodeNum = divide(*kdTree, bb, leafNum, 0); 
    309      
    310 #if VERBOSE_OUTPUT     
     379 
     380 
     381 
     382     
     383#ifdef VERBOSE_OUTPUT     
    311384    osg::notify(osg::NOTICE)<<"Root nodeNum="<<nodeNum<<std::endl; 
    312385#endif 
    313386     
    314 #if VERBOSE_OUTPUT     
     387#ifdef VERBOSE_OUTPUT     
    315388     
    316389    KDTreeTraverser traverser; 
     
    334407                         kdTree._bb.zMax()-kdTree._bb.zMin()); 
    335408 
    336 #if VERBOSE_OUTPUT     
     409#ifdef VERBOSE_OUTPUT     
    337410    osg::notify(osg::NOTICE)<<"computeDivisions("<<_maxNumLevels<<") "<<dimensions<< " { "<<std::endl; 
    338411#endif 
     
    355428        dimensions[axis] /= 2.0f; 
    356429 
    357 #if VERBOSE_OUTPUT     
     430#ifdef VERBOSE_OUTPUT     
    358431        osg::notify(osg::NOTICE)<<"  "<<level<<", "<<dimensions<<", "<<axis<<std::endl; 
    359432#endif 
    360433    } 
    361434 
    362 #if VERBOSE_OUTPUT     
     435#ifdef VERBOSE_OUTPUT     
    363436    osg::notify(osg::NOTICE)<<"}"<<std::endl; 
    364437#endif 
     
    372445    int axis = kdTree._axisStack[level]; 
    373446 
    374 #if VERBOSE_OUTPUT     
     447#ifdef VERBOSE_OUTPUT     
    375448    //osg::notify(osg::NOTICE)<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl; 
    376449#endif 
     
    378451    if (nodeIndex>=0) 
    379452    { 
    380 #if VERBOSE_OUTPUT     
     453#ifdef VERBOSE_OUTPUT     
    381454        osg::notify(osg::NOTICE)<<"  divide node"<<std::endl; 
    382455#endif 
     
    386459    else 
    387460    {     
     461 
     462#ifdef LEAF_OBJECT 
    388463        if (kdTree.getLeaf(nodeIndex)->_vertexIndices.size()<=_targetNumVerticesPerLeaf) return nodeIndex; 
    389      
     464#else 
     465        if (kdTree.getLeaf(nodeIndex).second<=_targetNumVerticesPerLeaf) return nodeIndex; 
     466#endif     
    390467        //osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl; 
    391468         
     
    397474        float mid = (original_min+original_max)*0.5f; 
    398475 
     476#ifdef LEAF_OBJECT 
    399477        { 
    400478            osg::ref_ptr<KDLeaf> leaf = kdTree.getLeaf(nodeIndex); 
     
    424502            { 
    425503                //osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl; 
    426                 kdTree.getNode(nodeNum)._leftChild = 0; 
    427                 kdTree.getNode(nodeNum)._rightChild = kdTree.replaceLeaf(nodeIndex, rightLeaf.get()); 
     504                kdTree.getNode(nodeNum).first = 0; 
     505                kdTree.getNode(nodeNum).second = kdTree.replaceLeaf(nodeIndex, rightLeaf.get()); 
    428506            } 
    429507            else if (rightLeaf->_vertexIndices.empty()) 
    430508            { 
    431509                //osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl; 
    432                 kdTree.getNode(nodeNum)._leftChild = kdTree.replaceLeaf(nodeIndex, leftLeaf.get()); 
    433                 kdTree.getNode(nodeNum)._rightChild = 0; 
     510                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf.get()); 
     511                kdTree.getNode(nodeNum).second = 0; 
    434512            } 
    435513            else 
    436514            { 
    437                 kdTree.getNode(nodeNum)._leftChild = kdTree.replaceLeaf(nodeIndex, leftLeaf.get()); 
    438                 kdTree.getNode(nodeNum)._rightChild = kdTree.addLeaf(rightLeaf.get()); 
    439             } 
    440  
    441  
    442         } 
    443          
    444         int originalLeftChildIndex = kdTree.getNode(nodeNum)._leftChild; 
    445         int originalRightChildIndex = kdTree.getNode(nodeNum)._rightChild; 
     515                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf.get()); 
     516                kdTree.getNode(nodeNum).second = kdTree.addLeaf(rightLeaf.get()); 
     517            } 
     518        } 
     519#else 
     520        { 
     521            KDLeaf& leaf = kdTree.getLeaf(nodeIndex); 
     522 
     523            osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(kdTree._geometry->getVertexArray()); 
     524 
     525            //osg::notify(osg::NOTICE)<<"  divide leaf->_vertexIndices.size()="<<leaf->_vertexIndices.size()<<std::endl; 
     526 
     527            unsigned int estimatedSize = leaf.second; 
     528 
     529            int end = leaf.first+leaf.second-1; 
     530            int left = leaf.first; 
     531            int right = leaf.first+leaf.second-1; 
     532             
     533            while(left<right) 
     534            { 
     535                while(left<right && ((*vertices)[kdTree._vertexIndices[left]])[axis]<=mid) { ++left; } 
     536                 
     537                while(left<right && ((*vertices)[kdTree._vertexIndices[right]])[axis]>mid) { --right; } 
     538 
     539                if (left<right) 
     540                { 
     541                    std::swap(kdTree._vertexIndices[left], kdTree._vertexIndices[right]); 
     542                    ++left; 
     543                    --right; 
     544                } 
     545            } 
     546             
     547            if (left==right) 
     548            { 
     549                if (((*vertices)[kdTree._vertexIndices[left]])[axis]<=mid) ++left; 
     550                else --right; 
     551            } 
     552             
     553            KDLeaf leftLeaf(leaf.first, (right-leaf.first)+1); 
     554            KDLeaf rightLeaf(left, (end-left)+1); 
     555 
     556#if 0             
     557            osg::notify(osg::NOTICE)<<"In  leaf.first     ="<<leaf.first     <<" leaf.second     ="<<leaf.second<<std::endl; 
     558            osg::notify(osg::NOTICE)<<"    leftLeaf.first ="<<leftLeaf.first <<" leftLeaf.second ="<<leftLeaf.second<<std::endl; 
     559            osg::notify(osg::NOTICE)<<"    rightLeaf.first="<<rightLeaf.first<<" rightLeaf.second="<<rightLeaf.second<<std::endl; 
     560            osg::notify(osg::NOTICE)<<"    left="<<left<<" right="<<right<<std::endl; 
     561 
     562            if (leaf.second != (leftLeaf.second +rightLeaf.second)) 
     563            { 
     564                osg::notify(osg::NOTICE)<<"*** Error in size, leaf.second="<<leaf.second 
     565                                        <<", leftLeaf.second="<<leftLeaf.second 
     566                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl; 
     567            } 
     568            else 
     569            { 
     570                osg::notify(osg::NOTICE)<<"Size OK, leaf.second="<<leaf.second 
     571                                        <<", leftLeaf.second="<<leftLeaf.second 
     572                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl; 
     573            } 
     574#endif 
     575            if (leftLeaf.second<=0) 
     576            { 
     577                //osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl; 
     578                kdTree.getNode(nodeNum).first = 0; 
     579                kdTree.getNode(nodeNum).second = kdTree.replaceLeaf(nodeIndex, rightLeaf); 
     580            } 
     581            else if (rightLeaf.second<=0) 
     582            { 
     583                //osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl; 
     584                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf); 
     585                kdTree.getNode(nodeNum).second = 0; 
     586            } 
     587            else 
     588            { 
     589                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf); 
     590                kdTree.getNode(nodeNum).second = kdTree.addLeaf(rightLeaf); 
     591            } 
     592        } 
     593#endif 
     594         
     595        int originalLeftChildIndex = kdTree.getNode(nodeNum).first; 
     596        int originalRightChildIndex = kdTree.getNode(nodeNum).second; 
    446597 
    447598 
     
    449600        bb._max[axis] = mid; 
    450601 
    451         //osg::notify(osg::NOTICE)<<"  divide leftLeaf "<<kdTree.getNode(nodeNum)._leftChild<<std::endl; 
     602        //osg::notify(osg::NOTICE)<<"  divide leftLeaf "<<kdTree.getNode(nodeNum).first<<std::endl; 
    452603        int leftChildIndex = divide(kdTree, bb, originalLeftChildIndex, level+1); 
    453604 
     
    457608        bb._min[axis] = mid; 
    458609 
    459         //osg::notify(osg::NOTICE)<<"  divide rightLeaf "<<kdTree.getNode(nodeNum)._rightChild<<std::endl; 
     610        //osg::notify(osg::NOTICE)<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl; 
    460611        int rightChildIndex = divide(kdTree, bb, originalRightChildIndex, level+1); 
    461612         
    462613        bb._min[axis] = restore; 
    463614         
    464         kdTree.getNode(nodeNum)._leftChild = leftChildIndex; 
    465         kdTree.getNode(nodeNum)._rightChild = rightChildIndex;  
     615        kdTree.getNode(nodeNum).first = leftChildIndex; 
     616        kdTree.getNode(nodeNum).second = rightChildIndex;  
    466617         
    467618        return nodeNum;         
     
    488639 
    489640    osgUtil::UpdateVisitor updateVisitor; 
     641    updateVisitor.setFrameStamp(new osg::FrameStamp); 
    490642    scene->accept(updateVisitor); 
     643    scene->getBound(); 
    491644 
    492645