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

Line 
1#ifndef __HASHPVS_H
2#define __HASHPVS_H
3
4//#include <hash_set>
5#include "common.h"
6#include <math.h>
7#include "PvsBase.h"
8#include "google/dense_hash_set"
9#include "google/dense_hash_map"
10
11
12namespace GtpVisibilityPreprocessor {
13
14
15/*template<typename T>
16struct my_hash_compare
17{
18   enum
19   {
20      bucket_size = 1,
21      min_buckets = 16
22   };
23
24   int operator()(int a) const
25   {
26           return a;
27   }
28
29
30   bool operator()(T a, T b) const
31   {
32      return a < b;
33   }
34};*/
35
36
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> >
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
43/** Iterator over a hash pvs.
44*/
45template<typename T, typename S>
46class HashPvsIterator
47{
48public:
49       
50        HashPvsIterator<T, S>() {}
51
52        HashPvsIterator<T, S>(const typename CONST_HASH_ITERATOR &itCurrent,
53                                                  const typename CONST_HASH_ITERATOR &itEnd):
54        mItCurrent(itCurrent), mItEnd(itEnd)
55        {
56        }
57
58        bool HasMoreEntries() const
59        {
60                return (mItCurrent != mItEnd);
61        }
62
63        T Next(S &pdf)
64        {
65                T sample = (*mItCurrent).second;
66                ++ mItCurrent;
67
68                return sample;
69        }
70
71        T Next()
72        {
73                T sample = (*mItCurrent).second;
74                ++ mItCurrent;
75
76                return sample;
77        }
78       
79private:
80        typename CONST_HASH_ITERATOR mItCurrent;
81        typename CONST_HASH_ITERATOR mItEnd;
82};
83
84
85/** Template class representing the Potentially Visible Set (PVS)
86        mainly from a view cell, but also e.g., from objects.
87*/
88template<typename T, typename S>
89class HashPvs//: public PvsBase<T>
90{
91        template<typename T, typename S> friend class HashPvsIterator;
92
93public:
94
95        HashPvs()
96        {
97                 mEntries.set_deleted_key(-1);
98                 mEntries.set_empty_key(-2);
99        };
100
101        int GetSize() const;
102        bool Empty() const;
103
104        /** Adds sample to PVS.
105                @returns contribution of sample (0 or 1)
106        */
107        float AddSample(T sample, const float pdf);
108        /** Adds sample to PVS without checking for presence of the sample
109                warning: pvs remains unsorted!
110        */
111        void AddSampleDirty(T sample, const float pdf);
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        */
115        bool AddSampleDirtyCheck(T sample, const float pdf);
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
126        inline bool RequiresResort() const;
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        */
133        inline bool Find(T sample, typename HASH_ITERATOR &it);
134
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
151        inline int GetSamples() const   { return mSamples; }
152
153        void MergeInPlace(const HashPvs<T, S> &a)
154        {
155                std::cerr << "hashpvs: mergeinplace not implemented yet" << std::endl;
156        }
157
158        inline bool RequiresResortLog() const { return false; }
159
160        void Reserve(const int n)
161        { // not necessary
162        }
163
164        /** Sort pvs entries assume that the pvs contains unique entries
165        */
166        void SimpleSort()
167        {       // not necessary
168        }
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        }
183
184
185protected:
186
187        /// hash table of PVS entries
188        HASH_SET mEntries;
189
190        /// Number of samples used to create the PVS
191        int mSamples;
192};
193
194
195template <typename T, typename S>
196bool HashPvs<T, S>::Find(T sample, typename HASH_ITERATOR &it)
197{
198        it = mEntries.find(sample->GetId());
199
200        // already in map
201        return (it != mEntries.end());
202}
203
204
205template <typename T, typename S>
206int HashPvs<T, S>::GetSize() const
207{
208        return (int)mEntries.size();
209}
210
211
212template <typename T, typename S>
213bool HashPvs<T, S>::Empty() const
214{
215        return mEntries.empty();
216}
217
218
219template <typename T, typename S>
220float HashPvs<T, S>::AddSample(T sample, const float pdf)
221{
222        static HASH_ITERATOR it;
223
224        if (Find(sample, it))
225                return 0.0f;
226       
227        mEntries.insert(pair<int, T>(sample->GetId(), sample));
228        return 1.0f;
229}
230       
231
232template <typename T, typename S>
233void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
234{
235        static HASH_ITERATOR it;
236
237        // not yet in map
238        if (!Find(sample, it))
239        {
240                mEntries.insert(pair<int, T>(sample->GetId(), sample));
241        }
242}
243
244
245template <typename T, typename S>
246bool HashPvs<T, S>::AddSampleDirtyCheck(T sample,
247                                                                                const float pdf)
248{
249        static pair<HASH_ITERATOR, bool> result;
250        result = mEntries.insert(pair<int, T>(sample->GetId(), sample));
251        return result.second;
252
253        /*
254        static CONST_HASH_ITERATOR it;
255
256        it = mEntries.find(sample->GetId());//, sample);
257
258        // already in map
259        const bool found = (it != mEntries.end());
260
261        //return false;
262        // already in map
263        if (found)
264        //if (Find(pair<int, T>(sample->GetId(), sample), it))
265                return false;
266
267        mEntries.insert(pair<int, T>(sample->GetId(), sample));
268       
269        return true;*/
270}
271
272
273template <typename T, typename S>
274void HashPvs<T, S>::Sort()
275{
276}
277
278
279template <typename T, typename S>
280void HashPvs<T, S>::Clear(const bool trim = true)
281{
282        mEntries.clear();
283}
284
285
286template <typename T, typename S>
287bool HashPvs<T, S>::IsDirty() const
288{
289        return false;
290}
291
292
293template <typename T, typename S>
294bool HashPvs<T, S>::RequiresResort() const
295{
296        return false;
297}
298
299
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;
306}
307
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{
360        CONST_HASH_ITERATOR ait, ait_end = a.mEntries.end();
361
362        for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
363        {
364                mergedPvs.AddSample((*ait).second, 1.0f);
365        }
366
367        CONST_HASH_ITERATOR bit, bit_end = b.mEntries.end();
368
369        for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
370        {
371                mergedPvs.AddSample((*bit).second, 1.0f);
372        }
373}
374
375}
376
377#endif
378
Note: See TracBrowser for help on using the repository browser.