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

Revision 2206, 7.6 KB checked in by mattausch, 18 years ago (diff)
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
[2164]95        HashPvs()//: mEntries(1009)
[2162]96        {
97                 mEntries.set_deleted_key(-1);
98                 mEntries.set_empty_key(-2);
99        };
[2102]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        */
[2116]108        float AddSample(T sample, const float pdf);
[2102]109
110        /** Adds sample to PVS without checking for presence of the sample
111                warning: pvs remains unsorted!
112        */
[2116]113        void AddSampleDirty(T sample, const float pdf);
[2102]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        */
[2116]118        bool AddSampleDirtyCheck(T sample, const float pdf);
[2102]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
[2164]131        inline bool RequiresResort() const;
[2102]132
[2116]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        */
[2161]139        inline bool Find(T sample, typename HASH_ITERATOR &it);
[2102]140
[2116]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        {
[2206]165                cerr << "hashpvs: mergeinplace not implemented yet" << endl;
[2116]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        }
[2102]199protected:
200
[2116]201        /// hash table of PVS entries
202        HASH_SET mEntries;
[2102]203
204        /// Number of samples used to create the PVS
205        int mSamples;
206};
207
208
[2116]209template <typename T, typename S>
[2161]210bool HashPvs<T, S>::Find(T sample, typename HASH_ITERATOR &it)
[2102]211{
[2162]212        it = mEntries.find(sample->GetId());
[2116]213
214        // already in map
215        return (it != mEntries.end());
[2102]216}
217
218
[2116]219template <typename T, typename S>
220int HashPvs<T, S>::GetSize() const
[2102]221{
[2116]222        return (int)mEntries.size();
[2102]223}
224
225
[2116]226template <typename T, typename S>
227bool HashPvs<T, S>::Empty() const
[2102]228{
[2116]229        return mEntries.empty();
[2102]230}
[2116]231
232
233template <typename T, typename S>
234float HashPvs<T, S>::AddSample(T sample, const float pdf)
235{
[2161]236        static HASH_ITERATOR it;
[2116]237
238        if (Find(sample, it))
239                return 0.0f;
[2102]240       
[2162]241        mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]242        return 1.0f;
243}
244       
[2102]245
[2116]246template <typename T, typename S>
247void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
[2102]248{
[2161]249        static HASH_ITERATOR it;
[2116]250
251        // not yet in map
252        if (!Find(sample, it))
253        {
[2162]254                mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]255        }
[2102]256}
257
258
[2116]259template <typename T, typename S>
260bool HashPvs<T, S>::AddSampleDirtyCheck(T sample,
261                                                                                const float pdf)
[2102]262{
[2164]263        static pair<HASH_ITERATOR, bool> result;
264        result = mEntries.insert(pair<int, T>(sample->GetId(), sample));
265        return result.second;
266
267        /*
[2162]268        static CONST_HASH_ITERATOR it;
[2116]269
[2162]270        it = mEntries.find(sample->GetId());//, sample);
271
[2116]272        // already in map
[2162]273        const bool found = (it != mEntries.end());
[2146]274
[2164]275        //return false;
[2146]276        // already in map
[2162]277        if (found)
278        //if (Find(pair<int, T>(sample->GetId(), sample), it))
[2116]279                return false;
[2162]280
281        mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]282       
[2164]283        return true;*/
[2102]284}
285
286
[2116]287template <typename T, typename S>
288void HashPvs<T, S>::Sort()
[2102]289{
290}
291
292
[2116]293template <typename T, typename S>
294void HashPvs<T, S>::Clear(const bool trim = true)
[2102]295{
[2116]296        mEntries.clear();
[2102]297}
298
299
[2116]300template <typename T, typename S>
301bool HashPvs<T, S>::IsDirty() const
[2102]302{
303        return false;
304}
305
306
[2116]307template <typename T, typename S>
308bool HashPvs<T, S>::RequiresResort() const
[2102]309{
310        return false;
311}
312
313
[2116]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;
[2102]320}
321
[2116]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{
[2161]374        CONST_HASH_ITERATOR ait, ait_end = a.mEntries.end();
[2116]375
376        for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
377        {
[2162]378                mergedPvs.AddSample((*ait).second, 1.0f);
[2116]379        }
380
[2161]381        CONST_HASH_ITERATOR bit, bit_end = b.mEntries.end();
[2116]382
383        for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
384        {
[2162]385                mergedPvs.AddSample((*bit).second, 1.0f);
[2116]386        }
387}
388
389}
390
[2102]391#endif
392
Note: See TracBrowser for help on using the repository browser.