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

Revision 1189, 11.0 KB checked in by mattausch, 18 years ago (diff)

changed osp partition to something taking mult references into account

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:
31  // sum of probability density of visible sample rays
32  float mSumPdf;
[310]33
[1189]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{
[1184]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
[556]75  // sum of probability density of visible sample rays
76  float mSumPdf;
[1189]77  int mCounter;
[1184]78
[1189]79  MailablePvsData() {}
80  MailablePvsData(const float sumPdf):
[556]81        mSumPdf(sumPdf) {}
82
83  // $$JB in order to return meaningfull values
84  // it assumes that the sum pdf has been normalized somehow!!!
[1184]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:
[469]99  Pvs(): /*mSamples(0), */mEntries() {}
[466]100 
[1189]101  //virtual ~Pvs();
102   
[469]103  /** Compresses PVS lossless or lossy.
104  */
[466]105  int Compress() {return 0;}
106  int GetSize() const {return (int)mEntries.size();}
[469]107  bool Empty() const {return mEntries.empty();}
[556]108
109  /** Normalize the visibility of entries in order to get comparable
[1141]110          results
111  */
[556]112  void NormalizeMaximum();
113 
[610]114  /** Merges pvs of a into this pvs.
[466]115   */
[1189]116  void Merge(const Pvs<T, S> &a);
[469]117 
[466]118  /** Difference of pvs to pvs b.
119          @returns number of different entries.
120  */
[1189]121  int Diff(const Pvs<T, S> &b);
[466]122 
[469]123  /** Finds sample in PVS.
124          @returns sample if found, NULL otherwise.
125  */
[1189]126  S *Find(T sample);
[492]127
[556]128  bool GetSampleContribution(T sample, const float pdf, float &contribution);
[469]129 
130  /** Adds sample to PVS.
131          @contribution contribution of sample (0 or 1)
132          @returns true if sample was not already in PVS.
133  */
[556]134  bool AddSample(T sample, const float pdf, float &contribution);
[469]135
136  /** Adds sample to PVS.
137          @returns contribution of sample (0 or 1)
138  */
[556]139  float AddSample(T sample, const float pdf);
[492]140 
[1184]141  /** Adds sample to PVS.
142          @returns PvsData
143  */
[1189]144  S *AddSample2(T sample, const float pdf);
[1184]145
[485]146  /** Adds one pvs to another one.
147          @returns new pvs size
148  */
[1189]149  int AddPvs(const Pvs<T, S> &pvs);
[752]150
[485]151  /** Subtracts one pvs from another one.
[752]152  WARNING: could contains bugs
[485]153          @returns new pvs size
154  */
[1189]155  int SubtractPvs(const Pvs<T, S> &pvs);
[469]156  /** Returns PVS data, i.e., how often it was seen from the view cell,
157          and the object itsef.
158  */
[1189]159  void GetData(const int index, T &entry, S &data);
[469]160
161  /** Collects the PVS entries and returns them in the vector.
162  */
163  void CollectEntries(std::vector<T> &entries);
164
[485]165  /** Removes sample from PVS if reference count is zero.
[1089]166          @param visibleSamples number of references to be removed
[485]167  */
[556]168  bool RemoveSample(T sample, const float pdf);
[485]169
[677]170  /** Compute continuous PVS difference */
[1189]171  void ComputeContinuousPvsDifference(Pvs<T, S> &pvs,
[677]172                                                                          float &pvsReduction,
173                                                                          float &pvsEnlargement);
174 
175
[752]176  /** Clears the pvs.
177  */
178  void Clear();
179
[695]180  /** Compute continuous PVS difference */
[1189]181  float GetPvsHomogenity(Pvs<T, S> &pvs) {
[695]182        float
183          pvsReduction,
184          pvsEnlargement;
[713]185       
[695]186        ComputeContinuousPvsDifference(pvs,
187                                                                   pvsReduction,
188                                                                   pvsEnlargement);
[713]189       
[695]190        return pvsReduction + pvsEnlargement;
191  }
192
[677]193                                         
194                                         
[469]195  /// Map of PVS entries
[1189]196  std::map<T, S, LtSample<T> > mEntries;
[310]197};
198
[581]199
[677]200
[695]201/**
202   Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
203   Provides separatelly PVS reduction from PVS enlargement.
204
205*/
[1189]206template <typename T, typename S>
[677]207void
[1189]208Pvs<T, S>::ComputeContinuousPvsDifference(Pvs<T, S> &b,
[677]209                                                                           float &pvsReduction,
210                                                                           float &pvsEnlargement)
211{
[705]212        pvsReduction = 0.0f;
213        pvsEnlargement = 0.0f;
[695]214  // Uses sum of log differences, which corresponds to entropy
[1189]215  std::map<T, S, LtSample<T> >::iterator it;
[677]216 
[1189]217  for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
218  {
[695]219        float bSumPdf = (*it).second.mSumPdf;
220        float aSumPdf = 0.0f;
[1189]221        S *data = Find((*it).first);           
222       
223        if (data)
224        {
225                aSumPdf = data->mSumPdf;
226                // mark this entry as processed to avoid double counting
227                data->mSumPdf = -aSumPdf;
[695]228        }
[713]229
230#if 0
[695]231        float diff = bSumPdf - aSumPdf;
232       
233        if (diff > 0.0f) {
234          pvsEnlargement += diff;
235        } else {
236          pvsReduction += -diff;
237        }
[713]238#else
239        if (!data)
240          pvsEnlargement += 1.0f;
241#endif
[695]242  }
243 
244  for (it = mEntries.begin(); it != mEntries.end(); ++ it) {
245        float aSumPdf = (*it).second.mSumPdf;
246        float bSumPdf = 0.0f;
247        if (aSumPdf < 0.0f) {
248          // this entry was already accounted for!
249          // just revert it back
250          (*it).second.mSumPdf = -aSumPdf;
251        } else {
[1189]252          S *data = b.Find((*it).first);
[695]253          if (data) {
[704]254                bSumPdf = data->mSumPdf;
[695]255          }
[713]256#if 0
[695]257          float diff = bSumPdf - aSumPdf;
258         
259          if (diff > 0.0f) {
260                pvsEnlargement += diff;
261          } else {
262                pvsReduction += -diff;
263          }
[713]264
265#else
266          if (!data)
267                pvsReduction += 1.0f;
268#endif
[695]269        }
270  }
[677]271}
272
[1189]273template <typename T, typename S>
274int Pvs<T, S>::Diff(const Pvs<T, S> &b)
[362]275{
276        int dif = 0;
277
[1189]278        std::map<T, S, LtSample<T> >::const_iterator it;
[362]279
280        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
281        {
[1189]282                S data = Find((*it).first);             
[362]283                if (!data) ++ dif;
284        }
285
286        return dif;
287}
288
[1189]289template <typename T, typename S> void Pvs<T, S>::Merge(const Pvs<T, S> &a)
[341]290{
[1189]291        std::map<T, S, LtSample<T> >::const_iterator it;
[362]292
[610]293        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
[362]294        {
[1189]295                AddSample((*it).first, (*it).second.mSumPdf);
[362]296        }
[341]297}
298
[1189]299
300template <typename T, typename S> void Pvs<T, S>::Clear()
[752]301{
302        mEntries.clear();
303}
304
305
[1189]306template <typename T, typename S>
307S *Pvs<T, S>::Find(T sample)
[310]308{
[1189]309  std::map<T, S, LtSample<T> >::iterator i = mEntries.find(sample);
310
311  if (i != mEntries.end())
312  {
313          return &(*i).second;
314  }
315  else
316  {
317          return NULL;
318  }
[310]319}
320
[1189]321template <typename T, typename S>
322void Pvs<T, S>::GetData(const int index,
[485]323                                         T &entry,
[1189]324                                         S &data)
[310]325{
[1189]326  std::map<T, S, LtSample<T> >::iterator i = mEntries.begin();
[310]327  for (int k = 0; k != index && i != mEntries.end(); i++, k++);
328
329  entry = (*i).first;
[311]330  data = (*i).second;
[1189]331 
[310]332}
333
[1189]334template <typename T, typename S>
[556]335float
[1189]336Pvs<T, S>::AddSample(T sample, const float pdf)
[177]337{
[1189]338        S *data = Find(sample);
[492]339 
[1189]340        if (data) 
341        {
342                data->mSumPdf += pdf;
343                return data->mSumPdf;
344        }
345        else
346        {
347                mEntries[sample] = S(pdf);
348                return pdf;
349        }
[466]350}
[177]351
[1189]352
353template <typename T, typename S>
354S * Pvs<T, S>::AddSample2(T sample, const float pdf)
[1184]355{
[1189]356        S *data = Find(sample);
[1184]357 
[1189]358        if (data) 
359        {
360                data->mSumPdf += pdf;
361        }
362        else
363        {
364                mEntries[sample] = S(pdf);
365                data = Find(sample);
366        }
367
368        return data;
[1184]369}
370
[1189]371template <typename T, typename S>
372bool Pvs<T, S>::AddSample(T sample,
[556]373                                  const float pdf,
374                                  float &contribution)
[466]375{
[1189]376  S *data = Find(sample);
[466]377 
[1189]378  if (data) 
379  {
[1112]380        data->mSumPdf += pdf;
[1189]381        contribution = pdf / data->mSumPdf;
[466]382        return false;
383  }
384  else {
[1189]385        mEntries[sample] = S(pdf);
[466]386        contribution = 1.0f;
387        return true;
388  }
[311]389}
[308]390
[1189]391template <typename T, typename S>
[492]392bool
[1189]393Pvs<T, S>::GetSampleContribution(T sample,
[556]394                                                          const float pdf,
395                                                          float &contribution)
[492]396{
[1189]397  S *data = Find(sample);
[492]398 
399  if (data)  {
[1189]400        contribution = pdf / (data->mSumPdf + pdf);
[492]401        return false;
402  }
403  else {
404        contribution = 1.0f;
405        return true;
406  }
407}
408
[1189]409template <typename T, typename S>
410bool Pvs<T, S>::RemoveSample(T sample,
[556]411                                                  const float pdf)
[485]412{
[1189]413  std::map<T, S, LtSample<T> >::
[556]414        iterator it = mEntries.find(sample);
[485]415 
[556]416  if (it == mEntries.end())
417        return false;
418 
[1189]419  S *data = &(*it).second;
[556]420 
421  data->mSumPdf -= pdf;
[1189]422
[556]423  if (data->mSumPdf <= 0.0f)
[1189]424  {
425          mEntries.erase(it);
426  }
427
[556]428  return true;
[485]429}
430
[1189]431template <typename T, typename S>
432int Pvs<T, S>::AddPvs(const Pvs<T, S> &pvs)
[485]433{
[1189]434  std::map<T, S, LtSample<T> >::
[556]435        const_iterator it, it_end = pvs.mEntries.end();
436 
437  float contri;
438  // output PVS of view cell
[1189]439  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
440  {     
441          AddSample((*it).first, (*it).second.mSumPdf, contri);
442  }
[556]443 
444  return GetSize();
[485]445}
446 
[1189]447template <typename T, typename S>
448int Pvs<T, S>::SubtractPvs(const Pvs<T, S> &pvs)
[485]449{
[1189]450  std::map<T, S, LtSample<T> >::
[556]451        const_iterator it, it_end = pvs.mEntries.end();
452 
453  // output PVS of view cell
454  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
455        RemoveSample((*it).first, (*it).second.mSumPdf);
456 
457  return GetSize();
[485]458}
459
[1189]460template <typename T, typename S>
461void Pvs<T, S>::CollectEntries(std::vector<T> &entries)
[469]462{
[1189]463        std::map<T, S, LtSample<T> >::
[485]464                const_iterator it, it_end = mEntries.end();
[469]465
466        // output PVS of view cell
467        for (it = mEntries.begin(); it != it_end; ++ it)
468                entries.push_back((*it)->first);
469}
470
[1189]471template <typename T, typename S>
472void Pvs<T, S>::NormalizeMaximum()
[556]473{
[1189]474  std::map<T, S, LtSample<T> >::
[556]475        const_iterator it, it_end = mEntries.end();
476
477  float maxPdfSum = -1.0f;
478
479  // output PVS of view cell
480  for (it = mEntries.begin(); it != it_end; ++ it) {
481        float sum = (*it)->second.sumPdf;
482        if (sum > maxSum)
483          maxSum = sum;
484  }
485
[1189]486  maxSum = 1.0f / maxSum;
[556]487
488  for (it = mEntries.begin(); it != it_end; ++ it) {
489        (*it)->second.sumPdf *= maxSum;
490  }
491 
492}
493
494
[311]495/** Class instantiating the Pvs template for kd tree nodes.
496*/
[1189]497class KdPvs: public Pvs<KdNode *, PvsData>
[308]498{
[1141]499public:
[311]500        int Compress();
[308]501};
502
[1077]503
[1189]504class ObjectPvs: public Pvs<Intersectable *, PvsData>
[1141]505{
506public:
[1168]507        /** Counts object int the pvs. Different to GetSize(), not
[1141]508                only the raw container size is returned,
509                but the individual contributions of the entries are summed up.
510        */
[1168]511        int CountObjectsInPvs() const;
[1141]512};
513
[1077]514//-- typedefs
515
[1189]516typedef std::map<KdNode *, PvsData, LtSample<KdNode *> > KdPvsMap;
517typedef std::map<Intersectable *, PvsData, LtSample<Intersectable *> > ObjectPvsMap;
518typedef std::map<ViewCell *, MailablePvsData, LtSample<ViewCell *> > ViewCellPvsMap;
[1077]519
[308]520
[1189]521typedef Pvs<ViewCell *, MailablePvsData> ViewCellPvs;
[1184]522
[860]523}
[469]524
[177]525#endif
526
Note: See TracBrowser for help on using the repository browser.