Ignore:
Timestamp:
08/10/05 17:09:29 (19 years ago)
Author:
mattausch
Message:

updated bsp viewcells

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r225 r233  
    55#include "Containers.h" 
    66#include <queue> 
     7#include <stack> 
    78 
    89class ViewCell; 
    … …  
    1516class Polygon; 
    1617 
    17   /** 
    18      BspNode abstract class serving for interior and leaf node implementation 
    19   */ 
    20   class BspNode  
    21   { 
    22           friend BspTree; 
    23  
    24   public: 
    25           /** Determines whether this node is a leaf or not 
    26           @return true if leaf 
    27           */ 
    28           virtual bool IsLeaf() const = 0; 
    29      
    30           /** Determines whether this node is a root 
    31           @return true if root 
    32           */ 
    33           virtual bool IsRoot() const; 
    34  
    35           /** Returns parent node. 
    36           */ 
    37           BspInterior *GetParent(); 
    38            
    39   protected: 
    40  
    41           /// parent of this node 
    42           BspInterior *mParent; 
    43   }; 
    44  
    45   /** BSP interior node implementation  
    46   */ 
    47   class BspInterior : public BspNode  
    48   { 
    49   public: 
    50           /** Standard contructor taking split plane as argument. 
    51           */ 
    52           BspInterior(Plane3 plane); 
    53           /** @return false since it is an interior node  
    54           */ 
    55           bool IsLeaf() const; 
    56  
    57           BspNode *GetBack(); 
    58           BspNode *GetFront(); 
    59  
    60           Plane3 *GetPlane(); 
    61  
    62           void ReplaceChildLink(BspNode *oldChild, BspNode *newChild); 
    63           void SetupChildLinks(BspNode *b, BspNode *f); 
    64  
    65   protected: 
     18typedef std::queue<Polygon *> PolygonQueue; 
     19 
     20/** 
     21    BspNode abstract class serving for interior and leaf node implementation 
     22*/ 
     23class BspNode  
     24{ 
     25        friend BspTree; 
     26 
     27public: 
     28        /** Determines whether this node is a leaf or not 
     29        @return true if leaf 
     30        */ 
     31        virtual bool IsLeaf() const = 0; 
     32 
     33        /** Determines whether this node is a root 
     34        @return true if root 
     35        */ 
     36        virtual bool IsRoot() const; 
     37 
     38        /** Returns parent node. 
     39        */ 
     40        BspInterior *GetParent(); 
     41         
     42protected: 
     43 
     44        /// parent of this node 
     45        BspInterior *mParent; 
     46}; 
     47 
     48/** BSP interior node implementation  
     49*/ 
     50class BspInterior : public BspNode  
     51{ 
     52public: 
     53        /** Standard contructor taking split plane as argument. 
     54        */ 
     55        BspInterior(Plane3 plane); 
     56        /** @return false since it is an interior node  
     57        */ 
     58        bool IsLeaf() const; 
     59 
     60        BspNode *GetBack(); 
     61        BspNode *GetFront(); 
     62 
     63        Plane3 *GetPlane(); 
     64 
     65        void ReplaceChildLink(BspNode *oldChild, BspNode *newChild); 
     66        void SetupChildLinks(BspNode *b, BspNode *f); 
     67 
     68        /** Splits polygons. 
     69                @param polys the polygons to be split 
     70                @param frontPolys returns the polygons in the front of the split plane 
     71                @param backPolys returns the polygons in the back of the split plane 
     72        */ 
     73        void SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys); 
     74 
     75protected: 
     76         
     77        /// Splitting plane corresponding to this node 
     78        Plane3 mPlane; 
     79        /// back node 
     80        BspNode *mBack; 
     81        /// front node 
     82        BspNode *mFront; 
     83}; 
     84 
     85 
     86/** BSP leaf node implementation */ 
     87class BspLeaf : public BspNode  
     88{ 
     89public: 
     90        BspLeaf(ViewCell *viewCell = NULL); 
     91 
     92        /** @return true since it is an interior node */ 
     93        bool IsLeaf() const; 
     94        ViewCell *GetViewCell(); 
     95 
     96protected: 
     97 
     98        /// polygonal representation of this viewcell 
     99        /// if NULL this note does not correspond to feasible viewcell 
     100        ViewCell *mViewCell; 
     101}; 
     102 
     103 
     104/** Class representing a polygon. 
     105*/ 
     106class Polygon 
     107{ 
     108public: 
     109        Polygon(); 
     110        Polygon(const VertexContainer &vertices); 
     111 
     112        /** Copies all the vertices of the face. 
     113        */ 
     114        Polygon(Face *face, Mesh *parent); 
     115         
     116        /** Returns supporting plane of this polygon. 
     117        */ 
     118        Plane3 GetSupportingPlane(); 
     119 
     120        /** Splits polygon. 
     121                @param partition the split plane 
     122                @param front the front polygon 
     123                @param back the back polygon 
     124        */ 
     125        void Split(Plane3 *partition, Polygon *front, Polygon *back); 
     126 
     127        enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT}; 
     128 
     129        /** Side of the plane where the polygon is located. 
     130            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT 
     131        */ 
     132        int Side(Plane3 *plane); 
     133 
     134        static void DeletePolygons(PolygonQueue *polys); 
     135 
     136        /// vertices are connected in counterclockwise order. 
     137        VertexContainer mVertices; 
     138}; 
     139 
     140/** Implementation of the ViewCell BSP tree. */ 
     141class BspTree  
     142{ 
     143public: 
     144                 
     145        /** Additional data which is passed down the BSP tree during traversal. 
     146        */ 
     147        struct BspTraversalData 
     148        {   
     149                /// the current node 
     150                BspNode *mNode; 
     151                /// parent of current node 
     152                BspInterior *mParent; 
     153                /// polygonal data for splitting 
     154                PolygonQueue *mPolys; 
     155                /// current depth 
     156                int mDepth; 
    66157                 
    67           /// Splitting plane corresponding to this node 
    68           Plane3 mPlane; 
    69           /// back node 
    70           BspNode *mBack; 
    71           /// front node 
    72           BspNode *mFront; 
    73   }; 
    74    
    75    
    76   /** BSP leaf node implementation */ 
    77   class BspLeaf : public BspNode  
    78   { 
    79   public: 
    80           BspLeaf(ViewCell *viewCell = NULL); 
    81      
    82           /** @return true since it is an interior node */ 
    83           bool IsLeaf() const; 
    84           ViewCell *GetViewCell(); 
    85  
    86   protected: 
    87     
    88           /// polygonal representation of this viewcell 
    89           /// if NULL this note does not correspond to feasible viewcell 
    90           ViewCell *mViewCell; 
    91   }; 
    92    
    93   typedef std::queue<Polygon *> PolygonQueue; 
    94  
    95   /** Class representing a polygon. 
    96   */ 
    97   class Polygon 
    98   { 
    99   public: 
    100           Polygon(); 
    101           Polygon(const VertexContainer &vertices); 
    102  
    103           /** Copies all the vertices of the face. 
    104           */ 
    105           Polygon(Face *face, Mesh *parent); 
    106           
    107            /** Returns supporting plane of this polygon. 
    108           */ 
    109           Plane3 GetSupportingPlane(); 
    110  
    111           /** Splits polygon. 
    112                   @param partition the split plane 
    113                   @param front the front polygon 
    114                   @param back the back polygon 
    115           */ 
    116           void Split(Plane3 *partition, Polygon *front, Polygon *back); 
    117  
    118           enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT}; 
    119  
    120           /** Side of the plane where the polygon is located. 
    121               @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT 
    122           */ 
    123           int Side(Plane3 *plane); 
    124  
    125           static void DeletePolygons(PolygonQueue *polys); 
    126  
    127           /// vertices are connected in counterclockwise order. 
    128           VertexContainer mVertices; 
    129   }; 
    130  
    131   /** Implementation of the ViewCell BSP tree. */ 
    132   class BspTree  
    133   { 
    134   public: 
    135                    
    136           /** Additional data which is passed down the BSP tree during traversal. 
    137           */ 
    138           struct BspTraversalData 
    139           {   
    140                   /// the current node 
    141                   BspNode *mNode; 
    142                   /// parent of current node 
    143                   BspInterior *mParent; 
    144                   /// polygonal data for splitting 
    145                   PolygonQueue *mPolys; 
    146                   /// current depth 
    147                   int mDepth; 
    148                        
    149                   BspTraversalData() {} 
    150                    
    151                   BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth):  
    152                   mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {} 
    153       }; 
    154  
    155  
    156           /** Constructs BSP tree from list of view cells. 
    157           */  
    158           BspTree(const ViewCellContainer &viewCells); 
    159           /** Constructs BSP tree from list of objects. 
    160                   @param object list of intersectables 
    161                   @param maxPolys maximal allowed number of polygons 
    162                   @param maxDepth maximal allowed BSP tree depth 
    163           */ 
    164           BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth); 
    165    
    166           ~BspTree(); 
    167  
    168   protected: 
    169           /** Selects a splitting plane from the given polygons.  
    170           */ 
    171           Plane3 SelectPlane(PolygonQueue *polyQueue); 
    172  
    173           /** Filters next viewcell down the tree and inserts it into the appropriate leaves 
    174                   (i.e., possibly more than one leaf). 
    175           */ 
    176           void InsertViewCell(ViewCell *viewCell); 
    177  
    178           /** Subdivides tree according to the given list of viewcells. 
    179           */ 
    180           void Subdivide(const ViewCellContainer &viewCells); 
    181           /** Subdivides tree according to the given list of objects. 
    182           */ 
    183           void Subdivide(const ObjectContainer &objects); 
    184             
    185           /** Subdivides leaf. 
    186                   @param leaf the leaf to be subdivided 
    187                   @param parent the parent node of this leaf 
    188                   @param polys the input polygons 
    189                   @param depth the current tree depth 
    190                   @param frontPolys the polygons of the front child node as a result from splitting 
    191                   @param backPolys the polygons of the back child node as a result from splitting 
    192           */ 
    193           BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent,  
    194                                                          PolygonQueue *polys, const int depth,  
    195                                                          PolygonQueue *frontPolys, PolygonQueue *backPolys); 
    196  
    197           /** Extracts the mesh instances of the objects and copies them into the mesh. 
    198           */ 
    199           static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys); 
    200  
    201           static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys); 
    202  
    203           /// Pointer to the root of the tree 
    204           BspNode *mRoot; 
    205           /// Pointer to the root cell of the viewspace 
    206           // ViewCell *mRootCell; 
    207           /// maximal number of polygons allowed in leaf 
    208           int mMaxPolys; 
    209           /// maximal depth 
    210           int mMaxDepth; 
    211   }; 
    212    
     158                BspTraversalData() {} 
     159                 
     160                BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth):  
     161                mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {} 
     162    }; 
     163 
     164        typedef std::stack<BspTraversalData> BspTraversalStack; 
     165 
     166        /** Constructs BSP tree from list of view cells. 
     167        */  
     168        BspTree(const ViewCellContainer &viewCells); 
     169        /** Constructs BSP tree from list of objects. 
     170                @param object list of intersectables 
     171                @param maxPolys maximal allowed number of polygons 
     172                @param maxDepth maximal allowed BSP tree depth 
     173        */ 
     174        BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth); 
     175 
     176        ~BspTree(); 
     177 
     178protected: 
     179        /** Builds a new extension of the tree. 
     180        */ 
     181        void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData); 
     182 
     183        /** Selects a splitting plane from the given polygons.  
     184        */ 
     185        Plane3 SelectPlane(PolygonQueue *polyQueue); 
     186 
     187        /** Filters next viewcell down the tree and inserts it into the appropriate leaves 
     188                (i.e., possibly more than one leaf). 
     189        */ 
     190        void InsertViewCell(ViewCell *viewCell); 
     191 
     192        /** Subdivides tree according to the given list of viewcells. 
     193        */ 
     194        void Subdivide(const ViewCellContainer &viewCells); 
     195        /** Subdivides tree according to the given list of objects. 
     196        */ 
     197        void Subdivide(const ObjectContainer &objects); 
     198         
     199        /** Subdivides leaf. 
     200                @param leaf the leaf to be subdivided 
     201                @param parent the parent node of this leaf 
     202                @param polys the input polygons 
     203                @param depth the current tree depth 
     204                @param frontPolys the polygons of the front child node as a result from splitting 
     205                @param backPolys the polygons of the back child node as a result from splitting 
     206        */ 
     207        BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent,  
     208                                                        PolygonQueue *polys, const int depth,  
     209                                                        ViewCell *viewCell, 
     210                                                        PolygonQueue *frontPolys, PolygonQueue *backPolys); 
     211 
     212        /** Filters polygons down the tree. 
     213                @param node the current BSP node 
     214                @param polys the polygons to be filtered 
     215                @param frontPolys returns the polygons in front of the split plane 
     216                @param backPolys returns the polygons in the back of the split plane 
     217        */ 
     218        void FilterPolygons(BspInterior *node, PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys); 
     219 
     220        /** Extracts the mesh instances of the objects and copies them into the mesh. 
     221        */ 
     222        static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys); 
     223 
     224        static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys); 
     225 
     226        /// Pointer to the root of the tree 
     227        BspNode *mRoot; 
     228        /// Pointer to the root cell of the viewspace 
     229        // ViewCell *mRootCell; 
     230        /// maximal number of polygons allowed in leaf 
     231        int mMaxPolys; 
     232        /// maximal depth 
     233        int mMaxDepth; 
     234}; 
     235 
    213236//}; // GtpVisibilityPreprocessor 
    214237 
Note: See TracChangeset for help on using the changeset viewer.