Ignore:
Timestamp:
02/15/07 13:19:17 (17 years ago)
Author:
mattausch
Message:

implemented bit pvs (warnin: only worjs for preprocessing)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • GTP/trunk/Lib/Vis/Preprocessing/src/BitVectorPvs.h

    r2116 r2117  
    1313typedef vector<bool> bit_vector; 
    1414 
     15 
    1516/** Iterator over a bitvector pvs. 
    1617*/ 
    17 #if 0 
    1818template<typename T, typename S> 
    1919class BitVectorPvsIterator 
    … …  
    2121public: 
    2222         
    23         HashPvsIterator<T, S>() {} 
    24  
    25         HashPvsIterator<T, S>(const typename HASH_SET::const_iterator &itCurrent, 
    26                                                   const typename HASH_SET::const_iterator &itEnd): 
    27         mItCurrent(itCurrent), mItEnd(itEnd) 
     23        BitVectorPvsIterator<T, S>(const typename bit_vector::const_iterator &itBegin, 
     24                                                           const typename bit_vector::const_iterator &itEnd 
     25                                                           //,const int lastElement 
     26                                                           ): 
     27        mItCurrent(itBegin), mItEnd(itEnd), mDistance(0)//, mLastElement 
    2828        { 
    2929        } 
    … …  
    3131        bool HasMoreEntries() const  
    3232        { 
    33                 return (mItCurrent != mItEnd); 
    34         } 
    35  
    36         PvsEntry<T, S> Next() 
     33                // find next element in bit vector 
     34                // warning: has to do traversal each time 
     35                typename bit_vector::const_iterator itNext = mItCurrent; 
     36 
     37                for (;(itNext != mItEnd) && !(*itNext); ++ itNext); 
     38 
     39                return (itNext != mItEnd); 
     40        } 
     41 
     42        T Next(S &pdf) 
     43        { 
     44                return Next(); 
     45        } 
     46         
     47        T Next() 
    3748        { 
    3849                // hack: create new pvs entry 
    39                 return PvsEntry<T, S>(*(mItCurrent) ++, S(0.0)); 
    40         } 
    41          
     50                for (; !(*mItCurrent); ++ mItCurrent, ++ mDistance); 
     51 
     52                T sample = sObjects[mDistance]; 
     53 
     54                ++ mDistance; 
     55                ++ mItCurrent; 
     56 
     57                return sample; 
     58        } 
     59 
     60         
     61        // vector of objects corresponding to pvs entries 
     62        static vector<T> sObjects; 
     63 
    4264private: 
    43         typename HASH_SET::const_iterator mItCurrent; 
    44         typename HASH_SET::const_iterator mItEnd; 
     65 
     66        typename bit_vector::const_iterator mItCurrent; 
     67        //typename bit_vector::const_iterator mItNext; 
     68        typename bit_vector::const_iterator mItEnd; 
     69         
     70        // note: store distance explicitly because I  
     71        // don't know how efficient 
     72        // std::distance is on specialisation of vector<bool> 
     73        int mDistance; 
    4574}; 
    46 #endif 
    47  
    48 #if 0 
     75 
     76 
    4977/** Pvs implemented as bitvector 
    5078*/ 
    … …  
    5684public: 
    5785 
    58         //HashPvs(): mEntries((Intersectable *)100) {}; 
    59         HashPvs() {}; 
     86        BitVectorPvs(); 
    6087        //virtual ~HashPvs() {}; 
    6188 
    … …  
    92119 
    93120        /** Finds sample in PVS. 
    94                 @param checkDirty if dirty part of the pvs should be checked for entry  
    95                 (warning: linear runtime in dirty part) 
    96                 @returns iterator on the sample if found, else the place where  
    97                 it would be added in the sorted vector. 
    98         */ 
    99         bool Find(T sample, typename HASH_SET::iterator &it); 
    100  
    101         typename HashPvsIterator<T, S> GetIterator() const; 
     121        */ 
     122        bool Find(T sample); 
     123 
     124        typename BitVectorPvsIterator<T, S> GetIterator() const; 
    102125 
    103126        /** Compute continuous PVS difference  
    104127        */ 
    105         float GetPvsHomogenity(HashPvs<T, S> &pvs); 
    106  
    107         static void Merge(HashPvs<T, S> &mergedPvs,  
    108                                           const HashPvs<T, S> &a,  
    109                                           const HashPvs<T, S> &b); 
     128        float GetPvsHomogenity(BitVectorPvs<T, S> &pvs); 
     129 
     130        static void Merge(BitVectorPvs<T, S> &mergedPvs,  
     131                                          const BitVectorPvs<T, S> &a,  
     132                                          const BitVectorPvs<T, S> &b); 
    110133 
    111134        static int GetEntrySizeByte();  
    … …  
    121144        } 
    122145 
    123         void MergeInPlace(const HashPvs<T, S> &a) 
     146        void MergeInPlace(const BitVectorPvs<T, S> &a) 
    124147        { 
    125148                cerr << "not implemented yet" << endl; 
    … …  
    133156        void Reserve(const int n)  
    134157        {  
     158                mEntries.reserve(n); 
     159        } 
     160 
     161        /** Sort pvs entries assume that the pvs contains unique entries 
     162        */ 
     163        void SimpleSort() 
     164        { 
    135165                // not necessary 
    136166        } 
    137167 
    138         /** Sort pvs entries assume that the pvs contains unique entries 
    139         */ 
    140         void SimpleSort() 
    141         { 
    142                 // not necessary 
    143         } 
    144  
    145         int SubtractPvs(const HashPvs<T, S> &pvs) 
     168        int SubtractPvs(const BitVectorPvs<T, S> &pvs) 
    146169        { 
    147170                cerr << "not yet implemented" << endl; 
    … …  
    151174        /** Compute continuous PVS difference  
    152175        */ 
    153         void ComputeContinuousPvsDifference(HashPvs<T, S> &pvs,  
     176        void ComputeContinuousPvsDifference(BitVectorPvs<T, S> &pvs,  
    154177                                                                                float &pvsReduction, 
    155178                                                                                float &pvsEnlargement) 
    … …  
    157180                cerr << "not yet implemented" << endl; 
    158181        } 
     182 
     183 
     184        static void SetPvsSize(const int pvsSize) { sPvsSize = pvsSize; }; 
     185         
    159186protected: 
    160187 
    161188        /// hash table of PVS entries 
    162         HASH_SET mEntries;  
     189        bit_vector mEntries;  
    163190 
    164191        /// Number of samples used to create the PVS 
    165192        int mSamples; 
     193 
     194public: 
     195        static int sPvsSize; 
    166196}; 
    167197 
    168198 
    169199template <typename T, typename S> 
    170 bool HashPvs<T, S>::Find(T sample, typename HASH_SET::iterator &it) 
    171 { 
    172         it = mEntries.find(sample); 
    173  
    174         // already in map 
    175         return (it != mEntries.end()); 
    176 } 
    177  
    178  
    179 template <typename T, typename S> 
    180 int HashPvs<T, S>::GetSize() const 
    181 { 
    182         return (int)mEntries.size(); 
    183 } 
    184  
    185  
    186 template <typename T, typename S> 
    187 bool HashPvs<T, S>::Empty() const 
    188 { 
    189         return mEntries.empty(); 
    190 } 
    191  
    192  
    193 template <typename T, typename S> 
    194 float HashPvs<T, S>::AddSample(T sample, const float pdf) 
    195 { 
    196         HASH_SET::iterator it; 
    197  
    198         if (Find(sample, it)) 
     200BitVectorPvs<T, S>::BitVectorPvs() 
     201{ 
     202        // initialize bit vector 
     203        mEntries.reserve(sPvsSize); 
     204        mEntries.resize(sPvsSize); 
     205 
     206        // set pvs entries to false 
     207        Clear(); 
     208} 
     209 
     210 
     211template <typename T, typename S> 
     212bool BitVectorPvs<T, S>::Find(T sample) 
     213{ 
     214        return mEntries[sample->GetId()]; 
     215} 
     216 
     217 
     218template <typename T, typename S> 
     219int BitVectorPvs<T, S>::GetSize() const 
     220{ 
     221        int size = 0; 
     222        bit_vector::const_iterator bit, bit_end = mEntries.end(); 
     223 
     224        for (bit = mEntries.begin(); bit != bit_end; ++ bit) 
     225        { 
     226                if (*bit) ++ size; 
     227        } 
     228 
     229        return size; 
     230} 
     231 
     232 
     233template <typename T, typename S> 
     234bool BitVectorPvs<T, S>::Empty() const 
     235{ 
     236        bit_vector::const_iterator bit, bit_end = mEntries.end(); 
     237 
     238        for (bit = mEntries.begin(); bit != bit_end; ++ bit) 
     239        { 
     240                if (*bit) return false; 
     241        } 
     242 
     243        return true; 
     244} 
     245 
     246 
     247template <typename T, typename S> 
     248float BitVectorPvs<T, S>::AddSample(T sample, const float pdf) 
     249{ 
     250        if (Find(sample)) 
    199251                return 0.0f; 
    200252         
    201         mEntries.insert(sample); 
     253        mEntries[sample->GetId()] = true; 
     254 
    202255        return 1.0f; 
    203256} 
    … …  
    205258 
    206259template <typename T, typename S> 
    207 void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf) 
    208 { 
    209         HASH_SET::iterator it; 
    210  
    211         // not yet in map 
    212         if (!Find(sample, it)) 
    213         { 
    214                 mEntries.insert(sample);         
    215         } 
    216 } 
    217  
    218  
    219 template <typename T, typename S> 
    220 bool HashPvs<T, S>::AddSampleDirtyCheck(T sample,  
     260void BitVectorPvs<T, S>::AddSampleDirty(T sample, const float pdf) 
     261{ 
     262        if (!Find(sample)) 
     263        { 
     264                mEntries[sample->GetId()] = true; 
     265        } 
     266} 
     267 
     268 
     269template <typename T, typename S> 
     270bool BitVectorPvs<T, S>::AddSampleDirtyCheck(T sample,  
    221271                                                                                const float pdf) 
    222272{ 
    223         HASH_SET::iterator it; 
    224  
    225         // already in map 
    226         if (Find(sample, it)) 
     273        if (Find(sample)) 
    227274                return false; 
    228275         
    229         mEntries.insert(sample); 
     276        mEntries[sample->GetId()] = true; 
    230277        return true; 
    231278} 
    … …  
    233280 
    234281template <typename T, typename S> 
    235 void HashPvs<T, S>::Sort() 
    236 { 
    237 } 
    238  
    239  
    240 template <typename T, typename S> 
    241 void HashPvs<T, S>::Clear(const bool trim = true) 
    242 { 
    243         mEntries.clear(); 
    244 } 
    245  
    246  
    247 template <typename T, typename S> 
    248 bool HashPvs<T, S>::IsDirty() const 
     282void BitVectorPvs<T, S>::Sort() 
     283{ 
     284} 
     285 
     286 
     287template <typename T, typename S> 
     288void BitVectorPvs<T, S>::Clear(const bool trim = true) 
     289{ 
     290        bit_vector::iterator bit, bit_end = mEntries.end(); 
     291        for (bit = mEntries.begin(); bit != bit_end; ++ bit) 
     292        { 
     293                (*bit) = false; 
     294        } 
     295} 
     296 
     297 
     298template <typename T, typename S> 
     299bool BitVectorPvs<T, S>::IsDirty() const 
    249300{ 
    250301        return false; 
    … …  
    253304 
    254305template <typename T, typename S> 
    255 bool HashPvs<T, S>::RequiresResort() const 
     306bool BitVectorPvs<T, S>::RequiresResort() const 
    256307{ 
    257308        return false; 
    … …  
    260311 
    261312template <typename T, typename S> 
    262 typename HashPvsIterator<T, S> HashPvs<T, S>::GetIterator() const 
    263 { 
    264         HashPvsIterator<T, S> pit(mEntries.begin(), mEntries.end()); 
     313typename BitVectorPvsIterator<T, S> BitVectorPvs<T, S>::GetIterator() const 
     314{ 
     315        BitVectorPvsIterator<T, S> pit(mEntries.begin(), mEntries.end()); 
    265316 
    266317        return pit; 
    … …  
    269320 
    270321template <typename T, typename S> 
    271 float HashPvs<T, S>::GetEntrySize() 
    272 { 
    273         return (float)(sizeof(T)) / float(1024 * 1024); 
    274 } 
    275  
    276  
    277 template <typename T, typename S> 
    278 int HashPvs<T, S>::GetEntrySizeByte() 
    279 { 
    280         return sizeof(T); 
    281 } 
    282  
    283  
    284 template <typename T, typename S> 
    285 float HashPvs<T, S>::GetPvsHomogenity(HashPvs<T, S> &pvs)  
     322float BitVectorPvs<T, S>::GetEntrySize() 
     323{ 
     324        return (float)(sizeof(bool)) / float(1024 * 1024); 
     325} 
     326 
     327 
     328template <typename T, typename S> 
     329int BitVectorPvs<T, S>::GetEntrySizeByte() 
     330{ 
     331        return sizeof(bool); 
     332} 
     333 
     334 
     335template <typename T, typename S> 
     336float BitVectorPvs<T, S>::GetPvsHomogenity(BitVectorPvs<T, S> &pvs)  
    286337{ 
    287338        float pvsReduction, pvsEnlargement; 
    … …  
    294345 
    295346template <typename T, typename S> 
    296 bool HashPvs<T, S>::GetSampleContribution(T sample, 
     347bool BitVectorPvs<T, S>::GetSampleContribution(T sample, 
    297348                                                                          const float pdf, 
    298349                                                                          float &contribution)  
    299350{ 
    300         HASH_SET::iterator it; 
    301         const bool entryFound = Find(sample, it); 
     351        const bool entryFound = Find(sample); 
    302352 
    303353        if (entryFound)   
    … …  
    315365 
    316366template <typename T, typename S> 
    317 void HashPvs<T, S>::Merge(HashPvs<T, S> &mergedPvs,  
    318                                                   const HashPvs<T, S> &a,  
    319                                                   const HashPvs<T, S> &b) 
    320 { 
     367void BitVectorPvs<T, S>::Merge(BitVectorPvs<T, S> &mergedPvs,  
     368                                                           const BitVectorPvs<T, S> &a,  
     369                                                           const BitVectorPvs<T, S> &b) 
     370{ 
     371        bit_vector::iterator bit, bit_end = mergedPvs.mEntries.end(); 
     372        bit_vector::const_iterator bitA =  a.mEntries.begin(), bitB = b.mEntries.begin(); 
     373 
     374        for (bit = mergedPvs.mEntries.begin(); bit != bit_end; ++ bit, ++ bitA, ++ bitB) 
     375        { 
     376        (*bit) = (*bitA) | (*bitB); 
     377        } 
     378} 
     379 
     380 
     381template<typename T, typename S> 
     382int BitVectorPvs<T, S>::sPvsSize = 0; 
     383 
     384template<typename T, typename S> 
     385vector<T> BitVectorPvsIterator<T, S>::sObjects; 
     386 
    321387} 
    322388 
    323389#endif 
    324390 
    325 } 
    326  
    327 #endif 
    328  
Note: See TracChangeset for help on using the changeset viewer.