Show
Ignore:
Timestamp:
06/06/08 16:10:20 (6 years ago)
Author:
robert
Message:

Cleaned up implementation to only use simple structure

Files:
1 modified

Legend:

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

    r8415 r8417  
    2020#include <osgDB/ReadFile> 
    2121 
    22 #define _GLIBCXX_DEBUG 
    23  
    2422#include <osg/ArgumentParser> 
    2523#include <osg/ApplicationUsage> 
     
    4846typedef std::vector< value_type >   Indices; 
    4947 
    50 //#define LEAF_OBJECT 
    5148//#define VERBOSE_OUTPUT 
    5249 
    53 #ifdef LEAF_OBJECT 
    54 class KDNode 
    55 { 
    56     public: 
    57      
    58         KDNode(): 
    59             first(0), 
    60             second(0) {} 
    61      
    62         KDNode(const KDNode& rhs): 
    63             first(rhs.first), 
    64             second(rhs.second) {} 
    65  
    66         KDNode& operator = (const KDNode& rhs) 
    67         { 
    68             first = rhs.first; 
    69             second = rhs.second; 
    70             return *this; 
    71         } 
    72  
    73         value_type first; 
    74         value_type second; 
    75 }; 
    76  
    77 class KDLeaf : public osg::Referenced 
    78 { 
    79     public: 
    80      
    81         KDLeaf() {} 
    82  
    83         Indices _vertexIndices;         
    84      
    85     protected: 
    86      
    87         virtual ~KDLeaf() {} 
    88 }; 
    89  
    90 #else 
    91     typedef std::pair< value_type, value_type> KDNode; 
    92     typedef std::pair< value_type, value_type> KDLeaf; 
    93 #endif 
     50typedef std::pair< value_type, value_type> KDNode; 
     51typedef std::pair< value_type, value_type> KDLeaf; 
    9452 
    9553 
     
    11068        typedef std::vector< KDNode >       KDNodeList; 
    11169 
    112 #ifdef LEAF_OBJECT 
    113         typedef std::vector< osg::ref_ptr<KDLeaf> > KDLeafList; 
     70        typedef std::vector< KDLeaf > KDLeafList; 
    11471 
    11572        /// note, leafNum is negative to distinguish from nodeNum 
    116         int addLeaf(KDLeaf* leaf) { int num = _kdLeaves.size(); _kdLeaves.push_back(leaf); return -(num+1); } 
    117  
    118         int replaceLeaf(int leafNum, KDLeaf* leaf) 
     73        int addLeaf(const KDLeaf& leaf) { int num = _kdLeaves.size(); _kdLeaves.push_back(leaf); return -(num+1); } 
     74 
     75        int replaceLeaf(int leafNum, const KDLeaf& leaf) 
    11976        { 
    12077            int num = -leafNum-1;  
     
    13087 
    13188        /// note, leafNum is negative to distinguish from nodeNum 
    132         KDLeaf* getLeaf(int leafNum) 
     89        KDLeaf& getLeaf(int leafNum) 
    13390        { 
    13491            int num = -leafNum-1; 
     
    13693            { 
    13794                osg::notify(osg::NOTICE)<<"Warning: getLeaf("<<leafNum<<", num = "<<num<<") _kdLeaves.size()="<<_kdLeaves.size()<<std::endl; 
    138                 return 0; 
    139             } 
    140  
    141             return _kdLeaves[num].get(); 
    142         } 
    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; 
    17095            } 
    17196 
    17297            return _kdLeaves[num]; 
    17398        } 
    174 #endif         
    175          
    17699         
    177100        int addNode(const KDNode& node) 
     
    222145            output(level)<<"leaf("<<level<<") { "; 
    223146 
    224 #ifdef LEAF_OBJECT 
    225             for(unsigned int i=0; i<leaf._vertexIndices.size(); ++i) 
    226             { 
    227                 if (i==0) osg::notify(osg::NOTICE)<<leaf._vertexIndices[i]; 
    228                 else osg::notify(osg::NOTICE)<<", "<<leaf._vertexIndices[i];                 
    229             } 
    230 #else 
    231147            unsigned int end = leaf.first+leaf.second; 
    232148            for(unsigned int i=leaf.first; i<end; ++i) 
     
    235151                else osg::notify(osg::NOTICE)<<", "<<tree._vertexIndices[i];                 
    236152            } 
    237 #endif 
     153 
    238154            osg::notify(osg::NOTICE)<<"}"<<std::endl;; 
    239155             
     
    256172            { 
    257173                value_type leafIndex = -nodeIndex-1; 
    258 #ifdef LEAF_OBJECT 
    259                 KDLeaf& leaf = *(tree._kdLeaves[leafIndex]); 
    260 #else 
     174 
    261175                KDLeaf& leaf = tree._kdLeaves[leafIndex]; 
    262 #endif 
     176 
    263177                traverse(tree, leaf, level); 
    264178            } 
     
    277191            else if (!tree._kdLeaves.empty()) 
    278192            { 
    279 #ifdef LEAF_OBJECT 
    280                 traverse(tree, *tree._kdLeaves.front(), 0); 
    281 #else 
    282193                traverse(tree, tree._kdLeaves.front(), 0); 
    283 #endif 
    284194            } 
    285195        } 
     
    355265    _numVerticesProcessed += vertices->size(); 
    356266 
    357 #ifdef LEAF_OBJECT 
    358     // create initial leaf list     
    359     KDLeaf* leaf = new KDLeaf; 
    360     leaf->_vertexIndices.reserve(vertices->size()); 
    361     for(unsigned int i=0; i<vertices->size(); ++i) 
    362     { 
    363         leaf->_vertexIndices.push_back(i); 
    364     } 
    365 #else 
    366  
    367267    kdTree->_vertexIndices.reserve(vertices->size()); 
    368268    for(unsigned int i=0; i<vertices->size(); ++i) 
     
    370270        kdTree->_vertexIndices.push_back(i); 
    371271    } 
     272     
    372273    KDLeaf leaf(0, kdTree->_vertexIndices.size()); 
    373  
    374 #endif 
    375274 
    376275    int leafNum = kdTree->addLeaf(leaf); 
     
    460359    {     
    461360 
    462 #ifdef LEAF_OBJECT 
    463         if (kdTree.getLeaf(nodeIndex)->_vertexIndices.size()<=_targetNumVerticesPerLeaf) return nodeIndex; 
    464 #else 
    465361        if (kdTree.getLeaf(nodeIndex).second<=_targetNumVerticesPerLeaf) return nodeIndex; 
    466 #endif     
     362 
    467363        //osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl; 
    468364         
     
    474370        float mid = (original_min+original_max)*0.5f; 
    475371 
    476 #ifdef LEAF_OBJECT 
    477         { 
    478             osg::ref_ptr<KDLeaf> leaf = kdTree.getLeaf(nodeIndex); 
    479  
    480             // create new node, and add two leaves to it. 
    481             osg::ref_ptr<KDLeaf> leftLeaf = new KDLeaf; 
    482             osg::ref_ptr<KDLeaf> rightLeaf = new KDLeaf; 
    483  
    484  
    485             osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(kdTree._geometry->getVertexArray()); 
    486  
    487             //osg::notify(osg::NOTICE)<<"  divide leaf->_vertexIndices.size()="<<leaf->_vertexIndices.size()<<std::endl; 
    488  
    489             unsigned int estimatedSize = leaf->_vertexIndices.size(); 
    490             leftLeaf->_vertexIndices.reserve(estimatedSize); 
    491             rightLeaf->_vertexIndices.reserve(estimatedSize); 
    492  
    493             for(unsigned int i=0; i<leaf->_vertexIndices.size(); ++i) 
    494             { 
    495                 unsigned int vi = leaf->_vertexIndices[i]; 
    496                 osg::Vec3& v = (*vertices)[vi]; 
    497                 if (v[axis] <= mid) leftLeaf->_vertexIndices.push_back(vi); 
    498                 else rightLeaf->_vertexIndices.push_back(vi); 
    499             } 
    500  
    501             if (leftLeaf->_vertexIndices.empty()) 
    502             { 
    503                 //osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl; 
    504                 kdTree.getNode(nodeNum).first = 0; 
    505                 kdTree.getNode(nodeNum).second = kdTree.replaceLeaf(nodeIndex, rightLeaf.get()); 
    506             } 
    507             else if (rightLeaf->_vertexIndices.empty()) 
    508             { 
    509                 //osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl; 
    510                 kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf.get()); 
    511                 kdTree.getNode(nodeNum).second = 0; 
    512             } 
    513             else 
    514             { 
    515                 kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf.get()); 
    516                 kdTree.getNode(nodeNum).second = kdTree.addLeaf(rightLeaf.get()); 
    517             } 
    518         } 
    519 #else 
    520372        { 
    521373            KDLeaf& leaf = kdTree.getLeaf(nodeIndex); 
     
    591443            } 
    592444        } 
    593 #endif 
     445 
    594446         
    595447        int originalLeftChildIndex = kdTree.getNode(nodeNum).first;