[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 |
|
---|
[3271] | 121 | if (0 && !IsNodeGeometryVisible(node, 10))
|
---|
[3251] | 122 | {
|
---|
[3271] | 123 | // todo: find out why it is jumping
|
---|
[3259] | 124 | node->SetLastVisitedFrame(mFrameId);
|
---|
[3251] | 125 | node->SetVisible(false);
|
---|
[3259] | 126 |
|
---|
| 127 | mBvh->MakeParentsVisible(node);
|
---|
| 128 |
|
---|
[3251] | 129 | continue;
|
---|
| 130 | }
|
---|
| 131 |
|
---|
[2767] | 132 | if (mBvh->IsWithinViewFrustum(node))
|
---|
| 133 | {
|
---|
| 134 | // for near plane intersecting bounding box possible
|
---|
| 135 | // wrong results => skip occlusion query
|
---|
[3065] | 136 | if (mBvh->IntersectsNearPlane(node))
|
---|
[2767] | 137 | {
|
---|
| 138 | // update node's visited flag
|
---|
| 139 | node->SetLastVisitedFrame(mFrameId);
|
---|
| 140 | node->SetVisible(true);
|
---|
| 141 | mBvh->MakeParentsVisible(node);
|
---|
| 142 |
|
---|
| 143 | TraverseNode(node);
|
---|
| 144 | }
|
---|
| 145 | else
|
---|
| 146 | {
|
---|
| 147 | // identify previously visible nodes
|
---|
| 148 | const bool wasVisible = node->IsVisible() && (node->GetLastVisitedFrame() == mFrameId - 1);
|
---|
| 149 |
|
---|
| 150 | // identify nodes that we cannot skip queries for
|
---|
[2792] | 151 | const bool queryFeasible = (!wasVisible || (node->IsVirtualLeaf() &&
|
---|
[2774] | 152 | (node->GetAssumedVisibleFrameId() <= mFrameId)));
|
---|
[2767] | 153 |
|
---|
[2773] | 154 | // node was not recently tested => reset flag
|
---|
[3259] | 155 | if (node->GetLastVisitedFrame() != (mFrameId - 1))
|
---|
[3251] | 156 | {
|
---|
[2773] | 157 | node->SetTimesTestedInvisible(0);
|
---|
[3251] | 158 | }
|
---|
[2773] | 159 |
|
---|
[2767] | 160 | // update node's visited flag
|
---|
| 161 | node->SetLastVisitedFrame(mFrameId);
|
---|
| 162 |
|
---|
| 163 | // skip testing previously visible interior nodes
|
---|
[2792] | 164 | if (queryFeasible)
|
---|
[2767] | 165 | {
|
---|
[2770] | 166 | if (!wasVisible)
|
---|
| 167 | {
|
---|
| 168 | QueryPreviouslyInvisibleNodes(node);
|
---|
| 169 | }
|
---|
| 170 | else
|
---|
| 171 | {
|
---|
| 172 | mVQueue.push(node);
|
---|
| 173 | }
|
---|
[2767] | 174 | }
|
---|
[2776] | 175 | else
|
---|
| 176 | {
|
---|
[3251] | 177 | // node is leaf => set to visible
|
---|
[2776] | 178 | if (node->IsVirtualLeaf())
|
---|
| 179 | {
|
---|
| 180 | node->SetVisible(true);
|
---|
| 181 | mBvh->MakeParentsVisible(node);
|
---|
| 182 | }
|
---|
| 183 | else // reset visibility classification
|
---|
| 184 | {
|
---|
| 185 | node->SetVisible(false);
|
---|
| 186 | }
|
---|
| 187 | }
|
---|
[2767] | 188 |
|
---|
[2770] | 189 | // always traverse a node if it was previously visible
|
---|
[2767] | 190 | if (wasVisible)
|
---|
[3251] | 191 | {
|
---|
[2767] | 192 | TraverseNode(node);
|
---|
[3251] | 193 | }
|
---|
[2767] | 194 | }
|
---|
| 195 | }
|
---|
| 196 | else
|
---|
| 197 | {
|
---|
| 198 | // for stats
|
---|
| 199 | ++ mStats.mNumFrustumCulledNodes;
|
---|
| 200 | }
|
---|
| 201 | }
|
---|
[2770] | 202 |
|
---|
[2771] | 203 | // distance queue empty: feed the remaining multiqueries to
|
---|
| 204 | // be able to proceed traversal
|
---|
[2770] | 205 | if (mDistanceQueue.empty())
|
---|
| 206 | {
|
---|
| 207 | IssueMultiQueries();
|
---|
| 208 | }
|
---|
[2767] | 209 | }
|
---|
[2770] | 210 |
|
---|
[2771] | 211 | // render the rest of the objects
|
---|
[2795] | 212 | if (mUseRenderQueue) ApplyRenderQueue();
|
---|
[2771] | 213 |
|
---|
| 214 |
|
---|
[2770] | 215 | //////////////
|
---|
| 216 | //-- issue remaining previously visible node queries
|
---|
| 217 |
|
---|
| 218 | while (!mVQueue.empty())
|
---|
| 219 | {
|
---|
| 220 | BvhNode *node = mVQueue.front();
|
---|
| 221 | mVQueue.pop();
|
---|
| 222 |
|
---|
[2792] | 223 | OcclusionQuery *query = IssueOcclusionQuery(node);
|
---|
[2770] | 224 | mQueryQueue.push(query);
|
---|
| 225 | }
|
---|
| 226 |
|
---|
| 227 | while (!mQueryQueue.empty())
|
---|
| 228 | {
|
---|
| 229 | OcclusionQuery *query = mQueryQueue.front();
|
---|
| 230 | mQueryQueue.pop();
|
---|
| 231 |
|
---|
[2772] | 232 | HandleQueryResult(query);
|
---|
[2770] | 233 | }
|
---|
[2864] | 234 |
|
---|
| 235 | //cout << "returned queries: " << returnedQueries << " waited for queries: " << waitedForQueries << " (=" << 100.0f * waitedForQueries / returnedQueries << "%)" << endl;
|
---|
[2755] | 236 | }
|
---|
| 237 |
|
---|
[2770] | 238 |
|
---|
| 239 | void CHCPlusPlusTraverser::QueryPreviouslyInvisibleNodes(BvhNode *node)
|
---|
| 240 | {
|
---|
[2800] | 241 | mIQueue.push_back(node);
|
---|
[2770] | 242 |
|
---|
[2771] | 243 | if (mIQueue.size() > mMaxBatchSize)
|
---|
[2770] | 244 | {
|
---|
| 245 | IssueMultiQueries();
|
---|
| 246 | }
|
---|
| 247 | }
|
---|
| 248 |
|
---|
| 249 |
|
---|
[2800] | 250 | OcclusionQuery * CHCPlusPlusTraverser::GetNextMultiQuery(BvhNodeContainer &iqueue)
|
---|
[2773] | 251 | {
|
---|
| 252 | OcclusionQuery *query = mQueryHandler.RequestQuery();
|
---|
| 253 |
|
---|
| 254 | float pFail = 1.0f;
|
---|
| 255 | float maxBatchVal = 0.0f;
|
---|
| 256 | float newPBatch = 1.0f;
|
---|
| 257 | float newBatchVal;
|
---|
| 258 |
|
---|
| 259 | // issue next query
|
---|
| 260 | while (!iqueue.empty())
|
---|
| 261 | {
|
---|
[2800] | 262 | BvhNode *node = iqueue.back();
|
---|
| 263 |
|
---|
| 264 | // node was already part of a mulitquery => avoid recursion
|
---|
| 265 | if (node->GetLastQueriedFrame() == mFrameId)
|
---|
[3259] | 266 | {
|
---|
[2800] | 267 | newPBatch = 0;
|
---|
[3259] | 268 | }
|
---|
[2800] | 269 | else
|
---|
[3259] | 270 | {
|
---|
[3258] | 271 | newPBatch *= mVisibilityPredictor.GetProbability(node);
|
---|
[3259] | 272 | }
|
---|
[2773] | 273 |
|
---|
| 274 | if (query->GetNodes().empty())
|
---|
[2774] | 275 | {
|
---|
[2800] | 276 | // single node will never cause a wasted query
|
---|
[2773] | 277 | newBatchVal = 1.0f;
|
---|
[2774] | 278 | }
|
---|
[2773] | 279 | else
|
---|
| 280 | {
|
---|
| 281 | int newSize = query->GetSize() + 1;
|
---|
| 282 | newBatchVal = newSize / (1.0f + (1.0f - newPBatch) * newSize);
|
---|
| 283 | }
|
---|
| 284 |
|
---|
[3259] | 285 | if (newBatchVal <= maxBatchVal) break;
|
---|
[2773] | 286 |
|
---|
[2800] | 287 | iqueue.pop_back();
|
---|
[2773] | 288 | query->AddNode(node);
|
---|
| 289 |
|
---|
| 290 | maxBatchVal = newBatchVal;
|
---|
| 291 | }
|
---|
| 292 |
|
---|
[2776] | 293 | //cout <<"size: " << query->GetSize() << endl;
|
---|
[2792] | 294 | IssueOcclusionQuery(*query);
|
---|
[2773] | 295 |
|
---|
| 296 | return query;
|
---|
| 297 | }
|
---|
| 298 |
|
---|
| 299 |
|
---|
[2800] | 300 | static inline bool lt(BvhNode *a, BvhNode *b)
|
---|
| 301 | {
|
---|
| 302 | return a->GetTimesTestedInvisible() < b->GetTimesTestedInvisible();
|
---|
| 303 | }
|
---|
| 304 |
|
---|
| 305 |
|
---|
[2770] | 306 | void CHCPlusPlusTraverser::IssueMultiQueries()
|
---|
| 307 | {
|
---|
[2800] | 308 | if (mUseMultiQueries)
|
---|
[2770] | 309 | {
|
---|
[2800] | 310 | // sort queries by #times invisible
|
---|
| 311 | sort(mIQueue.begin(), mIQueue.end(), lt);
|
---|
[2774] | 312 |
|
---|
[2800] | 313 | while (!mIQueue.empty())
|
---|
[3259] | 314 | {
|
---|
[2800] | 315 | mQueryQueue.push(GetNextMultiQuery(mIQueue));
|
---|
[3259] | 316 | }
|
---|
[3038] | 317 | }
|
---|
| 318 | else
|
---|
| 319 | {
|
---|
[2800] | 320 | BvhNodeContainer::const_iterator it, it_end = mIQueue.end();
|
---|
[2770] | 321 |
|
---|
[2800] | 322 | for (it = mIQueue.begin(); it != it_end; ++ it)
|
---|
[3259] | 323 | {
|
---|
[2800] | 324 | mQueryQueue.push(IssueOcclusionQuery(*it));
|
---|
[3259] | 325 | }
|
---|
[2800] | 326 |
|
---|
| 327 | mIQueue.clear();
|
---|
[2770] | 328 | }
|
---|
| 329 | }
|
---|
| 330 |
|
---|
| 331 |
|
---|
[2790] | 332 | }
|
---|