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

Revision 2713, 12.2 KB checked in by bittner, 17 years ago (diff)

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