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

Revision 2530, 7.6 KB checked in by mattausch, 17 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
[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
154        void MergeInPlace(const HashPvs<T, S> &a)
155        {
[2206]156                cerr << "hashpvs: mergeinplace not implemented yet" << endl;
[2116]157        }
158
[2530]159        inline bool RequiresResortLog() const { return false; }
[2116]160
[2530]161        void Reserve(const int n) { // not necessary }
[2116]162
163        /** Sort pvs entries assume that the pvs contains unique entries
164        */
[2530]165        void SimpleSort() {     // not necessary }
[2116]166
167        int SubtractPvs(const HashPvs<T, S> &pvs)
168        {
169                cerr << "not yet implemented" << endl;
170                return 0;
171        }
172        /** Compute continuous PVS difference
173        */
174        void ComputeContinuousPvsDifference(HashPvs<T, S> &pvs,
175                                                                                float &pvsReduction,
176                                                                                float &pvsEnlargement)
177        {
178                cerr << "not yet implemented" << endl;
179        }
[2530]180
181
[2102]182protected:
183
[2116]184        /// hash table of PVS entries
185        HASH_SET mEntries;
[2102]186
187        /// Number of samples used to create the PVS
188        int mSamples;
189};
190
191
[2116]192template <typename T, typename S>
[2161]193bool HashPvs<T, S>::Find(T sample, typename HASH_ITERATOR &it)
[2102]194{
[2162]195        it = mEntries.find(sample->GetId());
[2116]196
197        // already in map
198        return (it != mEntries.end());
[2102]199}
200
201
[2116]202template <typename T, typename S>
203int HashPvs<T, S>::GetSize() const
[2102]204{
[2116]205        return (int)mEntries.size();
[2102]206}
207
208
[2116]209template <typename T, typename S>
210bool HashPvs<T, S>::Empty() const
[2102]211{
[2116]212        return mEntries.empty();
[2102]213}
[2116]214
215
216template <typename T, typename S>
217float HashPvs<T, S>::AddSample(T sample, const float pdf)
218{
[2161]219        static HASH_ITERATOR it;
[2116]220
221        if (Find(sample, it))
222                return 0.0f;
[2102]223       
[2162]224        mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]225        return 1.0f;
226}
227       
[2102]228
[2116]229template <typename T, typename S>
230void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
[2102]231{
[2161]232        static HASH_ITERATOR it;
[2116]233
234        // not yet in map
235        if (!Find(sample, it))
236        {
[2162]237                mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]238        }
[2102]239}
240
241
[2116]242template <typename T, typename S>
243bool HashPvs<T, S>::AddSampleDirtyCheck(T sample,
244                                                                                const float pdf)
[2102]245{
[2164]246        static pair<HASH_ITERATOR, bool> result;
247        result = mEntries.insert(pair<int, T>(sample->GetId(), sample));
248        return result.second;
249
250        /*
[2162]251        static CONST_HASH_ITERATOR it;
[2116]252
[2162]253        it = mEntries.find(sample->GetId());//, sample);
254
[2116]255        // already in map
[2162]256        const bool found = (it != mEntries.end());
[2146]257
[2164]258        //return false;
[2146]259        // already in map
[2162]260        if (found)
261        //if (Find(pair<int, T>(sample->GetId(), sample), it))
[2116]262                return false;
[2162]263
264        mEntries.insert(pair<int, T>(sample->GetId(), sample));
[2116]265       
[2164]266        return true;*/
[2102]267}
268
269
[2116]270template <typename T, typename S>
271void HashPvs<T, S>::Sort()
[2102]272{
273}
274
275
[2116]276template <typename T, typename S>
277void HashPvs<T, S>::Clear(const bool trim = true)
[2102]278{
[2116]279        mEntries.clear();
[2102]280}
281
282
[2116]283template <typename T, typename S>
284bool HashPvs<T, S>::IsDirty() const
[2102]285{
286        return false;
287}
288
289
[2116]290template <typename T, typename S>
291bool HashPvs<T, S>::RequiresResort() const
[2102]292{
293        return false;
294}
295
296
[2116]297template <typename T, typename S>
298typename HashPvsIterator<T, S> HashPvs<T, S>::GetIterator() const
299{
300        HashPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
301
302        return pit;
[2102]303}
304
[2116]305
306template <typename T, typename S>
307float HashPvs<T, S>::GetEntrySize()
308{
309        return (float)(sizeof(T)) / float(1024 * 1024);
310}
311
312
313template <typename T, typename S>
314int HashPvs<T, S>::GetEntrySizeByte()
315{
316        return sizeof(T);
317}
318
319
320template <typename T, typename S>
321float HashPvs<T, S>::GetPvsHomogenity(HashPvs<T, S> &pvs)
322{
323        float pvsReduction, pvsEnlargement;
324
325        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
326
327        return pvsReduction + pvsEnlargement;
328}
329
330
331template <typename T, typename S>
332bool HashPvs<T, S>::GetSampleContribution(T sample,
333                                                                          const float pdf,
334                                                                          float &contribution)
335{
336        HASH_SET::iterator it;
337        const bool entryFound = Find(sample, it);
338
339        if (entryFound) 
340        {
341                contribution = 0.0f;
342                return false;
343        }
344        else
345        {
346                contribution = 1.0f;
347                return true;
348        }
349}
350
351
352template <typename T, typename S>
353void HashPvs<T, S>::Merge(HashPvs<T, S> &mergedPvs,
354                                                  const HashPvs<T, S> &a,
355                                                  const HashPvs<T, S> &b)
356{
[2161]357        CONST_HASH_ITERATOR ait, ait_end = a.mEntries.end();
[2116]358
359        for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
360        {
[2162]361                mergedPvs.AddSample((*ait).second, 1.0f);
[2116]362        }
363
[2161]364        CONST_HASH_ITERATOR bit, bit_end = b.mEntries.end();
[2116]365
366        for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
367        {
[2162]368                mergedPvs.AddSample((*bit).second, 1.0f);
[2116]369        }
370}
371
372}
373
[2102]374#endif
375
Note: See TracBrowser for help on using the repository browser.