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