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