source: GTP/trunk/Lib/Vis/Preprocessing/src/HashPvs.h @ 2633

Revision 2633, 7.6 KB checked in by mattausch, 17 years ago (diff)

revived hash pvs

RevLine 
[2102]1#ifndef __HASHPVS_H
2#define __HASHPVS_H
3
[2176]4//#include <hash_set>
[2102]5#include "common.h"
6#include <math.h>
7#include "PvsBase.h"
[2161]8#include "google/dense_hash_set"
[2162]9#include "google/dense_hash_map"
[2102]10
11
12namespace GtpVisibilityPreprocessor {
13
14
[2199]15/*template<typename T>
[2116]16struct my_hash_compare
17{
18   enum
19   {
[2146]20      bucket_size = 1,
21      min_buckets = 16
[2116]22   };
[2102]23
[2162]24   int operator()(int a) const
25   {
26           return a;
[2116]27   }
28
[2162]29
[2116]30   bool operator()(T a, T b) const
31   {
32      return a < b;
33   }
[2199]34};*/
[2116]35
36
[2162]37//#define HASH_SET google::dense_hash_set<T, my_hash_compare<T> >
38#define HASH_SET google::dense_hash_map<int, T>//, hash_compare<int> >
[2161]39//#define HASH_SET stdext::hash_set<T, my_hash_compare<T> >
40#define HASH_ITERATOR HASH_SET::iterator
41#define CONST_HASH_ITERATOR HASH_SET::const_iterator
42
[2116]43/** Iterator over a hash pvs.
44*/
45template<typename T, typename S>
46class HashPvsIterator
47{
48public:
49       
50        HashPvsIterator<T, S>() {}
51
[2161]52        HashPvsIterator<T, S>(const typename CONST_HASH_ITERATOR &itCurrent,
53                                                  const typename CONST_HASH_ITERATOR &itEnd):
[2116]54        mItCurrent(itCurrent), mItEnd(itEnd)
55        {
56        }
57
58        bool HasMoreEntries() const
59        {
60                return (mItCurrent != mItEnd);
61        }
62
[2117]63        T Next(S &pdf)
[2116]64        {
[2162]65                T sample = (*mItCurrent).second;
[2161]66                ++ mItCurrent;
67
68                return sample;
[2116]69        }
[2117]70
71        T Next()
72        {
[2162]73                T sample = (*mItCurrent).second;
[2161]74                ++ mItCurrent;
75
76                return sample;
[2117]77        }
[2116]78       
79private:
[2161]80        typename CONST_HASH_ITERATOR mItCurrent;
81        typename CONST_HASH_ITERATOR mItEnd;
[2116]82};
83
84
[2102]85/** Template class representing the Potentially Visible Set (PVS)
86        mainly from a view cell, but also e.g., from objects.
87*/
[2116]88template<typename T, typename S>
89class HashPvs//: public PvsBase<T>
[2102]90{
[2116]91        template<typename T, typename S> friend class HashPvsIterator;
[2102]92
93public:
94
[2530]95        HashPvs()
[2162]96        {
97                 mEntries.set_deleted_key(-1);
98                 mEntries.set_empty_key(-2);
99        };
[2102]100
101        int GetSize() const;
102        bool Empty() const;
103
104        /** Adds sample to PVS.
105                @returns contribution of sample (0 or 1)
106        */
[2116]107        float AddSample(T sample, const float pdf);
[2102]108        /** Adds sample to PVS without checking for presence of the sample
109                warning: pvs remains unsorted!
110        */
[2116]111        void AddSampleDirty(T sample, const float pdf);
[2102]112        /** Adds sample dirty (on the end of the vector) but
113                first checks if sample is already in clean part of the pvs.
114        */
[2116]115        bool AddSampleDirtyCheck(T sample, const float pdf);
[2102]116        /** Sort pvs entries - this should always be called after a
117                sequence of AddSampleDirty calls
118        */
119        void Sort();
120        /** Clears the pvs.
121        */
122        void Clear(const bool trim = true);
123
124        bool IsDirty() const;
125
[2164]126        inline bool RequiresResort() const;
[2116]127        /** Finds sample in PVS.
128                @param checkDirty if dirty part of the pvs should be checked for entry
129                (warning: linear runtime in dirty part)
130                @returns iterator on the sample if found, else the place where
131                it would be added in the sorted vector.
132        */
[2161]133        inline bool Find(T sample, typename HASH_ITERATOR &it);
[2102]134
[2116]135        typename HashPvsIterator<T, S> GetIterator() const;
136        /** Compute continuous PVS difference
137        */
138        float GetPvsHomogenity(HashPvs<T, S> &pvs);
139
140        static void Merge(HashPvs<T, S> &mergedPvs,
141                                          const HashPvs<T, S> &a,
142                                          const HashPvs<T, S> &b);
143
144        static int GetEntrySizeByte();
145        static float GetEntrySize();
146
147        bool GetSampleContribution(T sample,
148                                                   const float pdf,
149                                                           float &contribution);
150
[2530]151        inline int GetSamples() const   { return mSamples; }
[2116]152
153        void MergeInPlace(const HashPvs<T, S> &a)
154        {
[2633]155                std::cerr << "hashpvs: mergeinplace not implemented yet" << std::endl;
[2116]156        }
157
[2530]158        inline bool RequiresResortLog() const { return false; }
[2116]159
[2633]160        void Reserve(const int n)
161        { // not necessary
162        }
[2116]163
164        /** Sort pvs entries assume that the pvs contains unique entries
165        */
[2633]166        void SimpleSort()
167        {       // not necessary
168        }
[2116]169
170        int SubtractPvs(const HashPvs<T, S> &pvs)
171        {
172                cerr << "not yet implemented" << endl;
173                return 0;
174        }
175        /** Compute continuous PVS difference
176        */
177        void ComputeContinuousPvsDifference(HashPvs<T, S> &pvs,
178                                                                                float &pvsReduction,
179                                                                                float &pvsEnlargement)
180        {
181                cerr << "not yet implemented" << endl;
182        }
[2530]183
184
[2102]185protected:
186
[2116]187        /// hash table of PVS entries
188        HASH_SET mEntries;
[2102]189
190        /// Number of samples used to create the PVS
191        int mSamples;
192};
193
194
[2116]195template <typename T, typename S>
[2161]196bool HashPvs<T, S>::Find(T sample, typename HASH_ITERATOR &it)
[2102]197{
[2162]198        it = mEntries.find(sample->GetId());
[2116]199
200        // already in map
201        return (it != mEntries.end());
[2102]202}
203
204
[2116]205template <typename T, typename S>
206int HashPvs<T, S>::GetSize() const
[2102]207{
[2116]208        return (int)mEntries.size();
[2102]209}
210
211
[2116]212template <typename T, typename S>
213bool HashPvs<T, S>::Empty() const
[2102]214{
[2116]215        return mEntries.empty();
[2102]216}
[2116]217
218
219template <typename T, typename S>
220float HashPvs<T, S>::AddSample(T sample, const float pdf)
221{
[2161]222        static HASH_ITERATOR it;
[2116]223
224        if (Find(sample, it))
225                return 0.0f;
[2102]226       
[2162]227        mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]228        return 1.0f;
229}
230       
[2102]231
[2116]232template <typename T, typename S>
233void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
[2102]234{
[2161]235        static HASH_ITERATOR it;
[2116]236
237        // not yet in map
238        if (!Find(sample, it))
239        {
[2162]240                mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]241        }
[2102]242}
243
244
[2116]245template <typename T, typename S>
246bool HashPvs<T, S>::AddSampleDirtyCheck(T sample,
247                                                                                const float pdf)
[2102]248{
[2164]249        static pair<HASH_ITERATOR, bool> result;
250        result = mEntries.insert(pair<int, T>(sample->GetId(), sample));
251        return result.second;
252
253        /*
[2162]254        static CONST_HASH_ITERATOR it;
[2116]255
[2162]256        it = mEntries.find(sample->GetId());//, sample);
257
[2116]258        // already in map
[2162]259        const bool found = (it != mEntries.end());
[2146]260
[2164]261        //return false;
[2146]262        // already in map
[2162]263        if (found)
264        //if (Find(pair<int, T>(sample->GetId(), sample), it))
[2116]265                return false;
[2162]266
267        mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]268       
[2164]269        return true;*/
[2102]270}
271
272
[2116]273template <typename T, typename S>
274void HashPvs<T, S>::Sort()
[2102]275{
276}
277
278
[2116]279template <typename T, typename S>
280void HashPvs<T, S>::Clear(const bool trim = true)
[2102]281{
[2116]282        mEntries.clear();
[2102]283}
284
285
[2116]286template <typename T, typename S>
287bool HashPvs<T, S>::IsDirty() const
[2102]288{
289        return false;
290}
291
292
[2116]293template <typename T, typename S>
294bool HashPvs<T, S>::RequiresResort() const
[2102]295{
296        return false;
297}
298
299
[2116]300template <typename T, typename S>
301typename HashPvsIterator<T, S> HashPvs<T, S>::GetIterator() const
302{
303        HashPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
304
305        return pit;
[2102]306}
307
[2116]308
309template <typename T, typename S>
310float HashPvs<T, S>::GetEntrySize()
311{
312        return (float)(sizeof(T)) / float(1024 * 1024);
313}
314
315
316template <typename T, typename S>
317int HashPvs<T, S>::GetEntrySizeByte()
318{
319        return sizeof(T);
320}
321
322
323template <typename T, typename S>
324float HashPvs<T, S>::GetPvsHomogenity(HashPvs<T, S> &pvs)
325{
326        float pvsReduction, pvsEnlargement;
327
328        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
329
330        return pvsReduction + pvsEnlargement;
331}
332
333
334template <typename T, typename S>
335bool HashPvs<T, S>::GetSampleContribution(T sample,
336                                                                          const float pdf,
337                                                                          float &contribution)
338{
339        HASH_SET::iterator it;
340        const bool entryFound = Find(sample, it);
341
342        if (entryFound) 
343        {
344                contribution = 0.0f;
345                return false;
346        }
347        else
348        {
349                contribution = 1.0f;
350                return true;
351        }
352}
353
354
355template <typename T, typename S>
356void HashPvs<T, S>::Merge(HashPvs<T, S> &mergedPvs,
357                                                  const HashPvs<T, S> &a,
358                                                  const HashPvs<T, S> &b)
359{
[2161]360        CONST_HASH_ITERATOR ait, ait_end = a.mEntries.end();
[2116]361
362        for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
363        {
[2162]364                mergedPvs.AddSample((*ait).second, 1.0f);
[2116]365        }
366
[2161]367        CONST_HASH_ITERATOR bit, bit_end = b.mEntries.end();
[2116]368
369        for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
370        {
[2162]371                mergedPvs.AddSample((*bit).second, 1.0f);
[2116]372        }
373}
374
375}
376
[2102]377#endif
378
Note: See TracBrowser for help on using the repository browser.