00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #include <cstdlib>
00040 #include <cstdio>
00041 #include <cmath>
00042
00043 #include "OSGConfig.h"
00044
00045 #include "OSGWindow.h"
00046 #include "OSGGL.h"
00047 #include "OSGGLU.h"
00048 #include "OSGGLEXT.h"
00049 #include "OSGBaseFields.h"
00050 #include "OSGRenderTreeNodePool.h"
00051 #include "OSGOcclusionCullingTreeBuilder.h"
00052 #include "OSGBaseFunctions.h"
00053 #include "OSGBaseInitFunctions.h"
00054 #include "OSGRenderPartitionBase.h"
00055 #include "OSGRenderAction.h"
00056 #include "OSGVolumeDraw.h"
00057
00058 #include "OSGDepthChunk.h"
00059 #include "OSGColorMaskChunk.h"
00060 #include "OSGPolygonChunk.h"
00061 #include "OSGDrawableStatsAttachment.h"
00062
00063
00064
00065 OSG_USING_NAMESPACE
00066
00071 OcclusionCullingTreeBuilder OcclusionCullingTreeBuilder::Proto;
00072
00073 UInt32 OcclusionCullingTreeBuilder::_extOcclusionQuery= Window::invalidExtensionID;
00074 UInt32 OcclusionCullingTreeBuilder::_funcGenQueriesARB= Window::invalidFunctionID;
00075 UInt32 OcclusionCullingTreeBuilder::_funcGetQueryObjectuivARB= Window::invalidFunctionID;
00076 UInt32 OcclusionCullingTreeBuilder::_funcBeginQueryARB= Window::invalidFunctionID;
00077 UInt32 OcclusionCullingTreeBuilder::_funcEndQueryARB= Window::invalidFunctionID;
00078
00079
00080 StatElemDesc<StatIntElem> OcclusionCullingTreeBuilder::statNOccNodes(
00081 "OC-Nodes",
00082 "total number of nodes tested for occlusion");
00083
00084 StatElemDesc<StatIntElem> OcclusionCullingTreeBuilder::statNOccTests(
00085 "OC-Tests",
00086 "number of occlusion tests");
00087 StatElemDesc<StatIntElem> OcclusionCullingTreeBuilder::statNOccInvisible(
00088 "OC-Invisible",
00089 "number of nodes found invisible through occlusion");
00090
00091 StatElemDesc<StatRealElem> OcclusionCullingTreeBuilder::statNOccSuccessTestPer(
00092 "OC-Sucess",
00093 "percentage of successful tests for occlusion");
00094
00095 StatElemDesc<StatIntElem> OcclusionCullingTreeBuilder::statNOccTriangles(
00096 "OC-Triangles",
00097 "number of triangles culled");
00098
00099
00100
00101 bool OcclusionCullingTreeBuilder::_isOccStateCreated = false;
00102 StateMTRecPtr OcclusionCullingTreeBuilder::_testingStatePtr;
00103 State *OcclusionCullingTreeBuilder::_testingState;
00104
00105
00106 OcclusionCullingTreeBuilder::SortModeE OcclusionCullingTreeBuilder::_sortMode =
00107 OcclusionCullingTreeBuilder::ModeAdaptiveBucket;
00108 UInt32 OcclusionCullingTreeBuilder::_nBuckets = 1000;
00109
00110
00111
00112
00113 typedef void (OSG_APIENTRY *GenQueryT)(GLuint n, GLuint* ids);
00114 typedef void (OSG_APIENTRY *GetQueryObjectuivT)(GLuint id, GLenum pname,
00115 GLuint* param);
00116 typedef void (OSG_APIENTRY *BeginQueryT)(GLenum target, GLuint id);
00117 typedef void (OSG_APIENTRY *EndQueryT)(GLenum target);
00118
00119
00121 static bool initOccTreeBuilder(void)
00122 {
00123 addPostFactoryInitFunction(&OcclusionCullingTreeBuilder::staticInit);
00124
00125 return true;
00126 }
00127
00128 static OSG::StaticInitFuncWrapper registerOccTreeInitWrapper(
00129 initOccTreeBuilder);
00130
00131 bool OcclusionCullingTreeBuilder::staticInit(void)
00132 {
00133 _extOcclusionQuery = Window::registerExtension("GL_ARB_occlusion_query");
00134
00135 _funcGenQueriesARB = Window::registerFunction
00136 (OSG_DLSYM_UNDERSCORE"glGenQueriesARB", _extOcclusionQuery);
00137 _funcBeginQueryARB = Window::registerFunction
00138 (OSG_DLSYM_UNDERSCORE"glBeginQueryARB", _extOcclusionQuery);
00139 _funcEndQueryARB = Window::registerFunction
00140 (OSG_DLSYM_UNDERSCORE"glEndQueryARB", _extOcclusionQuery);
00141 _funcGetQueryObjectuivARB = Window::registerFunction
00142 (OSG_DLSYM_UNDERSCORE"glGetQueryObjectuivARB", _extOcclusionQuery);
00143
00144 return true;
00145 }
00146
00147
00148
00149
00150
00151 OcclusionCullingTreeBuilder::OcclusionCullingTreeBuilder(void)
00152 : uNumNodes (0),
00153 _numTestSamples(0),
00154 _isOccSetup (false),
00155 _currSample (0),
00156 _rt (NULL)
00157 {
00158 _buckets.clear();
00159 _buckets.resize(_nBuckets);
00160 _bucketsWork.clear();
00161 _bucketsWork.resize(_nBuckets);
00162 }
00163
00164 OcclusionCullingTreeBuilder::~OcclusionCullingTreeBuilder(void)
00165 {
00166
00167 }
00168
00169
00170 void OcclusionCullingTreeBuilder::reset(void)
00171 {
00172 TreeBuilderBase::reset();
00173 uNumNodes=0;
00174
00175 if(_buckets.size() != _nBuckets)
00176 {
00177 _buckets.resize(_nBuckets);
00178 _bucketsWork.resize(_nBuckets);
00179 }
00180
00181 std::vector<RenderTreeNode*>::iterator it, e;
00182
00183 for(it = _buckets.begin(), e = _buckets.end();
00184 it != e; ++it)
00185 {
00186 *it = NULL;
00187 }
00188
00189 for(it = _bucketsWork.begin(), e = _bucketsWork.end();
00190 it != e; ++it)
00191 {
00192 *it = NULL;
00193 }
00194
00195 _bucketLow = 0.f;
00196 _bucketHigh = 0.f;
00197 _bucketScale = 0.f;
00198
00199 _rt = NULL;
00200 }
00201
00202
00205 OcclusionCullingTreeBuilder::SortModeE
00206 OcclusionCullingTreeBuilder::setSortMode(SortModeE mode)
00207 {
00208 SortModeE o = _sortMode;
00209 _sortMode = _sortMode;
00210
00211 return o;
00212 }
00213
00216 UInt32 OcclusionCullingTreeBuilder::setNBuckets(UInt32 nbuckets)
00217 {
00218 UInt32 o = _nBuckets;
00219 _nBuckets = nbuckets;
00220
00221 return o;
00222 }
00223
00224
00225 inline
00226 void OcclusionCullingTreeBuilder::enterTesting(DrawEnv &denv,
00227 RenderPartitionBase *part)
00228 {
00229 if(!_inTesting)
00230 {
00231 _inTesting = true;
00232
00233 denv.activateState(_testingState, NULL);
00234 }
00235 }
00236
00237 inline
00238 void OcclusionCullingTreeBuilder::leaveTesting(DrawEnv &denv,
00239 RenderPartitionBase *part)
00240 {
00241 _inTesting = false;
00242 }
00243
00244 void OcclusionCullingTreeBuilder::draw(DrawEnv &denv,
00245 RenderPartitionBase *part)
00246 {
00247 #if 1 //CHECK_ENV_ACTION
00248
00249 Window* win = denv.getWindow();
00250
00251 if(_sortMode == ModeAdaptiveBucket)
00252 {
00253
00254 for(UInt32 i = 0; i < _nBuckets; ++i)
00255 {
00256 if(_buckets[i] != NULL)
00257 {
00258 _pRoot->addChild(_buckets[i]);
00259 }
00260 }
00261 }
00262
00263 if(!win->hasExtension(_extOcclusionQuery))
00264 {
00265
00266 SLOG << "Missing OCC GL extensions!!" << endLog;
00267 TreeBuilderBase::draw(denv,part);
00268 return;
00269 }
00270
00271
00272
00273
00274
00275 if(!_rt)
00276 {
00277 FFATAL(("OcclusionCullingTreeBuilder::draw: Action in denv is not a "
00278 "RenderAction!\n"));
00279 return;
00280 }
00281
00282 _uiActiveMatrix = 0;
00283 Real32 screenCoveredPercentage = 0.f;
00284 if(_rt->getOcclusionCullingQueryBufferSize() != _numTestSamples || !_isOccSetup)
00285 {
00286 _numTestSamples = _rt->getOcclusionCullingQueryBufferSize();
00287
00288 _testSamples.resize(_numTestSamples);
00289
00290
00291 GenQueryT genquer = reinterpret_cast<GenQueryT>(
00292 win->getFunction(_funcGenQueriesARB));
00293 genquer(_numTestSamples, &(_testSamples.front()));
00294 _isOccSetup = true;
00295 }
00296
00297 if(!_isOccStateCreated)
00298 {
00299 _isOccStateCreated = true;
00300
00301
00302 addPreFactoryExitFunction(&releaseTestingState);
00303
00304
00305 _testingStatePtr = State::create();
00306
00307 DepthChunkUnrecPtr dc = DepthChunk::create();
00308 dc->setReadOnly(true);
00309 _testingStatePtr->addChunk(dc);
00310
00311 ColorMaskChunkUnrecPtr cc = ColorMaskChunk::create();
00312 cc->setMaskR(false);
00313 cc->setMaskG(false);
00314 cc->setMaskB(false);
00315 cc->setMaskA(false);
00316 _testingStatePtr->addChunk(cc);
00317
00318 PolygonChunkUnrecPtr pc = PolygonChunk::create();
00319 pc->setCullFace(GL_BACK);
00320 _testingStatePtr->addChunk(pc);
00321
00322 commitChanges();
00323 }
00324
00325
00326
00327
00328
00329
00330 _vpWidth = denv.getPixelWidth();
00331 _vpHeight = denv.getPixelHeight();
00332
00333
00334
00335 _worldToScreen = denv.getVPWorldToScreen();
00336
00337 _testingState = &*_testingStatePtr;
00338
00339
00340 _minFeatureSize = _rt->getOcclusionCullingMinimumFeatureSize();
00341 _visPixelThreshold = _rt->getOcclusionCullingVisibilityThreshold();
00342 _coveredProbThreshold = _rt->getOcclusionCullingCoveredThreshold();
00343 _minTriangleCount = _rt->getOcclusionCullingMinimumTriangleCount();
00344 _inTesting = false;
00345
00346 _currSample = 0;
00347
00348 testNode(_pRoot, denv, part, screenCoveredPercentage);
00349
00350 StatCollector *sc = _rt->getStatCollector();
00351 if(sc != NULL)
00352 sc->getElem(statNOccNodes )->add(uNumNodes);
00353 uNumNodes=0;
00354 _uiActiveMatrix = 0;
00355
00356 leaveTesting(denv, part);
00357
00358
00359 while( !_testPendingNodes.empty() )
00360 {
00361 drawTestResults(denv, part);
00362 }
00363
00364
00365
00366
00367 if(sc != NULL)
00368 {
00369 Real32 percentage =
00370 Real32(sc->getElem(statNOccInvisible)->get()) /
00371 Real32(sc->getElem(statNOccTests)->get());
00372 sc->getElem(statNOccSuccessTestPer)->set(percentage);
00373 }
00374
00375
00376
00377
00378
00379
00380 uNumNodes=0;
00381 _currSample = 0;
00382
00383 #endif
00384 }
00385
00386 void OcclusionCullingTreeBuilder::testNode(RenderTreeNode *pNode,
00387 DrawEnv &denv,
00388 RenderPartitionBase *part,
00389 Real32 &scr_percent)
00390 {
00391 while (pNode != NULL)
00392 {
00393
00394 UInt32 uiNextMatrix = pNode->getMatrixStore().first;
00395
00396 if(uiNextMatrix != 0 && uiNextMatrix != _uiActiveMatrix)
00397 {
00398 glLoadMatrixf(pNode->getMatrixStore().second.getValues());
00399
00400 _uiActiveMatrix = uiNextMatrix;
00401
00402 _currMatrix.second = pNode->getMatrixStore().second;
00403
00404 updateTopMatrix(denv);
00405
00406 denv.setObjectToWorld(_accMatrix);
00407
00408 ++part->_uiNumMatrixChanges;
00409 }
00410
00411 const BoxVolume &volume = pNode->getVol();
00412 Pnt3r min,max;
00413
00414 volume.getBounds(min, max);
00415 Pnt3r p[8];
00416 p[0].setValues(min[0],min[1],min[2]);
00417 p[1].setValues(max[0],min[1],min[2]);
00418 p[2].setValues(min[0],max[1],min[2]);
00419 p[3].setValues(min[0],min[1],max[2]);
00420 p[4].setValues(max[0],max[1],min[2]);
00421 p[5].setValues(max[0],min[1],max[2]);
00422 p[6].setValues(min[0],max[1],max[2]);
00423 p[7].setValues(max[0],max[1],max[2]);
00424
00425
00426
00427
00428
00429 for(UInt32 i = 0; i<8;i++)
00430 {
00431
00432 denv.getObjectToWorld().mult (p[i], p[i]);
00433 _worldToScreen .multFull(p[i], p[i]);
00434
00435 }
00436 min=p[0];
00437 max=p[0];
00438 for(UInt32 i = 0; i<8; i++)
00439 {
00440 for(UInt32 j=0; j<2; j++)
00441 {
00442 if(p[i][j] < min[j])
00443 {
00444 min[j] = p[i][j];
00445 }
00446 if(p[i][j] > max[j])
00447 {
00448 max[j] = p[i][j];
00449 }
00450 }
00451 }
00452 max[0] = osgClamp(-1.f, max[0], 1.f);
00453 max[1] = osgClamp(-1.f, max[1], 1.f);
00454 min[0] = osgClamp(-1.f, min[0], 1.f);
00455 min[1] = osgClamp(-1.f, min[1], 1.f);
00456
00457
00458 Real32 cbb = (max[0] - min[0]) * (max[1] - min[1]) / 4.f;
00459
00460
00461
00462
00463
00464
00465 if(pNode->hasFunctor() == false)
00466 {
00467
00468 drawNode(pNode, denv, part);
00469 }
00470 else
00471 {
00472
00473
00474 if(cbb > scr_percent)
00475 {
00476 drawNode(pNode, denv, part);
00477
00478 }
00479 else
00480 {
00481
00482 Real32 pcov;
00483 pcov = sqrt(scr_percent) - sqrt(cbb);
00484 pcov *= pcov;
00485
00486
00487 if(pcov > _coveredProbThreshold || cbb < 0.001)
00488 {
00489
00490 DrawableStatsAttachment *st =
00491 DrawableStatsAttachment::get(pNode->getNode()->getCore());
00492 st->validate();
00493 UInt32 triangles = st->getTriangles();
00494
00495 if(cbb * _vpWidth * _vpHeight < _minFeatureSize)
00496 {
00497 StatCollector *sc = _rt->getStatCollector();
00498 if(sc != NULL)
00499 sc->getElem(statNOccTriangles)->
00500 add(triangles);
00501 if(_rt->getOcclusionCullingDebug() && pNode->getNode())
00502 {
00503 pNode->getNode()->setTravMask(
00504 pNode->getNode()->getTravMask() |
00505 _rt->getOcclusionCulledDebugMask()
00506 );
00507 }
00508 pNode->setIsRendered(true);
00509 }
00510 else if( triangles <= _minTriangleCount )
00511 {
00512 drawNode(pNode, denv, part);
00513 }
00514 else if((_testPendingNodes.size() == _numTestSamples - 1))
00515 {
00516 drawTestResults(denv, part);
00517 if(_testPendingNodes.size() == _numTestSamples - 1)
00518 {
00519 drawNode(pNode, denv, part);
00520 }
00521 else
00522 {
00523 drawTestNode(pNode, denv, part);
00524 }
00525 }
00526 else
00527 {
00528 drawTestNode(pNode, denv, part);
00529 }
00530 }
00531 else
00532 {
00533 drawNode(pNode, denv, part);
00534
00535 }
00536 }
00537 scr_percent += ((1.0 - scr_percent) * cbb);
00538 }
00539
00540
00541 if(pNode->getFirstChild() != NULL)
00542 {
00543 testNode(pNode->getFirstChild(), denv, part, scr_percent);
00544 }
00545
00546 pNode = pNode->getBrother();
00547 }
00548 }
00549
00550 void OcclusionCullingTreeBuilder::drawTestNode(RenderTreeNode *pNode,
00551 DrawEnv &denv,
00552 RenderPartitionBase *part)
00553 {
00554
00555
00556 while(_testPendingNodes.size() == _numTestSamples - 1)
00557 {
00558 drawTestResults(denv, part);
00559
00560 }
00561
00562
00563 Window* win = denv.getWindow();
00564 pNode->setIsRendered(false);
00565
00566
00567 if(_rt->getOcclusionCullingDebug() && pNode->getNode())
00568 {
00569 pNode->getNode()->setTravMask(
00570 pNode->getNode()->getTravMask() |
00571 _rt->getOcclusionTestedDebugMask()
00572 );
00573 }
00574
00575 const BoxVolume &volume = pNode->getVol();
00576 Pnt3r min,max;
00577 volume.getBounds(min, max);
00578 static GLfloat n[6][3] = {
00579 {-1.0, 0.0, 0.0}, {0.0, 1.0, 0.0}, {1.0, 0.0, 0.0},
00580 {0.0, -1.0, 0.0}, {0.0, 0.0, 1.0}, {0.0, 0.0, -1.0}
00581 };
00582 static GLint faces[6][4] = {
00583 { 0, 1, 2, 3}, { 3, 2, 6, 7}, { 7, 6, 5, 4},
00584 { 4, 5, 1, 0}, { 5, 6, 2, 1}, { 7, 4, 0, 3}
00585 };
00586
00587 GLfloat v[8][3];
00588 v[0][0] = v[1][0] = v[2][0] = v[3][0] = min[0];
00589 v[4][0] = v[5][0] = v[6][0] = v[7][0] = max[0];
00590 v[0][1] = v[1][1] = v[4][1] = v[5][1] = min[1];
00591 v[2][1] = v[3][1] = v[6][1] = v[7][1] = max[1];
00592 v[0][2] = v[3][2] = v[4][2] = v[7][2] = min[2];
00593 v[1][2] = v[2][2] = v[5][2] = v[6][2] = max[2];
00594
00595
00596 if(_currSample == _numTestSamples - 1)
00597 {
00598 _currSample = 0;
00599 }
00600 _currSample++;
00601
00602 StatCollector *sc = _rt->getStatCollector();
00603 if(sc != NULL)
00604 sc->getElem(statNOccTests )->inc();
00605
00606 enterTesting(denv, part);
00607 BeginQueryT beginq = reinterpret_cast<BeginQueryT>(
00608 win->getFunction(_funcBeginQueryARB));
00609
00610 pNode->setResultNum(_currSample);
00611 beginq(GL_SAMPLES_PASSED_ARB, _testSamples[_currSample]);
00612 glBegin(GL_QUADS);
00613 for(UInt32 i = 0; i<6; i++)
00614 {
00615 glNormal3fv(&n[i][0]);
00616 glVertex3fv(&v[faces[i][0]][0]);
00617 glNormal3fv(&n[i][0]);
00618 glVertex3fv(&v[faces[i][1]][0]);
00619 glNormal3fv(&n[i][0]);
00620 glVertex3fv(&v[faces[i][2]][0]);
00621 glNormal3fv(&n[i][0]);
00622 glVertex3fv(&v[faces[i][3]][0]);
00623 }
00624 glEnd();
00625
00626 EndQueryT endq = reinterpret_cast<EndQueryT>(
00627 win->getFunction(_funcEndQueryARB));
00628
00629 endq(GL_SAMPLES_PASSED_ARB);
00630 _testPendingNodes.push(pNode);
00631 }
00632
00633 void OcclusionCullingTreeBuilder::drawNode(RenderTreeNode *pNode,
00634 DrawEnv &denv,
00635 RenderPartitionBase *part)
00636 {
00637 leaveTesting(denv, part);
00638
00639 UInt32 uiNextMatrix = pNode->getMatrixStore().first;
00640
00641 if(uiNextMatrix != 0 && uiNextMatrix != _uiActiveMatrix)
00642 {
00643 glLoadMatrixf(pNode->getMatrixStore().second.getValues());
00644
00645 _uiActiveMatrix = uiNextMatrix;
00646
00647 _currMatrix.second = pNode->getMatrixStore().second;
00648
00649 updateTopMatrix(denv);
00650
00651 denv.setObjectToWorld(_accMatrix);
00652
00653 ++part->_uiNumMatrixChanges;
00654 }
00655
00656
00657 State *pNewState = pNode->getState();
00658 StateOverride *pNewStateOverride = pNode->getStateOverride();
00659
00660 denv.setLightState(pNode->getLightState());
00661
00662 denv.activateState(pNewState, pNewStateOverride);
00663
00664 pNode->setIsRendered(true);
00665
00666 if(_rt->getOcclusionCullingDebug() && pNode->getNode())
00667 {
00668 pNode->getNode()->setTravMask(
00669 pNode->getNode()->getTravMask() |
00670 _rt->getOcclusionVisibleDebugMask()
00671 );
00672 }
00673
00674
00675
00676 if(pNode->hasFunctor() == true)
00677 {
00678 if(part->_bCorrectNegScale)
00679 {
00680 const Matrix &m = _currMatrix.second;
00681
00682
00683
00684
00685 if(m[0].cross(m[1]).dot(m[2]) < 0.0)
00686 {
00687 glFrontFace(GL_CW);
00688 }
00689 else
00690 {
00691 glFrontFace(GL_CCW);
00692 }
00693 }
00694
00695
00696
00697 pNode->getFunctor()(&denv);
00698 }
00699 }
00700
00701 void OcclusionCullingTreeBuilder::drawTestResults(DrawEnv &denv,
00702 RenderPartitionBase *part)
00703 {
00704 RenderTreeNode* pNode;
00705 while (!_testPendingNodes.empty())
00706 {
00707 pNode = _testPendingNodes.front();
00708
00709 if(pNode->hasFunctor() == true && !pNode->getIsRendered())
00710 {
00711 Window* win = denv.getWindow();
00712 GetQueryObjectuivT getquiv =
00713 reinterpret_cast<GetQueryObjectuivT>(
00714 win->getFunction(_funcGetQueryObjectuivARB));
00715 GLuint available = 0;
00716 getquiv(_testSamples[pNode->getResultNum()], GL_QUERY_RESULT_AVAILABLE_ARB, &available);
00717 if (!available)
00718 {
00719
00720 return;
00721 }
00722 GLuint sampleCount = 1;
00723 getquiv(_testSamples[pNode->getResultNum()], GL_QUERY_RESULT_ARB, &sampleCount);
00724
00725 if(sampleCount > _visPixelThreshold)
00726 {
00727 drawNode(pNode, denv, part);
00728 }
00729 else
00730 {
00731 StatCollector *sc = _rt->getStatCollector();
00732 if(sc != NULL)
00733 sc->getElem(statNOccInvisible)->inc();
00734
00735 DrawableStatsAttachment *st =
00736 DrawableStatsAttachment::get(pNode->getNode()->getCore());
00737
00738 st->validate();
00739
00740 if(sc != NULL)
00741 sc->getElem(statNOccTriangles)->
00742 add(st->getTriangles());
00743
00744 if(_rt->getOcclusionCullingDebug() && pNode->getNode())
00745 {
00746 pNode->getNode()->setTravMask(
00747 pNode->getNode()->getTravMask() |
00748 _rt->getOcclusionCulledDebugMask()
00749 );
00750 }
00751 }
00752 }
00753
00754 _testPendingNodes.pop();
00755 }
00756 }
00757
00758 void OcclusionCullingTreeBuilder::add(RenderActionBase *pAction,
00759 RenderPartitionBase *part,
00760 RenderTreeNode *pNode,
00761 State *pState,
00762 StateOverride *pStateOverride,
00763 UInt32 uiKeyGen )
00764 {
00765 OSG_ASSERT((_rt == NULL) || (_rt == pAction));
00766
00767 _rt = dynamic_cast<RenderAction *>(pAction);
00768
00769 if(_rt && _rt->getOcclusionCullingDebug() && pNode->getNode())
00770 {
00771
00772 pNode->getNode()->setTravMask(0x0);
00773 }
00774
00775
00776 float val = pNode->getScalar();
00777
00778 if(_pRoot == NULL)
00779 {
00780 _pRoot = _pNodePool->create();
00781 _bucketLow = val;
00782 _bucketHigh = val + 0.1;
00783 _bucketScale = (_nBuckets + 1) / (_bucketHigh - _bucketLow);
00784 }
00785
00786 switch(_sortMode)
00787 {
00788 case ModeAdaptiveBucket:
00789 {
00790 UInt32 index = osgClamp(0u, static_cast<UInt32>((val - _bucketLow) * _bucketScale), _nBuckets - 1);
00791
00792
00793 if( index >= _nBuckets)
00794 {
00795 Real32 newLow = osgMin(val, _bucketLow);
00796 Real32 newHigh = osgMax(val, _bucketHigh);
00797 Real32 newScale = (_nBuckets + 1) / (newHigh - newLow);
00798
00799
00800
00801 Real32 rescale = _bucketScale / newScale;
00802 UInt32 step = osgNextPower2(static_cast<int>(osgCeil(rescale)));
00803
00804 newScale = _bucketScale / step;
00805 Real32 d = (_nBuckets - 1) / newScale;
00806 newLow = osgMax(newLow - d / 2.f, 0.f);
00807 newHigh = osgMin(newLow + d , 1.f);
00808
00809 #if 0
00810 std::cout << "ABS: (" << _bucketLow << " - " << _bucketHigh
00811 << ") => (" << newLow << " - " << newHigh
00812 << ")" << std::endl;
00813 #endif
00814
00815 Real32 iter = _bucketLow;
00816 Real32 istep = 1.f / _bucketScale;
00817
00818 for(UInt32 i = 0; i < _nBuckets; ++i, iter += istep)
00819 {
00820 if(_buckets[i] == NULL)
00821 continue;
00822
00823 int index = static_cast<int>((iter - newLow) * newScale);
00824
00825 if(_bucketsWork[index] == NULL)
00826 {
00827 _bucketsWork[index] = _buckets[i];
00828 }
00829 else
00830 {
00831 _bucketsWork[index]->addChild(_buckets[i]);
00832 }
00833 _buckets[i] = NULL;
00834 }
00835
00836
00837 _buckets.swap(_bucketsWork);
00838
00839 _bucketLow = newLow;
00840 _bucketHigh = newHigh;
00841 _bucketScale = newScale;
00842
00843 index = osgClamp(0u, static_cast<UInt32>((val - _bucketLow) * _bucketScale), _nBuckets - 1);
00844 }
00845
00846 if(_buckets[index] == NULL)
00847 {
00848 _buckets[index] = pNode;
00849 }
00850 else
00851 {
00852 _buckets[index]->addChild(pNode);
00853 }
00854 uNumNodes++;
00855 }
00856 break;
00857
00858 case ModeBucket:
00859 {
00860 int index = osgClamp(0u, static_cast<UInt32>(val * _nBuckets), _nBuckets - 1);
00861
00862 if(_buckets[index] == NULL)
00863 {
00864 _pRoot->addChild(pNode);
00865 _buckets[index] = pNode;
00866 }
00867 else
00868 {
00869 _buckets[index]->addChild(pNode);
00870 }
00871 uNumNodes++;
00872 }
00873 break;
00874
00875 case ModeScalar:
00876 {
00877 if(_pRoot->getFirstChild() == NULL)
00878 {
00879 _pRoot->addChild(pNode);
00880 uNumNodes++;
00881 }
00882 else
00883 {
00884 RenderTreeNode *pCurrent = _pRoot->getFirstChild();
00885
00886 RenderTreeNode *pLast = NULL;
00887 bool bFound = false;
00888
00889 do
00890 {
00891 if(pNode->getScalar() > pCurrent->getScalar())
00892 {
00893 pLast = pCurrent;
00894 pCurrent = pCurrent->getBrother();
00895 }
00896 else
00897 {
00898 bFound = true;
00899 }
00900
00901 } while(bFound == false &&
00902 pCurrent != NULL );
00903
00904 if(bFound == true)
00905 {
00906 if(pLast == NULL)
00907 {
00908 _pRoot->insertFirstChild(pNode);
00909 }
00910 else
00911 {
00912 _pRoot->insertChildAfter(pLast, pNode);
00913 }
00914 uNumNodes++;
00915 }
00916 else
00917 {
00918 _pRoot->addChild(pNode);
00919 uNumNodes++;
00920 }
00921 }
00922 }
00923 break;
00924
00925 default:
00926 FFATAL(("Unknown sort mode %d!\n", _sortMode));
00927 break;
00928 }
00929 }
00930
00931 bool OcclusionCullingTreeBuilder::releaseTestingState(void)
00932 {
00933 _isOccStateCreated = false;
00934 _testingStatePtr = NULL;
00935 _testingState = NULL;
00936
00937 return true;
00938 }
