1 | #ifndef __PVS_H
|
---|
2 | #define __PVS_H
|
---|
3 |
|
---|
4 | #include <map>
|
---|
5 | #include <vector>
|
---|
6 |
|
---|
7 | class KdNode;
|
---|
8 | class BspNode;
|
---|
9 | class Ray;
|
---|
10 | class Intersectable;
|
---|
11 | class ViewCellKdNode;
|
---|
12 |
|
---|
13 | template<typename T>
|
---|
14 | struct LtSample {
|
---|
15 | bool operator()(const T a, const T b) const
|
---|
16 | {
|
---|
17 | return a < b;
|
---|
18 | }
|
---|
19 | };
|
---|
20 |
|
---|
21 | /** Information stored with a PVS entry. Consists of the number
|
---|
22 | the object was seen from the view cell.
|
---|
23 | */
|
---|
24 |
|
---|
25 | template<typename T>
|
---|
26 | struct PvsData {
|
---|
27 | int mVisibleSamples;
|
---|
28 | PvsData<T>() {}
|
---|
29 | PvsData<T>(const int samples): mVisibleSamples(samples) {}
|
---|
30 | };
|
---|
31 |
|
---|
32 | /** Template class representing the Potentially Visible Set (PVS)
|
---|
33 | mainly from a view cell, but also e.g., from objects.
|
---|
34 | */
|
---|
35 | template<typename T>
|
---|
36 | class Pvs
|
---|
37 | {
|
---|
38 | public:
|
---|
39 | Pvs(): /*mSamples(0), */mEntries() {}
|
---|
40 |
|
---|
41 | //int mSamples;
|
---|
42 |
|
---|
43 | /** Compresses PVS lossless or lossy.
|
---|
44 | */
|
---|
45 | int Compress() {return 0;}
|
---|
46 | int GetSize() const {return (int)mEntries.size();}
|
---|
47 | bool Empty() const {return mEntries.empty();}
|
---|
48 |
|
---|
49 | /** Merges pvs of a and pvs of b into this pvs.
|
---|
50 | */
|
---|
51 | void Merge(const Pvs<T> &a, const Pvs<T> &b);
|
---|
52 |
|
---|
53 | /** Difference of pvs to pvs b.
|
---|
54 | @returns number of different entries.
|
---|
55 | */
|
---|
56 | int Diff(const Pvs<T> &b);
|
---|
57 |
|
---|
58 | /** Finds sample in PVS.
|
---|
59 | @returns sample if found, NULL otherwise.
|
---|
60 | */
|
---|
61 | PvsData<T> *Find(T sample);
|
---|
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 | */
|
---|
67 | bool AddSample(T sample, float &contribution);
|
---|
68 |
|
---|
69 | /** Adds sample to PVS.
|
---|
70 | @returns contribution of sample (0 or 1)
|
---|
71 | */
|
---|
72 | int AddSample(T sample);
|
---|
73 |
|
---|
74 | /** Adds one pvs to another one.
|
---|
75 | @returns new pvs size
|
---|
76 | */
|
---|
77 | int AddPvs(const Pvs<T> &pvs);
|
---|
78 | /** Subtracts one pvs from another one.
|
---|
79 | @returns new pvs size
|
---|
80 | */
|
---|
81 | int SubtractPvs(const Pvs<T> &pvs);
|
---|
82 | /** Returns PVS data, i.e., how often it was seen from the view cell,
|
---|
83 | and the object itsef.
|
---|
84 | */
|
---|
85 | void GetData(const int index, T &entry, PvsData<T> &data);
|
---|
86 |
|
---|
87 | /** Collects the PVS entries and returns them in the vector.
|
---|
88 | */
|
---|
89 | void CollectEntries(std::vector<T> &entries);
|
---|
90 |
|
---|
91 | /** Removes sample from PVS if reference count is zero.
|
---|
92 | @param visibleSampels number of references to be removed
|
---|
93 | */
|
---|
94 | bool RemoveSample(T sample, const int visibleSamples);
|
---|
95 |
|
---|
96 | /// Map of PVS entries
|
---|
97 | std::map<T, PvsData<T>, LtSample<T> > mEntries;
|
---|
98 | };
|
---|
99 |
|
---|
100 | template <typename T>
|
---|
101 | int Pvs<T>::Diff(const Pvs<T> &b)
|
---|
102 | {
|
---|
103 | int dif = 0;
|
---|
104 |
|
---|
105 | std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
|
---|
106 |
|
---|
107 | for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
|
---|
108 | {
|
---|
109 | PvsData<T> *data = Find((*it).first);
|
---|
110 | if (!data) ++ dif;
|
---|
111 | }
|
---|
112 |
|
---|
113 | return dif;
|
---|
114 | }
|
---|
115 |
|
---|
116 | template <typename T>
|
---|
117 | void Pvs<T>::Merge(const Pvs<T> &a, const Pvs<T> &b)
|
---|
118 | {
|
---|
119 | std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
|
---|
120 |
|
---|
121 | // todo: copy all elements instead of inserting
|
---|
122 | for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
|
---|
123 | mEntries.insert(*it);
|
---|
124 |
|
---|
125 | for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
|
---|
126 | {
|
---|
127 | PvsData<T> *data = Find((*it).first);
|
---|
128 |
|
---|
129 | if (data)
|
---|
130 | data->mVisibleSamples += (*it).second.mVisibleSamples;
|
---|
131 | else
|
---|
132 | mEntries.insert(*it);
|
---|
133 | }
|
---|
134 | }
|
---|
135 |
|
---|
136 | template <typename T>
|
---|
137 | PvsData<T> *Pvs<T>::Find(T sample)
|
---|
138 | {
|
---|
139 | std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.find(sample);
|
---|
140 | if (i != mEntries.end()) {
|
---|
141 | return &(*i).second;
|
---|
142 | } else
|
---|
143 | return NULL;
|
---|
144 | }
|
---|
145 |
|
---|
146 | template <typename T>
|
---|
147 | void Pvs<T>::GetData(const int index,
|
---|
148 | T &entry,
|
---|
149 | PvsData<T> &data)
|
---|
150 | {
|
---|
151 | std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.begin();
|
---|
152 | for (int k = 0; k != index && i != mEntries.end(); i++, k++);
|
---|
153 |
|
---|
154 | entry = (*i).first;
|
---|
155 | data = (*i).second;
|
---|
156 | }
|
---|
157 |
|
---|
158 | template <typename T>
|
---|
159 | int Pvs<T>::AddSample(T sample)
|
---|
160 | {
|
---|
161 | float dummy;
|
---|
162 | return AddSample(sample, dummy) ? 1 : 0;
|
---|
163 | }
|
---|
164 |
|
---|
165 | template <typename T>
|
---|
166 | bool Pvs<T>::AddSample(T sample, float &contribution)
|
---|
167 | {
|
---|
168 | PvsData<T> *data = Find(sample);
|
---|
169 |
|
---|
170 | if (data) {
|
---|
171 | data->mVisibleSamples++;
|
---|
172 | contribution = 1.0f/data->mVisibleSamples;
|
---|
173 | return false;
|
---|
174 | }
|
---|
175 | else {
|
---|
176 | mEntries[sample] = PvsData<T>(1);
|
---|
177 | contribution = 1.0f;
|
---|
178 | return true;
|
---|
179 | }
|
---|
180 | }
|
---|
181 |
|
---|
182 | template <typename T>
|
---|
183 | bool Pvs<T>::RemoveSample(T sample, const int visibleSamples)
|
---|
184 | {
|
---|
185 | std::map<T, PvsData<T>, LtSample<T> >::
|
---|
186 | iterator it = mEntries.find(sample);
|
---|
187 |
|
---|
188 | if (it == mEntries.end())
|
---|
189 | return false;
|
---|
190 |
|
---|
191 | PvsData<T> *data = &(*it).second;
|
---|
192 |
|
---|
193 | data->mVisibleSamples -= visibleSamples;
|
---|
194 | if (data->mVisibleSamples <= 0)
|
---|
195 | mEntries.erase(it);
|
---|
196 |
|
---|
197 | return true;
|
---|
198 | }
|
---|
199 |
|
---|
200 | template <typename T>
|
---|
201 | int Pvs<T>::AddPvs(const Pvs<T> &pvs)
|
---|
202 | {
|
---|
203 | std::map<T, PvsData<T>, LtSample<T> >::
|
---|
204 | const_iterator it, it_end = pvs.mEntries.end();
|
---|
205 |
|
---|
206 | float contri;
|
---|
207 | // output PVS of view cell
|
---|
208 | for (it = pvs.mEntries.begin(); it != it_end; ++ it)
|
---|
209 | AddSample((*it).first, contri);
|
---|
210 |
|
---|
211 | return GetSize();
|
---|
212 | }
|
---|
213 |
|
---|
214 | template <typename T>
|
---|
215 | int Pvs<T>::SubtractPvs(const Pvs<T> &pvs)
|
---|
216 | {
|
---|
217 | std::map<T, PvsData<T>, LtSample<T> >::
|
---|
218 | const_iterator it, it_end = pvs.mEntries.end();
|
---|
219 |
|
---|
220 | // output PVS of view cell
|
---|
221 | for (it = pvs.mEntries.begin(); it != it_end; ++ it)
|
---|
222 | RemoveSample((*it).first, (*it).second.mVisibleSamples);
|
---|
223 |
|
---|
224 | return GetSize();
|
---|
225 | }
|
---|
226 |
|
---|
227 | template <typename T>
|
---|
228 | void Pvs<T>::CollectEntries(std::vector<T> &entries)
|
---|
229 | {
|
---|
230 | std::map<T, PvsData<T>, LtSample<T> >::
|
---|
231 | const_iterator it, it_end = mEntries.end();
|
---|
232 |
|
---|
233 | // output PVS of view cell
|
---|
234 | for (it = mEntries.begin(); it != it_end; ++ it)
|
---|
235 | entries.push_back((*it)->first);
|
---|
236 | }
|
---|
237 |
|
---|
238 | /** Class instantiating the Pvs template for kd tree nodes.
|
---|
239 | */
|
---|
240 | class KdPvs: public Pvs<KdNode *>
|
---|
241 | {
|
---|
242 | int Compress();
|
---|
243 | };
|
---|
244 |
|
---|
245 | typedef std::map<KdNode *, PvsData<KdNode *>, LtSample<KdNode *> > KdPvsMap;
|
---|
246 | typedef std::map<Intersectable *, PvsData<Intersectable *>, LtSample<Intersectable *> > ObjectPvsMap;
|
---|
247 | typedef PvsData<Intersectable *> ObjectPvsData;
|
---|
248 | typedef PvsData<KdNode *> KdPvsData;
|
---|
249 |
|
---|
250 | typedef Pvs<Intersectable *> ObjectPvs;
|
---|
251 |
|
---|
252 |
|
---|
253 | #endif
|
---|
254 |
|
---|