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

Revision 367, 54.6 KB checked in by mattausch, 19 years ago (diff)

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