?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fixed: auto_ptr -> unique_ptr
[opensg.git] / Source / System / Cluster / Window / SortFirst / OSGTileLoadBalancer.cpp
blobd28d2c164b27ca4f30d53c56e3b01eeec0c6d9dc
1 /*---------------------------------------------------------------------------*\
2 * OpenSG *
3 * *
4 * *
5 * Copyright (C) 2000-2002 by the OpenSG Forum *
6 * *
7 * www.opensg.org *
8 * *
9 * contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de *
10 * *
11 \*---------------------------------------------------------------------------*/
12 /*---------------------------------------------------------------------------*\
13 * License *
14 * *
15 * This library is free software; you can redistribute it and/or modify it *
16 * under the terms of the GNU Library General Public License as published *
17 * by the Free Software Foundation, version 2. *
18 * *
19 * This library is distributed in the hope that it will be useful, but *
20 * WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
22 * Library General Public License for more details. *
23 * *
24 * You should have received a copy of the GNU Library General Public *
25 * License along with this library; if not, write to the Free Software *
26 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
27 * *
28 \*---------------------------------------------------------------------------*/
29 /*---------------------------------------------------------------------------*\
30 * Changes *
31 * *
32 * *
33 * *
34 * *
35 * *
36 * *
37 \*---------------------------------------------------------------------------*/
38
39 //---------------------------------------------------------------------------
40 // Includes
41 //---------------------------------------------------------------------------
42
43 #include <stdlib.h>
44 #include <stdio.h>
45
46 #include <functional>
47
48 #include "OSGGLU.h"
49
50 #include <algorithm>
51 #include "OSGConfig.h"
52 #include "OSGGeometry.h"
53 #include "OSGSimpleGeometry.h"
54
55 #include "OSGTileLoadBalancer.h"
56
57 OSG_USING_NAMESPACE
58
59 /** \class OSG::TileLoadBalancer
60 * \ingroup Cluster
61 * \brief Manages geometry load
62 *
63 *
64 *
65 *
66 *
67 **/
68
69 /*-------------------------------------------------------------------------*/
70 /* Constructors */
71
72 /*! Constructor
73 */
74 TileLoadBalancer::TileLoadBalancer(bool useFaceDistribution,
75 bool cutBestDirection):
76 _tileGeometryLoad ( ),
77 _renderNode ( ),
78 _useFaceDistribution(useFaceDistribution),
79 _cutBestDirection (cutBestDirection )
80 {
81 }
82
83 /*! Copy Constructor
84 */
85 TileLoadBalancer::TileLoadBalancer(const TileLoadBalancer &source):
86 _tileGeometryLoad (source._tileGeometryLoad ),
87 _renderNode (source._renderNode ),
88 _useFaceDistribution(source._useFaceDistribution),
89 _cutBestDirection (source._cutBestDirection )
90 {
91 }
92
93 /*-------------------------------------------------------------------------*/
94 /* Destructor */
95
96 /*! Destructor documentation
97 */
98 TileLoadBalancer::~TileLoadBalancer(void)
99 {
100 }
101
102 /*-------------------------------------------------------------------------*/
103 /* Assignment */
104
105 /*! assignment
106 */
107 TileLoadBalancer& TileLoadBalancer::operator = (const TileLoadBalancer &source)
108 {
109 if(this == &source)
110 return *this;
111 _tileGeometryLoad = source._tileGeometryLoad;
112 _renderNode = source._renderNode;
113 _useFaceDistribution = source._useFaceDistribution;
114 _cutBestDirection = source._cutBestDirection;
115 return *this;
116 }
117
118
119 /** Update the load balancing information
120 **/
121 void TileLoadBalancer::update(Node *node)
122 {
123 TileGeometryLoadMapT loadMap;
124
125 // collect old load objects
126 for(TileGeometryLoadLstT::iterator gI=_tileGeometryLoad.begin();gI!=_tileGeometryLoad.end();++gI)
127 {
128 if(gI->getNode() != NULL)
129 loadMap[gI->getNode()->getId()] = gI;
130 else
131 gI->setValid(false);
132 }
133
134 updateSubtree(node,loadMap);
135
136 // mark unused load objects as invalid.
137 for(TileGeometryLoadMapT::iterator mI=loadMap.begin();mI!=loadMap.end();++mI)
138 mI->second->setValid(false);
139
140 // remove all invalid objects.
141 _tileGeometryLoad.erase(std::remove_if(_tileGeometryLoad.begin(), _tileGeometryLoad.end(),
142 std::mem_fun_ref(&TileGeometryLoad::isInvalid)), _tileGeometryLoad.end());
143 }
144
145 /** load balance
146 *
147 * \param vp current viewport
148 * \param shrink shrink to max area of visible objects
149 * \param result resulting regions
150 *
151 **/
152 void TileLoadBalancer::balance(Viewport *vp,
153 bool shrink,
154 ResultT &result)
155 {
156 Matrix projection,viewing;
157 RegionLoadVecT visible;
158 RegionLoadVecT::iterator vi;
159 Int32 width =vp->calcPixelWidth();
160 Int32 height=vp->calcPixelHeight();
161 Int32 wmin[2]={width,height};
162 Int32 wmax[2]={0 ,0 };
163 Real32 rNear=vp->getCamera()->getNear();
164
165 result.clear();
166 vp->getCamera()->getViewing ( viewing ,width,height );
167 vp->getCamera()->getProjection( projection,width,height );
168 visible.reserve(_tileGeometryLoad.size());
169 for(TileGeometryLoadLstT::iterator l=_tileGeometryLoad.begin() ; l!=_tileGeometryLoad.end() ; ++l)
170 {
171 // update view dependent values
172 l->updateView(viewing,
173 projection,
174 rNear,
175 width,
176 height);
177 // sort by min values
178 if(l->isVisible())
179 {
180 // collect visible geometries
181 visible.push_back(RegionLoad(&(*l)));
182 if(shrink)
183 {
184 if(l->getMin()[0] < wmin[0])
185 wmin[0]=l->getMin()[0];
186 if(l->getMin()[1] < wmin[1])
187 wmin[1]=l->getMin()[1];
188 if(l->getMax()[0] > wmax[0])
189 wmax[0]=l->getMax()[0];
190 if(l->getMax()[1] > wmax[1])
191 wmax[1]=l->getMax()[1];
192 }
193 }
194 }
195 if(shrink)
196 {
197 // handle invisible area
198 if(wmax[0]<wmin[0] ||
199 wmax[1]<wmin[1] )
200 wmin[0]=wmax[0]=wmin[1]=wmax[1]=0;
201 // clamp to viewable area
202 if(wmin[0]<0)
203 wmin[0]=0;
204 if(wmin[1]<0)
205 wmin[1]=0;
206 if(wmax[0]>=width )
207 wmax[0]=width -1;
208 if(wmax[1]>=height)
209 wmax[1]=height-1;
210 }
211 else
212 {
213 wmin[0]=wmin[1]=0;
214 wmax[0]=width-1;
215 wmax[1]=height-1;
216 }
217 // calculate region cost
218 for(vi=visible.begin();vi!=visible.end();vi++)
219 {
220 vi->updateCost(wmin,wmax);
221 }
222 if(_renderNode.size()>1)
223 {
224 splitRegion(0, UInt32(_renderNode.size()) - 1,
225 visible,
226 wmin,
227 wmax,
228 0,
229 result);
230 }
231 else
232 {
233 Region region;
234 region.x1=wmin[0];
235 region.y1=wmin[1];
236 region.x2=wmax[0];
237 region.y2=wmax[1];
238 result.push_back(region);
239 }
240 }
241
242 void TileLoadBalancer::setRegionStatistics(Viewport *vp,
243 ResultT &result)
244 {
245 Matrix projection,viewing;
246 Int32 width =vp->calcPixelWidth();
247 Int32 height=vp->calcPixelHeight();
248 Real32 rNear=vp->getCamera()->getNear();
249 ResultT::iterator resultI;
250 TileGeometryLoadLstT::iterator l;
251
252 vp->getCamera()->getViewing ( viewing ,width,height );
253 vp->getCamera()->getProjection( projection,width,height );
254 for(resultI=result.begin();
255 resultI!=result.end();
256 ++resultI)
257 {
258 resultI->culledNodes=0;
259 resultI->faces=0;
260 resultI->culledFaces=0;
261 resultI->pixel=0;
262 }
263 for(l=_tileGeometryLoad.begin() ;
264 l!=_tileGeometryLoad.end() ;
265 ++l)
266 {
267 l->updateView(viewing,
268 projection,
269 rNear,
270 width,
271 height);
272 for(resultI=result.begin();
273 resultI!=result.end();
274 ++resultI)
275 {
276 if(!l->isVisible())
277 resultI->culledNodes++;
278 else
279 {
280 Int32 wmin[2];
281 Int32 wmax[2];
282 Int32 vismin[2];
283 Int32 vismax[2];
284 wmin[0]=resultI->x1;
285 wmin[1]=resultI->y1;
286 wmax[0]=resultI->x2;
287 wmax[1]=resultI->y2;
288 Real32 visible=l->getVisibleFraction(wmin,wmax,vismin,vismax)*
289 l->getFaces();
290 if(visible==0)
291 resultI->culledNodes++;
292 else
293 {
294 resultI->faces+=visible;
295 resultI->culledFaces+= l->getFaces()-visible;
296 resultI->pixel+=
297 (vismax[0] - vismin[0] + 1)*
298 (vismax[1] - vismin[1] + 1);
299 }
300 }
301 }
302 }
303 }
304
305 /** Add new render node
306 *
307 **/
308 void TileLoadBalancer::addRenderNode(const RenderNode &rn,UInt32 id)
309 {
310 while(_renderNode.size()<=id)
311 _renderNode.push_back(RenderNode());
312 _renderNode[id]=rn;
313 }
314
315 /** Draw recangular volume projection
316 *
317 **/
318 void TileLoadBalancer::drawVolumes(Window *win)
319 {
320 glPushMatrix();
321 glLoadIdentity();
322 glMatrixMode(GL_PROJECTION);
323 glPushMatrix();
324 glLoadIdentity();
325 glViewport(0,0,win->getWidth(),win->getHeight());
326 gluOrtho2D(0,win->getWidth(),
327 0,win->getHeight());
328 glDisable(GL_DEPTH_TEST);
329 glEnable(GL_COLOR_MATERIAL);
330 for(TileGeometryLoadLstT::iterator l=_tileGeometryLoad.begin() ; l!=_tileGeometryLoad.end() ; ++l)
331 {
332 if(l->isVisible())
333 {
334 glBegin(GL_LINE_LOOP);
335 glColor3f(0, 1, 0);
336 glVertex3i(l->getMin()[0],l->getMin()[1],0);
337 glVertex3i(l->getMax()[0],l->getMin()[1],0);
338 glVertex3i(l->getMax()[0],l->getMax()[1],0);
339 glVertex3i(l->getMin()[0],l->getMax()[1],0);
340 glEnd();
341 }
342 }
343 glDisable(GL_COLOR_MATERIAL);
344 glEnable(GL_DEPTH_TEST);
345 glPopMatrix();
346 glMatrixMode(GL_MODELVIEW);
347 glPopMatrix();
348 }
349
350 /** Add all geometry nodes in the given tree
351 **/
352 void TileLoadBalancer::updateSubtree(Node * const node,
353 TileGeometryLoadMapT &loadMap)
354 {
355 // is nodecore a geometry?
356 if(node->getCore() != NULL &&
357 dynamic_cast<Geometry *>(node->getCore()) != NULL)
358 {
359 // is this a new node
360 TileGeometryLoadMapT::iterator mI=loadMap.find(node->getId());
361 if(mI==loadMap.end())
362 {
363 _tileGeometryLoad.push_back(TileGeometryLoad(node->getId(),
364 _useFaceDistribution));
365 }
366 else
367 {
368 loadMap.erase(mI);
369 }
370 }
371 // handle all childs
372 for(MFUnrecChildNodePtr::const_iterator n = node->getMFChildren()->begin();
373 n !=node->getMFChildren()->end();
374 ++n)
375 {
376 updateSubtree(*n,loadMap);
377 }
378 }
379
380 /** Splitupt region
381 **/
382 void TileLoadBalancer::splitRegion(UInt32 rnFrom,
383 UInt32 rnTo,
384 RegionLoadVecT &visible,
385 Int32 wmin[2],
386 Int32 wmax[2],
387 UInt32 depth,
388 ResultT &result)
389 {
390 Int32 axis,cut;
391 Int32 maxA[2];
392 Int32 minB[2];
393 RegionLoadVecT visibleA;
394 RegionLoadVecT visibleB;
395 RegionLoadVecT::iterator vi;
396 UInt32 rnToA,rnFromB;
397 RenderNode groupRegionA,groupRegionB;
398 RenderNode *renderNodeA,*renderNodeB;
399
400 // create group render node if neccessary
401 rnToA =(rnTo+rnFrom)>>1;
402 rnFromB=rnToA+1;
403 if(rnFrom != rnToA)
404 {
405 groupRegionA.setGroup(&_renderNode[rnFrom],&_renderNode[rnToA+1]);
406 renderNodeA=&groupRegionA;
407 }
408 else
409 {
410 renderNodeA=&_renderNode[rnFrom];
411 }
412 if(rnFromB != rnTo)
413 {
414 groupRegionB.setGroup(&_renderNode[rnFromB],&_renderNode[rnTo+1]);
415 renderNodeB=&groupRegionB;
416 }
417 else
418 {
419 renderNodeB=&_renderNode[rnFromB];
420 }
421 #if 0
422 if((rnToA-rnFrom) != (rnTo-rnFromB))
423 {
424 renderNodeB->setInvisibleFaceCost(renderNodeA->getInvisibleFaceCost());
425 }
426 #endif
427 // do we check both axis?
428 if(_cutBestDirection)
429 axis=-1;
430 else
431 axis=depth&1;
432 // search for best cut
433 findBestCut(*renderNodeA,*renderNodeB,
434 visible,wmin,wmax,axis,cut);
435 // create new regions
436 maxA[axis ]=cut;
437 maxA[axis^1]=wmax[axis^1];
438 minB[axis ]=cut+1;
439 minB[axis^1]=wmin[axis^1];
440 visibleA.reserve(visible.size());
441 visibleB.reserve(visible.size());
442
443 // split regions
444 if(rnFrom != rnToA || rnFromB != rnTo)
445 {
446 // split visible regions
447 for(vi=visible.begin();vi!=visible.end();vi++)
448 {
449 if(vi->getLoad()->getMax()[axis] <= cut)
450 visibleA.push_back(*vi);
451 else
452 if(vi->getLoad()->getMin()[axis] > cut)
453 visibleB.push_back(*vi);
454 else
455 {
456 visibleA.push_back(*vi);
457 visibleB.push_back(*vi);
458 visibleA.rbegin()->updateCost(wmin,maxA);
459 visibleB.rbegin()->updateCost(minB,wmax);
460 }
461 }
462 }
463 if(rnFrom != rnToA)
464 splitRegion(rnFrom,rnToA,visibleA,wmin,maxA,depth+1,result);
465 else
466 {
467 Region region;
468 region.x1=wmin[0];
469 region.y1=wmin[1];
470 region.x2=maxA[0];
471 region.y2=maxA[1];
472 result.push_back(region);
473 }
474 if(rnFromB != rnTo)
475 splitRegion(rnFromB,rnTo,visibleB,minB,wmax,depth+1,result);
476 else
477 {
478 Region region;
479 region.x1=minB[0];
480 region.y1=minB[1];
481 region.x2=wmax[0];
482 region.y2=wmax[1];
483 result.push_back(region);
484 }
485 }
486
487 /** Find best cut through the geometries
488 **/
489 Real32 TileLoadBalancer::findBestCut (const RenderNode &renderNodeA,
490 const RenderNode &renderNodeB,
491 RegionLoadVecT &visible,
492 Int32 wmin[2],
493 Int32 wmax[2],
494 Int32 &bestAxis,
495 Int32 &bestCut)
496 {
497 RegionLoadVecT::iterator vi;
498 Int32 a,f,t,newCut;
499 Int32 minB[2];
500 Int32 maxA[2];
501 Real32 costA=0,costB=0;
502 Real32 newCost;
503 Real32 bestCost;
504 Int32 checkAxisFrom,checkAxisTo;
505 bestCost=1e22f;
506
507 if(bestAxis>=0)
508 {
509 // only check given axis
510 checkAxisFrom=checkAxisTo=bestAxis;
511 }
512 else
513 {
514 // check x and y cut
515 checkAxisFrom=0;
516 checkAxisTo=1;
517 }
518 for(a=checkAxisFrom;a<=checkAxisTo;++a)
519 {
520 f=wmin[a];
521 t=wmax[a];
522 maxA[0]=wmax[0];;
523 maxA[1]=wmax[1];;
524 minB[0]=wmin[0];;
525 minB[1]=wmin[1];;
526 do
527 {
528 newCut=(f+t)/2;
529 maxA[a]=newCut;
530 minB[a]=newCut+1;
531 costA=costB=0;
532 for(vi=visible.begin();vi!=visible.end();vi++)
533 {
534 if(vi->getLoad()->getMax()[a] <= newCut)
535 {
536 costA+=vi->getCost(renderNodeA);
537 }
538 else
539 if(vi->getLoad()->getMin()[a] > newCut)
540 {
541 costB+=vi->getCost(renderNodeB);
542 }
543 else
544 {
545 costA+=vi->getCost(renderNodeA,wmin,maxA);
546 costB+=vi->getCost(renderNodeB,minB,wmax);
547 }
548
549 }
550 newCost= osgMax( costA, costB );
551 if(newCost<bestCost)
552 {
553 bestCut=newCut;
554 bestCost=newCost;
555 bestAxis=a;
556 }
557 // walk into direction of inbalance
558 if(costA>costB)
559 t=newCut;
560 else
561 f=newCut;
562 }
563 while(t-f > 2);
564 }
565 return bestCost;
566 }
567