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

Revision 2575, 7.6 KB checked in by bittner, 16 years ago (diff)

big merge: preparation for havran ray caster, check if everything works
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 T1, typename S1> 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        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          std::cerr << "bitvector: merge in place not implemented yet"
148                    << std::endl;
149        }
150
151        bool RequiresResortLog() const
152        {
153                return false;
154        }
155
156        void Reserve(const int n)
157        {
158                mEntries.reserve(n);
159        }
160
161        /** Sort pvs entries assume that the pvs contains unique entries
162        */
163        void SimpleSort()
164        {
165                // not necessary
166        }
167
168        int SubtractPvs(const BitVectorPvs<T, S> &pvs)
169        {
170          std::cerr << "not yet implemented" << std::endl;
171          return 0;
172        }
173
174        /** Compute continuous PVS difference
175        */
176        void ComputeContinuousPvsDifference(BitVectorPvs<T, S> &pvs,
177                                                                                float &pvsReduction,
178                                                                                float &pvsEnlargement)
179        {
180          std::cerr << "not yet implemented" << std::endl;
181        }
182
183
184        static void SetPvsSize(const int pvsSize) { sPvsSize = pvsSize; };
185       
186protected:
187
188        /// hash table of PVS entries
189        bit_vector mEntries;
190
191        /// Number of samples used to create the PVS
192        int mSamples;
193
194public:
195        static int sPvsSize;
196};
197
198
199template <typename T, typename S>
200BitVectorPvs<T, S>::BitVectorPvs()
201{
202        // initialize bit vector
203        mEntries.reserve(sPvsSize);
204        mEntries.resize(sPvsSize);
205
206        // set pvs entries to false
207        Clear();
208}
209
210
211template <typename T, typename S>
212bool BitVectorPvs<T, S>::Find(T sample)
213{
214        return mEntries[sample->GetId()];
215}
216
217
218template <typename T, typename S>
219int BitVectorPvs<T, S>::GetSize() const
220{
221        int size = 0;
222        bit_vector::const_iterator bit, bit_end = mEntries.end();
223
224        for (bit = mEntries.begin(); bit != bit_end; ++ bit)
225        {
226                if (*bit) ++ size;
227        }
228
229        return size;
230}
231
232
233template <typename T, typename S>
234bool BitVectorPvs<T, S>::Empty() const
235{
236        bit_vector::const_iterator bit, bit_end = mEntries.end();
237
238        for (bit = mEntries.begin(); bit != bit_end; ++ bit)
239        {
240                if (*bit) return false;
241        }
242
243        return true;
244}
245
246
247template <typename T, typename S>
248float BitVectorPvs<T, S>::AddSample(T sample, const float pdf)
249{
250        if (Find(sample))
251                return 0.0f;
252       
253        mEntries[sample->GetId()] = true;
254
255        return 1.0f;
256}
257       
258
259template <typename T, typename S>
260void BitVectorPvs<T, S>::AddSampleDirty(T sample, const float pdf)
261{
262        if (!Find(sample))
263        {
264                mEntries[sample->GetId()] = true;
265        }
266}
267
268
269template <typename T, typename S>
270bool BitVectorPvs<T, S>::AddSampleDirtyCheck(T sample, 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)
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>
312BitVectorPvsIterator<T, S> BitVectorPvs<T, S>::GetIterator() const
313{
314  return BitVectorPvsIterator<T, S>(mEntries.begin(), mEntries.end());
315}
316
317
318template <typename T, typename S>
319float BitVectorPvs<T, S>::GetEntrySize()
320{
321        return (float)(sizeof(bool)) / float(1024 * 1024);
322}
323
324
325template <typename T, typename S>
326int BitVectorPvs<T, S>::GetEntrySizeByte()
327{
328        return sizeof(bool);
329}
330
331
332template <typename T, typename S>
333float BitVectorPvs<T, S>::GetPvsHomogenity(BitVectorPvs<T, S> &pvs)
334{
335        float pvsReduction, pvsEnlargement;
336
337        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
338
339        return pvsReduction + pvsEnlargement;
340}
341
342
343template <typename T, typename S>
344bool BitVectorPvs<T, S>::GetSampleContribution(T sample,
345                                                                          const float pdf,
346                                                                          float &contribution)
347{
348        const bool entryFound = Find(sample);
349
350        if (entryFound) 
351        {
352                contribution = 0.0f;
353                return false;
354        }
355        else
356        {
357                contribution = 1.0f;
358                return true;
359        }
360}
361
362
363template <typename T, typename S>
364void BitVectorPvs<T, S>::Merge(BitVectorPvs<T, S> &mergedPvs,
365                                                           const BitVectorPvs<T, S> &a,
366                                                           const BitVectorPvs<T, S> &b)
367{
368        bit_vector::iterator bit, bit_end = mergedPvs.mEntries.end();
369        bit_vector::const_iterator bitA =  a.mEntries.begin(), bitB = b.mEntries.begin();
370
371        for (bit = mergedPvs.mEntries.begin(); bit != bit_end; ++ bit, ++ bitA, ++ bitB)
372        {
373        (*bit) = (*bitA) | (*bitB);
374        }
375}
376
377
378template<typename T, typename S>
379int BitVectorPvs<T, S>::sPvsSize = 0;
380
381template<typename T, typename S>
382vector<T> BitVectorPvsIterator<T, S>::sObjects;
383
384}
385
386#endif
387
Note: See TracBrowser for help on using the repository browser.