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