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