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

Revision 1250, 42.7 KB checked in by szydlowski, 18 years ago (diff)

implemented enhanced vis with early abort
also own frame & time counter in demo mode
fixed dependencies in solution file

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        Real PlaneEvent::KT = 2.0;
27        Real PlaneEvent::KI = 1.0;
28
29        //----------------------------------------------------------------------------
30        // determine if this event is left or right of the reference event
31        void PlaneEvent::classify(const PlaneEvent& e, PlaneEvent::Side side)
32        {
33                // only classify events of the same dimension
34                if (mDimension == e.mDimension)
35                {
36                        if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
37                        {
38                                mRenderable->setSide(PES_LEFT);
39                        }
40                        else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
41                        {
42                                mRenderable->setSide(PES_RIGHT);
43                        }
44                        else if (mType == PET_ON)
45                        {
46                                if (mPosition[mDimension] < e.mPosition[e.mDimension] ||
47                                        (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
48                                {
49                                        mRenderable->setSide(PES_LEFT);
50                                }
51                                if (mPosition[mDimension] > e.mPosition[e.mDimension] ||
52                                        (mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
53                                {
54                                        mRenderable->setSide(PES_RIGHT);
55                                }
56                        }
57                }
58        }
59
60        //----------------------------------------------------------------------------
61        // clip this event to an aabb (move it so that the plane on one of the box planes)
62        PlaneEvent PlaneEvent::clip(AxisAlignedBox& box, PlaneEvent::Dimension dim)
63        {
64                Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
65                if (newpos[dim] < min[dim])
66                        newpos[dim] = min[dim];
67                else if (newpos[dim] > max[dim])
68                        newpos[dim] = max[dim];
69
70                return PlaneEvent(mRenderable, newpos, mDimension, mType);
71        }
72
73        //----------------------------------------------------------------------------
74        // the surface area heuristic to determine the cost of splitting the parent aabb
75        // along the plane represented by this event
76        void PlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split)
77        {
78                Real mu = splitBox(parent, split.bleft, split.bright);
79                Real sav = surfaceArea(parent);
80                Real pl = surfaceArea(split.bleft) / sav;
81                Real pr = surfaceArea(split.bright) / sav;
82                Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
83                Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
84
85                if (costl < costr)
86                {
87                        split.cost = costl;
88                        split.side = PES_LEFT;
89                        split.nleft = nLeft + nPlane;
90                        split.nright = nRight;
91                }
92                else
93                {
94                        split.cost = costr;
95                        split.side = PES_RIGHT;
96                        split.nleft = nLeft;
97                        split.nright = nPlane + nRight;
98
99                }
100                split.event = *this;
101        }
102
103        //----------------------------------------------------------------------------
104        // split the parent aabb with the plane in this event
105        Real PlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
106        {
107                Vector3 bmin = parent.getMinimum();
108                Vector3 bmax = parent.getMaximum();
109                // calculate the penalty for spliting the box that way
110                Real mu = lookupPenalty(
111                        (mPosition[mDimension] - bmin[mDimension]) /
112                        (bmax[mDimension] - bmin[mDimension]));
113                // set corners which are the same as parent AABB
114                left.setMinimum(bmin);
115                right.setMaximum(bmax);
116                // modify "inner" corners
117                bmin[mDimension] = mPosition[mDimension];
118                bmax[mDimension] = mPosition[mDimension];
119                // set the corners on the split plane
120                left.setMaximum(bmax);
121                right.setMinimum(bmin);
122
123                return mu;
124        }
125
126        //----------------------------------------------------------------------------
127        // compute surface area of a box ... DUH!
128        Real PlaneEvent::surfaceArea(const AxisAlignedBox& box)
129        {
130                Vector3 sides = box.getMaximum() - box.getMinimum();
131                return  2 * sides.x * sides.y +
132                        2 * sides.y * sides.z +
133                        2 * sides.z * sides.x;
134        }
135
136        //----------------------------------------------------------------------------
137        // lookup the penalty for placing the splitting plane near to the edge of the AABB
138        // 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
139        Real PlaneEvent::lookupPenalty(Real p)
140        {
141                // precomputed table of {x^6 + 1|0 <= x <= 1}
142                static Real mPenaltyLookupTable[PLT_SIZE];
143                static bool init_done = false;
144
145                if (!init_done)
146                {
147                        Real step = 1.0  / (PLT_SIZE - 1);
148                        Real x = 0.0;
149                        //LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
150                        for (int i = 0; i < PLT_SIZE; i++)
151                        {
152                                mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
153                                x += step;
154                                //LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
155                        }
156                        init_done = true;
157                        //LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
158                }
159
160                // normalize p to [0,1]
161                Real x = Math::Abs(p * 2 - 1);
162                // compute index
163                int i = Math::IFloor(x * (PLT_SIZE - 1));
164
165                return mPenaltyLookupTable[i];
166        }
167
168        //----------------------------------------------------------------------------
169        // compute cost of the split, reward splitting of empty space (lambda, const),
170        // penalize splitting off 'thin' slices (mu, const)
171        Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
172        {
173                // reward splitting off chunks of empty space
174                Real lambda = 1.0;
175                if (nLeft == 0 || nRight == 0)
176                {
177                        lambda = 0.8;
178                }
179
180                // penalize splitting off small chunks (thin slices)
181                Real mu = 1.0;
182                if (pLeft < 0.1 || pRight < 0.1 || pLeft > 0.9 || pRight > 0.9)
183                {
184                        mu = 1.5;
185                }
186                return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
187        }
188
189        //----------------------------------------------------------------------------
190        // compute cost of the split, reward splitting of empty space (lambda, const),
191        // penalize splitting off 'thin' slices (mu, parameter)
192        Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
193        {
194                // reward splitting off chunks of empty space
195                Real lambda = 1.0;
196                if (nLeft == 0 || nRight == 0)
197                {
198                        lambda = 0.8;
199                }
200
201                return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
202        }
203
204        //----------------------------------------------------------------------------
205        // surface area heuristic modified for the priority queue method of building
206        // the probabilities (p, pl, pr) are relative to the global (all enclosing) aabb
207        void PlaneEvent::pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight,
208                AxisAlignedBox& parentBox, SplitInfo& split)
209        {
210                Real mu = splitBox(parentBox, split.bleft, split.bright);
211                Real p = parentSA / globalSA;
212                Real pl = surfaceArea(split.bleft) / globalSA;
213                Real pr = surfaceArea(split.bright) / globalSA;
214                Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
215                Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
216
217                if (costl < costr)
218                {
219                        split.cost = costl;
220                        split.side = PES_LEFT;
221                        split.nleft = nLeft + nPlane;
222                        split.nright = nRight;
223                }
224                else
225                {
226                        split.cost = costr;
227                        split.side = PES_RIGHT;
228                        split.nleft = nLeft;
229                        split.nright = nPlane + nRight;
230
231                }
232                split.event = *this;
233        }
234
235        //----------------------------------------------------------------------------
236        // compute split cost without any penalties
237        Real PlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
238        {
239                return pParent * KT + (KI * (pLeft * nLeft + pRight * nRight));
240        }
241
242        //----------------------------------------------------------------------------
243        // DEBUG
244        String PlaneEvent::print()
245        {
246                String dim, type;
247                if (mDimension == PED_X)
248                        dim = "X";
249                if (mDimension == PED_Y)
250                        dim = "Y";
251                if (mDimension == PED_Z)
252                        dim = "Z";
253                if (mType == PET_END)
254                        type = "END  ";
255                if (mType == PET_ON)
256                        type = "ON   ";
257                if (mType == PET_START)
258                        type = "START";
259                //return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
260                return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
261        };
262
263        //----------------------------------------------------------------------------
264        String SplitInfo::print()
265        {
266                String sside;
267                if (side == PlaneEvent::PES_BOTH)
268                        sside = "BOTH ";
269                if (side == PlaneEvent::PES_LEFT)
270                        sside = "LEFT ";
271                if (side == PlaneEvent::PES_RIGHT)
272                        sside = "RIGHT";
273                return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " +
274                        StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
275                        " Side: " + sside + " Event: " + event.print() + " Leftbox: " +
276                        StringConverter::toString(bleft.getMinimum()) + ", " +
277                        StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
278                        StringConverter::toString(bright.getMinimum()) + ", " +
279                        StringConverter::toString(bright.getMaximum());
280        };
281
282        //----------------------------------------------------------------------------
283        String KdTree::SplitCandidate::print()
284        {               
285                String sside;
286                if (side == PlaneEvent::PES_BOTH)
287                        sside = "BOTH ";
288                if (side == PlaneEvent::PES_LEFT)
289                        sside = "LEFT ";
290                if (side == PlaneEvent::PES_RIGHT)
291                        sside = "RIGHT";
292                return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
293                        StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
294                        " Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
295                        best->print() +  " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
296                        + StringConverter::toString(aabb.getMaximum());
297
298        };
299
300        //----------------------------------------------------------------------------
301        //----------------------------------------------------------------------------
302        //----------------------------------------------------------------------------
303
304        KdTree::KdTree(int maxdepth, BuildMethod bm):
305        mMaxDepth(maxdepth),
306        mBuildMethod(bm),
307        mHiLiteLevel(0),
308        mShowAllBoxes(false),
309        mShowNodes(true),
310        mKdRoot(0),
311        mBuildLog(0)
312        {
313                init();
314        }
315
316        KdTree::KdTree(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes):
317        mMaxDepth(maxdepth),
318        mBuildMethod(bm),
319        mHiLiteLevel(hilite),
320        mShowAllBoxes(allboxes),
321        mShowNodes(shownodes),
322        mKdRoot(0),
323        mBuildLog(0)
324        {
325                init();
326        }
327
328        KdTree::~KdTree()
329        {
330                delete mKdRoot;
331        }
332
333        void KdTree::init()
334        {
335                MaterialPtr mat;
336                TextureUnitState *tex;
337
338                // init visualization materials (unlit solid green/yellow)
339                mat = MaterialManager::getSingleton().getByName("KdTree/BoxHiLite");
340                if (mat.isNull())
341                {
342                        ColourValue green(0, 1, 0);
343                        mat = MaterialManager::getSingleton().create("KdTree/BoxHiLite", "General");
344                        //mat->setAmbient(green);
345                        //mat->setDiffuse(green);
346                        mat->setLightingEnabled(false);
347                        tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
348                        tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, green, green);
349                }
350
351                mat = MaterialManager::getSingleton().getByName("KdTree/BoxViz");
352                if (mat.isNull())
353                {
354                        ColourValue yellow(1, 1, 0);
355                        mat = MaterialManager::getSingleton().create("KdTree/BoxViz", "General");
356                        //mat->setAmbient(yellow);
357                        //mat->setDiffuse(yellow);
358                        mat->setLightingEnabled(false);
359                        tex = mat->getTechnique(0)->getPass(0)->createTextureUnitState();
360                        tex->setColourOperationEx(LBX_SOURCE2, LBS_CURRENT, LBS_MANUAL, yellow, yellow);
361                }
362
363                // retrieve or create build log
364                try
365                {
366                        mBuildLog = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
367                }
368                catch (Exception&)
369                {               
370                        mBuildLog = LogManager::getSingleton().createLog(KDTREE_LOGNAME);
371                }
372
373                setEnhancedVis(false);
374        }
375
376        /************************************************************************/
377        /* KdTree insert/delete functions                                       */
378        /************************************************************************/
379
380        void KdTree::remove(KdRenderable * rend)
381        {
382                // DEBUG
383                //LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
384                std::queue<LeafPtr> cleanup;
385                LeafPtr leaf;
386                LeafSet ls = rend->getLeaves();
387                LeafSet::iterator it = ls.begin();
388                LeafSet::iterator end = ls.end();
389                while (it != end)
390                {
391                        cleanup.push(*it);
392                        it++;
393                }
394                while (!cleanup.empty())
395                {
396                        leaf = cleanup.front();
397                        cleanup.pop();
398                        leaf->remove(rend);
399                        bool gone = rend->detachFrom(leaf);
400                        assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
401                        //dump();
402                        recDelete(leaf);
403                        //dump();
404                }
405        }
406
407        void KdTree::recDelete(KdTree::Node * node)
408        {
409                if (node == 0) // DEBUG
410                {
411                        OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
412                                "SNAFU while inserting KdRenderable into KdTree.",
413                                "KdTree::recInsert" );
414                        return;
415                }
416
417                if (node->isEmpty())
418                {
419                        if (node == mKdRoot)
420                        {
421                                OGRE_DELETE(mKdRoot);
422                        }
423                        else
424                        {
425                                KdTree::Branch * parent = KDBRANCHPTR_CAST(node->getParent());
426                                if (node == parent->mLeft)
427                                {
428                                        OGRE_DELETE(parent->mLeft);
429                                }
430                                else if (node == parent->mRight)
431                                {
432                                        OGRE_DELETE(parent->mRight);
433                                }
434                                recDelete(parent);
435                        }
436                }
437        }
438
439        void KdTree::insert(KdRenderable * rend)
440        {
441                // make sure the tree exists
442                if (mKdRoot)
443                {
444                        // make sure the renderable is inside the world bounding box
445                        AxisAlignedBox aabb = rend->getBoundingBox();
446                        AxisAlignedBox isect = mKdRoot->mAABB.intersection(aabb);
447                        if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
448                        {
449                                recInsert(mKdRoot, rend);
450                        }
451                        else
452                        {
453                                //LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
454                                KdRenderableList nodelist;
455                                nodelist.push_back(rend);
456                                addRendToList(mKdRoot, nodelist);
457                                OGRE_DELETE(mKdRoot);
458                                mKdRoot = buildFromList(nodelist, 0, AxisAlignedBox());
459                        }
460                }
461                // otherwise build a new one
462                else
463                {
464                        build(rend);
465                }
466        }
467
468        void KdTree::recInsert(KdTree::Node * node, KdRenderable * rend)
469        {
470                if (node == 0) // DEBUG
471                {
472                        OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
473                                "SNAFU while inserting KdRenderable into KdTree.",
474                                "KdTree::recInsert" );
475                        return;
476                }
477
478                // rebuild the leaf/replace with subtree ...
479                if (node->isLeaf())
480                {
481                        //LogManager::getSingleton().logMessage("## Replacing leaf.");
482                        rebuildSubtree(node, rend);
483                }
484                else
485                {
486                        KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
487                        AxisAlignedBox aabb = rend->getBoundingBox();
488                        Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
489                        Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
490                        if (smin == smax)
491                        {
492                                if (smax == Plane::NEGATIVE_SIDE ||
493                                        (smax == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_LEFT))
494                                {
495                                        if (branch->mLeft)
496                                                recInsert(branch->mLeft, rend);
497                                        else
498                                                recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
499                                }
500                                else if (smin == Plane::POSITIVE_SIDE ||
501                                        (smin == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_RIGHT))
502                                {
503                                        if (branch->mRight)
504                                                recInsert(branch->mRight, rend);
505                                        else
506                                                recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
507                                }
508                        }
509                        else
510                        {
511                                if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
512                                {
513                                        if (branch->mLeft)
514                                                recInsert(branch->mLeft, rend);
515                                        else
516                                                recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
517                                }
518                                else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
519                                {
520                                        if (branch->mRight)
521                                                recInsert(branch->mRight, rend);
522                                        else
523                                                recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
524                                }
525                                else
526                                {
527                                        // to avoid SNAFUs, rebuild whole subtree
528                                        //LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
529                                        rebuildSubtree(node, rend);
530                                }
531                        }
532                }
533        }
534
535        void KdTree::recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend)
536        {
537                //LogManager::getSingleton().logMessage("## Inserting into new subtree");
538
539                AxisAlignedBox left, rigth, aabb;
540                PlaneEventList events;
541                int nObjects;
542               
543                rend->computeScene(events, aabb, nObjects, false);
544
545                // override aabb
546                splitBox(*parent, left, rigth);
547                if (side == PlaneEvent::PES_LEFT)
548                {
549                        aabb = left;
550                        if (mBuildMethod == KDBM_RECURSIVE)
551                                parent->mLeft = recBuild(events, nObjects, aabb, parent);
552                        else if (mBuildMethod == KDBM_PRIORITYQUEUE)
553                                parent->mLeft = pqBuild(events, nObjects, aabb, parent);
554                        else
555                        {
556                                OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
557                                        "Invalid build method for the KdTree.",
558                                        "KdTree::buildFromList");
559                                parent->mLeft = 0;
560                        }
561                       
562                }
563                else if (side == PlaneEvent::PES_RIGHT)
564                {
565                        aabb = rigth;
566                        if (mBuildMethod == KDBM_RECURSIVE)
567                                parent->mRight = recBuild(events, nObjects, aabb, parent);
568                        else if (mBuildMethod == KDBM_PRIORITYQUEUE)
569                                parent->mRight = pqBuild(events, nObjects, aabb, parent);
570                        else
571                        {
572                                OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
573                                        "Invalid build method for the KdTree.",
574                                        "KdTree::buildFromList");
575                                parent->mRight = 0;
576                        }
577                }
578        }
579
580        void KdTree::rebuildSubtree(KdTree::Node * node, KdRenderable * rend)
581        {
582                //LogManager::getSingleton().logMessage("## Rebuilding subtree");
583
584                AxisAlignedBox aabb = node->mAABB;
585               
586                KdRenderableList nodelist;
587                nodelist.push_back(rend);
588                addRendToList(node, nodelist);
589
590                if (node == mKdRoot)
591                {
592                        OGRE_DELETE(mKdRoot);
593                        mKdRoot = buildFromList(nodelist, 0, aabb);
594                }
595                else
596                {
597                        KdTree::Branch * parent = KDBRANCHPTR_CAST(node->getParent());
598
599                        if (node == parent->mLeft)
600                        {
601                                OGRE_DELETE(parent->mLeft);
602                                parent->mLeft = buildFromList(nodelist, parent, aabb);
603                        }
604                        else if (node == parent->mRight)
605                        {
606                                OGRE_DELETE(parent->mRight);
607                                parent->mRight = buildFromList(nodelist, parent, aabb);
608                        }
609                        else
610                        {
611                                OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
612                                        "SNAFU while inserting KdRenderable into KdTree.",
613                                        "KdTree::recInsert" );
614                        }
615                }
616        }
617
618        // compute both AABB then return the requested one.
619        void KdTree::splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
620        {
621                Vector3 bmin = parent.mAABB.getMinimum();
622                Vector3 bmax = parent.mAABB.getMaximum();
623                Real pos = - parent.mSplitPlane->d;
624                int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
625                // set corners which are the same as parent AABB
626                left.setMinimum(bmin);
627                right.setMaximum(bmax);
628                // modify "inner" corners
629                bmin[dim] = pos;
630                bmax[dim] = pos;
631                // set the corners on the split plane
632                left.setMaximum(bmax);
633                right.setMinimum(bmin);
634        }
635
636        void KdTree::addRendToList(KdTree::Node * node, KdRenderableList& nodelist)
637        {
638                if (node->isLeaf())
639                {
640                        KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
641                        KdRenderableList::iterator it  = leaf->mKdRenderables.begin();
642                        KdRenderableList::iterator end = leaf->mKdRenderables.end();
643                        while (it != end)
644                        {
645                                nodelist.push_back(*it);
646                                it++;
647                        }
648                }
649                else
650                {
651                        KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
652                        if (branch->mLeft)
653                                addRendToList(branch->mLeft, nodelist);
654                        if (branch->mRight)
655                                addRendToList(branch->mRight, nodelist);
656                }
657        }
658
659        /************************************************************************/
660        /* KdTree build functions                                               */
661        /************************************************************************/
662
663        void KdTree::build(KdRenderable * sceneRoot)
664        {
665                Timer *timer = Root::getSingleton().getTimer();
666                unsigned long t1, t2, t3, t4;
667
668                mStats.clear();
669               
670                // data we want to collect
671                PlaneEventList events;
672                AxisAlignedBox aabb;
673                int nObjects = 0;
674
675                t1 = timer->getMicroseconds(); // DEBUG
676                sceneRoot->computeScene(events, aabb, nObjects);
677                t2 = timer->getMicroseconds(); // DEBUG
678                events.sort();
679                t3 = timer->getMicroseconds(); // DEBUG
680
681                mStats.mNumSceneNodes = nObjects;
682
683                assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
684                // hack to avoid SNAFU with "2-dimensional" scene
685                aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
686                aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
687
688                if (mBuildMethod == KDBM_RECURSIVE)
689                        mKdRoot = recBuild(events, nObjects, aabb, 0);
690                else if (mBuildMethod == KDBM_PRIORITYQUEUE)
691                        mKdRoot = pqBuild(events, nObjects, aabb, 0);
692                else
693                {
694                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
695                                "Invalid build method for the KdTree.",
696                                "KdTree::build");
697                        mKdRoot = 0;
698                }
699
700                t4 = timer->getMicroseconds(); // DEBUG
701
702                String method = "Invalid";
703                if (mBuildMethod == KDBM_RECURSIVE)
704                        method = "Recursive";
705                else if (mBuildMethod == KDBM_PRIORITYQUEUE)
706                        method = "Priority Queue";
707
708                mBuildLog->logMessage("######## SAH Statistics ########");
709                mBuildLog->logMessage("Build Method: " + method);
710                mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
711                mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
712                mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
713                mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
714                mBuildLog->logMessage("Tree Depth: " + StringConverter::toString(mMaxDepth));
715                mBuildLog->logMessage("Number of Objects: " + StringConverter::toString(mStats.mNumSceneNodes));
716                mBuildLog->logMessage("Number of Leaves: " + StringConverter::toString(mStats.mNumLeaves));
717                mBuildLog->logMessage("Number of Nodes: " + StringConverter::toString(mStats.mNumNodes));
718                mBuildLog->logMessage("Total cost: " + StringConverter::toString(calcCost()));
719                mBuildLog->logMessage("################################");
720        }
721
722        KdTree::Node * KdTree::buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb)
723        {
724                // data we want to collect
725                PlaneEventList events;
726                AxisAlignedBox nodeaabb;
727                int nObjects = 0;
728
729                KdRenderableList::iterator it = nodelist.begin();
730                KdRenderableList::iterator end = nodelist.end();
731                while (it != end)
732                {
733                        (*it)->computeScene(events, nodeaabb, nObjects, false);
734                        it++;
735                }
736
737                events.sort();
738               
739                // HACK
740                if (aabb.isNull())
741                {
742                        aabb = nodeaabb;
743                }
744
745                if (mBuildMethod == KDBM_RECURSIVE)
746                        return recBuild(events, nObjects, aabb, parent);
747                else if (mBuildMethod == KDBM_PRIORITYQUEUE)
748                        return pqBuild(events, nObjects, aabb, parent);
749                else
750                {
751                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
752                                "Invalid build method for the KdTree.",
753                                "KdTree::buildFromList");
754                        return 0;
755                }
756        }
757
758        KdTree::Node * KdTree::recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
759        {
760                // determine the depth we are on
761                int level = 0;
762                if (parent)
763                {
764                        level = parent->getLevel() + 1;
765                }
766
767                /************************************************/
768                /**************** BEGIN FINDPLANE ***************/
769                /************************************************/
770                // find optimal split plane and split node accordingly
771
772                // initialize
773                const int dim = 3;
774                int pStart, pOn, pEnd;
775                int nLeft[dim], nPlane[dim], nRight[dim];
776                for (int i = 0; i < dim; i++)
777                {
778                        nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
779                }
780
781                SplitInfo split, best;
782                best.cost = Math::POS_INFINITY;
783
784                PlaneEventList::iterator begin = events.begin();
785                PlaneEventList::iterator end = events.end();
786                PlaneEventList::iterator it = begin;
787                // try all planes to find the best one for the given set of objects
788                while (it != end)
789                {
790                        PlaneEventList::iterator p = it;
791                        pStart = pOn = pEnd = 0;
792                        while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
793                        {
794                                it++; pEnd++;
795                        }
796                        while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
797                        {
798                                it++; pOn++;
799                        }
800                        while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
801                        {
802                                it++; pStart++;
803                        }
804                        int d = p->getDimension();
805                        nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
806                        p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split);
807                        if (split.cost < best.cost)
808                        {
809                                best = split;
810                        }
811                        nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
812                }
813
814                /************************************************/
815                /**************** BEGIN TERMINATE ***************/
816                /************************************************/
817                // check terminating condition
818                if (best.cost > PlaneEvent::KI*nObjects || level >= mMaxDepth)
819                {
820                        // Terminating condition reached, create leaf and add renderables to list
821                        KdTree::Leaf * leaf = new KdTree::Leaf(this, level, aabb, parent);
822                        KdRenderable *rend;
823                        it = begin;
824                        while (it != end)
825                        {
826                                rend = it->getRenderable();
827                                rend->setClassified(false);
828                                if (rend->attachTo(leaf, this))
829                                {
830                                        leaf->insert(rend);
831                                }
832                                it++;
833                        }
834                        // update stats
835                        ++ mStats.mNumNodes;
836                        ++ mStats.mNumLeaves;
837                        // update bounding box
838                        leaf->_updateBounds(false);
839                        return leaf;
840                }
841
842                /************************************************/
843                /**************** BEGIN CLASSIFY ****************/
844                /************************************************/
845                // split the event list in left and right sub-lists
846                else
847                {
848                        PlaneEventList eventsRight, eventsLeft;
849                        it = begin;
850                        // slightly redundant, since we mark each renderable up to 6 times
851                        while (it != end)
852                        {
853                                it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
854                                it->getRenderable()->setClassified(false);
855                                it++;
856                        }
857                        // now classify all renderables. do they belong to the left child, the right child or both?
858                        it = begin;
859                        while (it != end)
860                        {
861                                it->classify(best.event, best.side);
862                                it++;
863                        }
864                        // divide the event lists
865                        int nLeftS = 0, nRightS = 0, nBothS = 0;
866                        it = begin;
867                        while (it != end)
868                        {
869                                // right-only nodes go in right list
870                                if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
871                                {
872                                        if (!it->getRenderable()->isClassified())
873                                        {
874                                                it->getRenderable()->setClassified(true);
875                                                nRightS++;
876                                        }
877                                        eventsRight.push_back(*it);
878                                }
879                                // left-only nodes go in left list
880                                else if (it->getRenderable()->getSide() == PlaneEvent::PES_LEFT)
881                                {
882                                        if (!it->getRenderable()->isClassified())
883                                        {
884                                                it->getRenderable()->setClassified(true);
885                                                nLeftS++;
886                                        }
887                                        eventsLeft.push_back(*it);
888                                }
889                                // remaining nodes go in both lists, bust must be clipped to prevent
890                                // events from lying outside the new nodes aabb
891                                else
892                                {
893                                        if (!it->getRenderable()->isClassified())
894                                        {
895                                                it->getRenderable()->setClassified(true);
896                                                nBothS++;
897                                        }
898                                        eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
899                                        eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
900                                }
901                                it++;
902                        }
903
904                        // create a new branch node and continue recursion
905                        KdTree::Branch * branch = new KdTree::Branch(this, level, aabb, parent,
906                                best.event.getSplitPlane(), best.side);
907
908                        // now create the child nodes and continue recursion
909                        if (eventsLeft.size() > 0)
910                        {
911                                branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
912                        }
913                        if (eventsRight.size() > 0)
914                        {
915                                branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
916                        }
917
918                        // update stats
919                        ++ mStats.mNumNodes;
920
921                        // update bounding box
922                        branch->_updateBounds(false);
923
924                        return branch;
925                }
926        }
927
928        KdTree::Node * KdTree::pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
929        {
930                SplitCandidatePQ pqueue;
931                Real globalTreeCost;
932                Real globalSA;
933
934                KdTree::Node * newNode = 0, * topNode = 0;
935                // init global tree cost
936                globalTreeCost = PlaneEvent::KI * nObjects;
937                globalSA = PlaneEvent::surfaceArea(aabb);
938
939                PlaneEventList * e = new PlaneEventList(events);
940
941                // inital split candidate
942                SplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
943                SplitCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost,
944                        globalTreeCost - best->cost, best, PlaneEvent::PES_BOTH);
945                pqueue.push(splitcandidate);
946
947
948                /*** BEGIN ITERATIVE BUILD ***/
949                while (!pqueue.empty())
950                {
951                        SplitCandidate sc = pqueue.top();
952                        pqueue.pop();
953
954                        // determine the depth we are on
955                        int level = 0;
956                        if (sc.parent)
957                        {
958                                level = sc.parent->getLevel() + 1;
959                        }
960
961                        /************************************************/
962                        /**************** BEGIN TERMINATE ***************/
963                        /************************************************/
964                        // check terminating condition
965                        if (sc.decrease < 0.0 || level >= mMaxDepth)
966                        {
967                                // Terminating condition reached, create leaf and add renderables to list
968                                KdTree::Leaf * leaf = new KdTree::Leaf(this, level, sc.aabb, sc.parent);
969                                KdRenderable *rend;
970                                PlaneEventList::iterator begin = sc.events->begin();
971                                PlaneEventList::iterator end = sc.events->end();
972                                PlaneEventList::iterator it = begin;
973                                while (it != end)
974                                {
975                                        rend = it->getRenderable();
976                                        rend->setClassified(false);
977                                        if (rend->attachTo(leaf, this))
978                                        {
979                                                leaf->insert(rend);
980                                        }
981                                        it++;
982                                }
983                                newNode = leaf;
984                                if (!topNode)
985                                        topNode = leaf;
986                                // update stats
987                                ++ mStats.mNumNodes;
988                                ++ mStats.mNumLeaves;
989                        }
990
991                        /************************************************/
992                        /**************** BEGIN CLASSIFY ****************/
993                        /************************************************/
994                        else
995                        {
996                                PlaneEventList * eventsLeft = new PlaneEventList();
997                                PlaneEventList * eventsRight = new PlaneEventList();
998                                PlaneEventList::iterator begin = sc.events->begin();
999                                PlaneEventList::iterator end = sc.events->end();
1000                                PlaneEventList::iterator it = begin;
1001                                // slightly redundant, since we mark each renderable up to 6 times
1002                                while (it != end)
1003                                {
1004                                        it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
1005                                        it->getRenderable()->setClassified(false);
1006                                        it++;
1007                                }
1008
1009                                // now classify all renderables. do they belong to the left child, the right child or both?
1010                                it = begin;
1011                                while (it != end)
1012                                {
1013                                        it->classify(sc.best->event, sc.best->side);
1014                                        it++;
1015                                }
1016
1017                                // divide the event lists
1018                                int nLeftS = 0, nRightS = 0, nBothS = 0;
1019                                it = begin;
1020                                while (it != end)
1021                                {
1022                                        // right-only events go in the right list
1023                                        if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
1024                                        {
1025                                                if (!it->getRenderable()->isClassified())
1026                                                {
1027                                                        it->getRenderable()->setClassified(true);
1028                                                        nRightS++;
1029                                                }
1030
1031                                                eventsRight->push_back(*it);
1032                                        }
1033                                        // left-only events go in the left list
1034                                        else if (it->getRenderable()->getSide() == PlaneEvent::PES_LEFT)
1035                                        {
1036                                                if (!it->getRenderable()->isClassified())
1037                                                {
1038                                                        it->getRenderable()->setClassified(true);
1039                                                        nLeftS++;
1040                                                }
1041                                                eventsLeft->push_back(*it);
1042                                        }
1043                                        // the rest goes in both lists after being clipped
1044                                        else
1045                                        {
1046                                                if (!it->getRenderable()->isClassified())
1047                                                {
1048                                                        it->getRenderable()->setClassified(true);
1049                                                        nBothS++;
1050                                                }
1051
1052                                                eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
1053                                                eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
1054                                        }
1055                                        it++;
1056                                }
1057
1058                                // create a new branch node
1059                                KdTree::Branch * branch = new KdTree::Branch(this, level, sc.aabb, sc.parent,
1060                                        sc.best->event.getSplitPlane(), sc.best->side);
1061
1062                                globalTreeCost -= sc.decrease;
1063
1064
1065                                // now for each potential child node, compute the split plane and the cost decrease
1066                                // and place them in the queue
1067                                if (eventsLeft->size() > 0)
1068                                {
1069                                        best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
1070                                        Real old = PlaneEvent::surfaceArea(sc.best->bleft)/globalSA*PlaneEvent::KI*(nLeftS + nBothS);
1071                                        SplitCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft,
1072                                                branch, old, old - best->cost, best, PlaneEvent::PES_LEFT);
1073                                        pqueue.push(scleft);
1074                                }
1075                                // cleanup
1076                                else
1077                                {
1078                                        delete eventsLeft;
1079                                }
1080
1081                                if (eventsRight->size() > 0)
1082                                {
1083                                        best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
1084                                        Real old = PlaneEvent::surfaceArea(sc.best->bright)/globalSA*PlaneEvent::KI*(nBothS + nRightS);
1085                                        SplitCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright,
1086                                                branch, old, old - best->cost, best, PlaneEvent::PES_RIGHT);
1087                                        pqueue.push(scright);
1088                                }
1089                                // cleanup
1090                                else
1091                                {
1092                                        delete eventsRight;
1093                                }
1094
1095                                newNode = branch;
1096                                if (!topNode)
1097                                        topNode = branch;
1098
1099
1100                                // update stats
1101                                ++ mStats.mNumNodes;
1102                        }
1103
1104                        // attach new node to parent
1105                        if (sc.parent)
1106                        {
1107                                if (sc.side == PlaneEvent::PES_LEFT)
1108                                {
1109                                        sc.parent->mLeft = newNode;
1110                                }
1111                                else if (sc.side == PlaneEvent::PES_RIGHT)
1112                                {
1113                                        sc.parent->mRight = newNode;
1114                                }
1115                                else
1116                                {
1117                                        OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
1118                                                "PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","KdTree::pqBuild");
1119                                }
1120                        }
1121
1122                        // update bounding boxes when geometry (leaf) was added
1123                        if (newNode->isLeaf())
1124                                newNode->_updateBounds();
1125
1126                        //cleanup
1127                        OGRE_DELETE(sc.events);
1128                        OGRE_DELETE(sc.best);
1129                }
1130                mBuildLog->logMessage("Cost after PQBUILD €" + StringConverter::toString(globalTreeCost));
1131                return topNode;
1132        }
1133
1134        //-------------------------------------------------------------------------
1135        SplitInfo * KdTree::pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
1136        {
1137                static const int dim = 3;
1138                int pStart, pOn, pEnd;
1139                int nLeft[dim], nPlane[dim], nRight[dim];
1140                for (int i = 0; i < dim; i++)
1141                {
1142                        nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
1143                }
1144
1145                SplitInfo split, best;
1146                best.cost = Math::POS_INFINITY;
1147
1148                Real parentSA = PlaneEvent::surfaceArea(aabb);
1149
1150                PlaneEventList::iterator begin = events->begin();
1151                PlaneEventList::iterator end = events->end();
1152                PlaneEventList::iterator it = begin;
1153                // try all planes to find the best one for the given set of objects
1154                while (it != end)
1155                {
1156                        PlaneEventList::iterator p = it;
1157                        pStart = pOn = pEnd = 0;
1158                        while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
1159                        {
1160                                it++; pEnd++;
1161                        }
1162                        while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
1163                        {
1164                                it++; pOn++;
1165                        }
1166                        while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
1167                        {
1168                                it++; pStart++;
1169                        }
1170                        int d = p->getDimension();
1171                        nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
1172                        p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
1173                        if (split.cost < best.cost)
1174                        {
1175                                best = split;
1176                        }
1177                        nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
1178                }
1179                return new SplitInfo(best);
1180        }
1181
1182        /************************************************************************/
1183        /* KdTree rendering functions                                           */
1184        /************************************************************************/
1185
1186        //-------------------------------------------------------------------------
1187        void KdTree::queueVisibleObjects(KdTreeCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
1188                bool showBoxes, KdTree::NodeList& visibleNodes)
1189        {
1190                // debug
1191                //cam->mNumVisQueries = 0;
1192
1193                if (mKdRoot)
1194                        recQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(),
1195                                cam, queue, onlyShadowCasters, showBoxes, visibleNodes);
1196
1197                //mBuildLog->logMessage("Frame # " + StringConverter::toString(Root::getSingleton().getCurrentFrameNumber()) +
1198                //      " ," + StringConverter::toString(cam->mNumVisQueries) + " vis queries");
1199        }
1200
1201        //-------------------------------------------------------------------------
1202        void KdTree::recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame,
1203                KdTreeCamera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
1204                KdTree::NodeList& visibleNodes, bool fullVis)
1205        {
1206                KdTreeCamera::NodeVisibility vis = KdTreeCamera::KDNV_PART;
1207                // test visibility
1208                //if (cam->isVisible(node->mAABB))
1209                if (fullVis ||
1210                        ((vis = (cam->*getVisibility)(node->mAABB)) != KdTreeCamera::KDNV_NONE))
1211                        //((vis = (cam->*getVisibility)(node->mAABB)) != KdTreeCamera::KDNV_NONE))
1212                {
1213                        visibleNodes.push_back(node);
1214
1215                        bool v = (fullVis || vis == KdTreeCamera::KDNV_FULL);
1216                        node->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, v);
1217
1218                        if (!v)
1219                        {
1220
1221                                if (node->getLeftChild())
1222                                        recQueueVisibleObjects(node->getLeftChild(), currentFrame,
1223                                        cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1224                                if (node->getRightChild())
1225                                        recQueueVisibleObjects(node->getRightChild(), currentFrame,
1226                                        cam, queue, onlyShadowCasters, showBoxes, visibleNodes, v);
1227                        }
1228                }
1229        }
1230
1231        //-------------------------------------------------------------------------
1232        void KdTree::setEnhancedVis(bool enh)
1233        {
1234                if (enh)
1235                        getVisibility = &KdTreeCamera::getVisibilityEnhanced;
1236                else
1237                        getVisibility = &KdTreeCamera::getVisibilitySimple;
1238        }
1239
1240        //-------------------------------------------------------------------------
1241        bool KdTree::getEnhancedVis()
1242        {
1243                return getVisibility == &KdTreeCamera::getVisibilityEnhanced;
1244        }
1245
1246        //-------------------------------------------------------------------------
1247        //void KdTree::findVisibleNodes(NodeList& visibleNodes, Camera * cam)
1248        //{
1249        //      if (mKdRoot)
1250        //              recFindVisibleNodes(mKdRoot, visibleNodes, cam);
1251        //}
1252
1253        ////-------------------------------------------------------------------------
1254        //void KdTree::recFindVisibleNodes(KdTree::Node * node, NodeList& visibleNodes, Camera * cam)
1255        //{
1256        //      // test visibility
1257        //      if (cam->isVisible(node->mAABB))
1258        //      {
1259        //              visibleNodes.push_back(node);
1260
1261        //              if (node->getLeftChild())
1262        //                      recFindVisibleNodes(node->getLeftChild(), visibleNodes, cam);
1263        //              if (node->getRightChild())
1264        //                      recFindVisibleNodes(node->getRightChild(), visibleNodes, cam);
1265        //      }
1266        //}
1267
1268        /************************************************************************/
1269        /* KdTree debug & helper functions                                      */
1270        /************************************************************************/
1271
1272        //-------------------------------------------------------------------------
1273        void KdTree::dump()
1274        {
1275                LogManager::getSingleton().logMessage("#@#@#@#@ Dumping KdTree #@#@#@#@");
1276                if (mKdRoot)
1277                        dump(mKdRoot);
1278        }
1279
1280        //-------------------------------------------------------------------------
1281        void KdTree::dump(KdTree::Node * node)
1282        {
1283                LogManager * log = LogManager::getSingletonPtr();
1284                KdTreeSceneNode * scenenode;
1285                String pad;
1286                int p;
1287               
1288                pad = "";
1289                for (p = 0; p < node->getLevel(); p++)
1290                {
1291                        pad += " ";
1292                }
1293
1294                if (node->isLeaf())
1295                {
1296                        KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1297                        KdRenderableList::iterator it  = leaf->mKdRenderables.begin();
1298                        KdRenderableList::iterator end = leaf->mKdRenderables.end();
1299                        while (it != end)
1300                        {
1301                                scenenode = dynamic_cast<KdTreeSceneNode *>(*it);
1302                                log->logMessage(pad + "# Leaf   level " +
1303                                        StringConverter::toString(node->getLevel()) +
1304                                        " SceneNode " + scenenode->getName());
1305                                log->logMessage(pad + "## Objects: " + scenenode->dumpToString());
1306                                it++;
1307                        }
1308                }
1309                else
1310                {
1311                        KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1312                        if (branch->mLeft)
1313                        {
1314                                log->logMessage(pad + "# Branch level " +
1315                                        StringConverter::toString(node->getLevel()) + " Left Child");
1316                                dump(branch->mLeft);
1317                        }
1318                        if (branch->mRight)
1319                        {
1320                                log->logMessage(pad + "# Branch level " +
1321                                        StringConverter::toString(node->getLevel()) + " Right Child");
1322                                dump(branch->mRight);
1323                        }
1324                }
1325        }
1326
1327        //-------------------------------------------------------------------------
1328        Real KdTree::calcCost()
1329        {
1330                if (mKdRoot)
1331                        return calcCost(mKdRoot, PlaneEvent::surfaceArea(mKdRoot->mAABB));
1332                else
1333                        return 0;
1334        }
1335
1336        //-------------------------------------------------------------------------
1337        Real KdTree::calcCost(KdTree::Node * node, Real vs)
1338        {
1339                if (node == 0)
1340                        return 0.0;
1341
1342                if (node->isLeaf())
1343                {
1344                        KdTree::Leaf * leaf = KDLEAFPTR_CAST(node);
1345                        return (PlaneEvent::surfaceArea(node->mAABB)/vs) *
1346                                PlaneEvent::KI * leaf->mKdRenderables.size();
1347                }
1348                else
1349                {
1350                        KdTree::Branch * branch = KDBRANCHPTR_CAST(node);
1351                        return (PlaneEvent::surfaceArea(node->mAABB)/vs) * PlaneEvent::KT +
1352                                calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
1353                }
1354        }
1355
1356        /************************************************************************/
1357        /* KdTree::Node/Branch/Leaf functions                                   */
1358        /************************************************************************/
1359
1360        //-------------------------------------------------------------------------
1361        KdTree::Leaf::~Leaf()
1362        {
1363                // detach all scene nodes in the case that we are rebuilding
1364                // the tree but not the scene
1365                KdRenderableList::iterator it = mKdRenderables.begin();
1366                KdRenderableList::iterator end = mKdRenderables.end();
1367                while (it != end)
1368                {
1369                        (*it)->detachFrom(this);
1370                        it++;
1371                }
1372                mKdRenderables.clear();
1373        }
1374
1375        //-------------------------------------------------------------------------
1376        void KdTree::Leaf::queueVisibleObjects(unsigned long currentFrame,
1377                Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis)
1378        {
1379                KdRenderableList::iterator it  = mKdRenderables.begin();
1380                KdRenderableList::iterator end = mKdRenderables.end();
1381                while (it != end)
1382                {                       
1383                        if (!(*it)->isQueued(currentFrame, cam))
1384                        {
1385                                (*it)->queueObjects(cam, queue, onlyShadowCasters);
1386                        }
1387                        it++;
1388                }
1389
1390                if (showBoxes)
1391                        if (mLevel == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
1392                                queue->addRenderable(getWireBoundingBox());
1393        }
1394
1395        //-------------------------------------------------------------------------
1396        void KdTree::Leaf::getGeometryList(GtpVisibility::GeometryVector *geometryList)
1397        {
1398                KdRenderableList::iterator it = mKdRenderables.begin();
1399                KdRenderableList::iterator end = mKdRenderables.end();
1400                while (it != end)
1401                {
1402                        (*it)->getGeometryList(geometryList);
1403                        it++;
1404                }
1405        }
1406
1407        //-------------------------------------------------------------------------
1408        // update the world aabb based on the contained geometry
1409        void KdTree::Leaf::_updateBounds(bool recurse)
1410        {
1411                // reset box
1412                mWorldAABB.setNull();
1413
1414                // merge boxes from attached geometry
1415                KdRenderableList::iterator it = mKdRenderables.begin();
1416                KdRenderableList::iterator end = mKdRenderables.end();
1417                while (it != end)
1418                {
1419                        //(*it)->_updateBounds();
1420                        mWorldAABB.merge((*it)->getBoundingBox());
1421                        it++;
1422                }
1423
1424                // update parent recursively
1425                if (recurse && mParent)
1426                        mParent->_updateBounds(recurse);
1427        }
1428} // namespace Ogre
Note: See TracBrowser for help on using the repository browser.