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

Revision 2176, 18.1 KB checked in by mattausch, 18 years ago (diff)

removed using namespace std from .h

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
[2149]482                //cout << "box: " << box << endl;
[2124]483                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
484                        box.Max(axis),
485                        *mi)
486                        );
487        }
488
489        // insert all queries
490        for(ViewCellContainer::const_iterator mi = node->mViewCells.begin();
491                mi != node->mViewCells.end();
492                mi++)
493        {
494                AxisAlignedBox3 box = (*mi)->GetBox();
495
[2093]496                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN,
497                        box.Min(axis),
498                        *mi)
499                        );
[2124]500                /*splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
[2093]501                        box.Max(axis),
502                        *mi)
[2124]503                        );*/
[2093]504        }
505
506        stable_sort(splitCandidates->begin(), splitCandidates->end(), iltS);
[2073]507}
508
509
510float
[2093]511TraversalTree::BestCostRatio(TraversalLeaf *node,
512                                                         const AxisAlignedBox3 &box,
513                                                         const int axis,
514                                                         float &position,
515                                                         int &objectsBack,
516                                                         int &objectsFront
517                                                         )
[2073]518{
519
[2149]520#define DEBUG_COST 1
[2073]521
522#if DEBUG_COST
[2093]523        static int nodeId = -1;
524        char filename[256];
[2073]525
[2093]526        static int lastAxis = 100;
[2149]527
[2093]528        if (axis <= lastAxis)
[2149]529                ++ nodeId;
[2073]530
[2093]531        lastAxis = axis;
532
533        sprintf(filename, "sah-cost%d-%d.log", nodeId, axis);
534        ofstream costStream;
535
536        if (nodeId < 100)
537                costStream.open(filename);
538
[2073]539#endif
540
[2093]541        SortSubdivisionCandidates(node, axis);
[2073]542
[2093]543        // go through the lists, count the number of objects left and right
544        // and evaluate the following cost funcion:
545        // C = ct_div_ci  + (ol + or)/queries
[2073]546
[2093]547        vector<SortableEntry *>::const_iterator ci;
[2073]548
[2124]549        int objectsLeft = 0, objectsRight = (int)node->mViewCells.size();
[2073]550
[2124]551        int dummy1 = objectsLeft, dummy2 = objectsRight;
[2093]552
553        float minBox = box.Min(axis);
554        float maxBox = box.Max(axis);
555        float boxArea = box.SurfaceArea();
556
557        float minBand = minBox + mSplitBorder*(maxBox - minBox);
558        float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
559
560        float minSum = 1e20f;
561
[2149]562        int openBoxes = 0;
563
[2093]564        for(ci = splitCandidates->begin(); ci < splitCandidates->end(); ++ ci)
565        {
566                switch ((*ci)->type)
567                {
568                case SortableEntry::BOX_MIN:
[2124]569                        ++ objectsLeft;
[2149]570                        ++ openBoxes;
[2093]571                        break;
572                case SortableEntry::BOX_MAX:
[2124]573                        -- objectsRight;
[2149]574                        -- openBoxes;
[2093]575                        break;
576                }
577
[2124]578                if ((*ci)->value >= minBand && (*ci)->value <= maxBand)
[2093]579                {
580                        AxisAlignedBox3 lbox = box;
581                        AxisAlignedBox3 rbox = box;
[2124]582
[2093]583                        lbox.SetMax(axis, (*ci)->value);
584                        rbox.SetMin(axis, (*ci)->value);
585
[2124]586                        const float sum = objectsLeft * lbox.SurfaceArea() + objectsRight * rbox.SurfaceArea();
[2093]587
[2124]588                        // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
589                        // cout<<"cost= "<<sum<<endl;
[2093]590
[2073]591#if DEBUG_COST
[2093]592                        if (nodeId < 100)
593                        {
[2124]594                                float oldCost = (float)node->mViewCells.size();
[2149]595                                float newCost = mCt_div_ci + sum / boxArea;
[2124]596                                float ratio = newCost / oldCost;
[2149]597
598                                costStream << (*ci)->value << " " << ratio << " open: " << openBoxes;
599
600                                if ((*ci)->type == SortableEntry::BOX_MAX)
601                                        costStream << " max event" << endl;
602                                else
603                                        costStream << " min event" << endl;
[2093]604                        }
[2073]605#endif
[2093]606
607                        if (sum < minSum)
608                        {
609                                minSum = sum;
610                                position = (*ci)->value;
611
612                                objectsBack = objectsLeft;
613                                objectsFront = objectsRight;
614                        }
615                }
616        }
617
[2124]618        const float oldCost = (float)node->mViewCells.size();
619        const float newCost = mCt_div_ci + minSum / boxArea;
620        const float ratio = newCost / oldCost;
[2093]621
[2124]622        //if (boxArea == 0)
623        //      cout << "error: " << boxArea << endl;
624        if (ratio > 2)
625        {
626                cout << "costratio: " << ratio << " oldcost: " << oldCost << " box area: " << boxArea << " new: " << newCost << endl;
627                cout << "obj left: " <<objectsBack<< " obj right: " << objectsFront << endl;
628                cout << "dummy1: " << dummy1 << " dummy2: " << dummy2 << endl;
629        }
[2073]630#if 0
[2093]631        cout<<"===================="<<endl;
632        cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
633                        <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
[2073]634#endif
[2124]635
[2093]636        return ratio;
[2073]637}
638
639
[2124]640int TraversalTree::FindViewCellIntersections(const Vector3 &lStart,
641                                                                                         const Vector3 &lEnd,
642                                                                                         const ViewCellContainer &viewCells,
643                                                                                         ViewCellContainer &hitViewCells,
644                                                                                         const bool useMailboxing)
645{
646        int hits = 0;
647        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
648
649        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
650        {
651                ViewCell *viewCell = *vit;
652                // don't have to mail if each view cell belongs to exactly one leaf
653                if (!useMailboxing || !viewCell->Mailed())
654                {
655                        if (useMailboxing)
656                viewCell->Mail();
657
658                        // hack: assume that we use vsp tree,
659                        //P so we can just test intersection with bounding boxes
[2130]660                        if (viewCell->GetBox().Intersects(lStart, lEnd))
[2124]661                        {
662                                hitViewCells.push_back(viewCell);
663                                ++ hits;
664                        }
665                }
666        }
667
668        return hits;
669}
670
671
[2073]672int TraversalTree::CastLineSegment(const Vector3 &origin,
[2093]673                                                                   const Vector3 &termination,
[2124]674                                                                   ViewCellContainer &viewCells,
[2093]675                                                                   const bool useMailboxing)
[2073]676{
677        int hits = 0;
678
679        float mint = 0.0f, maxt = 1.0f;
680        const Vector3 dir = termination - origin;
681
[2093]682        stack<LineTraversalData> tStack;
[2073]683
684        Vector3 entp = origin;
685        Vector3 extp = termination;
686
687        TraversalNode *node = mRoot;
688        TraversalNode *farChild;
689
690        float position;
691        int axis;
692
693        while (1)
694        {
695                if (!node->IsLeaf())
696                {
697                        TraversalInterior *in = static_cast<TraversalInterior *>(node);
698                        position = in->mPosition;
699                        axis = in->mAxis;
700
701                        if (entp[axis] <= position)
702                        {
703                                if (extp[axis] <= position)
704                                {
705                                        node = in->mBack;
706                                        // cases N1,N2,N3,P5,Z2,Z3
707                                        continue;
[2093]708                                } else
[2073]709                                {
710                                        // case N4
711                                        node = in->mBack;
712                                        farChild = in->mFront;
713                                }
714                        }
715                        else
716                        {
717                                if (position <= extp[axis])
718                                {
719                                        node = in->mFront;
720                                        // cases P1,P2,P3,N5,Z1
721                                        continue;
722                                }
723                                else
724                                {
725                                        node = in->mFront;
726                                        farChild = in->mBack;
727                                        // case P4
728                                }
729                        }
730
731                        // $$ modification 3.5.2004 - hints from Kamil Ghais
732                        // case N4 or P4
[2093]733                        const float tdist = (position - origin[axis]) / dir[axis];
734                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
735
[2073]736                        extp = origin + dir * tdist;
737                        maxt = tdist;
738                }
739                else
740                {
741                        // compute intersection with all objects in this leaf
742                        TraversalLeaf *leaf = static_cast<TraversalLeaf *>(node);
743
[2124]744                        hits += FindViewCellIntersections(origin,
745                                                                                          termination,
746                                                                                          leaf->mViewCells,
747                                                                                          viewCells,
748                                                                                          useMailboxing);
749                       
[2073]750                        // get the next node from the stack
751                        if (tStack.empty())
752                                break;
753
754                        entp = extp;
755                        mint = maxt;
756                       
[2093]757                        LineTraversalData &s  = tStack.top();
[2073]758                        node = s.mNode;
759                        extp = s.mExitPoint;
760                        maxt = s.mMaxT;
[2093]761
[2073]762                        tStack.pop();
763                }
764        }
765
766        return hits;
767}
768
769
[2093]770void TraversalTree::CollectLeaves(vector<TraversalLeaf *> &leaves)
[2073]771{
[2093]772        stack<TraversalNode *> nodeStack;
773        nodeStack.push(mRoot);
[2073]774
[2093]775        while (!nodeStack.empty())
776        {
777                TraversalNode *node = nodeStack.top();
778                nodeStack.pop();
779               
780                if (node->IsLeaf())
781                {
782                        TraversalLeaf *leaf = (TraversalLeaf *)node;
783                        leaves.push_back(leaf);
784                }
785                else
786                {
787                        TraversalInterior *interior = (TraversalInterior *)node;
788                        nodeStack.push(interior->mBack);
789                        nodeStack.push(interior->mFront);
790                }
791        }
[2073]792}
793
794
[2093]795AxisAlignedBox3 TraversalTree::GetBox(const TraversalNode *node) const
796{       
797        TraversalInterior *parent = node->mParent;
798       
799        if (parent == NULL)
800                return mBox;
801
802        if (!node->IsLeaf())
803                return ((TraversalInterior *)node)->mBox;
804
805        AxisAlignedBox3 box(parent->mBox);
806       
807        if (parent->mFront == node)
808                box.SetMin(parent->mAxis, parent->mPosition);
809        else
810                box.SetMax(parent->mAxis, parent->mPosition);
811        return box;
[2073]812}
[2093]813
814}
Note: See TracBrowser for help on using the repository browser.