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

Revision 2636, 12.0 KB checked in by bittner, 17 years ago (diff)

moving objects partially functional

RevLine 
[2116]1#ifndef __VERBOSEPVS_H
2#define __VERBOSEPVS_H
[177]3
[469]4#include <vector>
[1189]5#include "common.h"
[2019]6#include <math.h>
[2582]7//#include "PvsBB.h"
[2116]8#include "PvsBase.h"
[2582]9#include "ObjectPvs.h"
[2116]10
11
[860]12namespace GtpVisibilityPreprocessor {
13
[2582]14inline int operator< (PvsEntry<Intersectable*, PvsData> const &a,
15                      PvsEntry<Intersectable*, PvsData> const &b)
[1742]16{
[2582]17  return a.mObject < b.mObject;
18}
[1742]19
[1740]20template <typename T, typename S>
[2570]21VerbosePvs<T, S>::VerbosePvs(const vector<PvsEntry<T, S> > &samples):
22mLastSorted(0)
[1740]23{
24        mEntries.reserve(samples.size());
25        mEntries = samples;
[1789]26        mSamples = samples.size();
[1740]27}
[677]28
[1789]29
[1757]30template <typename T, typename S>
[2116]31void VerbosePvs<T, S>::Sort()
[1757]32{
[2582]33        typename vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
34        typename vector<PvsEntry<T, S> >::iterator it_end = mEntries.end();
[1789]35
36        // throw out double entries
[2582]37        typename std::vector<PvsEntry<T, S> >::iterator newEnd = unique(it, it_end);
[1789]38        sort(it, newEnd);
[2019]39       
[1789]40        // now merge sorted ranges
41        ObjectPvs newPvs;
42        Merge(newPvs,
[2019]43                  mEntries.begin(),
44                  it,
45                  it,
46                  newEnd,
47                  mSamples,
48                  0);
[1789]49       
50        mEntries = newPvs.mEntries;
51        mLastSorted = (int)mEntries.size();
[2019]52        mQueriesSinceSort = 0;
[1757]53}
[1740]54
[1877]55template <typename T, typename S>
[2116]56void VerbosePvs<T, S>::SimpleSort()
[1877]57{
[2066]58        //  sort(mEntries.begin(), mEntries.end());
[2582]59        typename vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
[2066]60
61        sort(it, mEntries.end());
62        inplace_merge(mEntries.begin(), it, mEntries.end());
[2019]63 
[2066]64        mLastSorted = (int)mEntries.size();
65        mQueriesSinceSort = 0;
[1877]66}
[1789]67
[1877]68
[695]69/**
70   Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
71   Provides separatelly PVS reduction from PVS enlargement.
72
73*/
[1189]74template <typename T, typename S>
[677]75void
[2116]76VerbosePvs<T, S>::ComputeContinuousPvsDifference(VerbosePvs<T, S> &b,
[1740]77                                                                                  float &pvsReduction,
78                                                                                  float &pvsEnlargement)
[677]79{
[705]80        pvsReduction = 0.0f;
81        pvsEnlargement = 0.0f;
[1740]82
[1738]83        // Uses sum of log differences, which corresponds to entropy
[2582]84        typename vector<PvsEntry<T, S> >::iterator it;
[1738]85
86        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
[1189]87        {
[1740]88                float bSumPdf = (*it).mData.mSumPdf;
[1738]89                float aSumPdf = 0.0f;
[713]90
[2582]91                typename vector<PvsEntry<T, S> >::iterator oit;
[1790]92                const bool entryFound = Find((*it).mObject, oit);               
[1740]93
94                if (entryFound)
[1738]95                {
[1740]96                        aSumPdf = (*it).mData.mSumPdf;
97
[1738]98                        // mark this entry as processed to avoid double counting
[1740]99                        (*it).mData.mSumPdf = -aSumPdf;
[1738]100                }
101
[713]102#if 0
[1740]103                const float diff = bSumPdf - aSumPdf;
[1738]104
[2100]105                if (diff > 0.0f)
106                {
[1738]107                        pvsEnlargement += diff;
[2100]108                }
109                else
110                {
[1738]111                        pvsReduction += -diff;
112                }
[713]113#else
[1740]114                if (!entryFound)
[2100]115                {
[1738]116                        pvsEnlargement += 1.0f;
[2100]117                }
[713]118#endif
[1738]119        }
120
[1740]121        for (it = mEntries.begin(); it != mEntries.end(); ++ it)
122        {
123                float aSumPdf = (*it).mData.mSumPdf;
[1738]124                float bSumPdf = 0.0f;
[2100]125                if (aSumPdf < 0.0f)
126                {
[1738]127                        // this entry was already accounted for!
128                        // just revert it back
[1740]129                        (*it).mData.mSumPdf = -aSumPdf;
[2100]130                }
131                else
132                {
[2582]133                        typename vector<PvsEntry<T, S> >::iterator oit;
[1790]134               
135                        const bool entryFound = b.Find((*it).mObject, oit);
136                                               
[1740]137                        if (entryFound) {
138                                bSumPdf = (*oit).mData.mSumPdf;
[1738]139                        }
[713]140#if 0
[1740]141                        const float diff = bSumPdf - aSumPdf;
[713]142
[1738]143                        if (diff > 0.0f) {
144                                pvsEnlargement += diff;
145                        } else {
146                                pvsReduction += -diff;
147                        }
148
[713]149#else
[1740]150                        if (!entryFound)
[1738]151                                pvsReduction += 1.0f;
[713]152#endif
[1738]153                }
[695]154        }
[677]155}
156
[1738]157
[1189]158template <typename T, typename S>
[2116]159int VerbosePvs<T, S>::Diff(const VerbosePvs<T, S> &b)
[362]160{
161        int dif = 0;
162
[2582]163        typename std::vector<PvsEntry<T, S> >::const_iterator it;
[362]164
165        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
166        {
[2582]167                typename vector<PvsEntry<T, S> >::iterator bit;
[1790]168                const bool entryFound = Find((*it).first, bit);
169
170                if (!entryFound) ++ dif;
[362]171        }
172
173        return dif;
174}
175
[1740]176
177template <typename T, typename S>
[2116]178void VerbosePvs<T, S>::MergeInPlace(const VerbosePvs<T, S> &a)
[341]179{
[1786]180        // early exit
181        if (a.Empty())
182        {
183                return;
184        }
185        else if (Empty())
186        {
187                mEntries.reserve(a.GetSize());
188                mEntries = a.mEntries;
189                mSamples = a.mSamples;
190                return;
191        }
192
[1740]193        ObjectPvs interPvs;
194       
195        Merge(interPvs, *this, a);
196       
197        mEntries.reserve(interPvs.GetSize());
198        mEntries = interPvs.mEntries;
[1751]199        mSamples = interPvs.mSamples;
[1740]200}
201
202
203template <typename T, typename S>
[2116]204void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs,
205                                                         const VerbosePvs<T, S> &a,
206                                                         const VerbosePvs<T, S> &b)
[1740]207{
[2582]208        typename std::vector<PvsEntry<T, S> >::const_iterator ait =
[2116]209                a.mEntries.begin(), ait_end = a.mEntries.end();
[2582]210        typename std::vector<PvsEntry<T, S> >::const_iterator bit =
[2116]211                b.mEntries.begin(), bit_end = b.mEntries.end();
[1741]212       
[1789]213        Merge(mergedPvs,
214                  ait, ait_end,
215                  bit, bit_end,
216                  a.mSamples,
217                  b.mSamples);
218}
219
220
221template <typename T, typename S>
[2116]222void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs,
[1789]223                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
224                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
225                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
226                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
227                                          const int aSamples,
228                                          const int bSamples)
229{
[2582]230        typename std::vector<PvsEntry<T, S> >::const_iterator ait = aBegin;
231        typename std::vector<PvsEntry<T, S> >::const_iterator bit = bBegin;
[1789]232       
233        for (; (ait != aEnd); ++ ait)
[1741]234        {
235                Intersectable *aObj = (*ait).mObject;
236                Intersectable *bObj = NULL;
[1789]237                //Intersectable *bObjOld = NULL;
238       
239                const PvsEntry<T, S> &aEntry = (*ait);
[1740]240
[1789]241                for (; (bit != bEnd) && ((*bit).mObject <= (*ait).mObject); ++ bit)
[1741]242                {
243                        bObj = (*bit).mObject;
244
245                        // object found => add up probabilities
[1742]246                        if (bObj == aEntry.mObject)
[1741]247                        {
248                                PvsData newData(aEntry.mData.mSumPdf + (*bit).mData.mSumPdf);
249                                PvsEntry<T, S> entry(bObj, newData);
250                                mergedPvs.mEntries.push_back(entry);
251                        }
252                        else
253                        {
254                                mergedPvs.mEntries.push_back(*bit);
255                        }
256                }
257
258                // only push back if objects different
259                // (equal case is handled by second loop)
260                if (aObj != bObj)
261                {
262                        mergedPvs.mEntries.push_back(*ait);
263                }
264        }
265
266        // add the rest
[1789]267        for (; (bit != bEnd); ++ bit)
[1740]268        {
[1741]269                mergedPvs.mEntries.push_back(*bit);
270        }
[1789]271
272        mergedPvs.mSamples = aSamples + bSamples;
[1740]273}
274
275
[2199]276template <typename T, typename S> void VerbosePvs<T, S>::Clear(const bool trim)
[752]277{
278        mEntries.clear();
[1750]279        mSamples = 0;
[1789]280        mLastSorted = 0;
[1786]281
282        if (trim)
283        {
284                vector<PvsEntry<T,S> >().swap(mEntries);
285        }
[752]286}
287
288
[2116]289template <typename T, typename S> void VerbosePvs<T, S>::Trim()
[1750]290{
[1786]291        vector<PvsEntry<T,S> >(mEntries).swap(mEntries);
[1750]292}
293
294
[1189]295template <typename T, typename S>
[2116]296bool VerbosePvs<T, S>::Find(T sample,
[2582]297                            typename vector<PvsEntry<T, S> >::iterator &it,
298                            const bool checkDirty)
[310]299{
[2066]300        bool found = false;
[2077]301       
[2066]302        PvsEntry<T, S> dummy(sample, PvsData());
303
304        // only check clean part
[2582]305        typename vector<PvsEntry<T, S> >::iterator sorted_end = mEntries.begin() + mLastSorted;
[2077]306        mQueriesSinceSort++;
[2066]307
308        // binary search
309        it = lower_bound(mEntries.begin(), sorted_end, dummy);
310
311        if ((it != mEntries.end()) && ((*it).mObject == sample))
312                found = true;
313
314        // sample not found yet => search further in the unsorted part
315        if (!found && checkDirty)
316        {
[2582]317            typename vector<PvsEntry<T, S> >::iterator dit, dit_end = mEntries.end();
[2066]318
319        for (dit = sorted_end; (dit != dit_end) && ((*dit).mObject != sample); ++ dit);
[1790]320       
[2066]321                if (dit != dit_end)
322                {
323                        found = true;
324                        it = dit;
325                }
326        }
327
328        return found;
[310]329}
330
[1740]331
[1189]332template <typename T, typename S>
[2116]333void VerbosePvs<T, S>::GetData(const int index, T &entry, S &data)
[310]334{
[2582]335        typename std::vector<PvsEntry<T, S> >::iterator i = mEntries.begin();
[1738]336        for (int k = 0; k != index && i != mEntries.end(); ++ i, ++ k);
[310]337
[1738]338        entry = (*i).first;
339        data = (*i).second;
[310]340}
341
[1738]342
[1189]343template <typename T, typename S>
[2116]344float VerbosePvs<T, S>::AddSample(T sample, const float pdf)
[2071]345{
[1738]346        ++ mSamples;
[1790]347       
[2582]348        typename vector<PvsEntry<T, S> >::iterator it;
[1790]349        const bool entryFound = Find(sample, it);               
[1738]350
[1790]351        if (entryFound)
352        {       
[1740]353                S &data = (*it).mData;
354                data.mSumPdf += pdf;
355                return data.mSumPdf;
[1189]356        }
[1738]357        else
[2066]358        {
[1740]359                PvsEntry<T, S> entry(sample, pdf);
360                mEntries.insert(it, entry);
[1789]361                ++ mLastSorted;
[1738]362                return pdf;
[2066]363        }
[466]364}
[177]365
[1189]366
367template <typename T, typename S>
[2116]368void VerbosePvs<T, S>::AddSampleDirty(T sample, const float pdf)
[1757]369{
[1789]370        ++ mSamples;
371        mEntries.push_back(PvsEntry<T, S>(sample, pdf));
[1757]372}
373                                         
374
375template <typename T, typename S>
[2548]376typename vector< PvsEntry<T, S> >::iterator
377VerbosePvs<T, S>::AddSample2(T sample, const float pdf)
[1184]378{
[1740]379        ++ mSamples;
[1789]380       
[2582]381        typename vector<PvsEntry<T, S> >::iterator it;
[2066]382        const bool entryFound = Find(sample, it);
[1740]383
[1790]384        if (entryFound)
[1189]385        {
[1740]386                S &data = (*it).second;
387                data->mSumPdf += pdf;
[1189]388        }
[1740]389        else
[1189]390        {
[1740]391                PvsEntry<T, S> entry(sample, pdf);
392                mEntries.insert(it, entry);
[1789]393                ++ mLastSorted;
[1189]394        }
[1740]395
396        return it;
[1184]397}
398
[1740]399
[1789]400template <typename T, typename S>
[2530]401bool VerbosePvs<T, S>::AddSampleDirtyCheck(T sample, const float pdf)
[1789]402{
403        ++ mSamples;
404
[2582]405        typename vector<PvsEntry<T, S> >::iterator it;
[2066]406        const bool entryFound = Find(sample, it);
[1789]407
[2066]408        if (entryFound)
409        {
410                S &data = (*it).mData;
[1877]411         
[2066]412                data.mSumPdf += pdf;
413        return false;
[1789]414        }
[2066]415        else
416        {
417                AddSampleDirty(sample, pdf);
418                return true;
[1789]419        }
[311]420}
[308]421
[492]422
[1189]423template <typename T, typename S>
[2116]424bool VerbosePvs<T, S>::GetSampleContribution(T sample,
[1740]425                                                                          const float pdf,
426                                                                          float &contribution)
[485]427{
[2582]428        typename vector<PvsEntry<T, S> >::iterator it;
[1790]429        const bool entryFound = Find(sample, it);
[1189]430
[1790]431        if (entryFound) 
[1740]432        {
433                S &data = (*it).mData;
434                contribution = pdf / (data.mSumPdf + pdf);
435                return false;
436        }
437        else
438        {
439                contribution = 1.0f;
440                return true;
441        }
[485]442}
443
[1740]444
[1189]445template <typename T, typename S>
[2116]446bool VerbosePvs<T, S>::RemoveSample(T sample, const float pdf)
[485]447{
[1789]448       
[2582]449        typename vector<PvsEntry<T, S> >::iterator it;
[1790]450        const bool entryFound = Find(sample, it);
[1737]451
[1790]452        if (!entryFound)
[1740]453                return false;
454
[2636]455        // $$JB decrement only if the sample found
456        -- mSamples;
457
[1740]458        S &data = (*it).mData;
459
460        data.mSumPdf -= pdf;
461
462        if (data.mSumPdf <= 0.0f)
463        {
464                mEntries.erase(it);
[1789]465                -- mLastSorted; // wrong if sample was in tail!!
[1740]466        }
467
468        return true;
[485]469}
[1740]470
471
[1189]472template <typename T, typename S>
[2116]473int VerbosePvs<T, S>::SubtractPvs(const VerbosePvs<T, S> &pvs)
[485]474{
[1738]475        const int samples = mSamples - pvs.mSamples;
[1740]476
[2582]477        typename std::vector<PvsEntry<T, S> >::
478          const_iterator it, it_end = pvs.mEntries.end();
[1737]479
[1738]480        // output PVS of view cell
481        for (it = pvs.mEntries.begin(); it != it_end; ++ it)
[1740]482                RemoveSample((*it).mObject, (*it).mData.mSumPdf);
[1738]483
484        mSamples = samples;
[1740]485
[1738]486        return GetSize();
[485]487}
488
[1740]489
[1189]490template <typename T, typename S>
[2116]491void VerbosePvs<T, S>::CollectEntries(std::vector<T> &entries)
[469]492{
[2582]493        typename std::vector<PvsEntry<T, S> >::
494           const_iterator it, it_end = mEntries.end();
[469]495
496        // output PVS of view cell
497        for (it = mEntries.begin(); it != it_end; ++ it)
498                entries.push_back((*it)->first);
499}
500
[1740]501
[1189]502template <typename T, typename S>
[2116]503void VerbosePvs<T, S>::NormalizeMaximum()
[556]504{
[2582]505        typename std::vector<PvsEntry<T, S> >::
[1740]506                const_iterator it, it_end = mEntries.end();
[556]507
[1740]508        float maxPdfSum = -1.0f;
[556]509
[1740]510        // output PVS of view cell
511        for (it = mEntries.begin(); it != it_end; ++ it) {
512                float sum = (*it)->second.sumPdf;
[2582]513                if (sum > maxPdfSum)
514                        maxPdfSum = sum;
[1740]515        }
[556]516
[2582]517        maxPdfSum = 1.0f / maxPdfSum;
[556]518
[1740]519        for (it = mEntries.begin(); it != it_end; ++ it) {
[2582]520                (*it)->second.sumPdf *= maxPdfSum;
[1740]521        }
[556]522}
523
524
[1667]525template <typename T, typename S>
[2116]526float VerbosePvs<T, S>::GetEntrySize()
[1667]527{
[1673]528        return (float)(sizeof(T) + sizeof(S)) / float(1024 * 1024);
[1667]529}
530
531
532template <typename T, typename S>
[2116]533int VerbosePvs<T, S>::GetEntrySizeByte()
[1667]534{
535        return sizeof(T) + sizeof(S);
536}
537
538
[1740]539template <typename T, typename S>
[2116]540float VerbosePvs<T, S>::GetPvsHomogenity(VerbosePvs<T, S> &pvs)
[1740]541{
542        float pvsReduction, pvsEnlargement;
543
544        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
545        return pvsReduction + pvsEnlargement;
546}
547
548
[1742]549template <typename T, typename S>
[2582]550PvsIterator<T, S> VerbosePvs<T, S>::GetIterator() const
[1742]551{
552        PvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
553        return pit;
554}
555
[860]556}
[469]557
[177]558#endif
559
Note: See TracBrowser for help on using the repository browser.