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

Revision 1089, 9.3 KB checked in by mattausch, 18 years ago (diff)
RevLine 
[177]1#ifndef __PVS_H
2#define __PVS_H
3
4#include <map>
[469]5#include <vector>
[177]6
[860]7namespace GtpVisibilityPreprocessor {
8
[177]9class KdNode;
[240]10class BspNode;
[191]11class Ray;
[308]12class Intersectable;
[1077]13class ViewCell;
[177]14
[1077]15
[310]16template<typename T>
17struct LtSample {
[311]18    bool operator()(const T a, const T b) const
[310]19    {
20                return a < b;
21        }
22};
23
[469]24/** Information stored with a PVS entry. Consists of the number
25        the object was seen from the view cell.
26*/
[310]27
28template<typename T>
29struct PvsData {
[556]30  //  int mVisibleSamples;
31  // sum of probability density of visible sample rays
32  float mSumPdf;
[310]33  PvsData<T>() {}
[556]34  PvsData<T>(const float sumPdf):
35        mSumPdf(sumPdf) {}
36
37  // $$JB in order to return meaningfull values
38  // it assumes that the sum pdf has been normalized somehow!!!
39  float GetVisibility() { return mSumPdf; }
[310]40};
41
[469]42/** Template class representing the Potentially Visible Set (PVS)
43        mainly from a view cell, but also e.g., from objects.
44*/
[310]45template<typename T>
[311]46class Pvs
[310]47{
48public:
[469]49  Pvs(): /*mSamples(0), */mEntries() {}
[466]50 
[469]51  //int mSamples;
[466]52 
[469]53  /** Compresses PVS lossless or lossy.
54  */
[466]55  int Compress() {return 0;}
56  int GetSize() const {return (int)mEntries.size();}
[469]57  bool Empty() const {return mEntries.empty();}
[556]58
59  /** Normalize the visibility of entries in order to get comparable
60          results */
[469]61 
[556]62  void NormalizeMaximum();
63 
[610]64  /** Merges pvs of a into this pvs.
[466]65   */
[610]66  void Merge(const Pvs<T> &a);
[469]67 
[466]68  /** Difference of pvs to pvs b.
69          @returns number of different entries.
70  */
71  int Diff(const Pvs<T> &b);
72 
[469]73  /** Finds sample in PVS.
74          @returns sample if found, NULL otherwise.
75  */
[466]76  PvsData<T> *Find(T sample);
[492]77
[556]78  bool GetSampleContribution(T sample, const float pdf, float &contribution);
[469]79 
80  /** Adds sample to PVS.
81          @contribution contribution of sample (0 or 1)
82          @returns true if sample was not already in PVS.
83  */
[556]84  bool AddSample(T sample, const float pdf, float &contribution);
[469]85
86  /** Adds sample to PVS.
87          @returns contribution of sample (0 or 1)
88  */
[556]89  float AddSample(T sample, const float pdf);
[492]90 
[485]91  /** Adds one pvs to another one.
92          @returns new pvs size
93  */
94  int AddPvs(const Pvs<T> &pvs);
[752]95
[485]96  /** Subtracts one pvs from another one.
[752]97  WARNING: could contains bugs
[485]98          @returns new pvs size
99  */
100  int SubtractPvs(const Pvs<T> &pvs);
[469]101  /** Returns PVS data, i.e., how often it was seen from the view cell,
102          and the object itsef.
103  */
[466]104  void GetData(const int index, T &entry, PvsData<T> &data);
[469]105
106  /** Collects the PVS entries and returns them in the vector.
107  */
108  void CollectEntries(std::vector<T> &entries);
109
[485]110  /** Removes sample from PVS if reference count is zero.
[1089]111          @param visibleSamples number of references to be removed
[485]112  */
[556]113  bool RemoveSample(T sample, const float pdf);
[485]114
[677]115  /** Compute continuous PVS difference */
[704]116  void ComputeContinuousPvsDifference(Pvs<T> &pvs,
[677]117                                                                          float &pvsReduction,
118                                                                          float &pvsEnlargement);
119 
120
[752]121  /** Clears the pvs.
122  */
123  void Clear();
124
[695]125  /** Compute continuous PVS difference */
[704]126  float GetPvsHomogenity(Pvs<T> &pvs) {
[695]127        float
128          pvsReduction,
129          pvsEnlargement;
[713]130       
[695]131        ComputeContinuousPvsDifference(pvs,
132                                                                   pvsReduction,
133                                                                   pvsEnlargement);
[713]134       
[695]135        return pvsReduction + pvsEnlargement;
136  }
137
[677]138                                         
139                                         
[469]140  /// Map of PVS entries
[466]141  std::map<T, PvsData<T>, LtSample<T> > mEntries;
[310]142};
143
[581]144
[677]145
[695]146/**
147   Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
148   Provides separatelly PVS reduction from PVS enlargement.
149
150*/
[341]151template <typename T>
[677]152void
[704]153Pvs<T>::ComputeContinuousPvsDifference(Pvs<T> &b,
[677]154                                                                           float &pvsReduction,
155                                                                           float &pvsEnlargement)
156{
[705]157        pvsReduction = 0.0f;
158        pvsEnlargement = 0.0f;
[695]159  // Uses sum of log differences, which corresponds to entropy
[704]160  std::map<T, PvsData<T>, LtSample<T> >::iterator it;
[677]161 
[704]162  for (it = b.mEntries.begin();
163          it != b.mEntries.end(); ++ it) {
[695]164        float bSumPdf = (*it).second.mSumPdf;
165        float aSumPdf = 0.0f;
166        PvsData<T> *data = Find((*it).first);           
167        if (data) {
[704]168          aSumPdf = data->mSumPdf;
[695]169          // mark this entry as processed to avoid double counting
[704]170          data->mSumPdf = -aSumPdf;
[695]171        }
[713]172
173#if 0
[695]174        float diff = bSumPdf - aSumPdf;
175       
176        if (diff > 0.0f) {
177          pvsEnlargement += diff;
178        } else {
179          pvsReduction += -diff;
180        }
[713]181#else
182        if (!data)
183          pvsEnlargement += 1.0f;
184#endif
[695]185  }
186 
187  for (it = mEntries.begin(); it != mEntries.end(); ++ it) {
188        float aSumPdf = (*it).second.mSumPdf;
189        float bSumPdf = 0.0f;
190        if (aSumPdf < 0.0f) {
191          // this entry was already accounted for!
192          // just revert it back
193          (*it).second.mSumPdf = -aSumPdf;
194        } else {
195          PvsData<T> *data = b.Find((*it).first);
196          if (data) {
[704]197                bSumPdf = data->mSumPdf;
[695]198          }
[713]199#if 0
[695]200          float diff = bSumPdf - aSumPdf;
201         
202          if (diff > 0.0f) {
203                pvsEnlargement += diff;
204          } else {
205                pvsReduction += -diff;
206          }
[713]207
208#else
209          if (!data)
210                pvsReduction += 1.0f;
211#endif
[695]212        }
213  }
[677]214}
215
216template <typename T>
[362]217int Pvs<T>::Diff(const Pvs<T> &b)
218{
219        int dif = 0;
220
221        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
222
223        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
224        {
225                PvsData<T> *data = Find((*it).first);           
226                if (!data) ++ dif;
227        }
228
229        return dif;
230}
231
232template <typename T>
[610]233void Pvs<T>::Merge(const Pvs<T> &a)
[341]234{
[362]235        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
236
[610]237        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
[362]238        {
239                PvsData<T> *data = Find((*it).first);
240               
241                if (data)
[556]242                        data->mSumPdf += (*it).second.mSumPdf;
[362]243                else
244                        mEntries.insert(*it);
245        }
[341]246}
247
[752]248template <typename T> void Pvs<T>::Clear()
249{
250        mEntries.clear();
251}
252
253
[310]254template <typename T>
[311]255PvsData<T> *Pvs<T>::Find(T sample)
[310]256{
[311]257  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.find(sample);
[310]258  if (i != mEntries.end()) {
259    return &(*i).second;
[311]260  } else
[310]261    return NULL;
262}
263
264template <typename T>
[311]265void Pvs<T>::GetData(const int index,
[485]266                                         T &entry,
267                                         PvsData<T> &data)
[310]268{
[311]269  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.begin();
[310]270  for (int k = 0; k != index && i != mEntries.end(); i++, k++);
271
272  entry = (*i).first;
[311]273  data = (*i).second;
[310]274}
275
[311]276template <typename T>
[556]277float
278Pvs<T>::AddSample(T sample, const float pdf)
[177]279{
[492]280  PvsData<T> *data = Find(sample);
281 
282  if (data)  {
[556]283        data->mSumPdf+=pdf;
284        return data->mSumPdf;
[492]285  }
286  else {
[556]287        mEntries[sample] = PvsData<T>(pdf);
288        return pdf;
[492]289  }
[466]290}
[177]291
[466]292template <typename T>
[492]293bool
[556]294Pvs<T>::AddSample(T sample,
295                                  const float pdf,
296                                  float &contribution)
[466]297{
298  PvsData<T> *data = Find(sample);
299 
300  if (data)  {
[556]301        data->mSumPdf+=pdf;
302        contribution = pdf/data->mSumPdf;
[466]303        return false;
304  }
305  else {
[556]306        mEntries[sample] = PvsData<T>(pdf);
[466]307        contribution = 1.0f;
308        return true;
309  }
[311]310}
[308]311
[469]312template <typename T>
[492]313bool
[556]314Pvs<T>::GetSampleContribution(T sample,
315                                                          const float pdf,
316                                                          float &contribution)
[492]317{
318  PvsData<T> *data = Find(sample);
319 
320  if (data)  {
[556]321        contribution = pdf/(data->mSumPdf + pdf);
[492]322        return false;
323  }
324  else {
325        contribution = 1.0f;
326        return true;
327  }
328}
329
330template <typename T>
[556]331bool Pvs<T>::RemoveSample(T sample,
332                                                  const float pdf)
[485]333{
[556]334  std::map<T, PvsData<T>, LtSample<T> >::
335        iterator it = mEntries.find(sample);
[485]336 
[556]337  if (it == mEntries.end())
338        return false;
339 
340  PvsData<T> *data = &(*it).second;
341 
342  data->mSumPdf -= pdf;
343  if (data->mSumPdf <= 0.0f)
344        mEntries.erase(it);
345 
346  return true;
[485]347}
348
349template <typename T>
350int Pvs<T>::AddPvs(const Pvs<T> &pvs)
351{
[556]352  std::map<T, PvsData<T>, LtSample<T> >::
353        const_iterator it, it_end = pvs.mEntries.end();
354 
355  float contri;
356  // output PVS of view cell
357  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
358        AddSample((*it).first, (*it).second.mSumPdf, contri);
359 
360  return GetSize();
[485]361}
362 
363template <typename T>
364int Pvs<T>::SubtractPvs(const Pvs<T> &pvs)
365{
[556]366  std::map<T, PvsData<T>, LtSample<T> >::
367        const_iterator it, it_end = pvs.mEntries.end();
368 
369  // output PVS of view cell
370  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
371        RemoveSample((*it).first, (*it).second.mSumPdf);
372 
373  return GetSize();
[485]374}
375
376template <typename T>
[469]377void Pvs<T>::CollectEntries(std::vector<T> &entries)
378{
[485]379        std::map<T, PvsData<T>, LtSample<T> >::
380                const_iterator it, it_end = mEntries.end();
[469]381
382        // output PVS of view cell
383        for (it = mEntries.begin(); it != it_end; ++ it)
384                entries.push_back((*it)->first);
385}
386
[556]387template <typename T>
388void Pvs<T>::NormalizeMaximum()
389{
390  std::map<T, PvsData<T>, LtSample<T> >::
391        const_iterator it, it_end = mEntries.end();
392
393  float maxPdfSum = -1.0f;
394
395  // output PVS of view cell
396  for (it = mEntries.begin(); it != it_end; ++ it) {
397        float sum = (*it)->second.sumPdf;
398        if (sum > maxSum)
399          maxSum = sum;
400  }
401
402  maxSum = 1.0f/maxSum;
403
404  for (it = mEntries.begin(); it != it_end; ++ it) {
405        (*it)->second.sumPdf *= maxSum;
406  }
407 
408}
409
410
[311]411/** Class instantiating the Pvs template for kd tree nodes.
412*/
413class KdPvs: public Pvs<KdNode *>
[308]414{
[311]415        int Compress();
[308]416};
417
[1077]418
419//-- typedefs
420
[311]421typedef std::map<KdNode *, PvsData<KdNode *>, LtSample<KdNode *> > KdPvsMap;
[469]422typedef std::map<Intersectable *, PvsData<Intersectable *>, LtSample<Intersectable *> > ObjectPvsMap;
[1077]423typedef std::map<ViewCell *, PvsData<ViewCell *>, LtSample<ViewCell *> > ViewCellPvsMap;
424
[469]425typedef PvsData<Intersectable *> ObjectPvsData;
[311]426typedef PvsData<KdNode *> KdPvsData;
[308]427
[469]428typedef Pvs<Intersectable *> ObjectPvs;
[1077]429typedef Pvs<ViewCell *> ViewCellPvs;
[860]430}
[469]431
[177]432#endif
433
Note: See TracBrowser for help on using the repository browser.