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
00040
00041
00042
00043 #include <stdlib.h>
00044 #include <stdio.h>
00045
00046 #include <functional>
00047
00048 #include <OSGGLU.h>
00049
00050 #include <algorithm>
00051 #include <OSGConfig.h>
00052 #include <OSGDrawAction.h>
00053 #include <OSGGeometry.h>
00054 #include <OSGSimpleGeometry.h>
00055
00056 #include "OSGTileLoadBalancer.h"
00057
00058 OSG_USING_NAMESPACE
00059
00070
00071
00072
00075 TileLoadBalancer::TileLoadBalancer(bool useFaceDistribution,
00076 bool cutBestDirection):
00077 _useFaceDistribution(useFaceDistribution),
00078 _cutBestDirection(cutBestDirection)
00079 {
00080 }
00081
00084 TileLoadBalancer::TileLoadBalancer(const TileLoadBalancer &source):
00085 _tileGeometryLoad(source._tileGeometryLoad),
00086 _renderNode(source._renderNode),
00087 _useFaceDistribution(source._useFaceDistribution),
00088 _cutBestDirection(source._cutBestDirection)
00089 {
00090 }
00091
00092
00093
00094
00097 TileLoadBalancer::~TileLoadBalancer(void)
00098 {
00099 }
00100
00101
00102
00103
00106 TileLoadBalancer& TileLoadBalancer::operator = (const TileLoadBalancer &source)
00107 {
00108 if(this == &source)
00109 return *this;
00110 _tileGeometryLoad = source._tileGeometryLoad;
00111 _renderNode = source._renderNode;
00112 _useFaceDistribution = source._useFaceDistribution;
00113 _cutBestDirection = source._cutBestDirection;
00114 return *this;
00115 }
00116
00117
00120 void TileLoadBalancer::update(NodePtr node)
00121 {
00122 TileGeometryLoadMapT loadMap;
00123
00124
00125 for(TileGeometryLoadLstT::iterator gI=_tileGeometryLoad.begin();gI!=_tileGeometryLoad.end();++gI)
00126 {
00127 if(gI->getNode() != NullFC)
00128 loadMap[gI->getNode().getFieldContainerId()] = gI;
00129 else
00130 gI->setValid(false);
00131 }
00132
00133 updateSubtree(node,loadMap);
00134
00135
00136 for(TileGeometryLoadMapT::iterator mI=loadMap.begin();mI!=loadMap.end();++mI)
00137 mI->second->setValid(false);
00138
00139
00140 _tileGeometryLoad.erase(std::remove_if(_tileGeometryLoad.begin(), _tileGeometryLoad.end(),
00141 std::mem_fun_ref(&TileGeometryLoad::isInvalid)), _tileGeometryLoad.end());
00142 }
00143
00151 void TileLoadBalancer::balance(ViewportPtr vp,
00152 bool shrink,
00153 ResultT &result)
00154 {
00155 Matrix projection,viewing;
00156 RegionLoadVecT visible;
00157 RegionLoadVecT::iterator vi;
00158 Int32 width =vp->getPixelWidth();
00159 Int32 height=vp->getPixelHeight();
00160 Int32 wmin[2]={width,height};
00161 Int32 wmax[2]={0 ,0 };
00162 Real32 rNear=vp->getCamera()->getNear();
00163
00164 result.clear();
00165 vp->getCamera()->getViewing ( viewing ,width,height );
00166 vp->getCamera()->getProjection( projection,width,height );
00167 visible.reserve(_tileGeometryLoad.size());
00168 for(TileGeometryLoadLstT::iterator l=_tileGeometryLoad.begin() ; l!=_tileGeometryLoad.end() ; ++l)
00169 {
00170
00171 l->updateView(viewing,
00172 projection,
00173 rNear,
00174 width,
00175 height);
00176
00177 if(l->isVisible())
00178 {
00179
00180 visible.push_back(RegionLoad(&(*l)));
00181 if(shrink)
00182 {
00183 if(l->getMin()[0] < wmin[0])
00184 wmin[0]=l->getMin()[0];
00185 if(l->getMin()[1] < wmin[1])
00186 wmin[1]=l->getMin()[1];
00187 if(l->getMax()[0] > wmax[0])
00188 wmax[0]=l->getMax()[0];
00189 if(l->getMax()[1] > wmax[1])
00190 wmax[1]=l->getMax()[1];
00191 }
00192 }
00193 }
00194 if(shrink)
00195 {
00196
00197 if(wmax[0]<wmin[0] ||
00198 wmax[1]<wmin[1] )
00199 wmin[0]=wmax[0]=wmin[1]=wmax[1]=0;
00200
00201 if(wmin[0]<0)
00202 wmin[0]=0;
00203 if(wmin[1]<0)
00204 wmin[1]=0;
00205 if(wmax[0]>=width )
00206 wmax[0]=width -1;
00207 if(wmax[1]>=height)
00208 wmax[1]=height-1;
00209 }
00210 else
00211 {
00212 wmin[0]=wmin[1]=0;
00213 wmax[0]=width-1;
00214 wmax[1]=height-1;
00215 }
00216
00217 for(vi=visible.begin();vi!=visible.end();vi++)
00218 {
00219 vi->updateCost(wmin,wmax);
00220 }
00221 if(_renderNode.size()>1)
00222 {
00223 splitRegion(0,_renderNode.size()-1,
00224 visible,
00225 wmin,
00226 wmax,
00227 0,
00228 result);
00229 }
00230 else
00231 {
00232 Region region;
00233 region.x1=wmin[0];
00234 region.y1=wmin[1];
00235 region.x2=wmax[0];
00236 region.y2=wmax[1];
00237 result.push_back(region);
00238 }
00239 }
00240
00241 void TileLoadBalancer::setRegionStatistics(ViewportPtr vp,
00242 ResultT &result)
00243 {
00244 Matrix projection,viewing;
00245 Int32 width =vp->getPixelWidth();
00246 Int32 height=vp->getPixelHeight();
00247 Real32 rNear=vp->getCamera()->getNear();
00248 ResultT::iterator resultI;
00249 TileGeometryLoadLstT::iterator l;
00250
00251 vp->getCamera()->getViewing ( viewing ,width,height );
00252 vp->getCamera()->getProjection( projection,width,height );
00253 for(resultI=result.begin();
00254 resultI!=result.end();
00255 ++resultI)
00256 {
00257 resultI->culledNodes=0;
00258 resultI->faces=0;
00259 resultI->culledFaces=0;
00260 resultI->pixel=0;
00261 }
00262 for(l=_tileGeometryLoad.begin() ;
00263 l!=_tileGeometryLoad.end() ;
00264 ++l)
00265 {
00266 l->updateView(viewing,
00267 projection,
00268 rNear,
00269 width,
00270 height);
00271 for(resultI=result.begin();
00272 resultI!=result.end();
00273 ++resultI)
00274 {
00275 if(!l->isVisible())
00276 resultI->culledNodes++;
00277 else
00278 {
00279 Int32 wmin[2];
00280 Int32 wmax[2];
00281 Int32 vismin[2];
00282 Int32 vismax[2];
00283 wmin[0]=resultI->x1;
00284 wmin[1]=resultI->y1;
00285 wmax[0]=resultI->x2;
00286 wmax[1]=resultI->y2;
00287 Real32 visible=l->getVisibleFraction(wmin,wmax,vismin,vismax)*
00288 l->getFaces();
00289 if(visible==0)
00290 resultI->culledNodes++;
00291 else
00292 {
00293 resultI->faces+=visible;
00294 resultI->culledFaces+= l->getFaces()-visible;
00295 resultI->pixel+=
00296 (vismax[0] - vismin[0] + 1)*
00297 (vismax[1] - vismin[1] + 1);
00298 }
00299 }
00300 }
00301 }
00302 }
00303
00307 void TileLoadBalancer::addRenderNode(const RenderNode &rn,UInt32 id)
00308 {
00309 while(_renderNode.size()<=id)
00310 _renderNode.push_back(RenderNode());
00311 _renderNode[id]=rn;
00312 }
00313
00317 void TileLoadBalancer::drawVolumes(WindowPtr win)
00318 {
00319 glPushMatrix();
00320 glLoadIdentity();
00321 glMatrixMode(GL_PROJECTION);
00322 glPushMatrix();
00323 glLoadIdentity();
00324 glViewport(0,0,win->getWidth(),win->getHeight());
00325 gluOrtho2D(0,win->getWidth(),
00326 0,win->getHeight());
00327 glDisable(GL_DEPTH_TEST);
00328 glEnable(GL_COLOR_MATERIAL);
00329 for(TileGeometryLoadLstT::iterator l=_tileGeometryLoad.begin() ; l!=_tileGeometryLoad.end() ; ++l)
00330 {
00331 if(l->isVisible())
00332 {
00333 glBegin(GL_LINE_LOOP);
00334 glColor3f(0, 1, 0);
00335 glVertex3i(l->getMin()[0],l->getMin()[1],0);
00336 glVertex3i(l->getMax()[0],l->getMin()[1],0);
00337 glVertex3i(l->getMax()[0],l->getMax()[1],0);
00338 glVertex3i(l->getMin()[0],l->getMax()[1],0);
00339 glEnd();
00340 }
00341 }
00342 glDisable(GL_COLOR_MATERIAL);
00343 glEnable(GL_DEPTH_TEST);
00344 glPopMatrix();
00345 glMatrixMode(GL_MODELVIEW);
00346 glPopMatrix();
00347 }
00348
00351 void TileLoadBalancer::updateSubtree(NodePtr &node,TileGeometryLoadMapT &loadMap)
00352 {
00353
00354 if(node->getCore() != NullFC &&
00355 GeometryPtr::dcast(node->getCore()) != NullFC)
00356 {
00357
00358 TileGeometryLoadMapT::iterator mI=loadMap.find(node.getFieldContainerId());
00359 if(mI==loadMap.end())
00360 {
00361 _tileGeometryLoad.push_back(TileGeometryLoad(node.getFieldContainerId(),_useFaceDistribution));
00362 }
00363 else
00364 {
00365 loadMap.erase(mI);
00366 }
00367 }
00368
00369 for(MFNodePtr::iterator n=node->getMFChildren()->begin();
00370 n!=node->getMFChildren()->end();
00371 ++n)
00372 {
00373 updateSubtree(*n,loadMap);
00374 }
00375 }
00376
00379 void TileLoadBalancer::splitRegion(UInt32 rnFrom,
00380 UInt32 rnTo,
00381 RegionLoadVecT &visible,
00382 Int32 wmin[2],
00383 Int32 wmax[2],
00384 UInt32 depth,
00385 ResultT &result)
00386 {
00387 Int32 axis,cut;
00388 Int32 maxA[2];
00389 Int32 minB[2];
00390 RegionLoadVecT visibleA;
00391 RegionLoadVecT visibleB;
00392 RegionLoadVecT::iterator vi;
00393 UInt32 rnToA,rnFromB;
00394 RenderNode groupRegionA,groupRegionB;
00395 RenderNode *renderNodeA,*renderNodeB;
00396
00397
00398 rnToA =(rnTo+rnFrom)>>1;
00399 rnFromB=rnToA+1;
00400 if(rnFrom != rnToA)
00401 {
00402 groupRegionA.setGroup(&_renderNode[rnFrom],&_renderNode[rnToA+1]);
00403 renderNodeA=&groupRegionA;
00404 }
00405 else
00406 {
00407 renderNodeA=&_renderNode[rnFrom];
00408 }
00409 if(rnFromB != rnTo)
00410 {
00411 groupRegionB.setGroup(&_renderNode[rnFromB],&_renderNode[rnTo+1]);
00412 renderNodeB=&groupRegionB;
00413 }
00414 else
00415 {
00416 renderNodeB=&_renderNode[rnFromB];
00417 }
00418 #if 0
00419 if((rnToA-rnFrom) != (rnTo-rnFromB))
00420 {
00421 renderNodeB->setInvisibleFaceCost(renderNodeA->getInvisibleFaceCost());
00422 }
00423 #endif
00424
00425 if(_cutBestDirection)
00426 axis=-1;
00427 else
00428 axis=depth&1;
00429
00430 findBestCut(*renderNodeA,*renderNodeB,
00431 visible,wmin,wmax,axis,cut);
00432
00433 maxA[axis ]=cut;
00434 maxA[axis^1]=wmax[axis^1];
00435 minB[axis ]=cut+1;
00436 minB[axis^1]=wmin[axis^1];
00437 visibleA.reserve(visible.size());
00438 visibleB.reserve(visible.size());
00439
00440
00441 if(rnFrom != rnToA || rnFromB != rnTo)
00442 {
00443
00444 for(vi=visible.begin();vi!=visible.end();vi++)
00445 {
00446 if(vi->getLoad()->getMax()[axis] <= cut)
00447 visibleA.push_back(*vi);
00448 else
00449 if(vi->getLoad()->getMin()[axis] > cut)
00450 visibleB.push_back(*vi);
00451 else
00452 {
00453 visibleA.push_back(*vi);
00454 visibleB.push_back(*vi);
00455 visibleA.rbegin()->updateCost(wmin,maxA);
00456 visibleB.rbegin()->updateCost(minB,wmax);
00457 }
00458 }
00459 }
00460 if(rnFrom != rnToA)
00461 splitRegion(rnFrom,rnToA,visibleA,wmin,maxA,depth+1,result);
00462 else
00463 {
00464 Region region;
00465 region.x1=wmin[0];
00466 region.y1=wmin[1];
00467 region.x2=maxA[0];
00468 region.y2=maxA[1];
00469 result.push_back(region);
00470 }
00471 if(rnFromB != rnTo)
00472 splitRegion(rnFromB,rnTo,visibleB,minB,wmax,depth+1,result);
00473 else
00474 {
00475 Region region;
00476 region.x1=minB[0];
00477 region.y1=minB[1];
00478 region.x2=wmax[0];
00479 region.y2=wmax[1];
00480 result.push_back(region);
00481 }
00482 }
00483
00486 Real32 TileLoadBalancer::findBestCut (const RenderNode &renderNodeA,
00487 const RenderNode &renderNodeB,
00488 RegionLoadVecT &visible,
00489 Int32 wmin[2],
00490 Int32 wmax[2],
00491 Int32 &bestAxis,
00492 Int32 &bestCut)
00493 {
00494 RegionLoadVecT::iterator vi;
00495 Int32 a,f,t,newCut;
00496 Int32 minB[2];
00497 Int32 maxA[2];
00498 Real32 costA=0,costB=0;
00499 Real32 newCost;
00500 Real32 bestCost;
00501 Int32 checkAxisFrom,checkAxisTo;
00502 bestCost=1e22;
00503
00504 if(bestAxis>=0)
00505 {
00506
00507 checkAxisFrom=checkAxisTo=bestAxis;
00508 }
00509 else
00510 {
00511
00512 checkAxisFrom=0;
00513 checkAxisTo=1;
00514 }
00515 for(a=checkAxisFrom;a<=checkAxisTo;++a)
00516 {
00517 f=wmin[a];
00518 t=wmax[a];
00519 maxA[0]=wmax[0];;
00520 maxA[1]=wmax[1];;
00521 minB[0]=wmin[0];;
00522 minB[1]=wmin[1];;
00523 do
00524 {
00525 newCut=(f+t)/2;
00526 maxA[a]=newCut;
00527 minB[a]=newCut+1;
00528 costA=costB=0;
00529 for(vi=visible.begin();vi!=visible.end();vi++)
00530 {
00531 if(vi->getLoad()->getMax()[a] <= newCut)
00532 {
00533 costA+=vi->getCost(renderNodeA);
00534 }
00535 else
00536 if(vi->getLoad()->getMin()[a] > newCut)
00537 {
00538 costB+=vi->getCost(renderNodeB);
00539 }
00540 else
00541 {
00542 costA+=vi->getCost(renderNodeA,wmin,maxA);
00543 costB+=vi->getCost(renderNodeB,minB,wmax);
00544 }
00545
00546 }
00547 newCost= osgMax( costA, costB );
00548 if(newCost<bestCost)
00549 {
00550 bestCut=newCut;
00551 bestCost=newCost;
00552 bestAxis=a;
00553 }
00554
00555 if(costA>costB)
00556 t=newCut;
00557 else
00558 f=newCut;
00559 }
00560 while(t-f > 2);
00561 }
00562 return bestCost;
00563 }
00564
00565
00566
00567
00568
00569 #ifdef __sgi
00570 #pragma set woff 1174
00571 #endif
00572
00573 #ifdef OSG_LINUX_ICC
00574 #pragma warning( disable : 177 )
00575 #endif
00576
00577 namespace
00578 {
00579 static Char8 cvsid_cpp[] = "@(#)$Id:$";
00580 static Char8 cvsid_hpp[] = OSG_TILE_LOAD_BALANCER_HEADER_CVSID;
00581 static Char8 cvsid_inl[] = OSG_TILE_LOAD_BALANCER_INLINE_CVSID;
00582 }
