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

Revision 2206, 7.6 KB checked in by mattausch, 18 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,
270                                                                                const float pdf)
271{
272        if (Find(sample))
273                return false;
274       
275        mEntries[sample->GetId()] = true;
276        return true;
277}
278
279
280template <typename T, typename S>
281void BitVectorPvs<T, S>::Sort()
282{
283}
284
285
286template <typename T, typename S>
287void BitVectorPvs<T, S>::Clear(const bool trim = true)
288{
289        bit_vector::iterator bit, bit_end = mEntries.end();
290        for (bit = mEntries.begin(); bit != bit_end; ++ bit)
291        {
292                (*bit) = false;
293        }
294}
295
296
297template <typename T, typename S>
298bool BitVectorPvs<T, S>::IsDirty() const
299{
300        return false;
301}
302
303
304template <typename T, typename S>
305bool BitVectorPvs<T, S>::RequiresResort() const
306{
307        return false;
308}
309
310
311template <typename T, typename S>
312typename BitVectorPvsIterator<T, S> BitVectorPvs<T, S>::GetIterator() const
313{
314        BitVectorPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
315
316        return pit;
317}
318
319
320template <typename T, typename S>
321float BitVectorPvs<T, S>::GetEntrySize()
322{
323        return (float)(sizeof(bool)) / float(1024 * 1024);
324}
325
326
327template <typename T, typename S>
328int BitVectorPvs<T, S>::GetEntrySizeByte()
329{
330        return sizeof(bool);
331}
332
333
334template <typename T, typename S>
335float BitVectorPvs<T, S>::GetPvsHomogenity(BitVectorPvs<T, S> &pvs)
336{
337        float pvsReduction, pvsEnlargement;
338
339        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
340
341        return pvsReduction + pvsEnlargement;
342}
343
344
345template <typename T, typename S>
346bool BitVectorPvs<T, S>::GetSampleContribution(T sample,
347                                                                          const float pdf,
348                                                                          float &contribution)
349{
350        const bool entryFound = Find(sample);
351
352        if (entryFound) 
353        {
354                contribution = 0.0f;
355                return false;
356        }
357        else
358        {
359                contribution = 1.0f;
360                return true;
361        }
362}
363
364
365template <typename T, typename S>
366void BitVectorPvs<T, S>::Merge(BitVectorPvs<T, S> &mergedPvs,
367                                                           const BitVectorPvs<T, S> &a,
368                                                           const BitVectorPvs<T, S> &b)
369{
370        bit_vector::iterator bit, bit_end = mergedPvs.mEntries.end();
371        bit_vector::const_iterator bitA =  a.mEntries.begin(), bitB = b.mEntries.begin();
372
373        for (bit = mergedPvs.mEntries.begin(); bit != bit_end; ++ bit, ++ bitA, ++ bitB)
374        {
375        (*bit) = (*bitA) | (*bitB);
376        }
377}
378
379
380template<typename T, typename S>
381int BitVectorPvs<T, S>::sPvsSize = 0;
382
383template<typename T, typename S>
384vector<T> BitVectorPvsIterator<T, S>::sObjects;
385
386}
387
388#endif
389
Note: See TracBrowser for help on using the repository browser.