source: GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.cpp @ 2544

Revision 2544, 18.1 KB checked in by mattausch, 17 years ago (diff)
RevLine 
[2073]1#include <stack>
2#include <algorithm>
3#include <queue>
4#include "Environment.h"
5#include "Mesh.h"
6#include "TraversalTree.h"
7#include "ViewCell.h"
8#include "Beam.h"
[2124]9#include "Exporter.h"
[2073]10
11
[2176]12using namespace std;
13
[2073]14// $$JB HACK
15#define KD_PVS_AREA (1e-5f)
16
17namespace GtpVisibilityPreprocessor {
18
19int TraversalNode::sMailId = 1;
20int TraversalNode::sReservedMailboxes = 1;
21
22
23inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
24{
25        return obj1->mId < obj2->mId;
26}
27
28
[2093]29TraversalNode::TraversalNode(TraversalInterior *parent):
30mParent(parent), mMailbox(0)
31{
32}
[2073]33
[2093]34
35TraversalInterior::TraversalInterior(TraversalInterior *parent):
36TraversalNode(parent), mBack(NULL), mFront(NULL)
[2073]37{
38}
39
40
41TraversalInterior::~TraversalInterior()
42{
43        // recursivly destroy children
44        DEL_PTR(mFront);
45        DEL_PTR(mBack);
46}
47
48
[2093]49bool TraversalInterior::IsLeaf() const
50{
51        return false;
52}
53
54
55void TraversalInterior::SetupChildLinks(TraversalNode *b, TraversalNode *f)
56{
57        mBack = b;
58        mFront = f;
59       
60        b->mParent = f->mParent = this;
61}
62
63
[2124]64void TraversalInterior::ReplaceChildLink(TraversalNode *oldChild,
65                                                                                 TraversalNode *newChild)
[2093]66{
67        if (mBack == oldChild)
68                mBack = newChild;
69        else
70                mFront = newChild;
71}
72
73
74TraversalLeaf::TraversalLeaf(TraversalInterior *parent, const int objects):
75TraversalNode(parent)
76{
[2124]77        mViewCells.reserve(objects);
[2093]78}
79
80
81bool TraversalLeaf::IsLeaf() const
82{
83        return true;
84}
85
86
[2073]87TraversalLeaf::~TraversalLeaf()
88{
89}
90
91
92TraversalTree::TraversalTree()
[2093]93{
[2124]94        TraversalLeaf *leaf = new TraversalLeaf(NULL, 0);
95        leaf->mDepth = 0;
96        mRoot = leaf;
[2073]97
[2093]98        Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxNodes", mTermMaxNodes);
99        Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxDepth", mTermMaxDepth);
100        Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.minCost", mTermMinCost);
101        Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.maxCostRatio", mMaxCostRatio);
102        Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.ct_div_ci", mCt_div_ci);
103        Environment::GetSingleton()->GetFloatValue("TraversalTree.splitBorder", mSplitBorder);
[2073]104
[2093]105        Environment::GetSingleton()->GetBoolValue("TraversalTree.sahUseFaces", mSahUseFaces);
[2073]106
[2093]107        char splitType[64];
108        Environment::GetSingleton()->GetStringValue("TraversalTree.splitMethod", splitType);
109
[2124]110        splitCandidates = NULL;
[2093]111        mSplitMethod = SPLIT_SPATIAL_MEDIAN;
[2124]112
[2093]113        if (strcmp(splitType, "spatialMedian") == 0)
114        {
115                mSplitMethod = SPLIT_SPATIAL_MEDIAN;
116        }
117        else
118        {
119                if (strcmp(splitType, "objectMedian") == 0)
120                {
121                        mSplitMethod = SPLIT_OBJECT_MEDIAN;
122                }
123                else
124                {
125                        if (strcmp(splitType, "SAH") == 0)
126                        {
127                                mSplitMethod = SPLIT_SAH;
128                        }
129                        else
130                        {
[2124]131                                cerr << "Wrong kd split type " << splitType << endl;
[2093]132                                exit(1);
133                        }
134                }
135        }
[2124]136        cout << "Traversal Tree Split method: " << mSplitMethod << endl;
[2073]137}
138
139
140TraversalTree::~TraversalTree()
141{
142    DEL_PTR(mRoot);
143}
144
145
[2124]146bool TraversalTree::Construct(const ViewCellContainer &viewCells)
[2073]147{
[2093]148        if (!splitCandidates)
149        {
150                splitCandidates = new vector<SortableEntry *>;
151        }
[2073]152
[2093]153        // first construct a leaf that will get subdivide
154        TraversalLeaf *leaf = static_cast<TraversalLeaf *>(mRoot);
[2073]155
[2124]156        leaf->mViewCells = viewCells;
[2093]157        mStat.nodes = 1;
158        mBox.Initialize();
[2094]159
[2124]160        ViewCellContainer::const_iterator mi;
161
162        for ( mi = leaf->mViewCells.begin(); mi != leaf->mViewCells.end(); ++ mi)
[2093]163        {
164                mBox.Include((*mi)->GetBox());
165        }
[2073]166
[2093]167        cout << "TraversalTree Root Box:" << mBox << endl;
168        mRoot = Subdivide(TraversalData(leaf, mBox, 0));
169       
170        // remove the allocated array
[2124]171        if (splitCandidates)
172        {
173                CLEAR_CONTAINER(*splitCandidates);
174                delete splitCandidates;
175        }
176       
[2093]177        return true;
178}
[2073]179
180
[2093]181TraversalNode *TraversalTree::Subdivide(const TraversalData &tdata)
[2073]182{
[2093]183        TraversalNode *result = NULL;
[2073]184
[2093]185        //priority_queue<TraversalData> tStack;
186        stack<TraversalData> tStack;
[2073]187
[2093]188        tStack.push(tdata);
189        AxisAlignedBox3 backBox, frontBox;
[2073]190
[2093]191        while (!tStack.empty())
192        {
193                if (mStat.Nodes() > mTermMaxNodes)
194                {
195                        while (!tStack.empty())
196                        {
197                                EvaluateLeafStats(tStack.top());
198                                tStack.pop();
199                        }
200                        break;
201                }
202
203                TraversalData data = tStack.top();
[2073]204                tStack.pop();
205
[2093]206                TraversalLeaf *tLeaf = static_cast<TraversalLeaf *> (data.mNode);
207                TraversalNode *node = SubdivideNode(tLeaf,
208                                                                                        data.mBox,
209                                                                                        backBox,
210                                                                                        frontBox);
[2073]211
[2093]212                if (result == NULL)
213                        result = node;
[2073]214
[2093]215                if (!node->IsLeaf())
216                {
217                        TraversalInterior *interior = static_cast<TraversalInterior *>(node);
218
219                        // push the children on the stack
220                        tStack.push(TraversalData(interior->mBack, backBox, data.mDepth + 1));
221                        tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth + 1));
222
223                }
224                else
225                {
226                        EvaluateLeafStats(data);
227                }
228        }
229
230        return result;
[2073]231}
232
233
[2093]234bool TraversalTree::TerminationCriteriaMet(const TraversalLeaf *leaf)
[2073]235{
[2124]236        const bool criteriaMet = (
237                ((int)leaf->mViewCells.size() <= mTermMinCost) ||
238                 (leaf->mDepth >= mTermMaxDepth)
239                 || (GetBox(leaf).SurfaceArea() < 0.00001f)
240                 );
[2093]241
[2073]242        if (criteriaMet)
[2124]243        {
244                cerr << "\nOBJECTS=" << (int)leaf->mViewCells.size() << endl;
245                cerr << "\nDEPTH=" << (int)leaf->mDepth << endl;
246        }
[2073]247
248        return criteriaMet;
249}
250
251
[2093]252int TraversalTree::SelectPlane(TraversalLeaf *leaf,
253                                                           const AxisAlignedBox3 &box,
254                                                           float &position)
[2073]255{
[2093]256        int axis = -1;
[2073]257
[2093]258        switch (mSplitMethod)
259        {
260        case SPLIT_SPATIAL_MEDIAN:
261                {
262                        axis = box.Size().DrivingAxis();
[2124]263                        position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
[2093]264                        break;
[2073]265                }
[2093]266        case SPLIT_SAH:
267                {
268                        int objectsBack, objectsFront;
[2124]269                        float costRatio = 99999;//MAX_FLOAT;
[2093]270
[2124]271                        for (int i=0; i < 3; ++ i)
[2093]272                        {
[2124]273                                float p;
274                                float r = BestCostRatio(leaf,
275                                                                                box,
276                                                                                i,
277                                                                                p,
278                                                                                objectsBack,
279                                                                                objectsFront);
280       
281                                if (r < costRatio)
[2093]282                                {
[2124]283                                        costRatio = r;
284                                        axis = i;
285                                        position = p;
[2093]286                                }
287                        }
288
289                        if (costRatio > mMaxCostRatio)
290                        {
[2124]291                                cout << "Too big cost ratio " << costRatio << endl;
[2093]292                                axis = -1;
293                        }
294                        break;
295                }
296        }
297
298        return axis;
[2073]299}
300
[2093]301
[2073]302TraversalNode *TraversalTree::SubdivideNode(TraversalLeaf *leaf,
303                                                                                        const AxisAlignedBox3 &box,
304                                                                                        AxisAlignedBox3 &backBBox,
[2093]305                                                                                        AxisAlignedBox3 &frontBBox)
[2073]306{
307
308        if (TerminationCriteriaMet(leaf))
309                return leaf;
310
311        float position;
312
313        // select subdivision axis
314        int axis = SelectPlane( leaf, box, position );
315
316        if (axis == -1) {
[2124]317                cout << "terminate on cost ratio" << endl;
[2149]318                ++ mStat.costRatioNodes;
[2073]319                return leaf;
320        }
321
322        mStat.nodes+=2;
323        mStat.splits[axis]++;
324
325        // add the new nodes to the tree
326        TraversalInterior *node = new TraversalInterior(leaf->mParent);
327
328        node->mAxis = axis;
329        node->mPosition = position;
330        node->mBox = box;
331
332        backBBox = box;
333        frontBBox = box;
334
335        // first count ray sides
336        int objectsBack = 0;
337        int objectsFront = 0;
338
339        backBBox.SetMax(axis, position);
340        frontBBox.SetMin(axis, position);
341
[2124]342        ViewCellContainer::const_iterator mi, mi_end = leaf->mViewCells.end();
[2073]343
[2124]344        for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi)
[2073]345        {
346                // determine the side of this ray with respect to the plane
347                AxisAlignedBox3 box = (*mi)->GetBox();
[2124]348                if (box.Max(axis) > position)
349                        ++ objectsFront;
[2073]350
[2124]351                if (box.Min(axis) < position)
[2093]352                        ++ objectsBack;
[2073]353        }
354
355        TraversalLeaf *back = new TraversalLeaf(node, objectsBack);
356        TraversalLeaf *front = new TraversalLeaf(node, objectsFront);
357
[2124]358        back->mDepth = front->mDepth = leaf->mDepth + 1;
[2073]359
360        // replace a link from node's parent
[2093]361        if (leaf->mParent)
362        {               
[2073]363                leaf->mParent->ReplaceChildLink(leaf, node);
[2093]364        }
[2073]365
366        // and setup child links
367        node->SetupChildLinks(back, front);
368
[2124]369        for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi)
[2073]370        {
371                // determine the side of this ray with respect to the plane
372                AxisAlignedBox3 box = (*mi)->GetBox();
373
374                if (box.Max(axis) >= position )
375                {
[2124]376                        front->mViewCells.push_back(*mi);
[2073]377                }
378
379                if (box.Min(axis) < position )
380                {
[2124]381                        back->mViewCells.push_back(*mi);
[2073]382                }
383
[2124]384                mStat.objectRefs -= (int)leaf->mViewCells.size();
[2073]385                mStat.objectRefs += objectsBack + objectsFront;
386        }
387
[2093]388        delete leaf;
[2073]389
390        return node;
391}
392
393
[2093]394void TraversalTreeStatistics::Print(ostream &app) const
[2073]395{
[2093]396        app << "===== TraversalTree statistics ===============\n";
[2073]397
[2093]398        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
[2073]399
[2093]400        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
[2073]401
[2093]402        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz)\n";
[2073]403
[2124]404        for (int i = 0; i < 7; ++ i)
405                app << splits[i] << " ";
406        app << endl;
[2073]407
[2093]408        app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" <<
409                maxObjectRefs << "\n";
[2073]410
[2124]411        app << "#N_AVGOBJECTREFS  ( Avg number of object refs / leaf )\n" <<
412                totalObjectRefs / (double)Leaves() << "\n";
[2073]413
[2093]414        app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
[2124]415                objectRefs / (double)Leaves() << "\n";
[2073]416
[2093]417        app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
[2124]418                zeroQueryNodes * 100 / (double)Leaves() << endl;
[2073]419
[2093]420        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
[2124]421                maxDepthNodes * 100 / (double)Leaves() << endl;
[2073]422
[2093]423        app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
[2124]424                minCostNodes * 100 / (double)Leaves() << endl;
[2073]425
[2149]426        app << "#N_COSTRATIOLEAVES ( Percentage of leaves with cost ratio termination )\n"<<
427                costRatioNodes * 100 / (double)Leaves() << endl;
428
[2093]429        //  app << setprecision(4);
430        //  app << "#N_CTIME  ( Construction time [s] )\n"
431        //      << Time() << " \n";
[2073]432
[2124]433        app << "======= END OF TraversalTree statistics ========\n";
[2073]434}
435
436
[2093]437void TraversalTree::EvaluateLeafStats(const TraversalData &data)
[2073]438{
[2124]439        // the node became a leaf -> evaluate stats for leafs
440        TraversalLeaf *leaf = (TraversalLeaf *)data.mNode;
[2073]441
[2149]442        if (data.mDepth >= mTermMaxDepth)
[2124]443                ++ mStat.maxDepthNodes;
[2073]444
[2149]445        if ((int)(leaf->mViewCells.size()) <= mTermMinCost)
[2124]446                ++ mStat.minCostNodes;
447
448        mStat.totalObjectRefs += (int)leaf->mViewCells.size();
449
450        if ((int)(leaf->mViewCells.size()) > mStat.maxObjectRefs)
451                mStat.maxObjectRefs = (int)leaf->mViewCells.size();
[2073]452}
453
454
455void
[2093]456TraversalTree::SortSubdivisionCandidates(TraversalLeaf *node,
457                                                                                 const int axis)
[2073]458{
459        CLEAR_CONTAINER(*splitCandidates);
460        //splitCandidates->clear();
461
[2124]462    int requestedSize = 2 * (int)node->mViewCells.size();
[2073]463       
464        // creates a sorted split candidates array
465        if (splitCandidates->capacity() > 500000 &&
[2124]466                requestedSize < (int)(splitCandidates->capacity() / 10) )
[2093]467        {               
468                delete splitCandidates;
469                splitCandidates = new vector<SortableEntry *>;
470        }
[2073]471 
[2093]472        splitCandidates->reserve(requestedSize);
[2073]473
[2124]474       
[2093]475        // insert all queries
[2124]476        for(ViewCellContainer::const_iterator mi = node->mViewCells.begin();
477                mi != node->mViewCells.end();
[2093]478                mi++)
479        {
480                AxisAlignedBox3 box = (*mi)->GetBox();
481
[2544]482                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX, box.Max(axis),     *mi));
[2124]483        }
484
485        // insert all queries
486        for(ViewCellContainer::const_iterator mi = node->mViewCells.begin();
487                mi != node->mViewCells.end();
488                mi++)
489        {
490                AxisAlignedBox3 box = (*mi)->GetBox();
491
[2093]492                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN,
493                        box.Min(axis),
494                        *mi)
495                        );
[2124]496                /*splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
[2093]497                        box.Max(axis),
498                        *mi)
[2124]499                        );*/
[2093]500        }
501
502        stable_sort(splitCandidates->begin(), splitCandidates->end(), iltS);
[2073]503}
504
505
506float
[2093]507TraversalTree::BestCostRatio(TraversalLeaf *node,
508                                                         const AxisAlignedBox3 &box,
509                                                         const int axis,
510                                                         float &position,
511                                                         int &objectsBack,
512                                                         int &objectsFront
513                                                         )
[2073]514{
515
[2149]516#define DEBUG_COST 1
[2073]517
518#if DEBUG_COST
[2093]519        static int nodeId = -1;
520        char filename[256];
[2073]521
[2093]522        static int lastAxis = 100;
[2149]523
[2093]524        if (axis <= lastAxis)
[2149]525                ++ nodeId;
[2073]526
[2093]527        lastAxis = axis;
528
529        sprintf(filename, "sah-cost%d-%d.log", nodeId, axis);
530        ofstream costStream;
531
532        if (nodeId < 100)
533                costStream.open(filename);
534
[2073]535#endif
536
[2093]537        SortSubdivisionCandidates(node, axis);
[2073]538
[2093]539        // go through the lists, count the number of objects left and right
540        // and evaluate the following cost funcion:
541        // C = ct_div_ci  + (ol + or)/queries
[2073]542
[2093]543        vector<SortableEntry *>::const_iterator ci;
[2073]544
[2124]545        int objectsLeft = 0, objectsRight = (int)node->mViewCells.size();
[2073]546
[2124]547        int dummy1 = objectsLeft, dummy2 = objectsRight;
[2093]548
549        float minBox = box.Min(axis);
550        float maxBox = box.Max(axis);
551        float boxArea = box.SurfaceArea();
552
553        float minBand = minBox + mSplitBorder*(maxBox - minBox);
554        float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
555
556        float minSum = 1e20f;
557
[2149]558        int openBoxes = 0;
559
[2093]560        for(ci = splitCandidates->begin(); ci < splitCandidates->end(); ++ ci)
561        {
562                switch ((*ci)->type)
563                {
564                case SortableEntry::BOX_MIN:
[2124]565                        ++ objectsLeft;
[2149]566                        ++ openBoxes;
[2093]567                        break;
568                case SortableEntry::BOX_MAX:
[2124]569                        -- objectsRight;
[2149]570                        -- openBoxes;
[2093]571                        break;
572                }
573
[2124]574                if ((*ci)->value >= minBand && (*ci)->value <= maxBand)
[2093]575                {
576                        AxisAlignedBox3 lbox = box;
577                        AxisAlignedBox3 rbox = box;
[2124]578
[2093]579                        lbox.SetMax(axis, (*ci)->value);
580                        rbox.SetMin(axis, (*ci)->value);
581
[2124]582                        const float sum = objectsLeft * lbox.SurfaceArea() + objectsRight * rbox.SurfaceArea();
[2093]583
[2124]584                        // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
585                        // cout<<"cost= "<<sum<<endl;
[2093]586
[2073]587#if DEBUG_COST
[2093]588                        if (nodeId < 100)
589                        {
[2124]590                                float oldCost = (float)node->mViewCells.size();
[2149]591                                float newCost = mCt_div_ci + sum / boxArea;
[2124]592                                float ratio = newCost / oldCost;
[2149]593
594                                costStream << (*ci)->value << " " << ratio << " open: " << openBoxes;
595
596                                if ((*ci)->type == SortableEntry::BOX_MAX)
597                                        costStream << " max event" << endl;
598                                else
599                                        costStream << " min event" << endl;
[2093]600                        }
[2073]601#endif
[2093]602
603                        if (sum < minSum)
604                        {
605                                minSum = sum;
606                                position = (*ci)->value;
607
608                                objectsBack = objectsLeft;
609                                objectsFront = objectsRight;
610                        }
611                }
612        }
613
[2124]614        const float oldCost = (float)node->mViewCells.size();
615        const float newCost = mCt_div_ci + minSum / boxArea;
616        const float ratio = newCost / oldCost;
[2093]617
[2124]618        //if (boxArea == 0)
619        //      cout << "error: " << boxArea << endl;
620        if (ratio > 2)
621        {
622                cout << "costratio: " << ratio << " oldcost: " << oldCost << " box area: " << boxArea << " new: " << newCost << endl;
623                cout << "obj left: " <<objectsBack<< " obj right: " << objectsFront << endl;
624                cout << "dummy1: " << dummy1 << " dummy2: " << dummy2 << endl;
625        }
[2073]626#if 0
[2093]627        cout<<"===================="<<endl;
628        cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
629                        <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
[2073]630#endif
[2124]631
[2093]632        return ratio;
[2073]633}
634
635
[2124]636int TraversalTree::FindViewCellIntersections(const Vector3 &lStart,
637                                                                                         const Vector3 &lEnd,
638                                                                                         const ViewCellContainer &viewCells,
639                                                                                         ViewCellContainer &hitViewCells,
640                                                                                         const bool useMailboxing)
641{
642        int hits = 0;
643        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
644
645        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
646        {
647                ViewCell *viewCell = *vit;
648                // don't have to mail if each view cell belongs to exactly one leaf
649                if (!useMailboxing || !viewCell->Mailed())
650                {
651                        if (useMailboxing)
652                viewCell->Mail();
653
654                        // hack: assume that we use vsp tree,
655                        //P so we can just test intersection with bounding boxes
[2130]656                        if (viewCell->GetBox().Intersects(lStart, lEnd))
[2124]657                        {
658                                hitViewCells.push_back(viewCell);
659                                ++ hits;
660                        }
661                }
662        }
663
664        return hits;
665}
666
667
[2073]668int TraversalTree::CastLineSegment(const Vector3 &origin,
[2093]669                                                                   const Vector3 &termination,
[2124]670                                                                   ViewCellContainer &viewCells,
[2093]671                                                                   const bool useMailboxing)
[2073]672{
673        int hits = 0;
674
675        float mint = 0.0f, maxt = 1.0f;
676        const Vector3 dir = termination - origin;
677
[2093]678        stack<LineTraversalData> tStack;
[2073]679
680        Vector3 entp = origin;
681        Vector3 extp = termination;
682
683        TraversalNode *node = mRoot;
684        TraversalNode *farChild;
685
686        float position;
687        int axis;
688
689        while (1)
690        {
691                if (!node->IsLeaf())
692                {
693                        TraversalInterior *in = static_cast<TraversalInterior *>(node);
694                        position = in->mPosition;
695                        axis = in->mAxis;
696
697                        if (entp[axis] <= position)
698                        {
699                                if (extp[axis] <= position)
700                                {
701                                        node = in->mBack;
702                                        // cases N1,N2,N3,P5,Z2,Z3
703                                        continue;
[2093]704                                } else
[2073]705                                {
706                                        // case N4
707                                        node = in->mBack;
708                                        farChild = in->mFront;
709                                }
710                        }
711                        else
712                        {
713                                if (position <= extp[axis])
714                                {
715                                        node = in->mFront;
716                                        // cases P1,P2,P3,N5,Z1
717                                        continue;
718                                }
719                                else
720                                {
721                                        node = in->mFront;
722                                        farChild = in->mBack;
723                                        // case P4
724                                }
725                        }
726
727                        // $$ modification 3.5.2004 - hints from Kamil Ghais
728                        // case N4 or P4
[2093]729                        const float tdist = (position - origin[axis]) / dir[axis];
730                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
731
[2073]732                        extp = origin + dir * tdist;
733                        maxt = tdist;
734                }
735                else
736                {
737                        // compute intersection with all objects in this leaf
738                        TraversalLeaf *leaf = static_cast<TraversalLeaf *>(node);
739
[2124]740                        hits += FindViewCellIntersections(origin,
741                                                                                          termination,
742                                                                                          leaf->mViewCells,
743                                                                                          viewCells,
744                                                                                          useMailboxing);
745                       
[2073]746                        // get the next node from the stack
747                        if (tStack.empty())
748                                break;
749
750                        entp = extp;
751                        mint = maxt;
752                       
[2093]753                        LineTraversalData &s  = tStack.top();
[2073]754                        node = s.mNode;
755                        extp = s.mExitPoint;
756                        maxt = s.mMaxT;
[2093]757
[2073]758                        tStack.pop();
759                }
760        }
761
762        return hits;
763}
764
765
[2093]766void TraversalTree::CollectLeaves(vector<TraversalLeaf *> &leaves)
[2073]767{
[2093]768        stack<TraversalNode *> nodeStack;
769        nodeStack.push(mRoot);
[2073]770
[2093]771        while (!nodeStack.empty())
772        {
773                TraversalNode *node = nodeStack.top();
774                nodeStack.pop();
775               
776                if (node->IsLeaf())
777                {
778                        TraversalLeaf *leaf = (TraversalLeaf *)node;
779                        leaves.push_back(leaf);
780                }
781                else
782                {
783                        TraversalInterior *interior = (TraversalInterior *)node;
784                        nodeStack.push(interior->mBack);
785                        nodeStack.push(interior->mFront);
786                }
787        }
[2073]788}
789
790
[2093]791AxisAlignedBox3 TraversalTree::GetBox(const TraversalNode *node) const
792{       
793        TraversalInterior *parent = node->mParent;
794       
795        if (parent == NULL)
796                return mBox;
797
798        if (!node->IsLeaf())
799                return ((TraversalInterior *)node)->mBox;
800
801        AxisAlignedBox3 box(parent->mBox);
802       
803        if (parent->mFront == node)
804                box.SetMin(parent->mAxis, parent->mPosition);
805        else
806                box.SetMax(parent->mAxis, parent->mPosition);
807        return box;
[2073]808}
[2093]809
810}
Note: See TracBrowser for help on using the repository browser.