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

Revision 389, 59.2 KB checked in by mattausch, 19 years ago (diff)

changed bsp castray
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                return polys[Random((int)polys.size())]->GetSupportingPlane();
1087        }
1088
1089        // use heuristics to find appropriate plane
1090        return SelectPlaneHeuristics(leaf, polys, rays, sMaxPolyCandidates,
1091                                                                 sMaxRayCandidates);
1092}
1093
1094Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf,
1095                                                                          PolygonContainer &polys,
1096                                                                          const BoundedRayContainer &rays,
1097                                                                          const int maxPolyCandidates,
1098                                                                          const int maxRayCandidates)
1099{
1100        float lowestCost = MAX_FLOAT;
1101        int bestPlaneIdx = 0;
1102       
1103        int limit = maxPolyCandidates > 0 ?
1104                Min((int)polys.size(), maxPolyCandidates) : (int)polys.size();
1105       
1106        int candidateIdx = limit;
1107
1108        // only for pvs criterium
1109        PolygonContainer cell;
1110        vector<Plane3 *> planes;
1111        vector<bool> sides;
1112        int pvsSize = 0;
1113
1114        if (sSplitPlaneStrategy & PVS)
1115        {
1116                ConstructGeometry(leaf, cell);
1117                ExtractSplitPlanes(leaf, planes, sides);
1118                pvsSize = ComputePvsSize(rays);
1119        }
1120
1121        for (int i = 0; i < limit; ++ i)
1122        {
1123                candidateIdx = GetNextCandidateIdx(candidateIdx, polys);
1124               
1125                // evaluate current candidate
1126                const float candidateCost =
1127                        SplitPlaneCost(polys[candidateIdx]->GetSupportingPlane(),
1128                                                   polys, rays, cell, planes, sides, pvsSize);
1129
1130                //Debug << polys[candidateIdx] << endl;
1131                if (candidateCost < lowestCost)
1132                {
1133                        bestPlaneIdx = candidateIdx;
1134                        lowestCost = candidateCost;
1135                }
1136        }
1137       
1138        //limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();
1139        bool chooseFromRays = false;
1140        int bestIdx[3];
1141
1142        for (int i = 0; i < maxRayCandidates; ++ i)
1143        {
1144                Vector3 pt[3];
1145                int idx[3];
1146
1147                for (int j = 0; j < 3; j ++)
1148                {
1149                        idx[j] = Random((int)rays.size() * 2);
1150                               
1151                        if (idx[j] < (int)rays.size())
1152                                pt[j] = rays[idx[j]]->mRay->Extrap(rays[idx[j]]->mMinT);
1153                        else
1154                        {
1155                                idx[j] -= (int)rays.size();
1156                                pt[j] = rays[idx[j]]->mRay->Extrap(rays[idx[j]]->mMaxT);
1157                        }
1158                                       
1159                }
1160
1161                const float candidateCost =
1162                        SplitPlaneCost(Plane3(pt[0], pt[1], pt[2]),
1163                                                   polys, rays, cell, planes, sides, pvsSize);
1164
1165                if (candidateCost < lowestCost)
1166                {
1167                        chooseFromRays = true;
1168                        bestIdx[0] = idx[0]; bestIdx[1]= idx[1]; bestIdx[2] = idx[2];
1169                       
1170                        lowestCost = candidateCost;
1171                }
1172        }
1173
1174        CLEAR_CONTAINER(cell);
1175
1176        if (chooseFromRays)
1177        {
1178                Debug << "choose ray plane: " << lowestCost << endl;
1179                return Plane3(rays[bestIdx[0]]->mRay->Extrap(rays[bestIdx[0]]->mMaxT),
1180                                          rays[bestIdx[1]]->mRay->Extrap(rays[bestIdx[1]]->mMaxT),
1181                                          rays[bestIdx[2]]->mRay->Extrap(rays[bestIdx[2]]->mMaxT));
1182        }
1183
1184        //Debug << "Plane lowest cost: " << lowestCost << endl;
1185        return polys[bestPlaneIdx]->GetSupportingPlane();
1186}
1187
1188int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
1189{
1190        const int candidateIdx = Random(currentIdx --);
1191
1192        // swap candidates to avoid testing same plane 2 times
1193        std::swap(polys[currentIdx], polys[candidateIdx]);
1194       
1195        return currentIdx;
1196        //return Random((int)polys.size());
1197}
1198
1199float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1200                                                          const PolygonContainer &polys) const
1201{
1202        float val = 0;
1203
1204        float sumBalancedPolys = 0;
1205        float sumSplits = 0;
1206        float sumPolyArea = 0;
1207        float sumBalancedViewCells = 0;
1208        float sumBlockedRays = 0;
1209        float totalBlockedRays = 0;
1210        //float totalArea = 0;
1211        int totalViewCells = 0;
1212
1213        // need three unique ids for each type of view cell
1214        // for balanced view cells criterium
1215        ViewCell::NewMail();
1216        const int backId = ViewCell::sMailId;
1217        ViewCell::NewMail();
1218        const int frontId = ViewCell::sMailId;
1219        ViewCell::NewMail();
1220        const int frontAndBackId = ViewCell::sMailId;
1221
1222        PolygonContainer::const_iterator it, it_end = polys.end();
1223
1224        for (it = polys.begin(); it != it_end; ++ it)
1225        {
1226                const int classification = (*it)->ClassifyPlane(candidatePlane);
1227
1228                if (sSplitPlaneStrategy & BALANCED_POLYS)
1229                        sumBalancedPolys += sBalancedPolysTable[classification];
1230               
1231                if (sSplitPlaneStrategy & LEAST_SPLITS)
1232                        sumSplits += sLeastPolySplitsTable[classification];
1233
1234                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1235                {
1236                        if (classification == Polygon3::COINCIDENT)
1237                                sumPolyArea += (*it)->GetArea();
1238                        //totalArea += area;
1239                }
1240               
1241                if (sSplitPlaneStrategy & BLOCKED_RAYS)
1242                {
1243                        const float blockedRays = (float)(*it)->mPiercingRays.size();
1244               
1245                        if (classification == Polygon3::COINCIDENT)
1246                                sumBlockedRays += blockedRays;
1247                       
1248                        totalBlockedRays += blockedRays;
1249                }
1250
1251                // assign view cells to back or front according to classificaion
1252                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1253                {
1254                        MeshInstance *viewCell = (*it)->mParent;
1255               
1256                        // assure that we only count a view cell
1257                        // once for the front and once for the back side of the plane
1258                        if (classification == Polygon3::FRONT_SIDE)
1259                        {
1260                                if ((viewCell->mMailbox != frontId) &&
1261                                        (viewCell->mMailbox != frontAndBackId))
1262                                {
1263                                        sumBalancedViewCells += 1.0;
1264
1265                                        if (viewCell->mMailbox != backId)
1266                                                viewCell->mMailbox = frontId;
1267                                        else
1268                                                viewCell->mMailbox = frontAndBackId;
1269                                       
1270                                        ++ totalViewCells;
1271                                }
1272                        }
1273                        else if (classification == Polygon3::BACK_SIDE)
1274                        {
1275                                if ((viewCell->mMailbox != backId) &&
1276                                    (viewCell->mMailbox != frontAndBackId))
1277                                {
1278                                        sumBalancedViewCells -= 1.0;
1279
1280                                        if (viewCell->mMailbox != frontId)
1281                                                viewCell->mMailbox = backId;
1282                                        else
1283                                                viewCell->mMailbox = frontAndBackId;
1284
1285                                        ++ totalViewCells;
1286                                }
1287                        }
1288                }
1289        }
1290
1291        // all values should be approx. between 0 and 1 so they can be combined
1292        // and scaled with the factors according to their importance
1293        if (sSplitPlaneStrategy & BALANCED_POLYS)
1294                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
1295       
1296        if (sSplitPlaneStrategy & LEAST_SPLITS)   
1297                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
1298
1299        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1300                // HACK: polys.size should be total area so scaling is between 0 and 1
1301                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1302
1303        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1304                if (totalBlockedRays != 0)
1305                        val += sBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
1306
1307        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1308                if (totalViewCells != 0)
1309                        val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) / (float)totalViewCells;
1310       
1311        return val;
1312}
1313
1314bool BspTree::BoundRay(const Ray &ray, float &minT, float &maxT) const
1315{
1316        maxT = 1e6;
1317        minT = 0;
1318       
1319        // test with tree bounding box
1320        if (!mBox.GetMinMaxT(ray, &minT, &maxT))
1321                return false;
1322
1323        if (minT < 0) // start ray from origin
1324                minT = 0;
1325
1326        // bound ray or line segment
1327        if ((ray.GetType() == Ray::LOCAL_RAY) &&
1328            !ray.intersections.empty() &&
1329                (ray.intersections[0].mT <= maxT))
1330        {
1331                maxT = ray.intersections[0].mT;
1332        }
1333
1334        return true;
1335}
1336
1337float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1338                                                          const BoundedRayContainer &rays,
1339                                                          const float frontArea,
1340                                                          const float backArea,
1341                                                          const int pvsSize) const
1342{
1343        float val = 0;
1344
1345        float sumBalancedRays = 0;
1346        float sumRaySplits = 0;
1347        float frontPvs = 0;
1348        float backPvs = 0;
1349
1350        float totalSize = 0;
1351       
1352        // create three unique ids for pvs heuristics
1353        Intersectable::NewMail(); const int backId = ViewCell::sMailId;
1354        Intersectable::NewMail(); const int frontId = ViewCell::sMailId;
1355        Intersectable::NewMail(); const int frontAndBackId = ViewCell::sMailId;
1356
1357        int frontRays = 0;
1358        int backRays = 0;
1359               
1360        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
1361
1362        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1363        {
1364                Ray *ray = (*rit)->mRay;
1365                const float minT = (*rit)->mMinT;
1366                const float maxT = (*rit)->mMaxT;
1367
1368                const int cf =
1369                        ray->ClassifyPlane(candidatePlane, minT, maxT);
1370
1371                if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1372                {
1373                        sumBalancedRays += sBalancedRaysTable[cf];
1374                }
1375               
1376                if (sSplitPlaneStrategy & BALANCED_RAYS)
1377                {
1378                        sumRaySplits += sLeastRaySplitsTable[cf];
1379                }
1380
1381                if (sSplitPlaneStrategy & PVS)
1382                {
1383                        if (!ray->intersections.empty())
1384                        {
1385                                // in case the ray intersects an objcrs
1386                                // assure that we only count a object
1387                                // once for the front and once for the back side of the plane
1388                                AddToPvs(*ray->intersections[0].mObject,
1389                                                   frontPvs, backPvs,
1390                                                   cf, frontId, backId, frontAndBackId);
1391                        }
1392
1393                        // the source object in the origin of the ray
1394                        AddToPvs(*ray->sourceObject.mObject,
1395                                           frontPvs, backPvs,
1396                                           cf, frontId, backId, frontAndBackId);
1397
1398                        if (0)
1399                        {
1400                                if ((cf == Ray::BACK) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
1401                                        ++ backRays;
1402                                if ((cf == Ray::FRONT) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
1403                                        ++ frontRays;
1404                        }
1405                }
1406        }
1407
1408        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1409                if (!rays.empty())
1410                        val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
1411
1412        if (sSplitPlaneStrategy & BALANCED_RAYS)
1413                if (!rays.empty())
1414                        val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
1415
1416        if (sSplitPlaneStrategy & PVS)
1417                if (0 && !rays.empty()) // HACK (should divide by maximal possible pvs)
1418                        val += sPvsFactor * (frontPvs * (float)frontRays + (backPvs * (float)backRays)) / (float)rays.size();
1419                else
1420                        val += sPvsFactor * (frontPvs * frontArea + (backPvs * backArea)) /
1421                                ((frontArea + backArea) * (float)pvsSize);
1422
1423        //Debug << "pvs: " << pvsSize << " val " << val << endl;
1424        return val;
1425}
1426
1427void BspTree::AddToPvs(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) //TODO: really belongs to no pvs?
1436                return;
1437
1438        if (cf == Ray::FRONT)
1439        {
1440                if ((obj.mMailbox != frontId) &&
1441                        (obj.mMailbox != frontAndBackId))
1442                {
1443                        frontPvs += 1.0;
1444
1445                        if (obj.mMailbox != backId)
1446                                obj.mMailbox = frontId;
1447                        else
1448                                obj.mMailbox = frontAndBackId;                                 
1449                }
1450        }
1451        else if (cf == Ray::BACK)
1452        {
1453                if ((obj.mMailbox != backId) &&
1454                        (obj.mMailbox != frontAndBackId))
1455                {
1456                        backPvs += 1.0;
1457
1458                        if (obj.mMailbox != frontId)
1459                                obj.mMailbox = backId;
1460                        else
1461                                obj.mMailbox = frontAndBackId;
1462                }
1463        }
1464        // object belongs to both pvs
1465        else if ((cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
1466        {
1467                if (obj.mMailbox !=  frontAndBackId)
1468                {
1469                        if (obj.mMailbox != frontId)
1470                                frontPvs += 1.0;
1471                        if (obj.mMailbox != backId)
1472                                backPvs += 1.0;
1473               
1474                        obj.mMailbox = frontAndBackId;
1475                }
1476        }
1477}
1478
1479float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1480                                                          const PolygonContainer &polys,                                                         
1481                                                          const BoundedRayContainer &rays,
1482                                                          const PolygonContainer &cell,
1483                                                          const vector<Plane3 *> &planes,
1484                                                          const vector<bool> &sides,
1485                                                          const int pvsSize) const
1486{
1487        float val = 0;
1488
1489        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1490        {
1491                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1492                // we put a penalty on the dot product between the "tiny" vertical axis
1493                // and the split plane axis
1494                val += sVerticalSplitsFactor *
1495                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1496        }
1497
1498        // the following criteria loop over all polygons to find the cost value
1499        if ((sSplitPlaneStrategy & BALANCED_POLYS)      ||
1500                (sSplitPlaneStrategy & LEAST_SPLITS)        ||
1501                (sSplitPlaneStrategy & LARGEST_POLY_AREA)   ||
1502                (sSplitPlaneStrategy & BALANCED_VIEW_CELLS) ||
1503                (sSplitPlaneStrategy & BLOCKED_RAYS))
1504        {
1505        val += SplitPlaneCost(candidatePlane, polys);
1506        }
1507
1508        // the following criteria loop over all rays to find the cost value
1509        if ((sSplitPlaneStrategy & BALANCED_RAYS)      ||
1510                (sSplitPlaneStrategy & LEAST_RAY_SPLITS)   ||
1511                (sSplitPlaneStrategy & PVS))
1512        {
1513                float frontArea = 0;
1514                float backArea = 0;
1515
1516                if (sSplitPlaneStrategy & PVS)
1517                {
1518                        PolygonContainer frontCell;
1519                        PolygonContainer backCell;
1520
1521                        // construct child geometry with regard to the candidate split plane
1522                        ConstructChildGeometry(frontCell, cell, planes, sides, candidatePlane, true);
1523                        ConstructChildGeometry(backCell, cell, planes, sides, candidatePlane, false);
1524
1525                        frontArea = Polygon3::GetArea(frontCell);
1526                        backArea = Polygon3::GetArea(backCell);
1527
1528                        CLEAR_CONTAINER(frontCell);
1529                        CLEAR_CONTAINER(backCell);
1530                }
1531               
1532                val += SplitPlaneCost(candidatePlane, rays, frontArea, backArea, pvsSize);
1533        }
1534
1535        // return linear combination of the sums
1536        return val;
1537}
1538
1539void BspTree::ParseEnvironment()
1540{
1541        //-- parse bsp cell tree construction method
1542        char constructionMethodStr[60];
1543       
1544        environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
1545
1546        sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1547       
1548        if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1549                sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1550        else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1551                sConstructionMethod = FROM_SCENE_GEOMETRY;
1552        else if (strcmp(constructionMethodStr, "fromRays") == 0)
1553                sConstructionMethod = FROM_RAYS;
1554        else
1555        {
1556                cerr << "Wrong construction method " << constructionMethodStr << endl;
1557                exit(1);
1558    }
1559
1560        Debug << "Construction method: " << constructionMethodStr << endl;
1561
1562        //-- termination criteria for autopartition
1563        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1564        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1565        environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
1566
1567        //-- termination criteria for axis aligned split
1568        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", sCt_div_ci);
1569        environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", sMaxCostRatio);
1570        environment->GetIntValue("BspTree.Termination.AxisAligned.maxPolys",
1571                                                         sTermMaxPolysForAxisAligned);
1572        environment->GetIntValue("BspTree.Termination.AxisAligned.maxRays",
1573                                                         sTermMaxRaysForAxisAligned);
1574        environment->GetIntValue("BspTree.Termination.AxisAligned.maxObjects",
1575                                                         sTermMaxObjectsForAxisAligned);
1576        //-- partition criteria
1577        environment->GetIntValue("BspTree.maxPolyCandidates", sMaxPolyCandidates);
1578        environment->GetIntValue("BspTree.maxRayCandidates", sMaxRayCandidates);
1579        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1580        environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
1581       
1582        environment->GetBoolValue("BspTree.Visualization.storePolys", sStoreSplitPolys);
1583
1584        environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
1585        Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
1586
1587        // post processing stuff
1588        environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", sMinPvsDif);
1589        environment->GetIntValue("ViewCells.PostProcessing.minPvs", sMinPvs);
1590        environment->GetIntValue("ViewCells.PostProcessing.maxPvs", sMaxPvs);
1591
1592    Debug << "BSP max depth: " << sTermMaxDepth << endl;
1593        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1594        Debug << "BSP max rays: " << sTermMaxRays << endl;
1595        Debug << "BSP max polygon candidates: " << sMaxPolyCandidates << endl;
1596        Debug << "BSP max plane candidates: " << sMaxRayCandidates << endl;
1597
1598        Debug << "Split plane strategy: ";
1599        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1600                Debug << "random polygon ";
1601        if (sSplitPlaneStrategy & AXIS_ALIGNED)
1602                Debug << "axis aligned ";
1603        if (sSplitPlaneStrategy & LEAST_SPLITS)     
1604                Debug << "least splits ";
1605        if (sSplitPlaneStrategy & BALANCED_POLYS)
1606                Debug << "balanced polygons ";
1607        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1608                Debug << "balanced view cells ";
1609        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1610                Debug << "largest polygon area ";
1611        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1612                Debug << "vertical axis ";
1613        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1614                Debug << "blocked rays ";
1615        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1616                Debug << "least ray splits ";
1617        if (sSplitPlaneStrategy & BALANCED_RAYS)
1618                Debug << "balanced rays ";
1619        if (sSplitPlaneStrategy & PVS)
1620                Debug << "pvs";
1621        Debug << endl;
1622}
1623
1624void BspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1625{
1626        stack<BspNode *> nodeStack;
1627        nodeStack.push(mRoot);
1628 
1629        while (!nodeStack.empty())
1630        {
1631                BspNode *node = nodeStack.top();
1632   
1633                nodeStack.pop();
1634   
1635                if (node->IsLeaf())
1636                {
1637                        BspLeaf *leaf = (BspLeaf *)node;               
1638                        leaves.push_back(leaf);
1639                }
1640                else
1641                {
1642                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1643
1644                        nodeStack.push(interior->GetBack());
1645                        nodeStack.push(interior->GetFront());
1646                }
1647        }
1648}
1649
1650AxisAlignedBox3 BspTree::GetBoundingBox() const
1651{
1652        return mBox;
1653}
1654
1655BspNode *BspTree::GetRoot() const
1656{
1657        return mRoot;
1658}
1659
1660void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1661{
1662        // the node became a leaf -> evaluate stats for leafs
1663        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1664
1665        if (data.mDepth >= sTermMaxDepth)
1666                ++ mStat.maxDepthNodes;
1667       
1668        // store maximal and minimal depth
1669        if (data.mDepth > mStat.maxDepth)
1670                mStat.maxDepth = data.mDepth;
1671
1672        if (data.mDepth < mStat.minDepth)
1673                mStat.minDepth = data.mDepth;
1674
1675        // accumulate depth to compute average
1676        mStat.accumDepth += data.mDepth;
1677       
1678//#ifdef _DEBUG
1679        Debug << "BSP stats: "
1680                  << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
1681                  << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
1682                  << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << "), "
1683                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << endl;
1684//#endif
1685}
1686
1687int BspTree::CastRay(Ray &ray)
1688{
1689        int hits = 0;
1690 
1691        stack<BspRayTraversalData> tStack;
1692 
1693        float maxt, mint;
1694
1695        if (!BoundRay(ray, mint, maxt))
1696                return 0;
1697
1698        Intersectable::NewMail();
1699
1700        Vector3 entp = ray.Extrap(mint);
1701        Vector3 extp = ray.Extrap(maxt);
1702 
1703        BspNode *node = mRoot;
1704        BspNode *farChild = NULL;
1705       
1706        while (1)
1707        {
1708                if (!node->IsLeaf())
1709                {
1710                        BspInterior *in = (BspInterior *) node;
1711                       
1712                        Plane3 *splitPlane = in->GetPlane();
1713
1714                        int entSide = splitPlane->Side(entp);
1715                        int extSide = splitPlane->Side(extp);
1716
1717                        Vector3 intersection;
1718
1719                        if (entSide < 0)
1720                        {
1721                                node = in->GetBack();
1722
1723                                if(extSide <= 0) // plane does not split ray => no far child
1724                                        continue;
1725                                       
1726                                farChild = in->GetFront(); // plane splits ray
1727
1728                        } else if (entSide > 0)
1729                        {
1730                                node = in->GetFront();
1731
1732                                if (extSide >= 0) // plane does not split ray => no far child
1733                                        continue;
1734
1735                                farChild = in->GetBack(); // plane splits ray                   
1736                        }
1737                        else // ray and plane are coincident
1738                        // WHAT TO DO IN THIS CASE ?
1739                        {
1740                                break;
1741                                //node = in->GetFront();
1742                                //continue;
1743                        }
1744
1745                        // push data for far child
1746                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1747
1748                        // find intersection of ray segment with plane
1749                        float t;
1750                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t);
1751                        maxt *= t;
1752                       
1753                } else // reached leaf => intersection with view cell
1754                {
1755                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1756     
1757                        if (!leaf->mViewCell->Mailed())
1758                        {
1759                                ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
1760                                leaf->mViewCell->Mail();
1761                                ++ hits;
1762                        }
1763                       
1764                        //-- fetch the next far child from the stack
1765                        if (tStack.empty())
1766                                break;
1767     
1768                        entp = extp;
1769                        mint = maxt; // NOTE: need this?
1770
1771                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1772                                break;
1773
1774                        BspRayTraversalData &s = tStack.top();
1775
1776                        node = s.mNode;
1777                        extp = s.mExitPoint;
1778                        maxt = s.mMaxT;
1779
1780                        tStack.pop();
1781                }
1782        }
1783
1784        return hits;
1785}
1786
1787bool BspTree::Export(const string filename)
1788{
1789        Exporter *exporter = Exporter::GetExporter(filename);
1790
1791        if (exporter)
1792        {
1793                exporter->ExportBspTree(*this);
1794                return true;
1795        }       
1796
1797        return false;
1798}
1799
1800void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1801{
1802        stack<BspNode *> nodeStack;
1803        nodeStack.push(mRoot);
1804
1805        ViewCell::NewMail();
1806
1807        while (!nodeStack.empty())
1808        {
1809                BspNode *node = nodeStack.top();
1810                nodeStack.pop();
1811
1812                if (node->IsLeaf())
1813                {
1814                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1815
1816                        if (!viewCell->Mailed())
1817                        {
1818                                viewCell->Mail();
1819                                viewCells.push_back(viewCell);
1820                        }
1821                }
1822                else
1823                {
1824                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1825
1826                        nodeStack.push(interior->mFront);
1827                        nodeStack.push(interior->mBack);
1828                }
1829        }
1830}
1831
1832void BspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const
1833{
1834        stat.Reset();
1835
1836        stack<BspNode *> nodeStack;
1837        nodeStack.push(mRoot);
1838
1839        ViewCell::NewMail();
1840
1841        // exclude root cell
1842        mRootCell->Mail();
1843
1844        while (!nodeStack.empty())
1845        {
1846                BspNode *node = nodeStack.top();
1847                nodeStack.pop();
1848
1849                if (node->IsLeaf())
1850                {
1851                        ++ stat.bspLeaves;
1852
1853                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1854
1855                        if (!viewCell->Mailed())
1856                        {
1857                                viewCell->Mail();
1858                               
1859                                ++ stat.viewCells;
1860                                int pvsSize = viewCell->GetPvs().GetSize();
1861
1862                stat.pvs += pvsSize;
1863
1864                                if (pvsSize < 2)
1865                                        ++ stat.emptyPvs;
1866
1867                                if (pvsSize > stat.maxPvs)
1868                                        stat.maxPvs = pvsSize;
1869
1870                                if (pvsSize < stat.minPvs)
1871                                        stat.minPvs = pvsSize;
1872
1873                                if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)
1874                                        stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();           
1875                        }
1876                }
1877                else
1878                {
1879                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1880
1881                        nodeStack.push(interior->mFront);
1882                        nodeStack.push(interior->mBack);
1883                }
1884        }
1885}
1886
1887bool BspTree::MergeViewCells(BspLeaf *front, BspLeaf *back) const
1888{
1889        BspViewCell *viewCell =
1890                dynamic_cast<BspViewCell *>(ViewCell::Merge(*front->mViewCell, *back->mViewCell));
1891       
1892        if (!viewCell)
1893                return false;
1894
1895        // change view cells of all leaves associated with the
1896        // previous view cells
1897
1898        BspViewCell *fVc = front->mViewCell;
1899        BspViewCell *bVc = back->mViewCell;
1900
1901        vector<BspLeaf *> fLeaves = fVc->mBspLeaves;
1902        vector<BspLeaf *> bLeaves = bVc->mBspLeaves;
1903
1904        vector<BspLeaf *>::const_iterator it;
1905       
1906        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
1907        {
1908                (*it)->SetViewCell(viewCell);
1909                viewCell->mBspLeaves.push_back(*it);
1910        }
1911        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
1912        {
1913                (*it)->SetViewCell(viewCell);
1914                viewCell->mBspLeaves.push_back(*it);
1915        }
1916       
1917        DEL_PTR(fVc);
1918        DEL_PTR(bVc);
1919
1920        return true;
1921}
1922
1923bool BspTree::ShouldMerge(BspLeaf *front, BspLeaf *back) const
1924{
1925        ViewCell *fvc = front->mViewCell;
1926        ViewCell *bvc = back->mViewCell;
1927
1928        if ((fvc == mRootCell) || (bvc == mRootCell) || (fvc == bvc))
1929                return false;
1930
1931        int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
1932
1933        if (fvc->GetPvs().GetSize() + fdiff < sMaxPvs)
1934        {
1935                if ((fvc->GetPvs().GetSize() < sMinPvs) ||     
1936                        (bvc->GetPvs().GetSize() < sMinPvs) ||
1937                        ((fdiff < sMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < sMinPvsDif)))
1938                {
1939                        return true;
1940                }
1941        }
1942       
1943        return false;
1944}
1945
1946void BspTree::SetGenerateViewCells(int generateViewCells)
1947{
1948        mGenerateViewCells = generateViewCells;
1949}
1950
1951BspTreeStatistics &BspTree::GetStat()
1952{
1953        return mStat;
1954}
1955
1956int BspTree::SplitRays(const Plane3 &plane,
1957                                           BoundedRayContainer &rays,
1958                                           BoundedRayContainer &frontRays,
1959                                           BoundedRayContainer &backRays)
1960{
1961        int splits = 0;
1962
1963        while (!rays.empty())
1964        {
1965                BoundedRay *bRay = rays.back();
1966                Ray *ray = bRay->mRay;
1967                rays.pop_back();
1968               
1969                const int cf =
1970                        ray->ClassifyPlane(plane, bRay->mMinT, bRay->mMaxT);
1971               
1972                ray->SetId(cf);
1973
1974                switch (cf)
1975                {
1976                case Ray::COINCIDENT:
1977                        frontRays.push_back(bRay);
1978                        break;
1979                case Ray::BACK:
1980                        backRays.push_back(bRay);
1981                        break;
1982                case Ray::FRONT:
1983                        frontRays.push_back(bRay);
1984                        break;
1985                case Ray::FRONT_BACK:
1986                        {
1987                                // find intersection of ray segment with plane
1988                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
1989                                const float t = plane.FindT(ray->GetLoc(), extp);
1990                               
1991                                const float newT = t * bRay->mMaxT;
1992
1993                                frontRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
1994                                backRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
1995
1996                                DEL_PTR(bRay);
1997
1998                                ++ splits;
1999                        }
2000                        break;
2001                case Ray::BACK_FRONT:
2002                        {
2003                                // find intersection of ray segment with plane
2004                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
2005                                const float t = plane.FindT(ray->GetLoc(), extp);
2006                                const float newT = t * bRay->mMaxT;
2007
2008                                backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
2009                                frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
2010                               
2011                                DEL_PTR(bRay);
2012
2013                                ++ splits;
2014                        }
2015                        break;
2016                default:
2017                        Debug << "Should not come here" << endl;
2018                        break;
2019                }
2020        }
2021
2022        return splits;
2023}
2024
2025void BspTree::ExtractSplitPlanes(BspNode *n,
2026                                                                 vector<Plane3 *> &planes,
2027                                                                 vector<bool> &sides) const
2028{
2029        BspNode *lastNode;
2030        do
2031        {
2032                lastNode = n;
2033
2034                // want to get planes defining geometry of this node => don't take
2035                // split plane of node itself
2036                n = n->GetParent();
2037               
2038                if (n)
2039                {
2040                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
2041
2042                        planes.push_back(dynamic_cast<BspInterior *>(interior)->GetPlane());
2043                        sides.push_back(interior->mFront == lastNode);
2044                }
2045        }
2046        while (n);
2047}
2048
2049bool BspTree::ConstructChildGeometry(PolygonContainer &childCell,
2050                                                                         const PolygonContainer &cell,
2051                                                                         const vector<Plane3 *> &planes,
2052                                                                         const vector<bool> &sides,
2053                                                                         const Plane3 &splitPlane,
2054                                                                         const bool side) const
2055{
2056        // get cross section of new polygon
2057        Polygon3 *planePoly = GetBoundingBox().CrossSection(splitPlane);
2058
2059        // polygon is split by all other planes
2060        for (int i = 0; (i < (int)planes.size()) && planePoly; ++ i)
2061        {
2062                const int cf = planePoly->ClassifyPlane(*planes[i]);
2063                       
2064                // split new polygon with all previous planes
2065                switch (cf)
2066                {
2067                        case Polygon3::SPLIT:
2068                                {
2069                                        VertexContainer splitPts;
2070                               
2071                                        Polygon3 *frontPoly = new Polygon3();
2072                                        Polygon3 *backPoly = new Polygon3();
2073
2074                                        planePoly->Split(*planes[i], *frontPoly, *backPoly, splitPts);
2075                                        DEL_PTR(planePoly);
2076
2077                                        if(sides[i] == true)
2078                                        {
2079                                                planePoly = frontPoly;
2080                                                DEL_PTR(backPoly);
2081                                        }
2082                                        else
2083                                        {
2084                                                planePoly = backPoly;
2085                                                DEL_PTR(frontPoly);
2086                                        }
2087                                       
2088                                        if (!planePoly->Valid())
2089                                                DEL_PTR(planePoly);
2090                                }
2091                                break;
2092                        case Polygon3::BACK_SIDE:
2093                                if (sides[i])
2094                                        DEL_PTR(planePoly);
2095                                break;
2096                        case Polygon3::FRONT_SIDE:
2097                                if (!sides[i])
2098                                        DEL_PTR(planePoly);
2099                                break;
2100                        case Polygon3::COINCIDENT:
2101                                break;
2102                        default:
2103                                break;
2104                }
2105        }
2106       
2107        if (!planePoly)
2108        {
2109                //geometry is not changed at all, hence just copy polygons
2110                PolygonContainer::const_iterator it, it_end = cell.end();
2111               
2112                for (it = cell.begin(); it != it_end; ++ it)
2113                        childCell.push_back(new Polygon3((*it)->mVertices));
2114
2115                return false;
2116        }
2117
2118        //-- plane poly splits all other cell polygons
2119        for (int i = 0; i < (int)cell.size(); ++ i)
2120        {
2121                const int cf = cell[i]->ClassifyPlane(splitPlane);
2122                       
2123                // split new polygon with all previous planes
2124                switch (cf)
2125                {
2126                        case Polygon3::SPLIT:
2127                                {
2128                                        Polygon3 *poly = new Polygon3(cell[i]->mVertices);
2129
2130                                        Polygon3 *frontPoly = new Polygon3();
2131                                        Polygon3 *backPoly = new Polygon3();
2132                               
2133                                        VertexContainer splitPts;
2134                                               
2135                                        poly->Split(splitPlane, *frontPoly, *backPoly, splitPts);
2136                                        DEL_PTR(poly);
2137
2138                                        if (side == true)
2139                                        {
2140                                                poly = frontPoly;
2141                                                DEL_PTR(backPoly);
2142                                        }
2143                                        else
2144                                        {
2145                                                poly = backPoly;
2146                                                DEL_PTR(frontPoly);
2147                                        }
2148                                        if (!poly->Valid())
2149                                                DEL_PTR(poly);
2150                                        else
2151                                                childCell.push_back(poly);
2152                                }
2153                               
2154                                break;
2155                        case Polygon3::BACK_SIDE:
2156                                if (!side)
2157                                        childCell.push_back(new Polygon3(cell[i]->mVertices));                 
2158                                break;
2159                        case Polygon3::FRONT_SIDE:
2160                                if (side)
2161                                        childCell.push_back(new Polygon3(cell[i]->mVertices)); 
2162                                break;
2163                        case Polygon3::COINCIDENT:
2164                                childCell.push_back(new Polygon3(cell[i]->mVertices));
2165                                break;
2166                        default:
2167                               
2168                                break;
2169                }
2170        }
2171
2172        //-- finally add the new polygon
2173        childCell.push_back(planePoly);
2174       
2175        return true;
2176}
2177
2178
2179void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
2180{
2181        stack<BspNode *> tStack;
2182
2183        vector<Plane3 *> planes;
2184        vector<bool> sides;
2185
2186        ExtractSplitPlanes(n, planes, sides);
2187
2188        PolygonContainer candidatePolys;
2189
2190        // bounded planes are added to the polygons
2191        for (int i = 0; i < (int)planes.size(); ++ i)
2192        {
2193                candidatePolys.push_back(GetBoundingBox().CrossSection(*planes[i]));
2194        }
2195
2196        // add faces of bounding box (also could be faces of the cell)
2197        for (int i = 0; i < 6; ++ i)
2198        {
2199                VertexContainer vertices;
2200       
2201                for (int j = 0; j < 4; ++ j)
2202                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
2203
2204                candidatePolys.push_back(new Polygon3(vertices));
2205        }
2206
2207        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2208        {
2209                bool inside = true;
2210
2211                // polygon is split by all other planes
2212                for (int j = 0; (j < planes.size()) && inside; ++ j)
2213                {
2214                        Plane3 *plane = planes[j];
2215
2216                        if (i == j) // same plane
2217                                continue;
2218
2219                        VertexContainer splitPts;
2220                        Polygon3 *frontPoly, *backPoly;
2221
2222                        const int cf = candidatePolys[i]->ClassifyPlane(*plane);
2223                       
2224                        switch (cf)
2225                        {
2226                                case Polygon3::SPLIT:
2227                                        frontPoly = new Polygon3();
2228                                        backPoly = new Polygon3();
2229
2230                                        candidatePolys[i]->Split(*plane, *frontPoly,
2231                                                                                         *backPoly, splitPts);
2232                                        DEL_PTR(candidatePolys[i]);
2233
2234                                        if(sides[j] == true)
2235                                        {
2236                                                candidatePolys[i] = frontPoly;
2237                                                DEL_PTR(backPoly);
2238                                        }
2239                                        else
2240                                        {
2241                                                candidatePolys[i] = backPoly;
2242                                                DEL_PTR(frontPoly);
2243                                        }
2244                                       
2245                                        break;
2246
2247                                case Polygon3::BACK_SIDE:
2248                                        if (sides[j])
2249                                                inside = false;
2250                                        break;
2251                                case Polygon3::FRONT_SIDE:
2252                                        if (!sides[j])
2253                                                inside = false;
2254                                        break;
2255                                case Polygon3::COINCIDENT:
2256                                        break;
2257                                default:
2258                                        break;
2259                        }
2260                }
2261               
2262                if (inside)
2263                        cell.push_back(candidatePolys[i]);
2264                else
2265                        DEL_PTR(candidatePolys[i]);
2266        }
2267}
2268
2269void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
2270{
2271        vector<BspLeaf *> leaves = vc->mBspLeaves;
2272
2273        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2274
2275        for (it = leaves.begin(); it != it_end; ++ it)
2276                ConstructGeometry(*it, cell);
2277}
2278
2279int BspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
2280                                                   const bool onlyUnmailed) const
2281{
2282        PolygonContainer cell;
2283
2284        ConstructGeometry(n, cell);
2285
2286        stack<BspNode *> nodeStack;
2287        nodeStack.push(mRoot);
2288               
2289        // planes needed to verify that we found neighbor leaf.
2290        vector<Plane3 *> planes;
2291        vector<bool> sides;
2292
2293        ExtractSplitPlanes(n, planes, sides);
2294
2295        while (!nodeStack.empty())
2296        {
2297                BspNode *node = nodeStack.top();
2298                nodeStack.pop();
2299
2300                if (node->IsLeaf())
2301                {
2302            if (node != n && (!onlyUnmailed || !node->Mailed()))
2303                        {
2304                                // test all planes of current node on neighbour
2305                                PolygonContainer neighborCandidate;
2306                                ConstructGeometry(node, neighborCandidate);
2307                               
2308                                bool isAdjacent = true;
2309                                for (int i = 0; (i < planes.size()) && isAdjacent; ++ i)
2310                                {
2311                                        const int cf =
2312                                                Polygon3::ClassifyPlane(neighborCandidate, *planes[i]);
2313
2314                                        if ((cf == Polygon3::BACK_SIDE) && sides[i])
2315                                                isAdjacent = false;
2316                                        else if ((cf == Polygon3::FRONT_SIDE) && !sides[i])
2317                                                isAdjacent = false;
2318                                }
2319
2320                                if (isAdjacent)
2321                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2322
2323                                CLEAR_CONTAINER(neighborCandidate);
2324                        }
2325                }
2326                else
2327                {
2328                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2329       
2330                        const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
2331
2332                        if (cf == Polygon3::FRONT_SIDE)
2333                                nodeStack.push(interior->mFront);
2334                        else
2335                                if (cf == Polygon3::BACK_SIDE)
2336                                        nodeStack.push(interior->mBack);
2337                                else
2338                                {
2339                                        // random decision
2340                                        nodeStack.push(interior->mBack);
2341                                        nodeStack.push(interior->mFront);
2342                                }
2343                }
2344        }
2345       
2346        CLEAR_CONTAINER(cell);
2347        return (int)neighbors.size();
2348}
2349
2350BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
2351{
2352    stack<BspNode *> nodeStack;
2353        nodeStack.push(mRoot);
2354       
2355        int mask = rand();
2356 
2357        while (!nodeStack.empty())
2358        {
2359                BspNode *node = nodeStack.top();
2360                nodeStack.pop();
2361         
2362                if (node->IsLeaf())
2363                {
2364                        return dynamic_cast<BspLeaf *>(node);
2365                }
2366                else
2367                {
2368                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2369                       
2370                        BspNode *next;
2371       
2372                        PolygonContainer cell;
2373
2374                        // todo: not very efficient: constructs full cell everytime
2375                        ConstructGeometry(interior, cell);
2376
2377                        const int cf = Polygon3::ClassifyPlane(cell, halfspace);
2378
2379                        if (cf == Polygon3::BACK_SIDE)
2380                                next = interior->mFront;
2381                        else
2382                                if (cf == Polygon3::FRONT_SIDE)
2383                                        next = interior->mFront;
2384                        else
2385                        {
2386                                // random decision
2387                                if (mask & 1)
2388                                        next = interior->mBack;
2389                                else
2390                                        next = interior->mFront;
2391                                mask = mask >> 1;
2392                        }
2393
2394                        nodeStack.push(next);
2395                }
2396        }
2397       
2398        return NULL;
2399}
2400
2401BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
2402{
2403        stack<BspNode *> nodeStack;
2404       
2405        nodeStack.push(mRoot);
2406
2407        int mask = rand();
2408       
2409        while (!nodeStack.empty())
2410        {
2411                BspNode *node = nodeStack.top();
2412                nodeStack.pop();
2413               
2414                if (node->IsLeaf())
2415                {
2416                        if ( (!onlyUnmailed || !node->Mailed()) )
2417                                return dynamic_cast<BspLeaf *>(node);
2418                }
2419                else
2420                {
2421                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2422
2423                        // random decision
2424                        if (mask & 1)
2425                                nodeStack.push(interior->mBack);
2426                        else
2427                                nodeStack.push(interior->mFront);
2428
2429                        mask = mask >> 1;
2430                }
2431        }
2432       
2433        return NULL;
2434}
2435
2436int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
2437{
2438        int pvsSize = 0;
2439
2440        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
2441
2442        Intersectable::NewMail();
2443
2444        for (rit = rays.begin(); rit != rays.end(); ++ rit)
2445        {
2446                Ray *ray = (*rit)->mRay;
2447               
2448                if (!ray->intersections.empty())
2449                {
2450                        if (!ray->intersections[0].mObject->Mailed())
2451                        {
2452                                ray->intersections[0].mObject->Mail();
2453                                ++ pvsSize;
2454                        }
2455                }
2456                if (!ray->sourceObject.mObject->Mailed())
2457                {
2458                        ray->sourceObject.mObject->Mail();
2459                        ++ pvsSize;
2460                }
2461        }
2462
2463        return pvsSize;
2464}
Note: See TracBrowser for help on using the repository browser.