Changeset 234


Ignore:
Timestamp:
08/10/05 18:07:51 (19 years ago)
Author:
mattausch
Message:

added bsp tree stuff

Files:
9 edited

Legend:

Unmodified
Added
Removed
  • trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

    r225 r234  
    6363                                Name="VCCLCompilerTool" 
    6464                                AdditionalIncludeDirectories="..\support;..\support\devil\include;..\support\zlib\include;"$(QTDIR)\include";"$(QTDIR)\include\Qt";..\include" 
    65                                 PreprocessorDefinitions="WIN32;NDEBUG;_LIB" 
     65                                PreprocessorDefinitions="WIN32;NDEBUG;_LIB;DEST_BSP_VIEWCELLS" 
    6666                                RuntimeLibrary="2" 
    6767                                RuntimeTypeInfo="TRUE" 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

    r176 r234  
    1818Preprocessor::GenerateViewcells() 
    1919{ 
     20        ObjectContainer objects; 
     21        mSceneGraph->CollectObjects(&objects); 
     22        //mBspTree = new BspTree(objects); 
    2023   
    21   return true; 
     24        return true; 
    2225} 
    2326 
     
    6063} 
    6164 
     65bool 
     66Preprocessor::BuildBspTree() 
     67{ 
     68   
     69  return true; 
     70} 
     71 
     72 
    6273 
    6374void 
     
    6778} 
    6879 
     80void 
     81Preprocessor::BspTreeStatistics(ostream &s) 
     82{ 
     83//  s<<mBspTree->GetStatistics(); 
     84} 
    6985 
    7086bool 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h

    r221 r234  
    6060  virtual bool BuildKdTree(); 
    6161   
     62   /** Build the BSP tree of currently loaded occluders/occludees/viewcells. The construction 
     63      is driven by the environment settings, which also sais which of the three types of 
     64      entities should be used to drive the heuristical construction (only occluders by default) 
     65  */ 
     66  virtual bool BuildBspTree(); 
     67 
    6268  /** Compute visibility method. This method has to be reimplemented by the actual 
    6369      Preprocessor implementation (e.g. SamplingPreprocessor, ExactPreprocessor, 
     
    7581   
    7682  virtual void KdTreeStatistics(ostream &s); 
    77    
     83  virtual void BspTreeStatistics(ostream &s); 
     84 
    7885  /// scene graph loaded from file 
    7986  SceneGraph *mSceneGraph; 
     
    9097  ViewCellContainer mViewcells; 
    9198   
    92    
     99  BspTree * mBspTree; 
    93100   
    94101}; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r233 r234  
    247247 
    248248BspTree::BspTree(const ViewCellContainer &viewCells):  
    249 mMaxPolys(0), mMaxDepth(0), mRoot(NULL) 
     249mMaxPolys(0), mMaxDepth(999999), mRoot(NULL) // null => until we stripped all polygons 
    250250{ 
    251251        //mRootCell = cell; 
     
    298298        CopyMesh2Polygon(viewCell->GetMesh(), polys); 
    299299 
    300         tStack.push(BspTraversalData(mRoot, NULL, &polys, 0, viewCell)); 
     300        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0)); 
    301301 
    302302        while (!tStack.empty()) 
     
    318318 
    319319                        // push the children on the stack 
    320                         if (frontPolys->size() > 0) 
     320                        if (frontPolys->size() > 0) // if polygons on this side of bsp tree 
    321321                                tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), frontPolys, tData.mDepth + 1)); 
    322322                        else 
    323323                                delete frontPolys; 
    324324 
    325                         if (backPolys > 0) 
    326                                 tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1)); // TODO: really need to keep viewcell?? 
     325                        if (backPolys > 0) // if polygons on this side of bsp tree 
     326                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1)); 
    327327                        else 
    328328                                delete backPolys; 
     
    330330                else // reached leaf and must split 
    331331                { 
    332                         BuildTree(tStack, tData); 
    333                 } 
    334         } 
    335 /*      BspNode *currentNode = mRoot; 
    336    
    337         std::stack<BspTraversalData> tStack; 
    338         //  stack<STraversalData> tStack; 
    339  
    340         //tStack.push(tdata); 
    341  
    342         while (!tStack.empty())  
    343         { 
    344             BspTraversalData data = tStack.top(); 
    345  
    346             tStack.pop(); 
    347      
    348                 Mesh backPolys; 
    349                 Mesh frontPolys; 
    350  
    351                 if (data.mNode->IsLeaf()) // if we have a leaf => subdivide 
    352                 { 
    353                         BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode), 
    354                                                                                   data.mParent, 
    355                                                                                   data.mPolys, 
    356                                                                               data.mDepth, 
    357                                                                                   data.viewCell, 
    358                                                                                   backPolys, 
    359                                                                                   frontPolys); 
    360          
    361                         if (!node->IsLeaf()) // node was subdivided 
    362                         { 
    363                                 BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    364  
    365                                 // push the children on the stack (there are always two children) 
    366                                 //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1)); 
    367                                 //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1)); 
    368                         } 
    369                 } 
    370         }*/ 
     332                        BuildTree(tStack, tData, NULL); 
     333                } 
     334        } 
    371335} 
    372336 
     
    415379        Copy2PolygonSoup(objects, *polys); 
    416380 
    417         BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0, NULL); 
     381        BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0); 
    418382        tStack.push(tData); 
    419383 
     
    428392} 
    429393 
    430 void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData) 
     394void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData, ViewCell *viewCell) 
    431395{ 
    432396        PolygonQueue *backPolys = new PolygonQueue(); 
     
    437401                                                                  currentData.mPolys, 
    438402                                                                  currentData.mDepth, 
    439                                                                   currentData.mViewCell, 
     403                                                                  viewCell, 
    440404                                                                  backPolys, 
    441405                                                                  frontPolys); 
     
    446410 
    447411                // push the children on the stack (there are always two children) 
    448                 tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1, NULL)); 
    449                 tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1, currentData.mViewCell)); 
     412                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1)); 
     413                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1)); 
    450414        } 
    451415} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r233 r234  
    1717 
    1818typedef std::queue<Polygon *> PolygonQueue; 
     19 
     20class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics 
     21{ 
     22public: 
     23  // total number of nodes 
     24  int nodes; 
     25  // totals number of rays 
     26  int rays; 
     27  // total number of query domains 
     28  int queryDomains; 
     29  // total number of ray references 
     30  int rayRefs; 
     31  // refs in non empty leafs 
     32  int rayRefsNonZeroQuery; 
     33  // total number of query references 
     34  int objectRefs; 
     35  // nodes with zero queries 
     36  int zeroQueryNodes; 
     37  // max depth nodes 
     38  int maxDepthNodes; 
     39  // max number of rays per node 
     40  int maxObjectRefs; 
     41  // number of dynamically added ray refs 
     42  int addedRayRefs; 
     43  // number of dynamically removed ray refs 
     44  int removedRayRefs; 
     45   
     46  // Constructor 
     47  BspTreeStatistics()  
     48  { 
     49    Reset(); 
     50  } 
     51 
     52  int Nodes() const {return nodes;} 
     53  int Interior() const { return nodes/2; } 
     54  int Leaves() const { return (nodes/2) + 1; } 
     55 
     56  void Reset()  
     57  { 
     58          nodes = 0; 
     59 
     60          rays = queryDomains = 0; 
     61          rayRefs = rayRefsNonZeroQuery = objectRefs = 0; 
     62          zeroQueryNodes = 0; 
     63      maxDepthNodes = 0; 
     64      //minCostNodes = 0; 
     65          maxObjectRefs = 0; 
     66          addedRayRefs = removedRayRefs = 0; 
     67  } 
     68 
     69  void 
     70  Print(ostream &app) const; 
     71 
     72  friend ostream &operator<<(ostream &s, const BspTreeStatistics &stat) { 
     73    stat.Print(s); 
     74    return s; 
     75  } 
     76   
     77}; 
    1978 
    2079/** 
     
    179238        /** Builds a new extension of the tree. 
    180239        */ 
    181         void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData); 
     240        void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData, ViewCell *viewCell = NULL); 
    182241 
    183242        /** Selects a splitting plane from the given polygons.  
     
    232291        /// maximal depth 
    233292        int mMaxDepth; 
     293 
     294        BspTreeStatistics mStat; 
    234295}; 
    235296 
  • trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

    r191 r234  
    3030  p->KdTreeStatistics(cout); 
    3131 
     32#ifdef DEST_BSP_VIEWCELLS 
     33  p->GenerateViewcells(); 
     34  p->BspTreeStatistics(cout); 
     35#endif 
     36 
    3237  //  p->mSceneGraph->Export("soda.x3d"); 
    3338  if (0) { 
Note: See TracChangeset for help on using the changeset viewer.