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

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