1 | #include "CHCPlusPlusTraverser.h"
|
---|
2 | #include "RenderState.h"
|
---|
3 |
|
---|
4 | using namespace std;
|
---|
5 |
|
---|
6 | namespace CHCDemoEngine
|
---|
7 | {
|
---|
8 |
|
---|
9 |
|
---|
10 | CHCPlusPlusTraverser::CHCPlusPlusTraverser()
|
---|
11 | {
|
---|
12 | }
|
---|
13 |
|
---|
14 |
|
---|
15 | void CHCPlusPlusTraverser::HandleQueryResult(OcclusionQuery *query)
|
---|
16 | {
|
---|
17 | // wait until result available
|
---|
18 | const int visible = query->GetQueryResult() > mVisibilityThreshold;
|
---|
19 |
|
---|
20 | // multiquery
|
---|
21 | if (query->GetSize() > 1)
|
---|
22 | {
|
---|
23 | // failed query: query individual nodes
|
---|
24 | if (visible)
|
---|
25 | {
|
---|
26 | for (size_t i = 0; i < query->GetSize(); ++ i)
|
---|
27 | {
|
---|
28 | BvhNode *node = query->GetNodes()[i];
|
---|
29 |
|
---|
30 | mIQueue.push_back(node);
|
---|
31 | node->SetLastQueriedFrame(mFrameId);
|
---|
32 | }
|
---|
33 | }
|
---|
34 | else // query successful: update classifications
|
---|
35 | {
|
---|
36 | for (size_t i = 0; i < query->GetSize(); ++ i)
|
---|
37 | {
|
---|
38 | BvhNode *node = query->GetNodes()[i];
|
---|
39 | node->IncTimesTestedInvisible();
|
---|
40 | node->SetVisible(false);
|
---|
41 | node->SetLastQueriedFrame(mFrameId);
|
---|
42 | }
|
---|
43 |
|
---|
44 | mStats.mNumQueryCulledNodes += query->GetSize();
|
---|
45 | }
|
---|
46 | }
|
---|
47 | else // single query
|
---|
48 | {
|
---|
49 | BvhNode *node = query->GetFrontNode();
|
---|
50 |
|
---|
51 | node->SetLastQueriedFrame(mFrameId);
|
---|
52 |
|
---|
53 | // failed query: query individual nodes
|
---|
54 | if (visible)
|
---|
55 | {
|
---|
56 | // node was previously invisible
|
---|
57 | if (!node->IsVisible())
|
---|
58 | {
|
---|
59 | // reset flag
|
---|
60 | node->SetTimesTestedInvisible(0);
|
---|
61 | node->SetAssumedVisibleFrameId(mFrameId + mAssumedVisibleFrames);
|
---|
62 | }
|
---|
63 | else
|
---|
64 | { // randomize first invokation
|
---|
65 | node->SetAssumedVisibleFrameId(mFrameId + Random(mAssumedVisibleFrames + 1));
|
---|
66 | }
|
---|
67 |
|
---|
68 | mBvh->MakeParentsVisible(node);
|
---|
69 | TraverseNode(node);
|
---|
70 | }
|
---|
71 | else
|
---|
72 | {
|
---|
73 | node->IncTimesTestedInvisible();
|
---|
74 | ++ mStats.mNumQueryCulledNodes;
|
---|
75 | }
|
---|
76 |
|
---|
77 | node->SetVisible(visible);
|
---|
78 | }
|
---|
79 | }
|
---|
80 |
|
---|
81 |
|
---|
82 | void CHCPlusPlusTraverser::Traverse()
|
---|
83 | {
|
---|
84 | int waitedForQueries = 0;
|
---|
85 | int returnedQueries = 0;
|
---|
86 |
|
---|
87 | //-- PART 1: process finished occlusion queries
|
---|
88 | while (!mDistanceQueue.empty() || !mQueryQueue.empty())
|
---|
89 | {
|
---|
90 | bool resultAvailable = false;
|
---|
91 |
|
---|
92 | while (!mQueryQueue.empty() &&
|
---|
93 | (mDistanceQueue.empty() || (resultAvailable = mQueryQueue.front()->ResultAvailable())))
|
---|
94 | {
|
---|
95 | while (!resultAvailable && !mVQueue.empty())
|
---|
96 | {
|
---|
97 | BvhNode *node = mVQueue.front();
|
---|
98 | mVQueue.pop();
|
---|
99 |
|
---|
100 | OcclusionQuery *query = IssueOcclusionQuery(node);
|
---|
101 |
|
---|
102 | mQueryQueue.push(query);
|
---|
103 | resultAvailable = mQueryQueue.front()->ResultAvailable();
|
---|
104 | }
|
---|
105 |
|
---|
106 | if (!resultAvailable)
|
---|
107 | ++ waitedForQueries;
|
---|
108 | ++ returnedQueries;
|
---|
109 |
|
---|
110 | OcclusionQuery *query = mQueryQueue.front();
|
---|
111 | mQueryQueue.pop();
|
---|
112 |
|
---|
113 | // waiting for query result
|
---|
114 | HandleQueryResult(query);
|
---|
115 | }
|
---|
116 |
|
---|
117 | //-- PART 2: hierarchical traversal
|
---|
118 | if (!mDistanceQueue.empty())
|
---|
119 | {
|
---|
120 | BvhNode *node = mDistanceQueue.top();
|
---|
121 | mDistanceQueue.pop();
|
---|
122 |
|
---|
123 | if (mBvh->IsWithinViewFrustum(node))
|
---|
124 | {
|
---|
125 | // for near plane intersecting bounding box possible
|
---|
126 | // wrong results => skip occlusion query
|
---|
127 | if (IntersectsNearPlane(node))
|
---|
128 | {
|
---|
129 | // update node's visited flag
|
---|
130 | node->SetLastVisitedFrame(mFrameId);
|
---|
131 | node->SetVisible(true);
|
---|
132 | mBvh->MakeParentsVisible(node);
|
---|
133 |
|
---|
134 | TraverseNode(node);
|
---|
135 | }
|
---|
136 | else
|
---|
137 | {
|
---|
138 | // identify previously visible nodes
|
---|
139 | const bool wasVisible = node->IsVisible() && (node->GetLastVisitedFrame() == mFrameId - 1);
|
---|
140 |
|
---|
141 | // identify nodes that we cannot skip queries for
|
---|
142 | const bool queryFeasible = (!wasVisible || (node->IsVirtualLeaf() &&
|
---|
143 | (node->GetAssumedVisibleFrameId() <= mFrameId)));
|
---|
144 |
|
---|
145 | // node was not recently tested => reset flag
|
---|
146 | if (node->GetLastVisitedFrame() != mFrameId - 1)
|
---|
147 | node->SetTimesTestedInvisible(0);
|
---|
148 |
|
---|
149 | // update node's visited flag
|
---|
150 | node->SetLastVisitedFrame(mFrameId);
|
---|
151 |
|
---|
152 | // skip testing previously visible interior nodes
|
---|
153 | if (queryFeasible)
|
---|
154 | {
|
---|
155 | if (!wasVisible)
|
---|
156 | {
|
---|
157 | QueryPreviouslyInvisibleNodes(node);
|
---|
158 | }
|
---|
159 | else
|
---|
160 | {
|
---|
161 | mVQueue.push(node);
|
---|
162 | }
|
---|
163 | }
|
---|
164 | else
|
---|
165 | {
|
---|
166 | if (node->IsVirtualLeaf())
|
---|
167 | {
|
---|
168 | node->SetVisible(true);
|
---|
169 | mBvh->MakeParentsVisible(node);
|
---|
170 | }
|
---|
171 | else // reset visibility classification
|
---|
172 | {
|
---|
173 | node->SetVisible(false);
|
---|
174 | }
|
---|
175 | }
|
---|
176 |
|
---|
177 | // always traverse a node if it was previously visible
|
---|
178 | if (wasVisible)
|
---|
179 | TraverseNode(node);
|
---|
180 | }
|
---|
181 | }
|
---|
182 | else
|
---|
183 | {
|
---|
184 | // for stats
|
---|
185 | ++ mStats.mNumFrustumCulledNodes;
|
---|
186 | }
|
---|
187 | }
|
---|
188 |
|
---|
189 | // distance queue empty: feed the remaining multiqueries to
|
---|
190 | // be able to proceed traversal
|
---|
191 | if (mDistanceQueue.empty())
|
---|
192 | {
|
---|
193 | IssueMultiQueries();
|
---|
194 | }
|
---|
195 | }
|
---|
196 |
|
---|
197 | // render the rest of the objects
|
---|
198 | if (mUseRenderQueue) ApplyRenderQueue();
|
---|
199 |
|
---|
200 |
|
---|
201 | //////////////
|
---|
202 | //-- issue remaining previously visible node queries
|
---|
203 |
|
---|
204 | while (!mVQueue.empty())
|
---|
205 | {
|
---|
206 | BvhNode *node = mVQueue.front();
|
---|
207 | mVQueue.pop();
|
---|
208 |
|
---|
209 | OcclusionQuery *query = IssueOcclusionQuery(node);
|
---|
210 | mQueryQueue.push(query);
|
---|
211 | }
|
---|
212 |
|
---|
213 | while (!mQueryQueue.empty())
|
---|
214 | {
|
---|
215 | OcclusionQuery *query = mQueryQueue.front();
|
---|
216 | mQueryQueue.pop();
|
---|
217 |
|
---|
218 | HandleQueryResult(query);
|
---|
219 | }
|
---|
220 |
|
---|
221 | //cout << "returned queries: " << returnedQueries << " waited for queries: " << waitedForQueries << " (=" << 100.0f * waitedForQueries / returnedQueries << "%)" << endl;
|
---|
222 | }
|
---|
223 |
|
---|
224 |
|
---|
225 | void CHCPlusPlusTraverser::QueryPreviouslyInvisibleNodes(BvhNode *node)
|
---|
226 | {
|
---|
227 | mIQueue.push_back(node);
|
---|
228 |
|
---|
229 | if (mIQueue.size() > mMaxBatchSize)
|
---|
230 | {
|
---|
231 | IssueMultiQueries();
|
---|
232 | }
|
---|
233 | }
|
---|
234 |
|
---|
235 |
|
---|
236 | OcclusionQuery * CHCPlusPlusTraverser::GetNextMultiQuery(BvhNodeContainer &iqueue)
|
---|
237 | {
|
---|
238 | OcclusionQuery *query = mQueryHandler.RequestQuery();
|
---|
239 |
|
---|
240 | float pFail = 1.0f;
|
---|
241 | float maxBatchVal = 0.0f;
|
---|
242 | float newPBatch = 1.0f;
|
---|
243 | float newBatchVal;
|
---|
244 |
|
---|
245 | // issue next query
|
---|
246 | while (!iqueue.empty())
|
---|
247 | {
|
---|
248 | BvhNode *node = iqueue.back();
|
---|
249 |
|
---|
250 | // node was already part of a mulitquery => avoid recursion
|
---|
251 | if (node->GetLastQueriedFrame() == mFrameId)
|
---|
252 | newPBatch = 0;
|
---|
253 | else
|
---|
254 | newPBatch *= mVisibilityPredictor.GetProbability(node);
|
---|
255 |
|
---|
256 | if (query->GetNodes().empty())
|
---|
257 | {
|
---|
258 | // single node will never cause a wasted query
|
---|
259 | newBatchVal = 1.0f;
|
---|
260 | }
|
---|
261 | else
|
---|
262 | {
|
---|
263 | int newSize = query->GetSize() + 1;
|
---|
264 | newBatchVal = newSize / (1.0f + (1.0f - newPBatch) * newSize);
|
---|
265 | }
|
---|
266 |
|
---|
267 | if (newBatchVal <= maxBatchVal)
|
---|
268 | break;
|
---|
269 |
|
---|
270 | iqueue.pop_back();
|
---|
271 | query->AddNode(node);
|
---|
272 |
|
---|
273 | maxBatchVal = newBatchVal;
|
---|
274 | }
|
---|
275 |
|
---|
276 | //cout <<"size: " << query->GetSize() << endl;
|
---|
277 | IssueOcclusionQuery(*query);
|
---|
278 |
|
---|
279 | return query;
|
---|
280 | }
|
---|
281 |
|
---|
282 |
|
---|
283 | static inline bool lt(BvhNode *a, BvhNode *b)
|
---|
284 | {
|
---|
285 | return a->GetTimesTestedInvisible() < b->GetTimesTestedInvisible();
|
---|
286 | }
|
---|
287 |
|
---|
288 |
|
---|
289 | void CHCPlusPlusTraverser::IssueMultiQueries()
|
---|
290 | {
|
---|
291 | if (mUseMultiQueries)
|
---|
292 | {
|
---|
293 | // sort queries by #times invisible
|
---|
294 | sort(mIQueue.begin(), mIQueue.end(), lt);
|
---|
295 |
|
---|
296 | while (!mIQueue.empty())
|
---|
297 | mQueryQueue.push(GetNextMultiQuery(mIQueue));
|
---|
298 | }
|
---|
299 | else
|
---|
300 | {
|
---|
301 | BvhNodeContainer::const_iterator it, it_end = mIQueue.end();
|
---|
302 |
|
---|
303 | for (it = mIQueue.begin(); it != it_end; ++ it)
|
---|
304 | mQueryQueue.push(IssueOcclusionQuery(*it));
|
---|
305 |
|
---|
306 | mIQueue.clear();
|
---|
307 | }
|
---|
308 | }
|
---|
309 |
|
---|
310 |
|
---|
311 | }
|
---|