source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp @ 332

Revision 332, 37.7 KB checked in by mattausch, 19 years ago (diff)

fixed bug when asigning bsp root
subdivision termination criterium based on rays
Line 
1#include "Plane3.h"
2#include "ViewCellBsp.h"
3#include "Mesh.h"
4#include "common.h"
5#include "ViewCell.h"
6#include "Environment.h"
7#include "Polygon3.h"
8#include "Ray.h"
9#include "AxisAlignedBox3.h"
10#include <stack>
11#include <time.h>
12#include <iomanip>
13#include "Exporter.h"
14#include "Plane3.h"
15
16int BspTree::sTermMaxPolygons = 10;
17int BspTree::sTermMaxDepth = 20;
18int BspTree::sMaxCandidates = 10;
19int BspTree::sSplitPlaneStrategy = BALANCED_POLYS;
20int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS;
21int BspTree::sTermMaxPolysForAxisAligned = 50;
22int BspTree::sTermMaxRays = -1;
23
24float BspTree::sCt_div_ci = 1.0f;
25float BspTree::sSplitBorder = 1.0f;
26float BspTree::sMaxCostRatio = 0.9f;
27
28//-- factors for bsp tree split plane heuristics
29
30float BspTree::sLeastSplitsFactor = 1.0f;
31float BspTree::sBalancedPolysFactor = 1.0f;
32float BspTree::sBalancedViewCellsFactor = 1.0f;
33// NOTE:  very important criterium for 2.5d scenes
34float BspTree::sVerticalSplitsFactor = 1.0f;
35float BspTree::sLargestPolyAreaFactor = 1.0f;
36float BspTree::sBlockedRaysFactor = 1.0f;
37float BspTree::sLeastRaySplitsFactor = 1.0f;
38float BspTree::sBalancedRaysFactor = 1.0f;
39
40bool BspTree::sStoreSplitPolys = false;
41
42/** Evaluates split plane classification with respect to the plane's
43        contribution for a balanced tree.
44*/
45float BspTree::sLeastSplitsTable[] = {0, 0, 1, 0};
46/** Evaluates split plane classification with respect to the plane's
47        contribution for a minimum number splits in the tree.
48*/
49float BspTree::sBalancedPolysTable[] = {-1, 1, 0, 0};
50
51/****************************************************************/
52/*                  class BspNode implementation                */
53/****************************************************************/
54
55BspNode::BspNode():
56mParent(NULL), mPolygons(NULL)
57{}
58
59BspNode::BspNode(BspInterior *parent):
60mParent(parent), mPolygons(NULL)
61{}
62
63BspNode::~BspNode()
64{
65        if (mPolygons)
66        {
67                CLEAR_CONTAINER(*mPolygons);
68                DEL_PTR(mPolygons);
69        }
70}
71
72bool BspNode::IsRoot() const
73{
74        return mParent == NULL;
75}
76
77BspInterior *BspNode::GetParent()
78{
79        return mParent;
80}
81
82void BspNode::SetParent(BspInterior *parent)
83{
84        mParent = parent;
85}
86
87PolygonContainer *BspNode::GetPolygons()
88{
89        if (!mPolygons)
90                mPolygons = new PolygonContainer();
91
92        return mPolygons;
93}
94
95void BspNode::ProcessPolygons(PolygonContainer *polys, bool storePolys)
96{
97        if (storePolys)
98        {
99                while (!polys->empty())
100                {
101                        GetPolygons()->push_back(polys->back());
102                        polys->pop_back();
103                }
104        }
105        else CLEAR_CONTAINER(*polys);
106}
107
108
109/****************************************************************/
110/*              class BspInterior implementation                */
111/****************************************************************/
112
113
114BspInterior::BspInterior(const Plane3 &plane):
115mPlane(plane), mFront(NULL), mBack(NULL)
116{}
117
118bool BspInterior::IsLeaf() const
119{
120        return false;
121}
122
123BspNode *BspInterior::GetBack()
124{
125        return mBack;
126}
127
128BspNode *BspInterior::GetFront()
129{
130        return mFront;
131}
132
133Plane3 *BspInterior::GetPlane()
134{
135        return &mPlane;
136}
137
138void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild)
139{
140        if (mBack == oldChild)
141                mBack = newChild;
142        else
143                mFront = newChild;
144}
145
146void BspInterior::SetupChildLinks(BspNode *b, BspNode *f)
147{
148    mBack = b;
149    mFront = f;
150}
151
152void BspInterior::ProcessPolygon(Polygon3 **poly, const bool storePolys)
153{
154        if (storePolys)
155                GetPolygons()->push_back(*poly);
156        else
157                DEL_PTR(*poly);
158}
159
160void BspInterior::SplitRays(RayContainer &rays,
161                                                        RayContainer &frontRays,
162                                                        RayContainer &backRays)
163{
164        while (!rays.empty())
165        {
166                Ray *ray = rays.back();
167                rays.pop_back();
168
169                //-- ray-plane intersection
170                float maxT = 1e6;
171                float minT = 0;
172       
173                // test with tree bounding box
174/*              if (!mBox.GetMinMaxT(*ray, &minT, &maxT))
175                        continue;
176                if (minT < 0) // start ray from origin
177                        minT = 0;
178*/
179                // bound ray
180                if ((ray->GetType() == Ray::LOCAL_RAY) &&
181                        (!ray->intersections.empty())      &&
182                        (ray->intersections[0].mT <= maxT))
183                {
184                        maxT = ray->intersections[0].mT;
185                }
186               
187                int classification = ray->ClassifyPlane(mPlane, minT, maxT);
188               
189                switch (classification)
190                {
191                case Plane3::COINCIDENT:
192                        break;
193                case Plane3::BACK_SIDE:
194                        ray->SetId(BACK_RAY);
195                        backRays.push_back(ray);
196                        break;
197                case Plane3::FRONT_SIDE:
198                        ray->SetId(FRONT_RAY);
199                        frontRays.push_back(ray);
200                        break;
201                case Plane3::SPLIT:
202                        ray->SetId(SPLIT_RAY);
203                        frontRays.push_back(ray);
204                        backRays.push_back(ray);
205                        //extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
206                        break;
207                default:
208                        break;
209                }
210        }
211}
212
213int BspInterior::SplitPolygons(PolygonContainer &polys,
214                                                           PolygonContainer &frontPolys,
215                                                           PolygonContainer &backPolys,
216                                                           PolygonContainer &coincident,
217                                                           bool storePolys)
218{
219        Polygon3 *splitPoly = NULL;
220
221        int splits = 0;
222
223#ifdef _Debug
224        Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
225#endif
226        while (!polys.empty())
227        {
228                Polygon3 *poly = polys.back();
229                polys.pop_back();
230
231                //Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
232
233                // classify polygon
234                int classification = poly->ClassifyPlane(mPlane);
235
236                Polygon3 *front_piece = NULL;
237                Polygon3 *back_piece = NULL;
238       
239                VertexContainer splitVertices;
240
241                switch (classification)
242                {
243                        case Plane3::COINCIDENT:
244                                coincident.push_back(poly);
245                                break;                 
246                        case Plane3::FRONT_SIDE:       
247                                frontPolys.push_back(poly);
248                                break;
249                        case Plane3::BACK_SIDE:
250                                backPolys.push_back(poly);
251                                break;
252                        case Plane3::SPLIT:
253                                front_piece = new Polygon3(poly->mParent);
254                                back_piece = new Polygon3(poly->mParent);
255
256                                //-- split polygon into front and back part
257                                poly->Split(mPlane,
258                                                        *front_piece,
259                                                        *back_piece,
260                                                        splitVertices);
261                                       
262                                ++ splits; // increase number of splits
263
264                                //-- inherit rays
265                                if (poly->mPiercingRays)
266                                        InheritRays(*poly, *front_piece, *back_piece);
267
268                                // check if polygons still valid
269                                if (front_piece->Valid())
270                                        frontPolys.push_back(front_piece);
271                                else
272                                        DEL_PTR(front_piece);
273                               
274                                if (back_piece->Valid())
275                                        backPolys.push_back(back_piece);
276                                else                           
277                                        DEL_PTR(back_piece);
278                               
279#ifdef _DEBUG
280                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
281#endif
282                                ProcessPolygon(&poly, storePolys);
283                               
284                                break;
285                        default:
286                Debug << "SHOULD NEVER COME HERE\n";
287                                break;
288                }
289        }
290
291        return splits;
292}
293
294void BspInterior::InheritRays(const Polygon3 &poly,
295                                                      Polygon3 &front_piece,
296                                                      Polygon3 &back_piece)
297{
298        RayContainer *rays = poly.mPiercingRays;
299
300        RayContainer::const_iterator it, it_end = rays->end();
301
302        for (it = rays->begin(); it != it_end; ++ it)
303        {
304                switch((*it)->GetId())
305                {
306                case BACK_RAY:
307                        back_piece.GetPiercingRays()->push_back(*it);
308                        break;
309                case FRONT_RAY:
310                        front_piece.GetPiercingRays()->push_back(*it);
311                        break;
312                }
313        }
314}
315
316/****************************************************************/
317/*                  class BspLeaf implementation                */
318/****************************************************************/
319BspLeaf::BspLeaf(): mViewCell(NULL)
320{
321}
322
323BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell)
324{
325}
326
327BspLeaf::BspLeaf(BspInterior *parent): BspNode(parent), mViewCell(NULL)
328{}
329
330BspLeaf::BspLeaf(BspInterior *parent, ViewCell *viewCell):
331BspNode(parent), mViewCell(viewCell)
332{
333}
334
335ViewCell *BspLeaf::GetViewCell()
336{
337        return mViewCell;
338}
339
340void BspLeaf::SetViewCell(ViewCell *viewCell)
341{
342        mViewCell = viewCell;
343}
344
345bool BspLeaf::IsLeaf() const
346{
347        return true;
348}
349
350int BspLeaf::GenerateViewCell(const RayContainer &rays)
351{
352        int contributingSamples = 0;
353
354        mViewCell = new ViewCell();
355
356    RayContainer::const_iterator it, it_end = rays.end();
357
358        // add contributions from samples to the PVS
359        for (it = rays.begin(); it != it_end; ++ it)
360        {
361                if (!(*it)->intersections.empty())
362                {       
363            if (mViewCell->GetPvs().AddSample((*it)->intersections[0].mObject) > 0)
364                                ++ contributingSamples;
365                }
366        }
367
368        return contributingSamples;
369}
370
371
372/****************************************************************/
373/*                  class BspTree implementation                */
374/****************************************************************/
375
376BspTree::BspTree(ViewCell *viewCell):
377mRootCell(viewCell), mRoot(NULL), mGenerateViewCells(false)
378{
379        Randomize(); // initialise random generator for heuristics
380}
381 
382const BspTreeStatistics &BspTree::GetStatistics() const
383{
384        return mStat;
385}
386
387void BspTreeStatistics::Print(ostream &app) const
388{
389        app << "===== BspTree statistics ===============\n";
390
391        app << setprecision(4);
392
393        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
394
395        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
396
397        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
398
399        app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
400
401        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
402        maxDepthNodes * 100 / (double)Leaves() << endl;
403
404        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
405
406        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
407
408        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
409
410        app << "#N_INPUT_POLYGONS (number of input polygons )\n" <<     polys << endl;
411
412        app << "#N_PVS: " << pvs << endl;
413
414        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
415                 (polys + splits) / (double)polys << endl;
416       
417        app << "===== END OF BspTree statistics ==========\n";
418}
419
420BspTree::~BspTree()
421{
422        std::stack<BspNode *> tStack;
423
424        tStack.push(mRoot);
425
426        while (!tStack.empty())
427        {
428                BspNode *node = tStack.top();
429
430            tStack.pop();
431       
432                if (!node->IsLeaf())
433                {
434                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
435
436                        // push the children on the stack (there are always two children)
437                        tStack.push(interior->GetBack());
438                        tStack.push(interior->GetFront());
439                }
440
441                DEL_PTR(node);
442        }
443}
444
445void BspTree::InsertViewCell(ViewCell *viewCell)
446{
447        PolygonContainer *polys = new PolygonContainer();
448
449        // extract polygons that guide the split process
450        mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
451        mBox.Include(viewCell->GetBox()); // add to BSP aabb
452
453        InsertPolygons(polys);
454}
455
456void BspTree::InsertPolygons(PolygonContainer *polys)
457{       
458        std::stack<BspTraversalData> tStack;
459       
460        // traverse existing tree or create new tree
461    if (!mRoot)
462                mRoot = new BspLeaf();
463
464        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new RayContainer()));
465
466        while (!tStack.empty())
467        {
468                // filter polygons donw the tree
469                BspTraversalData tData = tStack.top();
470            tStack.pop();
471                       
472                if (!tData.mNode->IsLeaf())
473                {
474                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
475
476                        //-- filter view cell polygons down the tree until a leaf is reached
477                        if (!tData.mPolygons->empty())
478                        {
479                                PolygonContainer *frontPolys = new PolygonContainer();
480                                PolygonContainer *backPolys = new PolygonContainer();
481                                PolygonContainer coincident;
482
483                                int splits = 0;
484               
485                                // split viewcell polygons with respect to split plane
486                                splits += interior->SplitPolygons(*tData.mPolygons,
487                                                                                                  *frontPolys,
488                                                                                                  *backPolys,
489                                                                                                  coincident,
490                                                                                                  sStoreSplitPolys);
491                               
492                                // extract view cells associated with the split polygons
493                                ViewCell *frontViewCell = mRootCell;
494                                ViewCell *backViewCell = mRootCell;
495       
496                                if (!mGenerateViewCells)
497                                {
498                                        ExtractViewCells(&backViewCell,
499                                                                         &frontViewCell,
500                                                                         coincident,
501                                                                         interior->mPlane,
502                                                                         frontPolys->empty(),
503                                                                         backPolys->empty());
504                                }
505
506                                // don't need coincident polygons anymore
507                                interior->ProcessPolygons(&coincident, sStoreSplitPolys);
508
509                                mStat.splits += splits;
510
511                                // push the children on the stack
512                                tStack.push(BspTraversalData(interior->GetFront(),
513                                                                                         frontPolys,
514                                                                                         tData.mDepth + 1,
515                                                                                         frontViewCell,
516                                                                                         tData.mRays));
517
518                                tStack.push(BspTraversalData(interior->GetBack(),
519                                                                                         backPolys,
520                                                                                         tData.mDepth + 1,
521                                                                                         backViewCell,
522                                                                                         new RayContainer()));
523                        }
524
525                        // cleanup
526                        DEL_PTR(tData.mPolygons);
527                }
528                else
529                {
530                        // reached leaf => subdivide current viewcell
531                        BspNode *subRoot = Subdivide(tStack, tData);
532                }
533        }
534}
535
536int BspTree::AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent)
537{
538        FaceContainer::const_iterator fi;
539       
540        // copy the face data to polygons
541        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
542        {
543                Polygon3 *poly = new Polygon3((*fi), mesh);
544                poly->mParent = parent; // set parent intersectable
545                polys.push_back(poly);
546        }
547        return (int)mesh->mFaces.size();
548}
549
550int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
551                                                          PolygonContainer &polys,
552                                                          int maxObjects)
553{
554        int limit = (maxObjects > 0) ?
555                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
556 
557        int polysSize = 0;
558
559        for (int i = 0; i < limit; ++ i)
560        {
561                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
562                {
563                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
564                        polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(),
565                                                                                   polys, viewCells[i]);
566                }
567        }
568
569        return polysSize;
570}
571
572int BspTree::AddToPolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
573{
574        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
575 
576        for (int i = 0; i < limit; ++i)
577        {
578                Intersectable *object = objects[i];//*it;
579                Mesh *mesh = NULL;
580
581                switch (object->Type()) // extract the meshes
582                {
583                case Intersectable::MESH_INSTANCE:
584                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
585                        break;
586                case Intersectable::VIEW_CELL:
587                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
588                        break;
589                        // TODO: handle transformed mesh instances
590                default:
591                        Debug << "intersectable type not supported" << endl;
592                        break;
593                }
594               
595        if (mesh) // copy the mesh data to polygons
596                {
597                        mBox.Include(object->GetBox()); // add to BSP tree aabb
598                        AddMeshToPolygons(mesh, polys, mRootCell);
599                }
600        }
601
602        return (int)polys.size();
603}
604
605void BspTree::Construct(const ViewCellContainer &viewCells)
606{
607        mStat.nodes = 1;
608        mBox.Initialize();      // initialise bsp tree bounding box
609
610        // copy view cell meshes into one big polygon soup
611        PolygonContainer *polys = new PolygonContainer();
612        mStat.polys = AddToPolygonSoup(viewCells, *polys);
613
614        // construct tree from the view cell polygons
615        Construct(polys, new RayContainer());
616}
617
618
619void BspTree::Construct(const ObjectContainer &objects)
620{
621        mStat.nodes = 1;
622        mBox.Initialize();      // initialise bsp tree bounding box
623       
624        PolygonContainer *polys = new PolygonContainer();
625       
626        // copy mesh instance polygons into one big polygon soup
627        mStat.polys = AddToPolygonSoup(objects, *polys);
628
629        // construct tree from polygon soup
630        Construct(polys, new RayContainer());
631}
632
633void BspTree::Construct(const RayContainer &sampleRays)
634{
635        mStat.nodes = 1;
636        mBox.Initialize();      // initialise bsp tree bounding box
637       
638        PolygonContainer *polys = new PolygonContainer();
639        RayContainer *rays = new RayContainer();
640
641        RayContainer::const_iterator rit, rit_end = sampleRays.end();
642
643        long startTime = GetTime();
644        Debug << "**** Extracting polygons from rays ****\n";
645
646        std::map<Face *, Polygon3 *> facePolyMap;
647
648        //-- extract polygons intersected by the rays
649        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
650        {
651                Ray *ray = *rit;
652                ray->SetId(-1); // reset id
653                rays->push_back(ray);
654
655                // get ray-face intersection. Store polygon representing the rays together
656                // with rays intersecting the face.
657                if (!ray->intersections.empty())
658                {
659                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->intersections[0].mObject);
660                        Face *face = obj->GetMesh()->mFaces[ray->intersections[0].mFace];
661
662                        std::map<Face *, Polygon3 *>::iterator it= facePolyMap.find(face);
663
664                        if (it != facePolyMap.end())
665                        {
666                                (*it).second->AddPiercingRay(ray);
667                        }
668                        else
669                        {
670                                Polygon3 *poly = new Polygon3(face, obj->GetMesh());
671                                polys->push_back(poly);
672                                poly->AddPiercingRay(ray);
673
674                                facePolyMap[face] = poly;
675                        }
676                }
677        }
678       
679        Polygon3::IncludeInBox(*polys, mBox);
680        mStat.polys = (int)polys->size();
681
682        Debug << "**** Finished polygon extraction ****" << endl;
683        Debug << (int)polys->size() << " polys extracted from " << (int)rays->size() << " rays" << endl;
684        Debug << "extraction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
685
686        Construct(polys, rays);
687}
688
689void BspTree::Construct(PolygonContainer *polys, RayContainer *rays)
690{
691        std::stack<BspTraversalData> tStack;
692
693        mRoot = new BspLeaf();
694
695        BspTraversalData tData(mRoot, polys, 0, mRootCell, rays);
696        tStack.push(tData);
697
698        long startTime = GetTime();
699        cout << "**** Contructing bsp tree ****\n";
700
701        while (!tStack.empty())
702        {
703                tData = tStack.top();
704            tStack.pop();
705
706                // subdivide leaf node
707                BspNode *subRoot = Subdivide(tStack, tData);
708        }
709
710        cout << "**** Finished tree construction ****\n";
711        Debug << "BSP tree contruction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
712}
713
714
715BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
716{
717        //-- terminate traversal 
718        if (((int)tData.mPolygons->size() <= sTermMaxPolygons) ||
719                ((int)tData.mRays->size() <= sTermMaxRays) ||
720                (tData.mDepth >= sTermMaxDepth))
721               
722        {
723                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
724       
725                // generate new view cell for each leaf
726                if (mGenerateViewCells)
727                        mStat.contributingSamples += leaf->GenerateViewCell(*tData.mRays);
728                else
729                        // add view cell to leaf
730                        leaf->SetViewCell(tData.mViewCell);
731               
732                EvaluateLeafStats(tData);
733
734                //-- clean up
735                // remaining polygons are discarded or added to node
736                leaf->ProcessPolygons(tData.mPolygons, sStoreSplitPolys);
737                DEL_PTR(tData.mPolygons);
738                DEL_PTR(tData.mRays);
739
740                return leaf;
741        }
742
743        //-- continue subdivision
744
745        PolygonContainer coincident;
746       
747        PolygonContainer *frontPolys = new PolygonContainer();
748        PolygonContainer *backPolys = new PolygonContainer();
749
750        RayContainer *frontRays = new RayContainer();
751        RayContainer *backRays = new RayContainer();
752       
753        // create new interior node and two leaf nodes
754        BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
755                                                                                  *tData.mPolygons,
756                                                                                  *frontPolys,
757                                                                                  *backPolys,
758                                                                                  coincident,
759                                                                                  *tData.mRays,
760                                                                                  *frontRays,
761                                                                                  *backRays);
762        ViewCell *frontViewCell = mRootCell;
763        ViewCell *backViewCell = mRootCell;
764
765#ifdef _DEBUG   
766        if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
767        {       for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
768                        Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ;
769                Debug << endl;}
770#endif
771
772        // extract view cells from coincident polygons according to plane normal
773    // only if front or back polygons are empty
774        if (!mGenerateViewCells)
775        {
776                ExtractViewCells(&backViewCell,
777                                                 &frontViewCell,
778                                                 coincident,
779                                                 interior->mPlane,
780                                                 backPolys->empty(),
781                                                 frontPolys->empty());
782        }
783       
784        // don't need coincident polygons anymore
785        interior->ProcessPolygons(&coincident, sStoreSplitPolys);
786
787        // push the children on the stack
788        tStack.push(BspTraversalData(interior->GetBack(),
789                                                                 backPolys,
790                                                                 tData.mDepth + 1,
791                                                                 backViewCell,
792                                                                 backRays));
793
794        tStack.push(BspTraversalData(interior->GetFront(),
795                                                                 frontPolys,
796                                                                 tData.mDepth + 1,
797                                                                 frontViewCell,
798                                                                 frontRays));
799
800        // cleanup
801        DEL_PTR(tData.mNode);
802        DEL_PTR(tData.mPolygons);
803        DEL_PTR(tData.mRays);
804
805        return interior;
806}
807
808void BspTree::ExtractViewCells(ViewCell **backViewCell,
809                                                           ViewCell **frontViewCell,
810                                                           const PolygonContainer &coincident,
811                                                           const Plane3 splitPlane,
812                                                           const bool extractBack,
813                                                           const bool extractFront) const
814{
815        bool foundFront = !extractFront, foundBack = !extractBack;
816
817        PolygonContainer::const_iterator it =
818                coincident.begin(), it_end = coincident.end();
819
820        //-- find first view cells in front and back leafs
821        for (; !(foundFront && foundBack) && (it != it_end); ++ it)
822        {
823                if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
824                {
825                        *backViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
826                        foundBack = true;
827                }
828                else
829                {
830                        *frontViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
831                        foundFront = true;
832                }
833        }
834        //if (extractFront && foundFront)       Debug << "front view cell: " << *frontViewCell << endl;
835        //if (extractBack && foundBack) Debug << "back view cell: " << *backViewCell << endl;
836}
837
838BspInterior *BspTree::SubdivideNode(BspLeaf *leaf,
839                                                                        PolygonContainer &polys,
840                                                                        PolygonContainer &frontPolys,
841                                                                        PolygonContainer &backPolys,
842                                                                        PolygonContainer &coincident,
843                                                                        RayContainer &rays,
844                                                                        RayContainer &backRays,
845                                                                        RayContainer &frontRays)
846{
847        mStat.nodes += 2;
848       
849        // select subdivision plane
850        BspInterior *interior =
851                new BspInterior(SelectPlane(leaf, polys, rays));
852
853#ifdef _DEBUG
854        Debug << interior << endl;
855#endif
856       
857        // partition rays
858        interior->SplitRays(rays, frontRays, backRays);
859       
860        // split polygons with split plane
861        mStat.splits +=interior->SplitPolygons(polys,
862                                                                               frontPolys,
863                                                                       backPolys,
864                                                                       coincident,
865                                                                       sStoreSplitPolys);
866
867        BspInterior *parent = leaf->GetParent();
868
869        // replace a link from node's parent
870        if (!leaf->IsRoot())
871        {
872                parent->ReplaceChildLink(leaf, interior);
873                interior->SetParent(parent);
874        }
875        else // new root
876        {
877                mRoot = interior;
878        }
879
880        // and setup child links
881        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
882       
883        return interior;
884}
885
886void BspTree::SortSplitCandidates(const PolygonContainer &polys,
887                                                                  const int axis,
888                                                                  vector<SortableEntry> &splitCandidates) const
889{
890  splitCandidates.clear();
891 
892  int requestedSize = 2 * (int)polys.size();
893  // creates a sorted split candidates array 
894  splitCandidates.reserve(requestedSize);
895 
896  PolygonContainer::const_iterator it, it_end = polys.end();
897
898  AxisAlignedBox3 box;
899
900  // insert all queries
901  for(it = polys.begin(); it != it_end; ++ it)
902  {
903          box.Initialize();
904          box.Include(*(*it));
905         
906          splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
907      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
908  }
909 
910  stable_sort(splitCandidates.begin(), splitCandidates.end());
911}
912
913
914float BspTree::BestCostRatio(const PolygonContainer &polys,
915                                                         const AxisAlignedBox3 &box,
916                                                         const int axis,
917                                                         float &position,
918                                                         int &objectsBack,
919                                                         int &objectsFront) const
920{
921        vector<SortableEntry> splitCandidates;
922
923        SortSplitCandidates(polys, axis, splitCandidates);
924       
925        // go through the lists, count the number of objects left and right
926        // and evaluate the following cost funcion:
927        // C = ct_div_ci  + (ol + or)/queries
928       
929        int objectsLeft = 0, objectsRight = (int)polys.size();
930       
931        float minBox = box.Min(axis);
932        float maxBox = box.Max(axis);
933        float boxArea = box.SurfaceArea();
934 
935        float minBand = minBox + sSplitBorder * (maxBox - minBox);
936        float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
937       
938        float minSum = 1e20f;
939        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
940
941        for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
942        {
943                switch ((*ci).type)
944                {
945                        case SortableEntry::POLY_MIN:
946                                ++ objectsLeft;
947                                break;
948                        case SortableEntry::POLY_MAX:
949                            -- objectsRight;
950                                break;
951                        default:
952                                break;
953                }
954               
955                if ((*ci).value > minBand && (*ci).value < maxBand)
956                {
957                        AxisAlignedBox3 lbox = box;
958                        AxisAlignedBox3 rbox = box;
959                        lbox.SetMax(axis, (*ci).value);
960                        rbox.SetMin(axis, (*ci).value);
961
962                        float sum = objectsLeft * lbox.SurfaceArea() +
963                                                objectsRight * rbox.SurfaceArea();
964     
965                        if (sum < minSum)
966                        {
967                                minSum = sum;
968                                position = (*ci).value;
969
970                                objectsBack = objectsLeft;
971                                objectsFront = objectsRight;
972                        }
973                }
974        }
975 
976        float oldCost = (float)polys.size();
977        float newCost = sCt_div_ci + minSum / boxArea;
978        float ratio = newCost / oldCost;
979
980
981#if 0
982  Debug << "====================" << endl;
983  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
984      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
985#endif
986  return ratio;
987}
988
989Plane3 BspTree::SelectPlane(BspLeaf *leaf,
990                                                        PolygonContainer &polys,
991                                                        const RayContainer &rays)
992{
993        if (polys.size() == 0)
994        {
995                Debug << "Warning: No split candidate available\n";
996                return Plane3();
997        }
998
999        if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
1000                ((int)polys.size() > sTermMaxPolysForAxisAligned))
1001        {
1002                AxisAlignedBox3 box;
1003                box.Initialize();
1004       
1005                // todo: area subdivision
1006                Polygon3::IncludeInBox(polys, box);
1007       
1008                int objectsBack = 0, objectsFront = 0;
1009                int axis = 0;
1010                float costRatio = MAX_FLOAT;
1011                Vector3 position;
1012
1013                for (int i = 0; i < 3; ++ i)
1014                {
1015                        float p = 0;
1016                        float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
1017                       
1018                        if (r < costRatio)
1019                        {
1020                                costRatio = r;
1021                                axis = i;
1022                                position = p;
1023                        }
1024                }
1025               
1026                if (costRatio < sMaxCostRatio)
1027                {
1028                        Vector3 norm(0,0,0); norm[axis] = 1.0f;
1029                        return Plane3(norm, position);
1030                }
1031        }
1032
1033        // simplest strategy: just take next polygon
1034        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1035        {
1036                return polys[Random((int)polys.size())]->GetSupportingPlane();
1037        }
1038
1039        // use heuristics to find appropriate plane
1040        return SelectPlaneHeuristics(polys, rays, sMaxCandidates);
1041}
1042
1043Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer &polys,
1044                                                                          const RayContainer &rays,
1045                                                                          const int maxTests)
1046{
1047        float lowestCost = MAX_FLOAT;
1048        int bestPlaneIdx = 0;
1049       
1050        int limit = maxTests > 0 ? Min((int)polys.size(), maxTests) : (int)polys.size();
1051       
1052        int candidateIdx = limit;
1053       
1054        for (int i = 0; i < limit; ++ i)
1055        {
1056                candidateIdx = GetNextCandidateIdx(candidateIdx, polys);
1057
1058                Plane3 candidatePlane = polys[candidateIdx]->GetSupportingPlane();
1059               
1060                // evaluate current candidate
1061                float candidateCost = SplitPlaneCost(polys, candidatePlane, rays);
1062                       
1063                if (candidateCost < lowestCost)
1064                {
1065                        bestPlaneIdx = candidateIdx;
1066                        lowestCost = candidateCost;
1067                }
1068        }
1069       
1070        //Debug << "Plane lowest cost: " << lowestCost << endl;
1071        return polys[bestPlaneIdx]->GetSupportingPlane();
1072}
1073
1074int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
1075{
1076        int candidateIdx = Random(currentIdx --);
1077
1078        // swap candidates to avoid testing same plane 2 times
1079        Polygon3 *p = polys[candidateIdx];
1080        polys[candidateIdx] = polys[currentIdx];
1081        polys[currentIdx] = p;
1082       
1083        return currentIdx;
1084        //return Random((int)polys.size());
1085}
1086
1087float BspTree::SplitPlaneCost(PolygonContainer &polys,
1088                                                          const Plane3 &candidatePlane,
1089                                                          const RayContainer &rays)
1090{
1091        float val = 0;
1092
1093        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1094        {
1095                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1096                // we put a penalty on the dot product between the "tiny" vertical axis
1097                // and the split plane axis
1098                val += sVerticalSplitsFactor *
1099                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1100        }
1101
1102        if (!((sSplitPlaneStrategy & BALANCED_POLYS)      ||
1103                  (sSplitPlaneStrategy & LEAST_SPLITS)        ||
1104                  (sSplitPlaneStrategy & LARGEST_POLY_AREA)   ||
1105                  (sSplitPlaneStrategy & BALANCED_VIEW_CELLS) ||
1106                  (sSplitPlaneStrategy & BLOCKED_RAYS)))
1107        {
1108                return val;
1109        }
1110
1111        // -- strategies where the effect of the split plane is tested
1112        // on all input polygons
1113
1114        float sumBalancedPolys = 0;
1115        float sumSplits = 0;
1116        float sumPolyArea = 0;
1117        float sumBalancedViewCells = 0;
1118        float sumBlockedRays = 0;
1119        float totalBlockedRays = 0;
1120        //float totalArea = 0;
1121
1122        // container for balanced view cells criterium
1123        ObjectContainer frontViewCells;
1124        ObjectContainer backViewCells;
1125
1126        PolygonContainer::const_iterator it, it_end = polys.end();
1127
1128        for (it = polys.begin(); it != it_end; ++ it)
1129        {
1130                int classification = (*it)->ClassifyPlane(candidatePlane);
1131
1132                if (sSplitPlaneStrategy & BALANCED_POLYS)
1133                        sumBalancedPolys += sBalancedPolysTable[classification];
1134               
1135                if (sSplitPlaneStrategy & LEAST_SPLITS)
1136                        sumSplits += sLeastSplitsTable[classification];
1137
1138                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1139                {
1140                        if (classification == Plane3::COINCIDENT)
1141                                sumPolyArea += (*it)->GetArea();
1142                        //totalArea += area;
1143                }
1144               
1145                if (sSplitPlaneStrategy & BLOCKED_RAYS)
1146                {
1147                        float blockedRays = (float)(*it)->GetPiercingRays()->size();
1148               
1149                        if (classification == Plane3::COINCIDENT)
1150                                sumBlockedRays += blockedRays;
1151                        Debug << "adding rays: " << blockedRays << endl;
1152
1153                        totalBlockedRays += blockedRays;
1154                }
1155
1156                // assign view cells to back or front according to classificaion
1157                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1158                {
1159                        MeshInstance *viewCell = (*it)->mParent;
1160               
1161                        if (classification == Plane3::FRONT_SIDE)
1162                                frontViewCells.push_back(viewCell);
1163                        else if (viewCell && (classification == Plane3::BACK_SIDE))
1164                                backViewCells.push_back(viewCell);
1165                }
1166        }
1167
1168        // all values should be approx. between 0 and 1 so they can be combined
1169        // and scaled with the factors according to their importance
1170        if (sSplitPlaneStrategy & BALANCED_POLYS)
1171                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
1172
1173        if (sSplitPlaneStrategy & LEAST_SPLITS)   
1174                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
1175
1176        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1177                // HACK: polys.size should be total area so scaling is between 0 and 1
1178                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1179
1180        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1181                if (totalBlockedRays > 0)
1182                        val += sBlockedRaysFactor * sumBlockedRays / totalBlockedRays;
1183
1184        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1185        {
1186                // count number of unique view cells
1187                sort(frontViewCells.begin(), frontViewCells.end());
1188                sort(backViewCells.begin(), backViewCells.end());
1189
1190                ObjectContainer::const_iterator frontIt, frontIt_end = frontViewCells.end();
1191       
1192                Intersectable *vc = NULL;
1193                // increase counter for view cells in front of plane
1194                for (frontIt = frontViewCells.begin(); frontIt != frontIt_end; ++frontIt)
1195                {
1196                        if (*frontIt != vc)
1197                        {
1198                                vc = *frontIt;
1199                                sumBalancedViewCells += 1.0f;
1200                        }
1201                }
1202
1203                ObjectContainer::const_iterator backIt, backIt_end = backViewCells.end();
1204                vc = NULL;
1205                // decrease counter for view cells on back side of plane
1206                for (backIt = backViewCells.begin(); backIt != backIt_end; ++backIt)
1207                {
1208                        if (*backIt != vc)
1209                        {
1210                                vc = *backIt;
1211                                sumBalancedViewCells -= 1.0f;
1212                        }
1213                }
1214
1215                val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1216                        (float)(frontViewCells.size() + backViewCells.size());
1217        }
1218
1219        float sumBalancedRays = 0;
1220        float sumRaySplits = 0;
1221
1222        RayContainer::const_iterator rit, rit_end = rays.end();
1223
1224        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1225        {
1226                if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1227                {
1228                }
1229
1230                if (sSplitPlaneStrategy & BALANCED_RAYS)
1231                {
1232                }
1233        }
1234        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1235                if (!rays.empty())
1236                        val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
1237
1238        if (sSplitPlaneStrategy & BALANCED_RAYS)
1239                if (!rays.empty())
1240                        val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
1241
1242        // return linear combination of the sums
1243        return val;
1244}
1245
1246void BspTree::ParseEnvironment()
1247{
1248        //-- parse bsp cell tree construction method
1249        char constructionMethodStr[60];
1250       
1251        environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
1252
1253        sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1254       
1255        if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1256                sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1257        else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1258                sConstructionMethod = FROM_SCENE_GEOMETRY;
1259        else if (strcmp(constructionMethodStr, "fromRays") == 0)
1260                sConstructionMethod = FROM_RAYS;
1261        else
1262        {
1263                cerr << "Wrong construction method " << constructionMethodStr << endl;
1264                exit(1);
1265    }
1266
1267        Debug << "Construction method: " << constructionMethodStr << endl;
1268
1269        //-- termination criteria for autopartition
1270        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1271        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1272        environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
1273
1274        //-- termination criteria for axis aligned split
1275        environment->GetFloatValue("BspTree.Termination.ct_div_ci", sCt_div_ci);
1276        environment->GetFloatValue("BspTree.Termination.maxCostRatio", sMaxCostRatio);
1277        environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned",
1278                                                         sTermMaxPolysForAxisAligned);
1279       
1280        //-- partition criteria
1281        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
1282        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1283        environment->GetFloatValue("BspTree.splitBorder", sSplitBorder);
1284       
1285        environment->GetBoolValue("BspTree.storeSplitPolys", sStoreSplitPolys);
1286
1287        environment->GetFloatValue("BspTree.Construction.sideTolerance", Polygon3::sSideTolerance);
1288        Polygon3::sSideToleranceSqrt = Polygon3::sSideTolerance * Polygon3::sSideTolerance;
1289
1290    Debug << "BSP max depth: " << sTermMaxDepth << endl;
1291        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1292        Debug << "BSP max candidates: " << sMaxCandidates << endl;
1293       
1294        Debug << "Split plane strategy: ";
1295        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1296                Debug << "random polygon ";
1297        if (sSplitPlaneStrategy & AXIS_ALIGNED)
1298                Debug << "axis aligned ";
1299        if (sSplitPlaneStrategy & LEAST_SPLITS)     
1300                Debug << "least splits ";
1301        if (sSplitPlaneStrategy & BALANCED_POLYS)
1302                Debug << "balanced polygons ";
1303        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1304                Debug << "balanced view cells ";
1305        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1306                Debug << "largest polygon area ";
1307        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1308                Debug << "vertical axis ";
1309        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1310                Debug << "blocked rays ";
1311
1312        Debug << endl;
1313}
1314
1315void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
1316{
1317        stack<BspNode *> nodeStack;
1318        nodeStack.push(mRoot);
1319 
1320        while (!nodeStack.empty())
1321        {
1322                BspNode *node = nodeStack.top();
1323   
1324                nodeStack.pop();
1325   
1326                if (node->IsLeaf())
1327                {
1328                        BspLeaf *leaf = (BspLeaf *)node;
1329                       
1330                        leaves.push_back(leaf);
1331                } else
1332                {
1333                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1334                        nodeStack.push(interior->GetBack());
1335                        nodeStack.push(interior->GetFront());
1336                }
1337        }
1338}
1339
1340AxisAlignedBox3 BspTree::GetBoundingBox() const
1341{
1342        return mBox;
1343}
1344
1345BspNode *BspTree::GetRoot() const
1346{
1347        return mRoot;
1348}
1349
1350void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1351{
1352        // the node became a leaf -> evaluate stats for leafs
1353        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1354
1355        if (data.mDepth >= sTermMaxDepth)
1356                ++ mStat.maxDepthNodes;
1357        // store maximal and minimal depth
1358        if (data.mDepth > mStat.maxDepth)
1359                mStat.maxDepth = data.mDepth;
1360        if (data.mDepth < mStat.minDepth)
1361                mStat.minDepth = data.mDepth;
1362
1363        // accumulate depth to compute average
1364        mStat.accumDepth += data.mDepth;
1365
1366        if (leaf->mViewCell != mRootCell)
1367        {       
1368                ++ mStat.viewCells;
1369                mStat.pvs += leaf->mViewCell->GetPvs().GetSize();
1370        }
1371       
1372//#ifdef _DEBUG
1373        Debug << "BSP stats: "
1374                  << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
1375                  << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
1376                  << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << ")" << endl;
1377//#endif
1378}
1379
1380int BspTree::CastRay(Ray &ray)
1381{
1382        int hits = 0;
1383 
1384        stack<BspRayTraversalData> tStack;
1385 
1386        float maxt = 1e6;
1387        float mint = 0;
1388       
1389        Intersectable::NewMail();
1390
1391        // test with tree bounding box
1392        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
1393                return 0;
1394
1395        if (mint < 0) // start ray from origin
1396                mint = 0;
1397
1398        // bound ray
1399        if ((ray.GetType() == Ray::LOCAL_RAY) &&
1400                (!ray.intersections.empty())      &&
1401            (ray.intersections[0].mT <= maxt))
1402        {
1403                maxt = ray.intersections[0].mT;
1404    }
1405 
1406        Vector3 entp = ray.Extrap(mint);
1407        Vector3 extp = ray.Extrap(maxt);
1408 
1409        BspNode *node = mRoot;
1410        BspNode *farChild = NULL;
1411       
1412        while (1)
1413        {
1414                if (!node->IsLeaf())
1415                {
1416                        BspInterior *in = (BspInterior *) node;
1417                       
1418                        Plane3 *splitPlane = in->GetPlane();
1419
1420                        float t = 0;
1421                        bool coplanar = false;
1422               
1423                        int entSide = splitPlane->Side(entp);
1424                        int extSide = splitPlane->Side(extp);
1425
1426                        Vector3 intersection;
1427
1428                        if (entSide < 0)
1429                        {
1430                                node = in->GetBack();
1431
1432                                if(extSide <= 0) // plane does not split ray => no far child
1433                                        continue;
1434                                       
1435                                farChild = in->GetFront(); // plane splits ray
1436
1437                        } else if (entSide > 0)
1438                        {
1439                                node = in->GetFront();
1440
1441                                if (extSide >= 0) // plane does not split ray => no far child
1442                                        continue;
1443
1444                                farChild = in->GetBack(); // plane splits ray                   
1445                        }
1446                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
1447                        {
1448                                node = in->GetFront();
1449                                continue;
1450                        }
1451
1452                        // push data for far child
1453                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1454
1455                        // find intersection of ray segment with plane
1456                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
1457                       
1458                } else // reached leaf => intersection with view cell
1459                {
1460                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1461     
1462                        if (!leaf->mViewCell->Mailed())
1463                        {
1464                                ray.viewCells.push_back(leaf->mViewCell);
1465                                leaf->mViewCell->Mail();
1466                                ++ hits;
1467                        }
1468                       
1469                        //-- fetch the next far child from the stack
1470                        if (tStack.empty())
1471                                break;
1472     
1473                        entp = extp;
1474                        mint = maxt; // NOTE: need this?
1475                        BspRayTraversalData &s = tStack.top();
1476
1477                        node = s.mNode;
1478                        extp = s.mExitPoint;
1479                        maxt = s.mMaxT;
1480
1481                        //Debug << "leaf: new entrypt: " << entp << " new extp: " << extp << endl;
1482
1483                        tStack.pop();
1484                }
1485        }
1486
1487        return hits;
1488}
1489
1490bool BspTree::Export(const string filename)
1491{
1492        Exporter *exporter = Exporter::GetExporter(filename);
1493
1494        if (exporter)
1495        {
1496                exporter->ExportBspTree(*this);
1497                return true;
1498        }       
1499
1500        return false;
1501}
1502
1503void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1504{
1505        stack<BspNode *> nodeStack;
1506        nodeStack.push(mRoot);
1507
1508        ViewCell::NewMail();
1509
1510        while (!nodeStack.empty())
1511        {
1512                BspNode *node = nodeStack.top();
1513                nodeStack.pop();
1514
1515                if (node->IsLeaf())
1516                {
1517                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1518
1519                        if (!viewCell->Mailed())
1520                        {
1521                                viewCell->Mail();
1522                                viewCells.push_back(viewCell);
1523                        }
1524                }
1525                else
1526                {
1527                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1528
1529                        nodeStack.push(interior->mFront);
1530                        nodeStack.push(interior->mBack);
1531                }
1532        }
1533}
1534
1535void BspTree::SetGenerateViewCells(int generateViewCells)
1536{
1537        mGenerateViewCells = generateViewCells;
1538}
1539
1540BspTreeStatistics &BspTree::GetStat()
1541{
1542        return mStat;
1543}
Note: See TracBrowser for help on using the repository browser.