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