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

Revision 2149, 18.1 KB checked in by mattausch, 17 years ago (diff)

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