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

Revision 375, 55.8 KB checked in by mattausch, 19 years ago (diff)

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