source: GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h @ 2548

Revision 2548, 17.9 KB checked in by mattausch, 17 years ago (diff)
Line 
1#ifndef __VERBOSEPVS_H
2#define __VERBOSEPVS_H
3
4#include <vector>
5#include "common.h"
6#include <math.h>
7#include "PvsBase.h"
8
9
10
11namespace GtpVisibilityPreprocessor {
12
13
14/** Iterator over the pvs.
15*/
16template<typename T, typename S>
17class PvsIterator
18{
19public:
20        PvsIterator<T, S>(){}
21        PvsIterator<T, S>(const typename vector<PvsEntry<T, S> >::const_iterator &itCurrent,
22                                          const typename vector<PvsEntry<T, S> >::const_iterator &itEnd):
23        mItCurrent(itCurrent), mItEnd(itEnd)
24        {
25        }
26
27        inline bool HasMoreEntries() const { return (mItCurrent != mItEnd);     }
28
29        inline T Next(S &pdf) {
30                pdf = (*mItCurrent).mData;
31                return (*(mItCurrent ++)).mObject;
32        }
33
34        inline T Next() { return (*(mItCurrent ++)).mObject; }
35
36
37private:
38       
39        typename vector<PvsEntry<T, S> >::const_iterator mItCurrent;
40        typename vector<PvsEntry<T, S> >::const_iterator mItEnd;
41};
42
43
44/** Template class representing the Potentially Visible Set (PVS)
45        mainly from a view cell, but also e.g., from objects.
46*/
47template<typename T, typename S>
48class VerbosePvs
49{
50        template<typename T, typename S> friend class PvsIterator;
51
52public:
53
54        VerbosePvs(): mSamples(0), mEntries(), mLastSorted(0), mQueriesSinceSort(0)
55        {}
56
57        /** creates pvs and initializes it with the given entries.
58                Assumes that entries are sorted.
59        */
60        VerbosePvs(const vector<PvsEntry<T, S> > &samples);
61        virtual ~VerbosePvs() {};
62
63        /** Compresses PVS lossless or lossy.
64        */
65        int Compress() { return 0; }
66       
67        inline int GetSize() const { return (int)mEntries.size(); }
68       
69        inline bool Empty() const { return mEntries.empty(); }
70
71        inline void Reserve(const int n) { mEntries.reserve(n); }
72        /** Normalize the visibility of entries in order to get
73                comparable results.
74        */
75        void NormalizeMaximum();
76        /** Merges pvs of a into this pvs.
77                Warning: very slow!
78        */
79        void MergeInPlace(const VerbosePvs<T, S> &a);
80        /** Difference of pvs to pvs b.
81        @returns number of different entries.
82        */
83        int Diff(const VerbosePvs<T, S> &b);
84        /** Finds sample in PVS.
85                @param checkDirty if dirty part of the pvs should be checked for entry
86                (warning: linear runtime in dirty part)
87                @returns iterator on the sample if found, else the place where
88                it would be added in the sorted vector.
89        */
90        bool Find(T sample,
91                          typename vector<PvsEntry<T, S> >::iterator &it,
92                          const bool checkDirty = true);
93
94        bool GetSampleContribution(T sample, const float pdf, float &contribution);
95        /** Adds sample to PVS.
96                @returns contribution of sample (0 or 1)
97        */
98        float AddSample(T sample, const float pdf);
99        /** Adds sample to PVS without checking for presence of the sample
100                warning: pvs remains unsorted!
101        */
102        void AddSampleDirty(T sample, const float pdf);
103        /** Adds sample dirty (on the end of the vector) but
104                first checks if sample is already in clean part of the pvs.
105        */
106        bool AddSampleDirtyCheck(T sample, const float pdf);
107        /** Sort pvs entries. This should always be called after a
108                sequence of AddSampleDirty calls
109        */
110        void Sort();
111        /** Sort pvs entries assume that the pvs contains unique entries
112        */
113        void SimpleSort();
114        /** Adds sample to PVS.
115                @returns PvsData
116        */
117        typename std::vector<PvsEntry<T, S> >::iterator
118                AddSample2(T sample, const float pdf);
119        /** Subtracts one pvs from another one.
120                WARNING: could contains bugs
121                @returns new pvs size
122        */
123        int SubtractPvs(const VerbosePvs<T, S> &pvs);
124
125        /** Returns PVS data, i.e., how often it was seen from the view cell,
126                and the object itsef.
127        */
128        void GetData(const int index, T &entry, S &data);
129
130        /** Collects the PVS entries and returns them in the vector.
131        */
132        void CollectEntries(std::vector<T> &entries);
133
134        /** Removes sample from PVS if reference count is zero.
135        @param visibleSamples number of references to be removed
136        */
137        bool RemoveSample(T sample, const float pdf);
138
139        /** Compute continuous PVS difference
140        */
141        void ComputeContinuousPvsDifference(VerbosePvs<T, S> &pvs,
142                                                                                float &pvsReduction,
143                                                                                float &pvsEnlargement);
144
145        /** Clears the pvs.
146        */
147        void Clear(const bool trim = true);
148        /** Trim the vector containing the pvs.
149        */
150        void Trim();
151
152        static int GetEntrySizeByte();
153        static float GetEntrySize();
154
155        /** Compute continuous PVS difference
156        */
157        float GetPvsHomogenity(VerbosePvs<T, S> &pvs);
158
159        static void Merge(VerbosePvs<T, S> &mergedPvs,
160                                          const VerbosePvs<T, S> &a,
161                                          const VerbosePvs<T, S> &b);
162
163        inline int GetSamples() const { return mSamples; }
164
165        /** If there is an unsorted part in the pvs.
166        */
167        bool IsDirty() const { return mLastSorted < mEntries.size(); }
168
169        /** If this pvs requires a resort to stay efficient.
170        */
171        bool RequiresResort() const
172        {
173                // the last part should not be more than log of the sorted part. this
174                // way we can achieve logarithmic behaviour for insertion and find
175                const int n = mEntries.size();
176                const int dirtySize = n - mLastSorted;
177
178                const double LOG2E = 1.442695040f;
179
180                const float logN = log((float)max(1, n))/LOG2E;
181                const float logS = log((float)max(1, mLastSorted))/LOG2E;
182                const float logD = log((float)max(1, dirtySize))/LOG2E;
183
184                if (8*(n + 2*dirtySize*logD) <
185                        mQueriesSinceSort*((mLastSorted*logS + dirtySize*dirtySize/2)/n - logN))
186                {
187                        // cout<<"Q="<<mQueriesSinceSort<<" N="<<n<<" D="<<dirtySize<<endl;
188                        return true;
189                }
190               
191                return false;
192        }
193
194        /** If this pvs requires a resort to stay efficient.
195        */
196        bool RequiresResortLog() const
197        {
198                // the last part should not be more than log of the sorted part. this
199                // way we can achieve logarithmic behaviour for insertion and find
200                const int dirtySize = (int)mEntries.size() - mLastSorted;
201                return dirtySize > 4 * (int)(log((double)mEntries.size()) / log(2.0));
202        }
203
204        inline int GetLastSorted() const { return mLastSorted; }
205
206        typename PvsIterator<T, S> GetIterator() const;
207
208protected:
209
210        /** Merge pvs 1 from begin iterator to end iterator with
211                pvs 2 from begin iterator to end iterator.
212        */
213        static void Merge(VerbosePvs<T, S> &mergedPvs,
214                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
215                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
216                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
217                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
218                                          const int aSamples,
219                                          const int bSamples);
220
221
222        //////////////////////////////
223
224        /// vector of PVS entries
225        vector<PvsEntry<T, S> > mEntries;
226
227        /// Number of samples used to create the PVS
228        int mSamples;
229
230        /// Last sorted entry in the pvs (important for find and merge)
231        int mLastSorted;
232
233        int mQueriesSinceSort;
234};
235
236
237template <typename T, typename S>
238VerbosePvs<T, S>::VerbosePvs(const vector<PvsEntry<T, S> > &samples)
239{
240        mEntries.reserve(samples.size());
241        mEntries = samples;
242        mLastSorted = 0;
243        mSamples = samples.size();
244}
245
246
247template <typename T, typename S>
248void VerbosePvs<T, S>::Sort()
249{
250        vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
251        vector<PvsEntry<T, S> >::iterator it_end = mEntries.end();
252
253        // throw out double entries
254        std::vector<PvsEntry<T, S> >::iterator newEnd = unique(it, it_end);
255        sort(it, newEnd);
256       
257        // now merge sorted ranges
258        ObjectPvs newPvs;
259        Merge(newPvs,
260                  mEntries.begin(),
261                  it,
262                  it,
263                  newEnd,
264                  mSamples,
265                  0);
266       
267        mEntries = newPvs.mEntries;
268        mLastSorted = (int)mEntries.size();
269        mQueriesSinceSort = 0;
270}
271
272template <typename T, typename S>
273void VerbosePvs<T, S>::SimpleSort()
274{
275        //  sort(mEntries.begin(), mEntries.end());
276        vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
277
278        sort(it, mEntries.end());
279        inplace_merge(mEntries.begin(), it, mEntries.end());
280 
281        mLastSorted = (int)mEntries.size();
282        mQueriesSinceSort = 0;
283}
284
285
286/**
287   Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
288   Provides separatelly PVS reduction from PVS enlargement.
289
290*/
291template <typename T, typename S>
292void
293VerbosePvs<T, S>::ComputeContinuousPvsDifference(VerbosePvs<T, S> &b,
294                                                                                  float &pvsReduction,
295                                                                                  float &pvsEnlargement)
296{
297        pvsReduction = 0.0f;
298        pvsEnlargement = 0.0f;
299
300        // Uses sum of log differences, which corresponds to entropy
301        vector<PvsEntry<T, S> >::iterator it;
302
303        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
304        {
305                float bSumPdf = (*it).mData.mSumPdf;
306                float aSumPdf = 0.0f;
307
308                vector<PvsEntry<T, S> >::iterator oit;
309                const bool entryFound = Find((*it).mObject, oit);               
310
311                if (entryFound)
312                {
313                        aSumPdf = (*it).mData.mSumPdf;
314
315                        // mark this entry as processed to avoid double counting
316                        (*it).mData.mSumPdf = -aSumPdf;
317                }
318
319#if 0
320                const float diff = bSumPdf - aSumPdf;
321
322                if (diff > 0.0f)
323                {
324                        pvsEnlargement += diff;
325                }
326                else
327                {
328                        pvsReduction += -diff;
329                }
330#else
331                if (!entryFound)
332                {
333                        pvsEnlargement += 1.0f;
334                }
335#endif
336        }
337
338        for (it = mEntries.begin(); it != mEntries.end(); ++ it)
339        {
340                float aSumPdf = (*it).mData.mSumPdf;
341                float bSumPdf = 0.0f;
342                if (aSumPdf < 0.0f)
343                {
344                        // this entry was already accounted for!
345                        // just revert it back
346                        (*it).mData.mSumPdf = -aSumPdf;
347                }
348                else
349                {
350                        vector<PvsEntry<T, S> >::iterator oit;
351               
352                        const bool entryFound = b.Find((*it).mObject, oit);
353                                               
354                        if (entryFound) {
355                                bSumPdf = (*oit).mData.mSumPdf;
356                        }
357#if 0
358                        const float diff = bSumPdf - aSumPdf;
359
360                        if (diff > 0.0f) {
361                                pvsEnlargement += diff;
362                        } else {
363                                pvsReduction += -diff;
364                        }
365
366#else
367                        if (!entryFound)
368                                pvsReduction += 1.0f;
369#endif
370                }
371        }
372}
373
374
375template <typename T, typename S>
376int VerbosePvs<T, S>::Diff(const VerbosePvs<T, S> &b)
377{
378        int dif = 0;
379
380        std::vector<PvsEntry<T, S> >::const_iterator it;
381
382        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
383        {
384                vector<PvsEntry<T, S> >::iterator bit;
385                const bool entryFound = Find((*it).first, bit);
386
387                if (!entryFound) ++ dif;
388        }
389
390        return dif;
391}
392
393
394template <typename T, typename S>
395void VerbosePvs<T, S>::MergeInPlace(const VerbosePvs<T, S> &a)
396{
397        // early exit
398        if (a.Empty())
399        {
400                return;
401        }
402        else if (Empty())
403        {
404                mEntries.reserve(a.GetSize());
405                mEntries = a.mEntries;
406                mSamples = a.mSamples;
407                return;
408        }
409
410        ObjectPvs interPvs;
411       
412        Merge(interPvs, *this, a);
413       
414        mEntries.reserve(interPvs.GetSize());
415        mEntries = interPvs.mEntries;
416        mSamples = interPvs.mSamples;
417}
418
419
420template <typename T, typename S>
421void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs,
422                                                         const VerbosePvs<T, S> &a,
423                                                         const VerbosePvs<T, S> &b)
424{
425        std::vector<PvsEntry<T, S> >::const_iterator ait =
426                a.mEntries.begin(), ait_end = a.mEntries.end();
427        std::vector<PvsEntry<T, S> >::const_iterator bit =
428                b.mEntries.begin(), bit_end = b.mEntries.end();
429       
430        Merge(mergedPvs,
431                  ait, ait_end,
432                  bit, bit_end,
433                  a.mSamples,
434                  b.mSamples);
435}
436
437
438template <typename T, typename S>
439void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs,
440                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
441                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
442                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
443                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
444                                          const int aSamples,
445                                          const int bSamples)
446{
447        std::vector<PvsEntry<T, S> >::const_iterator ait = aBegin;
448        std::vector<PvsEntry<T, S> >::const_iterator bit = bBegin;
449       
450        for (; (ait != aEnd); ++ ait)
451        {
452                Intersectable *aObj = (*ait).mObject;
453                Intersectable *bObj = NULL;
454                //Intersectable *bObjOld = NULL;
455       
456                const PvsEntry<T, S> &aEntry = (*ait);
457
458                for (; (bit != bEnd) && ((*bit).mObject <= (*ait).mObject); ++ bit)
459                {
460                        bObj = (*bit).mObject;
461
462                        // object found => add up probabilities
463                        if (bObj == aEntry.mObject)
464                        {
465                                PvsData newData(aEntry.mData.mSumPdf + (*bit).mData.mSumPdf);
466                                PvsEntry<T, S> entry(bObj, newData);
467                                mergedPvs.mEntries.push_back(entry);
468                        }
469                        else
470                        {
471                                mergedPvs.mEntries.push_back(*bit);
472                        }
473                }
474
475                // only push back if objects different
476                // (equal case is handled by second loop)
477                if (aObj != bObj)
478                {
479                        mergedPvs.mEntries.push_back(*ait);
480                }
481        }
482
483        // add the rest
484        for (; (bit != bEnd); ++ bit)
485        {
486                mergedPvs.mEntries.push_back(*bit);
487        }
488
489        mergedPvs.mSamples = aSamples + bSamples;
490}
491
492
493template <typename T, typename S> void VerbosePvs<T, S>::Clear(const bool trim)
494{
495        mEntries.clear();
496        mSamples = 0;
497        mLastSorted = 0;
498
499        if (trim)
500        {
501                vector<PvsEntry<T,S> >().swap(mEntries);
502        }
503}
504
505
506template <typename T, typename S> void VerbosePvs<T, S>::Trim()
507{
508        vector<PvsEntry<T,S> >(mEntries).swap(mEntries);
509}
510
511
512template <typename T, typename S>
513bool VerbosePvs<T, S>::Find(T sample,
514                                         typename vector<PvsEntry<T, S> >::iterator &it,
515                                         const bool checkDirty)
516{
517        bool found = false;
518       
519        PvsEntry<T, S> dummy(sample, PvsData());
520
521        // only check clean part
522        vector<PvsEntry<T, S> >::iterator sorted_end = mEntries.begin() + mLastSorted;
523        mQueriesSinceSort++;
524
525        // binary search
526        it = lower_bound(mEntries.begin(), sorted_end, dummy);
527
528        if ((it != mEntries.end()) && ((*it).mObject == sample))
529                found = true;
530
531        // sample not found yet => search further in the unsorted part
532        if (!found && checkDirty)
533        {
534                vector<PvsEntry<T, S> >::iterator dit, dit_end = mEntries.end();
535
536        for (dit = sorted_end; (dit != dit_end) && ((*dit).mObject != sample); ++ dit);
537       
538                if (dit != dit_end)
539                {
540                        found = true;
541                        it = dit;
542                }
543        }
544
545        return found;
546}
547
548
549template <typename T, typename S>
550void VerbosePvs<T, S>::GetData(const int index, T &entry, S &data)
551{
552        std::vector<PvsEntry<T, S> >::iterator i = mEntries.begin();
553        for (int k = 0; k != index && i != mEntries.end(); ++ i, ++ k);
554
555        entry = (*i).first;
556        data = (*i).second;
557}
558
559
560template <typename T, typename S>
561float VerbosePvs<T, S>::AddSample(T sample, const float pdf)
562{
563        ++ mSamples;
564       
565        vector<PvsEntry<T, S> >::iterator it;
566        const bool entryFound = Find(sample, it);               
567
568        if (entryFound)
569        {       
570                S &data = (*it).mData;
571                data.mSumPdf += pdf;
572                return data.mSumPdf;
573        }
574        else
575        {
576                PvsEntry<T, S> entry(sample, pdf);
577                mEntries.insert(it, entry);
578                ++ mLastSorted;
579                return pdf;
580        }
581}
582
583
584template <typename T, typename S>
585void VerbosePvs<T, S>::AddSampleDirty(T sample, const float pdf)
586{
587        ++ mSamples;
588        mEntries.push_back(PvsEntry<T, S>(sample, pdf));
589}
590                                         
591
592template <typename T, typename S>
593typename vector< PvsEntry<T, S> >::iterator
594VerbosePvs<T, S>::AddSample2(T sample, const float pdf)
595{
596        ++ mSamples;
597       
598        vector<PvsEntry<T, S> >::iterator it;
599        const bool entryFound = Find(sample, it);
600
601        if (entryFound)
602        {
603                S &data = (*it).second;
604                data->mSumPdf += pdf;
605        }
606        else
607        {
608                PvsEntry<T, S> entry(sample, pdf);
609                mEntries.insert(it, entry);
610                ++ mLastSorted;
611        }
612
613        return it;
614}
615
616
617template <typename T, typename S>
618bool VerbosePvs<T, S>::AddSampleDirtyCheck(T sample, const float pdf)
619{
620        ++ mSamples;
621
622        vector<PvsEntry<T, S> >::iterator it;
623        const bool entryFound = Find(sample, it);
624
625        if (entryFound)
626        {
627                S &data = (*it).mData;
628         
629                data.mSumPdf += pdf;
630        return false;
631        }
632        else
633        {
634                AddSampleDirty(sample, pdf);
635                return true;
636        }
637}
638
639
640template <typename T, typename S>
641bool VerbosePvs<T, S>::GetSampleContribution(T sample,
642                                                                          const float pdf,
643                                                                          float &contribution)
644{
645        vector<PvsEntry<T, S> >::iterator it;
646        const bool entryFound = Find(sample, it);
647
648        if (entryFound) 
649        {
650                S &data = (*it).mData;
651                contribution = pdf / (data.mSumPdf + pdf);
652                return false;
653        }
654        else
655        {
656                contribution = 1.0f;
657                return true;
658        }
659}
660
661
662template <typename T, typename S>
663bool VerbosePvs<T, S>::RemoveSample(T sample, const float pdf)
664{
665        -- mSamples;
666       
667        vector<PvsEntry<T, S> >::iterator it;
668        const bool entryFound = Find(sample, it);
669
670        if (!entryFound)
671                return false;
672
673        S &data = (*it).mData;
674
675        data.mSumPdf -= pdf;
676
677        if (data.mSumPdf <= 0.0f)
678        {
679                mEntries.erase(it);
680                -- mLastSorted; // wrong if sample was in tail!!
681        }
682
683        return true;
684}
685
686
687template <typename T, typename S>
688int VerbosePvs<T, S>::SubtractPvs(const VerbosePvs<T, S> &pvs)
689{
690        const int samples = mSamples - pvs.mSamples;
691
692        std::vector<PvsEntry<T, S> >::
693                const_iterator it, it_end = pvs.mEntries.end();
694
695        // output PVS of view cell
696        for (it = pvs.mEntries.begin(); it != it_end; ++ it)
697                RemoveSample((*it).mObject, (*it).mData.mSumPdf);
698
699        mSamples = samples;
700
701        return GetSize();
702}
703
704
705template <typename T, typename S>
706void VerbosePvs<T, S>::CollectEntries(std::vector<T> &entries)
707{
708        std::vector<PvsEntry<T, S> >::
709                const_iterator it, it_end = mEntries.end();
710
711        // output PVS of view cell
712        for (it = mEntries.begin(); it != it_end; ++ it)
713                entries.push_back((*it)->first);
714}
715
716
717template <typename T, typename S>
718void VerbosePvs<T, S>::NormalizeMaximum()
719{
720        std::vector<PvsEntry<T, S> >::
721                const_iterator it, it_end = mEntries.end();
722
723        float maxPdfSum = -1.0f;
724
725        // output PVS of view cell
726        for (it = mEntries.begin(); it != it_end; ++ it) {
727                float sum = (*it)->second.sumPdf;
728                if (sum > maxSum)
729                        maxSum = sum;
730        }
731
732        maxSum = 1.0f / maxSum;
733
734        for (it = mEntries.begin(); it != it_end; ++ it) {
735                (*it)->second.sumPdf *= maxSum;
736        }
737}
738
739
740template <typename T, typename S>
741float VerbosePvs<T, S>::GetEntrySize()
742{
743        return (float)(sizeof(T) + sizeof(S)) / float(1024 * 1024);
744}
745
746
747template <typename T, typename S>
748int VerbosePvs<T, S>::GetEntrySizeByte()
749{
750        return sizeof(T) + sizeof(S);
751}
752
753
754template <typename T, typename S>
755float VerbosePvs<T, S>::GetPvsHomogenity(VerbosePvs<T, S> &pvs)
756{
757        float pvsReduction, pvsEnlargement;
758
759        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
760        return pvsReduction + pvsEnlargement;
761}
762
763
764template <typename T, typename S>
765typename PvsIterator<T, S> VerbosePvs<T, S>::GetIterator() const
766{
767        PvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
768        return pit;
769}
770
771}
772
773#endif
774
Note: See TracBrowser for help on using the repository browser.