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

Revision 1715, 11.4 KB checked in by bittner, 18 years ago (diff)

new visibility filter support

Line 
1#ifndef __PVS_H
2#define __PVS_H
3
4#include <map>
5#include <vector>
6#include "common.h"
7
8namespace GtpVisibilityPreprocessor {
9
10class KdNode;
11class BspNode;
12class Ray;
13class Intersectable;
14class ViewCell;
15
16
17template<typename T>
18struct LtSample
19{
20    bool operator()(const T a, const T b) const
21    {
22                return a < b;
23        }
24};
25
26/** Information stored with a PVS entry. Consists of the number
27        the object was seen from the view cell.
28*/
29class PvsData {
30public:
31        /// sum of probability density of visible sample rays
32        float mSumPdf;
33
34        PvsData() {}
35        PvsData(const float sumPdf):
36        mSumPdf(sumPdf) {}
37
38        // $$JB in order to return meaningfull values
39        // it assumes that the sum pdf has been normalized somehow!!!
40        float GetVisibility()
41        {
42                return mSumPdf;
43        }
44};
45
46
47class MailablePvsData
48{
49        ////////////////////////////
50        //  Mailing stuff
51protected:
52        int mMailbox;
53
54public:
55        // last mail id -> warning not thread safe!
56        // both mailId and mailbox should be unique for each thread!!!
57        static int sMailId;
58        static int sReservedMailboxes;
59
60
61        static void NewMail(const int reserve = 1) {
62                sMailId += sReservedMailboxes;
63                sReservedMailboxes = reserve;
64        }
65
66        void Mail() { mMailbox = sMailId; }
67        bool Mailed() const { return mMailbox == sMailId; }
68
69        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
70        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
71
72        int IncMail() { return ++ mMailbox - sMailId; }
73        //////////////////////////////////////////
74
75        // sum of probability density of visible sample rays
76        float mSumPdf;
77        int mCounter;
78
79        MailablePvsData() {}
80        MailablePvsData(const float sumPdf):
81        mSumPdf(sumPdf) {}
82
83        // $$JB in order to return meaningfull values
84        // it assumes that the sum pdf has been normalized somehow!!!
85        float GetVisibility()
86        {
87                return mSumPdf;
88        }
89};
90
91
92/** Template class representing the Potentially Visible Set (PVS)
93        mainly from a view cell, but also e.g., from objects.
94*/
95template<typename T, typename S>
96class Pvs
97{
98public:
99  Pvs(): mSamples(0), mEntries() {}
100 
101
102        //virtual ~Pvs();
103
104        /** Compresses PVS lossless or lossy.
105        */
106        int Compress() {return 0;}
107        int GetSize() const {return (int)mEntries.size();}
108        bool Empty() const {return mEntries.empty();}
109
110        /** Normalize the visibility of entries in order to get comparable
111                results
112        */
113        void NormalizeMaximum();
114
115        /** Merges pvs of a into this pvs.
116        */
117        void Merge(const Pvs<T, S> &a);
118
119        /** Difference of pvs to pvs b.
120                @returns number of different entries.
121        */
122        int Diff(const Pvs<T, S> &b);
123
124        /** Finds sample in PVS.
125                @returns sample if found, NULL otherwise.
126        */
127        S *Find(T sample);
128
129        bool GetSampleContribution(T sample, const float pdf, float &contribution);
130
131        /** Adds sample to PVS.
132                @contribution contribution of sample (0 or 1)
133                @returns true if sample was not already in PVS.
134        */
135        bool AddSample(T sample, const float pdf, float &contribution);
136
137        /** Adds sample to PVS.
138                @returns contribution of sample (0 or 1)
139        */
140        float AddSample(T sample, const float pdf);
141
142        /** Adds sample to PVS.
143                @returns PvsData
144        */
145        S *AddSample2(T sample, const float pdf);
146
147        /** Adds one pvs to another one.
148                @returns new pvs size
149        */
150        int AddPvs(const Pvs<T, S> &pvs);
151
152        /** Subtracts one pvs from another one.
153                WARNING: could contains bugs
154                @returns new pvs size
155        */
156        int SubtractPvs(const Pvs<T, S> &pvs);
157        /** Returns PVS data, i.e., how often it was seen from the view cell,
158                and the object itsef.
159        */
160        void GetData(const int index, T &entry, S &data);
161
162        /** Collects the PVS entries and returns them in the vector.
163        */
164        void CollectEntries(std::vector<T> &entries);
165
166        /** Removes sample from PVS if reference count is zero.
167                @param visibleSamples number of references to be removed
168        */
169        bool RemoveSample(T sample, const float pdf);
170
171        /** Compute continuous PVS difference
172        */
173        void ComputeContinuousPvsDifference(Pvs<T, S> &pvs,
174                float &pvsReduction,
175                float &pvsEnlargement);
176
177
178        /** Clears the pvs.
179        */
180        void Clear();
181
182        static int GetEntrySizeByte();
183        static float GetEntrySize();
184
185        /** Compute continuous PVS difference */
186        float GetPvsHomogenity(Pvs<T, S> &pvs) {
187                float
188                        pvsReduction,
189                        pvsEnlargement;
190
191                ComputeContinuousPvsDifference(pvs,
192                        pvsReduction,
193                        pvsEnlargement);
194
195                return pvsReduction + pvsEnlargement;
196        }
197
198        int Size() { return mEntries.size(); }
199
200        /// Map of PVS entries
201        std::map<T, S, LtSample<T> > mEntries;
202
203  /// Number of samples used to create the PVS
204  int mSamples;
205};
206
207
208
209/**
210   Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
211   Provides separatelly PVS reduction from PVS enlargement.
212
213*/
214template <typename T, typename S>
215void
216Pvs<T, S>::ComputeContinuousPvsDifference(Pvs<T, S> &b,
217                                                                           float &pvsReduction,
218                                                                           float &pvsEnlargement)
219{
220        pvsReduction = 0.0f;
221        pvsEnlargement = 0.0f;
222  // Uses sum of log differences, which corresponds to entropy
223  std::map<T, S, LtSample<T> >::iterator it;
224 
225  for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
226  {
227        float bSumPdf = (*it).second.mSumPdf;
228        float aSumPdf = 0.0f;
229        S *data = Find((*it).first);           
230       
231        if (data)
232        {
233                aSumPdf = data->mSumPdf;
234                // mark this entry as processed to avoid double counting
235                data->mSumPdf = -aSumPdf;
236        }
237
238#if 0
239        float diff = bSumPdf - aSumPdf;
240       
241        if (diff > 0.0f) {
242          pvsEnlargement += diff;
243        } else {
244          pvsReduction += -diff;
245        }
246#else
247        if (!data)
248          pvsEnlargement += 1.0f;
249#endif
250  }
251 
252  for (it = mEntries.begin(); it != mEntries.end(); ++ it) {
253        float aSumPdf = (*it).second.mSumPdf;
254        float bSumPdf = 0.0f;
255        if (aSumPdf < 0.0f) {
256          // this entry was already accounted for!
257          // just revert it back
258          (*it).second.mSumPdf = -aSumPdf;
259        } else {
260          S *data = b.Find((*it).first);
261          if (data) {
262                bSumPdf = data->mSumPdf;
263          }
264#if 0
265          float diff = bSumPdf - aSumPdf;
266         
267          if (diff > 0.0f) {
268                pvsEnlargement += diff;
269          } else {
270                pvsReduction += -diff;
271          }
272
273#else
274          if (!data)
275                pvsReduction += 1.0f;
276#endif
277        }
278  }
279}
280
281template <typename T, typename S>
282int Pvs<T, S>::Diff(const Pvs<T, S> &b)
283{
284        int dif = 0;
285
286        std::map<T, S, LtSample<T> >::const_iterator it;
287
288        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
289        {
290                S data = Find((*it).first);             
291                if (!data) ++ dif;
292        }
293
294        return dif;
295}
296
297template <typename T, typename S> void Pvs<T, S>::Merge(const Pvs<T, S> &a)
298{
299        std::map<T, S, LtSample<T> >::const_iterator it;
300
301        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
302        {
303                AddSample((*it).first, (*it).second.mSumPdf);
304        }
305}
306
307
308template <typename T, typename S> void Pvs<T, S>::Clear()
309{
310        mEntries.clear();
311}
312
313
314template <typename T, typename S>
315S *Pvs<T, S>::Find(T sample)
316{
317  std::map<T, S, LtSample<T> >::iterator i = mEntries.find(sample);
318
319  if (i != mEntries.end())
320  {
321          return &(*i).second;
322  }
323  else
324  {
325          return NULL;
326  }
327}
328
329template <typename T, typename S>
330void Pvs<T, S>::GetData(const int index,
331                                         T &entry,
332                                         S &data)
333{
334  std::map<T, S, LtSample<T> >::iterator i = mEntries.begin();
335  for (int k = 0; k != index && i != mEntries.end(); i++, k++);
336
337  entry = (*i).first;
338  data = (*i).second;
339 
340}
341
342template <typename T, typename S>
343float
344Pvs<T, S>::AddSample(T sample, const float pdf)
345{
346  mSamples++;
347  S *data = Find(sample);
348 
349  if (data) 
350        {
351          data->mSumPdf += pdf;
352          return data->mSumPdf;
353        }
354  else
355        {
356          mEntries[sample] = S(pdf);
357          return pdf;
358        }
359}
360
361
362template <typename T, typename S>
363S * Pvs<T, S>::AddSample2(T sample, const float pdf)
364{
365  mSamples++;
366  S *data = Find(sample);
367 
368  if (data) 
369        {
370          data->mSumPdf += pdf;
371        }
372  else
373        {
374          mEntries[sample] = S(pdf);
375          data = Find(sample);
376        }
377 
378  return data;
379}
380
381template <typename T, typename S>
382bool Pvs<T, S>::AddSample(T sample,
383                                  const float pdf,
384                                  float &contribution)
385{
386  mSamples++;
387  S *data = Find(sample);
388 
389  if (data) 
390  {
391        data->mSumPdf += pdf;
392        contribution = pdf / data->mSumPdf;
393        return false;
394  }
395  else {
396        mEntries[sample] = S(pdf);
397        contribution = 1.0f;
398        return true;
399  }
400}
401
402template <typename T, typename S>
403bool
404Pvs<T, S>::GetSampleContribution(T sample,
405                                                                 const float pdf,
406                                                                 float &contribution)
407{
408  S *data = Find(sample);
409 
410  if (data)  {
411        contribution = pdf / (data->mSumPdf + pdf);
412        return false;
413  }
414  else {
415        contribution = 1.0f;
416        return true;
417  }
418}
419
420template <typename T, typename S>
421bool Pvs<T, S>::RemoveSample(T sample,
422                                                  const float pdf)
423{
424  mSamples--;
425 
426  std::map<T, S, LtSample<T> >::
427        iterator it = mEntries.find(sample);
428 
429  if (it == mEntries.end())
430        return false;
431 
432  S *data = &(*it).second;
433 
434  data->mSumPdf -= pdf;
435
436  if (data->mSumPdf <= 0.0f)
437  {
438          mEntries.erase(it);
439  }
440
441  return true;
442}
443
444template <typename T, typename S>
445int Pvs<T, S>::AddPvs(const Pvs<T, S> &pvs)
446{
447  mSamples += pvs.mSamples;
448  std::map<T, S, LtSample<T> >::
449        const_iterator it, it_end = pvs.mEntries.end();
450 
451  float contri;
452  // output PVS of view cell
453  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
454  {     
455          AddSample((*it).first, (*it).second.mSumPdf, contri);
456  }
457 
458  return GetSize();
459}
460 
461template <typename T, typename S>
462int Pvs<T, S>::SubtractPvs(const Pvs<T, S> &pvs)
463{
464  mSamples -= pvs.mSamples;
465  std::map<T, S, LtSample<T> >::
466        const_iterator it, it_end = pvs.mEntries.end();
467 
468  // output PVS of view cell
469  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
470        RemoveSample((*it).first, (*it).second.mSumPdf);
471 
472  return GetSize();
473}
474
475template <typename T, typename S>
476void Pvs<T, S>::CollectEntries(std::vector<T> &entries)
477{
478        std::map<T, S, LtSample<T> >::
479                const_iterator it, it_end = mEntries.end();
480
481        // output PVS of view cell
482        for (it = mEntries.begin(); it != it_end; ++ it)
483                entries.push_back((*it)->first);
484}
485
486template <typename T, typename S>
487void Pvs<T, S>::NormalizeMaximum()
488{
489  std::map<T, S, LtSample<T> >::
490        const_iterator it, it_end = mEntries.end();
491
492  float maxPdfSum = -1.0f;
493
494  // output PVS of view cell
495  for (it = mEntries.begin(); it != it_end; ++ it) {
496        float sum = (*it)->second.sumPdf;
497        if (sum > maxSum)
498          maxSum = sum;
499  }
500
501  maxSum = 1.0f / maxSum;
502
503  for (it = mEntries.begin(); it != it_end; ++ it) {
504        (*it)->second.sumPdf *= maxSum;
505  }
506 
507}
508
509
510template <typename T, typename S>
511float Pvs<T, S>::GetEntrySize()
512{
513        return (float)(sizeof(T) + sizeof(S)) / float(1024 * 1024);
514}
515
516
517template <typename T, typename S>
518int Pvs<T, S>::GetEntrySizeByte()
519{
520        return sizeof(T) + sizeof(S);
521}
522
523
524///////////////////////////////////////
525
526/** Class instantiating the Pvs template for kd tree nodes.
527*/
528class KdPvs: public Pvs<KdNode *, PvsData>
529{
530public:
531        int Compress();
532};
533
534
535class ObjectPvs: public Pvs<Intersectable *, PvsData>
536{
537public:
538        /** Counts object int the pvs. Different to method "GetSize", not
539                only the raw container size is returned,
540                but the individual contributions of the entries are summed up.
541        */
542        float EvalPvsCost() const;
543};
544
545
546////////////
547//-- typedefs
548
549typedef std::map<KdNode *, PvsData, LtSample<KdNode *> > KdPvsMap;
550typedef std::map<Intersectable *, PvsData, LtSample<Intersectable *> > ObjectPvsMap;
551typedef std::map<ViewCell *, MailablePvsData, LtSample<ViewCell *> > ViewCellPvsMap;
552
553
554typedef Pvs<ViewCell *, MailablePvsData> ViewCellPvs;
555
556}
557
558#endif
559
Note: See TracBrowser for help on using the repository browser.