source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreBvHierarchy.cpp @ 2069

Revision 2069, 49.0 KB checked in by mattausch, 18 years ago (diff)
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 "OgreBvHierarchy.h"
11#include "OgreBvhRenderable.h"
12#include "OgreBvHierarchySceneNode.h"
13#include "OgreBvHierarchySceneManager.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 BvhIntersection
28{
29        OUTSIDE=0,
30        INSIDE=1,
31        INTERSECT=2
32};
33
34static BvhIntersection 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 BvhIntersection 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 BvhIntersection 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 BvhIntersection 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 BvhPlaneEvent::KT = 2.0;
238Real BvhPlaneEvent::KI = 1.0;
239
240//----------------------------------------------------------------------------
241// determine if this event is left or right of the reference event
242void BvhPlaneEvent::classify(const BvhPlaneEvent& e, BvhPlaneEvent::Side side)
243{
244        // only classify events of the same dimension
245        if (mDimension == e.mDimension)
246        {
247                if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
248                {
249                        mRenderable->setSide(PES_LEFT);
250                }
251                else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
252                {
253                        mRenderable->setSide(PES_RIGHT);
254                }
255                else if (mType == PET_ON)
256                {
257                        if (mPosition[mDimension] < e.mPosition[e.mDimension] ||
258                                (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
259                        {
260                                mRenderable->setSide(PES_LEFT);
261                        }
262                        if (mPosition[mDimension] > e.mPosition[e.mDimension] ||
263                                (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
264                        {
265                                mRenderable->setSide(PES_RIGHT);
266                        }
267                }
268        }
269}
270
271//----------------------------------------------------------------------------
272// clip this event to an aabb (move it so that the plane on one of the box planes)
273BvhPlaneEvent BvhPlaneEvent::clip(AxisAlignedBox& box, BvhPlaneEvent::Dimension dim)
274{
275        Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
276        if (newpos[dim] < min[dim])
277                newpos[dim] = min[dim];
278        else if (newpos[dim] > max[dim])
279                newpos[dim] = max[dim];
280
281        return BvhPlaneEvent(mRenderable, newpos, mDimension, mType);
282}
283
284//----------------------------------------------------------------------------
285// the surface area heuristic to determine the cost of splitting the parent aabb
286// along the plane represented by this event
287void BvhPlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BvhSplitInfo& split)
288{
289        Real mu = splitBox(parent, split.bleft, split.bright);
290        Real sav = surfaceArea(parent);
291        Real pl = surfaceArea(split.bleft) / sav;
292        Real pr = surfaceArea(split.bright) / sav;
293        Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
294        Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
295
296        if (costl < costr)
297        {
298                split.cost = costl;
299                split.side = PES_LEFT;
300                split.nleft = nLeft + nPlane;
301                split.nright = nRight;
302        }
303        else
304        {
305                split.cost = costr;
306                split.side = PES_RIGHT;
307                split.nleft = nLeft;
308                split.nright = nPlane + nRight;
309
310        }
311        split.event = *this;
312}
313
314//----------------------------------------------------------------------------
315// split the parent aabb with the plane in this event
316Real BvhPlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
317{
318        Vector3 bmin = parent.getMinimum();
319        Vector3 bmax = parent.getMaximum();
320        // calculate the penalty for spliting the box that way
321        Real mu = lookupPenalty(
322                (mPosition[mDimension] - bmin[mDimension]) /
323                (bmax[mDimension] - bmin[mDimension]));
324        // set corners which are the same as parent AABB
325        left.setMinimum(bmin);
326        right.setMaximum(bmax);
327        // modify "inner" corners
328        bmin[mDimension] = mPosition[mDimension];
329        bmax[mDimension] = mPosition[mDimension];
330        // set the corners on the split plane
331        left.setMaximum(bmax);
332        right.setMinimum(bmin);
333
334        return mu;
335}
336
337//----------------------------------------------------------------------------
338// compute surface area of a box ... DUH!
339Real BvhPlaneEvent::surfaceArea(const AxisAlignedBox& box)
340{
341        Vector3 sides = box.getMaximum() - box.getMinimum();
342        return  2 * sides.x * sides.y +
343                2 * sides.y * sides.z +
344                2 * sides.z * sides.x;
345}
346
347//----------------------------------------------------------------------------
348// lookup the penalty for placing the splitting plane near to the edge of the AABB
349// 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
350Real BvhPlaneEvent::lookupPenalty(Real p)
351{
352        // precomputed table of {x^6 + 1|0 <= x <= 1}
353        static Real mPenaltyLookupTable[PLT_SIZE];
354        static bool init_done = false;
355
356        if (!init_done)
357        {
358                Real step = 1.0  / (PLT_SIZE - 1);
359                Real x = 0.0;
360                //LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
361                for (int i = 0; i < PLT_SIZE; i++)
362                {
363                        mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
364                        x += step;
365                        //LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
366                }
367                init_done = true;
368                //LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
369        }
370
371        // normalize p to [0,1]
372        Real x = Math::Abs(p * 2 - 1);
373        // compute index
374        int i = Math::IFloor(x * (PLT_SIZE - 1));
375
376        return mPenaltyLookupTable[i];
377}
378
379//----------------------------------------------------------------------------
380// compute cost of the split, reward splitting of empty space (lambda, const),
381// penalize splitting off 'thin' slices (mu, const)
382Real BvhPlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
383{
384        // reward splitting off chunks of empty space
385        Real lambda = 1.0;
386        if (nLeft == 0 || nRight == 0)
387        {
388                lambda = 0.8;
389        }
390
391        // penalize splitting off small chunks (thin slices)
392        Real mu = 1.0;
393        if (pLeft < 0.1 || pRight < 0.1 || pLeft > 0.9 || pRight > 0.9)
394        {
395                mu = 1.5;
396        }
397        return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
398}
399
400//----------------------------------------------------------------------------
401// compute cost of the split, reward splitting of empty space (lambda, const),
402// penalize splitting off 'thin' slices (mu, parameter)
403Real BvhPlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
404{
405        // reward splitting off chunks of empty space
406        Real lambda = 1.0;
407        if (nLeft == 0 || nRight == 0)
408        {
409                lambda = 0.8;
410        }
411
412        return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
413}
414
415//----------------------------------------------------------------------------
416// surface area heuristic modified for the priority queue method of building
417// the probabilities (p, pl, pr) are relative to the global (all enclosing) aabb
418void BvhPlaneEvent::pqSAH(Real globalSA,
419                                                  Real parentSA,
420                                                  int nLeft,
421                                                  int nPlane,
422                                                  int nRight,
423                                                  AxisAlignedBox& parentBox,
424                                                  BvhSplitInfo& split)
425{
426        Real mu = splitBox(parentBox, split.bleft, split.bright);
427        Real p = parentSA / globalSA;
428        Real pl = surfaceArea(split.bleft) / globalSA;
429        Real pr = surfaceArea(split.bright) / globalSA;
430        Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
431        Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
432
433        if (costl < costr)
434        {
435                split.cost = costl;
436                split.side = PES_LEFT;
437                split.nleft = nLeft + nPlane;
438                split.nright = nRight;
439        }
440        else
441        {
442                split.cost = costr;
443                split.side = PES_RIGHT;
444                split.nleft = nLeft;
445                split.nright = nPlane + nRight;
446
447        }
448        split.event = *this;
449}
450
451//----------------------------------------------------------------------------
452// compute split cost without any penalties
453Real BvhPlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
454{
455        return pParent * KT + (KI * (pLeft * nLeft + pRight * nRight));
456}
457
458//----------------------------------------------------------------------------
459// DEBUG
460String BvhPlaneEvent::print()
461{
462        String dim, type;
463        if (mDimension == PED_X)
464                dim = "X";
465        if (mDimension == PED_Y)
466                dim = "Y";
467        if (mDimension == PED_Z)
468                dim = "Z";
469        if (mType == PET_END)
470                type = "END  ";
471        if (mType == PET_ON)
472                type = "ON   ";
473        if (mType == PET_START)
474                type = "START";
475        //return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
476        return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
477};
478
479//----------------------------------------------------------------------------
480String BvhSplitInfo::print()
481{
482        String sside;
483        if (side == BvhPlaneEvent::PES_BOTH)
484                sside = "BOTH ";
485        if (side == BvhPlaneEvent::PES_LEFT)
486                sside = "LEFT ";
487        if (side == BvhPlaneEvent::PES_RIGHT)
488                sside = "RIGHT";
489        return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " +
490                StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
491                " Side: " + sside + " Event: " + event.print() + " Leftbox: " +
492                StringConverter::toString(bleft.getMinimum()) + ", " +
493                StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
494                StringConverter::toString(bright.getMinimum()) + ", " +
495                StringConverter::toString(bright.getMaximum());
496};
497
498//----------------------------------------------------------------------------
499String BvHierarchy::BvhSubdivisionCandidate::print()
500{               
501        String sside;
502        if (side == BvhPlaneEvent::PES_BOTH)
503                sside = "BOTH ";
504        if (side == BvhPlaneEvent::PES_LEFT)
505                sside = "LEFT ";
506        if (side == BvhPlaneEvent::PES_RIGHT)
507                sside = "RIGHT";
508        return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
509                StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
510                " Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
511                best->print() +  " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
512                + StringConverter::toString(aabb.getMaximum());
513
514};
515
516//----------------------------------------------------------------------------
517//----------------------------------------------------------------------------
518//----------------------------------------------------------------------------
519
520BvHierarchy::BvHierarchy(int maxdepth, BuildMethod bm):
521mMaxDepth(maxdepth),
522mBuildMethod(bm),
523mHiLiteLevel(0),
524mShowAllBoxes(false),
525mShowNodes(true),
526mBvhRoot(0),
527mBuildLog(0)
528{
529        init();
530}
531
532BvHierarchy::BvHierarchy(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes):
533mMaxDepth(maxdepth),
534mBuildMethod(bm),
535mHiLiteLevel(hilite),
536mShowAllBoxes(allboxes),
537mShowNodes(shownodes),
538mBvhRoot(0),
539mBuildLog(0)
540{
541        init();
542}
543
544BvHierarchy::~BvHierarchy()
545{
546        delete mBvhRoot;
547}
548
549void BvHierarchy::init()
550{
551        MaterialPtr mat;
552        TextureUnitState *tex;
553
554        // init visualization materials (unlit solid green/yellow)
555        mat = MaterialManager::getSingleton().getByName("BvHierarchy/BoxHiLite");
556        if (mat.isNull())
557        {
558                ColourValue green(0, 1, 0);
559                mat = MaterialManager::getSingleton().create("BvHierarchy/BoxHiLite", "General");
560                //mat->setAmbient(green);
561                //mat->setDiffuse(green);
562                mat->setLightingEnabled(false);
563                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
564                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
565        }
566
567        mat = MaterialManager::getSingleton().getByName("BvHierarchy/BoxViz");
568        if (mat.isNull())
569        {
570                ColourValue yellow(1, 1, 0);
571                mat = MaterialManager::getSingleton().create("BvHierarchy/BoxViz", "General");
572                //mat->setAmbient(yellow);
573                //mat->setDiffuse(yellow);
574                mat->setLightingEnabled(false);
575                tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
576                tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, yellow, yellow);
577        }
578
579        // retrieve or create build log
580        try
581        {
582                mBuildLog = LogManager::getSingleton().getLog(BvHierarchy_LOGNAME);
583        }
584        catch (Exception&)
585        {               
586                mBuildLog = LogManager::getSingleton().createLog(BvHierarchy_LOGNAME);
587        }
588
589        setEnhancedVis(false);
590}
591
592/************************************************************************/
593/* BvHierarchy insert/delete functions                                       */
594/************************************************************************/
595
596void BvHierarchy::remove(BvhRenderable * rend)
597{
598        // DEBUG
599        //LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<BvHierarchySceneNode *>(rend))->getName());
600        std::queue<LeafPtr> cleanup;
601        LeafPtr leaf;
602        LeafSet ls = rend->getLeaves();
603        LeafSet::iterator it = ls.begin();
604        LeafSet::iterator end = ls.end();
605        while (it != end)
606        {
607                cleanup.push(*it);
608                it++;
609        }
610        while (!cleanup.empty())
611        {
612                leaf = cleanup.front();
613                cleanup.pop();
614                leaf->remove(rend);
615                bool gone = rend->detachFrom(leaf);
616                assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
617                //dump();
618                recDelete(leaf);
619                //dump();
620        }
621}
622
623void BvHierarchy::recDelete(BvHierarchy::Node * node)
624{
625        if (node == 0) // DEBUG
626        {
627                OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
628                        "SNAFU while inserting BvhRenderable into BvHierarchy.",
629                        "BvHierarchy::recInsert" );
630                return;
631        }
632
633        if (node->isEmpty())
634        {
635                if (node == mBvhRoot)
636                {
637                        OGRE_DELETE(mBvhRoot);
638                }
639                else
640                {
641                        BvHierarchy::Branch * parent = BVHBRANCHPTR_CAST(node->getParent());
642                        if (node == parent->mLeft)
643                        {
644                                OGRE_DELETE(parent->mLeft);
645                        }
646                        else if (node == parent->mRight)
647                        {
648                                OGRE_DELETE(parent->mRight);
649                        }
650                        recDelete(parent);
651                }
652        }
653}
654
655void BvHierarchy::insert(BvhRenderable * rend)
656{
657        // make sure the tree exists
658        if (mBvhRoot)
659        {
660                // make sure the renderable is inside the world bounding box
661                AxisAlignedBox aabb = rend->getBoundingBox();
662                AxisAlignedBox isect = mBvhRoot->mAABB.intersection(aabb);
663                if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
664                {
665                        recInsert(mBvhRoot, rend);
666                }
667                else
668                {
669                        //LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
670                        BvhRenderableList nodelist;
671                        nodelist.push_back(rend);
672                        addRendToList(mBvhRoot, nodelist);
673                        OGRE_DELETE(mBvhRoot);
674                        mBvhRoot = buildFromList(nodelist, 0, AxisAlignedBox());
675                }
676        }
677        // otherwise build a new one
678        else
679        {
680                build(rend);
681        }
682}
683
684void BvHierarchy::recInsert(BvHierarchy::Node * node, BvhRenderable * rend)
685{
686        if (node == 0) // DEBUG
687        {
688                OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
689                        "SNAFU while inserting BvhRenderable into BvHierarchy.",
690                        "BvHierarchy::recInsert" );
691                return;
692        }
693
694        // rebuild the leaf/replace with subtree ...
695        if (node->isLeaf())
696        {
697                //LogManager::getSingleton().logMessage("## Replacing leaf.");
698                rebuildSubtree(node, rend);
699        }
700        else
701        {
702                BvHierarchy::Branch * branch = BVHBRANCHPTR_CAST(node);
703                AxisAlignedBox aabb = rend->getBoundingBox();
704                Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
705                Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
706                if (smin == smax)
707                {
708                        if (smax == Plane::NEGATIVE_SIDE ||
709                                (smax == Plane::NO_SIDE && branch->mPlaneSide == BvhPlaneEvent::PES_LEFT))
710                        {
711                                if (branch->mLeft)
712                                        recInsert(branch->mLeft, rend);
713                                else
714                                        recInsertNew(branch, BvhPlaneEvent::PES_LEFT, rend);
715                        }
716                        else if (smin == Plane::POSITIVE_SIDE ||
717                                (smin == Plane::NO_SIDE && branch->mPlaneSide == BvhPlaneEvent::PES_RIGHT))
718                        {
719                                if (branch->mRight)
720                                        recInsert(branch->mRight, rend);
721                                else
722                                        recInsertNew(branch, BvhPlaneEvent::PES_RIGHT, rend);
723                        }
724                }
725                else
726                {
727                        if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
728                        {
729                                if (branch->mLeft)
730                                        recInsert(branch->mLeft, rend);
731                                else
732                                        recInsertNew(branch, BvhPlaneEvent::PES_LEFT, rend);
733                        }
734                        else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
735                        {
736                                if (branch->mRight)
737                                        recInsert(branch->mRight, rend);
738                                else
739                                        recInsertNew(branch, BvhPlaneEvent::PES_RIGHT, rend);
740                        }
741                        else
742                        {
743                                // to avoid SNAFUs, rebuild whole subtree
744                                //LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
745                                rebuildSubtree(node, rend);
746                        }
747                }
748        }
749}
750
751void BvHierarchy::recInsertNew(BvHierarchy::Branch * parent, BvhPlaneEvent::Side side, BvhRenderable * rend)
752{
753        //LogManager::getSingleton().logMessage("## Inserting into new subtree");
754
755        AxisAlignedBox left, rigth, aabb;
756        BvhPlaneEventList events;
757        int nObjects;
758       
759        rend->computeScene(events, aabb, nObjects, false);
760
761        // override aabb
762        splitBox(*parent, left, rigth);
763        if (side == BvhPlaneEvent::PES_LEFT)
764        {
765                aabb = left;
766                if (mBuildMethod == BVHBM_RECURSIVE)
767                        parent->mLeft = recBuild(events, nObjects, aabb, parent);
768                else if (mBuildMethod == BVHBM_PRIORITYQUEUE)
769                        parent->mLeft = pqBuild(events, nObjects, aabb, parent);
770                else
771                {
772                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
773                                "Invalid build method for the BvHierarchy.",
774                                "BvHierarchy::buildFromList");
775                        parent->mLeft = 0;
776                }
777               
778        }
779        else if (side == BvhPlaneEvent::PES_RIGHT)
780        {
781                aabb = rigth;
782                if (mBuildMethod == BVHBM_RECURSIVE)
783                        parent->mRight = recBuild(events, nObjects, aabb, parent);
784                else if (mBuildMethod == BVHBM_PRIORITYQUEUE)
785                        parent->mRight = pqBuild(events, nObjects, aabb, parent);
786                else
787                {
788                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
789                                "Invalid build method for the BvHierarchy.",
790                                "BvHierarchy::buildFromList");
791                        parent->mRight = 0;
792                }
793        }
794}
795
796void BvHierarchy::rebuildSubtree(BvHierarchy::Node * node, BvhRenderable * rend)
797{
798        //LogManager::getSingleton().logMessage("## Rebuilding subtree");
799
800        AxisAlignedBox aabb = node->mAABB;
801       
802        BvhRenderableList nodelist;
803        nodelist.push_back(rend);
804        addRendToList(node, nodelist);
805
806        if (node == mBvhRoot)
807        {
808                OGRE_DELETE(mBvhRoot);
809                mBvhRoot = buildFromList(nodelist, 0, aabb);
810        }
811        else
812        {
813                BvHierarchy::Branch * parent = BVHBRANCHPTR_CAST(node->getParent());
814
815                if (node == parent->mLeft)
816                {
817                        OGRE_DELETE(parent->mLeft);
818                        parent->mLeft = buildFromList(nodelist, parent, aabb);
819                }
820                else if (node == parent->mRight)
821                {
822                        OGRE_DELETE(parent->mRight);
823                        parent->mRight = buildFromList(nodelist, parent, aabb);
824                }
825                else
826                {
827                        OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
828                                "SNAFU while inserting BvhRenderable into BvHierarchy.",
829                                "BvHierarchy::recInsert" );
830                }
831        }
832}
833
834// compute both AABB then return the requested one.
835void BvHierarchy::splitBox(const BvHierarchy::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
836{
837        Vector3 bmin = parent.mAABB.getMinimum();
838        Vector3 bmax = parent.mAABB.getMaximum();
839        Real pos = - parent.mSplitPlane->d;
840        int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
841        // set corners which are the same as parent AABB
842        left.setMinimum(bmin);
843        right.setMaximum(bmax);
844        // modify "inner" corners
845        bmin[dim] = pos;
846        bmax[dim] = pos;
847        // set the corners on the split plane
848        left.setMaximum(bmax);
849        right.setMinimum(bmin);
850}
851
852void BvHierarchy::addRendToList(BvHierarchy::Node * node, BvhRenderableList& nodelist)
853{
854        if (node->isLeaf())
855        {
856                BvHierarchy::Leaf * leaf = BVHLEAFPTR_CAST(node);
857                BvhRenderableList::iterator it  = leaf->mBvhRenderables.begin();
858                BvhRenderableList::iterator end = leaf->mBvhRenderables.end();
859                while (it != end)
860                {
861                        nodelist.push_back(*it);
862                        it++;
863                }
864        }
865        else
866        {
867                BvHierarchy::Branch * branch = BVHBRANCHPTR_CAST(node);
868                if (branch->mLeft)
869                        addRendToList(branch->mLeft, nodelist);
870                if (branch->mRight)
871                        addRendToList(branch->mRight, nodelist);
872        }
873}
874
875/************************************************************************/
876/*                BvHierarchy build functions                           */
877/************************************************************************/
878
879void BvHierarchy::build(BvhRenderable * sceneRoot)
880{
881        Timer *timer = Root::getSingleton().getTimer();
882        unsigned long t1, t2, t3, t4;
883
884        mTreeStats.clear();
885       
886        // data we want to collect
887        BvhPlaneEventList events;
888        AxisAlignedBox aabb;
889        int nObjects = 0;
890
891        t1 = timer->getMicroseconds(); // DEBUG
892        sceneRoot->computeScene(events, aabb, nObjects);
893        t2 = timer->getMicroseconds(); // DEBUG
894        events.sort();
895        t3 = timer->getMicroseconds(); // DEBUG
896
897        mTreeStats.mNumSceneNodes = nObjects;
898
899        assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
900        // hack to avoid SNAFU with "2-dimensional" scene
901        aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
902        aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
903
904        if (mBuildMethod == BVHBM_RECURSIVE)
905                mBvhRoot = recBuild(events, nObjects, aabb, 0);
906        else if (mBuildMethod == BVHBM_PRIORITYQUEUE)
907                mBvhRoot = pqBuild(events, nObjects, aabb, 0);
908        else
909        {
910                OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
911                        "Invalid build method for the BvHierarchy.",
912                        "BvHierarchy::build");
913                mBvhRoot = 0;
914        }
915
916        t4 = timer->getMicroseconds(); // DEBUG
917
918        String method = "Invalid";
919        if (mBuildMethod == BVHBM_RECURSIVE)
920                method = "Recursive";
921        else if (mBuildMethod == BVHBM_PRIORITYQUEUE)
922                method = "Priority Queue";
923
924        mBuildLog->logMessage("######## SAH Statistics ########");
925        mBuildLog->logMessage("Build Method: " + method);
926        mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
927        mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
928        mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
929        mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
930        mBuildLog->logMessage("Tree Depth: " + StringConverter::toString(mMaxDepth));
931        mBuildLog->logMessage("Number of Objects: " + StringConverter::toString(mTreeStats.mNumSceneNodes));
932        mBuildLog->logMessage("Number of Leaves: " + StringConverter::toString(mTreeStats.mNumLeaves));
933        mBuildLog->logMessage("Number of Nodes: " + StringConverter::toString(mTreeStats.mNumNodes));
934        mBuildLog->logMessage("Total cost: " + StringConverter::toString(calcCost()));
935        mBuildLog->logMessage("################################");
936}
937
938BvHierarchy::Node * BvHierarchy::buildFromList(BvhRenderableList& nodelist, BvHierarchy::Branch * parent, AxisAlignedBox& aabb)
939{
940        // data we want to collect
941        BvhPlaneEventList events;
942        AxisAlignedBox nodeaabb;
943        int nObjects = 0;
944
945        BvhRenderableList::iterator it = nodelist.begin();
946        BvhRenderableList::iterator end = nodelist.end();
947        while (it != end)
948        {
949                (*it)->computeScene(events, nodeaabb, nObjects, false);
950                it++;
951        }
952
953        events.sort();
954       
955        // HACK
956        if (aabb.isNull())
957        {
958                aabb = nodeaabb;
959        }
960
961        if (mBuildMethod == BVHBM_RECURSIVE)
962                return recBuild(events, nObjects, aabb, parent);
963        else if (mBuildMethod == BVHBM_PRIORITYQUEUE)
964                return pqBuild(events, nObjects, aabb, parent);
965        else
966        {
967                OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
968                        "Invalid build method for the BvHierarchy.",
969                        "BvHierarchy::buildFromList");
970                return 0;
971        }
972}
973
974BvHierarchy::Node * BvHierarchy::recBuild(BvhPlaneEventList& events, int nObjects, AxisAlignedBox& aabb, BvHierarchy::Branch * parent)
975{
976        // determine the depth we are on
977        int level = 0;
978        if (parent)
979        {
980                level = parent->getLevel() + 1;
981        }
982
983        /************************************************/
984        /**************** BEGIN FINDPLANE ***************/
985        /************************************************/
986        // find optimal split plane and split node accordingly
987
988        // initialize
989        const int dim = 3;
990        int pStart, pOn, pEnd;
991        int nLeft[dim], nPlane[dim], nRight[dim];
992        for (int i = 0; i < dim; i++)
993        {
994                nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
995        }
996
997        BvhSplitInfo split, best;
998        best.cost = Math::POS_INFINITY;
999
1000        BvhPlaneEventList::iterator begin = events.begin();
1001        BvhPlaneEventList::iterator end = events.end();
1002        BvhPlaneEventList::iterator it = begin;
1003        // try all planes to find the best one for the given set of objects
1004        while (it != end)
1005        {
1006                BvhPlaneEventList::iterator p = it;
1007                pStart = pOn = pEnd = 0;
1008                while (it != end && p->equalsType(*it, BvhPlaneEvent::PET_END))
1009                {
1010                        it++; pEnd++;
1011                }
1012                while (it != end && p->equalsType(*it, BvhPlaneEvent::PET_ON))
1013                {
1014                        it++; pOn++;
1015                }
1016                while (it != end && p->equalsType(*it, BvhPlaneEvent::PET_START))
1017                {
1018                        it++; pStart++;
1019                }
1020                int d = p->getDimension();
1021                nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1022                p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split);
1023                if (split.cost < best.cost)
1024                {
1025                        best = split;
1026                }
1027                nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1028        }
1029
1030        /************************************************/
1031        /**************** BEGIN TERMINATE ***************/
1032        /************************************************/
1033        // check terminating condition
1034        if (best.cost > BvhPlaneEvent::KI*nObjects || level >= mMaxDepth)
1035        {
1036                // Terminating condition reached, create leaf and add renderables to list
1037                BvHierarchy::Leaf * leaf = new BvHierarchy::Leaf(this, level, aabb, parent);
1038                BvhRenderable *rend;
1039                it = begin;
1040                while (it != end)
1041                {
1042                        rend = it->getRenderable();
1043                        rend->setClassified(false);
1044                        if (rend->attachTo(leaf, this))
1045                        {
1046                                leaf->insert(rend);
1047                        }
1048                        it++;
1049                }
1050                // update stats
1051                ++ mTreeStats.mNumNodes;
1052                ++ mTreeStats.mNumLeaves;
1053                // update bounding box
1054                leaf->_updateBounds(false);
1055                return leaf;
1056        }
1057
1058        /************************************************/
1059        /**************** BEGIN CLASSIFY ****************/
1060        /************************************************/
1061        // split the event list in left and right sub-lists
1062        else
1063        {
1064                BvhPlaneEventList eventsRight, eventsLeft;
1065                it = begin;
1066                // slightly redundant, since we mark each renderable up to 6 times
1067                while (it != end)
1068                {
1069                        it->getRenderable()->setSide(BvhPlaneEvent::PES_BOTH);
1070                        it->getRenderable()->setClassified(false);
1071                        it++;
1072                }
1073                // now classify all renderables. do they belong to the left child, the right child or both?
1074                it = begin;
1075                while (it != end)
1076                {
1077                        it->classify(best.event, best.side);
1078                        it++;
1079                }
1080                // divide the event lists
1081                int nLeftS = 0, nRightS = 0, nBothS = 0;
1082                it = begin;
1083                while (it != end)
1084                {
1085                        // right-only nodes go in right list
1086                        if (it->getRenderable()->getSide() == BvhPlaneEvent::PES_RIGHT)
1087                        {
1088                                if (!it->getRenderable()->isClassified())
1089                                {
1090                                        it->getRenderable()->setClassified(true);
1091                                        nRightS++;
1092                                }
1093                                eventsRight.push_back(*it);
1094                        }
1095                        // left-only nodes go in left list
1096                        else if (it->getRenderable()->getSide() == BvhPlaneEvent::PES_LEFT)
1097                        {
1098                                if (!it->getRenderable()->isClassified())
1099                                {
1100                                        it->getRenderable()->setClassified(true);
1101                                        nLeftS++;
1102                                }
1103                                eventsLeft.push_back(*it);
1104                        }
1105                        // remaining nodes go in both lists, bust must be clipped to prevent
1106                        // events from lying outside the new nodes aabb
1107                        else
1108                        {
1109                                if (!it->getRenderable()->isClassified())
1110                                {
1111                                        it->getRenderable()->setClassified(true);
1112                                        nBothS++;
1113                                }
1114                                eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
1115                                eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
1116                        }
1117                        it++;
1118                }
1119
1120                // create a new branch node and continue recursion
1121                BvHierarchy::Branch * branch = new BvHierarchy::Branch(this, level, aabb, parent,
1122                        best.event.getSplitPlane(), best.side);
1123
1124                // now create the child nodes and continue recursion
1125                if (eventsLeft.size() > 0)
1126                {
1127                        branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
1128                }
1129                if (eventsRight.size() > 0)
1130                {
1131                        branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
1132                }
1133
1134                // update stats
1135                ++ mTreeStats.mNumNodes;
1136
1137                // update bounding box
1138                branch->_updateBounds(false);
1139
1140                return branch;
1141        }
1142}
1143
1144BvHierarchy::Node * BvHierarchy::pqBuild(BvhPlaneEventList& events,
1145                                                                                 int nObjects, AxisAlignedBox& aabb,
1146                                                                                 BvHierarchy::Branch * parent)
1147{
1148        SplitCandidatePQ pqueue;
1149        Real globalTreeCost;
1150        Real globalSA;
1151
1152        BvHierarchy::Node * newNode = 0, * topNode = 0;
1153        // init global tree cost
1154        globalTreeCost = BvhPlaneEvent::KI * nObjects;
1155        globalSA = BvhPlaneEvent::surfaceArea(aabb);
1156
1157        BvhPlaneEventList * e = new BvhPlaneEventList(events);
1158
1159        // inital split candidate
1160        BvhSplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
1161        BvhSubdivisionCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost,
1162                globalTreeCost - best->cost, best, BvhPlaneEvent::PES_BOTH);
1163        pqueue.push(splitcandidate);
1164
1165
1166        /*** BEGIN ITERATIVE BUILD ***/
1167        while (!pqueue.empty())
1168        {
1169                BvhSubdivisionCandidate sc = pqueue.top();
1170                pqueue.pop();
1171
1172                // determine the depth we are on
1173                int level = 0;
1174                if (sc.parent)
1175                {
1176                        level = sc.parent->getLevel() + 1;
1177                }
1178
1179                /************************************************/
1180                /**************** BEGIN TERMINATE ***************/
1181                /************************************************/
1182                // check terminating condition
1183                if (sc.decrease < 0.0 || level >= mMaxDepth)
1184                {
1185                        // Terminating condition reached, create leaf and add renderables to list
1186                        BvHierarchy::Leaf * leaf = new BvHierarchy::Leaf(this, level, sc.aabb, sc.parent);
1187                        BvhRenderable *rend;
1188                        BvhPlaneEventList::iterator begin = sc.events->begin();
1189                        BvhPlaneEventList::iterator end = sc.events->end();
1190                        BvhPlaneEventList::iterator it = begin;
1191                        while (it != end)
1192                        {
1193                                rend = it->getRenderable();
1194                                rend->setClassified(false);
1195                                if (rend->attachTo(leaf, this))
1196                                {
1197                                        leaf->insert(rend);
1198                                }
1199                                it++;
1200                        }
1201                        newNode = leaf;
1202                        if (!topNode)
1203                                topNode = leaf;
1204                        // update stats
1205                        ++ mTreeStats.mNumNodes;
1206                        ++ mTreeStats.mNumLeaves;
1207                }
1208
1209                /************************************************/
1210                /**************** BEGIN CLASSIFY ****************/
1211                /************************************************/
1212                else
1213                {
1214                        BvhPlaneEventList * eventsLeft = new BvhPlaneEventList();
1215                        BvhPlaneEventList * eventsRight = new BvhPlaneEventList();
1216                        BvhPlaneEventList::iterator begin = sc.events->begin();
1217                        BvhPlaneEventList::iterator end = sc.events->end();
1218                        BvhPlaneEventList::iterator it = begin;
1219                        // slightly redundant, since we mark each renderable up to 6 times
1220                        while (it != end)
1221                        {
1222                                it->getRenderable()->setSide(BvhPlaneEvent::PES_BOTH);
1223                                it->getRenderable()->setClassified(false);
1224                                it++;
1225                        }
1226
1227                        // now classify all renderables. do they belong to the left child, the right child or both?
1228                        it = begin;
1229                        while (it != end)
1230                        {
1231                                it->classify(sc.best->event, sc.best->side);
1232                                it++;
1233                        }
1234
1235                        // divide the event lists
1236                        int nLeftS = 0, nRightS = 0, nBothS = 0;
1237                        it = begin;
1238                        while (it != end)
1239                        {
1240                                // right-only events go in the right list
1241                                if (it->getRenderable()->getSide() == BvhPlaneEvent::PES_RIGHT)
1242                                {
1243                                        if (!it->getRenderable()->isClassified())
1244                                        {
1245                                                it->getRenderable()->setClassified(true);
1246                                                nRightS++;
1247                                        }
1248
1249                                        eventsRight->push_back(*it);
1250                                }
1251                                // left-only events go in the left list
1252                                else if (it->getRenderable()->getSide() == BvhPlaneEvent::PES_LEFT)
1253                                {
1254                                        if (!it->getRenderable()->isClassified())
1255                                        {
1256                                                it->getRenderable()->setClassified(true);
1257                                                nLeftS++;
1258                                        }
1259                                        eventsLeft->push_back(*it);
1260                                }
1261                                // the rest goes in both lists after being clipped
1262                                else
1263                                {
1264                                        if (!it->getRenderable()->isClassified())
1265                                        {
1266                                                it->getRenderable()->setClassified(true);
1267                                                nBothS++;
1268                                        }
1269
1270                                        eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
1271                                        eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
1272                                }
1273                                it++;
1274                        }
1275
1276                        // create a new branch node
1277                        BvHierarchy::Branch * branch = new BvHierarchy::Branch(this, level, sc.aabb, sc.parent,
1278                                sc.best->event.getSplitPlane(), sc.best->side);
1279
1280                        globalTreeCost -= sc.decrease;
1281
1282
1283                        // now for each potential child node, compute the split plane and the cost decrease
1284                        // and place them in the queue
1285                        if (eventsLeft->size() > 0)
1286                        {
1287                                best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
1288                                Real old = BvhPlaneEvent::surfaceArea(sc.best->bleft)/globalSA*BvhPlaneEvent::KI*(nLeftS + nBothS);
1289                                BvhSubdivisionCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
1290                                        branch, old, old - best->cost, best, BvhPlaneEvent::PES_LEFT);
1291                                pqueue.push(scleft);
1292                        }
1293                        // cleanup
1294                        else
1295                        {
1296                                delete eventsLeft;
1297                        }
1298
1299                        if (eventsRight->size() > 0)
1300                        {
1301                                best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
1302                                Real old = BvhPlaneEvent::surfaceArea(sc.best->bright)/globalSA*BvhPlaneEvent::KI*(nBothS + nRightS);
1303                                BvhSubdivisionCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
1304                                        branch, old, old - best->cost, best, BvhPlaneEvent::PES_RIGHT);
1305                                pqueue.push(scright);
1306                        }
1307                        // cleanup
1308                        else
1309                        {
1310                                delete eventsRight;
1311                        }
1312
1313                        newNode = branch;
1314                        if (!topNode)
1315                                topNode = branch;
1316
1317
1318                        // update stats
1319                        ++ mTreeStats.mNumNodes;
1320                }
1321
1322                // attach new node to parent
1323                if (sc.parent)
1324                {
1325                        if (sc.side == BvhPlaneEvent::PES_LEFT)
1326                        {
1327                                sc.parent->mLeft = newNode;
1328                        }
1329                        else if (sc.side == BvhPlaneEvent::PES_RIGHT)
1330                        {
1331                                sc.parent->mRight = newNode;
1332                        }
1333                        else
1334                        {
1335                                OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
1336                                        "PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","BvHierarchy::pqBuild");
1337                        }
1338                }
1339
1340                // update bounding boxes when geometry (leaf) was added
1341                if (newNode->isLeaf())
1342                        newNode->_updateBounds();
1343
1344                //cleanup
1345                OGRE_DELETE(sc.events);
1346                OGRE_DELETE(sc.best);
1347        }
1348        mBuildLog->logMessage("Cost after PQBUILD €" + StringConverter::toString(globalTreeCost));
1349        return topNode;
1350}
1351
1352//-------------------------------------------------------------------------
1353BvhSplitInfo * BvHierarchy::pqFindPlane(BvhPlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
1354{
1355        static const int dim = 3;
1356        int pStart, pOn, pEnd;
1357        int nLeft[dim], nPlane[dim], nRight[dim];
1358        for (int i = 0; i < dim; i++)
1359        {
1360                nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1361        }
1362
1363        BvhSplitInfo split, best;
1364        best.cost = Math::POS_INFINITY;
1365
1366        Real parentSA = BvhPlaneEvent::surfaceArea(aabb);
1367
1368        BvhPlaneEventList::iterator begin = events->begin();
1369        BvhPlaneEventList::iterator end = events->end();
1370        BvhPlaneEventList::iterator it = begin;
1371        // try all planes to find the best one for the given set of objects
1372        while (it != end)
1373        {
1374                BvhPlaneEventList::iterator p = it;
1375                pStart = pOn = pEnd = 0;
1376                while (it != end && p->equalsType(*it, BvhPlaneEvent::PET_END))
1377                {
1378                        it++; pEnd++;
1379                }
1380                while (it != end && p->equalsType(*it, BvhPlaneEvent::PET_ON))
1381                {
1382                        it++; pOn++;
1383                }
1384                while (it != end && p->equalsType(*it, BvhPlaneEvent::PET_START))
1385                {
1386                        it++; pStart++;
1387                }
1388                int d = p->getDimension();
1389                nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1390                p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
1391                if (split.cost < best.cost)
1392                {
1393                        best = split;
1394                }
1395                nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1396        }
1397        return new BvhSplitInfo(best);
1398}
1399
1400
1401
1402/************************************************************************/
1403/*               BvHierarchy rendering functions                        */
1404/************************************************************************/
1405
1406
1407//-------------------------------------------------------------------------
1408void BvHierarchy::queueVisibleObjects(BvHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
1409        bool showBoxes, BvHierarchy::NodeList& visibleNodes)
1410{
1411        mFrameStats.clear();
1412        cam->mNumVisQueries = 0;
1413
1414        if (mBvhRoot)
1415                recQueueVisibleObjects(mBvhRoot, Root::getSingleton().getCurrentFrameNumber(),
1416                        cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1417
1418        mFrameStats.mTraversedNodes = cam->mNumVisQueries;
1419}
1420
1421//-------------------------------------------------------------------------
1422void BvHierarchy::recQueueVisibleObjects(BvHierarchy::Node * node, unsigned long currentFrame,
1423        BvHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
1424        BvHierarchy::NodeList& visibleNodes, bool fullVis)
1425{
1426        BvHierarchyCamera::NodeVisibility vis = BvHierarchyCamera::BVHNV_PART;
1427        // test visibility
1428        //if (cam->isVisible(node->mAABB))
1429        if (fullVis ||
1430                ((vis = (cam->*getVisibility)(node->mAABB)) != BvHierarchyCamera::BVHNV_NONE))
1431        {
1432                visibleNodes.push_back(node);
1433
1434                bool v = (fullVis || vis == BvHierarchyCamera::BVHNV_FULL);
1435
1436                node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, v);
1437
1438                if (v || node->isLeaf())
1439                        ++ mFrameStats.mRenderedNodes;
1440
1441                if (!v)
1442                {
1443
1444                        if (node->getLeftChild())
1445                                recQueueVisibleObjects(node->getLeftChild(), currentFrame,
1446                                cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1447                        if (node->getRightChild())
1448                                recQueueVisibleObjects(node->getRightChild(), currentFrame,
1449                                cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1450                }
1451        }
1452        else
1453        {
1454                ++ mFrameStats.mFrustumCulledNodes;
1455        }
1456}
1457
1458//-------------------------------------------------------------------------
1459void BvHierarchy::setEnhancedVis(bool enh)
1460{
1461        if (enh)
1462                getVisibility = &BvHierarchyCamera::getVisibilityEnhanced;
1463        else
1464                getVisibility = &BvHierarchyCamera::getVisibilitySimple;
1465}
1466
1467//-------------------------------------------------------------------------
1468bool BvHierarchy::getEnhancedVis()
1469{
1470        return getVisibility == &BvHierarchyCamera::getVisibilityEnhanced;
1471}
1472
1473//-------------------------------------------------------------------------
1474//void BvHierarchy::findVisibleNodes(NodeList& visibleNodes, Camera * cam)
1475//{
1476//      if (mBvhRoot)
1477//              recFindVisibleNodes(mBvhRoot, visibleNodes, cam);
1478//}
1479
1480////-------------------------------------------------------------------------
1481//void BvHierarchy::recFindVisibleNodes(BvHierarchy::Node * node, NodeList& visibleNodes, Camera * cam)
1482//{
1483//      // test visibility
1484//      if (cam->isVisible(node->mAABB))
1485//      {
1486//              visibleNodes.push_back(node);
1487
1488//              if (node->getLeftChild())
1489//                      recFindVisibleNodes(node->getLeftChild(), visibleNodes, cam);
1490//              if (node->getRightChild())
1491//                      recFindVisibleNodes(node->getRightChild(), visibleNodes, cam);
1492//      }
1493//}
1494
1495void BvHierarchy::findNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude)
1496{
1497        if (mBvhRoot)
1498                recFindNodesIn(box, list, exclude, mBvhRoot);
1499}
1500
1501void BvHierarchy::findNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude)
1502{
1503        if (mBvhRoot)
1504                recFindNodesIn(sphere, list, exclude, mBvhRoot);
1505}
1506
1507void BvHierarchy::findNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude)
1508{
1509        if (mBvhRoot)
1510                recFindNodesIn(volume, list, exclude, mBvhRoot);
1511}
1512
1513void BvHierarchy::findNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude)
1514{
1515        if (mBvhRoot)
1516                recFindNodesIn(ray, list, exclude, mBvhRoot);
1517}
1518
1519void BvHierarchy::recFindNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1520{
1521        // check intersection
1522        if ( !full )
1523        {
1524                BvhIntersection isect = intersect(box, node->_getWorldAABB());
1525
1526                if ( isect == OUTSIDE )
1527                        return ;
1528
1529                full = ( isect == INSIDE );
1530        }
1531
1532        if (node->isLeaf())
1533        {
1534                LeafPtr leaf = BVHLEAFPTR_CAST(node);
1535                for (BvhRenderableList::iterator it = leaf->mBvhRenderables.begin();
1536                        it != leaf->mBvhRenderables.end(); it ++)
1537                {
1538                        SceneNode *sn = static_cast<BvHierarchySceneNode *>(*it);
1539
1540                        if (sn != exclude)
1541                        {
1542                                if (full)
1543                                {
1544                                        list.push_back(sn);
1545                                }
1546                                else
1547                                {
1548                                        BvhIntersection nsect = intersect(box, sn->_getWorldAABB());
1549
1550                                        if ( nsect != OUTSIDE )
1551                                        {
1552                                                list.push_back(sn);
1553                                        }
1554                                }
1555                        }
1556                }
1557        }
1558        else
1559        {
1560                if (node->getLeftChild())
1561                        recFindNodesIn(box, list, exclude, node->getLeftChild(), full);
1562                if (node->getRightChild())
1563                        recFindNodesIn(box, list, exclude, node->getRightChild(), full);
1564        }
1565}
1566
1567
1568void BvHierarchy::recFindNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1569{
1570        // TODO
1571}
1572
1573
1574void BvHierarchy::recFindNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1575{
1576        // TODO
1577}
1578
1579
1580void BvHierarchy::recFindNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full)
1581{
1582        // TODO
1583}
1584
1585
1586/************************************************************************/
1587/*              BvHierarchy debug & helper functions                    */
1588/************************************************************************/
1589
1590//-------------------------------------------------------------------------
1591void BvHierarchy::dump()
1592{
1593        //LogManager::getSingleton().logMessage("#@#@#@#@ Dumping BvHierarchy #@#@#@#@");
1594        mBuildLog->logMessage("#@#@#@#@ Dumping BvHierarchy #@#@#@#@");
1595        if (mBvhRoot)
1596                dump(mBvhRoot);
1597}
1598
1599//-------------------------------------------------------------------------
1600void BvHierarchy::dump(BvHierarchy::Node * node)
1601{
1602        //LogManager * log = LogManager::getSingletonPtr();
1603        BvHierarchySceneNode * scenenode;
1604        String pad;
1605        int p;
1606       
1607        pad = "";
1608        for (p = 0; p < node->getLevel(); p++)
1609        {
1610                pad += " ";
1611        }
1612
1613        if (node->isLeaf())
1614        {
1615                BvHierarchy::Leaf * leaf = BVHLEAFPTR_CAST(node);
1616                BvhRenderableList::iterator it  = leaf->mBvhRenderables.begin();
1617                BvhRenderableList::iterator end = leaf->mBvhRenderables.end();
1618                while (it != end)
1619                {
1620                        scenenode = static_cast<BvHierarchySceneNode *>(*it);
1621                        mBuildLog->logMessage(pad + "# Leaf   level " +
1622                                StringConverter::toString(node->getLevel()) +
1623                                " SceneNode " + scenenode->getName());
1624                        mBuildLog->logMessage(pad + "## Objects: " + scenenode->dumpToString());
1625                        it++;
1626                }
1627        }
1628        else
1629        {
1630                BvHierarchy::Branch * branch = BVHBRANCHPTR_CAST(node);
1631                if (branch->mLeft)
1632                {
1633                        mBuildLog->logMessage(pad + "# Branch level " +
1634                                StringConverter::toString(node->getLevel()) + " Left Child");
1635                        dump(branch->mLeft);
1636                }
1637                if (branch->mRight)
1638                {
1639                        mBuildLog->logMessage(pad + "# Branch level " +
1640                                StringConverter::toString(node->getLevel()) + " Right Child");
1641                        dump(branch->mRight);
1642                }
1643        }
1644}
1645
1646//-------------------------------------------------------------------------
1647Real BvHierarchy::calcCost()
1648{
1649        if (mBvhRoot)
1650                return calcCost(mBvhRoot, BvhPlaneEvent::surfaceArea(mBvhRoot->mAABB));
1651        else
1652                return 0;
1653}
1654
1655//-------------------------------------------------------------------------
1656Real BvHierarchy::calcCost(BvHierarchy::Node * node, Real vs)
1657{
1658        if (node == 0)
1659                return 0.0;
1660
1661        if (node->isLeaf())
1662        {
1663                BvHierarchy::Leaf * leaf = BVHLEAFPTR_CAST(node);
1664                return (BvhPlaneEvent::surfaceArea(node->mAABB)/vs) *
1665                        BvhPlaneEvent::KI * leaf->mBvhRenderables.size();
1666        }
1667        else
1668        {
1669                BvHierarchy::Branch * branch = BVHBRANCHPTR_CAST(node);
1670                return (BvhPlaneEvent::surfaceArea(node->mAABB)/vs) * BvhPlaneEvent::KT +
1671                        calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
1672        }
1673}
1674
1675/************************************************************************/
1676/* BvHierarchy::Node/Branch/Leaf functions                                   */
1677/************************************************************************/
1678
1679//-------------------------------------------------------------------------
1680BvHierarchy::Leaf::~Leaf()
1681{
1682        // detach all scene nodes in the case that we are rebuilding
1683        // the tree but not the scene
1684        BvhRenderableList::iterator it = mBvhRenderables.begin();
1685        BvhRenderableList::iterator end = mBvhRenderables.end();
1686        while (it != end)
1687        {
1688                (*it)->detachFrom(this);
1689                it++;
1690        }
1691        mBvhRenderables.clear();
1692}
1693
1694//-------------------------------------------------------------------------
1695void BvHierarchy::Leaf::queueVisibleObjects(unsigned long currentFrame,
1696        Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis)
1697{
1698        BvhRenderableList::iterator it  = mBvhRenderables.begin();
1699        BvhRenderableList::iterator end = mBvhRenderables.end();
1700        while (it != end)
1701        {                       
1702                if (!(*it)->isQueued(currentFrame, cam))
1703                {
1704                        (*it)->queueObjects(cam, queue, onlyShadowCasters);
1705                }
1706                it++;
1707        }
1708
1709        if (showBoxes)
1710                if (mLevel == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
1711                        queue->addRenderable(getWireBoundingBox());
1712}
1713
1714//-------------------------------------------------------------------------
1715void BvHierarchy::Leaf::getGeometryList(GtpVisibility::GeometryVector *geometryList)
1716{
1717        BvhRenderableList::iterator it = mBvhRenderables.begin();
1718        BvhRenderableList::iterator end = mBvhRenderables.end();
1719        while (it != end)
1720        {
1721                (*it)->getGeometryList(geometryList);
1722                it++;
1723        }
1724}
1725
1726//-------------------------------------------------------------------------
1727// update the world aabb based on the contained geometry
1728void BvHierarchy::Leaf::_updateBounds(bool recurse)
1729{
1730        // reset box
1731        mWorldAABB.setNull();
1732
1733        // merge boxes from attached geometry
1734        BvhRenderableList::iterator it = mBvhRenderables.begin();
1735        BvhRenderableList::iterator end = mBvhRenderables.end();
1736        while (it != end)
1737        {
1738                //(*it)->_updateBounds();
1739                mWorldAABB.merge((*it)->getBoundingBox());
1740                it++;
1741        }
1742
1743        // update parent recursively
1744        if (recurse && mParent)
1745                mParent->_updateBounds(recurse);
1746}
1747
1748} // namespace Ogre
Note: See TracBrowser for help on using the repository browser.