Show
Ignore:
Timestamp:
07/03/08 12:24:20 (6 years ago)
Author:
robert
Message:

Implement an experiemental triangle kdtree building support

Files:
1 modified

Legend:

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

    r8520 r8526  
    2727#include <osg/io_utils> 
    2828#include <osg/Geometry> 
     29#include <osg/TriangleIndexFunctor> 
    2930 
    3031 
     
    4647typedef std::vector< value_type >   Indices; 
    4748 
    48 //#define VERBOSE_OUTPUT 
     49// #define VERBOSE_OUTPUT 
    4950 
    5051typedef std::pair< value_type, value_type> KDNode; 
    5152typedef std::pair< value_type, value_type> KDLeaf; 
    5253 
     54struct Triangle 
     55{ 
     56    Triangle(unsigned int p1, unsigned int p2, unsigned int p3): 
     57        _p1(p1), _p2(p2), _p3(p3) {} 
     58         
     59    bool operator < (const Triangle& rhs) const 
     60    { 
     61        if (_p1<rhs._p1) return true; 
     62        if (_p1>rhs._p1) return false; 
     63        if (_p2<rhs._p2) return true; 
     64        if (_p2>rhs._p2) return false; 
     65        return _p3<rhs._p3; 
     66    } 
     67     
     68    unsigned int _p1; 
     69    unsigned int _p2; 
     70    unsigned int _p3;     
     71}; 
     72 
     73 
     74class KDPrimitiveLeaf : public osg::Referenced 
     75{ 
     76    public: 
     77     
     78      KDPrimitiveLeaf() {} 
     79       
     80      Indices _indices; 
     81 
     82    protected: 
     83       
     84      virtual ~KDPrimitiveLeaf() {}     
     85}; 
    5386 
    5487class KDTree : public osg::Shape 
     
    98131        } 
    99132         
     133 
     134 
     135        /// note, leafNum is negative to distinguish from nodeNum 
     136        int addPrimitiveLeaf(KDPrimitiveLeaf* leaf) { int num = _primitiveList.size(); _primitiveList.push_back(leaf); return -(num+1); } 
     137 
     138        int replacePrimitiveLeaf(int leafNum, KDPrimitiveLeaf* leaf) 
     139        { 
     140            int num = -leafNum-1;  
     141             
     142            if (num>_primitiveList.size()-1) 
     143            { 
     144                osg::notify(osg::NOTICE)<<"Warning: replaceChild("<<leafNum<<", leaf), num = "<<num<<" _primitiveList.size()="<<_primitiveList.size()<<std::endl; 
     145                return leafNum; 
     146            } 
     147             
     148            _primitiveList[num] = leaf; return leafNum; 
     149        } 
     150 
     151 
     152        /// note, leafNum is negative to distinguish from nodeNum 
     153        KDPrimitiveLeaf* getPrimitiveLeaf(int leafNum) 
     154        { 
     155            int num = -leafNum-1; 
     156            if (num<0 || num>_primitiveList.size()-1) 
     157            { 
     158                osg::notify(osg::NOTICE)<<"Warning: getLeaf("<<leafNum<<", num = "<<num<<") _primitiveList.size()="<<_primitiveList.size()<<std::endl; 
     159            } 
     160 
     161            return _primitiveList[num].get(); 
     162        } 
     163 
    100164        int addNode(const KDNode& node) 
    101165        { 
     
    126190        osg::ref_ptr<osg::Vec3Array>        _vertices; 
    127191        Indices                             _vertexIndices; 
     192         
     193        typedef std::vector< osg::ref_ptr<KDPrimitiveLeaf> > KDPrimitiveList; 
     194        KDPrimitiveList                     _primitiveList; 
    128195}; 
    129196 
     
    152219                if (i==leaf.first) osg::notify(osg::NOTICE)<<tree._vertexIndices[i]; 
    153220                else osg::notify(osg::NOTICE)<<", "<<tree._vertexIndices[i];                 
     221            } 
     222 
     223            osg::notify(osg::NOTICE)<<"}"<<std::endl;; 
     224             
     225        } 
     226 
     227        void traverse(KDTree& tree, KDPrimitiveLeaf& leaf, unsigned int level) 
     228        { 
     229            output(level)<<"leaf("<<level<<") size()="<<leaf._indices.size()<<"{ "; 
     230 
     231            for(unsigned int i=0; i<leaf._indices.size(); ++i) 
     232            { 
     233                if (i==0) osg::notify(osg::NOTICE)<<leaf._indices[i]; 
     234                else osg::notify(osg::NOTICE)<<", "<<leaf._indices[i];                 
    154235            } 
    155236 
     
    174255            { 
    175256                value_type leafIndex = -nodeIndex-1; 
    176  
    177                 KDLeaf& leaf = tree._kdLeaves[leafIndex]; 
    178  
    179                 traverse(tree, leaf, level); 
     257                 
     258                if (leafIndex<tree._primitiveList.size()) 
     259                { 
     260                    KDPrimitiveLeaf& leaf = *(tree._primitiveList[leafIndex]); 
     261                    traverse(tree, leaf, level); 
     262                } 
     263                else 
     264                { 
     265                    KDLeaf& leaf = tree._kdLeaves[leafIndex]; 
     266                    traverse(tree, leaf, level); 
     267                } 
     268 
    180269            } 
    181270 
     
    199288}; 
    200289 
    201  
    202290class KDTreeBuilder : public osg::NodeVisitor 
    203291{ 
     
    206294        KDTreeBuilder(): 
    207295            osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN), 
    208             _maxNumLevels(24), 
     296            _maxNumLevels(16), 
    209297            _targetNumVerticesPerLeaf(8), 
    210             _numVerticesProcessed(0) 
     298            _targetNumIndicesPerLeaf(15), 
     299            _numVerticesProcessed(0), 
     300            _processTriangles(true) 
    211301        {             
    212302        } 
     
    229319        void computeDivisions(KDTree& kdTree); 
    230320         
    231         int divide(KDTree& kdTree, osg::BoundingBox& bb, int nodeIndex, unsigned int level); 
     321        int divideTriangles(KDTree& kdTree, osg::BoundingBox& bb, int nodeIndex, unsigned int level); 
     322        int dividePoints(KDTree& kdTree, osg::BoundingBox& bb, int nodeIndex, unsigned int level); 
    232323 
    233324        unsigned int _maxNumLevels; 
    234325        unsigned int _targetNumVerticesPerLeaf; 
    235          
    236         unsigned int _numVerticesProcessed;    
     326        unsigned int _targetNumIndicesPerLeaf; 
     327         
     328        unsigned int _numVerticesProcessed; 
     329        bool         _processTriangles; 
     330         
     331        inline void disposeKDPrimitiveLeaf(KDPrimitiveLeaf* leaf) 
     332        { 
     333            leaf->_indices.clear(); 
     334            _leafRecycleList.push_back(leaf); 
     335        } 
     336         
     337        inline KDPrimitiveLeaf* createKDPrimitiveLeaf() 
     338        { 
     339            if (_leafRecycleList.empty()) return new KDPrimitiveLeaf; 
     340            osg::ref_ptr<KDPrimitiveLeaf> leaf = _leafRecycleList.back(); 
     341            _leafRecycleList.pop_back(); 
     342            return leaf.release(); 
     343        } 
     344         
     345        typedef std::list< osg::ref_ptr<KDPrimitiveLeaf> > LeafRecyleList; 
     346        LeafRecyleList _leafRecycleList; 
    237347 
    238348}; 
    239349 
     350struct TriangleIndicesCollector 
     351{ 
     352    TriangleIndicesCollector(): 
     353        _indices(0) 
     354    { 
     355    } 
     356 
     357    inline void operator () (unsigned int v1, unsigned int v2, unsigned int v3) 
     358    { 
     359        _indices->push_back(v1); 
     360        _indices->push_back(v2); 
     361        _indices->push_back(v3); 
     362    } 
     363     
     364    Indices* _indices; 
     365 
     366}; 
    240367 
    241368KDTree* KDTreeBuilder::createKDTree(osg::Geometry* geometry) 
     
    247374    osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray()); 
    248375    if (!vertices) return 0; 
     376     
     377    if (vertices->size() <= _targetNumVerticesPerLeaf) return 0; 
    249378 
    250379    osg::ref_ptr<KDTree> kdTree = new KDTree; 
     
    253382    kdTree->_vertices = vertices; 
    254383     
    255     unsigned int estimatedSize = (unsigned int)(float(vertices->size())/float(_targetNumVerticesPerLeaf)*1.5); 
     384    unsigned int estimatedSize = (unsigned int)(2.0*float(vertices->size())/float(_targetNumVerticesPerLeaf)); 
    256385 
    257386#ifdef VERBOSE_OUTPUT     
     
    267396    _numVerticesProcessed += vertices->size(); 
    268397 
    269     kdTree->_vertexIndices.reserve(vertices->size()); 
    270     for(unsigned int i=0; i<vertices->size(); ++i) 
     398    if (_processTriangles) 
    271399    { 
    272         kdTree->_vertexIndices.push_back(i); 
    273     } 
    274      
    275     KDLeaf leaf(0, kdTree->_vertexIndices.size()); 
    276  
    277     int leafNum = kdTree->addLeaf(leaf); 
    278     osg::BoundingBox bb = kdTree->_bb; 
    279     int nodeNum = divide(*kdTree, bb, leafNum, 0); 
    280  
    281  
    282  
    283      
    284 #ifdef VERBOSE_OUTPUT     
    285     osg::notify(osg::NOTICE)<<"Root nodeNum="<<nodeNum<<std::endl; 
    286 #endif 
     400 
     401        osg::TriangleIndexFunctor<TriangleIndicesCollector> collectTriangleIndices; 
     402        collectTriangleIndices._indices = &(kdTree->_vertexIndices); 
     403        geometry->accept(collectTriangleIndices); 
     404 
     405        KDPrimitiveLeaf* primitiveLeaf = createKDPrimitiveLeaf(); 
     406        primitiveLeaf->_indices.insert(primitiveLeaf->_indices.end(), 
     407                                       kdTree->_vertexIndices.begin(), 
     408                                       kdTree->_vertexIndices.end()); 
     409 
     410        // osg::notify(osg::NOTICE)<<"kdTree->_vertexIndices.size()="<<kdTree->_vertexIndices.size()<<std::endl; 
     411        int leafNum = kdTree->addPrimitiveLeaf(primitiveLeaf); 
     412 
     413        osg::BoundingBox bb = kdTree->_bb; 
     414        int nodeNum = divideTriangles(*kdTree, bb, leafNum, 0); 
     415     
     416        std::cout<<"_vertexIndices.size() = "<<kdTree->_vertexIndices.size()<<std::endl; 
     417        std::cout<<"_primtiveLeaf.size() = "<<kdTree->_primitiveList.size()<<std::endl; 
     418        unsigned int numIndices = 0; 
     419        for(KDTree::KDPrimitiveList::iterator itr = kdTree->_primitiveList.begin(); 
     420            itr != kdTree->_primitiveList.end(); 
     421            ++itr) 
     422        { 
     423            numIndices += (*itr)->_indices.size(); 
     424        } 
     425        std::cout<<"total numIndices = "<<numIndices<<std::endl; 
     426 
     427        typedef std::map<Triangle, unsigned int> TriangleMap; 
     428        TriangleMap triangleMap; 
     429        for(KDTree::KDPrimitiveList::iterator itr = kdTree->_primitiveList.begin(); 
     430            itr != kdTree->_primitiveList.end(); 
     431            ++itr) 
     432        { 
     433            Indices& indices = (*itr)->_indices; 
     434            for(unsigned int i=0; i<indices.size(); i+=3) 
     435            { 
     436                ++triangleMap[Triangle(indices[i],indices[i+1], indices[i+2])]; 
     437            } 
     438        } 
     439 
     440        int totalNumTriangles = triangleMap.size(); 
     441        int totalNumReferences = 0; 
     442        for(TriangleMap::iterator tm_itr = triangleMap.begin(); 
     443            tm_itr != triangleMap.end(); 
     444            ++tm_itr) 
     445        {    
     446            totalNumReferences += tm_itr->second; 
     447        } 
     448        std::cout<<"Average number of references = "<<double(totalNumReferences)/double(totalNumTriangles)<<std::endl; 
     449 
     450    } 
     451    else 
     452    { 
     453        kdTree->_vertexIndices.reserve(vertices->size()); 
     454        for(unsigned int i=0; i<vertices->size(); ++i) 
     455        { 
     456            kdTree->_vertexIndices.push_back(i); 
     457        } 
     458 
     459 
     460 
     461        KDLeaf leaf(0, kdTree->_vertexIndices.size()); 
     462 
     463        int leafNum = kdTree->addLeaf(leaf); 
     464 
     465        osg::BoundingBox bb = kdTree->_bb; 
     466        int nodeNum = dividePoints(*kdTree, bb, leafNum, 0); 
     467 
     468    #ifdef VERBOSE_OUTPUT     
     469        osg::notify(osg::NOTICE)<<"Root nodeNum="<<nodeNum<<std::endl; 
     470    #endif 
     471    } 
     472     
    287473     
    288474#ifdef VERBOSE_OUTPUT     
     
    291477    traverser.traverse(*kdTree); 
    292478     
     479     
    293480    osg::notify(osg::NOTICE)<<"Final kdTree->_kdNodes.size()="<<kdTree->_kdNodes.size()<<std::endl; 
    294481    osg::notify(osg::NOTICE)<<"Final kdTree->_kdLeaves.size()="<<kdTree->_kdLeaves.size()<<std::endl; 
     
    296483    osg::notify(osg::NOTICE)<<"osg::KDTreeBuilder::createKDTree() completed"<<std::endl<<std::endl; 
    297484#endif 
     485 
     486//    osg::notify(osg::NOTICE)<<"kdTree->_kdNodes.size()="<<kdTree->_kdNodes.size()<<"  estimated size = "<<estimatedSize<<std::endl; 
     487//    osg::notify(osg::NOTICE)<<"kdTree->_kdLeaves.size()="<<kdTree->_kdLeaves.size()<<"  estimated size = "<<estimatedSize<<std::endl<<std::endl; 
     488 
     489 
    298490 
    299491    return kdTree.release(); 
     
    339531} 
    340532 
    341 int KDTreeBuilder::divide(KDTree& kdTree, osg::BoundingBox& bb, int nodeIndex, unsigned int level) 
     533int KDTreeBuilder::divideTriangles(KDTree& kdTree, osg::BoundingBox& bb, int nodeIndex, unsigned int level) 
    342534{ 
    343535    if (kdTree._axisStack.size()<=level) return nodeIndex; 
     
    347539 
    348540#ifdef VERBOSE_OUTPUT     
    349     //osg::notify(osg::NOTICE)<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl; 
     541    osg::notify(osg::NOTICE)<<"divideTriangles("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl; 
    350542#endif 
    351543 
     
    361553    {     
    362554 
    363         if (kdTree.getLeaf(nodeIndex).second<=_targetNumVerticesPerLeaf) return nodeIndex; 
    364  
    365         //osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl; 
     555        if (kdTree.getPrimitiveLeaf(nodeIndex)->_indices.size()<=_targetNumIndicesPerLeaf) return nodeIndex; 
     556 
     557#ifdef VERBOSE_OUTPUT     
     558        osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl; 
     559#endif 
    366560         
    367561        int nodeNum = kdTree.addNode(KDNode()); 
     
    373567 
    374568        { 
     569            KDPrimitiveLeaf* leaf = kdTree.getPrimitiveLeaf(nodeIndex); 
     570 
     571            osg::Vec3Array* vertices = kdTree._vertices.get(); 
     572            Indices& indices = leaf->_indices; 
     573 
     574#ifdef VERBOSE_OUTPUT     
     575            osg::notify(osg::NOTICE)<<"  divide leaf->_indices.size()="<<leaf->_indices.size()<<std::endl; 
     576#endif 
     577 
     578            osg::ref_ptr<KDPrimitiveLeaf> leftLeaf = createKDPrimitiveLeaf(); 
     579            osg::ref_ptr<KDPrimitiveLeaf> rightLeaf = createKDPrimitiveLeaf(); 
     580 
     581            for(int i = 0; i<indices.size(); ) 
     582            { 
     583                int numLeft = 0; 
     584                int numRight = 0; 
     585 
     586                int i1 = indices[i++]; 
     587                if ((*vertices)[i1][axis]<=mid) ++numLeft; 
     588                else ++numRight; 
     589 
     590                int i2 = indices[i++]; 
     591                if ((*vertices)[i2][axis]<=mid) ++numLeft; 
     592                else ++numRight; 
     593 
     594                int i3 = indices[i++]; 
     595                if ((*vertices)[i3][axis]<=mid) ++numLeft; 
     596                else ++numRight; 
     597                 
     598                if (numLeft>0)  
     599                { 
     600                    leftLeaf->_indices.push_back(i1);                    leftLeaf->_indices.push_back(i2); 
     601                    leftLeaf->_indices.push_back(i3); 
     602                } 
     603                                 
     604                if (numRight>0)  
     605                { 
     606                    rightLeaf->_indices.push_back(i1); 
     607                    rightLeaf->_indices.push_back(i2); 
     608                    rightLeaf->_indices.push_back(i3); 
     609                } 
     610#if 0                 
     611                if (numRight>0 && numLeft>0)  
     612                { 
     613                    std::cout<<"In both"<<std::endl; 
     614                } 
     615                else 
     616                { 
     617                    std::cout<<"In one"<<std::endl; 
     618                } 
     619#endif 
     620            } 
     621 
     622            disposeKDPrimitiveLeaf(leaf); 
     623             
     624  
     625            if (leftLeaf->_indices.empty()) 
     626            { 
     627#ifdef VERBOSE_OUTPUT     
     628                osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl; 
     629#endif 
     630                kdTree.getNode(nodeNum).first = 0; 
     631                kdTree.getNode(nodeNum).second = kdTree.replacePrimitiveLeaf(nodeIndex, rightLeaf.get()); 
     632            } 
     633            else if (rightLeaf->_indices.empty()) 
     634            { 
     635#ifdef VERBOSE_OUTPUT     
     636                osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl; 
     637#endif 
     638                kdTree.getNode(nodeNum).first = kdTree.replacePrimitiveLeaf(nodeIndex, leftLeaf.get()); 
     639                kdTree.getNode(nodeNum).second = 0; 
     640            } 
     641            else 
     642            { 
     643                kdTree.getNode(nodeNum).first = kdTree.replacePrimitiveLeaf(nodeIndex, leftLeaf.get()); 
     644                kdTree.getNode(nodeNum).second = kdTree.addPrimitiveLeaf(rightLeaf.get()); 
     645            } 
     646        } 
     647         
     648 
     649         
     650        int originalLeftChildIndex = kdTree.getNode(nodeNum).first; 
     651        int originalRightChildIndex = kdTree.getNode(nodeNum).second; 
     652 
     653 
     654        float restore = bb._max[axis]; 
     655        bb._max[axis] = mid; 
     656 
     657        //osg::notify(osg::NOTICE)<<"  divide leftLeaf "<<kdTree.getNode(nodeNum).first<<std::endl; 
     658        int leftChildIndex = divideTriangles(kdTree, bb, originalLeftChildIndex, level+1); 
     659 
     660        bb._max[axis] = restore; 
     661         
     662        restore = bb._min[axis]; 
     663        bb._min[axis] = mid; 
     664 
     665        //osg::notify(osg::NOTICE)<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl; 
     666        int rightChildIndex = divideTriangles(kdTree, bb, originalRightChildIndex, level+1); 
     667         
     668        bb._min[axis] = restore; 
     669         
     670        kdTree.getNode(nodeNum).first = leftChildIndex; 
     671        kdTree.getNode(nodeNum).second = rightChildIndex;  
     672         
     673        return nodeNum;         
     674    } 
     675 
     676 
     677} 
     678 
     679 
     680 
     681int KDTreeBuilder::dividePoints(KDTree& kdTree, osg::BoundingBox& bb, int nodeIndex, unsigned int level) 
     682{ 
     683    if (kdTree._axisStack.size()<=level) return nodeIndex; 
     684 
     685 
     686    int axis = kdTree._axisStack[level]; 
     687 
     688#ifdef VERBOSE_OUTPUT     
     689    //osg::notify(osg::NOTICE)<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl; 
     690#endif 
     691 
     692    if (nodeIndex>=0) 
     693    { 
     694#ifdef VERBOSE_OUTPUT     
     695        osg::notify(osg::NOTICE)<<"  divide node"<<std::endl; 
     696#endif 
     697        KDNode& node = kdTree.getNode(nodeIndex); 
     698        return nodeIndex; 
     699    } 
     700    else 
     701    {     
     702 
     703        if (kdTree.getLeaf(nodeIndex).second<=_targetNumVerticesPerLeaf) return nodeIndex; 
     704 
     705        //osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl; 
     706         
     707        int nodeNum = kdTree.addNode(KDNode()); 
     708 
     709        float original_min = bb._min[axis]; 
     710        float original_max = bb._max[axis]; 
     711 
     712        float mid = (original_min+original_max)*0.5f; 
     713 
     714        { 
    375715            KDLeaf& leaf = kdTree.getLeaf(nodeIndex); 
    376716 
     
    378718 
    379719            //osg::notify(osg::NOTICE)<<"  divide leaf->_vertexIndices.size()="<<leaf->_vertexIndices.size()<<std::endl; 
    380  
    381             unsigned int estimatedSize = leaf.second; 
    382720 
    383721            int end = leaf.first+leaf.second-1; 
     
    455793 
    456794        //osg::notify(osg::NOTICE)<<"  divide leftLeaf "<<kdTree.getNode(nodeNum).first<<std::endl; 
    457         int leftChildIndex = divide(kdTree, bb, originalLeftChildIndex, level+1); 
     795        int leftChildIndex = dividePoints(kdTree, bb, originalLeftChildIndex, level+1); 
    458796 
    459797        bb._max[axis] = restore; 
     
    463801 
    464802        //osg::notify(osg::NOTICE)<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl; 
    465         int rightChildIndex = divide(kdTree, bb, originalRightChildIndex, level+1); 
     803        int rightChildIndex = dividePoints(kdTree, bb, originalRightChildIndex, level+1); 
    466804         
    467805        bb._min[axis] = restore; 
     
    483821    osg::ArgumentParser arguments(&argc,argv); 
    484822     
     823    osg::KDTreeBuilder builder; 
     824     
     825    while (arguments.read("--max",builder._maxNumLevels)) {} 
     826    while (arguments.read("--leaf",builder._targetNumIndicesPerLeaf)) {} 
     827    while (arguments.read("--points")) builder._processTriangles = false; 
     828    while (arguments.read("--triangles")) builder._processTriangles = true; 
     829 
    485830    osg::ref_ptr<osg::Node> scene = osgDB::readNodeFiles(arguments); 
    486831     
     
    500845    osg::Timer_t start = osg::Timer::instance()->tick(); 
    501846     
    502     osg::KDTreeBuilder builder; 
     847     
    503848    scene->accept(builder); 
    504849