[177] | 1 | #ifndef __PVS_H
|
---|
| 2 | #define __PVS_H
|
---|
| 3 |
|
---|
| 4 | #include <map>
|
---|
[469] | 5 | #include <vector>
|
---|
[177] | 6 |
|
---|
| 7 | class KdNode;
|
---|
[240] | 8 | class BspNode;
|
---|
[191] | 9 | class Ray;
|
---|
[308] | 10 | class Intersectable;
|
---|
[406] | 11 | class ViewCellKdNode;
|
---|
[177] | 12 |
|
---|
[310] | 13 | template<typename T>
|
---|
| 14 | struct LtSample {
|
---|
[311] | 15 | bool operator()(const T a, const T b) const
|
---|
[310] | 16 | {
|
---|
| 17 | return a < b;
|
---|
| 18 | }
|
---|
| 19 | };
|
---|
| 20 |
|
---|
[469] | 21 | /** Information stored with a PVS entry. Consists of the number
|
---|
| 22 | the object was seen from the view cell.
|
---|
| 23 | */
|
---|
[310] | 24 |
|
---|
| 25 | template<typename T>
|
---|
| 26 | struct PvsData {
|
---|
| 27 | int mVisibleSamples;
|
---|
| 28 | PvsData<T>() {}
|
---|
[311] | 29 | PvsData<T>(const int samples): mVisibleSamples(samples) {}
|
---|
[310] | 30 | };
|
---|
| 31 |
|
---|
[469] | 32 | /** Template class representing the Potentially Visible Set (PVS)
|
---|
| 33 | mainly from a view cell, but also e.g., from objects.
|
---|
| 34 | */
|
---|
[310] | 35 | template<typename T>
|
---|
[311] | 36 | class Pvs
|
---|
[310] | 37 | {
|
---|
| 38 | public:
|
---|
[469] | 39 | Pvs(): /*mSamples(0), */mEntries() {}
|
---|
[466] | 40 |
|
---|
[469] | 41 | //int mSamples;
|
---|
[466] | 42 |
|
---|
[469] | 43 | /** Compresses PVS lossless or lossy.
|
---|
| 44 | */
|
---|
[466] | 45 | int Compress() {return 0;}
|
---|
| 46 | int GetSize() const {return (int)mEntries.size();}
|
---|
[469] | 47 | bool Empty() const {return mEntries.empty();}
|
---|
| 48 |
|
---|
[466] | 49 | /** Merges pvs of a and pvs of b into this pvs.
|
---|
| 50 | */
|
---|
| 51 | void Merge(const Pvs<T> &a, const Pvs<T> &b);
|
---|
[469] | 52 |
|
---|
[466] | 53 | /** Difference of pvs to pvs b.
|
---|
| 54 | @returns number of different entries.
|
---|
| 55 | */
|
---|
| 56 | int Diff(const Pvs<T> &b);
|
---|
| 57 |
|
---|
[469] | 58 | /** Finds sample in PVS.
|
---|
| 59 | @returns sample if found, NULL otherwise.
|
---|
| 60 | */
|
---|
[466] | 61 | PvsData<T> *Find(T sample);
|
---|
[469] | 62 |
|
---|
| 63 | /** Adds sample to PVS.
|
---|
| 64 | @contribution contribution of sample (0 or 1)
|
---|
| 65 | @returns true if sample was not already in PVS.
|
---|
| 66 | */
|
---|
[466] | 67 | bool AddSample(T sample, float &contribution);
|
---|
[469] | 68 |
|
---|
| 69 | /** Adds sample to PVS.
|
---|
| 70 | @returns contribution of sample (0 or 1)
|
---|
| 71 | */
|
---|
[466] | 72 | int AddSample(T sample);
|
---|
[369] | 73 |
|
---|
[469] | 74 | /** Returns PVS data, i.e., how often it was seen from the view cell,
|
---|
| 75 | and the object itsef.
|
---|
| 76 | */
|
---|
[466] | 77 | void GetData(const int index, T &entry, PvsData<T> &data);
|
---|
[469] | 78 |
|
---|
| 79 | /** Collects the PVS entries and returns them in the vector.
|
---|
| 80 | */
|
---|
| 81 | void CollectEntries(std::vector<T> &entries);
|
---|
| 82 |
|
---|
| 83 | /// Map of PVS entries
|
---|
[466] | 84 | std::map<T, PvsData<T>, LtSample<T> > mEntries;
|
---|
[310] | 85 | };
|
---|
| 86 |
|
---|
[341] | 87 | template <typename T>
|
---|
[362] | 88 | int Pvs<T>::Diff(const Pvs<T> &b)
|
---|
| 89 | {
|
---|
| 90 | int dif = 0;
|
---|
| 91 |
|
---|
| 92 | std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
|
---|
| 93 |
|
---|
| 94 | for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
|
---|
| 95 | {
|
---|
| 96 | PvsData<T> *data = Find((*it).first);
|
---|
| 97 | if (!data) ++ dif;
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 | return dif;
|
---|
| 101 | }
|
---|
| 102 |
|
---|
| 103 | template <typename T>
|
---|
[350] | 104 | void Pvs<T>::Merge(const Pvs<T> &a, const Pvs<T> &b)
|
---|
[341] | 105 | {
|
---|
[362] | 106 | std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
|
---|
| 107 |
|
---|
| 108 | // todo: copy all elements instead of inserting
|
---|
| 109 | for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
|
---|
| 110 | {
|
---|
| 111 | mEntries.insert(*it);
|
---|
| 112 | }
|
---|
| 113 |
|
---|
| 114 | for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
|
---|
| 115 | {
|
---|
| 116 | PvsData<T> *data = Find((*it).first);
|
---|
| 117 |
|
---|
| 118 | if (data)
|
---|
| 119 | data->mVisibleSamples += (*it).second.mVisibleSamples;
|
---|
| 120 | else
|
---|
| 121 | mEntries.insert(*it);
|
---|
| 122 | }
|
---|
[341] | 123 | }
|
---|
| 124 |
|
---|
[310] | 125 | template <typename T>
|
---|
[311] | 126 | PvsData<T> *Pvs<T>::Find(T sample)
|
---|
[310] | 127 | {
|
---|
[311] | 128 | std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.find(sample);
|
---|
[310] | 129 | if (i != mEntries.end()) {
|
---|
| 130 | return &(*i).second;
|
---|
[311] | 131 | } else
|
---|
[310] | 132 | return NULL;
|
---|
| 133 | }
|
---|
| 134 |
|
---|
| 135 | template <typename T>
|
---|
[311] | 136 | void Pvs<T>::GetData(const int index,
|
---|
[310] | 137 | T &entry,
|
---|
| 138 | PvsData<T> &data)
|
---|
| 139 | {
|
---|
[311] | 140 | std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.begin();
|
---|
[310] | 141 | for (int k = 0; k != index && i != mEntries.end(); i++, k++);
|
---|
| 142 |
|
---|
| 143 | entry = (*i).first;
|
---|
[311] | 144 | data = (*i).second;
|
---|
[310] | 145 | }
|
---|
| 146 |
|
---|
[311] | 147 | template <typename T>
|
---|
| 148 | int Pvs<T>::AddSample(T sample)
|
---|
[177] | 149 | {
|
---|
[466] | 150 | float dummy;
|
---|
| 151 | return AddSample(sample, dummy) ? 1 : 0;
|
---|
| 152 | }
|
---|
[177] | 153 |
|
---|
[466] | 154 | template <typename T>
|
---|
| 155 | bool Pvs<T>::AddSample(T sample, float &contribution)
|
---|
| 156 | {
|
---|
| 157 | PvsData<T> *data = Find(sample);
|
---|
| 158 |
|
---|
| 159 | if (data) {
|
---|
| 160 | data->mVisibleSamples++;
|
---|
| 161 | contribution = 1.0f/data->mVisibleSamples;
|
---|
| 162 | return false;
|
---|
| 163 | }
|
---|
| 164 | else {
|
---|
| 165 | mEntries[sample] = PvsData<T>(1);
|
---|
| 166 | contribution = 1.0f;
|
---|
| 167 | return true;
|
---|
| 168 | }
|
---|
[311] | 169 | }
|
---|
[308] | 170 |
|
---|
[469] | 171 | template <typename T>
|
---|
| 172 | void Pvs<T>::CollectEntries(std::vector<T> &entries)
|
---|
| 173 | {
|
---|
| 174 | PvsMap<T>::const_iterator it, it_end = mEntries.end();
|
---|
| 175 |
|
---|
| 176 | // output PVS of view cell
|
---|
| 177 | for (it = mEntries.begin(); it != it_end; ++ it)
|
---|
| 178 | entries.push_back((*it)->first);
|
---|
| 179 | }
|
---|
| 180 |
|
---|
[311] | 181 | /** Class instantiating the Pvs template for kd tree nodes.
|
---|
| 182 | */
|
---|
| 183 | class KdPvs: public Pvs<KdNode *>
|
---|
[308] | 184 | {
|
---|
[311] | 185 | int Compress();
|
---|
[308] | 186 | };
|
---|
| 187 |
|
---|
[311] | 188 | typedef std::map<KdNode *, PvsData<KdNode *>, LtSample<KdNode *> > KdPvsMap;
|
---|
[469] | 189 | typedef std::map<Intersectable *, PvsData<Intersectable *>, LtSample<Intersectable *> > ObjectPvsMap;
|
---|
| 190 | typedef PvsData<Intersectable *> ObjectPvsData;
|
---|
[311] | 191 | typedef PvsData<KdNode *> KdPvsData;
|
---|
[308] | 192 |
|
---|
[469] | 193 | typedef Pvs<Intersectable *> ObjectPvs;
|
---|
[366] | 194 |
|
---|
[469] | 195 |
|
---|
[177] | 196 | #endif
|
---|
| 197 |
|
---|