Ignore:
Timestamp:
11/17/05 18:47:53 (19 years ago)
Author:
mattausch
Message:
 
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r419 r420  
    3131#include "Ray.h" 
    3232 
    33 // -------------------------------------------------------------- 
    34 // Static statistics for kd-tree search 
    35 // -------------------------------------------------------------- 
     33#include "RayInfo.h" 
     34 
     35 
     36/** 
     37        Static statistics for vsp kd-tree search 
     38*/ 
    3639class VspKdStatistics:  public StatisticsBase 
    3740{ 
    3841public:   
    39   // total number of nodes 
    40   int nodes; 
    41   // number of splits along each of the axes 
    42   int splits[7]; 
    43   // totals number of rays 
    44   int rays; 
     42        // total number of nodes 
     43        int nodes; 
     44        // number of splits along each of the axes 
     45        int splits[7]; 
     46        // totals number of rays 
     47        int rays; 
    4548        // initial size of the pvs 
    46   int initialPvsSize; 
     49        int initialPvsSize; 
    4750        // total number of query domains 
    48   int queryDomains; 
    49   // total number of ray references 
    50   int rayRefs; 
     51        int queryDomains; 
     52        // total number of ray references 
     53        int rayRefs; 
    5154 
    5255        // max depth nodes 
    53   int maxDepthNodes; 
    54   // max depth nodes 
    55   int minPvsNodes; 
    56   int minRaysNodes; 
     56        int maxDepthNodes; 
     57        // max depth nodes 
     58        int minPvsNodes; 
     59        int minRaysNodes; 
    5760        // max ray contribution nodes 
    58   int maxRayContribNodes; 
     61        int maxRayContribNodes; 
    5962        // max depth nodes 
    60   int minSizeNodes; 
    61          
    62   // max number of rays per node 
    63   int maxRayRefs; 
    64   // number of dynamically added ray refs 
    65   int addedRayRefs; 
    66   // number of dynamically removed ray refs 
    67   int removedRayRefs; 
    68    
    69   // Constructor 
    70   VspKdStatistics()  
    71   { 
    72           Reset(); 
    73   } 
    74  
    75   int Nodes() const {return nodes;} 
    76   int Interior() const { return nodes/2; } 
    77   int Leaves() const { return (nodes/2) + 1; } 
    78  
    79   void Reset()  
    80   { 
    81           nodes = 0; 
    82           for (int i=0; i<7; i++) 
    83                   splits[i] = 0; 
    84           rays = queryDomains = 0; 
    85           rayRefs = 0; 
    86           maxDepthNodes = 0; 
    87           minPvsNodes = 0; 
    88           minRaysNodes = 0;  
    89           maxRayRefs = 0; 
    90           addedRayRefs = removedRayRefs = 0; 
    91           initialPvsSize = 0; 
    92           maxRayContribNodes = 0; 
    93           minSizeNodes = 0; 
    94   } 
    95    
    96   void 
    97   Print(ostream &app) const; 
    98  
    99   friend ostream &operator<<(ostream &s, const VspKdStatistics &stat) { 
    100     stat.Print(s); 
    101     return s; 
    102   } 
    103    
     63        int minSizeNodes; 
     64         
     65        // max number of rays per node 
     66        int maxRayRefs; 
     67        // number of dynamically added ray refs 
     68        int addedRayRefs; 
     69        // number of dynamically removed ray refs 
     70        int removedRayRefs; 
     71   
     72        /** Default constructor. 
     73        */ 
     74        VspKdStatistics() {     Reset(); } 
     75        int Nodes() const { return nodes; } 
     76        int Interior() const { return nodes / 2; } 
     77        int Leaves() const { return (nodes / 2) + 1; } 
     78 
     79        void Reset()  
     80        { 
     81                nodes = 0; 
     82 
     83                for (int i=0; i<7; i++) 
     84                        splits[i] = 0; 
     85 
     86                rays = queryDomains = 0; 
     87                rayRefs = 0; 
     88                maxDepthNodes = 0; 
     89                minPvsNodes = 0; 
     90                minRaysNodes = 0;  
     91                maxRayRefs = 0; 
     92                addedRayRefs = removedRayRefs = 0; 
     93                initialPvsSize = 0; 
     94                maxRayContribNodes = 0; 
     95                minSizeNodes = 0; 
     96        } 
     97 
     98        void Print(ostream &app) const; 
     99        friend ostream &operator<<(ostream &s, const VspKdStatistics &stat)  
     100        { 
     101            stat.Print(s); 
     102            return s; 
     103        }   
    104104}; 
    105105 
    … …  
    108108 
    109109 
    110 // -------------------------------------------------------------- 
    111 // KD-tree node - abstract class 
    112 // -------------------------------------------------------------- 
     110/** Abstract superclass of Vsp-Kd-Tree nodes. 
     111*/ 
    113112class VspKdTreeNode 
    114113{ 
    … …  
    118117#define USE_FIXEDPOINT_T 1 
    119118 
    120 struct RayInfo 
    121 { 
    122         // pointer to the actual ray 
    123         VssRay *mRay; 
    124          
    125         // endpoints  - do we need them? 
    126 #if USE_FIXEDPOINT_T 
    127         short mMinT, mMaxT; 
    128 #else 
    129         float mMinT, mMaxT; 
    130 #endif 
    131          
    132         RayInfo():mRay(NULL) {} 
    133          
    134         RayInfo(VssRay *r):mRay(r), mMinT(0), 
    135 #if USE_FIXEDPOINT_T 
    136 #define FIXEDPOINT_ONE 0x7FFE 
    137         // mMaxT(0xFFFF) 
    138                 mMaxT(FIXEDPOINT_ONE) 
    139 #else 
    140                 mMaxT(1.0f) 
    141 #endif 
    142         {} 
    143          
    144         RayInfo(VssRay *r, 
    145                         const float _min, 
    146                         const float _max 
    147                         ):mRay(r)  
    148         { 
    149                 SetMinT(_min); 
    150                 SetMaxT(_max); 
    151         } 
    152          
    153         RayInfo(VssRay *r, 
    154                         const short _min, 
    155                         const float _max):mRay(r), mMinT(_min)  
    156         { 
    157                 SetMaxT(_max); 
    158         } 
    159          
    160         RayInfo(VssRay *r, 
    161                         const float _min, 
    162                         const short _max): 
    163         mRay(r), mMaxT(_max)  
    164         { 
    165                 SetMinT(_min); 
    166         } 
    167          
    168         friend bool operator<(const RayInfo &a, const RayInfo &b) { 
    169                 return a.mRay < b.mRay; 
    170         } 
    171    
    172          
    173         float ExtrapOrigin(const int axis) const { 
    174                 return mRay->GetOrigin(axis) + GetMinT()*mRay->GetDir(axis); 
    175         } 
    176          
    177         float ExtrapTermination(const int axis) const { 
    178                 return mRay->GetOrigin(axis) + GetMaxT()*mRay->GetDir(axis); 
    179         } 
    180          
    181 #if USE_FIXEDPOINT_T 
    182         float GetMinT () const { return mMinT/(float)(FIXEDPOINT_ONE); } 
    183         float GetMaxT () const { return mMaxT/(float)(FIXEDPOINT_ONE); } 
    184          
    185         void SetMinT (const float t) { 
    186                 mMinT = (short) (t*(float)(FIXEDPOINT_ONE)); 
    187         } 
    188          
    189         void SetMaxT (const float t) { 
    190                 mMaxT = (short) (t*(float)(FIXEDPOINT_ONE)); 
    191                 mMaxT++; 
    192                 //      if (mMaxT!=0xFFFF) 
    193                 //      mMaxT++; 
    194         } 
    195 #else 
    196         float GetMinT () const { return mMinT; } 
    197         float GetMaxT () const { return mMaxT; } 
    198          
    199         void SetMinT (const float t) { mMinT = t; } 
    200         void SetMaxT (const float t) { mMaxT = t; } 
    201 #endif  
    202  
    203  
    204         int ComputeRayIntersection(const int axis, const float position, float &t) const  
    205         {                
    206                 // intersect the ray with the plane 
    207                 float denom = mRay->GetDir(axis); 
    208      
    209                 if (fabs(denom) < 1e-20) 
    210                         //if (denom == 0.0f) 
    211                         return (mRay->GetOrigin(axis) > position) ? 1 : -1; 
    212      
    213                 t = (position - mRay->GetOrigin(axis))/denom; 
    214  
    215                 if (t < GetMinT()) 
    216                         return (denom > 0) ? 1 : -1; 
    217  
    218                 if (t > GetMaxT()) 
    219                         return (denom > 0) ? -1 : 1; 
    220  
    221                 return 0; 
    222         } 
    223  
    224  
    225 }; 
    226  
    227  
    228 typedef vector<RayInfo> RayInfoContainer; 
    229  
    230 enum {EInterior, ELeaf}; 
    231  
    232   ///////////////////////////////// 
    233   // The actual data goes here 
    234    
    235   // link to the parent 
    236   VspKdTreeInterior *mParent; 
    237  
    238   enum {SPLIT_X=0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ}; 
    239    
    240   // splitting axis 
    241   char mAxis; 
    242          
    243   // depth 
    244   unsigned char mDepth; 
    245    
    246   //  short depth; 
    247   // 
    248   ///////////////////////////////// 
    249    
    250   inline VspKdTreeNode(VspKdTreeInterior *p); 
    251  
    252    
    253   virtual ~VspKdTreeNode() {}; 
    254   virtual int Type() const = 0; 
    255    
    256  
    257   bool IsLeaf() const { return mAxis == -1; } 
    258    
    259   virtual void Print(ostream &s) const = 0; 
    260  
    261   virtual int GetAccessTime()  
    262   { 
    263           return 0x7FFFFFF; 
    264   } 
    265  
    266    
    267          
     119        enum {EInterior, ELeaf}; 
     120 
     121        /** Constructs new interior node from the parent node. 
     122        */ 
     123        inline VspKdTreeNode(VspKdTreeInterior *p); 
     124 
     125        /** Destroys this node and the subtree. 
     126        */ 
     127        virtual ~VspKdTreeNode(); 
     128 
     129        /** Type of the node (Einterior or ELeaf) 
     130        */ 
     131        virtual int Type() const = 0; 
     132  
     133        /** Returns true if this node is a leaf. 
     134        */ 
     135        bool IsLeaf() const; 
     136         
     137        /** Prints node stats. 
     138        */ 
     139        virtual void Print(ostream &s) const = 0; 
     140 
     141        /** Returns time needed to access this node. 
     142        */ 
     143        virtual int GetAccessTime(); // NOTE: don't really know how it is used! 
     144 
     145        /** Returns parent node. 
     146        */ 
     147        VspKdTreeInterior *GetParent() const; 
     148        /** Sets parent node. 
     149        */ 
     150        void SetParent(VspKdTreeInterior *p); 
     151 
     152protected: 
     153        ///////////////////////////////// 
     154        // The actual data goes here 
     155   
     156        /// link to the parent 
     157        VspKdTreeInterior *mParent; 
     158 
     159        enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ}; 
     160   
     161        /// splitting axis 
     162        char mAxis; 
     163         
     164        /// depth 
     165        unsigned char mDepth; 
    268166}; 
    269167 
    … …  
    276174        friend class VspKdTree; 
    277175 
     176        /** Constructs new interior node from parent node. 
     177        */ 
    278178        VspKdTreeInterior(VspKdTreeInterior *p); 
    279179                         
    … …  
    286186        virtual void Print(ostream &s) const; 
    287187 
     188        /** Returns back child. 
     189        */ 
    288190        inline VspKdTreeNode *GetBack() const; 
     191        /** Returns front child. 
     192        */ 
    289193        inline VspKdTreeNode *GetFront() const; 
    290194 
    291195protected: 
    292196 
     197        /** Sets pointers to back child and front child. 
     198        */ 
    293199        void SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f); 
    294   
     200 
     201        /** Replaces the pointer to oldChild with a pointer to newChild. 
     202        */ 
    295203        void ReplaceChildLink(VspKdTreeNode *oldChild, VspKdTreeNode *newChild); 
    296204  
     205        /** Computes intersection of the ray with the node boundaries. 
     206        */ 
    297207        int ComputeRayIntersection(const RayInfo &rayData, float &t); 
    298208 
    … …  
    321231        friend class VspKdTree; 
    322232 
     233        /** Constructs leaf from parent node. 
     234                @param p the parent node 
     235                @param nRays preallocates memory to store this number of rays 
     236        */ 
     237        VspKdTreeLeaf(VspKdTreeInterior *p,     const int nRays); 
     238         
     239        virtual ~VspKdTreeLeaf(); 
     240 
     241        virtual int Type() const;   
     242 
     243        virtual void Print(ostream &s) const; 
     244   
     245        /** Adds a ray to the leaf ray container. 
     246        */ 
     247        void AddRay(const RayInfo &data); 
     248        /** Returns size of the leaf PVS as induced by the rays 
     249                @note returns precomputed PVS size, which may not be valid 
     250                anymore. Run UpdatePvsSize to get a valid PVS. 
     251        */ 
     252        int GetPvsSize() const; 
     253        void SetPvsSize(const int s); 
     254 
     255        /** If PVS is not valid, this function recomputes the leaf  
     256                PVS as induced by the rays. 
     257        */ 
     258        void UpdatePvsSize(); 
     259 
     260        void Mail(); 
     261 
     262        bool Mailed() const; 
     263   
     264        bool Mailed(const int mail); 
     265 
     266        /** Returns average contribution of a ray to the PVS 
     267        */ 
     268        inline float GetAvgRayContribution() const; 
     269        /** Returns square of average contribution of a ray. 
     270        */ 
     271        inline float GetSqrRayContribution() const; 
     272 
     273        static void NewMail(); 
     274 
    323275        static int mailID; 
    324         int mailbox; 
    325    
    326         RayInfoContainer rays; 
     276 
     277protected: 
     278         
     279        int mMailbox; 
     280   
     281        RayInfoContainer mRays; 
    327282        bool mValidPvs; 
    328283         
    329         VspKdTreeLeaf(VspKdTreeInterior *p,     const int nRays): 
    330         VspKdTreeNode(p), rays(), mPvsSize(0), mValidPvs(false)  
    331         { 
    332                 rays.reserve(nRays); 
    333         } 
    334          
    335         virtual ~VspKdTreeLeaf() { } 
    336  
    337         virtual int Type() const   
    338         {  
    339                 return ELeaf;  
    340         } 
    341  
    342         virtual void Print(ostream &s) const  
    343         { 
    344                 s << endl << "L: r = " << (int)rays.size() << endl; 
    345         }; 
    346    
    347         void AddRay(const RayInfo &data)  
    348         { 
    349                 mValidPvs = false; 
    350                 rays.push_back(data); 
    351                 data.mRay->Ref(); 
    352         } 
    353          
    354         int GetPvsSize() const  
    355         { 
    356                 return mPvsSize; 
    357         } 
    358         void SetPvsSize(const int s)  
    359         { 
    360                 mPvsSize = s; 
    361         } 
    362  
    363         void UpdatePvsSize(); 
    364  
    365         void Mail()  
    366         {  
    367                 mailbox = mailID;  
    368         } 
    369    
    370         static void NewMail()  
    371         {  
    372                 ++ mailID;  
    373         } 
    374    
    375         bool Mailed() const  
    376         {  
    377                 return mailbox == mailID;  
    378         } 
    379    
    380         bool Mailed(const int mail)  
    381         { 
    382                 return mailbox >= mailID + mail; 
    383         } 
    384  
    385         float GetAvgRayContribution() const  
    386         { 
    387                 return GetPvsSize()/((float)rays.size() + Limits::Small); 
    388         } 
    389  
    390         float GetSqrRayContribution() const  
    391         { 
    392                 return sqr(GetPvsSize()/((float)rays.size() + Limits::Small)); 
    393         } 
    394284private: 
    395285        int mPvsSize; 
    396286}; 
    397  
    398 // Inline functions 
    399 inline VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p): 
    400 mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)  
    401 {} 
    402287 
    403288 
    … …  
    501386  }; 
    502387   
    503   // simplified data for ray traversal only... 
    504  
     388  /** Simplified data for ray traversal only. 
     389  */ 
    505390  struct RayTraversalData  
    506391  { 
    507           VspKdTreeNode::RayInfo mRayData; 
     392          RayInfo mRayData; 
    508393          VspKdTreeNode *mNode; 
    509394       
    510395          RayTraversalData() {} 
    511396           
    512           RayTraversalData(VspKdTreeNode *n, const VspKdTreeNode::RayInfo &data): 
     397          RayTraversalData(VspKdTreeNode *n, const RayInfo &data): 
    513398          mRayData(data), mNode(n) {} 
    514399  }; 
    … …  
    521406        virtual void Construct(VssRayContainer &rays, 
    522407                                                   AxisAlignedBox3 *forcedBoundingBox = NULL); 
    523          
    524         // incemental construction 
     408 
     409        /** Returns bounding box of the specified node. 
     410        */ 
     411        AxisAlignedBox3 GetBBox(VspKdTreeNode *node) const; 
     412 
     413        const VspKdStatistics &GetStatistics() const; 
     414 
     415        /** Get the root of the tree. 
     416        */ 
     417        VspKdTreeNode *GetRoot() const; 
     418 
     419        /** Returns average PVS size in tree. 
     420        */ 
     421        float GetAvgPvsSize(); 
     422 
     423        /** Parses the environment and stores the global VspKd tree parameters 
     424        */ 
     425        static void ParseEnvironment(); 
     426 
     427        ///////////////////////////// 
     428        // Construction parameters 
     429 
     430        /// max depth of the tree 
     431        static int sTermMaxDepth; 
     432 
     433        /// minimal ratio of the volume of the cell and the query volume 
     434        static float sTermMinSize; 
     435 
     436        /// minimal pvs per node to still get subdivided 
     437        static int sTermMinPvs; 
     438 
     439        /// minimal ray number per node to still get subdivided 
     440        static int sTermMinRays; 
     441         
     442        /// maximal cost ration to subdivide a node 
     443        static float sTermMaxCostRatio; 
     444         
     445        /// maximal contribution per ray to subdivide the node 
     446        static float sTermMaxRayContribution; 
     447 
     448        /** Returns memory usage in MB. 
     449        */ 
     450        float GetMemUsage() const; 
     451         
     452        float GetRayMemUsage() const; 
     453 
     454protected: 
     455        // incremental construction 
    525456        virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add); 
    526457 
    527         virtual void AddRays(VssRayContainer &add) 
    528         { 
    529                 VssRayContainer remove; 
    530                 UpdateRays(remove, add); 
    531         } 
     458        virtual void AddRays(VssRayContainer &add); 
    532459 
    533460        VspKdTreeNode *Locate(const Vector3 &v); 
    … …  
    549476 
    550477        void SortSplitCandidates(VspKdTreeLeaf *node, 
    551                                                          const int axis); 
    552          
    553    
    554         // return memory usage in MB 
    555         float GetMemUsage() const  
    556         { 
    557                 return  
    558                         (sizeof(VspKdTree) +  
    559                          mStat.Leaves() * sizeof(VspKdTreeLeaf) + 
    560                          mStat.Interior() * sizeof(VspKdTreeInterior) + 
    561                          mStat.rayRefs * sizeof(VspKdTreeNode::RayInfo)) / (1024.0f*1024.0f); 
    562         } 
    563          
    564         float GetRayMemUsage() const  
    565         { 
    566                 return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f); 
    567         } 
     478                                                         const int axis);        
    568479   
    569480        float BestCostRatioHeuristic(VspKdTreeLeaf *node, 
    … …  
    591502                                                int &pvsFront); 
    592503 
    593         AxisAlignedBox3 GetBBox(VspKdTreeNode *node) const;      
    594504 
    595505        VspKdTreeNode * SubdivideLeaf(VspKdTreeLeaf *leaf, 
    … …  
    619529                                         SimpleRayContainer &rays); 
    620530 
    621         float GetAvgPvsSize(); 
    622  
    623         /** Get the root of the tree. 
    624         */ 
    625         VspKdTreeNode *GetRoot() const; 
    626  
    627531        int CollapseSubtree(VspKdTreeNode *sroot, const int time); 
    628  
    629         const VspKdStatistics &GetStatistics() const; 
    630532         
    631533        int ReleaseMemory(const int time); 
    632  
    633         /** Parses the environment and stores the global BSP tree parameters 
    634         */ 
    635         static void ParseEnvironment(); 
    636  
    637         ///////////////////////////// 
    638         // Construction parameters 
    639  
    640         // max depth of the tree 
    641         static int sTermMaxDepth; 
    642  
    643         // minimal ratio of the volume of the cell and the query volume 
    644         static float sTermMinSize; 
    645  
    646         // minimal pvs per node to still get subdivided 
    647         static int sTermMinPvs; 
    648  
    649         // minimal ray number per node to still get subdivided 
    650         static int sTermMinRays; 
    651          
    652         // maximal cost ration to subdivide a node 
    653         static float sTermMaxCostRatio; 
    654          
    655         // maximal contribution per ray to subdivide the node 
    656         static float sTermMaxRayContribution; 
    657534 
    658535protected: 
Note: See TracChangeset for help on using the changeset viewer.