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