[2116] | 1 | #ifndef __BITVECTORPVS_H
|
---|
| 2 | #define __BITVECTORPVS_H
|
---|
| 3 |
|
---|
| 4 | #include <vector>
|
---|
| 5 | #include "common.h"
|
---|
| 6 | #include "PvsBase.h"
|
---|
| 7 |
|
---|
| 8 |
|
---|
| 9 | namespace GtpVisibilityPreprocessor {
|
---|
| 10 |
|
---|
| 11 | // specialisation of vector<bool>
|
---|
| 12 | typedef vector<bool> bit_vector;
|
---|
| 13 |
|
---|
[2117] | 14 |
|
---|
[2116] | 15 | /** Iterator over a bitvector pvs.
|
---|
| 16 | */
|
---|
| 17 | template<typename T, typename S>
|
---|
| 18 | class BitVectorPvsIterator
|
---|
| 19 | {
|
---|
| 20 | public:
|
---|
| 21 |
|
---|
[2117] | 22 | BitVectorPvsIterator<T, S>(const typename bit_vector::const_iterator &itBegin,
|
---|
| 23 | const typename bit_vector::const_iterator &itEnd
|
---|
| 24 | //,const int lastElement
|
---|
| 25 | ):
|
---|
| 26 | mItCurrent(itBegin), mItEnd(itEnd), mDistance(0)//, mLastElement
|
---|
[2116] | 27 | {
|
---|
| 28 | }
|
---|
| 29 |
|
---|
| 30 | bool HasMoreEntries() const
|
---|
| 31 | {
|
---|
[2117] | 32 | // find next element in bit vector
|
---|
| 33 | // warning: has to do traversal each time
|
---|
| 34 | typename bit_vector::const_iterator itNext = mItCurrent;
|
---|
| 35 |
|
---|
| 36 | for (;(itNext != mItEnd) && !(*itNext); ++ itNext);
|
---|
| 37 |
|
---|
| 38 | return (itNext != mItEnd);
|
---|
[2116] | 39 | }
|
---|
| 40 |
|
---|
[2117] | 41 | T Next(S &pdf)
|
---|
[2116] | 42 | {
|
---|
[2117] | 43 | return Next();
|
---|
| 44 | }
|
---|
| 45 |
|
---|
| 46 | T Next()
|
---|
| 47 | {
|
---|
[2116] | 48 | // hack: create new pvs entry
|
---|
[2117] | 49 | for (; !(*mItCurrent); ++ mItCurrent, ++ mDistance);
|
---|
| 50 |
|
---|
| 51 | T sample = sObjects[mDistance];
|
---|
| 52 |
|
---|
| 53 | ++ mDistance;
|
---|
| 54 | ++ mItCurrent;
|
---|
| 55 |
|
---|
| 56 | return sample;
|
---|
[2116] | 57 | }
|
---|
[2117] | 58 |
|
---|
[2116] | 59 |
|
---|
[2117] | 60 | // vector of objects corresponding to pvs entries
|
---|
| 61 | static vector<T> sObjects;
|
---|
| 62 |
|
---|
[2116] | 63 | private:
|
---|
[2117] | 64 |
|
---|
| 65 | typename bit_vector::const_iterator mItCurrent;
|
---|
| 66 | //typename bit_vector::const_iterator mItNext;
|
---|
| 67 | typename bit_vector::const_iterator mItEnd;
|
---|
| 68 |
|
---|
| 69 | // note: store distance explicitly because I
|
---|
| 70 | // don't know how efficient
|
---|
| 71 | // std::distance is on specialisation of vector<bool>
|
---|
| 72 | int mDistance;
|
---|
[2116] | 73 | };
|
---|
| 74 |
|
---|
[2117] | 75 |
|
---|
[2116] | 76 | /** Pvs implemented as bitvector
|
---|
| 77 | */
|
---|
| 78 | template<typename T, typename S>
|
---|
| 79 | class BitVectorPvs//: public PvsBase<T>
|
---|
| 80 | {
|
---|
| 81 | template<typename T, typename S> friend class BitVectorPvsIterator;
|
---|
| 82 |
|
---|
| 83 | public:
|
---|
| 84 |
|
---|
[2117] | 85 | BitVectorPvs();
|
---|
[2116] | 86 | //virtual ~HashPvs() {};
|
---|
| 87 |
|
---|
| 88 | int GetSize() const;
|
---|
| 89 | bool Empty() const;
|
---|
| 90 |
|
---|
| 91 | /** Adds sample to PVS.
|
---|
| 92 | @returns contribution of sample (0 or 1)
|
---|
| 93 | */
|
---|
| 94 | float AddSample(T sample, const float pdf);
|
---|
| 95 |
|
---|
| 96 | /** Adds sample to PVS without checking for presence of the sample
|
---|
| 97 | warning: pvs remains unsorted!
|
---|
| 98 | */
|
---|
| 99 | void AddSampleDirty(T sample, const float pdf);
|
---|
| 100 |
|
---|
| 101 | /** Adds sample dirty (on the end of the vector) but
|
---|
| 102 | first checks if sample is already in clean part of the pvs.
|
---|
| 103 | */
|
---|
| 104 | bool AddSampleDirtyCheck(T sample, const float pdf);
|
---|
| 105 |
|
---|
| 106 | /** Sort pvs entries - this should always be called after a
|
---|
| 107 | sequence of AddSampleDirty calls
|
---|
| 108 | */
|
---|
| 109 | void Sort();
|
---|
| 110 |
|
---|
| 111 | /** Clears the pvs.
|
---|
| 112 | */
|
---|
| 113 | void Clear(const bool trim = true);
|
---|
| 114 |
|
---|
| 115 | bool IsDirty() const;
|
---|
| 116 |
|
---|
| 117 | bool RequiresResort() const;
|
---|
| 118 |
|
---|
| 119 | /** Finds sample in PVS.
|
---|
| 120 | */
|
---|
[2117] | 121 | bool Find(T sample);
|
---|
[2116] | 122 |
|
---|
[2117] | 123 | typename BitVectorPvsIterator<T, S> GetIterator() const;
|
---|
[2116] | 124 |
|
---|
| 125 | /** Compute continuous PVS difference
|
---|
| 126 | */
|
---|
[2117] | 127 | float GetPvsHomogenity(BitVectorPvs<T, S> &pvs);
|
---|
[2116] | 128 |
|
---|
[2117] | 129 | static void Merge(BitVectorPvs<T, S> &mergedPvs,
|
---|
| 130 | const BitVectorPvs<T, S> &a,
|
---|
| 131 | const BitVectorPvs<T, S> &b);
|
---|
[2116] | 132 |
|
---|
| 133 | static int GetEntrySizeByte();
|
---|
| 134 | static float GetEntrySize();
|
---|
| 135 |
|
---|
| 136 | bool GetSampleContribution(T sample,
|
---|
| 137 | const float pdf,
|
---|
| 138 | float &contribution);
|
---|
| 139 |
|
---|
| 140 | int GetSamples() const
|
---|
| 141 | {
|
---|
| 142 | return mSamples;
|
---|
| 143 | }
|
---|
| 144 |
|
---|
[2117] | 145 | void MergeInPlace(const BitVectorPvs<T, S> &a)
|
---|
[2116] | 146 | {
|
---|
[2206] | 147 | cerr << "bitvector: merge in place not implemented yet" << endl;
|
---|
[2116] | 148 | }
|
---|
| 149 |
|
---|
| 150 | bool RequiresResortLog() const
|
---|
| 151 | {
|
---|
| 152 | return false;
|
---|
| 153 | }
|
---|
| 154 |
|
---|
| 155 | void Reserve(const int n)
|
---|
| 156 | {
|
---|
[2117] | 157 | mEntries.reserve(n);
|
---|
[2116] | 158 | }
|
---|
| 159 |
|
---|
| 160 | /** Sort pvs entries assume that the pvs contains unique entries
|
---|
| 161 | */
|
---|
| 162 | void SimpleSort()
|
---|
| 163 | {
|
---|
| 164 | // not necessary
|
---|
| 165 | }
|
---|
| 166 |
|
---|
[2117] | 167 | int SubtractPvs(const BitVectorPvs<T, S> &pvs)
|
---|
[2116] | 168 | {
|
---|
| 169 | cerr << "not yet implemented" << endl;
|
---|
| 170 | return 0;
|
---|
| 171 | }
|
---|
| 172 |
|
---|
| 173 | /** Compute continuous PVS difference
|
---|
| 174 | */
|
---|
[2117] | 175 | void ComputeContinuousPvsDifference(BitVectorPvs<T, S> &pvs,
|
---|
[2116] | 176 | float &pvsReduction,
|
---|
| 177 | float &pvsEnlargement)
|
---|
| 178 | {
|
---|
| 179 | cerr << "not yet implemented" << endl;
|
---|
| 180 | }
|
---|
[2117] | 181 |
|
---|
| 182 |
|
---|
| 183 | static void SetPvsSize(const int pvsSize) { sPvsSize = pvsSize; };
|
---|
| 184 |
|
---|
[2116] | 185 | protected:
|
---|
| 186 |
|
---|
| 187 | /// hash table of PVS entries
|
---|
[2117] | 188 | bit_vector mEntries;
|
---|
[2116] | 189 |
|
---|
| 190 | /// Number of samples used to create the PVS
|
---|
| 191 | int mSamples;
|
---|
[2117] | 192 |
|
---|
| 193 | public:
|
---|
| 194 | static int sPvsSize;
|
---|
[2116] | 195 | };
|
---|
| 196 |
|
---|
| 197 |
|
---|
| 198 | template <typename T, typename S>
|
---|
[2117] | 199 | BitVectorPvs<T, S>::BitVectorPvs()
|
---|
[2116] | 200 | {
|
---|
[2117] | 201 | // initialize bit vector
|
---|
| 202 | mEntries.reserve(sPvsSize);
|
---|
| 203 | mEntries.resize(sPvsSize);
|
---|
[2116] | 204 |
|
---|
[2117] | 205 | // set pvs entries to false
|
---|
| 206 | Clear();
|
---|
[2116] | 207 | }
|
---|
| 208 |
|
---|
| 209 |
|
---|
| 210 | template <typename T, typename S>
|
---|
[2117] | 211 | bool BitVectorPvs<T, S>::Find(T sample)
|
---|
[2116] | 212 | {
|
---|
[2117] | 213 | return mEntries[sample->GetId()];
|
---|
[2116] | 214 | }
|
---|
| 215 |
|
---|
| 216 |
|
---|
| 217 | template <typename T, typename S>
|
---|
[2117] | 218 | int BitVectorPvs<T, S>::GetSize() const
|
---|
[2116] | 219 | {
|
---|
[2117] | 220 | int size = 0;
|
---|
| 221 | bit_vector::const_iterator bit, bit_end = mEntries.end();
|
---|
| 222 |
|
---|
| 223 | for (bit = mEntries.begin(); bit != bit_end; ++ bit)
|
---|
| 224 | {
|
---|
| 225 | if (*bit) ++ size;
|
---|
| 226 | }
|
---|
| 227 |
|
---|
| 228 | return size;
|
---|
[2116] | 229 | }
|
---|
| 230 |
|
---|
| 231 |
|
---|
| 232 | template <typename T, typename S>
|
---|
[2117] | 233 | bool BitVectorPvs<T, S>::Empty() const
|
---|
[2116] | 234 | {
|
---|
[2117] | 235 | bit_vector::const_iterator bit, bit_end = mEntries.end();
|
---|
[2116] | 236 |
|
---|
[2117] | 237 | for (bit = mEntries.begin(); bit != bit_end; ++ bit)
|
---|
| 238 | {
|
---|
| 239 | if (*bit) return false;
|
---|
| 240 | }
|
---|
| 241 |
|
---|
| 242 | return true;
|
---|
| 243 | }
|
---|
| 244 |
|
---|
| 245 |
|
---|
| 246 | template <typename T, typename S>
|
---|
| 247 | float BitVectorPvs<T, S>::AddSample(T sample, const float pdf)
|
---|
| 248 | {
|
---|
| 249 | if (Find(sample))
|
---|
[2116] | 250 | return 0.0f;
|
---|
| 251 |
|
---|
[2117] | 252 | mEntries[sample->GetId()] = true;
|
---|
| 253 |
|
---|
[2116] | 254 | return 1.0f;
|
---|
| 255 | }
|
---|
| 256 |
|
---|
| 257 |
|
---|
| 258 | template <typename T, typename S>
|
---|
[2117] | 259 | void BitVectorPvs<T, S>::AddSampleDirty(T sample, const float pdf)
|
---|
[2116] | 260 | {
|
---|
[2117] | 261 | if (!Find(sample))
|
---|
[2116] | 262 | {
|
---|
[2117] | 263 | mEntries[sample->GetId()] = true;
|
---|
[2116] | 264 | }
|
---|
| 265 | }
|
---|
| 266 |
|
---|
| 267 |
|
---|
| 268 | template <typename T, typename S>
|
---|
[2117] | 269 | bool BitVectorPvs<T, S>::AddSampleDirtyCheck(T sample,
|
---|
[2116] | 270 | const float pdf)
|
---|
| 271 | {
|
---|
[2117] | 272 | if (Find(sample))
|
---|
[2116] | 273 | return false;
|
---|
| 274 |
|
---|
[2117] | 275 | mEntries[sample->GetId()] = true;
|
---|
[2116] | 276 | return true;
|
---|
| 277 | }
|
---|
| 278 |
|
---|
| 279 |
|
---|
| 280 | template <typename T, typename S>
|
---|
[2117] | 281 | void BitVectorPvs<T, S>::Sort()
|
---|
[2116] | 282 | {
|
---|
| 283 | }
|
---|
| 284 |
|
---|
| 285 |
|
---|
| 286 | template <typename T, typename S>
|
---|
[2117] | 287 | void BitVectorPvs<T, S>::Clear(const bool trim = true)
|
---|
[2116] | 288 | {
|
---|
[2117] | 289 | bit_vector::iterator bit, bit_end = mEntries.end();
|
---|
| 290 | for (bit = mEntries.begin(); bit != bit_end; ++ bit)
|
---|
| 291 | {
|
---|
| 292 | (*bit) = false;
|
---|
| 293 | }
|
---|
[2116] | 294 | }
|
---|
| 295 |
|
---|
| 296 |
|
---|
| 297 | template <typename T, typename S>
|
---|
[2117] | 298 | bool BitVectorPvs<T, S>::IsDirty() const
|
---|
[2116] | 299 | {
|
---|
| 300 | return false;
|
---|
| 301 | }
|
---|
| 302 |
|
---|
| 303 |
|
---|
| 304 | template <typename T, typename S>
|
---|
[2117] | 305 | bool BitVectorPvs<T, S>::RequiresResort() const
|
---|
[2116] | 306 | {
|
---|
| 307 | return false;
|
---|
| 308 | }
|
---|
| 309 |
|
---|
| 310 |
|
---|
| 311 | template <typename T, typename S>
|
---|
[2117] | 312 | typename BitVectorPvsIterator<T, S> BitVectorPvs<T, S>::GetIterator() const
|
---|
[2116] | 313 | {
|
---|
[2117] | 314 | BitVectorPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
|
---|
[2116] | 315 |
|
---|
| 316 | return pit;
|
---|
| 317 | }
|
---|
| 318 |
|
---|
| 319 |
|
---|
| 320 | template <typename T, typename S>
|
---|
[2117] | 321 | float BitVectorPvs<T, S>::GetEntrySize()
|
---|
[2116] | 322 | {
|
---|
[2117] | 323 | return (float)(sizeof(bool)) / float(1024 * 1024);
|
---|
[2116] | 324 | }
|
---|
| 325 |
|
---|
| 326 |
|
---|
| 327 | template <typename T, typename S>
|
---|
[2117] | 328 | int BitVectorPvs<T, S>::GetEntrySizeByte()
|
---|
[2116] | 329 | {
|
---|
[2117] | 330 | return sizeof(bool);
|
---|
[2116] | 331 | }
|
---|
| 332 |
|
---|
| 333 |
|
---|
| 334 | template <typename T, typename S>
|
---|
[2117] | 335 | float BitVectorPvs<T, S>::GetPvsHomogenity(BitVectorPvs<T, S> &pvs)
|
---|
[2116] | 336 | {
|
---|
| 337 | float pvsReduction, pvsEnlargement;
|
---|
| 338 |
|
---|
| 339 | ComputeContinuousPvsDifference(pvs, pvsReduction, pvsEnlargement);
|
---|
| 340 |
|
---|
| 341 | return pvsReduction + pvsEnlargement;
|
---|
| 342 | }
|
---|
| 343 |
|
---|
| 344 |
|
---|
| 345 | template <typename T, typename S>
|
---|
[2117] | 346 | bool BitVectorPvs<T, S>::GetSampleContribution(T sample,
|
---|
[2116] | 347 | const float pdf,
|
---|
| 348 | float &contribution)
|
---|
| 349 | {
|
---|
[2117] | 350 | const bool entryFound = Find(sample);
|
---|
[2116] | 351 |
|
---|
| 352 | if (entryFound)
|
---|
| 353 | {
|
---|
| 354 | contribution = 0.0f;
|
---|
| 355 | return false;
|
---|
| 356 | }
|
---|
| 357 | else
|
---|
| 358 | {
|
---|
| 359 | contribution = 1.0f;
|
---|
| 360 | return true;
|
---|
| 361 | }
|
---|
| 362 | }
|
---|
| 363 |
|
---|
| 364 |
|
---|
| 365 | template <typename T, typename S>
|
---|
[2117] | 366 | void BitVectorPvs<T, S>::Merge(BitVectorPvs<T, S> &mergedPvs,
|
---|
| 367 | const BitVectorPvs<T, S> &a,
|
---|
| 368 | const BitVectorPvs<T, S> &b)
|
---|
[2116] | 369 | {
|
---|
[2117] | 370 | bit_vector::iterator bit, bit_end = mergedPvs.mEntries.end();
|
---|
| 371 | bit_vector::const_iterator bitA = a.mEntries.begin(), bitB = b.mEntries.begin();
|
---|
| 372 |
|
---|
| 373 | for (bit = mergedPvs.mEntries.begin(); bit != bit_end; ++ bit, ++ bitA, ++ bitB)
|
---|
| 374 | {
|
---|
| 375 | (*bit) = (*bitA) | (*bitB);
|
---|
| 376 | }
|
---|
[2116] | 377 | }
|
---|
| 378 |
|
---|
| 379 |
|
---|
[2117] | 380 | template<typename T, typename S>
|
---|
| 381 | int BitVectorPvs<T, S>::sPvsSize = 0;
|
---|
| 382 |
|
---|
| 383 | template<typename T, typename S>
|
---|
| 384 | vector<T> BitVectorPvsIterator<T, S>::sObjects;
|
---|
| 385 |
|
---|
[2116] | 386 | }
|
---|
| 387 |
|
---|
| 388 | #endif
|
---|
| 389 |
|
---|