[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 | {
|
---|
[2575] | 81 | template<typename T1, typename S1> friend class BitVectorPvsIterator;
|
---|
[2116] | 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 |
|
---|
[2575] | 123 | 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 | {
|
---|
[2575] | 147 | std::cerr << "bitvector: merge in place not implemented yet"
|
---|
| 148 | << std::endl;
|
---|
[2116] | 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 | {
|
---|
[2575] | 170 | std::cerr << "not yet implemented" << std::endl;
|
---|
| 171 | return 0;
|
---|
[2116] | 172 | }
|
---|
| 173 |
|
---|
| 174 | /** Compute continuous PVS difference
|
---|
| 175 | */
|
---|
[2117] | 176 | void ComputeContinuousPvsDifference(BitVectorPvs<T, S> &pvs,
|
---|
[2116] | 177 | float &pvsReduction,
|
---|
| 178 | float &pvsEnlargement)
|
---|
| 179 | {
|
---|
[2575] | 180 | std::cerr << "not yet implemented" << std::endl;
|
---|
[2116] | 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>
|
---|
[2530] | 270 | bool BitVectorPvs<T, S>::AddSampleDirtyCheck(T sample, const float pdf)
|
---|
[2116] | 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>
|
---|
[2575] | 287 | void BitVectorPvs<T, S>::Clear(const bool trim)
|
---|
[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>
|
---|
[2575] | 312 | BitVectorPvsIterator<T, S> BitVectorPvs<T, S>::GetIterator() const
|
---|
[2116] | 313 | {
|
---|
[2575] | 314 | return BitVectorPvsIterator<T, S>(mEntries.begin(), mEntries.end());
|
---|
[2116] | 315 | }
|
---|
| 316 |
|
---|
| 317 |
|
---|
| 318 | template <typename T, typename S>
|
---|
[2117] | 319 | float BitVectorPvs<T, S>::GetEntrySize()
|
---|
[2116] | 320 | {
|
---|
[2117] | 321 | return (float)(sizeof(bool)) / float(1024 * 1024);
|
---|
[2116] | 322 | }
|
---|
| 323 |
|
---|
| 324 |
|
---|
| 325 | template <typename T, typename S>
|
---|
[2117] | 326 | int BitVectorPvs<T, S>::GetEntrySizeByte()
|
---|
[2116] | 327 | {
|
---|
[2117] | 328 | return sizeof(bool);
|
---|
[2116] | 329 | }
|
---|
| 330 |
|
---|
| 331 |
|
---|
| 332 | template <typename T, typename S>
|
---|
[2117] | 333 | float BitVectorPvs<T, S>::GetPvsHomogenity(BitVectorPvs<T, S> &pvs)
|
---|
[2116] | 334 | {
|
---|
| 335 | float pvsReduction, pvsEnlargement;
|
---|
| 336 |
|
---|
| 337 | ComputeContinuousPvsDifference(pvs, pvsReduction, pvsEnlargement);
|
---|
| 338 |
|
---|
| 339 | return pvsReduction + pvsEnlargement;
|
---|
| 340 | }
|
---|
| 341 |
|
---|
| 342 |
|
---|
| 343 | template <typename T, typename S>
|
---|
[2117] | 344 | bool BitVectorPvs<T, S>::GetSampleContribution(T sample,
|
---|
[2116] | 345 | const float pdf,
|
---|
| 346 | float &contribution)
|
---|
| 347 | {
|
---|
[2117] | 348 | const bool entryFound = Find(sample);
|
---|
[2116] | 349 |
|
---|
| 350 | if (entryFound)
|
---|
| 351 | {
|
---|
| 352 | contribution = 0.0f;
|
---|
| 353 | return false;
|
---|
| 354 | }
|
---|
| 355 | else
|
---|
| 356 | {
|
---|
| 357 | contribution = 1.0f;
|
---|
| 358 | return true;
|
---|
| 359 | }
|
---|
| 360 | }
|
---|
| 361 |
|
---|
| 362 |
|
---|
| 363 | template <typename T, typename S>
|
---|
[2117] | 364 | void BitVectorPvs<T, S>::Merge(BitVectorPvs<T, S> &mergedPvs,
|
---|
| 365 | const BitVectorPvs<T, S> &a,
|
---|
| 366 | const BitVectorPvs<T, S> &b)
|
---|
[2116] | 367 | {
|
---|
[2117] | 368 | bit_vector::iterator bit, bit_end = mergedPvs.mEntries.end();
|
---|
| 369 | bit_vector::const_iterator bitA = a.mEntries.begin(), bitB = b.mEntries.begin();
|
---|
| 370 |
|
---|
| 371 | for (bit = mergedPvs.mEntries.begin(); bit != bit_end; ++ bit, ++ bitA, ++ bitB)
|
---|
| 372 | {
|
---|
| 373 | (*bit) = (*bitA) | (*bitB);
|
---|
| 374 | }
|
---|
[2116] | 375 | }
|
---|
| 376 |
|
---|
| 377 |
|
---|
[2117] | 378 | template<typename T, typename S>
|
---|
| 379 | int BitVectorPvs<T, S>::sPvsSize = 0;
|
---|
| 380 |
|
---|
| 381 | template<typename T, typename S>
|
---|
| 382 | vector<T> BitVectorPvsIterator<T, S>::sObjects;
|
---|
| 383 |
|
---|
[2116] | 384 | }
|
---|
| 385 |
|
---|
| 386 | #endif
|
---|
| 387 |
|
---|