[8] | 1 | #include "RenderTraverser.h" |
---|
| 2 | #include "glInterface.h" |
---|
| 3 | #include "Timers.h" |
---|
| 4 | |
---|
| 5 | extern "C" |
---|
| 6 | { |
---|
| 7 | #include "MathStuff.h" |
---|
| 8 | } |
---|
| 9 | |
---|
| 10 | |
---|
| 11 | RenderTraverser::RenderTraverser(): mFrameID(1), mVisibilityThreshold(0), |
---|
| 12 | mHierarchyRoot(NULL), mOcclusionQueries(NULL), mCurrentTestIdx(0), mIsQueryMode(false), |
---|
| 13 | mNumTraversedNodes(0), mNumQueryCulledNodes(0), mNumFrustumCulledNodes(0), |
---|
| 14 | mRenderTime(0), mNumRenderedGeometry(0), mUseOptimization(true) |
---|
| 15 | { |
---|
| 16 | } |
---|
| 17 | |
---|
| 18 | RenderTraverser::~RenderTraverser() |
---|
| 19 | { |
---|
| 20 | if(mOcclusionQueries) |
---|
| 21 | delete [] mOcclusionQueries; |
---|
| 22 | } |
---|
| 23 | |
---|
| 24 | void RenderTraverser::Render(int mode) |
---|
| 25 | { |
---|
| 26 | mDistanceQueue.push(mHierarchyRoot); |
---|
| 27 | |
---|
| 28 | long startTime = getTime(); |
---|
| 29 | |
---|
| 30 | Preprocess(); |
---|
| 31 | |
---|
| 32 | switch(mode) |
---|
| 33 | { |
---|
| 34 | case RENDER_CULL_FRUSTUM: |
---|
| 35 | RenderCullFrustum(); |
---|
| 36 | break; |
---|
| 37 | case RENDER_STOP_AND_WAIT: |
---|
| 38 | RenderStopAndWait(); |
---|
| 39 | break; |
---|
| 40 | case RENDER_COHERENT: |
---|
| 41 | RenderCoherentWithQueue(); |
---|
| 42 | break; |
---|
| 43 | default: |
---|
| 44 | RenderCullFrustum(); |
---|
| 45 | break; |
---|
| 46 | } |
---|
| 47 | |
---|
| 48 | mFrameID ++; |
---|
| 49 | ResetQueries(); |
---|
| 50 | |
---|
| 51 | long endTime = getTime(); |
---|
| 52 | mRenderTime = endTime - startTime; |
---|
| 53 | |
---|
| 54 | finishTiming(); |
---|
| 55 | } |
---|
| 56 | |
---|
| 57 | /** |
---|
| 58 | This is the standard render traversal algorithm doing only frustum culling |
---|
| 59 | */ |
---|
| 60 | void RenderTraverser::RenderCullFrustum() |
---|
| 61 | { |
---|
| 62 | while(!mDistanceQueue.empty()) |
---|
| 63 | { |
---|
| 64 | HierarchyNode *node = mDistanceQueue.top(); |
---|
| 65 | mDistanceQueue.pop(); |
---|
| 66 | |
---|
| 67 | // interesting for the visualization, so rest and set |
---|
| 68 | node->SetVisible(false); |
---|
| 69 | mNumTraversedNodes ++; |
---|
| 70 | |
---|
| 71 | bool intersects; |
---|
| 72 | |
---|
| 73 | if(InsideViewFrustum(node, intersects)) |
---|
| 74 | { |
---|
| 75 | // update node's visited flag => needed for rendering |
---|
| 76 | // so set it also here |
---|
| 77 | node->SetLastVisited(mFrameID); |
---|
| 78 | node->SetVisible(true); |
---|
| 79 | TraverseNode(node); |
---|
| 80 | } |
---|
| 81 | else |
---|
| 82 | { |
---|
| 83 | mNumFrustumCulledNodes ++; |
---|
| 84 | } |
---|
| 85 | } |
---|
| 86 | } |
---|
| 87 | |
---|
| 88 | void RenderTraverser::RenderStopAndWait() |
---|
| 89 | { |
---|
| 90 | while(! mDistanceQueue.empty()) |
---|
| 91 | { |
---|
| 92 | HierarchyNode *node = mDistanceQueue.top(); |
---|
| 93 | mDistanceQueue.pop(); |
---|
| 94 | mNumTraversedNodes ++; |
---|
| 95 | // interesting for the visualization, so rest and set |
---|
| 96 | node->SetVisible(false); |
---|
| 97 | |
---|
| 98 | bool intersects; |
---|
| 99 | |
---|
| 100 | if(InsideViewFrustum(node, intersects)) |
---|
| 101 | { |
---|
| 102 | // update node's visited flag |
---|
| 103 | node->SetLastVisited(mFrameID); |
---|
| 104 | |
---|
| 105 | // for near plane intersecting abbs possible |
---|
| 106 | // wrong results => skip occlusion query |
---|
| 107 | if(intersects) |
---|
| 108 | { |
---|
| 109 | node->SetVisible(true); |
---|
| 110 | TraverseNode(node); |
---|
| 111 | } |
---|
| 112 | else |
---|
| 113 | { |
---|
| 114 | IssueOcclusionQuery(node, false); |
---|
| 115 | |
---|
| 116 | // wait if result not available |
---|
| 117 | int visiblePixels = GetOcclusionQueryResult(node); |
---|
| 118 | |
---|
| 119 | // node visible |
---|
| 120 | if(visiblePixels > mVisibilityThreshold) |
---|
| 121 | { |
---|
| 122 | node->SetVisible(true); |
---|
| 123 | TraverseNode(node); |
---|
| 124 | } |
---|
| 125 | else |
---|
| 126 | { |
---|
| 127 | mNumQueryCulledNodes ++; |
---|
| 128 | } |
---|
| 129 | } |
---|
| 130 | } |
---|
| 131 | else |
---|
| 132 | { |
---|
| 133 | mNumFrustumCulledNodes ++; |
---|
| 134 | } |
---|
| 135 | } |
---|
| 136 | } |
---|
| 137 | |
---|
| 138 | void RenderTraverser::RenderCoherentWithQueue() |
---|
| 139 | { |
---|
| 140 | QueryQueue queryQueue; |
---|
| 141 | |
---|
| 142 | //-- PART 1: process finished occlusion queries |
---|
| 143 | while(!mDistanceQueue.empty() || !queryQueue.empty()) |
---|
| 144 | { |
---|
| 145 | while(!queryQueue.empty() && |
---|
| 146 | (ResultAvailable(queryQueue.front()) || mDistanceQueue.empty())) |
---|
| 147 | { |
---|
| 148 | HierarchyNode *node = queryQueue.front(); |
---|
| 149 | queryQueue.pop(); |
---|
| 150 | |
---|
| 151 | // wait until result available |
---|
| 152 | int visiblePixels = GetOcclusionQueryResult(node); |
---|
| 153 | |
---|
| 154 | if(visiblePixels > mVisibilityThreshold) |
---|
| 155 | { |
---|
| 156 | PullUpVisibility(node); |
---|
| 157 | TraverseNode(node); |
---|
| 158 | } |
---|
| 159 | else |
---|
| 160 | { |
---|
| 161 | mNumQueryCulledNodes ++; |
---|
| 162 | } |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | //-- PART 2: hierarchical traversal |
---|
| 166 | if(! mDistanceQueue.empty()) |
---|
| 167 | { |
---|
| 168 | HierarchyNode *node = mDistanceQueue.top(); |
---|
| 169 | |
---|
| 170 | mDistanceQueue.pop(); |
---|
| 171 | |
---|
| 172 | mNumTraversedNodes ++; |
---|
| 173 | |
---|
| 174 | bool intersects; |
---|
| 175 | |
---|
| 176 | if(InsideViewFrustum(node, intersects)) |
---|
| 177 | { |
---|
| 178 | // for near plane intersecting abbs possible |
---|
| 179 | // wrong results => skip occlusion query |
---|
| 180 | if(intersects) |
---|
| 181 | { |
---|
| 182 | // update node's visited flag |
---|
| 183 | node->SetLastVisited(mFrameID); |
---|
| 184 | |
---|
| 185 | PullUpVisibility(node); |
---|
| 186 | TraverseNode(node); |
---|
| 187 | } |
---|
| 188 | else |
---|
| 189 | { |
---|
| 190 | // identify previously visible nodes |
---|
| 191 | bool wasVisible = node->Visible() && (node->LastVisited() == mFrameID - 1); |
---|
| 192 | |
---|
| 193 | // identify nodes that we cannot skip queries for |
---|
| 194 | bool leafOrWasInvisible = !wasVisible || node->IsLeaf(); |
---|
| 195 | |
---|
| 196 | // reset node's visibility classification |
---|
| 197 | node->SetVisible(false); |
---|
| 198 | |
---|
| 199 | // update node's visited flag |
---|
| 200 | node->SetLastVisited(mFrameID); |
---|
| 201 | |
---|
| 202 | // skip testing previously visible interior nodes |
---|
| 203 | if(leafOrWasInvisible) |
---|
| 204 | { |
---|
| 205 | IssueOcclusionQuery(node, wasVisible); |
---|
| 206 | queryQueue.push(node); |
---|
| 207 | } |
---|
| 208 | |
---|
| 209 | // always traverse a node if it was visible |
---|
| 210 | if(wasVisible) |
---|
| 211 | TraverseNode(node); |
---|
| 212 | } |
---|
| 213 | } |
---|
| 214 | else |
---|
| 215 | { |
---|
| 216 | // for stats |
---|
| 217 | mNumFrustumCulledNodes ++; |
---|
| 218 | } |
---|
| 219 | } |
---|
| 220 | } |
---|
| 221 | } |
---|
| 222 | |
---|
| 223 | void RenderTraverser::TraverseNode(HierarchyNode *node) |
---|
| 224 | { |
---|
| 225 | if(node->IsLeaf()) |
---|
| 226 | mNumRenderedGeometry += node->Render(); |
---|
| 227 | else |
---|
| 228 | { |
---|
| 229 | // for non leafs this renders only the bounding volume (if the flag is set) |
---|
| 230 | //node->Render(); |
---|
| 231 | mDistanceQueue.push(node->GetLeftChild()); |
---|
| 232 | mDistanceQueue.push(node->GetRightChild()); |
---|
| 233 | } |
---|
| 234 | } |
---|
| 235 | |
---|
| 236 | void RenderTraverser::RenderVisualization() |
---|
| 237 | { |
---|
| 238 | mDistanceQueue.push(mHierarchyRoot); |
---|
| 239 | |
---|
| 240 | while(! mDistanceQueue.empty()) |
---|
| 241 | { |
---|
| 242 | HierarchyNode *node = mDistanceQueue.top(); |
---|
| 243 | mDistanceQueue.pop(); |
---|
| 244 | |
---|
| 245 | // identify previously visible nodes |
---|
| 246 | bool wasVisible = node->Visible() && (node->LastVisited() == mFrameID - 1); |
---|
| 247 | |
---|
| 248 | if(wasVisible) |
---|
| 249 | TraverseNode(node); |
---|
| 250 | else |
---|
| 251 | { |
---|
| 252 | // also render culled nodes |
---|
| 253 | glColor3f(1.0,0.0,0.0); |
---|
| 254 | node->RenderBoundingVolumeForVisualization(); |
---|
| 255 | } |
---|
| 256 | } |
---|
| 257 | } |
---|
| 258 | |
---|
| 259 | |
---|
| 260 | void RenderTraverser::PullUpVisibility(HierarchyNode *node) |
---|
| 261 | { |
---|
| 262 | while(node && !node->Visible()) |
---|
| 263 | { |
---|
| 264 | node->SetVisible(true); |
---|
| 265 | node = node->GetParent(); |
---|
| 266 | } |
---|
| 267 | } |
---|
| 268 | |
---|
| 269 | bool RenderTraverser::ResultAvailable(HierarchyNode *node) |
---|
| 270 | { |
---|
| 271 | int result; |
---|
| 272 | |
---|
| 273 | glGetQueryivARB(node->GetOcclusionQuery(), |
---|
| 274 | GL_QUERY_RESULT_AVAILABLE_ARB, &result); |
---|
| 275 | |
---|
| 276 | return (result == GL_TRUE); |
---|
| 277 | } |
---|
| 278 | |
---|
| 279 | void RenderTraverser::SetHierarchy(HierarchyNode *sceneRoot) |
---|
| 280 | { |
---|
| 281 | mHierarchyRoot = sceneRoot; |
---|
| 282 | |
---|
| 283 | // not valid anymore for new hierarchy => delete |
---|
| 284 | delete [] mOcclusionQueries; |
---|
| 285 | mOcclusionQueries = NULL; |
---|
| 286 | } |
---|
| 287 | |
---|
| 288 | HierarchyNode *RenderTraverser::GetHierarchy() |
---|
| 289 | { |
---|
| 290 | return mHierarchyRoot; |
---|
| 291 | } |
---|
| 292 | |
---|
| 293 | int RenderTraverser::GetOcclusionQueryResult(HierarchyNode *node) |
---|
| 294 | { |
---|
| 295 | unsigned int result; |
---|
| 296 | |
---|
| 297 | glGetQueryObjectuivARB(node->GetOcclusionQuery(), GL_QUERY_RESULT_ARB, &result); |
---|
| 298 | |
---|
| 299 | return (int)result; |
---|
| 300 | } |
---|
| 301 | |
---|
| 302 | |
---|
| 303 | void RenderTraverser::Switch2GLQueryState() |
---|
| 304 | { |
---|
| 305 | // boolean used to avoid unnecessary state changes |
---|
| 306 | if(!mIsQueryMode) |
---|
| 307 | { |
---|
| 308 | glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE); |
---|
| 309 | glDepthMask(GL_FALSE); |
---|
| 310 | glDisable(GL_LIGHTING); |
---|
| 311 | mIsQueryMode = true; |
---|
| 312 | } |
---|
| 313 | } |
---|
| 314 | |
---|
| 315 | |
---|
| 316 | void RenderTraverser::Switch2GLRenderState() |
---|
| 317 | { |
---|
| 318 | // boolean used to avoid unnecessary state changes |
---|
| 319 | if(mIsQueryMode) |
---|
| 320 | { |
---|
| 321 | // switch back to rendermode |
---|
| 322 | glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); |
---|
| 323 | glDepthMask(GL_TRUE); |
---|
| 324 | glEnable(GL_LIGHTING); |
---|
| 325 | mIsQueryMode = false; |
---|
| 326 | } |
---|
| 327 | } |
---|
| 328 | |
---|
| 329 | void RenderTraverser::IssueOcclusionQuery(HierarchyNode *node, bool wasVisible) |
---|
| 330 | { |
---|
| 331 | // get next available test id |
---|
| 332 | unsigned int occlusionQuery = mOcclusionQueries[mCurrentTestIdx++]; |
---|
| 333 | |
---|
| 334 | node->SetOcclusionQuery(occlusionQuery); |
---|
| 335 | // do the actual occlusion query for this node |
---|
| 336 | glBeginQueryARB(GL_SAMPLES_PASSED_ARB, occlusionQuery); |
---|
| 337 | |
---|
| 338 | // if leaf and was visible => will be rendered anyway, thus we |
---|
| 339 | // can also test with the real geometry |
---|
| 340 | if(node->IsLeaf() && wasVisible && mUseOptimization) |
---|
| 341 | { |
---|
| 342 | mNumRenderedGeometry += node->Render(); |
---|
| 343 | } |
---|
| 344 | else |
---|
| 345 | { |
---|
| 346 | // change state so the bounding box gets not actually rendered on the screen |
---|
| 347 | Switch2GLQueryState(); |
---|
| 348 | node->RenderBoundingVolume(); |
---|
| 349 | Switch2GLRenderState(); |
---|
| 350 | } |
---|
| 351 | |
---|
| 352 | glEndQueryARB(GL_SAMPLES_PASSED_ARB); |
---|
| 353 | } |
---|
| 354 | |
---|
| 355 | void RenderTraverser::Preprocess() |
---|
| 356 | { |
---|
| 357 | if(!mOcclusionQueries) |
---|
| 358 | { |
---|
| 359 | mOcclusionQueries = new unsigned int[mHierarchyRoot->GetNumHierarchyNodes()]; |
---|
| 360 | } |
---|
| 361 | |
---|
| 362 | // view frustum planes for view frustum culling |
---|
| 363 | calcViewFrustumPlanes(&mClipPlanes, mProjViewMatrix); |
---|
| 364 | calcAABNPVertexIndices(mNPVertexIndices, mClipPlanes); |
---|
| 365 | // generate ids for occlusion test |
---|
| 366 | glGenQueriesARB(mHierarchyRoot->GetNumHierarchyNodes(), mOcclusionQueries); |
---|
| 367 | mCurrentTestIdx = 0; |
---|
| 368 | |
---|
| 369 | // reset statistics |
---|
| 370 | mNumTraversedNodes = 0; |
---|
| 371 | mNumQueryCulledNodes = 0; |
---|
| 372 | mNumFrustumCulledNodes = 0; |
---|
| 373 | mNumRenderedGeometry = 0; |
---|
| 374 | } |
---|
| 375 | |
---|
| 376 | |
---|
| 377 | void RenderTraverser::ResetQueries() |
---|
| 378 | { |
---|
| 379 | // tell the driver that the occlusion queries won't be needed any more |
---|
| 380 | glDeleteQueriesARB(mHierarchyRoot->GetNumHierarchyNodes(), mOcclusionQueries); |
---|
| 381 | } |
---|
| 382 | |
---|
| 383 | |
---|
| 384 | void RenderTraverser::SetViewpoint(Vector3 const &viewpoint) |
---|
| 385 | { |
---|
| 386 | copyVector3(mViewpoint, viewpoint); |
---|
| 387 | } |
---|
| 388 | |
---|
| 389 | |
---|
| 390 | void RenderTraverser::SetProjViewMatrix(Matrix4x4 const &projViewMatrix) |
---|
| 391 | { |
---|
| 392 | copyMatrix(mProjViewMatrix, projViewMatrix); |
---|
| 393 | } |
---|
| 394 | |
---|
| 395 | |
---|
| 396 | bool RenderTraverser::InsideViewFrustum(HierarchyNode *node, bool &intersects) |
---|
| 397 | { |
---|
| 398 | Vector3x8 vertices; |
---|
| 399 | |
---|
| 400 | bool intersect = false; |
---|
| 401 | |
---|
| 402 | calcAABoxPoints(vertices, node->GetBoundingVolume()); |
---|
| 403 | |
---|
| 404 | // simply test all 6 vertices |
---|
| 405 | for (int i = 0; i < 6; i++) |
---|
| 406 | { |
---|
| 407 | // test the n-vertex |
---|
| 408 | // note: the calcAABNearestVertexId should be preprocessed |
---|
| 409 | if(!pointBeforePlane(mClipPlanes.plane[i], vertices[mNPVertexIndices[i * 2]])) |
---|
| 410 | { |
---|
| 411 | // outside |
---|
| 412 | return false; |
---|
| 413 | } |
---|
| 414 | } |
---|
| 415 | |
---|
| 416 | // test if bounding box is intersected by nearplane (using the p-vertex) |
---|
| 417 | intersects = (!pointBeforePlane(mClipPlanes.plane[5], vertices[mNPVertexIndices[11]])); |
---|
| 418 | |
---|
| 419 | // -- get vector from viewpoint to center of bounding volume |
---|
| 420 | Vector3 vec;
|
---|
| 421 | calcAABoxCenter(vec, node->GetBoundingVolume());
|
---|
| 422 | diffVector3(vec, vec, mViewpoint);
|
---|
| 423 |
|
---|
| 424 | // compute distance from nearest point to viewpoint
|
---|
| 425 | diffVector3(vec, vertices[calcAABNearestVertexIdx(vec)], mViewpoint);
|
---|
| 426 | node->SetDistance(squaredLength(vec));
|
---|
| 427 | |
---|
| 428 | return true; |
---|
| 429 | } |
---|
| 430 | |
---|
| 431 | |
---|
| 432 | void RenderTraverser::SetVisibilityThreshold(int threshold) |
---|
| 433 | { |
---|
| 434 | mVisibilityThreshold = threshold; |
---|
| 435 | } |
---|
| 436 | |
---|
| 437 | long RenderTraverser::GetRenderTime() |
---|
| 438 | { |
---|
| 439 | return mRenderTime; |
---|
| 440 | } |
---|
| 441 | |
---|
| 442 | int RenderTraverser::GetNumTraversedNodes() |
---|
| 443 | { |
---|
| 444 | return mNumTraversedNodes; |
---|
| 445 | } |
---|
| 446 | |
---|
| 447 | int RenderTraverser::GetNumQueryCulledNodes() |
---|
| 448 | { |
---|
| 449 | return mNumQueryCulledNodes; |
---|
| 450 | } |
---|
| 451 | |
---|
| 452 | int RenderTraverser::GetNumFrustumCulledNodes() |
---|
| 453 | { |
---|
| 454 | return mNumFrustumCulledNodes; |
---|
| 455 | } |
---|
| 456 | |
---|
| 457 | |
---|
| 458 | int RenderTraverser::GetNumRenderedGeometry() |
---|
| 459 | { |
---|
| 460 | return mNumRenderedGeometry; |
---|
| 461 | } |
---|
| 462 | |
---|
| 463 | |
---|
| 464 | int RenderTraverser::GetVisibilityThreshold() |
---|
| 465 | { |
---|
| 466 | return mVisibilityThreshold; |
---|
| 467 | } |
---|
| 468 | |
---|
| 469 | void RenderTraverser::SetUseOptimization(bool useOptimization) |
---|
| 470 | { |
---|
| 471 | mUseOptimization = useOptimization; |
---|
| 472 | printf("using opt %d\n", mUseOptimization); |
---|
| 473 | } |
---|