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

Revision 2206, 7.6 KB checked in by mattausch, 18 years ago (diff)
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()//: mEntries(1009)
96        {
97                 mEntries.set_deleted_key(-1);
98                 mEntries.set_empty_key(-2);
99        };
100        //virtual ~HashPvs() {};
101
102        int GetSize() const;
103        bool Empty() const;
104
105        /** Adds sample to PVS.
106                @returns contribution of sample (0 or 1)
107        */
108        float AddSample(T sample, const float pdf);
109
110        /** Adds sample to PVS without checking for presence of the sample
111                warning: pvs remains unsorted!
112        */
113        void AddSampleDirty(T sample, const float pdf);
114
115        /** Adds sample dirty (on the end of the vector) but
116                first checks if sample is already in clean part of the pvs.
117        */
118        bool AddSampleDirtyCheck(T sample, const float pdf);
119
120        /** Sort pvs entries - this should always be called after a
121                sequence of AddSampleDirty calls
122        */
123        void Sort();
124
125        /** Clears the pvs.
126        */
127        void Clear(const bool trim = true);
128
129        bool IsDirty() const;
130
131        inline bool RequiresResort() const;
132
133        /** Finds sample in PVS.
134                @param checkDirty if dirty part of the pvs should be checked for entry
135                (warning: linear runtime in dirty part)
136                @returns iterator on the sample if found, else the place where
137                it would be added in the sorted vector.
138        */
139        inline bool Find(T sample, typename HASH_ITERATOR &it);
140
141        typename HashPvsIterator<T, S> GetIterator() const;
142
143        /** Compute continuous PVS difference
144        */
145        float GetPvsHomogenity(HashPvs<T, S> &pvs);
146
147        static void Merge(HashPvs<T, S> &mergedPvs,
148                                          const HashPvs<T, S> &a,
149                                          const HashPvs<T, S> &b);
150
151        static int GetEntrySizeByte();
152        static float GetEntrySize();
153
154        bool GetSampleContribution(T sample,
155                                                   const float pdf,
156                                                           float &contribution);
157
158        int GetSamples() const
159        {
160                return mSamples;
161        }
162
163        void MergeInPlace(const HashPvs<T, S> &a)
164        {
165                cerr << "hashpvs: mergeinplace not implemented yet" << endl;
166        }
167
168        bool RequiresResortLog() const
169        {
170                return false;
171        }
172
173        void Reserve(const int n)
174        {
175                // not necessary
176        }
177
178        /** Sort pvs entries assume that the pvs contains unique entries
179        */
180        void SimpleSort()
181        {
182                // not necessary
183        }
184
185        int SubtractPvs(const HashPvs<T, S> &pvs)
186        {
187                cerr << "not yet implemented" << endl;
188                return 0;
189        }
190
191        /** Compute continuous PVS difference
192        */
193        void ComputeContinuousPvsDifference(HashPvs<T, S> &pvs,
194                                                                                float &pvsReduction,
195                                                                                float &pvsEnlargement)
196        {
197                cerr << "not yet implemented" << endl;
198        }
199protected:
200
201        /// hash table of PVS entries
202        HASH_SET mEntries;
203
204        /// Number of samples used to create the PVS
205        int mSamples;
206};
207
208
209template <typename T, typename S>
210bool HashPvs<T, S>::Find(T sample, typename HASH_ITERATOR &it)
211{
212        it = mEntries.find(sample->GetId());
213
214        // already in map
215        return (it != mEntries.end());
216}
217
218
219template <typename T, typename S>
220int HashPvs<T, S>::GetSize() const
221{
222        return (int)mEntries.size();
223}
224
225
226template <typename T, typename S>
227bool HashPvs<T, S>::Empty() const
228{
229        return mEntries.empty();
230}
231
232
233template <typename T, typename S>
234float HashPvs<T, S>::AddSample(T sample, const float pdf)
235{
236        static HASH_ITERATOR it;
237
238        if (Find(sample, it))
239                return 0.0f;
240       
241        mEntries.insert(pair<int, T>(sample->GetId(), sample));
242        return 1.0f;
243}
244       
245
246template <typename T, typename S>
247void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
248{
249        static HASH_ITERATOR it;
250
251        // not yet in map
252        if (!Find(sample, it))
253        {
254                mEntries.insert(pair<int, T>(sample->GetId(), sample));
255        }
256}
257
258
259template <typename T, typename S>
260bool HashPvs<T, S>::AddSampleDirtyCheck(T sample,
261                                                                                const float pdf)
262{
263        static pair<HASH_ITERATOR, bool> result;
264        result = mEntries.insert(pair<int, T>(sample->GetId(), sample));
265        return result.second;
266
267        /*
268        static CONST_HASH_ITERATOR it;
269
270        it = mEntries.find(sample->GetId());//, sample);
271
272        // already in map
273        const bool found = (it != mEntries.end());
274
275        //return false;
276        // already in map
277        if (found)
278        //if (Find(pair<int, T>(sample->GetId(), sample), it))
279                return false;
280
281        mEntries.insert(pair<int, T>(sample->GetId(), sample));
282       
283        return true;*/
284}
285
286
287template <typename T, typename S>
288void HashPvs<T, S>::Sort()
289{
290}
291
292
293template <typename T, typename S>
294void HashPvs<T, S>::Clear(const bool trim = true)
295{
296        mEntries.clear();
297}
298
299
300template <typename T, typename S>
301bool HashPvs<T, S>::IsDirty() const
302{
303        return false;
304}
305
306
307template <typename T, typename S>
308bool HashPvs<T, S>::RequiresResort() const
309{
310        return false;
311}
312
313
314template <typename T, typename S>
315typename HashPvsIterator<T, S> HashPvs<T, S>::GetIterator() const
316{
317        HashPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
318
319        return pit;
320}
321
322
323template <typename T, typename S>
324float HashPvs<T, S>::GetEntrySize()
325{
326        return (float)(sizeof(T)) / float(1024 * 1024);
327}
328
329
330template <typename T, typename S>
331int HashPvs<T, S>::GetEntrySizeByte()
332{
333        return sizeof(T);
334}
335
336
337template <typename T, typename S>
338float HashPvs<T, S>::GetPvsHomogenity(HashPvs<T, S> &pvs)
339{
340        float pvsReduction, pvsEnlargement;
341
342        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
343
344        return pvsReduction + pvsEnlargement;
345}
346
347
348template <typename T, typename S>
349bool HashPvs<T, S>::GetSampleContribution(T sample,
350                                                                          const float pdf,
351                                                                          float &contribution)
352{
353        HASH_SET::iterator it;
354        const bool entryFound = Find(sample, it);
355
356        if (entryFound) 
357        {
358                contribution = 0.0f;
359                return false;
360        }
361        else
362        {
363                contribution = 1.0f;
364                return true;
365        }
366}
367
368
369template <typename T, typename S>
370void HashPvs<T, S>::Merge(HashPvs<T, S> &mergedPvs,
371                                                  const HashPvs<T, S> &a,
372                                                  const HashPvs<T, S> &b)
373{
374        CONST_HASH_ITERATOR ait, ait_end = a.mEntries.end();
375
376        for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
377        {
378                mergedPvs.AddSample((*ait).second, 1.0f);
379        }
380
381        CONST_HASH_ITERATOR bit, bit_end = b.mEntries.end();
382
383        for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
384        {
385                mergedPvs.AddSample((*bit).second, 1.0f);
386        }
387}
388
389}
390
391#endif
392
Note: See TracBrowser for help on using the repository browser.