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