Ignore:
Timestamp:
12/05/05 04:42:54 (19 years ago)
Author:
mattausch
Message:

fixed bug in VspBspTree?
view cells in VssPreprocessor?
bounding rays for vspkdtree

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r445 r448  
    99#include "VssRay.h" 
    1010#include "RayInfo.h" 
     11#include "ViewCellBsp.h" 
    1112 
    1213class ViewCell; 
    … …  
    1415class Plane3; 
    1516class VspBspTree;   
    16 class VspBspInterior; 
    17 class VspBspNode; 
     17class BspInterior; 
     18class BspNode; 
    1819class AxisAlignedBox3; 
    1920class Ray; 
    2021 
    21 class VspBspNodeGeometry 
    22 { 
    23 public: 
    24         VspBspNodeGeometry() 
    25         {};   
    26  
    27         ~VspBspNodeGeometry(); 
    28  
    29         float GetArea() const; 
    30          
    31         /** Computes new cell based on the old cell definition and a new split plane 
    32                 @param side indicates which side of the halfspace  
    33         */ 
    34         void SplitGeometry(VspBspNodeGeometry &front,  
    35                                            VspBspNodeGeometry &back, 
    36                                            const VspBspTree &tree, 
    37                                            const Plane3 &splitPlane) const; 
    38  
    39         Polygon3 *SplitPolygon(Polygon3 *poly, const VspBspTree &tree) const; 
    40  
    41         PolygonContainer mPolys; 
    42 }; 
    43  
    44 /** Data structure used for optimized ray casting. 
     22/*class BspNodeGeometry; 
     23class BspTreeStatistics; 
     24class BspViewCellsStatistics; 
     25class BspNode; 
     26class BspLeaf; 
     27class BspInterior; 
    4528*/ 
    46 struct VspBspRayTraversalData  
    47 { 
    48     VspBspNode *mNode; 
    49     Vector3 mExitPoint; 
    50     float mMaxT; 
    51      
    52     VspBspRayTraversalData() {} 
    53  
    54     VspBspRayTraversalData(VspBspNode *n, const Vector3 &extp, const float maxt): 
    55     mNode(n), mExitPoint(extp), mMaxT(maxt)  
    56         {} 
    57 }; 
    58  
    59 class VspBspTreeStatistics: public StatisticsBase 
    60 { 
    61 public: 
    62         // total number of nodes 
    63         int nodes; 
    64         // number of splits 
    65         int splits; 
    66         // totals number of rays 
    67         int rays; 
    68         // maximal reached depth 
    69         int maxDepth; 
    70         // minimal depth 
    71         int minDepth; 
    72          
    73         // max depth nodes 
    74         int maxDepthNodes; 
    75         // minimum depth nodes 
    76         int minDepthNodes; 
    77         // max depth nodes 
    78         int minPvsNodes; 
    79         // nodes with minimum PVS 
    80         int minRaysNodes; 
    81         // max ray contribution nodes 
    82         int maxRayContribNodes; 
    83         // minimum area nodes 
    84         int minAreaNodes; 
    85  
    86         // max number of rays per node 
    87         int maxObjectRefs; 
    88         // accumulated depth (used to compute average) 
    89         int accumDepth; 
    90         // number of initial polygons 
    91         int polys; 
    92         /// samples contributing to pvs 
    93         int contributingSamples; 
    94         /// sample contributions to pvs 
    95         int sampleContributions; 
    96         /// largest pvs 
    97         int largestPvs; 
    98  
    99         // Constructor 
    100         VspBspTreeStatistics()  
    101         { 
    102                 Reset(); 
    103         } 
    104  
    105         int Nodes() const {return nodes;} 
    106         int Interior() const { return nodes / 2; } 
    107         int Leaves() const { return (nodes / 2) + 1; } 
    108          
    109         // TODO: computation wrong 
    110         double AvgDepth() const { return accumDepth / (double)Leaves();};  
    111    
    112         void Reset()  
    113         { 
    114                 nodes = 0; 
    115                 splits = 0; 
    116                  
    117                 maxDepth = 0; 
    118                 minDepth = 99999; 
    119                 polys = 0; 
    120                 accumDepth = 0; 
    121          
    122                 maxDepthNodes = 0; 
    123                 minPvsNodes = 0; 
    124                 minRaysNodes = 0; 
    125                 maxRayContribNodes = 0; 
    126                 minAreaNodes = 0; 
    127  
    128                 contributingSamples = 0; 
    129                 sampleContributions = 0; 
    130         } 
    131  
    132         void Print(ostream &app) const; 
    133  
    134         friend ostream &operator<<(ostream &s, const VspBspTreeStatistics &stat)  
    135         { 
    136                 stat.Print(s); 
    137                 return s; 
    138         }  
    139 }; 
    140  
    141 class VspBspViewCellsStatistics: public StatisticsBase 
    142 { 
    143 public: 
    144  
    145         /// number of view cells 
    146         int viewCells; 
    147  
    148         /// size of the PVS 
    149         int pvs; 
    150    
    151         /// largest PVS of all view cells 
    152         int maxPvs; 
    153  
    154         /// smallest PVS of all view cells 
    155         int minPvs; 
    156  
    157         /// view cells with empty PVS 
    158         int emptyPvs; 
    159  
    160         /// number of bsp leaves covering the view space 
    161         int bspLeaves; 
    162  
    163         /// largest number of leaves covered by one view cell   
    164         int maxVspBspLeaves; 
    165  
    166     // Constructor 
    167         VspBspViewCellsStatistics()  
    168         { 
    169                 Reset(); 
    170         } 
    171  
    172         double AvgVspBspLeaves() const {return (double)bspLeaves / (double)viewCells;}; 
    173         double AvgPvs() const {return (double)pvs / (double)viewCells;}; 
    174    
    175         void Reset()  
    176         { 
    177                 viewCells = 0;   
    178                 pvs = 0;   
    179                 maxPvs = 0; 
    180  
    181                 minPvs = 999999; 
    182                 emptyPvs = 0; 
    183                 bspLeaves = 0; 
    184                 maxVspBspLeaves = 0; 
    185         } 
    186  
    187         void Print(ostream &app) const; 
    188  
    189         friend ostream &operator<<(ostream &s, const VspBspViewCellsStatistics &stat)  
    190         { 
    191                 stat.Print(s); 
    192                 return s; 
    193         }   
    194 }; 
    195  
    196 /** 
    197     VspBspNode abstract class serving for interior and leaf node implementation 
    198 */ 
    199 class VspBspNode  
    200 { 
    201         friend class VspBspTree; 
    202  
    203 public: 
    204         VspBspNode(); 
    205         virtual ~VspBspNode(){}; 
    206         VspBspNode(VspBspInterior *parent); 
    207  
    208         /** Determines whether this node is a leaf or not 
    209         @return true if leaf 
    210         */ 
    211         virtual bool IsLeaf() const = 0; 
    212  
    213         /** Determines whether this node is a root 
    214         @return true if root 
    215         */ 
    216         virtual bool IsRoot() const; 
    217  
    218         /** Returns parent node. 
    219         */ 
    220         VspBspInterior *GetParent(); 
    221  
    222         /** Sets parent node. 
    223         */ 
    224         void SetParent(VspBspInterior *parent); 
    225  
    226          
    227         static int sMailId; 
    228         int mMailbox; 
    229    
    230         void Mail() { mMailbox = sMailId; } 
    231         static void NewMail() { ++ sMailId; } 
    232         bool Mailed() const { return mMailbox == sMailId; } 
    233  
    234 protected: 
    235  
    236         /// parent of this node 
    237         VspBspInterior *mParent; 
    238 }; 
    239  
    240 /** BSP interior node implementation  
    241 */ 
    242 class VspBspInterior : public VspBspNode  
    243 { 
    244         friend class VspBspTree; 
    245 public: 
    246         /** Standard contructor taking split plane as argument. 
    247         */ 
    248         VspBspInterior(const Plane3 &plane); 
    249         ~VspBspInterior(); 
    250         /** @return false since it is an interior node  
    251         */ 
    252         bool IsLeaf() const; 
    253  
    254         VspBspNode *GetBack(); 
    255         VspBspNode *GetFront(); 
    256  
    257         Plane3 *GetPlane(); 
    258  
    259         void ReplaceChildLink(VspBspNode *oldChild, VspBspNode *newChild); 
    260         void SetupChildLinks(VspBspNode *b, VspBspNode *f); 
    261  
    262         /** Splits polygons with respect to the split plane. 
    263                 @param polys the polygons to be split. the polygons are consumed and 
    264                            distributed to the containers frontPolys, backPolys, coincident. 
    265                 @param frontPolys returns the polygons in the front of the split plane 
    266                 @param backPolys returns the polygons in the back of the split plane 
    267                 @param coincident returns the polygons coincident to the split plane 
    268  
    269                 @returns the number of splits    
    270         */ 
    271         int SplitPolygons(PolygonContainer &polys,  
    272                                           PolygonContainer &frontPolys,  
    273                                           PolygonContainer &backPolys,  
    274                                           PolygonContainer &coincident); 
    275  
    276         friend ostream &operator<<(ostream &s, const VspBspInterior &A) 
    277         { 
    278                 return s << A.mPlane; 
    279         } 
    280  
    281 protected: 
    282  
    283         /// Splitting plane corresponding to this node 
    284         Plane3 mPlane; 
    285         /// back node 
    286         VspBspNode *mBack; 
    287         /// front node 
    288         VspBspNode *mFront; 
    289 }; 
    290  
    291 /** BSP leaf node implementation. 
    292 */ 
    293 class VspBspLeaf : public VspBspNode  
    294 { 
    295         friend class VspBspTree; 
    296  
    297 public: 
    298         VspBspLeaf(); 
    299         VspBspLeaf(BspViewCell *viewCell); 
    300         VspBspLeaf(VspBspInterior *parent); 
    301         VspBspLeaf(VspBspInterior *parent, BspViewCell *viewCell); 
    302  
    303         /** @return true since it is an interior node  
    304         */ 
    305         bool IsLeaf() const; 
    306          
    307         /** Returns pointer of view cell. 
    308         */ 
    309         BspViewCell *GetViewCell() const; 
    310  
    311         /** Sets pointer to view cell. 
    312         */ 
    313         void SetViewCell(BspViewCell *viewCell); 
    314  
    315         /** Adds ray sample contributions to the PVS. 
    316                 @param sampleContributions the number contributions of the samples 
    317                 @param contributingSampels the number of contributing rays 
    318                  
    319         */ 
    320         void AddToPvs(const RayInfoContainer &rays,  
    321                                   int &sampleContributions, 
    322                                   int &contributingSamples,  
    323                                   bool storeLeavesWithRays = false); 
    324  
    325 protected: 
    326  
    327         /// if NULL this does not correspond to feasible viewcell 
    328         BspViewCell *mViewCell; 
    329 }; 
    33029 
    33130/** 
    … …  
    34544        {   
    34645                /// the current node 
    347                 VspBspNode *mNode; 
     46                BspNode *mNode; 
    34847                /// polygonal data for splitting 
    34948                PolygonContainer *mPolygons; 
    35049                /// current depth 
    35150                int mDepth; 
    352                 /// the view cell associated with this subdivsion 
    353                 ViewCell *mViewCell; 
     51                 
    35452                /// rays piercing this node 
    35553                RayInfoContainer *mRays; 
    35654                /// area of current node 
    35755                float mArea; 
    358                 /// geometry of current node induced by split planes 
    359                 VspBspNodeGeometry *mGeometry; 
    360  
     56                /// geometry of node as induced by planes 
     57                BspNodeGeometry *mGeometry; 
     58                 
    36159                /// pvs size 
    36260                int mPvs; 
    … …  
    37472                mPolygons(NULL), 
    37573                mDepth(0), 
    376                 mViewCell(NULL), 
    37774                mRays(NULL), 
    37875                mPvs(0), 
    … …  
    38178                {} 
    38279                 
    383                 VspBspTraversalData(VspBspNode *node,  
     80                VspBspTraversalData(BspNode *node,  
    38481                                                 PolygonContainer *polys,  
    38582                                                 const int depth,  
    386                                                  ViewCell *viewCell, 
    38783                                                 RayInfoContainer *rays, 
    38884                                                 int pvs, 
    38985                                                 float area, 
    390                                                  VspBspNodeGeometry *cell):  
     86                                                 BspNodeGeometry *geom):  
    39187                mNode(node),  
    39288                mPolygons(polys),  
    39389                mDepth(depth),  
    394                 mViewCell(viewCell), 
    39590                mRays(rays), 
    39691                mPvs(pvs), 
    39792                mArea(area), 
    398                 mGeometry(cell) 
     93                mGeometry(geom) 
     94                {} 
     95 
     96                VspBspTraversalData(PolygonContainer *polys,  
     97                                                        const int depth,  
     98                                                        RayInfoContainer *rays, 
     99                                                        BspNodeGeometry *geom):  
     100                mNode(NULL),  
     101                mPolygons(polys),  
     102                mDepth(depth),  
     103                mRays(rays), 
     104                mPvs(0), 
     105                mArea(0), 
     106                mGeometry(geom) 
    399107                {} 
    400108    }; 
    … …  
    406114        VspBspTree(); 
    407115 
     116        /** Default destructor. 
     117        */ 
    408118        ~VspBspTree(); 
    409119 
    410         const VspBspTreeStatistics &GetStatistics() const;  
     120        /** Returns BSP Tree statistics. 
     121        */ 
     122        const BspTreeStatistics &GetStatistics() const;  
    411123   
    412124 
    … …  
    420132        /** Returns list of BSP leaves. 
    421133        */ 
    422         void CollectLeaves(vector<VspBspLeaf *> &leaves) const; 
     134        void CollectLeaves(vector<BspLeaf *> &leaves) const; 
    423135 
    424136        /** Returns box which bounds the whole tree. 
    … …  
    428140        /** Returns root of BSP tree. 
    429141        */ 
    430         VspBspNode *GetRoot() const; 
     142        BspNode *GetRoot() const; 
    431143 
    432144        /** Exports VspBsp tree to file. 
    … …  
    450162        /** Returns statistics. 
    451163        */ 
    452         VspBspTreeStatistics &GetStat(); 
     164        BspTreeStatistics &GetStat(); 
    453165 
    454166        /** finds neighbouring leaves of this tree node. 
    455167        */ 
    456         int FindNeighbors(VspBspNode *n, vector<VspBspLeaf *> &neighbors,  
     168        int FindNeighbors(BspNode *n,  
     169                                          vector<BspLeaf *> &neighbors,  
    457170                                          const bool onlyUnmailed) const; 
    458171 
    … …  
    460173                leading to this node. 
    461174        */ 
    462         void ConstructGeometry(VspBspNode *n, PolygonContainer &cell) const; 
     175        void ConstructGeometry(BspNode *n, PolygonContainer &cell) const; 
    463176 
    464177        /** Constructs geometry associated with the half space intersections  
    … …  
    469182        /** Construct geometry and stores it in a geometry node container. 
    470183        */ 
    471         void ConstructGeometry(VspBspNode *n, VspBspNodeGeometry &cell) const; 
     184        void ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const; 
    472185 
    473186        /** Returns random leaf of BSP tree. 
    474187                @param halfspace defines the halfspace from which the leaf is taken. 
    475188        */ 
    476         VspBspLeaf *GetRandomLeaf(const Plane3 &halfspace); 
     189        BspLeaf *GetRandomLeaf(const Plane3 &halfspace); 
    477190 
    478191        /** Returns random leaf of BSP tree. 
    479192                @param onlyUnmailed if only unmailed leaves should be returned. 
    480193        */ 
    481         VspBspLeaf *GetRandomLeaf(const bool onlyUnmailed = false); 
     194        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false); 
    482195 
    483196        /** Traverses tree and counts all view cells as well as their PVS size. 
    484197        */ 
    485         void EvaluateViewCellsStats(VspBspViewCellsStatistics &stat) const; 
     198        void EvaluateViewCellsStats(BspViewCellsStatistics &stat) const; 
    486199 
    487200 
    … …  
    489202        */ 
    490203        BspViewCell *GetRootCell() const; 
     204 
     205        /** Returns epsilon of this tree. 
     206        */ 
     207        float GetEpsilon() const; 
    491208 
    492209protected: 
    … …  
    521238                @returns new root of the subtree 
    522239        */ 
    523         VspBspNode *Subdivide(VspBspTraversalStack &tStack, VspBspTraversalData &tData); 
    524  
    525         /** Constructs the tree from the given list of polygons and rays. 
     240        BspNode *Subdivide(VspBspTraversalStack &tStack,  
     241                                           VspBspTraversalData &tData); 
     242 
     243        /** Constructs the tree from the given traversal data. 
    526244                @param polys stores set of polygons on which subdivision may be based 
    527245                @param rays storesset of rays on which subdivision may be based 
    528246        */ 
    529         void Construct(PolygonContainer *polys, RayInfoContainer *rays); 
     247        void Construct(const PolygonContainer &polys, RayInfoContainer *rays); 
    530248 
    531249        /** Selects the best possible splitting plane.  
    … …  
    536254                @returns the split plane 
    537255        */ 
    538         Plane3 SelectPlane(VspBspLeaf *leaf,  
     256        Plane3 SelectPlane(BspLeaf *leaf,  
    539257                                           VspBspTraversalData &data); 
    540258 
    … …  
    564282        */ 
    565283 
    566         VspBspInterior *SubdivideNode(VspBspTraversalData &tData, 
     284        BspInterior *SubdivideNode(VspBspTraversalData &tData, 
    567285                                                           VspBspTraversalData &frontData, 
    568286                                                           VspBspTraversalData &backData, 
    … …  
    575293                @param rays bundle of rays on which the split can be based 
    576294        */ 
    577         Plane3 SelectPlaneHeuristics(VspBspLeaf *leaf, 
     295        Plane3 SelectPlaneHeuristics(BspLeaf *leaf, 
    578296                                                                 VspBspTraversalData &data); 
    579297 
    … …  
    639357        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const; 
    640358 
    641         /** Bounds ray and returns minT and maxT. 
    642                 @returns true if ray hits BSP tree bounding box 
    643         */ 
    644         bool BoundRay(const Ray &ray, float &minT, float &maxT) const; 
    645  
    646359        /** Subdivides the rays into front and back rays according to the split plane. 
    647360                 
    … …  
    662375        /** Extracts the split planes representing the space bounded by node n. 
    663376        */ 
    664         void ExtractHalfSpaces(VspBspNode *n, vector<Plane3> &halfSpaces) const; 
     377        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const; 
    665378 
    666379        /** Adds the object to the pvs of the front and back leaf with a given classification. 
    … …  
    686399        float AccumulatedRayLength(const RayInfoContainer &rays) const; 
    687400 
    688  
     401        /** Splits polygons with respect to the split plane. 
     402 
     403                @param plane the split plane 
     404                @param polys the polygons to be split. the polygons are consumed and 
     405                           distributed to the containers frontPolys, backPolys, coincident. 
     406                @param frontPolys returns the polygons in the front of the split plane 
     407                @param backPolys returns the polygons in the back of the split plane 
     408                @param coincident returns the polygons coincident to the split plane 
     409 
     410                @returns the number of splits    
     411        */ 
     412        int SplitPolygons(const Plane3 &plane, 
     413                                          PolygonContainer &polys,  
     414                                          PolygonContainer &frontPolys,  
     415                                          PolygonContainer &backPolys,  
     416                                          PolygonContainer &coincident) const; 
     417 
     418        /** Adds ray sample contributions to the PVS. 
     419                @param sampleContributions the number contributions of the samples 
     420                @param contributingSampels the number of contributing rays 
     421                 
     422        */ 
     423        void AddToPvs(BspLeaf *leaf, 
     424                                  const RayInfoContainer &rays,  
     425                                  int &sampleContributions, 
     426                                  int &contributingSamples); 
    689427 
    690428        /// Pointer to the root of the tree 
    691         VspBspNode *mRoot; 
    692                  
    693         VspBspTreeStatistics mStat; 
     429        BspNode *mRoot; 
     430                 
     431        BspTreeStatistics mStat; 
    694432 
    695433        /// Strategies for choosing next split plane. 
    … …  
    749487        bool mPvsUseArea; 
    750488 
     489        float mEpsilon; 
     490 
     491        int mMaxTests; 
     492 
    751493private: 
    752494         
Note: See TracChangeset for help on using the changeset viewer.