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

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