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

Revision 335, 37.3 KB checked in by mattausch, 19 years ago (diff)

reprogrammed splitplane evaluation. updated default.env
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(candidatePlane, polys, 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(const Plane3 &candidatePlane,
1088                                                          const PolygonContainer &polys) const
1089{
1090        float val = 0;
1091
1092        float sumBalancedPolys = 0;
1093        float sumSplits = 0;
1094        float sumPolyArea = 0;
1095        float sumBalancedViewCells = 0;
1096        float sumBlockedRays = 0;
1097        float totalBlockedRays = 0;
1098        //float totalArea = 0;
1099        int totalViewCells = 0;
1100
1101        ViewCell::NewMail();
1102       
1103        PolygonContainer::const_iterator it, it_end = polys.end();
1104
1105        for (it = polys.begin(); it != it_end; ++ it)
1106        {
1107                int classification = (*it)->ClassifyPlane(candidatePlane);
1108
1109                if (sSplitPlaneStrategy & BALANCED_POLYS)
1110                        sumBalancedPolys += sBalancedPolysTable[classification];
1111               
1112                if (sSplitPlaneStrategy & LEAST_SPLITS)
1113                        sumSplits += sLeastSplitsTable[classification];
1114
1115                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1116                {
1117                        if (classification == Plane3::COINCIDENT)
1118                                sumPolyArea += (*it)->GetArea();
1119                        //totalArea += area;
1120                }
1121               
1122                if (sSplitPlaneStrategy & BLOCKED_RAYS)
1123                {
1124                        float blockedRays = (float)(*it)->GetPiercingRays()->size();
1125               
1126                        if (classification == Plane3::COINCIDENT)
1127                                sumBlockedRays += blockedRays;
1128                        Debug << "adding rays: " << blockedRays << endl;
1129
1130                        totalBlockedRays += blockedRays;
1131                }
1132
1133                // assign view cells to back or front according to classificaion
1134                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1135                {
1136                        MeshInstance *viewCell = (*it)->mParent;
1137               
1138                        if (!viewCell->Mailed())
1139                        {
1140                                viewCell->Mail();
1141
1142                                if (classification == Plane3::FRONT_SIDE)
1143                                        sumBalancedViewCells += 1.0f;
1144                                else if (viewCell && (classification == Plane3::BACK_SIDE))
1145                                        sumBalancedViewCells -= 1.0f;
1146                                ++ totalViewCells;
1147                        }
1148                }
1149        }
1150
1151        // all values should be approx. between 0 and 1 so they can be combined
1152        // and scaled with the factors according to their importance
1153        if (sSplitPlaneStrategy & BALANCED_POLYS)
1154                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
1155
1156        if (sSplitPlaneStrategy & LEAST_SPLITS)   
1157                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
1158
1159        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1160                // HACK: polys.size should be total area so scaling is between 0 and 1
1161                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1162
1163        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1164                if (totalBlockedRays != 0)
1165                        val += sBlockedRaysFactor * sumBlockedRays / totalBlockedRays;
1166
1167        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1168                if (totalViewCells != 0)
1169                        val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1170                                (float)totalViewCells;
1171       
1172        return val;
1173}
1174
1175float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1176                                                          const RayContainer &rays) const
1177{
1178        float val = 0;
1179
1180        float sumBalancedRays = 0;
1181        float sumRaySplits = 0;
1182
1183        RayContainer::const_iterator rit, rit_end = rays.end();
1184
1185        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1186        {
1187                if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1188                {
1189                }
1190
1191                if (sSplitPlaneStrategy & BALANCED_RAYS)
1192                {
1193                }
1194        }
1195
1196        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1197                if (!rays.empty())
1198                        val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
1199
1200        if (sSplitPlaneStrategy & BALANCED_RAYS)
1201                if (!rays.empty())
1202                        val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
1203
1204        return val;
1205}
1206
1207float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1208                                                          const PolygonContainer &polys,                                                         
1209                                                          const RayContainer &rays) const
1210{
1211        float val = 0;
1212
1213        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1214        {
1215                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1216                // we put a penalty on the dot product between the "tiny" vertical axis
1217                // and the split plane axis
1218                val += sVerticalSplitsFactor *
1219                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1220        }
1221
1222        if ((sSplitPlaneStrategy & BALANCED_POLYS)      ||
1223                (sSplitPlaneStrategy & LEAST_SPLITS)        ||
1224                (sSplitPlaneStrategy & LARGEST_POLY_AREA)   ||
1225                (sSplitPlaneStrategy & BALANCED_VIEW_CELLS) ||
1226                (sSplitPlaneStrategy & BLOCKED_RAYS))
1227        {
1228        val += SplitPlaneCost(candidatePlane, polys);
1229        }
1230
1231        if ((sSplitPlaneStrategy & BALANCED_RAYS)      ||
1232                (sSplitPlaneStrategy & LEAST_RAY_SPLITS))
1233        {
1234                val += SplitPlaneCost(candidatePlane, rays);
1235        }
1236
1237        // return linear combination of the sums
1238        return val;
1239}
1240
1241void BspTree::ParseEnvironment()
1242{
1243        //-- parse bsp cell tree construction method
1244        char constructionMethodStr[60];
1245       
1246        environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
1247
1248        sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1249       
1250        if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1251                sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1252        else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1253                sConstructionMethod = FROM_SCENE_GEOMETRY;
1254        else if (strcmp(constructionMethodStr, "fromRays") == 0)
1255                sConstructionMethod = FROM_RAYS;
1256        else
1257        {
1258                cerr << "Wrong construction method " << constructionMethodStr << endl;
1259                exit(1);
1260    }
1261
1262        Debug << "Construction method: " << constructionMethodStr << endl;
1263
1264        //-- termination criteria for autopartition
1265        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1266        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1267        environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
1268
1269        //-- termination criteria for axis aligned split
1270        environment->GetFloatValue("BspTree.Termination.ct_div_ci", sCt_div_ci);
1271        environment->GetFloatValue("BspTree.Termination.maxCostRatio", sMaxCostRatio);
1272        environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned",
1273                                                         sTermMaxPolysForAxisAligned);
1274       
1275        //-- partition criteria
1276        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
1277        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1278        environment->GetFloatValue("BspTree.splitBorder", sSplitBorder);
1279       
1280        environment->GetBoolValue("BspTree.storeSplitPolys", sStoreSplitPolys);
1281
1282        environment->GetFloatValue("BspTree.Construction.sideTolerance", Polygon3::sSideTolerance);
1283        Polygon3::sSideToleranceSqrt = Polygon3::sSideTolerance * Polygon3::sSideTolerance;
1284
1285    Debug << "BSP max depth: " << sTermMaxDepth << endl;
1286        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1287        Debug << "BSP max candidates: " << sMaxCandidates << endl;
1288       
1289        Debug << "Split plane strategy: ";
1290        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1291                Debug << "random polygon ";
1292        if (sSplitPlaneStrategy & AXIS_ALIGNED)
1293                Debug << "axis aligned ";
1294        if (sSplitPlaneStrategy & LEAST_SPLITS)     
1295                Debug << "least splits ";
1296        if (sSplitPlaneStrategy & BALANCED_POLYS)
1297                Debug << "balanced polygons ";
1298        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1299                Debug << "balanced view cells ";
1300        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1301                Debug << "largest polygon area ";
1302        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1303                Debug << "vertical axis ";
1304        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1305                Debug << "blocked rays ";
1306
1307        Debug << endl;
1308}
1309
1310void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
1311{
1312        stack<BspNode *> nodeStack;
1313        nodeStack.push(mRoot);
1314 
1315        while (!nodeStack.empty())
1316        {
1317                BspNode *node = nodeStack.top();
1318   
1319                nodeStack.pop();
1320   
1321                if (node->IsLeaf())
1322                {
1323                        BspLeaf *leaf = (BspLeaf *)node;
1324                       
1325                        leaves.push_back(leaf);
1326                } else
1327                {
1328                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1329                        nodeStack.push(interior->GetBack());
1330                        nodeStack.push(interior->GetFront());
1331                }
1332        }
1333}
1334
1335AxisAlignedBox3 BspTree::GetBoundingBox() const
1336{
1337        return mBox;
1338}
1339
1340BspNode *BspTree::GetRoot() const
1341{
1342        return mRoot;
1343}
1344
1345void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1346{
1347        // the node became a leaf -> evaluate stats for leafs
1348        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1349
1350        if (data.mDepth >= sTermMaxDepth)
1351                ++ mStat.maxDepthNodes;
1352        // store maximal and minimal depth
1353        if (data.mDepth > mStat.maxDepth)
1354                mStat.maxDepth = data.mDepth;
1355        if (data.mDepth < mStat.minDepth)
1356                mStat.minDepth = data.mDepth;
1357
1358        // accumulate depth to compute average
1359        mStat.accumDepth += data.mDepth;
1360
1361        if (leaf->mViewCell != mRootCell)
1362        {       
1363                ++ mStat.viewCells;
1364                mStat.pvs += leaf->mViewCell->GetPvs().GetSize();
1365        }
1366       
1367#ifdef _DEBUG
1368        Debug << "BSP stats: "
1369                  << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
1370                  << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
1371                  << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << ")" << endl;
1372#endif
1373}
1374
1375int BspTree::CastRay(Ray &ray)
1376{
1377        int hits = 0;
1378 
1379        stack<BspRayTraversalData> tStack;
1380 
1381        float maxt = 1e6;
1382        float mint = 0;
1383       
1384        Intersectable::NewMail();
1385
1386        // test with tree bounding box
1387        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
1388                return 0;
1389
1390        if (mint < 0) // start ray from origin
1391                mint = 0;
1392
1393        // bound ray
1394        if ((ray.GetType() == Ray::LOCAL_RAY) &&
1395                (!ray.intersections.empty())      &&
1396            (ray.intersections[0].mT <= maxt))
1397        {
1398                maxt = ray.intersections[0].mT;
1399    }
1400 
1401        Vector3 entp = ray.Extrap(mint);
1402        Vector3 extp = ray.Extrap(maxt);
1403 
1404        BspNode *node = mRoot;
1405        BspNode *farChild = NULL;
1406       
1407        while (1)
1408        {
1409                if (!node->IsLeaf())
1410                {
1411                        BspInterior *in = (BspInterior *) node;
1412                       
1413                        Plane3 *splitPlane = in->GetPlane();
1414
1415                        float t = 0;
1416                        bool coplanar = false;
1417               
1418                        int entSide = splitPlane->Side(entp);
1419                        int extSide = splitPlane->Side(extp);
1420
1421                        Vector3 intersection;
1422
1423                        if (entSide < 0)
1424                        {
1425                                node = in->GetBack();
1426
1427                                if(extSide <= 0) // plane does not split ray => no far child
1428                                        continue;
1429                                       
1430                                farChild = in->GetFront(); // plane splits ray
1431
1432                        } else if (entSide > 0)
1433                        {
1434                                node = in->GetFront();
1435
1436                                if (extSide >= 0) // plane does not split ray => no far child
1437                                        continue;
1438
1439                                farChild = in->GetBack(); // plane splits ray                   
1440                        }
1441                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
1442                        {
1443                                node = in->GetFront();
1444                                continue;
1445                        }
1446
1447                        // push data for far child
1448                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1449
1450                        // find intersection of ray segment with plane
1451                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
1452                       
1453                } else // reached leaf => intersection with view cell
1454                {
1455                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1456     
1457                        if (!leaf->mViewCell->Mailed())
1458                        {
1459                                ray.viewCells.push_back(leaf->mViewCell);
1460                                leaf->mViewCell->Mail();
1461                                ++ hits;
1462                        }
1463                       
1464                        //-- fetch the next far child from the stack
1465                        if (tStack.empty())
1466                                break;
1467     
1468                        entp = extp;
1469                        mint = maxt; // NOTE: need this?
1470                        BspRayTraversalData &s = tStack.top();
1471
1472                        node = s.mNode;
1473                        extp = s.mExitPoint;
1474                        maxt = s.mMaxT;
1475
1476                        //Debug << "leaf: new entrypt: " << entp << " new extp: " << extp << endl;
1477
1478                        tStack.pop();
1479                }
1480        }
1481
1482        return hits;
1483}
1484
1485bool BspTree::Export(const string filename)
1486{
1487        Exporter *exporter = Exporter::GetExporter(filename);
1488
1489        if (exporter)
1490        {
1491                exporter->ExportBspTree(*this);
1492                return true;
1493        }       
1494
1495        return false;
1496}
1497
1498void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1499{
1500        stack<BspNode *> nodeStack;
1501        nodeStack.push(mRoot);
1502
1503        ViewCell::NewMail();
1504
1505        while (!nodeStack.empty())
1506        {
1507                BspNode *node = nodeStack.top();
1508                nodeStack.pop();
1509
1510                if (node->IsLeaf())
1511                {
1512                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1513
1514                        if (!viewCell->Mailed())
1515                        {
1516                                viewCell->Mail();
1517                                viewCells.push_back(viewCell);
1518                        }
1519                }
1520                else
1521                {
1522                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1523
1524                        nodeStack.push(interior->mFront);
1525                        nodeStack.push(interior->mBack);
1526                }
1527        }
1528}
1529
1530void BspTree::SetGenerateViewCells(int generateViewCells)
1531{
1532        mGenerateViewCells = generateViewCells;
1533}
1534
1535BspTreeStatistics &BspTree::GetStat()
1536{
1537        return mStat;
1538}
Note: See TracBrowser for help on using the repository browser.