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

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