source: GTP/trunk/Lib/Vis/Preprocessing/src/PvsBase.h @ 2709

Revision 2709, 9.7 KB checked in by mattausch, 16 years ago (diff)

sheduling dynamic object only when necessary

RevLine 
[2116]1#ifndef __PVSBASE_H
2#define __PVSBASE_H
3
4#include "common.h"
5#include "Containers.h"
[2707]6#include <vector>
[2116]7
8namespace GtpVisibilityPreprocessor {
9
[2582]10/** Information stored with a PVS entry. Consists of the number
11        the object was seen from the view cell.
12*/
13struct PvsData
14{
15public:
16        PvsData() {}
17        PvsData(const float sumPdf):
18        mSumPdf(sumPdf) {}
19       
20        // $$JB in order to return meaningfull values
21        // it assumes that the sum pdf has been normalized somehow!!!
22        inline float GetVisibility() { return mSumPdf; }
[2116]23
[2582]24        /// sum of probability density of visible sample rays
25        float mSumPdf;
26};
27
28
29class MailablePvsData
30{
31public:
32        // sum of probability density of visible sample rays
33        float mSumPdf;
34        int mCounter;
35
36        MailablePvsData() {}
37        MailablePvsData(const float sumPdf):
38        mSumPdf(sumPdf) {}
39
40        // $$JB in order to return meaningfull values
41        // it assumes that the sum pdf has been normalized somehow!!!
42        inline float GetVisibility() { return mSumPdf; }
43
44
45        ///////////////
46        //  Mailing stuff
47
48        // last mail id -> warning not thread safe!
49        // both mailId and mailbox should be unique for each thread!!!
50        static int sMailId;
51        static int sReservedMailboxes;
52
53        static void NewMail(const int reserve = 1)
54        {
55                sMailId += sReservedMailboxes;
56                sReservedMailboxes = reserve;
57        }
58
59        void Mail() { mMailbox = sMailId; }
60        bool Mailed() const { return mMailbox == sMailId; }
61
62        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
63        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
64
65        int IncMail() { return ++ mMailbox - sMailId; }
66       
67        //////////////////////////////////////////
68
69protected:
70
71        int mMailbox;
72
73};
74
75
[2116]76/** Information stored with a PVS entry. Consists of the number
77        the object was seen from the view cell.
78*/
79template<typename T, typename S>
80struct PvsEntry
81{
82public:
83
[2117]84        PvsEntry(): mObject(NULL), mData(0) {}
85        PvsEntry(T sample): mObject(sample), mData(0) {}
[2116]86        PvsEntry(T sample, const S &data): mObject(sample), mData(data) {}
87
88        T mObject;
89        S mData;
90
[2582]91  //template<typename T, typename S>
92  friend int operator< (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b);
93  //template<typename T, typename S>
94  friend int operator== (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b);
[2116]95};
96
97
98template<typename T, typename S>
99int operator< (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
100{
101        return a.mObject < b.mObject;
102}
103
104template<typename T, typename S>
105int operator== (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
106{
107        return a.mObject == b.mObject;
108}
109
110
111template<typename T, typename S>
112struct LtSample
113{
114    bool operator()(const PvsEntry<T, S> &a, const PvsEntry<T, S> &b) const
115    {
116                return a.mObject < b.mObject;
117        }
118};
119
120template<typename T, typename S>
121int equalSample (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
122{
123        return a.mObject == b.mObject;
124}
125
[2582]126
127/** Iterator over the pvs.
[2116]128*/
[2582]129template<typename T, typename S>
130class PvsIterator
[2116]131{
132public:
[2582]133        PvsIterator<T, S>(){}
134        PvsIterator<T, S>(const typename vector<PvsEntry<T, S> >::const_iterator &itCurrent,
135                                          const typename vector<PvsEntry<T, S> >::const_iterator &itEnd):
136        mItCurrent(itCurrent), mItEnd(itEnd)
137        {
138        }
139 
140        inline bool HasMoreEntries() const { return (mItCurrent != mItEnd);     }
141
142        inline T Next(S &pdf) {
143                pdf = (*mItCurrent).mData;
144                return (*(mItCurrent ++)).mObject;
145        }
146
[2707]147 
[2582]148        inline T Next() { return (*(mItCurrent ++)).mObject; }
149
[2707]150  inline T Current(S &pdf) {
151        pdf = (*mItCurrent).mData;
152        return (*(mItCurrent)).mObject;
153  }
[2582]154
[2707]155  //private:
[2116]156       
[2707]157  typename vector<PvsEntry<T, S> >::const_iterator mItCurrent;
158  typename vector<PvsEntry<T, S> >::const_iterator mItEnd;
[2582]159};
[2116]160
[2582]161
162
163
164struct VerbosePvsStats
165{
166        VerbosePvsStats(): mDistanceWeightedTriangles(0), mDistanceWeightedPvs(0), mWeightedTriangles(0)
167        {}
168
169        float mDistanceWeightedTriangles;
170        float mDistanceWeightedPvs;
171        float mWeightedTriangles;
[2116]172};
173
174
[2582]175/** Template class representing the Potentially Visible Set (PVS)
176        mainly from a view cell, but also e.g., from objects.
177*/
178template<typename T, typename S>
179class VerbosePvs
[2116]180{
[2582]181  template<typename T1, typename S1> friend class PvsIterator;
182
[2116]183public:
184
[2582]185        VerbosePvs(): mSamples(0), mEntries(), mLastSorted(0), mQueriesSinceSort(0)
186        {}
[2116]187
[2582]188        /** creates pvs and initializes it with the given entries.
189                Assumes that entries are sorted.
190        */
191        VerbosePvs(const vector<PvsEntry<T, S> > &samples);
192        virtual ~VerbosePvs() {};
[2116]193
[2582]194        /** Compresses PVS lossless or lossy.
195        */
196        int Compress() { return 0; }
197       
198        inline int GetSize() const { return (int)mEntries.size(); }
199       
200        inline bool Empty() const { return mEntries.empty(); }
[2529]201
[2582]202        inline void Reserve(const int n) { mEntries.reserve(n); }
203        /** Normalize the visibility of entries in order to get
204                comparable results.
205        */
206        void NormalizeMaximum();
207        /** Merges pvs of a into this pvs.
208                Warning: very slow!
209        */
210        void MergeInPlace(const VerbosePvs<T, S> &a);
211        /** Difference of pvs to pvs b.
212        @returns number of different entries.
213        */
214        int Diff(const VerbosePvs<T, S> &b);
215        /** Finds sample in PVS.
216                @param checkDirty if dirty part of the pvs should be checked for entry
217                (warning: linear runtime in dirty part)
218                @returns iterator on the sample if found, else the place where
219                it would be added in the sorted vector.
220        */
221        bool Find(T sample,
222                          typename vector<PvsEntry<T, S> >::iterator &it,
223                          const bool checkDirty = true);
[2116]224
[2582]225        bool GetSampleContribution(T sample, const float pdf, float &contribution);
226        /** Adds sample to PVS.
227                @returns contribution of sample (0 or 1)
228        */
229        float AddSample(T sample, const float pdf);
230        /** Adds sample to PVS without checking for presence of the sample
231                warning: pvs remains unsorted!
232        */
233        void AddSampleDirty(T sample, const float pdf);
234        /** Adds sample dirty (on the end of the vector) but
235                first checks if sample is already in clean part of the pvs.
236        */
237        bool AddSampleDirtyCheck(T sample, const float pdf);
238        /** Sort pvs entries. This should always be called after a
239                sequence of AddSampleDirty calls
240        */
241        void Sort();
242        /** Sort pvs entries assume that the pvs contains unique entries
243        */
244        void SimpleSort();
245        /** Adds sample to PVS.
246                @returns PvsData
247        */
248        typename std::vector<PvsEntry<T, S> >::iterator
249                AddSample2(T sample, const float pdf);
250        /** Subtracts one pvs from another one.
251                WARNING: could contains bugs
252                @returns new pvs size
253        */
254        int SubtractPvs(const VerbosePvs<T, S> &pvs);
[2116]255
[2582]256        /** Returns PVS data, i.e., how often it was seen from the view cell,
257                and the object itsef.
258        */
259        void GetData(const int index, T &entry, S &data);
260
261        /** Collects the PVS entries and returns them in the vector.
262        */
263        void CollectEntries(std::vector<T> &entries);
264
265        /** Removes sample from PVS if reference count is zero.
266        @param visibleSamples number of references to be removed
267        */
[2707]268  bool RemoveSample(T sample, const float pdf);
[2582]269
[2707]270  void Remove(typename vector<PvsEntry<T, S> >::iterator &it);
271
[2582]272        /** Compute continuous PVS difference
273        */
274        void ComputeContinuousPvsDifference(VerbosePvs<T, S> &pvs,
275                                                                                float &pvsReduction,
276                                                                                float &pvsEnlargement);
277
278        /** Clears the pvs.
279        */
280        void Clear(const bool trim = true);
281        /** Trim the vector containing the pvs.
282        */
283        void Trim();
284
285        static int GetEntrySizeByte();
286        static float GetEntrySize();
287
288        /** Compute continuous PVS difference
289        */
290        float GetPvsHomogenity(VerbosePvs<T, S> &pvs);
291
292        static void Merge(VerbosePvs<T, S> &mergedPvs,
293                                          const VerbosePvs<T, S> &a,
294                                          const VerbosePvs<T, S> &b);
295
296        inline int GetSamples() const { return mSamples; }
297
298        /** If there is an unsorted part in the pvs.
299        */
300        bool IsDirty() const { return mLastSorted < mEntries.size(); }
301
302        /** If this pvs requires a resort to stay efficient.
303        */
304        bool RequiresResort() const
[2116]305        {
[2582]306                // the last part should not be more than log of the sorted part. this
307                // way we can achieve logarithmic behaviour for insertion and find
[2709]308                const int n = (int)mEntries.size();
[2582]309                const int dirtySize = n - mLastSorted;
310
311                const double LOG2E = 1.442695040f;
312
[2709]313                const float logN = log((float) Max(1, n))/ (float)LOG2E;
314                const float logS = log((float) Max(1, mLastSorted))/ (float)LOG2E;
315                const float logD = log((float) Max(1, dirtySize))/ (float)LOG2E;
[2582]316
317                if (8*(n + 2*dirtySize*logD) <
318                        mQueriesSinceSort*((mLastSorted*logS + dirtySize*dirtySize/2)/n - logN))
319                {
320                        // cout<<"Q="<<mQueriesSinceSort<<" N="<<n<<" D="<<dirtySize<<endl;
321                        return true;
322                }
323               
324                return false;
[2116]325        }
326
[2582]327        /** If this pvs requires a resort to stay efficient.
328        */
329        bool RequiresResortLog() const
330        {
331                // the last part should not be more than log of the sorted part. this
332                // way we can achieve logarithmic behaviour for insertion and find
333                const int dirtySize = (int)mEntries.size() - mLastSorted;
334                return dirtySize > 4 * (int)(log((double)mEntries.size()) / log(2.0));
335        }
[2116]336
[2582]337        inline int GetLastSorted() const { return mLastSorted; }
[2116]338
[2582]339  PvsIterator<T, S> GetIterator() const;
[2116]340
[2582]341        VerbosePvsStats mStats;
342
[2707]343  //protected:
[2116]344
[2582]345        /** Merge pvs 1 from begin iterator to end iterator with
346                pvs 2 from begin iterator to end iterator.
347        */
348        static void Merge(VerbosePvs<T, S> &mergedPvs,
349                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
350                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
351                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
352                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
353                                          const int aSamples,
354                                          const int bSamples);
[2116]355
[2582]356
357        //////////////////////////////
358
359        /// vector of PVS entries
360        vector<PvsEntry<T, S> > mEntries;
361
362        /// Number of samples used to create the PVS
363        int mSamples;
364
365        /// Last sorted entry in the pvs (important for find and merge)
366        int mLastSorted;
367
368        int mQueriesSinceSort;
[2116]369};
370
[2582]371
[2116]372}
373
[2582]374#endif
Note: See TracBrowser for help on using the repository browser.