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

Revision 372, 57.0 KB checked in by bittner, 19 years ago (diff)

preparation for vss preprocessor. converted all .cpp and .h to dos new line format
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::sTermMaxObjectsForAxisAligned = 50;
23int BspTree::sTermMaxRaysForAxisAligned = -1;
24int BspTree::sTermMaxRays = -1;
25int BspTree::sMinPvsDif = 10;
26
27float BspTree::sCt_div_ci = 1.0f;
28float BspTree::sSplitBorder = 1.0f;
29float BspTree::sMaxCostRatio = 0.9f;
30
31//-- factors for bsp tree split plane heuristics
32
33float BspTree::sLeastSplitsFactor = 1.0f;
34float BspTree::sBalancedPolysFactor = 1.0f;
35float BspTree::sBalancedViewCellsFactor = 1.0f;
36
37// NOTE:  very important criterium for 2.5d scenes
38float BspTree::sVerticalSplitsFactor = 1.0f;
39float BspTree::sLargestPolyAreaFactor = 1.0f;
40float BspTree::sBlockedRaysFactor = 1.0f;
41float BspTree::sLeastRaySplitsFactor = 1.0f;
42float BspTree::sBalancedRaysFactor = 1.0f;
43float BspTree::sPvsFactor = 1.0f;
44
45bool BspTree::sStoreSplitPolys = false;
46
47int BspNode::mailID = 1;
48
49/** Evaluates split plane classification with respect to the plane's
50        contribution for a minimum number splits in the tree.
51*/
52float BspTree::sLeastPolySplitsTable[] = {0, 0, 1, 0};
53/** Evaluates split plane classification with respect to the plane's
54        contribution for a balanced tree.
55*/
56float BspTree::sBalancedPolysTable[] = {1, -1, 0, 0};
57
58/** Evaluates split plane classification with respect to the plane's
59        contribution for a minimum number of ray splits.
60*/
61float BspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
62/** Evaluates split plane classification with respect to the plane's
63        contribution for balanced rays.
64*/
65float BspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
66
67/****************************************************************/
68/*                  class BspNode implementation                */
69/****************************************************************/
70
71BspNode::BspNode():
72mParent(NULL), mPolygons(NULL)
73{}
74
75BspNode::BspNode(BspInterior *parent):
76mParent(parent), mPolygons(NULL)
77{}
78
79BspNode::~BspNode()
80{
81        if (mPolygons)
82        {
83                CLEAR_CONTAINER(*mPolygons);
84                DEL_PTR(mPolygons);
85        }
86}
87
88bool BspNode::IsRoot() const
89{
90        return mParent == NULL;
91}
92
93BspInterior *BspNode::GetParent()
94{
95        return mParent;
96}
97
98void BspNode::SetParent(BspInterior *parent)
99{
100        mParent = parent;
101}
102
103PolygonContainer *BspNode::GetPolygons()
104{
105        if (!mPolygons)
106                mPolygons = new PolygonContainer();
107
108        return mPolygons;
109}
110
111void BspNode::ProcessPolygons(PolygonContainer *polys, bool storePolys)
112{
113        if (storePolys)
114        {
115                while (!polys->empty())
116                {
117                        GetPolygons()->push_back(polys->back());
118                        polys->pop_back();
119                }
120        }
121        else CLEAR_CONTAINER(*polys);
122}
123
124
125/****************************************************************/
126/*              class BspInterior implementation                */
127/****************************************************************/
128
129
130BspInterior::BspInterior(const Plane3 &plane):
131mPlane(plane), mFront(NULL), mBack(NULL)
132{}
133
134bool BspInterior::IsLeaf() const
135{
136        return false;
137}
138
139BspNode *BspInterior::GetBack()
140{
141        return mBack;
142}
143
144BspNode *BspInterior::GetFront()
145{
146        return mFront;
147}
148
149Plane3 *BspInterior::GetPlane()
150{
151        return &mPlane;
152}
153
154void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild)
155{
156        if (mBack == oldChild)
157                mBack = newChild;
158        else
159                mFront = newChild;
160}
161
162void BspInterior::SetupChildLinks(BspNode *b, BspNode *f)
163{
164    mBack = b;
165    mFront = f;
166}
167
168void BspInterior::ProcessPolygon(Polygon3 **poly, const bool storePolys)
169{
170        if (storePolys)
171                GetPolygons()->push_back(*poly);
172        else
173                DEL_PTR(*poly);
174}
175
176int BspInterior::SplitPolygons(PolygonContainer &polys,
177                                                           PolygonContainer &frontPolys,
178                                                           PolygonContainer &backPolys,
179                                                           PolygonContainer &coincident,
180                                                           const bool storePolys)
181{
182        Polygon3 *splitPoly = NULL;
183
184        int splits = 0;
185
186#ifdef _Debug
187        Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
188#endif
189        while (!polys.empty())
190        {
191                Polygon3 *poly = polys.back();
192                polys.pop_back();
193
194                //Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
195
196                // classify polygon
197                const int cf = poly->ClassifyPlane(mPlane);
198
199                Polygon3 *front_piece = NULL;
200                Polygon3 *back_piece = NULL;
201       
202                VertexContainer splitVertices;
203
204                switch (cf)
205                {
206                        case Polygon3::COINCIDENT:
207                                coincident.push_back(poly);
208                                break;                 
209                        case Polygon3::FRONT_SIDE:     
210                                frontPolys.push_back(poly);
211                                break;
212                        case Polygon3::BACK_SIDE:
213                                backPolys.push_back(poly);
214                                break;
215                        case Polygon3::SPLIT:
216                                front_piece = new Polygon3(poly->mParent);
217                                back_piece = new Polygon3(poly->mParent);
218
219                                //-- split polygon into front and back part
220                                poly->Split(mPlane,
221                                                        *front_piece,
222                                                        *back_piece,
223                                                        splitVertices);
224                                       
225                                ++ splits; // increase number of splits
226
227                                //-- inherit rays from parent polygon for blocked ray criterium
228                                poly->InheritRays(*front_piece, *back_piece);
229                                //Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl;
230                               
231                                // check if polygons still valid
232                                if (front_piece->Valid())
233                                        frontPolys.push_back(front_piece);
234                                else
235                                        DEL_PTR(front_piece);
236                               
237                                if (back_piece->Valid())
238                                        backPolys.push_back(back_piece);
239                                else                           
240                                        DEL_PTR(back_piece);
241                               
242#ifdef _DEBUG
243                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
244#endif
245                                ProcessPolygon(&poly, storePolys);                     
246                                break;
247                        default:
248                Debug << "SHOULD NEVER COME HERE\n";
249                                break;
250                }
251        }
252
253        return splits;
254}
255
256/****************************************************************/
257/*                  class BspLeaf implementation                */
258/****************************************************************/
259BspLeaf::BspLeaf(): mViewCell(NULL)
260{
261}
262
263BspLeaf::BspLeaf(BspViewCell *viewCell):
264mViewCell(viewCell)
265{
266}
267
268BspLeaf::BspLeaf(BspInterior *parent):
269BspNode(parent), mViewCell(NULL)
270{}
271
272BspLeaf::BspLeaf(BspInterior *parent, BspViewCell *viewCell):
273BspNode(parent), mViewCell(viewCell)
274{
275}
276
277BspViewCell *BspLeaf::GetViewCell() const
278{
279        return mViewCell;
280}
281
282void BspLeaf::SetViewCell(BspViewCell *viewCell)
283{
284        mViewCell = viewCell;
285}
286
287bool BspLeaf::IsLeaf() const
288{
289        return true;
290}
291
292void BspLeaf::GenerateViewCell(const BoundedRayContainer &rays,
293                                                           int &sampleContributions,
294                                                           int &contributingSamples)
295{
296        sampleContributions = 0;
297        contributingSamples = 0;
298
299        mViewCell = dynamic_cast<BspViewCell *>(ViewCell::Generate());
300        mViewCell->mBspLeaves.push_back(this);
301
302    BoundedRayContainer::const_iterator it, it_end = rays.end();
303
304        // add contributions from samples to the PVS
305        for (it = rays.begin(); it != it_end; ++ it)
306        {
307                int contribution = 0;
308                Ray *ray = (*it)->mRay;
309                       
310                if (!ray->intersections.empty())
311                {       
312            contribution += mViewCell->GetPvs().AddSample(ray->intersections[0].mObject);
313                }
314
315                contribution += mViewCell->GetPvs().AddSample(ray->sourceObject.mObject);
316
317                if (contribution > 0)
318                {
319                        sampleContributions += contribution;
320                        ++ contributingSamples;
321                }
322
323                // warning: not ordered
324                ray->bspIntersections.push_back(Ray::BspIntersection((*it)->mMinT, this));
325        }
326}
327
328
329/****************************************************************/
330/*                  class BspTree implementation                */
331/****************************************************************/
332
333BspTree::BspTree(ViewCell *viewCell):
334mRootCell(viewCell), mRoot(NULL), mGenerateViewCells(false),
335mStorePiercingRays(true)
336{
337        Randomize(); // initialise random generator for heuristics
338}
339 
340const BspTreeStatistics &BspTree::GetStatistics() const
341{
342        return mStat;
343}
344
345void BspTreeStatistics::Print(ostream &app) const
346{
347        app << "===== BspTree statistics ===============\n";
348
349        app << setprecision(4);
350
351        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
352
353        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
354
355        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
356
357        app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
358
359        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
360        maxDepthNodes * 100 / (double)Leaves() << endl;
361
362        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
363
364        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
365
366        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
367
368        app << "#N_INPUT_POLYGONS (number of input polygons )\n" <<     polys << endl;
369
370        app << "#N_PVS: " << pvs << endl;
371
372        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
373                 (polys + splits) / (double)polys << endl;
374       
375        app << "===== END OF BspTree statistics ==========\n";
376}
377
378BspTree::~BspTree()
379{
380        std::stack<BspNode *> tStack;
381
382        tStack.push(mRoot);
383
384        while (!tStack.empty())
385        {
386                BspNode *node = tStack.top();
387
388            tStack.pop();
389       
390                if (!node->IsLeaf())
391                {
392                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
393
394                        // push the children on the stack (there are always two children)
395                        tStack.push(interior->GetBack());
396                        tStack.push(interior->GetFront());
397                }
398
399                DEL_PTR(node);
400        }
401}
402
403void BspTree::InsertViewCell(ViewCell *viewCell)
404{
405        PolygonContainer *polys = new PolygonContainer();
406
407        // extract polygons that guide the split process
408        mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
409        mBox.Include(viewCell->GetBox()); // add to BSP aabb
410
411        InsertPolygons(polys);
412}
413
414void BspTree::InsertPolygons(PolygonContainer *polys)
415{       
416        std::stack<BspTraversalData> tStack;
417       
418        // traverse existing tree or create new tree
419    if (!mRoot)
420                mRoot = new BspLeaf();
421
422        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer()));
423
424        while (!tStack.empty())
425        {
426                // filter polygons donw the tree
427                BspTraversalData tData = tStack.top();
428            tStack.pop();
429                       
430                if (!tData.mNode->IsLeaf())
431                {
432                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
433
434                        //-- filter view cell polygons down the tree until a leaf is reached
435                        if (!tData.mPolygons->empty())
436                        {
437                                PolygonContainer *frontPolys = new PolygonContainer();
438                                PolygonContainer *backPolys = new PolygonContainer();
439                                PolygonContainer coincident;
440
441                                int splits = 0;
442               
443                                // split viewcell polygons with respect to split plane
444                                splits += interior->SplitPolygons(*tData.mPolygons,
445                                                                                                  *frontPolys,
446                                                                                                  *backPolys,
447                                                                                                  coincident,
448                                                                                                  sStoreSplitPolys);
449                               
450                                // extract view cells associated with the split polygons
451                                ViewCell *frontViewCell = mRootCell;
452                                ViewCell *backViewCell = mRootCell;
453       
454                                if (!mGenerateViewCells)
455                                {
456                                        ExtractViewCells(&backViewCell,
457                                                                         &frontViewCell,
458                                                                         coincident,
459                                                                         interior->mPlane,
460                                                                         frontPolys->empty(),
461                                                                         backPolys->empty());
462                                }
463
464                                // don't need coincident polygons anymore
465                                interior->ProcessPolygons(&coincident, sStoreSplitPolys);
466
467                                mStat.splits += splits;
468
469                                // push the children on the stack
470                                tStack.push(BspTraversalData(interior->GetFront(),
471                                                                                         frontPolys,
472                                                                                         tData.mDepth + 1,
473                                                                                         frontViewCell,
474                                                                                         tData.mRays));
475
476                                tStack.push(BspTraversalData(interior->GetBack(),
477                                                                                         backPolys,
478                                                                                         tData.mDepth + 1,
479                                                                                         backViewCell,
480                                                                                         new BoundedRayContainer()));
481                        }
482
483                        // cleanup
484                        DEL_PTR(tData.mPolygons);
485                }
486                else
487                {
488                        // reached leaf => subdivide current viewcell
489                        BspNode *subRoot = Subdivide(tStack, tData);
490                }
491        }
492}
493
494int BspTree::AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent)
495{
496        FaceContainer::const_iterator fi;
497       
498        // copy the face data to polygons
499        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
500        {
501                Polygon3 *poly = new Polygon3((*fi), mesh);
502               
503                if (poly->Valid())
504                {
505                        poly->mParent = parent; // set parent intersectable
506                        polys.push_back(poly);
507                }
508                else
509                        DEL_PTR(poly);
510        }
511        return (int)mesh->mFaces.size();
512}
513
514int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
515                                                          PolygonContainer &polys,
516                                                          int maxObjects)
517{
518        int limit = (maxObjects > 0) ?
519                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
520 
521        int polysSize = 0;
522
523        for (int i = 0; i < limit; ++ i)
524        {
525                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
526                {
527                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
528                        polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
529                }
530        }
531
532        return polysSize;
533}
534
535int BspTree::AddToPolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
536{
537        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
538 
539        for (int i = 0; i < limit; ++i)
540        {
541                Intersectable *object = objects[i];//*it;
542                Mesh *mesh = NULL;
543
544                switch (object->Type()) // extract the meshes
545                {
546                case Intersectable::MESH_INSTANCE:
547                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
548                        break;
549                case Intersectable::VIEW_CELL:
550                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
551                        break;
552                        // TODO: handle transformed mesh instances
553                default:
554                        Debug << "intersectable type not supported" << endl;
555                        break;
556                }
557               
558        if (mesh) // copy the mesh data to polygons
559                {
560                        mBox.Include(object->GetBox()); // add to BSP tree aabb
561                        AddMeshToPolygons(mesh, polys, mRootCell);
562                }
563        }
564
565        return (int)polys.size();
566}
567
568void BspTree::Construct(const ViewCellContainer &viewCells)
569{
570        mStat.nodes = 1;
571        mBox.Initialize();      // initialise bsp tree bounding box
572
573        // copy view cell meshes into one big polygon soup
574        PolygonContainer *polys = new PolygonContainer();
575        mStat.polys = AddToPolygonSoup(viewCells, *polys);
576
577        // construct tree from the view cell polygons
578        Construct(polys, new BoundedRayContainer());
579}
580
581
582void BspTree::Construct(const ObjectContainer &objects)
583{
584        mStat.nodes = 1;
585        mBox.Initialize();      // initialise bsp tree bounding box
586       
587        PolygonContainer *polys = new PolygonContainer();
588       
589        // copy mesh instance polygons into one big polygon soup
590        mStat.polys = AddToPolygonSoup(objects, *polys);
591
592        // construct tree from polygon soup
593        Construct(polys, new BoundedRayContainer());
594}
595
596void BspTree::Construct(const RayContainer &sampleRays)
597{
598        mStat.nodes = 1;
599        mBox.Initialize();      // initialise BSP tree bounding box
600       
601        PolygonContainer *polys = new PolygonContainer();
602        BoundedRayContainer *rays = new BoundedRayContainer();
603
604        RayContainer::const_iterator rit, rit_end = sampleRays.end();
605
606        long startTime = GetTime();
607
608        Debug << "**** Extracting polygons from rays ****\n";
609
610        std::map<Face *, Polygon3 *> facePolyMap;
611
612        //-- extract polygons intersected by the rays
613        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
614        {
615                Ray *ray = *rit;
616       
617                // get ray-face intersection. Store polygon representing the rays together
618                // with rays intersecting the face.
619                if (!ray->intersections.empty())
620                {
621                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->intersections[0].mObject);
622                        Face *face = obj->GetMesh()->mFaces[ray->intersections[0].mFace];
623
624                        std::map<Face *, Polygon3 *>::iterator it = facePolyMap.find(face);
625
626                        if (it != facePolyMap.end())
627                        {
628                                //store rays if needed for heuristics
629                                if (sSplitPlaneStrategy & BLOCKED_RAYS)
630                                        (*it).second->mPiercingRays.push_back(ray);
631                        }
632                        else
633                        {       //store rays if needed for heuristics
634                                Polygon3 *poly = new Polygon3(face, obj->GetMesh());
635                                poly->mParent = obj;
636                                polys->push_back(poly);
637
638                                if (sSplitPlaneStrategy & BLOCKED_RAYS)
639                                        poly->mPiercingRays.push_back(ray);
640
641                                facePolyMap[face] = poly;
642                        }
643                }
644        }
645       
646        facePolyMap.clear();
647
648        // compue bounding box
649        Polygon3::IncludeInBox(*polys, mBox);
650
651        //-- store rays
652        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
653        {
654                Ray *ray = *rit;
655        ray->SetId(-1); // reset id
656
657                float minT, maxT;
658                if (BoundRay(*ray, minT, maxT))
659                        rays->push_back(new BoundedRay(ray, minT, maxT));
660        }
661
662        mStat.polys = (int)polys->size();
663
664        Debug << "**** Finished polygon extraction ****" << endl;
665        Debug << (int)polys->size() << " polys extracted from " << (int)rays->size() << " rays" << endl;
666        Debug << "extraction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
667
668        Construct(polys, rays);
669}
670
671void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays)
672{
673        std::stack<BspTraversalData> tStack;
674
675        mRoot = new BspLeaf();
676
677        BspTraversalData tData(mRoot, polys, 0, mRootCell, rays);
678        tStack.push(tData);
679
680        long startTime = GetTime();
681        cout << "**** Contructing bsp tree ****\n";
682
683        while (!tStack.empty())
684        {
685                tData = tStack.top();
686            tStack.pop();
687
688                // subdivide leaf node
689                BspNode *subRoot = Subdivide(tStack, tData);
690        }
691
692        cout << "**** Finished tree construction ****\n";
693        Debug << "BSP tree contruction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
694}
695
696
697BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
698{
699        //-- terminate traversal 
700        if (((int)tData.mPolygons->size() <= sTermMaxPolygons) ||
701                ((int)tData.mRays->size() <= sTermMaxRays) ||
702                (tData.mDepth >= sTermMaxDepth))
703               
704        {
705                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
706       
707                // generate new view cell for each leaf
708                if (mGenerateViewCells)
709                {
710                        int conSamp, sampCon;
711                        leaf->GenerateViewCell(*tData.mRays, conSamp, sampCon);
712                       
713                        mStat.contributingSamples += conSamp;
714                        mStat.sampleContributions += sampCon;
715                }
716                else
717                {
718                        // add view cell to leaf
719                        leaf->SetViewCell(dynamic_cast<BspViewCell *>(tData.mViewCell));
720                        leaf->mViewCell->mBspLeaves.push_back(leaf);
721                }
722
723                EvaluateLeafStats(tData);
724               
725                //-- clean up
726               
727                // remaining polygons are discarded or added to node
728                leaf->ProcessPolygons(tData.mPolygons, sStoreSplitPolys);
729                DEL_PTR(tData.mPolygons);
730                // discard rays
731                CLEAR_CONTAINER(*tData.mRays);
732                DEL_PTR(tData.mRays);
733
734                return leaf;
735        }
736
737        //-- continue subdivision
738
739        PolygonContainer coincident;
740       
741        PolygonContainer *frontPolys = new PolygonContainer();
742        PolygonContainer *backPolys = new PolygonContainer();
743
744        BoundedRayContainer *frontRays = new BoundedRayContainer();
745        BoundedRayContainer *backRays = new BoundedRayContainer();
746       
747        // create new interior node and two leaf nodes
748        BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
749                                                                                  *tData.mPolygons,
750                                                                                  *frontPolys,
751                                                                                  *backPolys,
752                                                                                  coincident,
753                                                                                  *tData.mRays,
754                                                                                  *frontRays,
755                                                                                  *backRays);
756        ViewCell *frontViewCell = mRootCell;
757        ViewCell *backViewCell = mRootCell;
758
759#ifdef _DEBUG   
760        if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
761        {       for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
762                        Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ;
763                Debug << endl;}
764#endif
765
766        // extract view cells from coincident polygons according to plane normal
767    // only if front or back polygons are empty
768        if (!mGenerateViewCells)
769        {
770                ExtractViewCells(&backViewCell,
771                                                 &frontViewCell,
772                                                 coincident,
773                                                 interior->mPlane,
774                                                 backPolys->empty(),
775                                                 frontPolys->empty());
776        }
777       
778        // don't need coincident polygons anymore
779        interior->ProcessPolygons(&coincident, sStoreSplitPolys);
780
781        // push the children on the stack
782        tStack.push(BspTraversalData(interior->GetBack(),
783                                                                 backPolys,
784                                                                 tData.mDepth + 1,
785                                                                 backViewCell,
786                                                                 backRays));
787
788        tStack.push(BspTraversalData(interior->GetFront(),
789                                                                 frontPolys,
790                                                                 tData.mDepth + 1,
791                                                                 frontViewCell,
792                                                                 frontRays));
793
794        // cleanup
795        DEL_PTR(tData.mNode);
796        DEL_PTR(tData.mPolygons);
797        DEL_PTR(tData.mRays);
798
799        return interior;
800}
801
802void BspTree::ExtractViewCells(ViewCell **backViewCell,
803                                                           ViewCell **frontViewCell,
804                                                           const PolygonContainer &coincident,
805                                                           const Plane3 splitPlane,
806                                                           const bool extractBack,
807                                                           const bool extractFront) const
808{
809        bool foundFront = !extractFront, foundBack = !extractBack;
810
811        PolygonContainer::const_iterator it =
812                coincident.begin(), it_end = coincident.end();
813
814        //-- find first view cells in front and back leafs
815        for (; !(foundFront && foundBack) && (it != it_end); ++ it)
816        {
817                if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
818                {
819                        *backViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
820                        foundBack = true;
821                }
822                else
823                {
824                        *frontViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
825                        foundFront = true;
826                }
827        }
828        //if (extractFront && foundFront)       Debug << "front view cell: " << *frontViewCell << endl;
829        //if (extractBack && foundBack) Debug << "back view cell: " << *backViewCell << endl;
830}
831
832BspInterior *BspTree::SubdivideNode(BspLeaf *leaf,
833                                                                        PolygonContainer &polys,
834                                                                        PolygonContainer &frontPolys,
835                                                                        PolygonContainer &backPolys,
836                                                                        PolygonContainer &coincident,
837                                                                        BoundedRayContainer &rays,
838                                                                        BoundedRayContainer &frontRays,
839                                                                        BoundedRayContainer &backRays)
840{
841        mStat.nodes += 2;
842       
843        // select subdivision plane
844        BspInterior *interior =
845                new BspInterior(SelectPlane(leaf, polys, rays));
846
847#ifdef _DEBUG
848        Debug << interior << endl;
849#endif
850       
851        // subdivide rays into front and back rays
852        SplitRays(interior->mPlane, rays, frontRays, backRays);
853       
854        // subdivide polygons with plane
855        mStat.splits += interior->SplitPolygons(polys,
856                                                    frontPolys,
857                                                                                        backPolys,
858                                                                                        coincident,
859                                                                                        sStoreSplitPolys);
860
861        BspInterior *parent = leaf->GetParent();
862
863        // replace a link from node's parent
864        if (!leaf->IsRoot())
865        {
866                parent->ReplaceChildLink(leaf, interior);
867                interior->SetParent(parent);
868        }
869        else // new root
870        {
871                mRoot = interior;
872        }
873
874        // and setup child links
875        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
876       
877        return interior;
878}
879
880void BspTree::SortSplitCandidates(const PolygonContainer &polys,
881                                                                  const int axis,
882                                                                  vector<SortableEntry> &splitCandidates) const
883{
884  splitCandidates.clear();
885 
886  int requestedSize = 2 * (int)polys.size();
887  // creates a sorted split candidates array 
888  splitCandidates.reserve(requestedSize);
889 
890  PolygonContainer::const_iterator it, it_end = polys.end();
891
892  AxisAlignedBox3 box;
893
894  // insert all queries
895  for(it = polys.begin(); it != it_end; ++ it)
896  {
897          box.Initialize();
898          box.Include(*(*it));
899         
900          splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
901      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
902  }
903 
904  stable_sort(splitCandidates.begin(), splitCandidates.end());
905}
906
907
908float BspTree::BestCostRatio(const PolygonContainer &polys,
909                                                         const AxisAlignedBox3 &box,
910                                                         const int axis,
911                                                         float &position,
912                                                         int &objectsBack,
913                                                         int &objectsFront) const
914{
915        vector<SortableEntry> splitCandidates;
916
917        SortSplitCandidates(polys, axis, splitCandidates);
918       
919        // go through the lists, count the number of objects left and right
920        // and evaluate the following cost funcion:
921        // C = ct_div_ci  + (ol + or)/queries
922       
923        int objectsLeft = 0, objectsRight = (int)polys.size();
924       
925        float minBox = box.Min(axis);
926        float maxBox = box.Max(axis);
927        float boxArea = box.SurfaceArea();
928 
929        float minBand = minBox + sSplitBorder * (maxBox - minBox);
930        float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
931       
932        float minSum = 1e20f;
933        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
934
935        for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
936        {
937                switch ((*ci).type)
938                {
939                        case SortableEntry::POLY_MIN:
940                                ++ objectsLeft;
941                                break;
942                        case SortableEntry::POLY_MAX:
943                            -- objectsRight;
944                                break;
945                        default:
946                                break;
947                }
948               
949                if ((*ci).value > minBand && (*ci).value < maxBand)
950                {
951                        AxisAlignedBox3 lbox = box;
952                        AxisAlignedBox3 rbox = box;
953                        lbox.SetMax(axis, (*ci).value);
954                        rbox.SetMin(axis, (*ci).value);
955
956                        float sum = objectsLeft * lbox.SurfaceArea() +
957                                                objectsRight * rbox.SurfaceArea();
958     
959                        if (sum < minSum)
960                        {
961                                minSum = sum;
962                                position = (*ci).value;
963
964                                objectsBack = objectsLeft;
965                                objectsFront = objectsRight;
966                        }
967                }
968        }
969 
970        float oldCost = (float)polys.size();
971        float newCost = sCt_div_ci + minSum / boxArea;
972        float ratio = newCost / oldCost;
973
974
975#if 0
976  Debug << "====================" << endl;
977  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
978      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
979#endif
980  return ratio;
981}
982
983bool BspTree::SelectAxisAlignedPlane(Plane3 &plane,
984                                                                         const PolygonContainer &polys) const
985{
986        AxisAlignedBox3 box;
987        box.Initialize();
988       
989        // create bounding box of region
990        Polygon3::IncludeInBox(polys, box);
991       
992        int objectsBack = 0, objectsFront = 0;
993        int axis = 0;
994        float costRatio = MAX_FLOAT;
995        Vector3 position;
996
997        //-- area subdivision
998        for (int i = 0; i < 3; ++ i)
999        {
1000                float p = 0;
1001                float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
1002               
1003                if (r < costRatio)
1004                {
1005                        costRatio = r;
1006                        axis = i;
1007                        position = p;
1008                }
1009        }
1010       
1011        if (costRatio >= sMaxCostRatio)
1012                return false;
1013
1014        Vector3 norm(0,0,0); norm[axis] = 1.0f;
1015        plane = Plane3(norm, position);
1016
1017        return true;
1018}
1019
1020Plane3 BspTree::SelectPlane(BspLeaf *leaf,
1021                                                        PolygonContainer &polys,
1022                                                        const BoundedRayContainer &rays)
1023{
1024        if (polys.empty())
1025        {
1026                Debug << "Warning: No autopartition polygon candidate available\n";
1027       
1028                // return axis aligned split
1029                AxisAlignedBox3 box;
1030                box.Initialize();
1031       
1032                // create bounding box of region
1033                Polygon3::IncludeInBox(polys, box);
1034
1035                const int axis = box.Size().DrivingAxis();
1036                const Vector3 position = (box.Min()[axis] + box.Max()[axis])*0.5f;
1037
1038                Vector3 norm(0,0,0); norm[axis] = 1.0f;
1039                return Plane3(norm, position);
1040        }
1041       
1042        if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
1043                ((int)polys.size() > sTermMaxPolysForAxisAligned) &&
1044                ((int)rays.size() > sTermMaxRaysForAxisAligned) &&
1045                ((sTermMaxObjectsForAxisAligned < 0) ||
1046                  (Polygon3::CountIntersectables(polys) > sTermMaxObjectsForAxisAligned)))
1047        {
1048                Plane3 plane;
1049                if (SelectAxisAlignedPlane(plane, polys))
1050                        return plane;
1051        }
1052
1053        // simplest strategy: just take next polygon
1054        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1055        {
1056                return polys[Random((int)polys.size())]->GetSupportingPlane();
1057        }
1058
1059        // use heuristics to find appropriate plane
1060        return SelectPlaneHeuristics(polys, rays, sMaxCandidates);
1061}
1062
1063Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer &polys,
1064                                                                          const BoundedRayContainer &rays,
1065                                                                          const int maxTests)
1066{
1067        float lowestCost = MAX_FLOAT;
1068        int bestPlaneIdx = 0;
1069       
1070        int limit = maxTests > 0 ? Min((int)polys.size(), maxTests) : (int)polys.size();
1071       
1072        int candidateIdx = limit;
1073       
1074        for (int i = 0; i < limit; ++ i)
1075        {
1076                candidateIdx = GetNextCandidateIdx(candidateIdx, polys);
1077
1078                Plane3 candidatePlane = polys[candidateIdx]->GetSupportingPlane();
1079               
1080                // evaluate current candidate
1081                float candidateCost = SplitPlaneCost(candidatePlane, polys, rays);
1082                       
1083                if (candidateCost < lowestCost)
1084                {
1085                        bestPlaneIdx = candidateIdx;
1086                        lowestCost = candidateCost;
1087                }
1088        }
1089       
1090        //Debug << "Plane lowest cost: " << lowestCost << endl;
1091        return polys[bestPlaneIdx]->GetSupportingPlane();
1092}
1093
1094int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
1095{
1096        const int candidateIdx = Random(currentIdx --);
1097
1098        // swap candidates to avoid testing same plane 2 times
1099        std::swap(polys[currentIdx], polys[candidateIdx]);
1100
1101        /*Polygon3 *p = polys[candidateIdx];
1102        polys[candidateIdx] = polys[currentIdx];
1103        polys[currentIdx] = p;*/
1104       
1105        return currentIdx;
1106        //return Random((int)polys.size());
1107}
1108
1109float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1110                                                          const PolygonContainer &polys) const
1111{
1112        float val = 0;
1113
1114        float sumBalancedPolys = 0;
1115        float sumSplits = 0;
1116        float sumPolyArea = 0;
1117        float sumBalancedViewCells = 0;
1118        float sumBlockedRays = 0;
1119        float totalBlockedRays = 0;
1120        //float totalArea = 0;
1121        int totalViewCells = 0;
1122
1123        // need three unique ids for each type of view cell
1124        // for balanced view cells criterium
1125        ViewCell::NewMail();
1126        const int backId = ViewCell::sMailId;
1127        ViewCell::NewMail();
1128        const int frontId = ViewCell::sMailId;
1129        ViewCell::NewMail();
1130        const int frontAndBackId = ViewCell::sMailId;
1131
1132        PolygonContainer::const_iterator it, it_end = polys.end();
1133
1134        for (it = polys.begin(); it != it_end; ++ it)
1135        {
1136                const int classification = (*it)->ClassifyPlane(candidatePlane);
1137
1138                if (sSplitPlaneStrategy & BALANCED_POLYS)
1139                        sumBalancedPolys += sBalancedPolysTable[classification];
1140               
1141                if (sSplitPlaneStrategy & LEAST_SPLITS)
1142                        sumSplits += sLeastPolySplitsTable[classification];
1143
1144                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1145                {
1146                        if (classification == Polygon3::COINCIDENT)
1147                                sumPolyArea += (*it)->GetArea();
1148                        //totalArea += area;
1149                }
1150               
1151                if (sSplitPlaneStrategy & BLOCKED_RAYS)
1152                {
1153                        const float blockedRays = (float)(*it)->mPiercingRays.size();
1154               
1155                        if (classification == Polygon3::COINCIDENT)
1156                                sumBlockedRays += blockedRays;
1157                       
1158                        totalBlockedRays += blockedRays;
1159                }
1160
1161                // assign view cells to back or front according to classificaion
1162                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1163                {
1164                        MeshInstance *viewCell = (*it)->mParent;
1165               
1166                        // assure that we only count a view cell
1167                        // once for the front and once for the back side of the plane
1168                        if (classification == Polygon3::FRONT_SIDE)
1169                        {
1170                                if ((viewCell->mMailbox != frontId) &&
1171                                        (viewCell->mMailbox != frontAndBackId))
1172                                {
1173                                        sumBalancedViewCells += 1.0;
1174
1175                                        if (viewCell->mMailbox != backId)
1176                                                viewCell->mMailbox = frontId;
1177                                        else
1178                                                viewCell->mMailbox = frontAndBackId;
1179                                       
1180                                        ++ totalViewCells;
1181                                }
1182                        }
1183                        else if (classification == Polygon3::BACK_SIDE)
1184                        {
1185                                if ((viewCell->mMailbox != backId) &&
1186                                    (viewCell->mMailbox != frontAndBackId))
1187                                {
1188                                        sumBalancedViewCells -= 1.0;
1189
1190                                        if (viewCell->mMailbox != frontId)
1191                                                viewCell->mMailbox = backId;
1192                                        else
1193                                                viewCell->mMailbox = frontAndBackId;
1194
1195                                        ++ totalViewCells;
1196                                }
1197                        }
1198                }
1199        }
1200
1201        // all values should be approx. between 0 and 1 so they can be combined
1202        // and scaled with the factors according to their importance
1203        if (sSplitPlaneStrategy & BALANCED_POLYS)
1204                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
1205
1206        if (sSplitPlaneStrategy & LEAST_SPLITS)   
1207                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
1208
1209        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1210                // HACK: polys.size should be total area so scaling is between 0 and 1
1211                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1212
1213        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1214                if (totalBlockedRays != 0)
1215                        val += sBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
1216
1217        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1218                if (totalViewCells != 0)
1219                        val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1220                                (float)totalViewCells;
1221       
1222        return val;
1223}
1224
1225bool BspTree::BoundRay(const Ray &ray, float &minT, float &maxT) const
1226{
1227        maxT = 1e6;
1228        minT = 0;
1229       
1230        // test with tree bounding box
1231        if (!mBox.GetMinMaxT(ray, &minT, &maxT))
1232                return false;
1233
1234        if (minT < 0) // start ray from origin
1235                minT = 0;
1236
1237        // bound ray or line segment
1238        if ((ray.GetType() == Ray::LOCAL_RAY) &&
1239            !ray.intersections.empty() &&
1240                (ray.intersections[0].mT <= maxT))
1241        {
1242                maxT = ray.intersections[0].mT;
1243        }
1244
1245        return true;
1246}
1247
1248float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1249                                                          const BoundedRayContainer &rays) const
1250{
1251        float val = 0;
1252
1253        float sumBalancedRays = 0;
1254        float sumRaySplits = 0;
1255        float pvsSize = 0;
1256        float totalSize = 0;
1257
1258        // need three unique ids for small pvs criterium
1259        Intersectable::NewMail();
1260        const int backId = ViewCell::sMailId;
1261        Intersectable::NewMail();
1262        const int frontId = ViewCell::sMailId;
1263        Intersectable::NewMail();
1264        const int frontAndBackId = ViewCell::sMailId;
1265        //Debug << "f " << frontId <<  " b " << backId << " fb " << frontAndBackId << endl;
1266
1267        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
1268
1269        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1270        {
1271                Ray *ray = (*rit)->mRay;
1272                const float minT = (*rit)->mMinT;
1273                const float maxT = (*rit)->mMaxT;
1274
1275                const int cf =
1276                        ray->ClassifyPlane(candidatePlane, minT, maxT);
1277
1278                if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1279                {
1280                        sumBalancedRays += sBalancedRaysTable[cf];
1281                }
1282               
1283                if (sSplitPlaneStrategy & BALANCED_RAYS)
1284                {
1285                        sumRaySplits += sLeastRaySplitsTable[cf];
1286                }
1287
1288                if (sSplitPlaneStrategy & PVS)
1289                {
1290                        vector<Ray::Intersection>::const_iterator it,
1291                                it_end = ray->intersections.end();
1292
1293                        if (!ray->intersections.empty())
1294                        {
1295
1296                                // assure that we only count a object
1297                                // once for the front and once for the back side of the plane
1298                                pvsSize += PvsValue(*ray->intersections[0].mObject,
1299                                                                        cf,
1300                                                                        frontId,
1301                                                                        backId,
1302                                                                        frontAndBackId);
1303
1304                                // always add 2 for each object (= maximal large PVS)
1305                                //if (inc > 0.01)       totalSize += 2.0;
1306                        }
1307                        //todo emerging obj
1308                }
1309        }
1310
1311        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1312                if (!rays.empty())
1313                        val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
1314
1315        if (sSplitPlaneStrategy & BALANCED_RAYS)
1316                if (!rays.empty())
1317                        val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
1318
1319        if (sSplitPlaneStrategy & PVS)
1320                if (!rays.empty()) // HACK (should be maximal possible pvs)
1321                        val += sPvsFactor * pvsSize / (float)rays.size();
1322
1323        //Debug << "pvs: " << pvsSize << " val " << val << endl;
1324        return val;
1325}
1326
1327
1328float BspTree::PvsValue(Intersectable &obj,
1329                                            const int cf,
1330                                            const int frontId,
1331                                            const int backId,
1332                                            const int frontAndBackId) const
1333{
1334        float pvsVal = 0;
1335
1336        if (cf == Ray::COINCIDENT)
1337                return pvsVal;
1338
1339        if (cf == Ray::FRONT)
1340        {
1341                if ((obj.mMailbox != frontId) &&
1342                        (obj.mMailbox != frontAndBackId))
1343                        pvsVal = 1.0;
1344
1345                if (obj.mMailbox != backId)
1346                        obj.mMailbox = frontId;
1347                else
1348                        obj.mMailbox = frontAndBackId;                                 
1349        }
1350        else if (cf == Ray::BACK)
1351        {
1352                if ((obj.mMailbox != backId) &&
1353                        (obj.mMailbox != frontAndBackId))
1354                {
1355                        pvsVal = 1.0;
1356
1357                        if (obj.mMailbox != frontId)
1358                                obj.mMailbox = backId;
1359                        else
1360                                obj.mMailbox = frontAndBackId;
1361                }
1362        }
1363        else if ((cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
1364        {
1365                if ((obj.mMailbox == backId) || (obj.mMailbox == frontId))
1366                        pvsVal = 1.0;
1367                else if (obj.mMailbox != frontAndBackId)
1368                        pvsVal = 2.0;
1369                       
1370                obj.mMailbox = frontAndBackId;
1371        }
1372
1373        return pvsVal;
1374}
1375
1376float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1377                                                          const PolygonContainer &polys,                                                         
1378                                                          const BoundedRayContainer &rays) const
1379{
1380        float val = 0;
1381
1382        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1383        {
1384                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1385                // we put a penalty on the dot product between the "tiny" vertical axis
1386                // and the split plane axis
1387                val += sVerticalSplitsFactor *
1388                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1389        }
1390
1391        // the following criteria loop over all polygons to find the cost value
1392        if ((sSplitPlaneStrategy & BALANCED_POLYS)      ||
1393                (sSplitPlaneStrategy & LEAST_SPLITS)        ||
1394                (sSplitPlaneStrategy & LARGEST_POLY_AREA)   ||
1395                (sSplitPlaneStrategy & BALANCED_VIEW_CELLS) ||
1396                (sSplitPlaneStrategy & BLOCKED_RAYS))
1397        {
1398        val += SplitPlaneCost(candidatePlane, polys);
1399        }
1400
1401        // the following criteria loop over all rays to find the cost value
1402        if ((sSplitPlaneStrategy & BALANCED_RAYS)      ||
1403                (sSplitPlaneStrategy & LEAST_RAY_SPLITS)   ||
1404                (sSplitPlaneStrategy & PVS))
1405        {
1406                val += SplitPlaneCost(candidatePlane, rays);
1407        }
1408
1409        // return linear combination of the sums
1410        return val;
1411}
1412
1413void BspTree::ParseEnvironment()
1414{
1415        //-- parse bsp cell tree construction method
1416        char constructionMethodStr[60];
1417       
1418        environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
1419
1420        sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1421       
1422        if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1423                sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1424        else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1425                sConstructionMethod = FROM_SCENE_GEOMETRY;
1426        else if (strcmp(constructionMethodStr, "fromRays") == 0)
1427                sConstructionMethod = FROM_RAYS;
1428        else
1429        {
1430                cerr << "Wrong construction method " << constructionMethodStr << endl;
1431                exit(1);
1432    }
1433
1434        Debug << "Construction method: " << constructionMethodStr << endl;
1435
1436        //-- termination criteria for autopartition
1437        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1438        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1439        environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
1440
1441        //-- termination criteria for axis aligned split
1442        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", sCt_div_ci);
1443        environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", sMaxCostRatio);
1444        environment->GetIntValue("BspTree.Termination.AxisAligned.maxPolys",
1445                                                         sTermMaxPolysForAxisAligned);
1446        environment->GetIntValue("BspTree.Termination.AxisAligned.maxRays",
1447                                                         sTermMaxRaysForAxisAligned);
1448        environment->GetIntValue("BspTree.Termination.AxisAligned.maxObjects",
1449                                                         sTermMaxObjectsForAxisAligned);
1450        //-- partition criteria
1451        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
1452        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1453        environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
1454       
1455        environment->GetBoolValue("BspTree.storeSplitPolys", sStoreSplitPolys);
1456
1457        environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
1458        Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
1459
1460        environment->GetIntValue("ViewCells.minPvsDif", sMinPvsDif);
1461
1462    Debug << "BSP max depth: " << sTermMaxDepth << endl;
1463        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1464        Debug << "BSP max candidates: " << sMaxCandidates << endl;
1465       
1466        Debug << "Split plane strategy: ";
1467        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1468                Debug << "random polygon ";
1469        if (sSplitPlaneStrategy & AXIS_ALIGNED)
1470                Debug << "axis aligned ";
1471        if (sSplitPlaneStrategy & LEAST_SPLITS)     
1472                Debug << "least splits ";
1473        if (sSplitPlaneStrategy & BALANCED_POLYS)
1474                Debug << "balanced polygons ";
1475        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1476                Debug << "balanced view cells ";
1477        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1478                Debug << "largest polygon area ";
1479        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1480                Debug << "vertical axis ";
1481        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1482                Debug << "blocked rays ";
1483        if (sSplitPlaneStrategy & PVS)
1484                Debug << "pvs";
1485        Debug << endl;
1486}
1487
1488void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
1489{
1490        stack<BspNode *> nodeStack;
1491        nodeStack.push(mRoot);
1492 
1493        while (!nodeStack.empty())
1494        {
1495                BspNode *node = nodeStack.top();
1496   
1497                nodeStack.pop();
1498   
1499                if (node->IsLeaf())
1500                {
1501                        BspLeaf *leaf = (BspLeaf *)node;
1502                       
1503                        leaves.push_back(leaf);
1504                } else
1505                {
1506                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1507
1508                        nodeStack.push(interior->GetBack());
1509                        nodeStack.push(interior->GetFront());
1510                }
1511        }
1512}
1513
1514AxisAlignedBox3 BspTree::GetBoundingBox() const
1515{
1516        return mBox;
1517}
1518
1519BspNode *BspTree::GetRoot() const
1520{
1521        return mRoot;
1522}
1523
1524void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1525{
1526        // the node became a leaf -> evaluate stats for leafs
1527        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1528
1529        if (data.mDepth >= sTermMaxDepth)
1530                ++ mStat.maxDepthNodes;
1531        // store maximal and minimal depth
1532        if (data.mDepth > mStat.maxDepth)
1533                mStat.maxDepth = data.mDepth;
1534        if (data.mDepth < mStat.minDepth)
1535                mStat.minDepth = data.mDepth;
1536
1537        // accumulate depth to compute average
1538        mStat.accumDepth += data.mDepth;
1539
1540        if (leaf->mViewCell != mRootCell)
1541        {       
1542                ++ mStat.viewCells;
1543                mStat.pvs += leaf->mViewCell->GetPvs().GetSize();
1544        }
1545       
1546#ifdef _DEBUG
1547        Debug << "BSP stats: "
1548                  << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
1549                  << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
1550                  << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << ")" << endl;
1551#endif
1552}
1553
1554int BspTree::CastRay(Ray &ray)
1555{
1556        int hits = 0;
1557 
1558        stack<BspRayTraversalData> tStack;
1559 
1560        float maxt, mint;
1561
1562        if (!BoundRay(ray, mint, maxt))
1563                return 0;
1564
1565        Intersectable::NewMail();
1566
1567        Vector3 entp = ray.Extrap(mint);
1568        Vector3 extp = ray.Extrap(maxt);
1569 
1570        BspNode *node = mRoot;
1571        BspNode *farChild = NULL;
1572       
1573        while (1)
1574        {
1575                if (!node->IsLeaf())
1576                {
1577                        BspInterior *in = (BspInterior *) node;
1578                       
1579                        Plane3 *splitPlane = in->GetPlane();
1580
1581                        int entSide = splitPlane->Side(entp);
1582                        int extSide = splitPlane->Side(extp);
1583
1584                        Vector3 intersection;
1585
1586                        if (entSide < 0)
1587                        {
1588                                node = in->GetBack();
1589
1590                                if(extSide <= 0) // plane does not split ray => no far child
1591                                        continue;
1592                                       
1593                                farChild = in->GetFront(); // plane splits ray
1594
1595                        } else if (entSide > 0)
1596                        {
1597                                node = in->GetFront();
1598
1599                                if (extSide >= 0) // plane does not split ray => no far child
1600                                        continue;
1601
1602                                farChild = in->GetBack(); // plane splits ray                   
1603                        }
1604                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
1605                        {
1606                                node = in->GetFront();
1607                                continue;
1608                        }
1609
1610                        // push data for far child
1611                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1612
1613                        // find intersection of ray segment with plane
1614                        float t;
1615                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t);
1616                        maxt *= t;
1617                       
1618                } else // reached leaf => intersection with view cell
1619                {
1620                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1621     
1622                        if (!leaf->mViewCell->Mailed())
1623                        {
1624                                ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
1625                                leaf->mViewCell->Mail();
1626                                ++ hits;
1627                        }
1628                       
1629                        //-- fetch the next far child from the stack
1630                        if (tStack.empty())
1631                                break;
1632     
1633                        entp = extp;
1634                        mint = maxt; // NOTE: need this?
1635
1636                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1637                                break;
1638
1639                        BspRayTraversalData &s = tStack.top();
1640
1641                        node = s.mNode;
1642                        extp = s.mExitPoint;
1643                        maxt = s.mMaxT;
1644
1645                        tStack.pop();
1646                }
1647        }
1648
1649        return hits;
1650}
1651
1652bool BspTree::Export(const string filename)
1653{
1654        Exporter *exporter = Exporter::GetExporter(filename);
1655
1656        if (exporter)
1657        {
1658                exporter->ExportBspTree(*this);
1659                return true;
1660        }       
1661
1662        return false;
1663}
1664
1665void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1666{
1667        stack<BspNode *> nodeStack;
1668        nodeStack.push(mRoot);
1669
1670        ViewCell::NewMail();
1671
1672        while (!nodeStack.empty())
1673        {
1674                BspNode *node = nodeStack.top();
1675                nodeStack.pop();
1676
1677                if (node->IsLeaf())
1678                {
1679                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1680
1681                        if (!viewCell->Mailed())
1682                        {
1683                                viewCell->Mail();
1684                                viewCells.push_back(viewCell);
1685                        }
1686                }
1687                else
1688                {
1689                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1690
1691                        nodeStack.push(interior->mFront);
1692                        nodeStack.push(interior->mBack);
1693                }
1694        }
1695}
1696
1697int BspTree::CountViewCellPvs() const
1698{
1699        int count = 0;
1700        stack<BspNode *> nodeStack;
1701        nodeStack.push(mRoot);
1702
1703        ViewCell::NewMail();
1704
1705        // exclude root cell
1706        mRootCell->Mail();
1707
1708        while (!nodeStack.empty())
1709        {
1710                BspNode *node = nodeStack.top();
1711                nodeStack.pop();
1712
1713                if (node->IsLeaf())
1714                {
1715                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1716
1717                        if (!viewCell->Mailed())
1718                        {
1719                                viewCell->Mail();
1720                                count += viewCell->GetPvs().GetSize();
1721                        }
1722                }
1723                else
1724                {
1725                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1726
1727                        nodeStack.push(interior->mFront);
1728                        nodeStack.push(interior->mBack);
1729                }
1730        }
1731        return count;
1732}
1733
1734bool BspTree::MergeViewCells(BspLeaf *front, BspLeaf *back) const
1735{
1736        BspViewCell *viewCell =
1737                dynamic_cast<BspViewCell *>(ViewCell::Merge(*front->mViewCell, *back->mViewCell));
1738       
1739        if (!viewCell)
1740                return false;
1741
1742        // change view cells of all leaves associated with the
1743        // previous view cells
1744
1745        BspViewCell *fVc = front->mViewCell;
1746        BspViewCell *bVc = back->mViewCell;
1747
1748        vector<BspLeaf *> fLeaves = fVc->mBspLeaves;
1749        vector<BspLeaf *> bLeaves = bVc->mBspLeaves;
1750
1751        vector<BspLeaf *>::const_iterator it;
1752       
1753        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
1754        {
1755                (*it)->SetViewCell(viewCell);
1756                viewCell->mBspLeaves.push_back(*it);
1757        }
1758        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
1759        {
1760                (*it)->SetViewCell(viewCell);
1761                viewCell->mBspLeaves.push_back(*it);
1762        }
1763       
1764        DEL_PTR(fVc);
1765        DEL_PTR(bVc);
1766
1767        return true;
1768}
1769
1770bool BspTree::ShouldMerge(BspLeaf *front, BspLeaf *back) const
1771{
1772        ViewCell *fvc = front->mViewCell;
1773        ViewCell *bvc = back->mViewCell;
1774
1775        if ((fvc == mRootCell) || (bvc == mRootCell) || (fvc == bvc))
1776                return false;
1777
1778        /*Debug << "merge (" << sMinPvsDif << ")" << endl;
1779        Debug << "size f: " << fvc->GetPvs().GetSize() << ", "
1780                  << "size b: " << bvc->GetPvs().GetSize() << endl;
1781       
1782        Debug << "diff f: " << fvc->GetPvs().Diff(bvc->GetPvs()) << ", "
1783                  << "diff b: " << bvc->GetPvs().Diff(fvc->GetPvs()) << endl;*/
1784
1785    if ((fvc->GetPvs().Diff(bvc->GetPvs()) < sMinPvsDif) &&
1786            (bvc->GetPvs().Diff(fvc->GetPvs()) < sMinPvsDif))
1787                return true;
1788
1789        return false;
1790}
1791
1792void BspTree::SetGenerateViewCells(int generateViewCells)
1793{
1794        mGenerateViewCells = generateViewCells;
1795}
1796
1797BspTreeStatistics &BspTree::GetStat()
1798{
1799        return mStat;
1800}
1801
1802int BspTree::SplitRays(const Plane3 &plane,
1803                                           BoundedRayContainer &rays,
1804                                           BoundedRayContainer &frontRays,
1805                                           BoundedRayContainer &backRays)
1806{
1807        int splits = 0;
1808
1809        while (!rays.empty())
1810        {
1811                BoundedRay *bRay = rays.back();
1812                Ray *ray = bRay->mRay;
1813                rays.pop_back();
1814               
1815                const int cf =
1816                        ray->ClassifyPlane(plane, bRay->mMinT, bRay->mMaxT);
1817               
1818                ray->SetId(cf);
1819
1820                switch (cf)
1821                {
1822                case Ray::COINCIDENT:
1823                        frontRays.push_back(bRay);
1824                        break;
1825                case Ray::BACK:
1826                        backRays.push_back(bRay);
1827                        break;
1828                case Ray::FRONT:
1829                        frontRays.push_back(bRay);
1830                        break;
1831                case Ray::FRONT_BACK:
1832                        {
1833                                // find intersection of ray segment with plane
1834                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
1835                                const float t = plane.FindT(ray->GetLoc(), extp);
1836                               
1837                                const float newT = t * bRay->mMaxT;
1838
1839                                frontRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
1840                                backRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
1841
1842                                DEL_PTR(bRay);
1843
1844                                ++ splits;
1845                        }
1846                        break;
1847                case Ray::BACK_FRONT:
1848                        {
1849                                // find intersection of ray segment with plane
1850                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
1851                                const float t = plane.FindT(ray->GetLoc(), extp);
1852                                const float newT = t * bRay->mMaxT;
1853
1854                                backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
1855                                frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
1856                               
1857                                DEL_PTR(bRay);
1858
1859                                ++ splits;
1860                        }
1861                        break;
1862                default:
1863                        Debug << "Should not come here" << endl;
1864                        break;
1865                }
1866        }
1867
1868        return splits;
1869}
1870
1871void BspTree::ExtractSplitPlanes(BspNode *n,
1872                                                                 vector<Plane3 *> &planes,
1873                                                                 vector<bool> &sides) const
1874{
1875        BspNode *lastNode;
1876        do
1877        {
1878                lastNode = n;
1879
1880                // want to get planes defining geometry of this node => don't take
1881                // split plane of node itself
1882                n = n->GetParent();
1883               
1884                if (n)
1885                {
1886                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
1887
1888                        planes.push_back(dynamic_cast<BspInterior *>(interior)->GetPlane());
1889                        sides.push_back(interior->mFront == lastNode);
1890                }
1891        }
1892        while (n);
1893}
1894
1895struct Candidate
1896{
1897        Polygon3 *mPoly;
1898        Plane3 mPlane;
1899        bool mSide;
1900
1901        Candidate(Polygon3 *poly, const Plane3 &plane, const bool &side):
1902        mPoly(poly), mPlane(plane), mSide(side)
1903        {}
1904};
1905
1906void BspTree::AddHalfspace(PolygonContainer &cell,
1907                                                   vector<Plane3> &planes,
1908                                                   vector<bool> &sides,
1909                                                   const Plane3 &halfspace,
1910                                                   const bool side) const
1911{
1912        Polygon3 *poly = GetBoundingBox().CrossSection(halfspace);
1913
1914        bool inside = true;
1915
1916        // polygon is split by all other planes
1917        for (int i = 0; (i < planes.size()) && inside; ++ i)
1918        {
1919                VertexContainer splitPts;
1920                Polygon3 *frontPoly, *backPoly;
1921
1922                const int cf = poly->ClassifyPlane(planes[i]);
1923                       
1924                // split new polygon with all previous planes
1925                switch (cf)
1926                {
1927                        case Polygon3::SPLIT:
1928                                frontPoly = new Polygon3();
1929                                backPoly = new Polygon3();
1930
1931                                poly->Split(planes[i], *frontPoly, *backPoly, splitPts);
1932                                DEL_PTR(poly);
1933
1934                                if(sides[i] == true)
1935                                {
1936                                        poly = frontPoly;
1937                                        DEL_PTR(backPoly);
1938                                }
1939                                        else
1940                                        {
1941                                                poly = backPoly;
1942                                                DEL_PTR(frontPoly);
1943                                        }
1944                                        inside = true;
1945                                        break;
1946                        case Polygon3::BACK_SIDE:
1947                                if (sides[i])
1948                                        inside = false;
1949                                break;
1950                        case Polygon3::FRONT_SIDE:
1951                                if (!sides[i])
1952                                        inside = false;
1953                                break;
1954                        default:
1955                                break;
1956                }
1957        }
1958
1959        //-- plane poly splits all other candidates
1960
1961    // some polygons may fall out => rebuild cell
1962        vector<Candidate> candidates;
1963
1964        for (int i = 0; i < (int)cell.size(); ++ i)
1965        {
1966                candidates.push_back(Candidate(cell[i], planes[i], sides[i]));
1967        }
1968
1969        cell.clear();
1970        planes.clear();
1971        sides.clear();
1972
1973        for (int i = 0; i < (int)candidates.size(); ++ i)
1974        {
1975                bool candidateInside = true;
1976
1977                VertexContainer splitPts;
1978                Polygon3 *frontPoly, *backPoly;
1979
1980                const int cf = poly->ClassifyPlane(halfspace);
1981                       
1982                // split new polygon with all previous planes
1983                switch (cf)
1984                {
1985                        case Polygon3::SPLIT:
1986                                frontPoly = new Polygon3();
1987                                backPoly = new Polygon3();
1988
1989                                poly->Split(halfspace, *frontPoly, *backPoly, splitPts);
1990                                DEL_PTR(candidates[i].mPoly);
1991
1992                                if (sides[i] == true)
1993                                {
1994                                        candidates[i].mPoly = frontPoly;
1995                                        DEL_PTR(backPoly);
1996                                }
1997                                else
1998                                {
1999                                        candidates[i].mPoly = backPoly;
2000                                        DEL_PTR(frontPoly);
2001                                }
2002                                inside = true;
2003                                break;
2004                        case Polygon3::BACK_SIDE:
2005                                if (candidates[i].mSide)
2006                                        candidateInside = false;
2007                                break;
2008                        case Polygon3::FRONT_SIDE:
2009                                if (!candidates[i].mSide)
2010                                        candidateInside = false;
2011                                break;
2012                        default:
2013                                break;
2014                }
2015               
2016                if (candidateInside)
2017                {
2018                        cell.push_back(candidates[i].mPoly);
2019                        sides.push_back(candidates[i].mSide);
2020                        planes.push_back(candidates[i].mPlane);
2021                }
2022                else
2023                {
2024                        DEL_PTR(candidates[i].mPoly);
2025                }
2026        }
2027
2028        //-- finally add polygon
2029        if (inside)
2030        {
2031                cell.push_back(poly);
2032                planes.push_back(halfspace);
2033                sides.push_back(side);
2034        }
2035        else
2036        {
2037                DEL_PTR(poly);
2038        }
2039}
2040
2041
2042void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
2043{
2044        stack<BspNode *> tStack;
2045
2046        vector<Plane3 *> planes;
2047        vector<bool> sides;
2048
2049        ExtractSplitPlanes(n, planes, sides);
2050
2051        PolygonContainer candidatePolys;
2052
2053        // bounded planes are added to the polygons
2054        for (int i = 0; i < (int)planes.size(); ++ i)
2055        {
2056                candidatePolys.push_back(GetBoundingBox().CrossSection(*planes[i]));
2057        }
2058
2059        // add faces of bounding box (also could be faces of the cell)
2060        for (int i = 0; i < 6; ++ i)
2061        {
2062                VertexContainer vertices;
2063       
2064                for (int j = 0; j < 4; ++ j)
2065                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
2066
2067                candidatePolys.push_back(new Polygon3(vertices));
2068        }
2069
2070        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2071        {
2072                bool inside = true;
2073
2074                // polygon is split by all other planes
2075                for (int j = 0; (j < planes.size()) && inside; ++ j)
2076                {
2077                        Plane3 *plane = planes[j];
2078
2079                        if (i == j) // same plane
2080                                continue;
2081
2082                        VertexContainer splitPts;
2083                        Polygon3 *frontPoly, *backPoly;
2084
2085                        const int cf = candidatePolys[i]->ClassifyPlane(*plane);
2086                       
2087                        switch (cf)
2088                        {
2089                                case Polygon3::SPLIT:
2090                                        frontPoly = new Polygon3();
2091                                        backPoly = new Polygon3();
2092
2093                                        candidatePolys[i]->Split(*plane, *frontPoly,
2094                                                                                         *backPoly, splitPts);
2095                                        DEL_PTR(candidatePolys[i]);
2096
2097                                        if(sides[j] == true)
2098                                        {
2099                                                candidatePolys[i] = frontPoly;
2100                                                DEL_PTR(backPoly);
2101                                        }
2102                                        else
2103                                        {
2104                                                candidatePolys[i] = backPoly;
2105                                                DEL_PTR(frontPoly);
2106                                        }
2107                                        inside = true;
2108                                        break;
2109
2110                                case Polygon3::BACK_SIDE:
2111                                        if (sides[j])
2112                                                inside = false;
2113                                        break;
2114                                case Polygon3::FRONT_SIDE:
2115                                        if (!sides[j])
2116                                                inside = false;
2117                                        break;
2118                                default:
2119                                        break;
2120                        }
2121                }
2122               
2123                if (inside)
2124                        cell.push_back(candidatePolys[i]);
2125                else
2126                        DEL_PTR(candidatePolys[i]);
2127        }
2128}
2129
2130void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
2131{
2132        vector<BspLeaf *> leaves = vc->mBspLeaves;
2133
2134        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2135
2136        for (it = leaves.begin(); it != it_end; ++ it)
2137                ConstructGeometry(*it, cell);
2138}
2139
2140int BspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
2141                                                   const bool onlyUnmailed) const
2142{
2143        PolygonContainer cell;
2144
2145        ConstructGeometry(n, cell);
2146
2147        stack<BspNode *> nodeStack;
2148        nodeStack.push(mRoot);
2149               
2150        // planes needed to verify that we found neighbor leaf.
2151        vector<Plane3 *> planes;
2152        vector<bool> sides;
2153
2154        ExtractSplitPlanes(n, planes, sides);
2155
2156        while (!nodeStack.empty())
2157        {
2158                BspNode *node = nodeStack.top();
2159                nodeStack.pop();
2160
2161                if (node->IsLeaf())
2162                {
2163            if (node != n && (!onlyUnmailed || !node->Mailed()))
2164                        {
2165                                // test all planes of current node on neighbour
2166                                PolygonContainer neighborCandidate;
2167                                ConstructGeometry(node, neighborCandidate);
2168                               
2169                                bool isAdjacent = true;
2170                                for (int i = 0; (i < planes.size()) && isAdjacent; ++ i)
2171                                {
2172                                        const int cf =
2173                                                Polygon3::ClassifyPlane(neighborCandidate, *planes[i]);
2174
2175                                        if ((cf == Polygon3::BACK_SIDE) && sides[i])
2176                                                isAdjacent = false;
2177                                        else if ((cf == Polygon3::FRONT_SIDE) && !sides[i])
2178                                                isAdjacent = false;
2179                                }
2180
2181                                if (isAdjacent)
2182                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2183
2184                                CLEAR_CONTAINER(neighborCandidate);
2185                        }
2186                }
2187                else
2188                {
2189                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2190       
2191                        const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
2192
2193                        if (cf == Polygon3::FRONT_SIDE)
2194                                nodeStack.push(interior->mFront);
2195                        else
2196                                if (cf == Polygon3::BACK_SIDE)
2197                                        nodeStack.push(interior->mBack);
2198                                else
2199                                {
2200                                        // random decision
2201                                        nodeStack.push(interior->mBack);
2202                                        nodeStack.push(interior->mFront);
2203                                }
2204                }
2205        }
2206       
2207        CLEAR_CONTAINER(cell);
2208        return (int)neighbors.size();
2209}
2210
2211BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
2212{
2213    stack<BspNode *> nodeStack;
2214        nodeStack.push(mRoot);
2215       
2216        int mask = rand();
2217 
2218        while (!nodeStack.empty())
2219        {
2220                BspNode *node = nodeStack.top();
2221                nodeStack.pop();
2222         
2223                if (node->IsLeaf())
2224                {
2225                        return dynamic_cast<BspLeaf *>(node);
2226                }
2227                else
2228                {
2229                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2230                       
2231                        BspNode *next;
2232       
2233                        PolygonContainer cell;
2234
2235                        // todo: not very efficient: constructs full cell everytime
2236                        ConstructGeometry(interior, cell);
2237
2238                        const int cf = Polygon3::ClassifyPlane(cell, halfspace);
2239
2240                        if (cf == Polygon3::BACK_SIDE)
2241                                next = interior->mFront;
2242                        else
2243                                if (cf == Polygon3::FRONT_SIDE)
2244                                        next = interior->mFront;
2245                        else
2246                        {
2247                                // random decision
2248                                if (mask & 1)
2249                                        next = interior->mBack;
2250                                else
2251                                        next = interior->mFront;
2252                                mask = mask >> 1;
2253                        }
2254
2255                        nodeStack.push(next);
2256                }
2257        }
2258       
2259        return NULL;
2260}
2261
2262BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
2263{
2264        stack<BspNode *> nodeStack;
2265       
2266        nodeStack.push(mRoot);
2267
2268        int mask = rand();
2269       
2270        while (!nodeStack.empty())
2271        {
2272                BspNode *node = nodeStack.top();
2273                nodeStack.pop();
2274               
2275                if (node->IsLeaf())
2276                {
2277                        if ( (!onlyUnmailed || !node->Mailed()) )
2278                                return dynamic_cast<BspLeaf *>(node);
2279                }
2280                else
2281                {
2282                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2283
2284                        // random decision
2285                        if (mask & 1)
2286                                nodeStack.push(interior->mBack);
2287                        else
2288                                nodeStack.push(interior->mFront);
2289
2290                        mask = mask >> 1;
2291                }
2292        }
2293       
2294        return NULL;
2295}
2296
2297int BspTree::CountPvs(const BoundedRayContainer &rays) const
2298{
2299        int pvsSize = 0;
2300
2301        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
2302        vector<Ray::BspIntersection>::const_iterator iit;
2303
2304        ViewCell::NewMail();
2305
2306        for (rit = rays.begin(); rit != rit_end; ++ rit)
2307        {
2308                Ray *ray = (*rit)->mRay;
2309               
2310                for (iit = ray->bspIntersections.begin(); iit != ray->bspIntersections.end(); ++ iit)
2311                {
2312                        BspViewCell *vc = (*iit).mLeaf->mViewCell;
2313
2314                        if (vc->Mailed())
2315                        {
2316                                pvsSize += vc->GetPvs().GetSize();
2317                        }
2318                }
2319        }
2320
2321        return pvsSize;
2322}
Note: See TracBrowser for help on using the repository browser.