[2116] | 1 | #ifndef __VERBOSEPVS_H
|
---|
| 2 | #define __VERBOSEPVS_H
|
---|
[177] | 3 |
|
---|
[469] | 4 | #include <vector>
|
---|
[1189] | 5 | #include "common.h"
|
---|
[2019] | 6 | #include <math.h>
|
---|
[2116] | 7 | #include "PvsBase.h"
|
---|
| 8 |
|
---|
| 9 |
|
---|
[177] | 10 |
|
---|
[860] | 11 | namespace GtpVisibilityPreprocessor {
|
---|
| 12 |
|
---|
[177] | 13 |
|
---|
[2530] | 14 | /** Iterator over the pvs.
|
---|
| 15 | */
|
---|
[1740] | 16 | template<typename T, typename S>
|
---|
[1742] | 17 | class PvsIterator
|
---|
| 18 | {
|
---|
| 19 | public:
|
---|
[2116] | 20 | PvsIterator<T, S>(){}
|
---|
[1742] | 21 | PvsIterator<T, S>(const typename vector<PvsEntry<T, S> >::const_iterator &itCurrent,
|
---|
| 22 | const typename vector<PvsEntry<T, S> >::const_iterator &itEnd):
|
---|
| 23 | mItCurrent(itCurrent), mItEnd(itEnd)
|
---|
| 24 | {
|
---|
| 25 | }
|
---|
| 26 |
|
---|
[2530] | 27 | inline bool HasMoreEntries() const { return (mItCurrent != mItEnd); }
|
---|
[1742] | 28 |
|
---|
[2530] | 29 | inline T Next(S &pdf) {
|
---|
[2117] | 30 | pdf = (*mItCurrent).mData;
|
---|
| 31 | return (*(mItCurrent ++)).mObject;
|
---|
[1742] | 32 | }
|
---|
[2116] | 33 |
|
---|
[2530] | 34 | inline T Next() { return (*(mItCurrent ++)).mObject; }
|
---|
[2117] | 35 |
|
---|
[2530] | 36 |
|
---|
[1742] | 37 | private:
|
---|
[2530] | 38 |
|
---|
[1742] | 39 | typename vector<PvsEntry<T, S> >::const_iterator mItCurrent;
|
---|
| 40 | typename vector<PvsEntry<T, S> >::const_iterator mItEnd;
|
---|
[1740] | 41 | };
|
---|
| 42 |
|
---|
| 43 |
|
---|
[2570] | 44 | struct VerbosePvsStats
|
---|
| 45 | {
|
---|
| 46 | VerbosePvsStats(): mDistanceWeightedTriangles(0), mDistanceWeightedPvs(0), mWeightedTriangles(0)
|
---|
| 47 | {}
|
---|
| 48 |
|
---|
| 49 | float mDistanceWeightedTriangles;
|
---|
| 50 | float mDistanceWeightedPvs;
|
---|
| 51 | float mWeightedTriangles;
|
---|
| 52 | };
|
---|
| 53 |
|
---|
| 54 |
|
---|
[469] | 55 | /** Template class representing the Potentially Visible Set (PVS)
|
---|
| 56 | mainly from a view cell, but also e.g., from objects.
|
---|
| 57 | */
|
---|
[1189] | 58 | template<typename T, typename S>
|
---|
[2116] | 59 | class VerbosePvs
|
---|
[310] | 60 | {
|
---|
[2116] | 61 | template<typename T, typename S> friend class PvsIterator;
|
---|
[1740] | 62 |
|
---|
[310] | 63 | public:
|
---|
[2100] | 64 |
|
---|
[2530] | 65 | VerbosePvs(): mSamples(0), mEntries(), mLastSorted(0), mQueriesSinceSort(0)
|
---|
| 66 | {}
|
---|
[1738] | 67 |
|
---|
[1742] | 68 | /** creates pvs and initializes it with the given entries.
|
---|
[2529] | 69 | Assumes that entries are sorted.
|
---|
[1742] | 70 | */
|
---|
[2116] | 71 | VerbosePvs(const vector<PvsEntry<T, S> > &samples);
|
---|
| 72 | virtual ~VerbosePvs() {};
|
---|
[492] | 73 |
|
---|
[1706] | 74 | /** Compresses PVS lossless or lossy.
|
---|
| 75 | */
|
---|
[2529] | 76 | int Compress() { return 0; }
|
---|
[2100] | 77 |
|
---|
[2529] | 78 | inline int GetSize() const { return (int)mEntries.size(); }
|
---|
[2100] | 79 |
|
---|
[2529] | 80 | inline bool Empty() const { return mEntries.empty(); }
|
---|
[469] | 81 |
|
---|
[2529] | 82 | inline void Reserve(const int n) { mEntries.reserve(n); }
|
---|
[1740] | 83 | /** Normalize the visibility of entries in order to get
|
---|
[2529] | 84 | comparable results.
|
---|
[1706] | 85 | */
|
---|
| 86 | void NormalizeMaximum();
|
---|
| 87 | /** Merges pvs of a into this pvs.
|
---|
[2529] | 88 | Warning: very slow!
|
---|
[1706] | 89 | */
|
---|
[2116] | 90 | void MergeInPlace(const VerbosePvs<T, S> &a);
|
---|
[1706] | 91 | /** Difference of pvs to pvs b.
|
---|
[2100] | 92 | @returns number of different entries.
|
---|
[1706] | 93 | */
|
---|
[2116] | 94 | int Diff(const VerbosePvs<T, S> &b);
|
---|
[1706] | 95 | /** Finds sample in PVS.
|
---|
[1789] | 96 | @param checkDirty if dirty part of the pvs should be checked for entry
|
---|
[2100] | 97 | (warning: linear runtime in dirty part)
|
---|
[2066] | 98 | @returns iterator on the sample if found, else the place where
|
---|
[2100] | 99 | it would be added in the sorted vector.
|
---|
[1706] | 100 | */
|
---|
[1790] | 101 | bool Find(T sample,
|
---|
| 102 | typename vector<PvsEntry<T, S> >::iterator &it,
|
---|
| 103 | const bool checkDirty = true);
|
---|
[469] | 104 |
|
---|
[1706] | 105 | bool GetSampleContribution(T sample, const float pdf, float &contribution);
|
---|
| 106 | /** Adds sample to PVS.
|
---|
| 107 | @returns contribution of sample (0 or 1)
|
---|
| 108 | */
|
---|
| 109 | float AddSample(T sample, const float pdf);
|
---|
[1789] | 110 | /** Adds sample to PVS without checking for presence of the sample
|
---|
[2066] | 111 | warning: pvs remains unsorted!
|
---|
[1789] | 112 | */
|
---|
| 113 | void AddSampleDirty(T sample, const float pdf);
|
---|
| 114 | /** Adds sample dirty (on the end of the vector) but
|
---|
| 115 | first checks if sample is already in clean part of the pvs.
|
---|
| 116 | */
|
---|
[2116] | 117 | bool AddSampleDirtyCheck(T sample, const float pdf);
|
---|
[2529] | 118 | /** Sort pvs entries. This should always be called after a
|
---|
[1789] | 119 | sequence of AddSampleDirty calls
|
---|
| 120 | */
|
---|
| 121 | void Sort();
|
---|
[2100] | 122 | /** Sort pvs entries assume that the pvs contains unique entries
|
---|
[1740] | 123 | */
|
---|
[2100] | 124 | void SimpleSort();
|
---|
[1706] | 125 | /** Adds sample to PVS.
|
---|
| 126 | @returns PvsData
|
---|
| 127 | */
|
---|
[2116] | 128 | typename std::vector<PvsEntry<T, S> >::iterator
|
---|
| 129 | AddSample2(T sample, const float pdf);
|
---|
[1706] | 130 | /** Subtracts one pvs from another one.
|
---|
| 131 | WARNING: could contains bugs
|
---|
| 132 | @returns new pvs size
|
---|
| 133 | */
|
---|
[2116] | 134 | int SubtractPvs(const VerbosePvs<T, S> &pvs);
|
---|
[1740] | 135 |
|
---|
[1706] | 136 | /** Returns PVS data, i.e., how often it was seen from the view cell,
|
---|
| 137 | and the object itsef.
|
---|
| 138 | */
|
---|
| 139 | void GetData(const int index, T &entry, S &data);
|
---|
| 140 |
|
---|
| 141 | /** Collects the PVS entries and returns them in the vector.
|
---|
| 142 | */
|
---|
| 143 | void CollectEntries(std::vector<T> &entries);
|
---|
| 144 |
|
---|
| 145 | /** Removes sample from PVS if reference count is zero.
|
---|
[2100] | 146 | @param visibleSamples number of references to be removed
|
---|
[1706] | 147 | */
|
---|
| 148 | bool RemoveSample(T sample, const float pdf);
|
---|
| 149 |
|
---|
| 150 | /** Compute continuous PVS difference
|
---|
| 151 | */
|
---|
[2116] | 152 | void ComputeContinuousPvsDifference(VerbosePvs<T, S> &pvs,
|
---|
[1740] | 153 | float &pvsReduction,
|
---|
| 154 | float &pvsEnlargement);
|
---|
[1706] | 155 |
|
---|
| 156 | /** Clears the pvs.
|
---|
| 157 | */
|
---|
[1750] | 158 | void Clear(const bool trim = true);
|
---|
[2529] | 159 | /** Trim the vector containing the pvs.
|
---|
| 160 | */
|
---|
[1750] | 161 | void Trim();
|
---|
| 162 |
|
---|
[1706] | 163 | static int GetEntrySizeByte();
|
---|
| 164 | static float GetEntrySize();
|
---|
| 165 |
|
---|
[1740] | 166 | /** Compute continuous PVS difference
|
---|
| 167 | */
|
---|
[2116] | 168 | float GetPvsHomogenity(VerbosePvs<T, S> &pvs);
|
---|
[1706] | 169 |
|
---|
[2116] | 170 | static void Merge(VerbosePvs<T, S> &mergedPvs,
|
---|
| 171 | const VerbosePvs<T, S> &a,
|
---|
| 172 | const VerbosePvs<T, S> &b);
|
---|
[1706] | 173 |
|
---|
[2529] | 174 | inline int GetSamples() const { return mSamples; }
|
---|
[1738] | 175 |
|
---|
[2529] | 176 | /** If there is an unsorted part in the pvs.
|
---|
| 177 | */
|
---|
| 178 | bool IsDirty() const { return mLastSorted < mEntries.size(); }
|
---|
[1789] | 179 |
|
---|
[2529] | 180 | /** If this pvs requires a resort to stay efficient.
|
---|
| 181 | */
|
---|
[1789] | 182 | bool RequiresResort() const
|
---|
| 183 | {
|
---|
[2100] | 184 | // the last part should not be more than log of the sorted part. this
|
---|
| 185 | // way we can achieve logarithmic behaviour for insertion and find
|
---|
| 186 | const int n = mEntries.size();
|
---|
| 187 | const int dirtySize = n - mLastSorted;
|
---|
[2019] | 188 |
|
---|
[2116] | 189 | const double LOG2E = 1.442695040f;
|
---|
[2100] | 190 |
|
---|
| 191 | const float logN = log((float)max(1, n))/LOG2E;
|
---|
| 192 | const float logS = log((float)max(1, mLastSorted))/LOG2E;
|
---|
| 193 | const float logD = log((float)max(1, dirtySize))/LOG2E;
|
---|
| 194 |
|
---|
| 195 | if (8*(n + 2*dirtySize*logD) <
|
---|
| 196 | mQueriesSinceSort*((mLastSorted*logS + dirtySize*dirtySize/2)/n - logN))
|
---|
| 197 | {
|
---|
[2529] | 198 | // cout<<"Q="<<mQueriesSinceSort<<" N="<<n<<" D="<<dirtySize<<endl;
|
---|
[2100] | 199 | return true;
|
---|
| 200 | }
|
---|
| 201 |
|
---|
| 202 | return false;
|
---|
[1789] | 203 | }
|
---|
| 204 |
|
---|
[2529] | 205 | /** If this pvs requires a resort to stay efficient.
|
---|
| 206 | */
|
---|
[2100] | 207 | bool RequiresResortLog() const
|
---|
| 208 | {
|
---|
| 209 | // the last part should not be more than log of the sorted part. this
|
---|
| 210 | // way we can achieve logarithmic behaviour for insertion and find
|
---|
| 211 | const int dirtySize = (int)mEntries.size() - mLastSorted;
|
---|
| 212 | return dirtySize > 4 * (int)(log((double)mEntries.size()) / log(2.0));
|
---|
| 213 | }
|
---|
| 214 |
|
---|
[2529] | 215 | inline int GetLastSorted() const { return mLastSorted; }
|
---|
[1789] | 216 |
|
---|
[1742] | 217 | typename PvsIterator<T, S> GetIterator() const;
|
---|
| 218 |
|
---|
[2570] | 219 | VerbosePvsStats mStats;
|
---|
| 220 |
|
---|
[1742] | 221 | protected:
|
---|
| 222 |
|
---|
[2529] | 223 | /** Merge pvs 1 from begin iterator to end iterator with
|
---|
| 224 | pvs 2 from begin iterator to end iterator.
|
---|
| 225 | */
|
---|
[2116] | 226 | static void Merge(VerbosePvs<T, S> &mergedPvs,
|
---|
[2100] | 227 | const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
|
---|
| 228 | const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
|
---|
| 229 | const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
|
---|
| 230 | const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
|
---|
| 231 | const int aSamples,
|
---|
| 232 | const int bSamples);
|
---|
| 233 |
|
---|
[2529] | 234 |
|
---|
[2116] | 235 | //////////////////////////////
|
---|
| 236 |
|
---|
[1738] | 237 | /// vector of PVS entries
|
---|
[1740] | 238 | vector<PvsEntry<T, S> > mEntries;
|
---|
[2100] | 239 |
|
---|
[1736] | 240 | /// Number of samples used to create the PVS
|
---|
| 241 | int mSamples;
|
---|
[2100] | 242 |
|
---|
[1789] | 243 | /// Last sorted entry in the pvs (important for find and merge)
|
---|
[2019] | 244 | int mLastSorted;
|
---|
| 245 |
|
---|
[2100] | 246 | int mQueriesSinceSort;
|
---|
[310] | 247 | };
|
---|
| 248 |
|
---|
[581] | 249 |
|
---|
[1740] | 250 | template <typename T, typename S>
|
---|
[2570] | 251 | VerbosePvs<T, S>::VerbosePvs(const vector<PvsEntry<T, S> > &samples):
|
---|
| 252 | mLastSorted(0)
|
---|
[1740] | 253 | {
|
---|
| 254 | mEntries.reserve(samples.size());
|
---|
| 255 | mEntries = samples;
|
---|
[1789] | 256 | mSamples = samples.size();
|
---|
[1740] | 257 | }
|
---|
[677] | 258 |
|
---|
[1789] | 259 |
|
---|
[1757] | 260 | template <typename T, typename S>
|
---|
[2116] | 261 | void VerbosePvs<T, S>::Sort()
|
---|
[1757] | 262 | {
|
---|
[2116] | 263 | vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
|
---|
| 264 | vector<PvsEntry<T, S> >::iterator it_end = mEntries.end();
|
---|
[1789] | 265 |
|
---|
| 266 | // throw out double entries
|
---|
| 267 | std::vector<PvsEntry<T, S> >::iterator newEnd = unique(it, it_end);
|
---|
| 268 | sort(it, newEnd);
|
---|
[2019] | 269 |
|
---|
[1789] | 270 | // now merge sorted ranges
|
---|
| 271 | ObjectPvs newPvs;
|
---|
| 272 | Merge(newPvs,
|
---|
[2019] | 273 | mEntries.begin(),
|
---|
| 274 | it,
|
---|
| 275 | it,
|
---|
| 276 | newEnd,
|
---|
| 277 | mSamples,
|
---|
| 278 | 0);
|
---|
[1789] | 279 |
|
---|
| 280 | mEntries = newPvs.mEntries;
|
---|
| 281 | mLastSorted = (int)mEntries.size();
|
---|
[2019] | 282 | mQueriesSinceSort = 0;
|
---|
[1757] | 283 | }
|
---|
[1740] | 284 |
|
---|
[1877] | 285 | template <typename T, typename S>
|
---|
[2116] | 286 | void VerbosePvs<T, S>::SimpleSort()
|
---|
[1877] | 287 | {
|
---|
[2066] | 288 | // sort(mEntries.begin(), mEntries.end());
|
---|
[2116] | 289 | vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
|
---|
[2066] | 290 |
|
---|
| 291 | sort(it, mEntries.end());
|
---|
| 292 | inplace_merge(mEntries.begin(), it, mEntries.end());
|
---|
[2019] | 293 |
|
---|
[2066] | 294 | mLastSorted = (int)mEntries.size();
|
---|
| 295 | mQueriesSinceSort = 0;
|
---|
[1877] | 296 | }
|
---|
[1789] | 297 |
|
---|
[1877] | 298 |
|
---|
[695] | 299 | /**
|
---|
| 300 | Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
|
---|
| 301 | Provides separatelly PVS reduction from PVS enlargement.
|
---|
| 302 |
|
---|
| 303 | */
|
---|
[1189] | 304 | template <typename T, typename S>
|
---|
[677] | 305 | void
|
---|
[2116] | 306 | VerbosePvs<T, S>::ComputeContinuousPvsDifference(VerbosePvs<T, S> &b,
|
---|
[1740] | 307 | float &pvsReduction,
|
---|
| 308 | float &pvsEnlargement)
|
---|
[677] | 309 | {
|
---|
[705] | 310 | pvsReduction = 0.0f;
|
---|
| 311 | pvsEnlargement = 0.0f;
|
---|
[1740] | 312 |
|
---|
[1738] | 313 | // Uses sum of log differences, which corresponds to entropy
|
---|
[2116] | 314 | vector<PvsEntry<T, S> >::iterator it;
|
---|
[1738] | 315 |
|
---|
| 316 | for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
|
---|
[1189] | 317 | {
|
---|
[1740] | 318 | float bSumPdf = (*it).mData.mSumPdf;
|
---|
[1738] | 319 | float aSumPdf = 0.0f;
|
---|
[713] | 320 |
|
---|
[1790] | 321 | vector<PvsEntry<T, S> >::iterator oit;
|
---|
| 322 | const bool entryFound = Find((*it).mObject, oit);
|
---|
[1740] | 323 |
|
---|
| 324 | if (entryFound)
|
---|
[1738] | 325 | {
|
---|
[1740] | 326 | aSumPdf = (*it).mData.mSumPdf;
|
---|
| 327 |
|
---|
[1738] | 328 | // mark this entry as processed to avoid double counting
|
---|
[1740] | 329 | (*it).mData.mSumPdf = -aSumPdf;
|
---|
[1738] | 330 | }
|
---|
| 331 |
|
---|
[713] | 332 | #if 0
|
---|
[1740] | 333 | const float diff = bSumPdf - aSumPdf;
|
---|
[1738] | 334 |
|
---|
[2100] | 335 | if (diff > 0.0f)
|
---|
| 336 | {
|
---|
[1738] | 337 | pvsEnlargement += diff;
|
---|
[2100] | 338 | }
|
---|
| 339 | else
|
---|
| 340 | {
|
---|
[1738] | 341 | pvsReduction += -diff;
|
---|
| 342 | }
|
---|
[713] | 343 | #else
|
---|
[1740] | 344 | if (!entryFound)
|
---|
[2100] | 345 | {
|
---|
[1738] | 346 | pvsEnlargement += 1.0f;
|
---|
[2100] | 347 | }
|
---|
[713] | 348 | #endif
|
---|
[1738] | 349 | }
|
---|
| 350 |
|
---|
[1740] | 351 | for (it = mEntries.begin(); it != mEntries.end(); ++ it)
|
---|
| 352 | {
|
---|
| 353 | float aSumPdf = (*it).mData.mSumPdf;
|
---|
[1738] | 354 | float bSumPdf = 0.0f;
|
---|
[2100] | 355 | if (aSumPdf < 0.0f)
|
---|
| 356 | {
|
---|
[1738] | 357 | // this entry was already accounted for!
|
---|
| 358 | // just revert it back
|
---|
[1740] | 359 | (*it).mData.mSumPdf = -aSumPdf;
|
---|
[2100] | 360 | }
|
---|
| 361 | else
|
---|
| 362 | {
|
---|
[1790] | 363 | vector<PvsEntry<T, S> >::iterator oit;
|
---|
| 364 |
|
---|
| 365 | const bool entryFound = b.Find((*it).mObject, oit);
|
---|
| 366 |
|
---|
[1740] | 367 | if (entryFound) {
|
---|
| 368 | bSumPdf = (*oit).mData.mSumPdf;
|
---|
[1738] | 369 | }
|
---|
[713] | 370 | #if 0
|
---|
[1740] | 371 | const float diff = bSumPdf - aSumPdf;
|
---|
[713] | 372 |
|
---|
[1738] | 373 | if (diff > 0.0f) {
|
---|
| 374 | pvsEnlargement += diff;
|
---|
| 375 | } else {
|
---|
| 376 | pvsReduction += -diff;
|
---|
| 377 | }
|
---|
| 378 |
|
---|
[713] | 379 | #else
|
---|
[1740] | 380 | if (!entryFound)
|
---|
[1738] | 381 | pvsReduction += 1.0f;
|
---|
[713] | 382 | #endif
|
---|
[1738] | 383 | }
|
---|
[695] | 384 | }
|
---|
[677] | 385 | }
|
---|
| 386 |
|
---|
[1738] | 387 |
|
---|
[1189] | 388 | template <typename T, typename S>
|
---|
[2116] | 389 | int VerbosePvs<T, S>::Diff(const VerbosePvs<T, S> &b)
|
---|
[362] | 390 | {
|
---|
| 391 | int dif = 0;
|
---|
| 392 |
|
---|
[1740] | 393 | std::vector<PvsEntry<T, S> >::const_iterator it;
|
---|
[362] | 394 |
|
---|
| 395 | for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
|
---|
| 396 | {
|
---|
[1790] | 397 | vector<PvsEntry<T, S> >::iterator bit;
|
---|
| 398 | const bool entryFound = Find((*it).first, bit);
|
---|
| 399 |
|
---|
| 400 | if (!entryFound) ++ dif;
|
---|
[362] | 401 | }
|
---|
| 402 |
|
---|
| 403 | return dif;
|
---|
| 404 | }
|
---|
| 405 |
|
---|
[1740] | 406 |
|
---|
| 407 | template <typename T, typename S>
|
---|
[2116] | 408 | void VerbosePvs<T, S>::MergeInPlace(const VerbosePvs<T, S> &a)
|
---|
[341] | 409 | {
|
---|
[1786] | 410 | // early exit
|
---|
| 411 | if (a.Empty())
|
---|
| 412 | {
|
---|
| 413 | return;
|
---|
| 414 | }
|
---|
| 415 | else if (Empty())
|
---|
| 416 | {
|
---|
| 417 | mEntries.reserve(a.GetSize());
|
---|
| 418 | mEntries = a.mEntries;
|
---|
| 419 | mSamples = a.mSamples;
|
---|
| 420 | return;
|
---|
| 421 | }
|
---|
| 422 |
|
---|
[1740] | 423 | ObjectPvs interPvs;
|
---|
| 424 |
|
---|
| 425 | Merge(interPvs, *this, a);
|
---|
| 426 |
|
---|
| 427 | mEntries.reserve(interPvs.GetSize());
|
---|
| 428 | mEntries = interPvs.mEntries;
|
---|
[1751] | 429 | mSamples = interPvs.mSamples;
|
---|
[1740] | 430 | }
|
---|
| 431 |
|
---|
| 432 |
|
---|
| 433 | template <typename T, typename S>
|
---|
[2116] | 434 | void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs,
|
---|
| 435 | const VerbosePvs<T, S> &a,
|
---|
| 436 | const VerbosePvs<T, S> &b)
|
---|
[1740] | 437 | {
|
---|
[2116] | 438 | std::vector<PvsEntry<T, S> >::const_iterator ait =
|
---|
| 439 | a.mEntries.begin(), ait_end = a.mEntries.end();
|
---|
| 440 | std::vector<PvsEntry<T, S> >::const_iterator bit =
|
---|
| 441 | b.mEntries.begin(), bit_end = b.mEntries.end();
|
---|
[1741] | 442 |
|
---|
[1789] | 443 | Merge(mergedPvs,
|
---|
| 444 | ait, ait_end,
|
---|
| 445 | bit, bit_end,
|
---|
| 446 | a.mSamples,
|
---|
| 447 | b.mSamples);
|
---|
| 448 | }
|
---|
| 449 |
|
---|
| 450 |
|
---|
| 451 | template <typename T, typename S>
|
---|
[2116] | 452 | void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs,
|
---|
[1789] | 453 | const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
|
---|
| 454 | const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
|
---|
| 455 | const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
|
---|
| 456 | const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
|
---|
| 457 | const int aSamples,
|
---|
| 458 | const int bSamples)
|
---|
| 459 | {
|
---|
| 460 | std::vector<PvsEntry<T, S> >::const_iterator ait = aBegin;
|
---|
| 461 | std::vector<PvsEntry<T, S> >::const_iterator bit = bBegin;
|
---|
| 462 |
|
---|
| 463 | for (; (ait != aEnd); ++ ait)
|
---|
[1741] | 464 | {
|
---|
| 465 | Intersectable *aObj = (*ait).mObject;
|
---|
| 466 | Intersectable *bObj = NULL;
|
---|
[1789] | 467 | //Intersectable *bObjOld = NULL;
|
---|
| 468 |
|
---|
| 469 | const PvsEntry<T, S> &aEntry = (*ait);
|
---|
[1740] | 470 |
|
---|
[1789] | 471 | for (; (bit != bEnd) && ((*bit).mObject <= (*ait).mObject); ++ bit)
|
---|
[1741] | 472 | {
|
---|
| 473 | bObj = (*bit).mObject;
|
---|
| 474 |
|
---|
| 475 | // object found => add up probabilities
|
---|
[1742] | 476 | if (bObj == aEntry.mObject)
|
---|
[1741] | 477 | {
|
---|
| 478 | PvsData newData(aEntry.mData.mSumPdf + (*bit).mData.mSumPdf);
|
---|
| 479 | PvsEntry<T, S> entry(bObj, newData);
|
---|
| 480 | mergedPvs.mEntries.push_back(entry);
|
---|
| 481 | }
|
---|
| 482 | else
|
---|
| 483 | {
|
---|
| 484 | mergedPvs.mEntries.push_back(*bit);
|
---|
| 485 | }
|
---|
| 486 | }
|
---|
| 487 |
|
---|
| 488 | // only push back if objects different
|
---|
| 489 | // (equal case is handled by second loop)
|
---|
| 490 | if (aObj != bObj)
|
---|
| 491 | {
|
---|
| 492 | mergedPvs.mEntries.push_back(*ait);
|
---|
| 493 | }
|
---|
| 494 | }
|
---|
| 495 |
|
---|
| 496 | // add the rest
|
---|
[1789] | 497 | for (; (bit != bEnd); ++ bit)
|
---|
[1740] | 498 | {
|
---|
[1741] | 499 | mergedPvs.mEntries.push_back(*bit);
|
---|
| 500 | }
|
---|
[1789] | 501 |
|
---|
| 502 | mergedPvs.mSamples = aSamples + bSamples;
|
---|
[1740] | 503 | }
|
---|
| 504 |
|
---|
| 505 |
|
---|
[2199] | 506 | template <typename T, typename S> void VerbosePvs<T, S>::Clear(const bool trim)
|
---|
[752] | 507 | {
|
---|
| 508 | mEntries.clear();
|
---|
[1750] | 509 | mSamples = 0;
|
---|
[1789] | 510 | mLastSorted = 0;
|
---|
[1786] | 511 |
|
---|
| 512 | if (trim)
|
---|
| 513 | {
|
---|
| 514 | vector<PvsEntry<T,S> >().swap(mEntries);
|
---|
| 515 | }
|
---|
[752] | 516 | }
|
---|
| 517 |
|
---|
| 518 |
|
---|
[2116] | 519 | template <typename T, typename S> void VerbosePvs<T, S>::Trim()
|
---|
[1750] | 520 | {
|
---|
[1786] | 521 | vector<PvsEntry<T,S> >(mEntries).swap(mEntries);
|
---|
[1750] | 522 | }
|
---|
| 523 |
|
---|
| 524 |
|
---|
[1189] | 525 | template <typename T, typename S>
|
---|
[2116] | 526 | bool VerbosePvs<T, S>::Find(T sample,
|
---|
[1790] | 527 | typename vector<PvsEntry<T, S> >::iterator &it,
|
---|
| 528 | const bool checkDirty)
|
---|
[310] | 529 | {
|
---|
[2066] | 530 | bool found = false;
|
---|
[2077] | 531 |
|
---|
[2066] | 532 | PvsEntry<T, S> dummy(sample, PvsData());
|
---|
| 533 |
|
---|
| 534 | // only check clean part
|
---|
| 535 | vector<PvsEntry<T, S> >::iterator sorted_end = mEntries.begin() + mLastSorted;
|
---|
[2077] | 536 | mQueriesSinceSort++;
|
---|
[2066] | 537 |
|
---|
| 538 | // binary search
|
---|
| 539 | it = lower_bound(mEntries.begin(), sorted_end, dummy);
|
---|
| 540 |
|
---|
| 541 | if ((it != mEntries.end()) && ((*it).mObject == sample))
|
---|
| 542 | found = true;
|
---|
| 543 |
|
---|
| 544 | // sample not found yet => search further in the unsorted part
|
---|
| 545 | if (!found && checkDirty)
|
---|
| 546 | {
|
---|
| 547 | vector<PvsEntry<T, S> >::iterator dit, dit_end = mEntries.end();
|
---|
| 548 |
|
---|
| 549 | for (dit = sorted_end; (dit != dit_end) && ((*dit).mObject != sample); ++ dit);
|
---|
[1790] | 550 |
|
---|
[2066] | 551 | if (dit != dit_end)
|
---|
| 552 | {
|
---|
| 553 | found = true;
|
---|
| 554 | it = dit;
|
---|
| 555 | }
|
---|
| 556 | }
|
---|
| 557 |
|
---|
| 558 | return found;
|
---|
[310] | 559 | }
|
---|
| 560 |
|
---|
[1740] | 561 |
|
---|
[1189] | 562 | template <typename T, typename S>
|
---|
[2116] | 563 | void VerbosePvs<T, S>::GetData(const int index, T &entry, S &data)
|
---|
[310] | 564 | {
|
---|
[1740] | 565 | std::vector<PvsEntry<T, S> >::iterator i = mEntries.begin();
|
---|
[1738] | 566 | for (int k = 0; k != index && i != mEntries.end(); ++ i, ++ k);
|
---|
[310] | 567 |
|
---|
[1738] | 568 | entry = (*i).first;
|
---|
| 569 | data = (*i).second;
|
---|
[310] | 570 | }
|
---|
| 571 |
|
---|
[1738] | 572 |
|
---|
[1189] | 573 | template <typename T, typename S>
|
---|
[2116] | 574 | float VerbosePvs<T, S>::AddSample(T sample, const float pdf)
|
---|
[2071] | 575 | {
|
---|
[1738] | 576 | ++ mSamples;
|
---|
[1790] | 577 |
|
---|
| 578 | vector<PvsEntry<T, S> >::iterator it;
|
---|
| 579 | const bool entryFound = Find(sample, it);
|
---|
[1738] | 580 |
|
---|
[1790] | 581 | if (entryFound)
|
---|
| 582 | {
|
---|
[1740] | 583 | S &data = (*it).mData;
|
---|
| 584 | data.mSumPdf += pdf;
|
---|
| 585 | return data.mSumPdf;
|
---|
[1189] | 586 | }
|
---|
[1738] | 587 | else
|
---|
[2066] | 588 | {
|
---|
[1740] | 589 | PvsEntry<T, S> entry(sample, pdf);
|
---|
| 590 | mEntries.insert(it, entry);
|
---|
[1789] | 591 | ++ mLastSorted;
|
---|
[1738] | 592 | return pdf;
|
---|
[2066] | 593 | }
|
---|
[466] | 594 | }
|
---|
[177] | 595 |
|
---|
[1189] | 596 |
|
---|
| 597 | template <typename T, typename S>
|
---|
[2116] | 598 | void VerbosePvs<T, S>::AddSampleDirty(T sample, const float pdf)
|
---|
[1757] | 599 | {
|
---|
[1789] | 600 | ++ mSamples;
|
---|
| 601 | mEntries.push_back(PvsEntry<T, S>(sample, pdf));
|
---|
[1757] | 602 | }
|
---|
| 603 |
|
---|
| 604 |
|
---|
| 605 | template <typename T, typename S>
|
---|
[2548] | 606 | typename vector< PvsEntry<T, S> >::iterator
|
---|
| 607 | VerbosePvs<T, S>::AddSample2(T sample, const float pdf)
|
---|
[1184] | 608 | {
|
---|
[1740] | 609 | ++ mSamples;
|
---|
[1789] | 610 |
|
---|
[1790] | 611 | vector<PvsEntry<T, S> >::iterator it;
|
---|
[2066] | 612 | const bool entryFound = Find(sample, it);
|
---|
[1740] | 613 |
|
---|
[1790] | 614 | if (entryFound)
|
---|
[1189] | 615 | {
|
---|
[1740] | 616 | S &data = (*it).second;
|
---|
| 617 | data->mSumPdf += pdf;
|
---|
[1189] | 618 | }
|
---|
[1740] | 619 | else
|
---|
[1189] | 620 | {
|
---|
[1740] | 621 | PvsEntry<T, S> entry(sample, pdf);
|
---|
| 622 | mEntries.insert(it, entry);
|
---|
[1789] | 623 | ++ mLastSorted;
|
---|
[1189] | 624 | }
|
---|
[1740] | 625 |
|
---|
| 626 | return it;
|
---|
[1184] | 627 | }
|
---|
| 628 |
|
---|
[1740] | 629 |
|
---|
[1789] | 630 | template <typename T, typename S>
|
---|
[2530] | 631 | bool VerbosePvs<T, S>::AddSampleDirtyCheck(T sample, const float pdf)
|
---|
[1789] | 632 | {
|
---|
| 633 | ++ mSamples;
|
---|
| 634 |
|
---|
[1790] | 635 | vector<PvsEntry<T, S> >::iterator it;
|
---|
[2066] | 636 | const bool entryFound = Find(sample, it);
|
---|
[1789] | 637 |
|
---|
[2066] | 638 | if (entryFound)
|
---|
| 639 | {
|
---|
| 640 | S &data = (*it).mData;
|
---|
[1877] | 641 |
|
---|
[2066] | 642 | data.mSumPdf += pdf;
|
---|
| 643 | return false;
|
---|
[1789] | 644 | }
|
---|
[2066] | 645 | else
|
---|
| 646 | {
|
---|
| 647 | AddSampleDirty(sample, pdf);
|
---|
| 648 | return true;
|
---|
[1789] | 649 | }
|
---|
[311] | 650 | }
|
---|
[308] | 651 |
|
---|
[492] | 652 |
|
---|
[1189] | 653 | template <typename T, typename S>
|
---|
[2116] | 654 | bool VerbosePvs<T, S>::GetSampleContribution(T sample,
|
---|
[1740] | 655 | const float pdf,
|
---|
| 656 | float &contribution)
|
---|
[485] | 657 | {
|
---|
[1790] | 658 | vector<PvsEntry<T, S> >::iterator it;
|
---|
| 659 | const bool entryFound = Find(sample, it);
|
---|
[1189] | 660 |
|
---|
[1790] | 661 | if (entryFound)
|
---|
[1740] | 662 | {
|
---|
| 663 | S &data = (*it).mData;
|
---|
| 664 | contribution = pdf / (data.mSumPdf + pdf);
|
---|
| 665 | return false;
|
---|
| 666 | }
|
---|
| 667 | else
|
---|
| 668 | {
|
---|
| 669 | contribution = 1.0f;
|
---|
| 670 | return true;
|
---|
| 671 | }
|
---|
[485] | 672 | }
|
---|
| 673 |
|
---|
[1740] | 674 |
|
---|
[1189] | 675 | template <typename T, typename S>
|
---|
[2116] | 676 | bool VerbosePvs<T, S>::RemoveSample(T sample, const float pdf)
|
---|
[485] | 677 | {
|
---|
[1740] | 678 | -- mSamples;
|
---|
[1789] | 679 |
|
---|
[1790] | 680 | vector<PvsEntry<T, S> >::iterator it;
|
---|
| 681 | const bool entryFound = Find(sample, it);
|
---|
[1737] | 682 |
|
---|
[1790] | 683 | if (!entryFound)
|
---|
[1740] | 684 | return false;
|
---|
| 685 |
|
---|
| 686 | S &data = (*it).mData;
|
---|
| 687 |
|
---|
| 688 | data.mSumPdf -= pdf;
|
---|
| 689 |
|
---|
| 690 | if (data.mSumPdf <= 0.0f)
|
---|
| 691 | {
|
---|
| 692 | mEntries.erase(it);
|
---|
[1789] | 693 | -- mLastSorted; // wrong if sample was in tail!!
|
---|
[1740] | 694 | }
|
---|
| 695 |
|
---|
| 696 | return true;
|
---|
[485] | 697 | }
|
---|
[1740] | 698 |
|
---|
| 699 |
|
---|
[1189] | 700 | template <typename T, typename S>
|
---|
[2116] | 701 | int VerbosePvs<T, S>::SubtractPvs(const VerbosePvs<T, S> &pvs)
|
---|
[485] | 702 | {
|
---|
[1738] | 703 | const int samples = mSamples - pvs.mSamples;
|
---|
[1740] | 704 |
|
---|
| 705 | std::vector<PvsEntry<T, S> >::
|
---|
[1738] | 706 | const_iterator it, it_end = pvs.mEntries.end();
|
---|
[1737] | 707 |
|
---|
[1738] | 708 | // output PVS of view cell
|
---|
| 709 | for (it = pvs.mEntries.begin(); it != it_end; ++ it)
|
---|
[1740] | 710 | RemoveSample((*it).mObject, (*it).mData.mSumPdf);
|
---|
[1738] | 711 |
|
---|
| 712 | mSamples = samples;
|
---|
[1740] | 713 |
|
---|
[1738] | 714 | return GetSize();
|
---|
[485] | 715 | }
|
---|
| 716 |
|
---|
[1740] | 717 |
|
---|
[1189] | 718 | template <typename T, typename S>
|
---|
[2116] | 719 | void VerbosePvs<T, S>::CollectEntries(std::vector<T> &entries)
|
---|
[469] | 720 | {
|
---|
[1740] | 721 | std::vector<PvsEntry<T, S> >::
|
---|
[485] | 722 | const_iterator it, it_end = mEntries.end();
|
---|
[469] | 723 |
|
---|
| 724 | // output PVS of view cell
|
---|
| 725 | for (it = mEntries.begin(); it != it_end; ++ it)
|
---|
| 726 | entries.push_back((*it)->first);
|
---|
| 727 | }
|
---|
| 728 |
|
---|
[1740] | 729 |
|
---|
[1189] | 730 | template <typename T, typename S>
|
---|
[2116] | 731 | void VerbosePvs<T, S>::NormalizeMaximum()
|
---|
[556] | 732 | {
|
---|
[1740] | 733 | std::vector<PvsEntry<T, S> >::
|
---|
| 734 | const_iterator it, it_end = mEntries.end();
|
---|
[556] | 735 |
|
---|
[1740] | 736 | float maxPdfSum = -1.0f;
|
---|
[556] | 737 |
|
---|
[1740] | 738 | // output PVS of view cell
|
---|
| 739 | for (it = mEntries.begin(); it != it_end; ++ it) {
|
---|
| 740 | float sum = (*it)->second.sumPdf;
|
---|
| 741 | if (sum > maxSum)
|
---|
| 742 | maxSum = sum;
|
---|
| 743 | }
|
---|
[556] | 744 |
|
---|
[1740] | 745 | maxSum = 1.0f / maxSum;
|
---|
[556] | 746 |
|
---|
[1740] | 747 | for (it = mEntries.begin(); it != it_end; ++ it) {
|
---|
| 748 | (*it)->second.sumPdf *= maxSum;
|
---|
| 749 | }
|
---|
[556] | 750 | }
|
---|
| 751 |
|
---|
| 752 |
|
---|
[1667] | 753 | template <typename T, typename S>
|
---|
[2116] | 754 | float VerbosePvs<T, S>::GetEntrySize()
|
---|
[1667] | 755 | {
|
---|
[1673] | 756 | return (float)(sizeof(T) + sizeof(S)) / float(1024 * 1024);
|
---|
[1667] | 757 | }
|
---|
| 758 |
|
---|
| 759 |
|
---|
| 760 | template <typename T, typename S>
|
---|
[2116] | 761 | int VerbosePvs<T, S>::GetEntrySizeByte()
|
---|
[1667] | 762 | {
|
---|
| 763 | return sizeof(T) + sizeof(S);
|
---|
| 764 | }
|
---|
| 765 |
|
---|
| 766 |
|
---|
[1740] | 767 | template <typename T, typename S>
|
---|
[2116] | 768 | float VerbosePvs<T, S>::GetPvsHomogenity(VerbosePvs<T, S> &pvs)
|
---|
[1740] | 769 | {
|
---|
| 770 | float pvsReduction, pvsEnlargement;
|
---|
| 771 |
|
---|
| 772 | ComputeContinuousPvsDifference(pvs, pvsReduction, pvsEnlargement);
|
---|
| 773 | return pvsReduction + pvsEnlargement;
|
---|
| 774 | }
|
---|
| 775 |
|
---|
| 776 |
|
---|
[1742] | 777 | template <typename T, typename S>
|
---|
[2116] | 778 | typename PvsIterator<T, S> VerbosePvs<T, S>::GetIterator() const
|
---|
[1742] | 779 | {
|
---|
| 780 | PvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
|
---|
| 781 | return pit;
|
---|
| 782 | }
|
---|
| 783 |
|
---|
[860] | 784 | }
|
---|
[469] | 785 |
|
---|
[177] | 786 | #endif
|
---|
| 787 |
|
---|