Changeset 224 for trunk


Ignore:
Timestamp:
08/09/05 18:39:28 (19 years ago)
Author:
mattausch
Message:

added stuff for bsp tree

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

Legend:

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

    r176 r224  
    1313  KdPvs mKdPvs; 
    1414   
    15   enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE }; 
     15  enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEWCELL }; 
    1616   
    1717  Intersectable():mailbox(0) {} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

    r221 r224  
    11#ifndef _ViewCell_H__ 
    22#define _ViewCell_H__ 
     3 
     4#include "Intersectable.h" 
    35 
    46class Mesh; 
     
    1113        View cell represented as a mesh 
    1214*/ 
    13 class ViewCell 
     15class ViewCell: public Intersectable 
    1416{ 
    1517public: 
     
    2830        BspPvs *GetPVS() {return mPvs;} 
    2931 
     32        AxisAlignedBox3 GetBox()  {return mMesh->mBox;} 
     33   
     34        int CastRay(Ray &ray) {return 0;} 
     35   
     36        bool IsConvex() {return mMesh->mIsConvex;} 
     37        bool IsWatertight() {return mMesh->mIsWatertight;} 
     38        float IntersectionComplexity() {return mMesh->mFaces.size();} 
     39 
     40        int Type() const { return VIEWCELL; } 
     41 
     42        void GetRandomSurfacePoint(Vector3 &point, Vector3 &normal) {point = Vector3(0,0,0);}; 
     43 
    3044protected: 
    3145 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r222 r224  
    66#include <stack> 
    77 
     8#define DEL_PTR(ptr) while (0) {if (ptr) {delete (ptr); (ptr) = NULL;}} 
     9 
    810//namespace GtpVisibilityPreprocessor { 
    911/****************************************************************/ 
     
    1517} 
    1618 
     19BspInterior *BspNode::GetParent()  
     20{  
     21        return mParent;  
     22} 
    1723/****************************************************************/ 
    1824/*              class BspInterior implementation                */ 
     
    6167} 
    6268 
    63  
    6469/****************************************************************/ 
    6570/*                  class BspLeaf implementation                */ 
     
    8489/****************************************************************/ 
    8590 
    86 BspTree::BspTree(ViewCell *cell)  
    87 { 
    88         mRootCell = cell; 
    89         mRoot = new BspLeaf(mRootCell); 
    90 } 
    91  
    92    
    93 void BspTree::Subdivide() 
     91BspTree::BspTree(const ViewCellContainer &viewCells):  
     92mMaxPolys(0), mMaxDepth(0), mRoot(NULL) 
     93{ 
     94        //mRootCell = cell; 
     95        Subdivide(viewCells); 
     96} 
     97 
     98BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth): 
     99mMaxPolys(maxPolys), mMaxDepth(maxDepth) 
     100{ 
     101        mRoot = new BspLeaf(); 
     102 
     103        Subdivide(objects); 
     104} 
     105  
     106BspTree::~BspTree() 
     107{ 
     108        std::stack<BspNode *> tStack; 
     109 
     110        tStack.push(mRoot); 
     111 
     112        while (!tStack.empty()) 
     113        { 
     114                BspNode *node = tStack.top(); 
     115 
     116            tStack.pop(); 
     117         
     118                if (!node->IsLeaf()) 
     119                { 
     120                        BspInterior *interior = dynamic_cast<BspInterior *>(node); 
     121 
     122                        // push the children on the stack (there are always two children) 
     123                        interior->GetBack()->mParent = NULL; 
     124                        interior->GetFront()->mParent = NULL; 
     125 
     126                        tStack.push(interior->GetBack()); 
     127                        tStack.push(interior->GetFront()); 
     128                } 
     129 
     130                delete node; 
     131                node = NULL; 
     132        } 
     133} 
     134 
     135 
     136void BspTree::InsertViewCell(ViewCell *viewCell) 
    94137{ 
    95138        BspNode *currentNode = mRoot; 
     
    103146        { 
    104147            BspTraversalData data = tStack.top(); 
     148 
    105149            tStack.pop(); 
    106150     
     
    112156                        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode), 
    113157                                                                                  data.mParent, 
    114                                                                                   &data.mViewCell, 
     158                                                                                  data.mPolys, 
    115159                                                                              data.mDepth, 
    116160                                                                                  backPolys, 
     
    122166 
    123167                                // push the children on the stack (there are always two children) 
    124                                 tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1)); 
    125                                 tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1)); 
     168                                //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1)); 
     169                                //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1)); 
    126170                        } 
    127171                } 
     
    129173} 
    130174 
    131 Plane3 BspTree::SelectPlane(Mesh *polys) 
     175void BspTree::Subdivide(const ViewCellContainer &viewCells) 
     176{ 
     177} 
     178 
     179void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh) 
     180{ 
     181        ObjectContainer::const_iterator it, it_end = objects.end(); 
     182 
     183        for (it = objects.begin(); it != it_end; ++ it) 
     184        { 
     185                FaceContainer::const_iterator fi; 
     186                Intersectable *object = *it; 
     187 
     188                // extract the mesh instances 
     189                if (object->Type() == Intersectable::MESH_INSTANCE) 
     190                { 
     191                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object); 
     192 
     193                        Mesh *polys = inst->GetMesh(); 
     194 
     195                        // copy the face data 
     196                        for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi) 
     197                        { 
     198                                Face *face = new Face((*fi)->mVertexIndices); 
     199                                mesh.AddFace(face); 
     200                        } 
     201                } 
     202        } 
     203} 
     204 
     205void BspTree::Subdivide(const ObjectContainer &objects) 
     206{ 
     207        std::stack<BspTraversalData> tStack; 
     208        Mesh polys; 
     209         
     210        // copy mesh instance polygons into one big polygon soup 
     211        Copy2PolygonSoup(objects, polys); 
     212 
     213        BspTraversalData tdata(mRoot, mRoot->GetParent(), &polys, 0); 
     214        tStack.push(tdata); 
     215 
     216        while (!tStack.empty())  
     217        { 
     218            BspTraversalData data = tStack.top(); 
     219 
     220            tStack.pop(); 
     221     
     222                Mesh backPolys; 
     223                Mesh frontPolys; 
     224 
     225                BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode), 
     226                                                                          data.mParent, 
     227                                                                          data.mPolys, 
     228                                                                      data.mDepth, 
     229                                                                          backPolys, 
     230                                                                          frontPolys); 
     231         
     232                if (!node->IsLeaf()) // node was subdivided 
     233                { 
     234                        BspInterior *interior = dynamic_cast<BspInterior *>(node); 
     235 
     236                        // push the children on the stack (there are always two children) 
     237                        tStack.push(BspTraversalData(interior->GetBack(), interior, &backPolys, data.mDepth + 1)); 
     238                        tStack.push(BspTraversalData(interior->GetFront(), interior, &frontPolys, data.mDepth + 1)); 
     239                } 
     240        } 
     241} 
     242 
     243Plane3 BspTree::SelectPlane(Mesh *polys)  
    132244{ 
    133245        // TODO: more sophisticated criteria 
     
    136248 
    137249BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent,  
    138                                                                 Mesh *viewCell, const int depth,  
     250                                                                Mesh *polys, const int depth,  
    139251                                                                Mesh &frontPolys, Mesh &backPolys) 
    140252{ 
    141         ViewCell *viewCell = leaf->GetViewCell(); 
    142  
    143         // terminate traversal if no more faces in mesh or outside 
    144         if (!viewCell || (viewCell->mFaces.size() == 0)) 
    145         { 
     253        // terminate traversal if no more faces in mesh 
     254        if ((polys->mFaces.size() <= mMaxPolys) || (depth >= mMaxDepth)) 
     255        { 
     256                // don't need to store polygon information 
     257                polys->mFaces->clear(); // HACK: faces were deleted before 
     258                DEL_PTR(polys); // we can savely delete mesh 
     259 
    146260                return leaf; 
    147261        } 
     262 
    148263        // add the new nodes to the tree + select subdivision plane 
    149         BspInterior *node = new BspInterior(SelectPlane(viewCell));  
     264        BspInterior *node = new BspInterior(SelectPlane(polys));  
    150265 
    151266        FaceContainer::const_iterator fi; 
    152267 
    153         for (fi = viewCell->mFaces.begin(); fi != viewCell->mFaces.end(); ++ fi) 
    154         { 
    155                 int  result = node->GetPlane()->Side(); 
    156                 Mesh *front_piece, *back_piece; 
     268        for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi) 
     269        { 
     270                Face *face = (*fi); 
     271 
     272                int  result = 0;// = node->GetPlane()->Side(node->GetPlane()); 
     273 
     274                Face *front_piece, *back_piece; 
    157275 
    158276                switch (result) 
    159277                { 
    160278                        case 1: 
    161                                 frontPolys.AddFace(poly); 
     279                                frontPolys.AddFace(face); 
    162280                                break; 
    163281                        case -1: 
    164                                 backPolys.AddFace(poly); 
     282                                backPolys.AddFace(face); 
    165283                                break; 
    166284                        case 0: 
    167                                 //Split_Polygon (poly, tree->partition, front_piece, back_piece); 
     285                                //Split_Polygon (face, tree->partition, front_piece, back_piece); 
    168286                                backPolys.AddFace(back_piece); 
    169287                                frontPolys.AddFace(front_piece); 
     288 
     289                                // face not needed anymore 
     290                                DEL_PTR(face); 
     291 
    170292                                break; 
    171                         default; 
    172                                 brak; 
    173                 } 
    174         } 
     293                        default: 
     294                                break; 
     295                } 
     296        } 
     297 
    175298        // backside of convex view cell polygon => outside 
    176         BspLeaf *back = new BspLeaf(NULL); 
    177         BspLeaf *front = new BspLeaf(viewCell); 
     299        BspLeaf *back = new BspLeaf(); 
     300        BspLeaf *front = new BspLeaf(); 
    178301 
    179302        // replace a link from node's parent 
     
    185308        // and setup child links 
    186309        node->SetupChildLinks(back, front); 
    187    
    188         delete leaf; 
     310 
     311        // don't need to store polygon information 
     312        polys->mFaces->clear(); // HACK: faces were deleted before 
     313        DEL_PTR(polys); // we can savely delete mesh 
     314 
     315        DEL_PTR(leaf); 
     316 
    189317        return node; 
    190318} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r222 r224  
    33 
    44#include "Mesh.h" 
     5#include "Containers.h" 
     6 
     7 
    58class ViewCell; 
    69class Plane3; 
     
    811 
    912//namespace GtpVisibilityPreprocessor { 
    10    
     13class BspTree;   
    1114class BspInterior; 
    1215 
     
    1720  class BspNode  
    1821  { 
     22          friend BspTree; 
     23 
    1924  public: 
    2025          /** Determines whether this node is a leaf or not 
     
    2833          virtual bool IsRoot() const; 
    2934 
     35          /** Returns parent node. 
     36          */ 
     37          BspInterior *GetParent(); 
     38           
    3039  protected: 
    3140 
     
    3443  }; 
    3544 
    36   /** BSP interior node implementation */ 
     45  /** BSP interior node implementation  
     46  */ 
    3747  class BspInterior : public BspNode  
    38   {    
     48  { 
    3949  public: 
    40           BspInterior(Plane3 plane): mPlane(plane) {} 
    41           /** @return false since it is an interior node */ 
     50          /** Standard contructor taking split plane as argument. 
     51          */ 
     52          BspInterior(Plane3 plane); 
     53          /** @return false since it is an interior node  
     54          */ 
    4255          bool IsLeaf() const; 
    4356 
    44           BspNode *GetBack() {return mBack;} 
    45           BspNode *GetFront() {return mFront;} 
     57          BspNode *GetBack(); 
     58          BspNode *GetFront(); 
    4659 
    4760          Plane3 *GetPlane(); 
     
    7891  }; 
    7992   
    80   /** Implementation of the ViewCell BSP tree */ 
     93  /** Implementation of the ViewCell BSP tree. */ 
    8194  class BspTree  
    8295  { 
     
    8497          struct BspTraversalData 
    8598          {   
     99                  /// the current node 
    86100                  BspNode *mNode; 
     101                  /// parent of current node 
    87102                  BspInterior *mParent; 
    88  
    89                   Mesh mViewCell; 
     103                  /// polygonal data for splitting 
     104                  Mesh *mPolys; 
     105                  /// current depth 
    90106                  int mDepth; 
    91107                       
    92108                  BspTraversalData() {} 
    93                   BspTraversalData(BspNode *n, BspInterior *p, const Mesh &m, const int d):  
    94                   mNode(n), mParent(p), mViewCell(m), mDepth(d) {} 
     109                   
     110                  BspTraversalData(BspNode *node, BspInterior *parent, Mesh *polys, const int depth):  
     111                  mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {} 
    95112      }; 
    96113          
    97           /** Constructor takes a pointer to the cell corresponding to the whole 
    98           viewspace */ 
    99           BspTree(ViewCell *cell); 
    100          
     114          /** Constructs BSP tree from list of view cells. 
     115          */  
     116          BspTree(const ViewCellContainer &viewCells); 
     117          /** Constructs BSP tree from list of objects. 
     118                  @param object list of intersectables 
     119                  @param maxPolys maximal allowed number of polygons 
     120                  @param maxDepth maximal allowed BSP tree depth 
     121          */ 
     122          BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth); 
     123   
     124          ~BspTree(); 
     125 
    101126  protected: 
    102           /** Selects a splitting plane from the given polygons. */ 
     127          /** Selects a splitting plane from the given polygons.  
     128          */ 
    103129          Plane3 SelectPlane(Mesh *polys); 
    104130 
    105           void Subdivide(); 
     131          /** Filters next viewcell down the tree and inserts it into the appropriate leaves 
     132                  (i.e., possibly more than one leaf). 
     133          */ 
     134          void InsertViewCell(ViewCell *viewCell); 
     135 
     136          /** Subdivides tree according to the given list of viewcells. 
     137          */ 
     138          void Subdivide(const ViewCellContainer &viewCells); 
     139          /** Subdivides tree according to the given list of objects. 
     140          */ 
     141          void Subdivide(const ObjectContainer &objects); 
    106142            
     143          /** Subdivides leaf. 
     144                  @param leaf the leaf to be subdivided 
     145                  @param parent the parent node of this leaf 
     146                  @param polys the input polygons 
     147                  @param depth the current tree depth 
     148                  @param frontPolys the polygons of the front child node as a result from splitting 
     149                  @param backPolys the polygons of the back child node as a result from splitting 
     150          */ 
    107151          BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent,  
    108                                                          Mesh *viewCell, const int depth,  
     152                                                         Mesh *polys, const int depth,  
    109153                                                         Mesh &frontPolys, Mesh &backPolys); 
     154 
     155          /** Extracts the mesh instances of the objects and copies them into the mesh. 
     156          */ 
     157          static void Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh); 
     158 
    110159 
    111160          /// Pointer to the root of the tree 
    112161          BspNode *mRoot; 
    113162          /// Pointer to the root cell of the viewspace 
    114           ViewCell *mRootCell; 
     163          // ViewCell *mRootCell; 
     164          /// maximal number of polygons allowed in leaf 
     165          int mMaxPolys; 
     166          /// maximal depth 
     167          int mMaxDepth; 
    115168  }; 
    116169   
Note: See TracChangeset for help on using the changeset viewer.