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

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