source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreBiHierarchy.cpp @ 2348

Revision 2348, 58.5 KB checked in by vizrt_christian_seidl, 17 years ago (diff)

Added: BIHierarchy SceneManager?

BITerrain SceneManager?
Line 
1/*
2-----------------------------------------------------------------------------
3This source file is part of the GameTools Project
4http://www.gametools.org
5
6Author: Martin Szydlowski
7-----------------------------------------------------------------------------
8*/
9
10#include "OgreBiHierarchy.h"
11#include "OgreBihRenderable.h"
12#include "OgreBiHierarchySceneNode.h"
13#include "OgreBiHierarchySceneManager.h"
14
15#include <OgreStringConverter.h>
16#include <OgreLogManager.h>
17#include <OgreRoot.h>
18#include <OgreTimer.h>
19
20#include <OgreMaterialManager.h>
21
22#define PLT_SIZE 101
23
24namespace Ogre
25{
26
27enum BihIntersection
28{
29        OUTSIDE=0,
30        INSIDE=1,
31        INTERSECT=2
32};
33
34static BihIntersection intersect( const Ray &one, const AxisAlignedBox &two )
35{
36        // Null box?
37        if (two.isNull()) return OUTSIDE;
38
39        bool inside = true;
40        const Vector3* pCorners = two.getAllCorners();
41        Vector3 origin = one.getOrigin();
42        Vector3 dir = one.getDirection();
43
44        Vector3 maxT(-1, -1, -1);
45
46        int i = 0;
47        for(i=0; i<3; i++ )
48        {
49                if( origin[i] < pCorners[0][i] )
50                {
51                        inside = false;
52                        if( dir[i] > 0 )
53                        {
54                                maxT[i] = (pCorners[0][i] - origin[i])/ dir[i];
55                        }
56                }
57                else if( origin[i] > pCorners[4][i] )
58                {
59                        inside = false;
60                        if( dir[i] < 0 )
61                        {
62                                maxT[i] = (pCorners[4][i] - origin[i]) / dir[i];
63                        }
64                }
65        }
66
67        if( inside )
68        {
69                return INTERSECT;
70        }
71        int whichPlane = 0;
72        if( maxT[1] > maxT[whichPlane])
73                whichPlane = 1;
74        if( maxT[2] > maxT[whichPlane])
75                whichPlane = 2;
76
77        if( ((int)maxT[whichPlane]) & 0x80000000 )
78        {
79                return OUTSIDE;
80        }
81        for(i=0; i<3; i++ )
82        {
83                if( i!= whichPlane )
84                {
85                        float f = origin[i] + maxT[whichPlane] * dir[i];
86                        if ( f < (pCorners[0][i] - 0.00001f) ||
87                                f > (pCorners[4][i] +0.00001f ) )
88                        {
89                                return OUTSIDE;
90                        }
91                }
92        }
93
94        return INTERSECT;
95
96}
97
98
99/** Checks how the second box intersects with the first.
100*/
101static BihIntersection intersect( const PlaneBoundedVolume &one, const AxisAlignedBox &two )
102{
103        // Null box?
104        if (two.isNull()) return OUTSIDE;
105
106        // Get corners of the box
107        const Vector3* pCorners = two.getAllCorners();
108
109        // For each plane, see if all points are on the negative side
110        // If so, object is not visible.
111        // If one or more are, it's partial.
112        // If all aren't, full
113        int corners[ 8 ] = {0, 4, 3, 5, 2, 6, 1, 7};
114        bool all_inside = true;
115        PlaneList::const_iterator i, iend;
116        iend = one.planes.end();
117        for (i = one.planes.begin(); i != iend; ++i)
118        {
119                const Plane& plane = *i;
120                bool all_outside = true;
121
122                float distance = 0;
123
124                for ( int corner = 0; corner < 8; ++corner )
125                {
126                        distance = plane.getDistance( pCorners[ corners[ corner ] ] );
127                        all_outside = all_outside && ( distance < 0 );
128                        all_inside = all_inside && ( distance >= 0 );
129
130                        if ( !all_outside && !all_inside )
131                                break;
132                }
133
134                if ( all_outside )
135                        return OUTSIDE;
136        }
137
138        if ( all_inside )
139                return INSIDE;
140        else
141                return INTERSECT;
142
143}
144
145
146/** Checks how the second box intersects with the first.
147*/
148static BihIntersection intersect( const AxisAlignedBox &one, const AxisAlignedBox &two )
149{
150        // Null box?
151        if (one.isNull() || two.isNull()) return OUTSIDE;
152
153        const Vector3 * outside = one.getAllCorners();
154        const Vector3 *inside = two.getAllCorners();
155
156        if ( inside[ 4 ].x < outside[ 0 ].x ||
157                inside[ 4 ].y < outside[ 0 ].y ||
158                inside[ 4 ].z < outside[ 0 ].z ||
159                inside[ 0 ].x > outside[ 4 ].x ||
160                inside[ 0 ].y > outside[ 4 ].y ||
161                inside[ 0 ].z > outside[ 4 ].z )
162        {
163                return OUTSIDE;
164        }
165
166        bool full = ( inside[ 0 ].x > outside[ 0 ].x &&
167                inside[ 0 ].y > outside[ 0 ].y &&
168                inside[ 0 ].z > outside[ 0 ].z &&
169                inside[ 4 ].x < outside[ 4 ].x &&
170                inside[ 4 ].y < outside[ 4 ].y &&
171                inside[ 4 ].z < outside[ 4 ].z );
172
173        if ( full )
174                return INSIDE;
175        else
176                return INTERSECT;
177
178}
179
180/** Checks how the box intersects with the sphere.
181*/
182static BihIntersection intersect( const Sphere &one, const AxisAlignedBox &two )
183{
184        // Null box?
185        if (two.isNull()) return OUTSIDE;
186
187        float sradius = one.getRadius();
188
189        sradius *= sradius;
190
191        Vector3 scenter = one.getCenter();
192
193        const Vector3 *corners = two.getAllCorners();
194
195        float s, d = 0;
196
197        Vector3 mndistance = ( corners[ 0 ] - scenter );
198        Vector3 mxdistance = ( corners[ 4 ] - scenter );
199
200        if ( mndistance.squaredLength() < sradius &&
201                mxdistance.squaredLength() < sradius )
202        {
203                return INSIDE;
204        }
205
206        //find the square of the distance
207        //from the sphere to the box
208        for ( int i = 0 ; i < 3 ; i++ )
209        {
210                if ( scenter[ i ] < corners[ 0 ][ i ] )
211                {
212                        s = scenter[ i ] - corners[ 0 ][ i ];
213                        d += s * s;
214                }
215
216                else if ( scenter[ i ] > corners[ 4 ][ i ] )
217                {
218                        s = scenter[ i ] - corners[ 4 ][ i ];
219                        d += s * s;
220                }
221
222        }
223
224        bool partial = ( d <= sradius );
225
226        if ( !partial )
227        {
228                return OUTSIDE;
229        }
230
231        else
232        {
233                return INTERSECT;
234        }
235}
236
237Real BihPlaneEvent::KT = 2.0;
238Real BihPlaneEvent::KI = 2.0;
239
240//----------------------------------------------------------------------------
241// determine if this event is left or right of the reference event
242// if the absolute flag is set, we decide by the objectcenter wether the
243// event goes to left or right.
244void BihPlaneEvent::classify(const BihPlaneEvent& e, BihPlaneEvent::Side side, bool absolute)
245{
246        // only classify events of the same dimension
247        if (mDimension == e.mDimension)
248        {
249                if (!absolute)
250                {
251                        if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
252                        {
253                                mRenderable->setSide(PES_LEFT);
254                                return;
255                        }
256                        else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
257                        {
258                                mRenderable->setSide(PES_RIGHT);
259                                return;
260                        }
261                        else if (mType == PET_ON)
262                        {
263                                if (mPosition[mDimension] < e.mPosition[e.mDimension] ||
264                                        (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
265                                {
266                                        mRenderable->setSide(PES_LEFT);
267                                        return;
268                                }
269                                if (mPosition[mDimension] > e.mPosition[e.mDimension] ||
270                                        (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
271                                {
272                                        mRenderable->setSide(PES_RIGHT);
273                                        return;
274                                }
275                        }
276                } else
277                {
278                        // The object lies on the splitting plane
279                        // we decide with the object center if it goes right or left.
280                        Vector3 mMid=mRenderable->getBoundingBox().getCenter();
281                        float mMidDimension=0;
282                        switch (mDimension)
283                        {
284                                case BihPlaneEvent::PED_X:
285                                        mMidDimension=mMid.x;
286                                        break;
287                                case BihPlaneEvent::PED_Y:
288                                        mMidDimension=mMid.y;
289                                        break;
290                                case BihPlaneEvent::PED_Z:
291                                        mMidDimension=mMid.z;
292                                        break;
293                        }
294                        if (mMidDimension <= e.mPosition[e.mDimension])
295                        {
296                                mRenderable->setSide(PES_LEFT);
297                                return;
298                        }
299                        else if (mMidDimension > e.mPosition[e.mDimension])
300                        {
301                                mRenderable->setSide(PES_RIGHT);
302                                return;
303                        }
304                }
305
306
307
308
309        }
310}
311
312//----------------------------------------------------------------------------
313// clip this event to an aabb (move it so that the plane on one of the box planes)
314BihPlaneEvent BihPlaneEvent::clip(AxisAlignedBox& box, BihPlaneEvent::Dimension dim)
315{
316        Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
317        if (newpos[dim] < min[dim])
318                newpos[dim] = min[dim];
319        else if (newpos[dim] > max[dim])
320                newpos[dim] = max[dim];
321
322        return BihPlaneEvent(mRenderable, newpos, mDimension, mType);
323}
324
325//----------------------------------------------------------------------------
326// the surface area heuristic to determine the cost of splitting the parent aabb
327// along the plane represented by this event
328void BihPlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split)
329{
330        Real mu = splitBox(parent, split.bleft, split.bright);
331        Real sav = surfaceArea(parent);
332        Real pl = surfaceArea(split.bleft) / sav;
333        Real pr = surfaceArea(split.bright) / sav;
334        Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
335        Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
336
337        if (costl < costr)
338        {
339                split.cost = costl;
340                split.side = PES_LEFT;
341                split.nleft = nLeft + nPlane;
342                split.nright = nRight;
343        }
344        else
345        {
346                split.cost = costr;
347                split.side = PES_RIGHT;
348                split.nleft = nLeft;
349                split.nright = nPlane + nRight;
350
351        }
352        split.event = *this;
353}
354
355//----------------------------------------------------------------------------
356// the surface area heuristic to determine the cost of splitting the parent aabb
357// along the plane represented by this event modified for BV
358
359void BihPlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split,AxisAlignedBox left,AxisAlignedBox right)
360{
361        //Real mu = splitBox(parent, split.bleft, split.bright);
362        split.bleft=left;
363        split.bright=right;
364        Vector3 bmin = parent.getMinimum();
365        Vector3 bmax = parent.getMaximum();
366        Real mu=lookupPenalty(
367                (mPosition[mDimension] - bmin[mDimension]) /
368                (bmax[mDimension] - bmin[mDimension]));
369        Real sav = surfaceArea(parent);
370        Real pl = surfaceArea(split.bleft) / sav;
371        Real pr = surfaceArea(split.bright) / sav;
372        Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
373        Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
374
375        if (costl < costr)
376        {
377                split.cost = costl;
378                split.side = PES_LEFT;
379                split.nleft = nLeft + nPlane;
380                split.nright = nRight;
381        }
382        else
383        {
384                split.cost = costr;
385                split.side = PES_RIGHT;
386                split.nleft = nLeft;
387                split.nright = nPlane + nRight;
388
389        }
390        split.event = *this;
391}
392
393//----------------------------------------------------------------------------
394// split the parent aabb with the plane in this event
395Real BihPlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
396{
397        Vector3 bmin = parent.getMinimum();
398        Vector3 bmax = parent.getMaximum();
399        // calculate the penalty for spliting the box that way
400        Real mu = lookupPenalty(
401                (mPosition[mDimension] - bmin[mDimension]) /
402                (bmax[mDimension] - bmin[mDimension]));
403        // set corners which are the same as parent AABB
404        left.setMinimum(bmin);
405        right.setMaximum(bmax);
406        // modify "inner" corners
407        bmin[mDimension] = mPosition[mDimension];
408        bmax[mDimension] = mPosition[mDimension];
409        // set the corners on the split plane
410        left.setMaximum(bmax);
411        right.setMinimum(bmin);
412
413        return mu;
414}
415
416//----------------------------------------------------------------------------
417// compute surface area of a box ... DUH!
418Real BihPlaneEvent::surfaceArea(const AxisAlignedBox& box)
419{
420        Vector3 sides = box.getMaximum() - box.getMinimum();
421        return  2 * sides.x * sides.y +
422                2 * sides.y * sides.z +
423                2 * sides.z * sides.x;
424}
425
426//----------------------------------------------------------------------------
427// lookup the penalty for placing the splitting plane near to the edge of the AABB
428// 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
429Real BihPlaneEvent::lookupPenalty(Real p)
430{
431        // precomputed table of {x^6 + 1|0 <= x <= 1}
432        static Real mPenaltyLookupTable[PLT_SIZE];
433        static bool init_done = false;
434
435        if (!init_done)
436        {
437                Real step = 1.0  / (PLT_SIZE - 1);
438                Real x = 0.0;
439                //LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
440                for (int i = 0; i < PLT_SIZE; i++)
441                {
442                        mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
443                        x += step;
444                        //LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
445                }
446                init_done = true;
447                //LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
448        }
449
450        // normalize p to [0,1]
451        Real x = Math::Abs(p * 2 - 1);
452        // compute index
453        int i = Math::IFloor(x * (PLT_SIZE - 1));
454
455        return mPenaltyLookupTable[i];
456}
457
458//----------------------------------------------------------------------------
459// compute cost of the split, reward splitting of empty space (lambda, const),
460// penalize splitting off 'thin' slices (mu, const)
461Real BihPlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
462{
463        // reward splitting off chunks of empty space
464        Real lambda = 1.0;
465        if (nLeft == 0 || nRight == 0)
466        {
467                lambda = 0.8;
468        }
469
470        // penalize splitting off small chunks (thin slices)
471        Real mu = 1.0;
472        if (pLeft < 0.1 || pRight < 0.1 || pLeft > 0.9 || pRight > 0.9)
473        {
474                mu = 1.5;
475        }
476        return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
477}
478
479//----------------------------------------------------------------------------
480// compute cost of the split, reward splitting of empty space (lambda, const),
481// penalize splitting off 'thin' slices (mu, parameter)
482Real BihPlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
483{
484        // reward splitting off chunks of empty space
485        Real lambda = 1.0;
486        if (nLeft == 0 || nRight == 0)
487        {
488                lambda = 0.8;
489        }
490
491        return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
492}
493
494//----------------------------------------------------------------------------
495// surface area heuristic modified for the priority queue method of building
496// the probabilities (p, pl, pr) are relative to the global (all enclosing) aabb
497void BihPlaneEvent::pqSAH(Real globalSA,
498                                                  Real parentSA,
499                                                  int nLeft,
500                                                  int nPlane,
501                                                  int nRight,
502                                                  AxisAlignedBox& parentBox,
503                                                  BihSplitInfo& split)
504{
505        Real mu = splitBox(parentBox, split.bleft, split.bright);
506        Real p = parentSA / globalSA;
507        Real pl = surfaceArea(split.bleft) / globalSA;
508        Real pr = surfaceArea(split.bright) / globalSA;
509        Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
510        Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
511
512        if (costl < costr)
513        {
514                split.cost = costl;
515                split.side = PES_LEFT;
516                split.nleft = nLeft + nPlane;
517                split.nright = nRight;
518        }
519        else
520        {
521                split.cost = costr;
522                split.side = PES_RIGHT;
523                split.nleft = nLeft;
524                split.nright = nPlane + nRight;
525
526        }
527        split.event = *this;
528}
529
530//----------------------------------------------------------------------------
531// compute split cost without any penalties
532Real BihPlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
533{
534        return pParent * KT + (KI * (pLeft * nLeft + pRight * nRight));
535}
536
537//----------------------------------------------------------------------------
538// DEBUG
539String BihPlaneEvent::print()
540{
541        String dim, type;
542        if (mDimension == PED_X)
543                dim = "X";
544        if (mDimension == PED_Y)
545                dim = "Y";
546        if (mDimension == PED_Z)
547                dim = "Z";
548        if (mType == PET_END)
549                type = "END  ";
550        if (mType == PET_ON)
551                type = "ON   ";
552        if (mType == PET_START)
553                type = "START";
554        //return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
555        return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
556};
557
558//----------------------------------------------------------------------------
559String BihSplitInfo::print()
560{
561        String sside;
562        if (side == BihPlaneEvent::PES_BOTH)
563                sside = "BOTH ";
564        if (side == BihPlaneEvent::PES_LEFT)
565                sside = "LEFT ";
566        if (side == BihPlaneEvent::PES_RIGHT)
567                sside = "RIGHT";
568        return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " +
569                StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
570                " Side: " + sside + " Event: " + event.print() + " Leftbox: " +
571                StringConverter::toString(bleft.getMinimum()) + ", " +
572                StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
573                StringConverter::toString(bright.getMinimum()) + ", " +
574                StringConverter::toString(bright.getMaximum());
575};
576
577//----------------------------------------------------------------------------
578String BiHierarchy::BihSubdivisionCandidate::print()
579{               
580        String sside;
581        if (side == BihPlaneEvent::PES_BOTH)
582                sside = "BOTH ";
583        if (side == BihPlaneEvent::PES_LEFT)
584                sside = "LEFT ";
585        if (side == BihPlaneEvent::PES_RIGHT)
586                sside = "RIGHT";
587        return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
588                StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
589                " Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
590                best->print() +  " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
591                + StringConverter::toString(aabb.getMaximum());
592
593};
594
595//----------------------------------------------------------------------------
596//----------------------------------------------------------------------------
597//----------------------------------------------------------------------------
598
599BiHierarchy::BiHierarchy(int maxdepth, BuildMethod bm):
600mMaxDepth(maxdepth),
601mBuildMethod(bm),
602mHiLiteLevel(0),
603mShowAllBoxes(false),
604mShowNodes(true),
605mBihRoot(0),
606mBuildLog(0),
607mAlgorithm(BIHAL_SAH)
608{
609        init();
610}
611
612BiHierarchy::BiHierarchy(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes):
613mMaxDepth(maxdepth),
614mBuildMethod(bm),
615mHiLiteLevel(hilite),
616mShowAllBoxes(allboxes),
617mShowNodes(shownodes),
618mBihRoot(0),
619mBuildLog(0),
620mAlgorithm(BIHAL_SAH)
621{
622        init();
623}
624
625BiHierarchy::~BiHierarchy()
626{
627        delete mBihRoot;
628}
629
630void BiHierarchy::init()
631{
632        MaterialPtr mat;
633        TextureUnitState *tex;
634
635        // init visualization materials (unlit solid green/yellow)
636        mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxHiLite");
637        if (mat.isNull())
638        {
639                ColourValue green(0, 1, 0);
640                mat = MaterialManager::getSingleton().create("BiHierarchy/BoxHiLite", "General");
641                //mat->setAmbient(green);
642                //mat->setDiffuse(green);
643                mat->setLightingEnabled(false);
644                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
645                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
646        }
647
648        mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxLeft");
649        if (mat.isNull())
650        {
651                ColourValue red(1, 0, 0);
652                mat = MaterialManager::getSingleton().create("BiHierarchy/BoxLeft", "General");
653                //mat->setAmbient(green);
654                //mat->setDiffuse(green);
655                mat->setLightingEnabled(false);
656                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
657               
658                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, red, red);
659        }
660
661        mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxRight");
662        if (mat.isNull())
663        {
664                ColourValue green(0, 1, 0);
665                mat = MaterialManager::getSingleton().create("BiHierarchy/BoxRight", "General");
666                //mat->setAmbient(green);
667                //mat->setDiffuse(green);
668                mat->setLightingEnabled(false);
669                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
670                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
671        }
672        mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxLeftDark");
673        if (mat.isNull())
674        {
675                ColourValue red(0.5, 0, 0);
676                mat = MaterialManager::getSingleton().create("BiHierarchy/BoxLeftDark", "General");
677                //mat->setAmbient(green);
678                //mat->setDiffuse(green);
679                mat->setLightingEnabled(false);
680                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
681               
682                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, red, red);
683        }
684
685        mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxRightDark");
686        if (mat.isNull())
687        {
688                ColourValue green(0, 0.5, 0);
689                mat = MaterialManager::getSingleton().create("BiHierarchy/BoxRightDark", "General");
690                //mat->setAmbient(green);
691                //mat->setDiffuse(green);
692                mat->setLightingEnabled(false);
693                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
694                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
695        }
696
697        mat = MaterialManager::getSingleton().getByName("BiHierarchy/BoxViz");
698        if (mat.isNull())
699        {
700                ColourValue yellow(1, 1, 0);
701                mat = MaterialManager::getSingleton().create("BiHierarchy/BoxViz", "General");
702                //mat->setAmbient(yellow);
703                //mat->setDiffuse(yellow);
704                mat->setLightingEnabled(false);
705                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
706                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, yellow, yellow);
707        }
708        mat = MaterialManager::getSingleton().getByName("BaseWhiteNoLighting");
709        if (mat.isNull())
710        {
711                ColourValue white(1, 1, 0);
712                mat = MaterialManager::getSingleton().create("BaseWhiteNoLighting", "General");
713                //mat->setAmbient(yellow);
714                //mat->setDiffuse(yellow);
715                mat->setLightingEnabled(false);
716                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
717                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, white, white);
718        }
719
720        // retrieve or create build log
721        try
722        {
723                mBuildLog = LogManager::getSingleton().getLog(BiHierarchy_LOGNAME);
724        }
725        catch (Exception&)
726        {               
727                mBuildLog = LogManager::getSingleton().createLog(BiHierarchy_LOGNAME);
728        }
729
730        setEnhancedVis(false);
731}
732
733/************************************************************************/
734/* BiHierarchy insert/delete functions                                       */
735/************************************************************************/
736
737void BiHierarchy::remove(BihRenderable * rend)
738{
739        // DEBUG
740        //LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<BiHierarchySceneNode *>(rend))->getName());
741        std::queue<LeafPtr> cleanup;
742        LeafPtr leaf;
743        LeafSet ls = rend->getLeaves();
744        LeafSet::iterator it = ls.begin();
745        LeafSet::iterator end = ls.end();
746        while (it != end)
747        {
748                cleanup.push(*it);
749                it++;
750        }
751        while (!cleanup.empty())
752        {
753                leaf = cleanup.front();
754                cleanup.pop();
755                leaf->remove(rend);
756                bool gone = rend->detachFrom(leaf);
757                assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
758                //dump();
759                recDelete(leaf);
760                //dump();
761        }
762}
763
764void BiHierarchy::recDelete(BiHierarchy::Node * node)
765{
766        if (node == 0) // DEBUG
767        {
768                OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
769                        "SNAFU while inserting BihRenderable into BiHierarchy.",
770                        "BiHierarchy::recInsert" );
771                return;
772        }
773
774        if (node->isEmpty())
775        {
776                if (node == mBihRoot)
777                {
778                        OGRE_DELETE(mBihRoot);
779                }
780                else
781                {
782                        BiHierarchy::Branch * parent = BIHBRANCHPTR_CAST(node->getParent());
783                        if (node == parent->mLeft)
784                        {
785                                OGRE_DELETE(parent->mLeft);
786                        }
787                        else if (node == parent->mRight)
788                        {
789                                OGRE_DELETE(parent->mRight);
790                        }
791                        recDelete(parent);
792                }
793        }
794}
795
796void BiHierarchy::insert(BihRenderable * rend)
797{
798        // make sure the tree exists
799        if (mBihRoot)
800        {
801                // make sure the renderable is inside the world bounding box
802                AxisAlignedBox aabb = rend->getBoundingBox();
803                AxisAlignedBox isect = mBihRoot->mAABB.intersection(aabb);
804                if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
805                {
806                        recInsert(mBihRoot, rend);
807                }
808                else
809                {
810                        //LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
811                        BihRenderableList nodelist;
812                        nodelist.push_back(rend);
813                        addRendToList(mBihRoot, nodelist);
814                        OGRE_DELETE(mBihRoot);
815                        mBihRoot = buildFromList(nodelist, 0, AxisAlignedBox());
816                }
817        }
818        // otherwise build a new one
819        else
820        {
821                build(rend);
822        }
823}
824
825void BiHierarchy::recInsert(BiHierarchy::Node * node, BihRenderable * rend)
826{
827        if (node == 0) // DEBUG
828        {
829                OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
830                        "SNAFU while inserting BihRenderable into BiHierarchy.",
831                        "BiHierarchy::recInsert" );
832                return;
833        }
834
835        // rebuild the leaf/replace with subtree ...
836        if (node->isLeaf())
837        {
838                //LogManager::getSingleton().logMessage("## Replacing leaf.");
839                rebuildSubtree(node, rend);
840        }
841        else
842        {
843                BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
844                AxisAlignedBox aabb = rend->getBoundingBox();
845                Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
846                Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
847                if (smin == smax)
848                {
849                        if (smax == Plane::NEGATIVE_SIDE ||
850                                (smax == Plane::NO_SIDE && branch->mPlaneSide == BihPlaneEvent::PES_LEFT))
851                        {
852                                if (branch->mLeft)
853                                        recInsert(branch->mLeft, rend);
854                                else
855                                        recInsertNew(branch, BihPlaneEvent::PES_LEFT, rend);
856                        }
857                        else if (smin == Plane::POSITIVE_SIDE ||
858                                (smin == Plane::NO_SIDE && branch->mPlaneSide == BihPlaneEvent::PES_RIGHT))
859                        {
860                                if (branch->mRight)
861                                        recInsert(branch->mRight, rend);
862                                else
863                                        recInsertNew(branch, BihPlaneEvent::PES_RIGHT, rend);
864                        }
865                }
866                else
867                {
868                        if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
869                        {
870                                if (branch->mLeft)
871                                        recInsert(branch->mLeft, rend);
872                                else
873                                        recInsertNew(branch, BihPlaneEvent::PES_LEFT, rend);
874                        }
875                        else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
876                        {
877                                if (branch->mRight)
878                                        recInsert(branch->mRight, rend);
879                                else
880                                        recInsertNew(branch, BihPlaneEvent::PES_RIGHT, rend);
881                        }
882                        else
883                        {
884                                // to avoid SNAFUs, rebuild whole subtree
885                                //LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
886                                rebuildSubtree(node, rend);
887                        }
888                }
889        }
890}
891
892void BiHierarchy::recInsertNew(BiHierarchy::Branch * parent, BihPlaneEvent::Side side, BihRenderable * rend)
893{
894        //LogManager::getSingleton().logMessage("## Inserting into new subtree");
895
896        AxisAlignedBox left, rigth, aabb;
897        BihPlaneEventList events;
898        int nObjects;
899       
900        rend->computeScene(events, aabb, nObjects, false);
901
902        // override aabb
903        splitBox(*parent, left, rigth);
904        if (side == BihPlaneEvent::PES_LEFT)
905        {
906                aabb = left;
907                if (mBuildMethod == BIHBM_RECURSIVE)
908                        parent->mLeft = recBuild(events, nObjects, aabb, parent);
909                else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
910                        parent->mLeft = pqBuild(events, nObjects, aabb, parent);
911                else
912                {
913                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
914                                "Invalid build method for the BiHierarchy.",
915                                "BiHierarchy::buildFromList");
916                        parent->mLeft = 0;
917                }
918               
919        }
920        else if (side == BihPlaneEvent::PES_RIGHT)
921        {
922                aabb = rigth;
923                if (mBuildMethod == BIHBM_RECURSIVE)
924                        parent->mRight = recBuild(events, nObjects, aabb, parent);
925                else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
926                        parent->mRight = pqBuild(events, nObjects, aabb, parent);
927                else
928                {
929                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
930                                "Invalid build method for the BiHierarchy.",
931                                "BiHierarchy::buildFromList");
932                        parent->mRight = 0;
933                }
934        }
935}
936
937void BiHierarchy::rebuildSubtree(BiHierarchy::Node * node, BihRenderable * rend)
938{
939        //LogManager::getSingleton().logMessage("## Rebuilding subtree");
940
941        AxisAlignedBox aabb = node->mAABB;
942       
943        BihRenderableList nodelist;
944        nodelist.push_back(rend);
945        addRendToList(node, nodelist);
946
947        if (node == mBihRoot)
948        {
949                OGRE_DELETE(mBihRoot);
950                mBihRoot = buildFromList(nodelist, 0, aabb);
951        }
952        else
953        {
954                BiHierarchy::Branch * parent = BIHBRANCHPTR_CAST(node->getParent());
955
956                if (node == parent->mLeft)
957                {
958                        OGRE_DELETE(parent->mLeft);
959                        parent->mLeft = buildFromList(nodelist, parent, aabb);
960                }
961                else if (node == parent->mRight)
962                {
963                        OGRE_DELETE(parent->mRight);
964                        parent->mRight = buildFromList(nodelist, parent, aabb);
965                }
966                else
967                {
968                        OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
969                                "SNAFU while inserting BihRenderable into BiHierarchy.",
970                                "BiHierarchy::recInsert" );
971                }
972        }
973}
974
975// compute both AABB then return the requested one.
976void BiHierarchy::splitBox(const BiHierarchy::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
977{
978        Vector3 bmin = parent.mAABB.getMinimum();
979        Vector3 bmax = parent.mAABB.getMaximum();
980        Real pos = - parent.mSplitPlane->d;
981        int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
982        // set corners which are the same as parent AABB
983        left.setMinimum(bmin);
984        right.setMaximum(bmax);
985        // modify "inner" corners
986        bmin[dim] = pos;
987        bmax[dim] = pos;
988        // set the corners on the split plane
989        left.setMaximum(bmax);
990        right.setMinimum(bmin);
991}
992
993void BiHierarchy::addRendToList(BiHierarchy::Node * node, BihRenderableList& nodelist)
994{
995        if (node->isLeaf())
996        {
997                BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
998                BihRenderableList::iterator it  = leaf->mBihRenderables.begin();
999                BihRenderableList::iterator end = leaf->mBihRenderables.end();
1000                while (it != end)
1001                {
1002                        nodelist.push_back(*it);
1003                        it++;
1004                }
1005        }
1006        else
1007        {
1008                BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
1009                if (branch->mLeft)
1010                        addRendToList(branch->mLeft, nodelist);
1011                if (branch->mRight)
1012                        addRendToList(branch->mRight, nodelist);
1013        }
1014}
1015
1016/************************************************************************/
1017/*                BiHierarchy build functions                           */
1018/************************************************************************/
1019
1020void BiHierarchy::build(BihRenderable * sceneRoot)
1021{
1022        Timer *timer = Root::getSingleton().getTimer();
1023        unsigned long t1, t2, t3, t4;
1024
1025        mTreeStats.clear();
1026       
1027        // data we want to collect
1028        BihPlaneEventList events;
1029        AxisAlignedBox aabb;
1030        int nObjects = 0;
1031
1032        t1 = timer->getMicroseconds(); // DEBUG
1033        sceneRoot->computeScene(events, aabb, nObjects);
1034        t2 = timer->getMicroseconds(); // DEBUG
1035        events.sort();
1036        t3 = timer->getMicroseconds(); // DEBUG
1037
1038        mTreeStats.mNumSceneNodes = nObjects;
1039
1040        assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
1041        // hack to avoid SNAFU with "2-dimensional" scene
1042        aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
1043        aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
1044
1045        if (mBuildMethod == BIHBM_RECURSIVE)
1046                mBihRoot = recBuild(events, nObjects, aabb, 0);
1047        else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
1048                mBihRoot = pqBuild(events, nObjects, aabb, 0);
1049        else
1050        {
1051                OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
1052                        "Invalid build method for the BiHierarchy.",
1053                        "BiHierarchy::build");
1054                mBihRoot = 0;
1055        }
1056
1057        t4 = timer->getMicroseconds(); // DEBUG
1058
1059        String method = "Invalid";
1060        if (mBuildMethod == BIHBM_RECURSIVE)
1061                method = "Recursive";
1062        else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
1063                method = "Priority Queue";
1064
1065        mBuildLog->logMessage("######## SAH Statistics ########");
1066        mBuildLog->logMessage("Build Method: " + method);
1067        mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
1068        mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
1069        mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
1070        mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
1071        mBuildLog->logMessage("Tree Depth: " + StringConverter::toString(mMaxDepth));
1072        mBuildLog->logMessage("Number of Objects: " + StringConverter::toString(mTreeStats.mNumSceneNodes));
1073        mBuildLog->logMessage("Number of Leaves: " + StringConverter::toString(mTreeStats.mNumLeaves));
1074        mBuildLog->logMessage("Number of Nodes: " + StringConverter::toString(mTreeStats.mNumNodes));
1075        mBuildLog->logMessage("Total cost: " + StringConverter::toString(calcCost()));
1076        mBuildLog->logMessage("################################");
1077}
1078
1079BiHierarchy::Node * BiHierarchy::buildFromList(BihRenderableList& nodelist, BiHierarchy::Branch * parent, AxisAlignedBox& aabb)
1080{
1081        // data we want to collect
1082        BihPlaneEventList events;
1083        AxisAlignedBox nodeaabb;
1084        int nObjects = 0;
1085
1086        BihRenderableList::iterator it = nodelist.begin();
1087        BihRenderableList::iterator end = nodelist.end();
1088        while (it != end)
1089        {
1090                (*it)->computeScene(events, nodeaabb, nObjects, false);
1091                it++;
1092        }
1093
1094        events.sort();
1095       
1096        // HACK
1097        if (aabb.isNull())
1098        {
1099                aabb = nodeaabb;
1100        }
1101
1102        if (mBuildMethod == BIHBM_RECURSIVE)
1103                return recBuild(events, nObjects, aabb, parent);
1104        else if (mBuildMethod == BIHBM_PRIORITYQUEUE)
1105                return pqBuild(events, nObjects, aabb, parent);
1106        else
1107        {
1108                OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
1109                        "Invalid build method for the BiHierarchy.",
1110                        "BiHierarchy::buildFromList");
1111                return 0;
1112        }
1113}
1114
1115BiHierarchy::Node * BiHierarchy::recBuild(BihPlaneEventList& events, int nObjects, AxisAlignedBox& aabb, BiHierarchy::Branch * parent)
1116{
1117        // determine the depth we are on
1118        int level = 0;
1119        if (parent)
1120        {
1121                level = parent->getLevel() + 1;
1122        }
1123
1124        /************************************************/
1125        /**************** BEGIN FINDPLANE ***************/
1126        /************************************************/
1127        // find optimal split plane and split node accordingly
1128
1129        // initialize
1130        const int dim = 3;
1131        int pStart, pOn, pEnd;
1132        int nLeft[dim], nPlane[dim], nRight[dim];
1133        int nObjectCount[dim];
1134        float LeftOffset[dim],RightOffset[dim];
1135        for (int i = 0; i < dim; i++)
1136        {
1137                nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1138                nObjectCount[i]=0;
1139        }
1140
1141        BihSplitInfo split, best;
1142        best.cost = Math::POS_INFINITY;
1143
1144        BihPlaneEventList::iterator begin = events.begin();
1145        BihPlaneEventList::iterator end = events.end();
1146        BihPlaneEventList::iterator it = begin;
1147
1148        BihPlaneEventList::iterator it_a = begin; // iterator for adjusting the bounding box
1149   
1150        AxisAlignedBox minLefts[dim];
1151        AxisAlignedBox minRights[dim];
1152
1153        bool LeftMod[dim];
1154        bool RightMod[dim];
1155
1156        AxisAlignedBox minLeft;
1157        AxisAlignedBox minRight;
1158       
1159
1160        // try all planes to find the best one for the given set of objects
1161       
1162        // Use SAH method
1163        if (mAlgorithm==BIHAL_SAH)
1164        {
1165                while (it != end)
1166                {
1167                        BihPlaneEventList::iterator p = it;
1168                        pStart = pOn = pEnd = 0;
1169                       
1170                        while (it != end && p->equalsType(*it, BihPlaneEvent::PET_END))
1171                        {
1172                                it++; pEnd++;
1173                        }
1174                        while (it != end && p->equalsType(*it, BihPlaneEvent::PET_ON))
1175                        {
1176                                it++; pOn++;
1177                        }
1178                        while (it != end && p->equalsType(*it, BihPlaneEvent::PET_START))
1179                        {
1180                                it++; pStart++;
1181                        }
1182                       
1183                       
1184                        int d = p->getDimension();
1185                        nPlane[d] = pOn;
1186                        //nRight[d] -= pOn; nRight[d] -= pEnd;
1187
1188            // find the corrected offsets for the left and right bounding box
1189                        it_a = begin;
1190                        LeftOffset[d]=0;
1191                        RightOffset[d]=0;
1192                        minLefts[d].setNull();
1193                minRights[d].setNull();
1194                        nRight[d]=0;
1195                        nLeft[d]=0;
1196                       
1197
1198                        while (it_a != end)
1199                        {
1200                                if (it_a->getDimension()==d)
1201                                {
1202                                        it_a->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1203                                        it_a->getRenderable()->setClassified(false);
1204                                        it_a->classify(*p, split.side,true);
1205                                        if (it_a->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1206                                        {
1207                                                if (!it_a->getRenderable()->isClassified())
1208                                                {
1209                                                        it_a->getRenderable()->setClassified(true);
1210                                                        nRight[d]++;
1211                                                }
1212                                                minRights[d].merge(it_a->getRenderable()->getBoundingBox());
1213                                               
1214                                        }
1215                                        // left-only nodes go in left list
1216                                        else if (it_a->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1217                                        {
1218                                                if (!it_a->getRenderable()->isClassified())
1219                                                {
1220                                                        it_a->getRenderable()->setClassified(true);
1221                                                        nLeft[d]++;
1222                                                }
1223                                                minLefts[d].merge(it_a->getRenderable()->getBoundingBox());
1224                                               
1225                                        }
1226                                }
1227
1228
1229                                it_a++;
1230                        }
1231
1232                       
1233                                p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split,minLefts[d],minRights[d]);
1234                                mBuildLog->logMessage("SAH " + StringConverter::toString(best.cost)+ " " + StringConverter::toString(split.cost) +
1235                                        "dim: " + StringConverter::toString(d));
1236                                if (split.cost < best.cost)
1237                                {
1238                                        best = split;
1239                                }
1240                       
1241
1242                        //nLeft[d] += pStart; nLeft[d] += pOn;
1243                       
1244                    nPlane[d] = 0;
1245                }
1246        } else
1247        {   
1248               
1249                int d;
1250                while (it != end)
1251                {
1252                        BihPlaneEventList::iterator p = it;
1253                        d = p->getDimension();
1254                        //if ((p->equalsType(*it, BihPlaneEvent::PET_START)) || (p->equalsType(*it, BihPlaneEvent::PET_ON)))
1255                          nObjectCount[d]++;
1256                        it++;
1257                }
1258
1259                int MaxDimension=1;
1260                for (int i = 1; i < dim; i++)
1261            {
1262                    if (nObjectCount[i]>nObjectCount[i-1]) MaxDimension=i;
1263            }
1264                it = begin;
1265               
1266                nObjectCount[MaxDimension]/=2;
1267                while ((it != end) && (nObjectCount[MaxDimension]))
1268                {
1269                        BihPlaneEventList::iterator p = it;
1270                        if  (p->getDimension()== MaxDimension)
1271                        {
1272                          nObjectCount[MaxDimension]--;
1273                          best.event=*it;
1274                          best.cost=0;
1275                         
1276                        }
1277                        it++;
1278                }
1279
1280               
1281
1282               
1283       
1284
1285
1286
1287
1288        }
1289
1290
1291        /************************************************/
1292        /**************** BEGIN TERMINATE ***************/
1293        /************************************************/
1294        // check terminating condition
1295        if (/*best.cost > BihPlaneEvent::KI*nObjects ||*/ level >= mMaxDepth || nObjects<20 )
1296        {
1297                // Terminating condition reached, create leaf and add renderables to list
1298                mBuildLog->logMessage("Terminate " + StringConverter::toString(best.cost)+ " o:" + StringConverter::toString(nObjects) +
1299                                " ki: " + StringConverter::toString(BihPlaneEvent::KI*nObjects)+ " dim: " + StringConverter::toString(best.event.getDimension()));
1300                BiHierarchy::Leaf * leaf = new BiHierarchy::Leaf(this, level, aabb, parent);
1301                if (parent->GetSide()==1) leaf->SetToLeft(); else leaf->SetToRight();
1302
1303               
1304                BihRenderable *rend;
1305                it = begin;
1306                while (it != end)
1307                {
1308                        rend = it->getRenderable();
1309                        rend->setClassified(false);
1310                        if (rend->attachTo(leaf, this))
1311                        {
1312                                leaf->insert(rend);
1313                        }
1314                        it++;
1315                }
1316                // update stats
1317                ++ mTreeStats.mNumNodes;
1318                ++ mTreeStats.mNumLeaves;
1319                // update bounding box
1320                leaf->_updateBounds(false);
1321                return leaf;
1322        }
1323
1324        /************************************************/
1325        /**************** BEGIN CLASSIFY ****************/
1326        /************************************************/
1327        // split the event list in left and right sub-lists
1328        else
1329        {
1330                BihPlaneEventList eventsRight, eventsLeft;
1331                it = begin;
1332                // slightly redundant, since we mark each renderable up to 6 times
1333                while (it != end)
1334                {
1335                        it->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1336                        it->getRenderable()->setClassified(false);
1337                        it++;
1338                }
1339                // now classify all renderables. do they belong to the left child, the right child or both?
1340                it = begin;
1341                while (it != end)
1342                {
1343                        it->classify(best.event, best.side,true);
1344                        it++;
1345                }
1346                // divide the event lists
1347                int nLeftS = 0, nRightS = 0, nBothS = 0;
1348                it = begin;
1349
1350                minLeft.setNull();
1351            minRight.setNull();
1352
1353               
1354       
1355                while (it != end)
1356                {
1357                        // right-only nodes go in right list
1358                        if (it->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1359                        {
1360                                if (!it->getRenderable()->isClassified())
1361                                {
1362                                        it->getRenderable()->setClassified(true);
1363                                        nRightS++;
1364                                }
1365                                minRight.merge(it->getRenderable()->getBoundingBox());
1366                                //mBuildLog->logMessage("merge right " + StringConverter::toString(minRight.volume()));
1367                                eventsRight.push_back(*it);
1368                        }
1369                        // left-only nodes go in left list
1370                        else if (it->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1371                        {
1372                                if (!it->getRenderable()->isClassified())
1373                                {
1374                                        it->getRenderable()->setClassified(true);
1375                                        nLeftS++;
1376                                }
1377                                minLeft.merge(it->getRenderable()->getBoundingBox());
1378                                //mBuildLog->logMessage("merge left " + StringConverter::toString(minLeft.volume()));
1379                                eventsLeft.push_back(*it);
1380                        }
1381                        // remaining nodes go in both lists, bust must be clipped to prevent
1382                        // events from lying outside the new nodes aabb
1383                        else
1384                        {
1385                                if (!it->getRenderable()->isClassified())
1386                                {
1387                                        it->getRenderable()->setClassified(true);
1388                                        nBothS++;
1389                                }
1390                               
1391                                // calculate the intersecting box for the right side
1392               
1393                 
1394                                  minRight.merge(best.bright.intersection(it->getRenderable()->getBoundingBox()));
1395                               
1396
1397                                //mBuildLog->logMessage("merge Right Overlap " + StringConverter::toString(minRight.volume()));
1398                                eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
1399                               
1400                                  minLeft.merge(best.bleft.intersection(it->getRenderable()->getBoundingBox()));
1401                               
1402                                //mBuildLog->logMessage("merge Left Overlap " + StringConverter::toString(minLeft.volume()));
1403                                eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
1404                        }
1405                        it++;
1406                }
1407
1408                mBuildLog->logMessage("Split R:" + StringConverter::toString(nRightS)+ " L:" + StringConverter::toString(nLeftS) +
1409                                " O: " + StringConverter::toString(nObjects));
1410
1411
1412                // calculate minimum of the left bounding box
1413                /*
1414                AxisAlignedBox minimum;
1415                minimum.setNull();
1416                it=eventsLeft.begin();
1417                while (it!=eventsLeft.end())
1418                {
1419                        minimum.merge(it->getRenderable()->getBoundingBox());
1420                        it++;
1421                }
1422                */
1423
1424
1425
1426                // create a new branch node and continue recursion
1427                BiHierarchy::Branch * branch = new BiHierarchy::Branch(this, level, aabb, parent,
1428                        best.event.getSplitPlane(), best.side);
1429
1430                // now create the child nodes and continue recursion
1431                /*
1432                if (best.bleft.volume()>minLeft.volume())
1433                {
1434                        mBuildLog->logMessage("Volume Smaller Left " + StringConverter::toString(minLeft.volume()) + " " + StringConverter::toString(best.bleft.volume(),3,3));
1435                }
1436
1437                if (best.bright.volume()>minRight.volume())
1438                {
1439                        mBuildLog->logMessage("Volume Smaller Right " + StringConverter::toString(minRight.volume()) + " " + StringConverter::toString(best.bright.volume(),3,3));
1440                }
1441                */
1442
1443                if (eventsLeft.size() > 0)
1444                {
1445                       
1446                        branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, /*best.bleft*/minLeft, branch);
1447                        branch->mLeft->SetToLeft();
1448                        mBuildLog->logMessage("SetToLeft");
1449                        //branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
1450                }
1451                if (eventsRight.size() > 0)
1452                {
1453                       
1454                        branch->mRight = recBuild(eventsRight, nBothS + nRightS, /*best.bright*/ minRight, branch);
1455                        branch->mRight->SetToRight();
1456                        mBuildLog->logMessage("SetToRight");
1457
1458
1459                        //branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
1460                }
1461
1462                // update stats
1463                ++ mTreeStats.mNumNodes;
1464
1465                // update bounding box
1466                branch->_updateBounds(false);
1467
1468                return branch;
1469        }
1470}
1471
1472BiHierarchy::Node * BiHierarchy::pqBuild(BihPlaneEventList& events,
1473                                                                                 int nObjects, AxisAlignedBox& aabb,
1474                                                                                 BiHierarchy::Branch * parent)
1475{
1476        SplitCandidatePQ pqueue;
1477        Real globalTreeCost;
1478        Real globalSA;
1479
1480        BiHierarchy::Node * newNode = 0, * topNode = 0;
1481        // init global tree cost
1482        globalTreeCost = BihPlaneEvent::KI * nObjects;
1483        globalSA = BihPlaneEvent::surfaceArea(aabb);
1484
1485        BihPlaneEventList * e = new BihPlaneEventList(events);
1486
1487        // inital split candidate
1488        BihSplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
1489        BihSubdivisionCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost,
1490                globalTreeCost - best->cost, best, BihPlaneEvent::PES_BOTH);
1491        pqueue.push(splitcandidate);
1492
1493
1494        /*** BEGIN ITERATIVE BUILD ***/
1495        while (!pqueue.empty())
1496        {
1497                BihSubdivisionCandidate sc = pqueue.top();
1498                pqueue.pop();
1499
1500                // determine the depth we are on
1501                int level = 0;
1502                if (sc.parent)
1503                {
1504                        level = sc.parent->getLevel() + 1;
1505                }
1506
1507                /************************************************/
1508                /**************** BEGIN TERMINATE ***************/
1509                /************************************************/
1510                // check terminating condition
1511                if (sc.decrease < 0.0 || level >= mMaxDepth)
1512                {
1513                        // Terminating condition reached, create leaf and add renderables to list
1514                        BiHierarchy::Leaf * leaf = new BiHierarchy::Leaf(this, level, sc.aabb, sc.parent);
1515                        BihRenderable *rend;
1516                        BihPlaneEventList::iterator begin = sc.events->begin();
1517                        BihPlaneEventList::iterator end = sc.events->end();
1518                        BihPlaneEventList::iterator it = begin;
1519                        while (it != end)
1520                        {
1521                                rend = it->getRenderable();
1522                                rend->setClassified(false);
1523                                if (rend->attachTo(leaf, this))
1524                                {
1525                                        leaf->insert(rend);
1526                                }
1527                                it++;
1528                        }
1529                        newNode = leaf;
1530                        if (!topNode)
1531                                topNode = leaf;
1532                        // update stats
1533                        ++ mTreeStats.mNumNodes;
1534                        ++ mTreeStats.mNumLeaves;
1535                }
1536
1537                /************************************************/
1538                /**************** BEGIN CLASSIFY ****************/
1539                /************************************************/
1540                else
1541                {
1542                        BihPlaneEventList * eventsLeft = new BihPlaneEventList();
1543                        BihPlaneEventList * eventsRight = new BihPlaneEventList();
1544                        BihPlaneEventList::iterator begin = sc.events->begin();
1545                        BihPlaneEventList::iterator end = sc.events->end();
1546                        BihPlaneEventList::iterator it = begin;
1547                        // slightly redundant, since we mark each renderable up to 6 times
1548                        while (it != end)
1549                        {
1550                                it->getRenderable()->setSide(BihPlaneEvent::PES_BOTH);
1551                                it->getRenderable()->setClassified(false);
1552                                it++;
1553                        }
1554
1555                        // now classify all renderables. do they belong to the left child, the right child or both?
1556                        it = begin;
1557                        while (it != end)
1558                        {
1559                                it->classify(sc.best->event, sc.best->side,false);
1560                                it++;
1561                        }
1562
1563                        // divide the event lists
1564                        int nLeftS = 0, nRightS = 0, nBothS = 0;
1565                        it = begin;
1566                        while (it != end)
1567                        {
1568                                // right-only events go in the right list
1569                                if (it->getRenderable()->getSide() == BihPlaneEvent::PES_RIGHT)
1570                                {
1571                                        if (!it->getRenderable()->isClassified())
1572                                        {
1573                                                it->getRenderable()->setClassified(true);
1574                                                nRightS++;
1575                                        }
1576
1577                                        eventsRight->push_back(*it);
1578                                }
1579                                // left-only events go in the left list
1580                                else if (it->getRenderable()->getSide() == BihPlaneEvent::PES_LEFT)
1581                                {
1582                                        if (!it->getRenderable()->isClassified())
1583                                        {
1584                                                it->getRenderable()->setClassified(true);
1585                                                nLeftS++;
1586                                        }
1587                                        eventsLeft->push_back(*it);
1588                                }
1589                                // the rest goes in both lists after being clipped
1590                                else
1591                                {
1592                                        if (!it->getRenderable()->isClassified())
1593                                        {
1594                                                it->getRenderable()->setClassified(true);
1595                                                nBothS++;
1596                                        }
1597
1598                                        eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
1599                                        eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
1600                                }
1601                                it++;
1602                        }
1603
1604                        // create a new branch node
1605                        BiHierarchy::Branch * branch = new BiHierarchy::Branch(this, level, sc.aabb, sc.parent,
1606                                sc.best->event.getSplitPlane(), sc.best->side);
1607
1608                        globalTreeCost -= sc.decrease;
1609
1610
1611                        // now for each potential child node, compute the split plane and the cost decrease
1612                        // and place them in the queue
1613                        if (eventsLeft->size() > 0)
1614                        {
1615                                best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
1616                                Real old = BihPlaneEvent::surfaceArea(sc.best->bleft)/globalSA*BihPlaneEvent::KI*(nLeftS + nBothS);
1617                                BihSubdivisionCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
1618                                        branch, old, old - best->cost, best, BihPlaneEvent::PES_LEFT);
1619                                pqueue.push(scleft);
1620                        }
1621                        // cleanup
1622                        else
1623                        {
1624                                delete eventsLeft;
1625                        }
1626
1627                        if (eventsRight->size() > 0)
1628                        {
1629                                best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
1630                                Real old = BihPlaneEvent::surfaceArea(sc.best->bright)/globalSA*BihPlaneEvent::KI*(nBothS + nRightS);
1631                                BihSubdivisionCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
1632                                        branch, old, old - best->cost, best, BihPlaneEvent::PES_RIGHT);
1633                                pqueue.push(scright);
1634                        }
1635                        // cleanup
1636                        else
1637                        {
1638                                delete eventsRight;
1639                        }
1640
1641                        newNode = branch;
1642                        if (!topNode)
1643                                topNode = branch;
1644
1645
1646                        // update stats
1647                        ++ mTreeStats.mNumNodes;
1648                }
1649
1650                // attach new node to parent
1651                if (sc.parent)
1652                {
1653                        if (sc.side == BihPlaneEvent::PES_LEFT)
1654                        {
1655                                sc.parent->mLeft = newNode;
1656                        }
1657                        else if (sc.side == BihPlaneEvent::PES_RIGHT)
1658                        {
1659                                sc.parent->mRight = newNode;
1660                        }
1661                        else
1662                        {
1663                                OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
1664                                        "PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","BiHierarchy::pqBuild");
1665                        }
1666                }
1667
1668                // update bounding boxes when geometry (leaf) was added
1669                if (newNode->isLeaf())
1670                        newNode->_updateBounds();
1671
1672                //cleanup
1673                OGRE_DELETE(sc.events);
1674                OGRE_DELETE(sc.best);
1675        }
1676        mBuildLog->logMessage("Cost after PQBUILD €" + StringConverter::toString(globalTreeCost));
1677        return topNode;
1678}
1679
1680//-------------------------------------------------------------------------
1681BihSplitInfo * BiHierarchy::pqFindPlane(BihPlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
1682{
1683        static const int dim = 3;
1684        int pStart, pOn, pEnd;
1685        int nLeft[dim], nPlane[dim], nRight[dim];
1686        for (int i = 0; i < dim; i++)
1687        {
1688                nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1689        }
1690
1691        BihSplitInfo split, best;
1692        best.cost = Math::POS_INFINITY;
1693
1694        Real parentSA = BihPlaneEvent::surfaceArea(aabb);
1695
1696        BihPlaneEventList::iterator begin = events->begin();
1697        BihPlaneEventList::iterator end = events->end();
1698        BihPlaneEventList::iterator it = begin;
1699        // try all planes to find the best one for the given set of objects
1700        while (it != end)
1701        {
1702                BihPlaneEventList::iterator p = it;
1703                pStart = pOn = pEnd = 0;
1704                while (it != end && p->equalsType(*it, BihPlaneEvent::PET_END))
1705                {
1706                        it++; pEnd++;
1707                }
1708                while (it != end && p->equalsType(*it, BihPlaneEvent::PET_ON))
1709                {
1710                        it++; pOn++;
1711                }
1712                while (it != end && p->equalsType(*it, BihPlaneEvent::PET_START))
1713                {
1714                        it++; pStart++;
1715                }
1716                int d = p->getDimension();
1717                nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1718                p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
1719                if (split.cost < best.cost)
1720                {
1721                        best = split;
1722                }
1723                nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1724        }
1725        return new BihSplitInfo(best);
1726}
1727
1728
1729
1730/************************************************************************/
1731/*               BiHierarchy rendering functions                        */
1732/************************************************************************/
1733
1734
1735//-------------------------------------------------------------------------
1736void BiHierarchy::queueVisibleObjects(BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
1737        bool showBoxes, BiHierarchy::NodeList& visibleNodes)
1738{
1739        mFrameStats.clear();
1740        cam->mNumVisQueries = 0;
1741
1742        if (mBihRoot)
1743                recQueueVisibleObjects(mBihRoot, Root::getSingleton().getCurrentFrameNumber(),
1744                        cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1745
1746        mFrameStats.mTraversedNodes = cam->mNumVisQueries;
1747}
1748
1749//-------------------------------------------------------------------------
1750void BiHierarchy::recQueueVisibleObjects(BiHierarchy::Node * node, unsigned long currentFrame,
1751        BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
1752        BiHierarchy::NodeList& visibleNodes, bool fullVis)
1753{
1754        BiHierarchyCamera::NodeVisibility vis = BiHierarchyCamera::BIHNV_PART;
1755        // test visibility
1756        //if (cam->isVisible(node->mAABB))
1757        if (fullVis ||
1758                ((vis = (cam->*getVisibility)(node->mAABB)) != BiHierarchyCamera::BIHNV_NONE))
1759        {
1760                visibleNodes.push_back(node);
1761
1762                bool v = (fullVis || vis == BiHierarchyCamera::BIHNV_FULL);
1763
1764                node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, v);
1765
1766                if (v || node->isLeaf())
1767                        ++ mFrameStats.mRenderedNodes;
1768
1769                if (!v)
1770                {
1771
1772                        if (node->getLeftChild())
1773                                recQueueVisibleObjects(node->getLeftChild(), currentFrame,
1774                                cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1775                        if (node->getRightChild())
1776                                recQueueVisibleObjects(node->getRightChild(), currentFrame,
1777                                cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1778                }
1779        }
1780        else
1781        {
1782                ++ mFrameStats.mFrustumCulledNodes;
1783        }
1784}
1785
1786//-------------------------------------------------------------------------
1787void BiHierarchy::setEnhancedVis(bool enh)
1788{
1789        if (enh)
1790                getVisibility = &BiHierarchyCamera::getVisibilityEnhanced;
1791        else
1792                getVisibility = &BiHierarchyCamera::getVisibilitySimple;
1793}
1794
1795//-------------------------------------------------------------------------
1796bool BiHierarchy::getEnhancedVis()
1797{
1798        return getVisibility == &BiHierarchyCamera::getVisibilityEnhanced;
1799}
1800
1801//-------------------------------------------------------------------------
1802//void BiHierarchy::findVisibleNodes(NodeList& visibleNodes, Camera * cam)
1803//{
1804//      if (mBihRoot)
1805//              recFindVisibleNodes(mBihRoot, visibleNodes, cam);
1806//}
1807
1808////-------------------------------------------------------------------------
1809//void BiHierarchy::recFindVisibleNodes(BiHierarchy::Node * node, NodeList& visibleNodes, Camera * cam)
1810//{
1811//      // test visibility
1812//      if (cam->isVisible(node->mAABB))
1813//      {
1814//              visibleNodes.push_back(node);
1815
1816//              if (node->getLeftChild())
1817//                      recFindVisibleNodes(node->getLeftChild(), visibleNodes, cam);
1818//              if (node->getRightChild())
1819//                      recFindVisibleNodes(node->getRightChild(), visibleNodes, cam);
1820//      }
1821//}
1822
1823void BiHierarchy::findNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude)
1824{
1825        if (mBihRoot)
1826                recFindNodesIn(box, list, exclude, mBihRoot);
1827}
1828
1829void BiHierarchy::findNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude)
1830{
1831        if (mBihRoot)
1832                recFindNodesIn(sphere, list, exclude, mBihRoot);
1833}
1834
1835void BiHierarchy::findNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude)
1836{
1837        if (mBihRoot)
1838                recFindNodesIn(volume, list, exclude, mBihRoot);
1839}
1840
1841void BiHierarchy::findNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude)
1842{
1843        if (mBihRoot)
1844                recFindNodesIn(ray, list, exclude, mBihRoot);
1845}
1846
1847void BiHierarchy::recFindNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1848{
1849        // check intersection
1850        if ( !full )
1851        {
1852                BihIntersection isect = intersect(box, node->_getWorldAABB());
1853
1854                if ( isect == OUTSIDE )
1855                        return ;
1856
1857                full = ( isect == INSIDE );
1858        }
1859
1860        if (node->isLeaf())
1861        {
1862                LeafPtr leaf = BIHLEAFPTR_CAST(node);
1863                for (BihRenderableList::iterator it = leaf->mBihRenderables.begin();
1864                        it != leaf->mBihRenderables.end(); it ++)
1865                {
1866                        SceneNode *sn = static_cast<BiHierarchySceneNode *>(*it);
1867
1868                        if (sn != exclude)
1869                        {
1870                                if (full)
1871                                {
1872                                        list.push_back(sn);
1873                                }
1874                                else
1875                                {
1876                                        BihIntersection nsect = intersect(box, sn->_getWorldAABB());
1877
1878                                        if ( nsect != OUTSIDE )
1879                                        {
1880                                                list.push_back(sn);
1881                                        }
1882                                }
1883                        }
1884                }
1885        }
1886        else
1887        {
1888                if (node->getLeftChild())
1889                        recFindNodesIn(box, list, exclude, node->getLeftChild(), full);
1890                if (node->getRightChild())
1891                        recFindNodesIn(box, list, exclude, node->getRightChild(), full);
1892        }
1893}
1894
1895
1896void BiHierarchy::recFindNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1897{
1898        // TODO
1899}
1900
1901
1902void BiHierarchy::recFindNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1903{
1904        // TODO
1905}
1906
1907
1908void BiHierarchy::recFindNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1909{
1910        // TODO
1911}
1912
1913
1914/************************************************************************/
1915/*              BiHierarchy debug & helper functions                    */
1916/************************************************************************/
1917
1918//-------------------------------------------------------------------------
1919void BiHierarchy::dump()
1920{
1921        //LogManager::getSingleton().logMessage("#@#@#@#@ Dumping BiHierarchy #@#@#@#@");
1922        mBuildLog->logMessage("#@#@#@#@ Dumping BiHierarchy #@#@#@#@");
1923        if (mBihRoot)
1924                dump(mBihRoot);
1925}
1926
1927//-------------------------------------------------------------------------
1928void BiHierarchy::dump(BiHierarchy::Node * node)
1929{
1930        //LogManager * log = LogManager::getSingletonPtr();
1931        BiHierarchySceneNode * scenenode;
1932        String pad;
1933        int p;
1934       
1935        pad = "";
1936        for (p = 0; p < node->getLevel(); p++)
1937        {
1938                pad += " ";
1939        }
1940
1941        if (node->isLeaf())
1942        {
1943                BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
1944                BihRenderableList::iterator it  = leaf->mBihRenderables.begin();
1945                BihRenderableList::iterator end = leaf->mBihRenderables.end();
1946                while (it != end)
1947                {
1948                        scenenode = static_cast<BiHierarchySceneNode *>(*it);
1949                        mBuildLog->logMessage(pad + "# Leaf   level " +
1950                                StringConverter::toString(node->getLevel()) +
1951                                " SceneNode " + scenenode->getName());
1952                        mBuildLog->logMessage(pad + "## Objects: " + scenenode->dumpToString());
1953                        it++;
1954                }
1955        }
1956        else
1957        {
1958                BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
1959                if (branch->mLeft)
1960                {
1961                        mBuildLog->logMessage(pad + "# Branch level " +
1962                                StringConverter::toString(node->getLevel()) + " Left Child");
1963                        dump(branch->mLeft);
1964                }
1965                if (branch->mRight)
1966                {
1967                        mBuildLog->logMessage(pad + "# Branch level " +
1968                                StringConverter::toString(node->getLevel()) + " Right Child");
1969                        dump(branch->mRight);
1970                }
1971        }
1972}
1973
1974//-------------------------------------------------------------------------
1975Real BiHierarchy::calcCost()
1976{
1977        if (mBihRoot)
1978                return calcCost(mBihRoot, BihPlaneEvent::surfaceArea(mBihRoot->mAABB));
1979        else
1980                return 0;
1981}
1982
1983//-------------------------------------------------------------------------
1984Real BiHierarchy::calcCost(BiHierarchy::Node * node, Real vs)
1985{
1986        if (node == 0)
1987                return 0.0;
1988
1989        if (node->isLeaf())
1990        {
1991                BiHierarchy::Leaf * leaf = BIHLEAFPTR_CAST(node);
1992                return (BihPlaneEvent::surfaceArea(node->mAABB)/vs) *
1993                        BihPlaneEvent::KI * leaf->mBihRenderables.size();
1994        }
1995        else
1996        {
1997                BiHierarchy::Branch * branch = BIHBRANCHPTR_CAST(node);
1998                return (BihPlaneEvent::surfaceArea(node->mAABB)/vs) * BihPlaneEvent::KT +
1999                        calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
2000        }
2001}
2002
2003/************************************************************************/
2004/* BiHierarchy::Node/Branch/Leaf functions                                   */
2005/************************************************************************/
2006
2007//-------------------------------------------------------------------------
2008BiHierarchy::Leaf::~Leaf()
2009{
2010        // detach all scene nodes in the case that we are rebuilding
2011        // the tree but not the scene
2012        BihRenderableList::iterator it = mBihRenderables.begin();
2013        BihRenderableList::iterator end = mBihRenderables.end();
2014        while (it != end)
2015        {
2016                (*it)->detachFrom(this);
2017                it++;
2018        }
2019        mBihRenderables.clear();
2020}
2021
2022//-------------------------------------------------------------------------
2023void BiHierarchy::Leaf::queueVisibleObjects(unsigned long currentFrame,
2024        Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis)
2025{
2026        BihRenderableList::iterator it  = mBihRenderables.begin();
2027        BihRenderableList::iterator end = mBihRenderables.end();
2028        while (it != end)
2029        {                       
2030                if (!(*it)->isQueued(currentFrame, cam))
2031                {
2032                        (*it)->queueObjects(cam, queue, onlyShadowCasters);
2033                }
2034                it++;
2035        }
2036
2037        if (showBoxes)
2038        {
2039        if (mLevel == mOwner->getHiLiteLevel()|| (mLevel-1) == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
2040                queue->addRenderable(getWireBoundingBox());
2041                /*
2042                if (mLevel == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
2043                        queue->addRenderable(getWireBoundingBox());
2044                */
2045        }
2046
2047}
2048
2049//-------------------------------------------------------------------------
2050void BiHierarchy::Leaf::getGeometryList(GeometryVector *geometryList)
2051{
2052        BihRenderableList::iterator it = mBihRenderables.begin();
2053        BihRenderableList::iterator end = mBihRenderables.end();
2054        while (it != end)
2055        {
2056                (*it)->getGeometryList(geometryList);
2057                it++;
2058        }
2059}
2060
2061//-------------------------------------------------------------------------
2062// update the world aabb based on the contained geometry
2063void BiHierarchy::Leaf::_updateBounds(bool recurse)
2064{
2065        // reset box
2066        mWorldAABB.setNull();
2067
2068        // merge boxes from attached geometry
2069        BihRenderableList::iterator it = mBihRenderables.begin();
2070        BihRenderableList::iterator end = mBihRenderables.end();
2071        while (it != end)
2072        {
2073                //(*it)->_updateBounds();
2074                mWorldAABB.merge((*it)->getBoundingBox());
2075                it++;
2076        }
2077
2078        // update parent recursively
2079        if (recurse && mParent)
2080                mParent->_updateBounds(recurse);
2081}
2082
2083} // namespace Ogre
Note: See TracBrowser for help on using the repository browser.