Changeset 195 for trunk


Ignore:
Timestamp:
08/04/05 19:53:48 (19 years ago)
Author:
mattausch
Message:

added bsp tree stuff

Location:
trunk/VUT/GtpVisibilityPreprocessor/src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBSP.h

    r194 r195  
    22#define _ViewCellBsp_H__ 
    33 
     4#include "Mesh.h" 
    45class ViewCell; 
    56class Plane3; 
    6 class Mesh; 
     7//class Mesh; 
    78 
    89//namespace GtpVisibilityPreprocessor { 
     
    1011class BSPInterior; 
    1112 
    12 /** 
    13         BSPNode abstract class serving for interior and leaf node implementation 
    14 */ 
    15 class BSPNode  
    16 { 
    17 public: 
    18         /** Determines whether this node is a leaf or not 
    19         @return true if leaf 
    20     */ 
    21     virtual bool IsLeaf() const = 0; 
     13 
     14  /** 
     15     BSPNode abstract class serving for interior and leaf node implementation 
     16  */ 
     17  class BSPNode  
     18  { 
     19  public: 
     20          /** Determines whether this node is a leaf or not 
     21          @return true if leaf 
     22          */ 
     23          virtual bool IsLeaf() const = 0; 
    2224     
    23     /** Determines whether this node is a root 
    24         @return true if root 
    25     */ 
    26     virtual bool IsRoot() const; 
     25          /** Determines whether this node is a root 
     26          @return true if root 
     27          */ 
     28          virtual bool IsRoot() const; 
    2729 
    28         protected: 
     30  protected: 
    2931 
    30                 void SplitPoly(Plane3 *plane, Mesh *viewcell); 
    31  
    32     /// parent of this node 
    33     BSPInterior *mParent; 
     32          /// parent of this node 
     33          BSPInterior *mParent; 
    3434  }; 
    3535 
    3636  /** BSP interior node implementation */ 
    3737  class BSPInterior : public BSPNode  
    38   {     
    39     /** @return false since it is an interior node */ 
    40     bool IsLeaf() const; 
     38  {    
     39  public: 
     40          /** @return false since it is an interior node */ 
     41          bool IsLeaf() const; 
     42 
     43          BSPNode *GetBack() {return mBack;} 
     44          BSPNode *GetFront() {return mFront;} 
     45 
     46          void ReplaceChildLink(BSPNode *oldChild, BSPNode *newChild); 
     47          void SetupChildLinks(BSPNode *b, BSPNode *f); 
    4148 
    4249  protected: 
    43     /// Splitting plane corresponding to this node 
    44     Plane3 mPlane; 
    45     /// back node 
    46     BSPNode *mBack; 
    47     /// front node 
    48     BSPNode *mFront; 
     50                 
     51          /// Splitting plane corresponding to this node 
     52          Plane3 mPlane; 
     53          /// back node 
     54          BSPNode *mBack; 
     55          /// front node 
     56          BSPNode *mFront; 
    4957  }; 
    5058   
     
    5462  { 
    5563  public: 
    56         BSPLeaf(ViewCell *viewCell = NULL); 
     64          BSPLeaf(ViewCell *viewCell = NULL); 
    5765     
    58         /** @return true since it is an interior node */ 
    59     bool IsLeaf() const; 
     66          /** @return true since it is an interior node */ 
     67          bool IsLeaf() const; 
    6068 
    6169  protected: 
    62     /// polygonal representation of this viewcell 
    63     /// if NULL this note does not correspond to feasible viewcell 
    64     ViewCell *mViewCell; 
     70    
     71          /// polygonal representation of this viewcell 
     72          /// if NULL this note does not correspond to feasible viewcell 
     73          ViewCell *mViewCell; 
    6574  }; 
    6675   
     
    6978  { 
    7079  public: 
    71     /** Constructor takes a pointer to the cell corresponding to the whole 
    72         viewspace */ 
    73     BSPTree(ViewCell *cell); 
     80          struct BSPTraversalData 
     81          {   
     82                  BSPNode *mNode; 
     83                  BSPInterior *mParent; 
     84 
     85                  Mesh mViewCell; 
     86                  int mDepth; 
     87                       
     88                  BSPTraversalData() {} 
     89                  BSPTraversalData(BSPNode *n, BSPInterior *p, const Mesh &m, const int d):  
     90                  mNode(n), mParent(p), mViewCell(m), mDepth(d) {} 
     91      }; 
     92          
     93          /** Constructor takes a pointer to the cell corresponding to the whole 
     94          viewspace */ 
     95          BSPTree(ViewCell *cell); 
    7496         
    7597  protected: 
    76     /// Pointer to the root of the tree 
    77     BSPNode *mRoot; 
    78     /// Pointer to the root cell of the viewspace */ 
    79         ViewCell *mRootCell; 
     98            
     99          Plane3 *SelectPlane(Mesh *viewcell); 
     100           void Subdivide(); 
     101            
     102           BSPNode *SubdivideNode(BSPLeaf *leaf, BSPInterior *parent,  
     103                                                         Mesh *viewCell, const int depth,  
     104                                                         Mesh &frontPolys, Mesh &backPolys); 
     105 
     106          /// Pointer to the root of the tree 
     107          BSPNode *mRoot; 
     108          /// Pointer to the root cell of the viewspace 
     109          ViewCell *mRootCell; 
    80110  }; 
    81111   
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r194 r195  
    33#include "Mesh.h" 
    44 
    5 class ViewCell; 
    6  
     5#include "ViewCell.h" 
     6#include <stack> 
    77//namespace GtpVisibilityPreprocessor { 
    8  
     8/****************************************************************/ 
     9/*                  class BSPNode implementation                */ 
     10/****************************************************************/ 
    911bool BSPNode::IsRoot() const  
    1012{ 
     
    1214} 
    1315 
    14 void BSPNode::SplitPoly(Plane3 *plane, Mesh *viewcell) 
    15 { 
    16 } 
     16/****************************************************************/ 
     17/*              class BSPInterior implementation                */ 
     18/****************************************************************/ 
    1719 
    1820bool BSPInterior::IsLeaf() const 
     
    2022        return false;  
    2123} 
     24 
     25void BSPInterior::ReplaceChildLink(BSPNode *oldChild, BSPNode *newChild)  
     26{ 
     27        if (mBack == oldChild) 
     28        { 
     29                mBack = newChild; 
     30        } 
     31    else 
     32        { 
     33                mFront = newChild; 
     34        } 
     35} 
     36 
     37void BSPInterior::SetupChildLinks(BSPNode *b, BSPNode *f)  
     38{ 
     39    mBack = b; 
     40    mFront = f; 
     41} 
     42 
     43/****************************************************************/ 
     44/*                  class BSPLeaf implementation                */ 
     45/****************************************************************/ 
    2246 
    2347BSPLeaf::BSPLeaf(ViewCell *viewCell): mViewCell(viewCell)  
     
    3054} 
    3155 
     56/****************************************************************/ 
     57/*                  class BSPTree implementation                */ 
     58/****************************************************************/ 
     59 
    3260BSPTree::BSPTree(ViewCell *cell)  
    3361{ 
     
    3664} 
    3765 
     66   
     67void BSPTree::Subdivide() 
     68{ 
     69        BSPNode *currentNode = mRoot; 
     70   
     71        std::stack<BSPTraversalData> tStack; 
     72        //  stack<STraversalData> tStack; 
     73 
     74        //tStack.push(tdata); 
     75 
     76        while (!tStack.empty())  
     77        { 
     78            BSPTraversalData data = tStack.top(); 
     79            tStack.pop(); 
     80     
     81                Mesh backPolys; 
     82                Mesh frontPolys; 
     83 
     84                BSPNode *node = SubdivideNode(dynamic_cast<BSPLeaf *>(data.mNode), 
     85                                                                      data.mParent, 
     86                                                                          data.mDepth, 
     87                                                                          backPolys, 
     88                                                                          frontPolys); 
     89         
     90                if (!node->IsLeaf()) 
     91                { 
     92                        BSPInterior *interior = dynamic_cast<BSPInterior *>(node); 
     93 
     94                        // push the children on the stack 
     95                        if (interior->GetBack()) 
     96                                tStack.push(BSPTraversalData(interior->GetBack(), interior, backPolys, data.mDepth+1)); 
     97                        if (interior->GetFront()) 
     98                                tStack.push(BSPTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth+1)); 
     99                } 
     100        } 
     101} 
     102 
     103Plane3 *BSPTree::SelectPlane(Mesh *viewcell) 
     104{ 
     105        return viewcell->GetFacePlane(0); 
     106} 
     107 
     108BSPNode *BSPTree::SubdivideNode(BSPLeaf *leaf, BSPInterior *parent,  
     109                                                                Mesh *viewCell, const int depth,  
     110                                                                Mesh &frontPolys, Mesh &backPolys) 
     111{ 
     112static int sMaxDepth = 5; // HACK 
     113        // terminate traversal if no more faces in mesh 
     114        if ((viewCell->mFaces.size() == 0) && depth > sMaxDepth) 
     115                return leaf; 
     116  
     117        // add the new nodes to the tree 
     118        BSPInterior *node = new BSPInterior; 
     119   
     120        // select subdivision plane 
     121        node->mPlane = SelectPlane(viewCell); 
     122 
     123        FaceContainer::const_iterator fi; 
     124 
     125        for ( fi = viewCell->mFaces.begin(); fi != viewCell->mFaces.end(); ++ fi) 
     126        { 
     127        } 
     128   
     129        BSPLeaf *back = new BSPLeaf(mRootCell); 
     130        BSPLeaf *front = new BSPLeaf(mRootCell); 
     131 
     132        // replace a link from node's parent 
     133        if (parent) 
     134        { 
     135                parent->ReplaceChildLink(leaf, node); 
     136        } 
     137 
     138        // and setup child links 
     139        node->SetupChildLinks(back, front); 
     140   
     141        delete leaf; 
     142        return node; 
     143} 
     144 
    38145//} // GtpVisibilityPreprocessor 
Note: See TracChangeset for help on using the changeset viewer.