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

Revision 342, 40.8 KB checked in by mattausch, 19 years ago (diff)
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 minimum number splits in the tree.
44*/
45float BspTree::sLeastSplitsTable[] = {0, 0, 1, 0};
46/** Evaluates split plane classification with respect to the plane's
47        contribution for a balanced tree.
48*/
49float BspTree::sBalancedTreeTable[] = {-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        // needed for balanced view cells criterium
1102        ViewCell::NewMail();
1103        int backId = ViewCell::sMailId;
1104        ViewCell::NewMail();
1105        int frontId = ViewCell::sMailId;
1106        ViewCell::NewMail();
1107        int frontAndBackId = ViewCell::sMailId;
1108
1109        PolygonContainer::const_iterator it, it_end = polys.end();
1110
1111        for (it = polys.begin(); it != it_end; ++ it)
1112        {
1113                int classification = (*it)->ClassifyPlane(candidatePlane);
1114
1115                if (sSplitPlaneStrategy & BALANCED_POLYS)
1116                        sumBalancedPolys += sBalancedTreeTable[classification];
1117               
1118                if (sSplitPlaneStrategy & LEAST_SPLITS)
1119                        sumSplits += sLeastSplitsTable[classification];
1120
1121                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1122                {
1123                        if (classification == Plane3::COINCIDENT)
1124                                sumPolyArea += (*it)->GetArea();
1125                        //totalArea += area;
1126                }
1127               
1128                if (sSplitPlaneStrategy & BLOCKED_RAYS)
1129                {
1130                        float blockedRays = (float)(*it)->GetPiercingRays()->size();
1131               
1132                        if (classification == Plane3::COINCIDENT)
1133                                sumBlockedRays += blockedRays;
1134                       
1135                        totalBlockedRays += blockedRays;
1136                }
1137
1138                // assign view cells to back or front according to classificaion
1139                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1140                {
1141                        MeshInstance *viewCell = (*it)->mParent;
1142               
1143                        // assure that we only count a view cell
1144                        // once for the front and once for the back side of the plane
1145                        if (classification == Plane3::FRONT_SIDE)
1146                        {
1147                                if ((viewCell->mMailbox != frontId) &&
1148                                        (viewCell->mMailbox != frontAndBackId))
1149                                {
1150                                        sumBalancedViewCells += 1.0;
1151
1152                                        if (viewCell->mMailbox != backId)
1153                                                viewCell->mMailbox = frontId;
1154                                        else
1155                                                viewCell->mMailbox = frontAndBackId;
1156                                       
1157                                        ++ totalViewCells;
1158                                }
1159                        }
1160                        else if (classification == Plane3::BACK_SIDE)
1161                        {
1162                                if ((viewCell->mMailbox != backId) &&
1163                                    (viewCell->mMailbox != frontAndBackId))
1164                                {
1165                                        sumBalancedViewCells -= 1.0;
1166
1167                                        if (viewCell->mMailbox != frontId)
1168                                                viewCell->mMailbox = backId;
1169                                        else
1170                                                viewCell->mMailbox = frontAndBackId;
1171
1172                                        ++ totalViewCells;
1173                                }
1174                        }
1175                }
1176        }
1177
1178        // all values should be approx. between 0 and 1 so they can be combined
1179        // and scaled with the factors according to their importance
1180        if (sSplitPlaneStrategy & BALANCED_POLYS)
1181                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
1182
1183        if (sSplitPlaneStrategy & LEAST_SPLITS)   
1184                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
1185
1186        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1187                // HACK: polys.size should be total area so scaling is between 0 and 1
1188                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1189
1190        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1191                if (totalBlockedRays != 0)
1192                        val += sBlockedRaysFactor * sumBlockedRays / totalBlockedRays;
1193
1194        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1195                if (totalViewCells != 0)
1196                        val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1197                                (float)totalViewCells;
1198       
1199        return val;
1200}
1201
1202float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1203                                                          const RayContainer &rays) const
1204{
1205        float val = 0;
1206
1207        float sumBalancedRays = 0;
1208        float sumRaySplits = 0;
1209
1210        RayContainer::const_iterator rit, rit_end = rays.end();
1211
1212        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1213        {
1214                Ray *ray = *rit;
1215
1216                float maxT = 1e6;
1217                float minT = 0;
1218       
1219                // test with tree bounding box
1220                /*if (!mBox.GetMinMaxT(*ray, &minT, &maxT))
1221                        continue;
1222                if (minT < 0) // start ray from origin
1223                        minT = 0;*/
1224
1225                // bound ray
1226                if ((ray->GetType() == Ray::LOCAL_RAY) &&
1227                        (!ray->intersections.empty())      &&
1228                        (ray->intersections[0].mT <= maxT))
1229                {
1230                        maxT = ray->intersections[0].mT;
1231                }
1232
1233                int classification = ray->ClassifyPlane(candidatePlane, minT, maxT);
1234
1235                if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1236                {
1237                        sumBalancedRays += sBalancedTreeTable[classification];
1238                }
1239               
1240                if (sSplitPlaneStrategy & BALANCED_RAYS)
1241                {
1242                        sumRaySplits += sLeastSplitsTable[classification];
1243                }
1244        }
1245
1246        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1247                if (!rays.empty())
1248                        val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
1249
1250        if (sSplitPlaneStrategy & BALANCED_RAYS)
1251                if (!rays.empty())
1252                        val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
1253
1254        return val;
1255}
1256
1257float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1258                                                          const PolygonContainer &polys,                                                         
1259                                                          const RayContainer &rays) const
1260{
1261        float val = 0;
1262
1263        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1264        {
1265                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1266                // we put a penalty on the dot product between the "tiny" vertical axis
1267                // and the split plane axis
1268                val += sVerticalSplitsFactor *
1269                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1270        }
1271
1272        // the following criteria loop over all polygons to find the cost value
1273        if ((sSplitPlaneStrategy & BALANCED_POLYS)      ||
1274                (sSplitPlaneStrategy & LEAST_SPLITS)        ||
1275                (sSplitPlaneStrategy & LARGEST_POLY_AREA)   ||
1276                (sSplitPlaneStrategy & BALANCED_VIEW_CELLS) ||
1277                (sSplitPlaneStrategy & BLOCKED_RAYS))
1278        {
1279        val += SplitPlaneCost(candidatePlane, polys);
1280        }
1281
1282        // the following criteria loop over all rays to find the cost value
1283        if ((sSplitPlaneStrategy & BALANCED_RAYS)      ||
1284                (sSplitPlaneStrategy & LEAST_RAY_SPLITS))
1285        {
1286                val += SplitPlaneCost(candidatePlane, rays);
1287        }
1288
1289        // return linear combination of the sums
1290        return val;
1291}
1292
1293void BspTree::ParseEnvironment()
1294{
1295        //-- parse bsp cell tree construction method
1296        char constructionMethodStr[60];
1297       
1298        environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
1299
1300        sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1301       
1302        if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1303                sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1304        else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1305                sConstructionMethod = FROM_SCENE_GEOMETRY;
1306        else if (strcmp(constructionMethodStr, "fromRays") == 0)
1307                sConstructionMethod = FROM_RAYS;
1308        else
1309        {
1310                cerr << "Wrong construction method " << constructionMethodStr << endl;
1311                exit(1);
1312    }
1313
1314        Debug << "Construction method: " << constructionMethodStr << endl;
1315
1316        //-- termination criteria for autopartition
1317        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1318        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1319        environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
1320
1321        //-- termination criteria for axis aligned split
1322        environment->GetFloatValue("BspTree.Termination.ct_div_ci", sCt_div_ci);
1323        environment->GetFloatValue("BspTree.Termination.maxCostRatio", sMaxCostRatio);
1324        environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned",
1325                                                         sTermMaxPolysForAxisAligned);
1326       
1327        //-- partition criteria
1328        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
1329        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1330        environment->GetFloatValue("BspTree.splitBorder", sSplitBorder);
1331       
1332        environment->GetBoolValue("BspTree.storeSplitPolys", sStoreSplitPolys);
1333
1334        environment->GetFloatValue("BspTree.Construction.sideTolerance", Polygon3::sSideTolerance);
1335        Polygon3::sSideToleranceSqrt = Polygon3::sSideTolerance * Polygon3::sSideTolerance;
1336
1337    Debug << "BSP max depth: " << sTermMaxDepth << endl;
1338        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1339        Debug << "BSP max candidates: " << sMaxCandidates << endl;
1340       
1341        Debug << "Split plane strategy: ";
1342        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1343                Debug << "random polygon ";
1344        if (sSplitPlaneStrategy & AXIS_ALIGNED)
1345                Debug << "axis aligned ";
1346        if (sSplitPlaneStrategy & LEAST_SPLITS)     
1347                Debug << "least splits ";
1348        if (sSplitPlaneStrategy & BALANCED_POLYS)
1349                Debug << "balanced polygons ";
1350        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1351                Debug << "balanced view cells ";
1352        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1353                Debug << "largest polygon area ";
1354        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1355                Debug << "vertical axis ";
1356        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1357                Debug << "blocked rays ";
1358
1359        Debug << endl;
1360}
1361
1362void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
1363{
1364        stack<BspNode *> nodeStack;
1365        nodeStack.push(mRoot);
1366 
1367        while (!nodeStack.empty())
1368        {
1369                BspNode *node = nodeStack.top();
1370   
1371                nodeStack.pop();
1372   
1373                if (node->IsLeaf())
1374                {
1375                        BspLeaf *leaf = (BspLeaf *)node;
1376                       
1377                        leaves.push_back(leaf);
1378                } else
1379                {
1380                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1381                        nodeStack.push(interior->GetBack());
1382                        nodeStack.push(interior->GetFront());
1383                }
1384        }
1385}
1386
1387AxisAlignedBox3 BspTree::GetBoundingBox() const
1388{
1389        return mBox;
1390}
1391
1392BspNode *BspTree::GetRoot() const
1393{
1394        return mRoot;
1395}
1396
1397void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1398{
1399        // the node became a leaf -> evaluate stats for leafs
1400        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1401
1402        if (data.mDepth >= sTermMaxDepth)
1403                ++ mStat.maxDepthNodes;
1404        // store maximal and minimal depth
1405        if (data.mDepth > mStat.maxDepth)
1406                mStat.maxDepth = data.mDepth;
1407        if (data.mDepth < mStat.minDepth)
1408                mStat.minDepth = data.mDepth;
1409
1410        // accumulate depth to compute average
1411        mStat.accumDepth += data.mDepth;
1412
1413        if (leaf->mViewCell != mRootCell)
1414        {       
1415                ++ mStat.viewCells;
1416                mStat.pvs += leaf->mViewCell->GetPvs().GetSize();
1417        }
1418       
1419#ifdef _DEBUG
1420        Debug << "BSP stats: "
1421                  << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
1422                  << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
1423                  << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << ")" << endl;
1424#endif
1425}
1426
1427int BspTree::CastRay(Ray &ray)
1428{
1429        int hits = 0;
1430 
1431        stack<BspRayTraversalData> tStack;
1432 
1433        float maxt = 1e6;
1434        float mint = 0;
1435       
1436        Intersectable::NewMail();
1437
1438        // test with tree bounding box
1439        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
1440                return 0;
1441
1442        if (mint < 0) // start ray from origin
1443                mint = 0;
1444
1445        // bound ray
1446        if ((ray.GetType() == Ray::LOCAL_RAY) &&
1447                (!ray.intersections.empty())      &&
1448            (ray.intersections[0].mT <= maxt))
1449        {
1450                maxt = ray.intersections[0].mT;
1451    }
1452 
1453        Vector3 entp = ray.Extrap(mint);
1454        Vector3 extp = ray.Extrap(maxt);
1455 
1456        BspNode *node = mRoot;
1457        BspNode *farChild = NULL;
1458       
1459        while (1)
1460        {
1461                if (!node->IsLeaf())
1462                {
1463                        BspInterior *in = (BspInterior *) node;
1464                       
1465                        Plane3 *splitPlane = in->GetPlane();
1466
1467                        float t = 0;
1468                        bool coplanar = false;
1469               
1470                        int entSide = splitPlane->Side(entp);
1471                        int extSide = splitPlane->Side(extp);
1472
1473                        Vector3 intersection;
1474
1475                        if (entSide < 0)
1476                        {
1477                                node = in->GetBack();
1478
1479                                if(extSide <= 0) // plane does not split ray => no far child
1480                                        continue;
1481                                       
1482                                farChild = in->GetFront(); // plane splits ray
1483
1484                        } else if (entSide > 0)
1485                        {
1486                                node = in->GetFront();
1487
1488                                if (extSide >= 0) // plane does not split ray => no far child
1489                                        continue;
1490
1491                                farChild = in->GetBack(); // plane splits ray                   
1492                        }
1493                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
1494                        {
1495                                node = in->GetFront();
1496                                continue;
1497                        }
1498
1499                        // push data for far child
1500                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1501
1502                        // find intersection of ray segment with plane
1503                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
1504                       
1505                } else // reached leaf => intersection with view cell
1506                {
1507                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1508     
1509                        if (!leaf->mViewCell->Mailed())
1510                        {
1511                                ray.viewCells.push_back(leaf->mViewCell);
1512                                leaf->mViewCell->Mail();
1513                                ++ hits;
1514                        }
1515                       
1516                        //-- fetch the next far child from the stack
1517                        if (tStack.empty())
1518                                break;
1519     
1520                        entp = extp;
1521                        mint = maxt; // NOTE: need this?
1522                        BspRayTraversalData &s = tStack.top();
1523
1524                        node = s.mNode;
1525                        extp = s.mExitPoint;
1526                        maxt = s.mMaxT;
1527
1528                        //Debug << "leaf: new entrypt: " << entp << " new extp: " << extp << endl;
1529
1530                        tStack.pop();
1531                }
1532        }
1533
1534        return hits;
1535}
1536
1537bool BspTree::Export(const string filename)
1538{
1539        Exporter *exporter = Exporter::GetExporter(filename);
1540
1541        if (exporter)
1542        {
1543                exporter->ExportBspTree(*this);
1544                return true;
1545        }       
1546
1547        return false;
1548}
1549
1550void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1551{
1552        stack<BspNode *> nodeStack;
1553        nodeStack.push(mRoot);
1554
1555        ViewCell::NewMail();
1556
1557        while (!nodeStack.empty())
1558        {
1559                BspNode *node = nodeStack.top();
1560                nodeStack.pop();
1561
1562                if (node->IsLeaf())
1563                {
1564                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1565
1566                        if (!viewCell->Mailed())
1567                        {
1568                                viewCell->Mail();
1569                                viewCells.push_back(viewCell);
1570                        }
1571                }
1572                else
1573                {
1574                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1575
1576                        nodeStack.push(interior->mFront);
1577                        nodeStack.push(interior->mBack);
1578                }
1579        }
1580}
1581
1582int BspTree::MergeViewCells()
1583{
1584        stack<BspNode *> nodeStack;
1585        stack<BspLeaf *> leafStack;
1586
1587        nodeStack.push(mRoot);
1588       
1589        // collect leaves
1590        while (!nodeStack.empty())
1591        {
1592                BspNode *node = nodeStack.top();
1593               
1594                nodeStack.pop();
1595
1596                if (node->IsLeaf())
1597                {
1598                        BspNode *leaf = dynamic_cast<BspLeaf *>(node);
1599
1600                        // get other leaf we can merge with
1601                        while (!leafStack.empty() && leafStack.top()->mParent == node->mParent)
1602                        {
1603                                leafStack.pop();
1604                                BspNode *mergedNode = MergeNodes(node->mParent);
1605
1606                                if (mergedNode->IsLeaf())
1607                                        leafStack.push(dynamic_cast<BspLeaf *>(mergedNode));
1608                                else
1609                                        leafStack.push(dynamic_cast<BspLeaf *>(node));
1610                        }
1611                }
1612                else
1613                {
1614                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1615                        nodeStack.push(interior->mFront);
1616                        nodeStack.push(interior->mBack);
1617                }
1618        }
1619
1620        return 0;
1621}
1622
1623bool BspTree::MergeNecessary(BspLeaf *front, BspLeaf *back) const
1624{
1625        return true;
1626}
1627
1628BspNode *BspTree::MergeNodes(BspInterior *node)
1629{
1630        BspLeaf *front = dynamic_cast<BspLeaf *>(node->mFront);
1631        BspLeaf *back = dynamic_cast<BspLeaf *>(node->mBack);
1632
1633        if (!MergeNecessary(front, back))
1634                return node;
1635
1636        DEL_PTR(front->mViewCell);
1637        DEL_PTR(front);
1638               
1639        DEL_PTR(back->mViewCell);
1640        DEL_PTR(back);
1641
1642        BspLeaf *leaf = new BspLeaf(new ViewCell());
1643        BspInterior *parent = node->GetParent();
1644
1645        // replace a link from node's parent
1646        if (!node->IsRoot())
1647        {
1648                parent->ReplaceChildLink(node, leaf);
1649                node->SetParent(parent);
1650        }
1651        else // new root
1652        {
1653                mRoot = leaf;
1654        }
1655               
1656        return leaf;
1657}
1658
1659/*BspNode *BspTree::MergeNodes(BspNode *node)
1660{
1661        BspNode *front = MergeNodes(dynamic_cast<BspInterior *>(node)->mFront);
1662        BspNode *back = MergeNodes(dynamic_cast<BspInterior *>(node)->mBack);
1663
1664        if (!front->IsLeaf() && !back->IsLeaf())
1665
1666        {
1667                if (!MergeNecessary(front, back))
1668                        return node;
1669
1670                DEL_PTR(front->mViewCell);
1671                DEL_PTR(front);
1672               
1673                DEL_PTR(back->mViewCell);
1674                DEL_PTR(back);
1675
1676                BspLeaf *leaf = new BspLeaf(new ViewCell());
1677                BspInterior *parent = node->GetParent();
1678
1679                // replace a link from node's parent
1680                if (!node->IsRoot())
1681                {
1682                        parent->ReplaceChildLink(node, leaf);
1683                        node->SetParent(parent);
1684                }
1685                else // new root
1686                {
1687                        mRoot = leaf;
1688                }
1689               
1690                return leaf;
1691        }
1692
1693        return node;
1694}*/
1695
1696void BspTree::SetGenerateViewCells(int generateViewCells)
1697{
1698        mGenerateViewCells = generateViewCells;
1699}
1700
1701BspTreeStatistics &BspTree::GetStat()
1702{
1703        return mStat;
1704}
Note: See TracBrowser for help on using the repository browser.