source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTree.cpp @ 2280

Revision 2280, 47.9 KB checked in by mattausch, 18 years ago (diff)

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