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

RevLine 
[177]1#ifndef __PVS_H
2#define __PVS_H
3
4#include <map>
[469]5#include <vector>
[1189]6#include "common.h"
[177]7
[860]8namespace GtpVisibilityPreprocessor {
9
[177]10class KdNode;
[240]11class BspNode;
[191]12class Ray;
[308]13class Intersectable;
[1077]14class ViewCell;
[177]15
[1077]16
[310]17template<typename T>
[1189]18struct LtSample
19{
[311]20    bool operator()(const T a, const T b) const
[310]21    {
22                return a < b;
23        }
24};
25
[469]26/** Information stored with a PVS entry. Consists of the number
27        the object was seen from the view cell.
28*/
[1189]29class PvsData {
30public:
[1706]31        /// sum of probability density of visible sample rays
32        float mSumPdf;
[310]33
[1706]34        PvsData() {}
35        PvsData(const float sumPdf):
[1189]36        mSumPdf(sumPdf) {}
37
[1706]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        }
[1189]44};
45
46
47class MailablePvsData
48{
[1706]49        ////////////////////////////
50        //  Mailing stuff
[1184]51protected:
52        int mMailbox;
53
54public:
[1706]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
[1184]61        static void NewMail(const int reserve = 1) {
62                sMailId += sReservedMailboxes;
63                sReservedMailboxes = reserve;
64        }
[1706]65
[1184]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; }
[1706]73        //////////////////////////////////////////
[1184]74
[1706]75        // sum of probability density of visible sample rays
76        float mSumPdf;
77        int mCounter;
[1184]78
[1706]79        MailablePvsData() {}
80        MailablePvsData(const float sumPdf):
[556]81        mSumPdf(sumPdf) {}
82
[1706]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        }
[310]89};
90
[1184]91
[469]92/** Template class representing the Potentially Visible Set (PVS)
93        mainly from a view cell, but also e.g., from objects.
94*/
[1189]95template<typename T, typename S>
[311]96class Pvs
[310]97{
98public:
[1715]99  Pvs(): mSamples(0), mEntries() {}
100 
[556]101
[1706]102        //virtual ~Pvs();
[492]103
[1706]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();}
[469]109
[1706]110        /** Normalize the visibility of entries in order to get comparable
111                results
112        */
113        void NormalizeMaximum();
[1184]114
[1706]115        /** Merges pvs of a into this pvs.
116        */
117        void Merge(const Pvs<T, S> &a);
[752]118
[1706]119        /** Difference of pvs to pvs b.
120                @returns number of different entries.
121        */
122        int Diff(const Pvs<T, S> &b);
[469]123
[1706]124        /** Finds sample in PVS.
125                @returns sample if found, NULL otherwise.
126        */
127        S *Find(T sample);
[469]128
[1706]129        bool GetSampleContribution(T sample, const float pdf, float &contribution);
[485]130
[1706]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);
[677]136
[1706]137        /** Adds sample to PVS.
138                @returns contribution of sample (0 or 1)
139        */
140        float AddSample(T sample, const float pdf);
[752]141
[1706]142        /** Adds sample to PVS.
143                @returns PvsData
144        */
145        S *AddSample2(T sample, const float pdf);
[1667]146
[1706]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;
[1715]202
203  /// Number of samples used to create the PVS
204  int mSamples;
[310]205};
206
[581]207
[677]208
[695]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*/
[1189]214template <typename T, typename S>
[677]215void
[1189]216Pvs<T, S>::ComputeContinuousPvsDifference(Pvs<T, S> &b,
[677]217                                                                           float &pvsReduction,
218                                                                           float &pvsEnlargement)
219{
[705]220        pvsReduction = 0.0f;
221        pvsEnlargement = 0.0f;
[695]222  // Uses sum of log differences, which corresponds to entropy
[1189]223  std::map<T, S, LtSample<T> >::iterator it;
[677]224 
[1189]225  for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
226  {
[695]227        float bSumPdf = (*it).second.mSumPdf;
228        float aSumPdf = 0.0f;
[1189]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;
[695]236        }
[713]237
238#if 0
[695]239        float diff = bSumPdf - aSumPdf;
240       
241        if (diff > 0.0f) {
242          pvsEnlargement += diff;
243        } else {
244          pvsReduction += -diff;
245        }
[713]246#else
247        if (!data)
248          pvsEnlargement += 1.0f;
249#endif
[695]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 {
[1189]260          S *data = b.Find((*it).first);
[695]261          if (data) {
[704]262                bSumPdf = data->mSumPdf;
[695]263          }
[713]264#if 0
[695]265          float diff = bSumPdf - aSumPdf;
266         
267          if (diff > 0.0f) {
268                pvsEnlargement += diff;
269          } else {
270                pvsReduction += -diff;
271          }
[713]272
273#else
274          if (!data)
275                pvsReduction += 1.0f;
276#endif
[695]277        }
278  }
[677]279}
280
[1189]281template <typename T, typename S>
282int Pvs<T, S>::Diff(const Pvs<T, S> &b)
[362]283{
284        int dif = 0;
285
[1189]286        std::map<T, S, LtSample<T> >::const_iterator it;
[362]287
288        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
289        {
[1189]290                S data = Find((*it).first);             
[362]291                if (!data) ++ dif;
292        }
293
294        return dif;
295}
296
[1189]297template <typename T, typename S> void Pvs<T, S>::Merge(const Pvs<T, S> &a)
[341]298{
[1189]299        std::map<T, S, LtSample<T> >::const_iterator it;
[362]300
[610]301        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
[362]302        {
[1189]303                AddSample((*it).first, (*it).second.mSumPdf);
[362]304        }
[341]305}
306
[1189]307
308template <typename T, typename S> void Pvs<T, S>::Clear()
[752]309{
310        mEntries.clear();
311}
312
313
[1189]314template <typename T, typename S>
315S *Pvs<T, S>::Find(T sample)
[310]316{
[1189]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  }
[310]327}
328
[1189]329template <typename T, typename S>
330void Pvs<T, S>::GetData(const int index,
[485]331                                         T &entry,
[1189]332                                         S &data)
[310]333{
[1189]334  std::map<T, S, LtSample<T> >::iterator i = mEntries.begin();
[310]335  for (int k = 0; k != index && i != mEntries.end(); i++, k++);
336
337  entry = (*i).first;
[311]338  data = (*i).second;
[1189]339 
[310]340}
341
[1189]342template <typename T, typename S>
[556]343float
[1189]344Pvs<T, S>::AddSample(T sample, const float pdf)
[177]345{
[1715]346  mSamples++;
347  S *data = Find(sample);
[492]348 
[1715]349  if (data) 
[1189]350        {
[1715]351          data->mSumPdf += pdf;
352          return data->mSumPdf;
[1189]353        }
[1715]354  else
[1189]355        {
[1715]356          mEntries[sample] = S(pdf);
357          return pdf;
[1189]358        }
[466]359}
[177]360
[1189]361
362template <typename T, typename S>
363S * Pvs<T, S>::AddSample2(T sample, const float pdf)
[1184]364{
[1715]365  mSamples++;
366  S *data = Find(sample);
[1184]367 
[1715]368  if (data) 
[1189]369        {
[1715]370          data->mSumPdf += pdf;
[1189]371        }
[1715]372  else
[1189]373        {
[1715]374          mEntries[sample] = S(pdf);
375          data = Find(sample);
[1189]376        }
[1715]377 
378  return data;
[1184]379}
380
[1189]381template <typename T, typename S>
382bool Pvs<T, S>::AddSample(T sample,
[556]383                                  const float pdf,
384                                  float &contribution)
[466]385{
[1715]386  mSamples++;
[1189]387  S *data = Find(sample);
[466]388 
[1189]389  if (data) 
390  {
[1112]391        data->mSumPdf += pdf;
[1189]392        contribution = pdf / data->mSumPdf;
[466]393        return false;
394  }
395  else {
[1189]396        mEntries[sample] = S(pdf);
[466]397        contribution = 1.0f;
398        return true;
399  }
[311]400}
[308]401
[1189]402template <typename T, typename S>
[492]403bool
[1189]404Pvs<T, S>::GetSampleContribution(T sample,
[1528]405                                                                 const float pdf,
406                                                                 float &contribution)
[492]407{
[1189]408  S *data = Find(sample);
[492]409 
410  if (data)  {
[1189]411        contribution = pdf / (data->mSumPdf + pdf);
[492]412        return false;
413  }
414  else {
415        contribution = 1.0f;
416        return true;
417  }
418}
419
[1189]420template <typename T, typename S>
421bool Pvs<T, S>::RemoveSample(T sample,
[556]422                                                  const float pdf)
[485]423{
[1715]424  mSamples--;
425 
[1189]426  std::map<T, S, LtSample<T> >::
[556]427        iterator it = mEntries.find(sample);
[485]428 
[556]429  if (it == mEntries.end())
430        return false;
431 
[1189]432  S *data = &(*it).second;
[556]433 
434  data->mSumPdf -= pdf;
[1189]435
[556]436  if (data->mSumPdf <= 0.0f)
[1189]437  {
438          mEntries.erase(it);
439  }
440
[556]441  return true;
[485]442}
443
[1189]444template <typename T, typename S>
445int Pvs<T, S>::AddPvs(const Pvs<T, S> &pvs)
[485]446{
[1715]447  mSamples += pvs.mSamples;
[1189]448  std::map<T, S, LtSample<T> >::
[556]449        const_iterator it, it_end = pvs.mEntries.end();
450 
451  float contri;
452  // output PVS of view cell
[1189]453  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
454  {     
455          AddSample((*it).first, (*it).second.mSumPdf, contri);
456  }
[556]457 
458  return GetSize();
[485]459}
460 
[1189]461template <typename T, typename S>
462int Pvs<T, S>::SubtractPvs(const Pvs<T, S> &pvs)
[485]463{
[1715]464  mSamples -= pvs.mSamples;
[1189]465  std::map<T, S, LtSample<T> >::
[556]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();
[485]473}
474
[1189]475template <typename T, typename S>
476void Pvs<T, S>::CollectEntries(std::vector<T> &entries)
[469]477{
[1189]478        std::map<T, S, LtSample<T> >::
[485]479                const_iterator it, it_end = mEntries.end();
[469]480
481        // output PVS of view cell
482        for (it = mEntries.begin(); it != it_end; ++ it)
483                entries.push_back((*it)->first);
484}
485
[1189]486template <typename T, typename S>
487void Pvs<T, S>::NormalizeMaximum()
[556]488{
[1189]489  std::map<T, S, LtSample<T> >::
[556]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
[1189]501  maxSum = 1.0f / maxSum;
[556]502
503  for (it = mEntries.begin(); it != it_end; ++ it) {
504        (*it)->second.sumPdf *= maxSum;
505  }
506 
507}
508
509
[1667]510template <typename T, typename S>
511float Pvs<T, S>::GetEntrySize()
512{
[1673]513        return (float)(sizeof(T) + sizeof(S)) / float(1024 * 1024);
[1667]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
[311]526/** Class instantiating the Pvs template for kd tree nodes.
527*/
[1189]528class KdPvs: public Pvs<KdNode *, PvsData>
[308]529{
[1141]530public:
[311]531        int Compress();
[308]532};
533
[1077]534
[1189]535class ObjectPvs: public Pvs<Intersectable *, PvsData>
[1141]536{
537public:
[1586]538        /** Counts object int the pvs. Different to method "GetSize", not
[1141]539                only the raw container size is returned,
540                but the individual contributions of the entries are summed up.
541        */
[1707]542        float EvalPvsCost() const;
[1141]543};
544
[1586]545
546////////////
[1077]547//-- typedefs
548
[1189]549typedef std::map<KdNode *, PvsData, LtSample<KdNode *> > KdPvsMap;
550typedef std::map<Intersectable *, PvsData, LtSample<Intersectable *> > ObjectPvsMap;
551typedef std::map<ViewCell *, MailablePvsData, LtSample<ViewCell *> > ViewCellPvsMap;
[1077]552
[308]553
[1189]554typedef Pvs<ViewCell *, MailablePvsData> ViewCellPvs;
[1184]555
[860]556}
[469]557
[177]558#endif
559
Note: See TracBrowser for help on using the repository browser.