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

Revision 362, 49.9 KB checked in by mattausch, 19 years ago (diff)

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