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

Revision 2199, 17.7 KB checked in by mattausch, 18 years ago (diff)

using mutationsamples for evaluation

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