Show
Ignore:
Timestamp:
09/30/03 15:48:58 (11 years ago)
Author:
robert
Message:

Added quad tree support into osgforest

Files:
1 modified

Legend:

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

    r2316 r2327  
    5252        unsigned int    _type; 
    5353    }; 
    54  
     54     
    5555    typedef std::vector< osg::ref_ptr<Tree> > TreeList; 
     56     
     57    class Cell : public osg::Referenced 
     58    { 
     59    public: 
     60        typedef std::vector< osg::ref_ptr<Cell> > CellList; 
     61 
     62        Cell():_parent(0) {} 
     63        Cell(osg::BoundingBox& bb):_parent(0), _bb(bb) {} 
     64         
     65        void addCell(Cell* cell) { cell->_parent=this; _cells.push_back(cell); } 
     66 
     67        void addTree(Tree* tree) { _trees.push_back(tree); } 
     68         
     69        void addTrees(const TreeList& trees) { _trees.insert(_trees.end(),trees.begin(),trees.end()); } 
     70         
     71        void computeBound(); 
     72         
     73        bool contains(const osg::Vec3& position) const { return _bb.contains(position); } 
     74         
     75        bool divide(unsigned int maxNumTreesPerCell=10); 
     76         
     77        bool devide(bool xAxis, bool yAxis, bool zAxis); 
     78         
     79        void bin(); 
     80 
     81 
     82        Cell*               _parent; 
     83        osg::BoundingBox    _bb; 
     84        CellList            _cells; 
     85        TreeList            _trees; 
     86         
     87    }; 
    5688 
    5789    float random(float min,float max) { return min + (max-min)*(float)rand()/(float)RAND_MAX; } 
     
    6597 
    6698    osg::Geometry* createOrthogonalQuads( const osg::Vec3& pos, float w, float h, osg::UByte4 color ); 
     99 
     100    osg::Node* createBillboardGraph(Cell* cell,osg::StateSet* stateset); 
     101 
     102    osg::Node* createXGraph(Cell* cell,osg::StateSet* stateset); 
     103 
     104    osg::Node* createTransformGraph(Cell* cell,osg::StateSet* stateset); 
    67105 
    68106    osg::Node* createScene(); 
     
    144182 
    145183 
     184void ForestTechniqueManager::Cell::computeBound() 
     185{ 
     186    _bb.init(); 
     187    for(CellList::iterator citr=_cells.begin(); 
     188        citr!=_cells.end(); 
     189        ++citr) 
     190    { 
     191        (*citr)->computeBound(); 
     192        _bb.expandBy((*citr)->_bb); 
     193    } 
     194 
     195    for(TreeList::iterator titr=_trees.begin(); 
     196        titr!=_trees.end(); 
     197        ++titr) 
     198    { 
     199        _bb.expandBy((*titr)->_position); 
     200    } 
     201} 
     202 
     203bool ForestTechniqueManager::Cell::divide(unsigned int maxNumTreesPerCell) 
     204{ 
     205 
     206    if (_trees.size()<=maxNumTreesPerCell) return false; 
     207 
     208    computeBound(); 
     209 
     210    float radius = _bb.radius(); 
     211    float divide_distance = radius*0.7f; 
     212    if (devide((_bb.xMax()-_bb.xMin())>divide_distance,(_bb.yMax()-_bb.yMin())>divide_distance,(_bb.zMax()-_bb.zMin())>divide_distance)) 
     213    { 
     214        // recusively divide the new cells till maxNumTreesPerCell is met. 
     215        for(CellList::iterator citr=_cells.begin(); 
     216            citr!=_cells.end(); 
     217            ++citr) 
     218        { 
     219            (*citr)->divide(maxNumTreesPerCell); 
     220        } 
     221        return true; 
     222   } 
     223   else 
     224   { 
     225        return false; 
     226   } 
     227} 
     228 
     229bool ForestTechniqueManager::Cell::devide(bool xAxis, bool yAxis, bool zAxis) 
     230{ 
     231    if (!(xAxis || yAxis || zAxis)) return false; 
     232 
     233    if (_cells.empty()) 
     234        _cells.push_back(new Cell(_bb)); 
     235 
     236    if (xAxis) 
     237    { 
     238        unsigned int numCellsToDivide=_cells.size(); 
     239        for(unsigned int i=0;i<numCellsToDivide;++i) 
     240        { 
     241            Cell* orig_cell = _cells[i].get(); 
     242            Cell* new_cell = new Cell(orig_cell->_bb); 
     243 
     244            float xCenter = (orig_cell->_bb.xMin()+orig_cell->_bb.xMax())*0.5f; 
     245            orig_cell->_bb.xMax() = xCenter; 
     246            new_cell->_bb.xMin() = xCenter; 
     247 
     248            _cells.push_back(new_cell); 
     249        } 
     250    } 
     251 
     252    if (yAxis) 
     253    { 
     254        unsigned int numCellsToDivide=_cells.size(); 
     255        for(unsigned int i=0;i<numCellsToDivide;++i) 
     256        { 
     257            Cell* orig_cell = _cells[i].get(); 
     258            Cell* new_cell = new Cell(orig_cell->_bb); 
     259 
     260            float yCenter = (orig_cell->_bb.yMin()+orig_cell->_bb.yMax())*0.5f; 
     261            orig_cell->_bb.yMax() = yCenter; 
     262            new_cell->_bb.yMin() = yCenter; 
     263 
     264            _cells.push_back(new_cell); 
     265        } 
     266    } 
     267 
     268    if (zAxis) 
     269    { 
     270        unsigned int numCellsToDivide=_cells.size(); 
     271        for(unsigned int i=0;i<numCellsToDivide;++i) 
     272        { 
     273            Cell* orig_cell = _cells[i].get(); 
     274            Cell* new_cell = new Cell(orig_cell->_bb); 
     275 
     276            float zCenter = (orig_cell->_bb.zMin()+orig_cell->_bb.zMax())*0.5f; 
     277            orig_cell->_bb.zMax() = zCenter; 
     278            new_cell->_bb.zMin() = zCenter; 
     279 
     280            _cells.push_back(new_cell); 
     281        } 
     282    } 
     283 
     284    bin(); 
     285 
     286    return true; 
     287 
     288} 
     289 
     290void ForestTechniqueManager::Cell::bin() 
     291{    
     292    // put trees in apprpriate cells. 
     293    TreeList treesNotAssigned; 
     294    for(TreeList::iterator titr=_trees.begin(); 
     295        titr!=_trees.end(); 
     296        ++titr) 
     297    { 
     298        Tree* tree = titr->get(); 
     299        bool assigned = false; 
     300        for(CellList::iterator citr=_cells.begin(); 
     301            citr!=_cells.end() && !assigned; 
     302            ++citr) 
     303        { 
     304            if ((*citr)->contains(tree->_position)) 
     305            { 
     306                (*citr)->addTree(tree); 
     307                assigned = true; 
     308            } 
     309        } 
     310        if (!assigned) treesNotAssigned.push_back(tree); 
     311    } 
     312 
     313    // put the unassigned trees back into the original local tree list. 
     314    _trees.swap(treesNotAssigned); 
     315 
     316 
     317    // prune empty cells. 
     318    CellList cellsNotEmpty; 
     319    for(CellList::iterator citr=_cells.begin(); 
     320        citr!=_cells.end(); 
     321        ++citr) 
     322    { 
     323        if (!((*citr)->_trees.empty())) 
     324        { 
     325            cellsNotEmpty.push_back(*citr); 
     326        } 
     327    } 
     328    _cells.swap(cellsNotEmpty); 
     329 
     330 
     331} 
     332 
    146333osg::Geode* ForestTechniqueManager::createTerrain(const osg::Vec3& origin, const osg::Vec3& size) 
    147334{ 
     
    391578} 
    392579 
     580osg::Node* ForestTechniqueManager::createBillboardGraph(Cell* cell,osg::StateSet* stateset) 
     581{ 
     582    bool needGroup = !(cell->_cells.empty()); 
     583    bool needBillboard = !(cell->_trees.empty()); 
     584     
     585    osg::Billboard* billboard = 0; 
     586    osg::Group* group = 0; 
     587     
     588    if (needBillboard) 
     589    { 
     590        billboard = new osg::Billboard; 
     591        billboard->setStateSet(stateset); 
     592        for(TreeList::iterator itr=cell->_trees.begin(); 
     593            itr!=cell->_trees.end(); 
     594            ++itr) 
     595        { 
     596            Tree& tree = **itr; 
     597            billboard->addDrawable(createSprite(tree._width,tree._height,tree._color),tree._position);     
     598        } 
     599    } 
     600     
     601    if (needGroup) 
     602    { 
     603        group = new osg::Group; 
     604        for(Cell::CellList::iterator itr=cell->_cells.begin(); 
     605            itr!=cell->_cells.end(); 
     606            ++itr) 
     607        { 
     608            group->addChild(createBillboardGraph(itr->get(),stateset)); 
     609        } 
     610         
     611        if (billboard) group->addChild(billboard); 
     612         
     613    } 
     614    if (group) return group; 
     615    else return billboard; 
     616} 
     617 
     618osg::Node* ForestTechniqueManager::createXGraph(Cell* cell,osg::StateSet* stateset) 
     619{ 
     620    bool needGroup = !(cell->_cells.empty()); 
     621    bool needTrees = !(cell->_trees.empty()); 
     622     
     623    osg::Geode* geode = 0; 
     624    osg::Group* group = 0; 
     625     
     626    if (needTrees) 
     627    { 
     628        geode = new osg::Geode; 
     629        geode->setStateSet(stateset); 
     630         
     631        for(TreeList::iterator itr=cell->_trees.begin(); 
     632            itr!=cell->_trees.end(); 
     633            ++itr) 
     634        { 
     635            Tree& tree = **itr; 
     636            geode->addDrawable(createOrthogonalQuads(tree._position,tree._width,tree._height,tree._color)); 
     637        } 
     638    } 
     639     
     640    if (needGroup) 
     641    { 
     642        group = new osg::Group; 
     643        for(Cell::CellList::iterator itr=cell->_cells.begin(); 
     644            itr!=cell->_cells.end(); 
     645            ++itr) 
     646        { 
     647            group->addChild(createXGraph(itr->get(),stateset)); 
     648        } 
     649         
     650        if (geode) group->addChild(geode); 
     651         
     652    } 
     653    if (group) return group; 
     654    else return geode; 
     655} 
     656 
     657osg::Node* ForestTechniqueManager::createTransformGraph(Cell* cell,osg::StateSet* stateset) 
     658{ 
     659    bool needGroup = !(cell->_cells.empty()); 
     660    bool needTrees = !(cell->_trees.empty()); 
     661     
     662    osg::Group* transform_group = 0; 
     663    osg::Group* group = 0; 
     664     
     665    if (needTrees) 
     666    { 
     667        transform_group = new osg::Group; 
     668         
     669        osg::Geometry* geometry = createOrthogonalQuads(osg::Vec3(0.0f,0.0f,0.0f),1.0f,1.0f,osg::UByte4(255,255,255,255)); 
     670         
     671        for(TreeList::iterator itr=cell->_trees.begin(); 
     672            itr!=cell->_trees.end(); 
     673            ++itr) 
     674        { 
     675            Tree& tree = **itr; 
     676            osg::MatrixTransform* transform = new osg::MatrixTransform; 
     677            transform->setMatrix(osg::Matrix::scale(tree._width,tree._width,tree._height)*osg::Matrix::translate(tree._position)); 
     678     
     679            osg::Geode* geode = new osg::Geode; 
     680            geode->setStateSet(stateset); 
     681            geode->addDrawable(geometry); 
     682            transform->addChild(geode); 
     683            transform_group->addChild(transform); 
     684        } 
     685    } 
     686     
     687    if (needGroup) 
     688    { 
     689        group = new osg::Group; 
     690        for(Cell::CellList::iterator itr=cell->_cells.begin(); 
     691            itr!=cell->_cells.end(); 
     692            ++itr) 
     693        { 
     694            group->addChild(createTransformGraph(itr->get(),stateset)); 
     695        } 
     696         
     697        if (transform_group) group->addChild(transform_group); 
     698         
     699    } 
     700    if (group) return group; 
     701    else return transform_group; 
     702} 
     703 
     704 
    393705osg::Node* ForestTechniqueManager::createScene() 
    394706{ 
     
    397709    unsigned int numTreesToCreates = 10000; 
    398710 
     711    std::cout<<"Creating terrain..."; 
    399712    osg::ref_ptr<osg::Node> terrain = createTerrain(origin,size); 
    400      
     713    std::cout<<"done."<<std::endl; 
     714     
     715    std::cout<<"Creating tree locations...";std::cout.flush(); 
    401716    TreeList trees; 
    402717    createTreeList(terrain.get(),origin,size,numTreesToCreates,trees); 
     718    std::cout<<"done."<<std::endl; 
     719     
     720    std::cout<<"Creating cell subdivision..."; 
     721    osg::ref_ptr<Cell> cell = new Cell; 
     722    cell->addTrees(trees); 
     723    cell->divide(); 
     724     std::cout<<"done."<<std::endl; 
     725    
    403726     
    404727    osg::Texture2D *tex = new osg::Texture2D; 
     
    424747    _techniqueSwitch = new osg::Switch; 
    425748     
    426     { 
    427         osg::Billboard* billboard = new osg::Billboard; 
    428         billboard->setStateSet(dstate); 
    429  
    430         for(TreeList::iterator itr=trees.begin(); 
    431             itr!=trees.end(); 
    432             ++itr) 
    433         { 
    434             Tree& tree = **itr; 
    435             billboard->addDrawable(createSprite(tree._width,tree._height,tree._color),tree._position);     
    436         } 
    437      
    438         _techniqueSwitch->addChild(billboard); 
    439     } 
    440  
    441     { 
    442         osg::Geode* geode = new osg::Geode; 
    443         geode->setStateSet(dstate); 
    444          
    445         for(TreeList::iterator itr=trees.begin(); 
    446             itr!=trees.end(); 
    447             ++itr) 
    448         { 
    449             Tree& tree = **itr; 
    450             geode->addDrawable(createOrthogonalQuads(tree._position,tree._width,tree._height,tree._color)); 
    451         } 
    452          
    453         _techniqueSwitch->addChild(geode); 
    454     } 
    455  
    456     { 
    457  
    458         osg::Group* transform_group = new osg::Group; 
    459         //group->setStateSet(dstate); 
    460          
    461         osg::Geometry* geometry = createOrthogonalQuads(osg::Vec3(0.0f,0.0f,0.0f),1.0f,1.0f,osg::UByte4(255,255,255,255)); 
    462          
    463         for(TreeList::iterator itr=trees.begin(); 
    464             itr!=trees.end(); 
    465             ++itr) 
    466         { 
    467             Tree& tree = **itr; 
    468             osg::MatrixTransform* transform = new osg::MatrixTransform; 
    469             transform->setMatrix(osg::Matrix::scale(tree._width,tree._width,tree._height)*osg::Matrix::translate(tree._position)); 
    470      
    471             osg::Geode* geode = new osg::Geode; 
    472             geode->setStateSet(dstate); 
    473             geode->addDrawable(geometry); 
    474             transform->addChild(geode); 
    475             transform_group->addChild(transform); 
    476         } 
    477          
    478         _techniqueSwitch->addChild(transform_group); 
    479     } 
     749    std::cout<<"Creating billboard based forest..."; 
     750   _techniqueSwitch->addChild(createBillboardGraph(cell.get(),dstate)); 
     751    std::cout<<"done."<<std::endl; 
     752 
     753    std::cout<<"Creating double quad based forest..."; 
     754   _techniqueSwitch->addChild(createXGraph(cell.get(),dstate)); 
     755    std::cout<<"done."<<std::endl; 
     756 
     757    std::cout<<"Creating transform based forest..."; 
     758   _techniqueSwitch->addChild(createTransformGraph(cell.get(),dstate)); 
     759    std::cout<<"done."<<std::endl; 
    480760     
    481761    _currentTechnique = 0;