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

Revision 1168, 9.6 KB checked in by mattausch, 18 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 ViewCell;
14
15
16template<typename T>
17struct LtSample {
18    bool operator()(const T a, const T b) const
19    {
20                return a < b;
21        }
22};
23
24/** Information stored with a PVS entry. Consists of the number
25        the object was seen from the view cell.
26*/
27
28template<typename T>
29struct PvsData {
30  //  int mVisibleSamples;
31  // sum of probability density of visible sample rays
32  float mSumPdf;
33  PvsData<T>() {}
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; }
40};
41
42/** Template class representing the Potentially Visible Set (PVS)
43        mainly from a view cell, but also e.g., from objects.
44*/
45template<typename T>
46class Pvs
47{
48public:
49  Pvs(): /*mSamples(0), */mEntries() {}
50 
51  //int mSamples;
52 
53  /** Compresses PVS lossless or lossy.
54  */
55  int Compress() {return 0;}
56  int GetSize() const {return (int)mEntries.size();}
57  bool Empty() const {return mEntries.empty();}
58
59  /** Normalize the visibility of entries in order to get comparable
60          results
61  */
62  void NormalizeMaximum();
63 
64  /** Merges pvs of a into this pvs.
65   */
66  void Merge(const Pvs<T> &a);
67 
68  /** Difference of pvs to pvs b.
69          @returns number of different entries.
70  */
71  int Diff(const Pvs<T> &b);
72 
73  /** Finds sample in PVS.
74          @returns sample if found, NULL otherwise.
75  */
76  PvsData<T> *Find(T sample);
77
78  bool GetSampleContribution(T sample, const float pdf, float &contribution);
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  */
84  bool AddSample(T sample, const float pdf, float &contribution);
85
86  /** Adds sample to PVS.
87          @returns contribution of sample (0 or 1)
88  */
89  float AddSample(T sample, const float pdf);
90 
91  /** Adds one pvs to another one.
92          @returns new pvs size
93  */
94  int AddPvs(const Pvs<T> &pvs);
95
96  /** Subtracts one pvs from another one.
97  WARNING: could contains bugs
98          @returns new pvs size
99  */
100  int SubtractPvs(const Pvs<T> &pvs);
101  /** Returns PVS data, i.e., how often it was seen from the view cell,
102          and the object itsef.
103  */
104  void GetData(const int index, T &entry, PvsData<T> &data);
105
106  /** Collects the PVS entries and returns them in the vector.
107  */
108  void CollectEntries(std::vector<T> &entries);
109
110  /** Removes sample from PVS if reference count is zero.
111          @param visibleSamples number of references to be removed
112  */
113  bool RemoveSample(T sample, const float pdf);
114
115  /** Compute continuous PVS difference */
116  void ComputeContinuousPvsDifference(Pvs<T> &pvs,
117                                                                          float &pvsReduction,
118                                                                          float &pvsEnlargement);
119 
120
121  /** Clears the pvs.
122  */
123  void Clear();
124
125  /** Compute continuous PVS difference */
126  float GetPvsHomogenity(Pvs<T> &pvs) {
127        float
128          pvsReduction,
129          pvsEnlargement;
130       
131        ComputeContinuousPvsDifference(pvs,
132                                                                   pvsReduction,
133                                                                   pvsEnlargement);
134       
135        return pvsReduction + pvsEnlargement;
136  }
137
138                                         
139                                         
140  /// Map of PVS entries
141  std::map<T, PvsData<T>, LtSample<T> > mEntries;
142};
143
144
145
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*/
151template <typename T>
152void
153Pvs<T>::ComputeContinuousPvsDifference(Pvs<T> &b,
154                                                                           float &pvsReduction,
155                                                                           float &pvsEnlargement)
156{
157        pvsReduction = 0.0f;
158        pvsEnlargement = 0.0f;
159  // Uses sum of log differences, which corresponds to entropy
160  std::map<T, PvsData<T>, LtSample<T> >::iterator it;
161 
162  for (it = b.mEntries.begin();
163          it != b.mEntries.end(); ++ it) {
164        float bSumPdf = (*it).second.mSumPdf;
165        float aSumPdf = 0.0f;
166        PvsData<T> *data = Find((*it).first);           
167        if (data) {
168          aSumPdf = data->mSumPdf;
169          // mark this entry as processed to avoid double counting
170          data->mSumPdf = -aSumPdf;
171        }
172
173#if 0
174        float diff = bSumPdf - aSumPdf;
175       
176        if (diff > 0.0f) {
177          pvsEnlargement += diff;
178        } else {
179          pvsReduction += -diff;
180        }
181#else
182        if (!data)
183          pvsEnlargement += 1.0f;
184#endif
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) {
197                bSumPdf = data->mSumPdf;
198          }
199#if 0
200          float diff = bSumPdf - aSumPdf;
201         
202          if (diff > 0.0f) {
203                pvsEnlargement += diff;
204          } else {
205                pvsReduction += -diff;
206          }
207
208#else
209          if (!data)
210                pvsReduction += 1.0f;
211#endif
212        }
213  }
214}
215
216template <typename T>
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>
233void Pvs<T>::Merge(const Pvs<T> &a)
234{
235        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
236
237        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
238        {
239                PvsData<T> *data = Find((*it).first);
240               
241                if (data)
242                        data->mSumPdf += (*it).second.mSumPdf;
243                else
244                        mEntries.insert(*it);
245        }
246}
247
248template <typename T> void Pvs<T>::Clear()
249{
250        mEntries.clear();
251}
252
253
254template <typename T>
255PvsData<T> *Pvs<T>::Find(T sample)
256{
257  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.find(sample);
258  if (i != mEntries.end()) {
259    return &(*i).second;
260  } else
261    return NULL;
262}
263
264template <typename T>
265void Pvs<T>::GetData(const int index,
266                                         T &entry,
267                                         PvsData<T> &data)
268{
269  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.begin();
270  for (int k = 0; k != index && i != mEntries.end(); i++, k++);
271
272  entry = (*i).first;
273  data = (*i).second;
274}
275
276template <typename T>
277float
278Pvs<T>::AddSample(T sample, const float pdf)
279{
280  PvsData<T> *data = Find(sample);
281 
282  if (data)  {
283        data->mSumPdf += pdf;
284        return data->mSumPdf;
285  }
286  else {
287        mEntries[sample] = PvsData<T>(pdf);
288        return pdf;
289  }
290}
291
292template <typename T>
293bool
294Pvs<T>::AddSample(T sample,
295                                  const float pdf,
296                                  float &contribution)
297{
298  PvsData<T> *data = Find(sample);
299 
300  if (data)  {
301        data->mSumPdf += pdf;
302        contribution = pdf/data->mSumPdf;
303        return false;
304  }
305  else {
306        mEntries[sample] = PvsData<T>(pdf);
307        contribution = 1.0f;
308        return true;
309  }
310}
311
312template <typename T>
313bool
314Pvs<T>::GetSampleContribution(T sample,
315                                                          const float pdf,
316                                                          float &contribution)
317{
318  PvsData<T> *data = Find(sample);
319 
320  if (data)  {
321        contribution = pdf/(data->mSumPdf + pdf);
322        return false;
323  }
324  else {
325        contribution = 1.0f;
326        return true;
327  }
328}
329
330template <typename T>
331bool Pvs<T>::RemoveSample(T sample,
332                                                  const float pdf)
333{
334  std::map<T, PvsData<T>, LtSample<T> >::
335        iterator it = mEntries.find(sample);
336 
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;
347}
348
349template <typename T>
350int Pvs<T>::AddPvs(const Pvs<T> &pvs)
351{
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();
361}
362 
363template <typename T>
364int Pvs<T>::SubtractPvs(const Pvs<T> &pvs)
365{
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();
374}
375
376template <typename T>
377void Pvs<T>::CollectEntries(std::vector<T> &entries)
378{
379        std::map<T, PvsData<T>, LtSample<T> >::
380                const_iterator it, it_end = mEntries.end();
381
382        // output PVS of view cell
383        for (it = mEntries.begin(); it != it_end; ++ it)
384                entries.push_back((*it)->first);
385}
386
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
411/** Class instantiating the Pvs template for kd tree nodes.
412*/
413class KdPvs: public Pvs<KdNode *>
414{
415public:
416        int Compress();
417};
418
419
420class ObjectPvs: public Pvs<Intersectable *>
421{
422public:
423        /** Counts object int the pvs. Different to GetSize(), not
424                only the raw container size is returned,
425                but the individual contributions of the entries are summed up.
426        */
427        int CountObjectsInPvs() const;
428};
429
430//-- typedefs
431
432typedef std::map<KdNode *, PvsData<KdNode *>, LtSample<KdNode *> > KdPvsMap;
433typedef std::map<Intersectable *, PvsData<Intersectable *>, LtSample<Intersectable *> > ObjectPvsMap;
434typedef std::map<ViewCell *, PvsData<ViewCell *>, LtSample<ViewCell *> > ViewCellPvsMap;
435
436typedef PvsData<Intersectable *> ObjectPvsData;
437typedef PvsData<KdNode *> KdPvsData;
438
439//typedef Pvs<Intersectable *> ObjectPvs;
440typedef Pvs<ViewCell *> ViewCellPvs;
441}
442
443#endif
444
Note: See TracBrowser for help on using the repository browser.