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

Revision 292, 26.3 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
15#define INITIAL_COST 999999// unreachable high initial cost for heuristic evaluation
16
17int BspTree::sTermMaxPolygons = 10;
18int BspTree::sTermMaxDepth = 20;
19int BspTree::sMaxCandidates = 10;
20int BspTree::sSplitPlaneStrategy = NEXT_POLYGON;
21int BspTree::sConstructionMethod = VIEW_CELLS;
22
23/** Evaluates split plane classification with respect to the plane's
24        contribution for a balanced tree.
25*/
26int BspTree::sLeastSplitsTable[4] = {0, 0, 1, 0};
27/** Evaluates split plane classification with respect to the plane's
28        contribution for a minimum number splits in the tree.
29*/
30int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0};
31
32const int FACTOR_BALANCE = 1;
33const int FACTOR_LEAST_SPLITS = 1;
34
35//int counter = 0;
36//bool BspTree::displayDebug = false;
37/****************************************************************/
38/*                  class BspNode implementation                */
39/****************************************************************/
40
41BspNode::BspNode(): mParent(NULL), mPolygons(NULL)//,mViewCellIdx(0)
42{}
43
44BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL)//,mViewCellIdx(0)
45{}
46
47BspNode::~BspNode()
48{
49        if (mPolygons)
50        {
51                CLEAR_CONTAINER(*mPolygons);
52                DEL_PTR(mPolygons);
53        }
54}
55
56bool BspNode::IsRoot() const
57{
58        return mParent == NULL;
59}
60
61BspInterior *BspNode::GetParent()
62{
63        return mParent;
64}
65
66void BspNode::SetParent(BspInterior *parent)
67{
68        mParent = parent;
69}
70
71PolygonContainer *BspNode::GetPolygons()
72{
73        if (!mPolygons)
74                mPolygons = new PolygonContainer();
75
76        return mPolygons;
77}
78
79void BspNode::ProcessPolygons(PolygonContainer *polys, bool storePolys)
80{
81        if (storePolys)
82        {
83                while (!polys->empty())
84                {
85                        GetPolygons()->push_back(polys->back());
86                        polys->pop_back();
87                }
88        }
89        else CLEAR_CONTAINER(*polys);
90}
91
92
93/****************************************************************/
94/*              class BspInterior implementation                */
95/****************************************************************/
96
97
98BspInterior::BspInterior(const Plane3 &plane):
99mPlane(plane), mFront(NULL), mBack(NULL)
100{}
101
102bool BspInterior::IsLeaf() const
103{
104        return false;
105}
106
107BspNode *BspInterior::GetBack()
108{
109        return mBack;
110}
111
112BspNode *BspInterior::GetFront()
113{
114        return mFront;
115}
116
117Plane3 *BspInterior::GetPlane()
118{
119        return &mPlane;
120}
121
122void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild)
123{
124        if (mBack == oldChild)
125                mBack = newChild;
126        else
127                mFront = newChild;
128}
129
130void BspInterior::SetupChildLinks(BspNode *b, BspNode *f)
131{
132    mBack = b;
133    mFront = f;
134}
135
136void BspInterior::ProcessPolygon(Polygon3 **poly, const bool storePolys)
137{
138        if (storePolys)
139                GetPolygons()->push_back(*poly);
140        else
141                DEL_PTR(*poly);
142}
143
144void BspInterior::SplitPolygons(PolygonContainer *polys,
145                                                                PolygonContainer *frontPolys,
146                                                                PolygonContainer *backPolys,
147                                                                PolygonContainer *coincident,
148                                                                int &splits,
149                                                                bool storePolys)
150{
151        Polygon3 *splitPoly = NULL;
152#ifdef _Debug
153        Debug << "Splitting polygons of node " << this << " with plane " << mPlane << endl;
154#endif
155        while (!polys->empty())
156        {
157                Polygon3 *poly = polys->back();
158                polys->pop_back();
159
160                //Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
161
162                // test if split is neccessary
163                int classification = poly->ClassifyPlane(mPlane);
164
165                Polygon3 *front_piece = NULL;
166                Polygon3 *back_piece = NULL;
167       
168                switch (classification)
169                {
170                        case Polygon3::COINCIDENT:
171                                //Debug << "coincident" << endl;       
172                                coincident->push_back(poly);
173                                break;                 
174                        case Polygon3::FRONT_SIDE:     
175                                //Debug << "front" << endl;
176                                frontPolys->push_back(poly);
177                                break;
178                        case Polygon3::BACK_SIDE:
179                                //Debug << "back" << endl;
180                                backPolys->push_back(poly);
181                                break;
182                        case Polygon3::SPLIT:
183                                front_piece = new Polygon3(poly->mParent);
184                                back_piece = new Polygon3(poly->mParent);
185Debug << "*************\n";
186Debug << "initial poly\n" << *poly << endl;
187                                //-- split polygon into front and back part
188                                poly->Split(&mPlane, front_piece, back_piece);
189
190                                ++ splits; // increase number of splits
191                       
192                                if (front_piece->mVertices.size() >= 3) // check if polygon still valid
193                                        frontPolys->push_back(front_piece);
194                                else{
195                                        Debug << "poly\n" << *poly << "split front piece not valid\n" << *front_piece << endl;
196                                        DEL_PTR(front_piece);}
197                               
198                                if (back_piece->mVertices.size() >= 3) // check if polygon still valid
199                                        backPolys->push_back(back_piece);
200                                else{
201                                        Debug << "poly\n" << *poly << "split back piece not valid\n" << *back_piece << endl;
202                                        DEL_PTR(back_piece);}
203                               
204Debug << "*************\n";
205#ifdef _DEBUG
206                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
207#endif
208                                ProcessPolygon(&poly, storePolys);
209                               
210                                break;
211                        default:
212                Debug << "SHOULD NEVER COME HERE\n";
213                                break;
214                }
215        }
216        //Debug << "inside: " << inside << endl;
217}
218
219/****************************************************************/
220/*                  class BspLeaf implementation                */
221/****************************************************************/
222BspLeaf::BspLeaf(): mViewCell(NULL)
223{
224}
225
226BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell)
227{
228}
229
230BspLeaf::BspLeaf(BspInterior *parent): BspNode(parent), mViewCell(NULL)
231{}
232
233BspLeaf::BspLeaf(BspInterior *parent, ViewCell *viewCell):
234BspNode(parent), mViewCell(viewCell)
235{
236}
237ViewCell *BspLeaf::GetViewCell()
238{
239        return mViewCell;
240}
241
242void BspLeaf::SetViewCell(ViewCell *viewCell)
243{
244        mViewCell = viewCell;
245}
246
247bool BspLeaf::IsLeaf() const
248{
249        return true;
250}
251
252/****************************************************************/
253/*                  class BspTree implementation                */
254/****************************************************************/
255
256BspTree::BspTree():
257mTermMaxPolygons(0),
258mTermMaxDepth(0),
259mRoot(NULL),
260//mStorePolys(true)
261mStorePolys(false)
262{
263        Randomize(); // initialise random generator for heuristics
264}
265 
266const BspTreeStatistics &BspTree::GetStatistics() const
267{
268        return mStat;
269}
270
271void BspTreeStatistics::Print(ostream &app) const
272{
273        app << "===== BspTree statistics ===============\n";
274
275        app << setprecision(4);
276
277        app << "#N_RAYS Number of rays )\n"
278                << rays << endl;
279        app << "#N_DOMAINS  ( Number of query domains )\n"
280                << queryDomains <<endl;
281
282        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
283
284        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
285
286        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
287
288        app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
289
290        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
291        rayRefs << "\n";
292
293        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
294        rayRefs/(double)rays << "\n";
295
296        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
297        rayRefs/(double)Leaves() << "\n";
298
299        app << "#N_MAXOBJECTREFS  ( Max number of rayRefs / leaf )\n" <<
300        maxObjectRefs << "\n";
301
302        app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
303        rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
304
305        app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
306        objectRefs/(double)Leaves() << "\n";
307
308        app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
309        zeroQueryNodes*100/(double)Leaves() << endl;
310
311        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
312        maxDepthNodes * 100 / (double)Leaves() << endl;
313
314        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
315
316        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
317
318        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
319
320        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
321        addedRayRefs << endl;
322
323        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n" <<
324        removedRayRefs << endl;
325
326        app << "#N_INPUT_POLYGONS (number of input polygons )\n" <<
327                polys << endl;
328
329        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
330                 (polys + splits) / (double)polys << endl;
331       
332        app << "===== END OF BspTree statistics ==========\n";
333}
334
335BspTree::~BspTree()
336{
337        std::stack<BspNode *> tStack;
338
339        tStack.push(mRoot);
340
341        while (!tStack.empty())
342        {
343                BspNode *node = tStack.top();
344
345            tStack.pop();
346       
347                if (!node->IsLeaf())
348                {
349                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
350
351                        // push the children on the stack (there are always two children)
352                        tStack.push(interior->GetBack());
353                        tStack.push(interior->GetFront());
354                }
355
356                DEL_PTR(node);
357        }
358}
359
360void BspTree::InsertViewCell(ViewCell *viewCell)
361{
362        PolygonContainer *polys = new PolygonContainer();
363
364        // extract polygons that guide the split process
365        mStat.polys += AddMesh2Polygons(viewCell->GetMesh(), *polys);
366        mBox.Include(viewCell->GetBox()); // add to BSP aabb
367
368        InsertPolygons(polys);
369}
370
371void BspTree::InsertPolygons(PolygonContainer *polys, ViewCellContainer *viewCells)
372{       
373        std::stack<BspTraversalData> tStack;
374               
375        // traverse tree or create new one
376        BspNode *firstNode = mRoot ? mRoot : new BspLeaf();
377
378        tStack.push(BspTraversalData(firstNode, polys, 0, NULL));
379
380        while (!tStack.empty())
381        {
382                // filter polygons donw the tree
383                BspTraversalData tData = tStack.top();
384            tStack.pop();
385                       
386                if (!tData.mNode->IsLeaf())
387                {
388                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
389
390                        //-- filter view cell polygons down the tree until a leaf is reached
391                        if ((int)tData.mPolygons->size() > 0)
392                        {
393                                PolygonContainer *frontPolys = new PolygonContainer();
394                                PolygonContainer *backPolys = new PolygonContainer();
395                                PolygonContainer coincident;
396
397                                int splits = 0;
398               
399                                // split viecell polygons with respect to split plane
400                                interior->SplitPolygons(tData.mPolygons,
401                                                                                frontPolys,
402                                                                                backPolys,
403                                                                                &coincident,
404                                                                                splits,
405                                                                                mStorePolys);
406                               
407                                // get view cell associated with the split polygon
408                                ViewCell *viewCell = (coincident.size() > 0) ?
409                                        dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL;
410                                interior->ProcessPolygons(&coincident, mStorePolys);
411
412                                //Debug << "split node on level " << tData.mDepth << " bk: " << backPolys->size() << " frnt: " << frontPolys->size() << endl;
413                                mStat.splits += splits;
414
415                                // push the children on the stack
416                                tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
417                                tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, viewCell));
418                        }
419
420                        // cleanup
421                        DEL_PTR(tData.mPolygons);
422                }
423                else // reached leaf => subdivide current viewcell
424                {
425                        if (tData.mPolygons->size() > 0)
426                                Debug << "Subdividing further: polygon size: " << (int)tData.mPolygons->size() << ", view cell: " << tData.mViewCell << endl;
427
428                        BspNode *root = Subdivide(tStack, tData, viewCells);           
429
430                        if (!mRoot) // tree empty => new root
431                                mRoot = root;
432                }
433        }
434}
435
436void BspTree::InitTree(int maxPolygons, int maxDepth)
437{
438        mTermMaxPolygons = maxPolygons;
439        mTermMaxDepth = maxDepth;
440        mStat.nodes = 1;
441       
442        mBox.Initialize();      // initialise bsp tree bounding box
443}
444
445
446
447int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent)
448{
449        FaceContainer::const_iterator fi;
450        int polysNum = 0;
451
452        // copy the face data to polygons
453        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
454        {
455                Polygon3 *poly = new Polygon3((*fi), mesh);
456                poly->mParent = parent; // set parent intersectable
457                polys.push_back(poly);
458
459                if (!poly->CheckValid())
460                        Debug << "Input polygon not valid: " << *poly << endl;
461
462                ++ polysNum;
463        }
464        return polysNum;
465}
466
467int BspTree::Copy2PolygonSoup(const ViewCellContainer &viewCells, PolygonContainer &polys, int maxObjects)
468{
469        int limit = (maxObjects > 0) ? Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
470 
471        for (int i = 0; i < limit; ++i)
472        {//if ((i == 12) ||(i==14))
473                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
474                {
475                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
476                        AddMesh2Polygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
477                }
478        }
479
480        return (int)polys.size();
481}
482
483int BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
484{
485        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
486 
487        for (int i = 0; i < limit; ++i)
488        {
489                Intersectable *object = objects[i];//*it;
490                Mesh *mesh = NULL;
491
492                switch (object->Type()) // extract the meshes
493                {
494                case Intersectable::MESH_INSTANCE:
495                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
496                        break;
497                case Intersectable::VIEWCELL:
498                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
499                        break;
500                        // TODO: handle transformed mesh instances
501                default:
502                        break;
503                }
504               
505        if (mesh) // copy the mesh data to polygons
506                {
507                        mBox.Include(object->GetBox()); // add to BSP tree aabb
508                        AddMesh2Polygons(mesh, polys);
509                }
510        }
511
512        return (int)polys.size();
513}
514
515void BspTree::Construct(const ViewCellContainer &viewCells)
516{
517        InitTree(sTermMaxPolygons, sTermMaxDepth);
518
519        // copy view cell meshes into one big polygon soup
520        PolygonContainer *polys = new PolygonContainer();
521        mStat.polys = Copy2PolygonSoup(viewCells, *polys);
522
523        // construct tree from viewcell polygons
524        Construct(polys);
525        //Export("bsp.x3d");
526}
527
528
529void BspTree::Construct(const ObjectContainer &objects, ViewCellContainer *viewCells)
530{
531        // take termination criteria from globals
532        InitTree(sTermMaxPolygons, sTermMaxDepth);
533       
534        PolygonContainer *polys = new PolygonContainer();
535       
536        // copy mesh instance polygons into one big polygon soup
537        mStat.polys = Copy2PolygonSoup(objects, *polys);
538
539        // construct tree from polygon soup
540        Construct(polys, viewCells);
541}
542
543void BspTree::Construct(const RayContainer &rays, ViewCellContainer *viewCells)
544{
545        // TODO
546}
547
548void BspTree::Construct(PolygonContainer *polys, ViewCellContainer *viewCells)
549{
550        std::stack<BspTraversalData> tStack;
551       
552        BspTraversalData tData(new BspLeaf(), polys, 0, NULL);
553
554        tStack.push(tData);
555
556        long startTime = GetTime();
557        Debug << "**** Contructing tree using objects ****\n";
558        while (!tStack.empty())
559        {
560                tData = tStack.top();
561            tStack.pop();
562
563                // subdivide leaf node
564                BspNode *root = Subdivide(tStack, tData, viewCells);
565
566                // empty tree => new root corresponding to unbounded space
567                if (!mRoot)
568                        mRoot = root;
569        }
570
571        Debug << "**** Finished tree construction ****\n";
572        Debug << "BSP tree contruction time: "<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
573}
574
575
576BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData,
577                                                        ViewCellContainer *viewCells)
578{
579        //-- terminate traversal 
580        if ((tData.mPolygons->size() <= mTermMaxPolygons) || (tData.mDepth >= mTermMaxDepth))
581        {
582#ifdef _DEBUG
583                Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
584#endif
585
586                EvaluateLeafStats(tData);
587
588                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
589
590                //-- new viewcells are generated and added to each leaf
591                if (viewCells)
592                {
593                        ViewCell *viewCell = new ViewCell();
594                        leaf->SetViewCell(viewCell);
595                        viewCells->push_back(viewCell);
596                        Debug << "creating new viewcell" << endl;
597                }
598                //-- add viewcell stored in split polygon
599                else if (tData.mViewCell)
600                {
601                        if (leaf->GetViewCell())
602                                Debug << "ERROR: leaf already has view cell " << endl;//leaf->mViewCellIdx << endl;
603
604                        //leaf->mViewCellIdx = counter;
605                        Debug << "insert view cell " << tData.mViewCell << endl;
606
607                        leaf->SetViewCell(dynamic_cast<ViewCell *>(tData.mViewCell));
608                }
609       
610                // remaining polygons are discarded or added to node
611                tData.mNode->ProcessPolygons(tData.mPolygons, mStorePolys);
612                DEL_PTR(tData.mPolygons);
613
614                return tData.mNode;
615        }
616
617        //-- continue subdivision
618        PolygonContainer *backPolys = new PolygonContainer();
619        PolygonContainer *frontPolys = new PolygonContainer();
620        PolygonContainer coincident;
621       
622        // create new interior node and two leaf nodes
623        BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
624                                                                                  tData.mPolygons,
625                                                                                  frontPolys,
626                                                                                  backPolys,
627                                                                                  &coincident);
628
629        if ((backPolys->size() == 0) && (coincident.size() > 1))
630        {
631                Debug << "WARNING: size " << (int)coincident.size() << " at depth " << tData.mDepth << ", #back polys: " << (int)backPolys->size() << ", #front polys: " << (int)frontPolys->size() << endl;
632                for (int i=0; i<coincident.size(); ++i)
633                        Debug << "coincident poly " << i << ", vc: " << coincident[i]->mParent << "\n" << *coincident[i] << endl;
634        }
635        //Debug << "coincident size: " << coincident.size() << endl;
636
637        // get view cell associated with the first split polygon
638        ViewCell *viewCell = (coincident.size() > 0) ?
639                                        dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL;
640        interior->ProcessPolygons(&coincident, mStorePolys);
641
642        // push the children on the stack
643        // split polygon is only needed in the back leaf
644        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
645        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, viewCell));
646
647        // cleanup
648        DEL_PTR(tData.mNode);
649        DEL_PTR(tData.mPolygons);
650
651        return interior;
652}
653
654
655BspInterior *BspTree::SubdivideNode(BspLeaf *leaf,
656                                                                        PolygonContainer *polys,
657                                                                        PolygonContainer *frontPolys,
658                                                                        PolygonContainer *backPolys,
659                                                                        PolygonContainer *coincident)
660{
661        mStat.nodes += 2;
662
663        // add the new nodes to the tree + select subdivision plane
664        BspInterior *interior = new BspInterior(SelectPlane(polys));
665
666#ifdef _DEBUG
667        Debug << interior << endl;
668#endif
669
670        // split polygon according to current plane
671        int splits = 0;
672       
673        interior->SplitPolygons(polys, frontPolys, backPolys, coincident, splits, mStorePolys);
674       
675        mStat.splits += splits;
676
677        BspInterior *parent = leaf->GetParent();
678
679        // replace a link from node's parent
680        if (parent)
681        {
682                parent->ReplaceChildLink(leaf, interior);
683                interior->SetParent(parent);
684        }
685
686        // and setup child links
687        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
688       
689        return interior;
690}
691
692Plane3 BspTree::SelectPlane(PolygonContainer *polys)  const
693{
694        if (polys->size() == 0)
695        {
696                Debug << "Warning: No split candidate available\n";
697                return Plane3();
698        }
699
700        // simple strategy: just take next polygon
701        if (sSplitPlaneStrategy == NEXT_POLYGON)
702        {
703                return polys->front()->GetSupportingPlane();
704        }
705       
706        // use heuristics to find appropriate plane
707        return SelectPlaneHeuristics(polys, sMaxCandidates);
708}
709
710Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const
711{
712        int lowestCost = INITIAL_COST;
713        int bestPlaneIdx = 0;
714       
715        int limit = Min((int)polygons->size(), maxTests);
716
717        for (int i = 0; i < limit; ++ i)
718        {
719                int candidateIdx = Random((int)polygons->size()); // TODO:  avoid testing same plane 2 times
720                Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane();
721               
722                // evaluate current candidate
723                int candidateCost = EvalSplitPlane(polygons, candidatePlane);
724                       
725                if (candidateCost < lowestCost)
726                {
727                        bestPlaneIdx = candidateIdx;
728                        lowestCost = candidateCost;
729                        //Debug << "new plane cost " << lowestCost << endl;
730                }
731        }
732        //Debug << "Plane lowest cost: " << lowestCost << endl;
733       
734        return (*polygons)[bestPlaneIdx]->GetSupportingPlane();
735}
736
737int BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const
738{
739        PolygonContainer::const_iterator it;
740
741        int sumBalanced = 0, sumLeastSplits = 0;
742
743        for (it = polygons->begin(); it != polygons->end(); ++ it)
744        {
745                int classification = (*it)->ClassifyPlane(candidatePlane);
746               
747                if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == BALANCED_TREE))
748                {
749                        sumBalanced += sBalancedTreeTable[classification];
750                }
751               
752                if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == LEAST_SPLITS))
753                {
754                        sumLeastSplits += sLeastSplitsTable[classification];
755                }
756        }
757
758        // return linear combination of both sums
759        return FACTOR_BALANCE * abs(sumBalanced) + FACTOR_LEAST_SPLITS *abs(sumLeastSplits);
760}
761
762void BspTree::ParseEnvironment()
763{
764        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
765        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
766        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
767
768        Debug << "BSP max depth: " << sTermMaxDepth << endl;
769        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
770        Debug << "BSP max candidates: " << sMaxCandidates << endl;
771
772        //-- extract strategy to choose the next split plane
773        char splitPlaneStrategyStr[60];
774
775        environment->GetStringValue("BspTree.splitPlaneStrategy", splitPlaneStrategyStr);
776       
777        sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
778       
779        if (strcmp(splitPlaneStrategyStr, "nextPolygon") == 0)
780                sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
781        else if (strcmp(splitPlaneStrategyStr, "leastSplits") == 0)
782                sSplitPlaneStrategy = BspTree::LEAST_SPLITS;
783        else if (strcmp(splitPlaneStrategyStr, "balancedTree") == 0)
784                sSplitPlaneStrategy = BspTree::BALANCED_TREE;
785        else if (strcmp(splitPlaneStrategyStr, "combined") == 0)
786                sSplitPlaneStrategy = BspTree::COMBINED;
787        else
788        {
789                cerr << "Wrong BSP split plane strategy " << splitPlaneStrategyStr << endl;
790                exit(1);
791    }
792
793        Debug << "Split plane heuristic: " << splitPlaneStrategyStr << endl;
794
795        //-- parse BSP tree construction method
796        char constructionMethodStr[60];
797       
798        environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr);
799
800        sConstructionMethod = BspTree::VIEW_CELLS;
801       
802        if (strcmp(constructionMethodStr, "viewCells") == 0)
803                sConstructionMethod = BspTree::VIEW_CELLS;
804        else if (strcmp(constructionMethodStr, "sceneGeometry") == 0)
805                sConstructionMethod = BspTree::SCENE_GEOMETRY;
806        else if (strcmp(constructionMethodStr, "rays") == 0)
807                sConstructionMethod = BspTree::RAYS;
808        else
809        {
810                cerr << "Wrong bsp construction method " << constructionMethodStr << endl;
811                exit(1);
812    }
813
814        Debug << "Construction method: " << constructionMethodStr << endl;
815}
816
817void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
818{
819        stack<BspNode *> nodeStack;
820        nodeStack.push(mRoot);
821 
822        while (!nodeStack.empty())
823        {
824                BspNode *node = nodeStack.top();
825   
826                nodeStack.pop();
827   
828                if (node->IsLeaf())
829                {
830                        BspLeaf *leaf = (BspLeaf *)node;
831                       
832                        leaves.push_back(leaf);
833                } else
834                {
835                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
836                        nodeStack.push(interior->GetBack());
837                        nodeStack.push(interior->GetFront());
838                }
839        }
840}
841
842int BspTree::CollectLeafPvs()
843{
844        int totalPvsSize = 0;
845 
846        stack<BspNode *> nodeStack;
847 
848        nodeStack.push(mRoot);
849 
850        while (!nodeStack.empty())
851        {
852                BspNode *node = nodeStack.top();
853               
854                nodeStack.pop();
855               
856                if (node->IsLeaf())
857                {
858                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
859
860                        ViewCell *viewcell = leaf->GetViewCell();
861                       
862                        if (!viewcell->Mailed())
863                        {
864                                viewcell->Mail(); // what does mail mean?
865                                       
866                                // add this node to pvs of all nodes it can see
867                                BspPvsMap::iterator ni;
868         
869        /*                      for (ni = object->mBspPvs.mEntries.begin(); ni != object->mKdPvs.mEntries.end(); ni++)
870                                {
871                                        BspNode *node = (*ni).first;
872           
873                                        // $$ JB TEMPORARY solution -> should add object PVS or explictly computed
874                                        // BSP tree PVS
875                                if (leaf->mBspPvs.AddNodeSample(node))
876                                                totalPvsSize++;
877                                }*/
878                        }
879                } else
880                {
881                        // traverse tree
882                        BspInterior *interior = (BspInterior *)node;
883     
884                        nodeStack.push(interior->GetFront());
885                        nodeStack.push(interior->GetBack());
886                }
887        }
888
889        return totalPvsSize;
890}
891
892AxisAlignedBox3 BspTree::GetBoundingBox() const
893{
894        return mBox;
895}
896
897BspNode *BspTree::GetRoot() const
898{
899        return mRoot;
900}
901
902bool BspTree::StorePolys() const
903{
904        return mStorePolys;
905}
906
907void BspTree::EvaluateLeafStats(const BspTraversalData &data)
908{
909        // the node became a leaf -> evaluate stats for leafs
910        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
911
912        if (data.mDepth >= mTermMaxDepth)
913        {
914                ++ mStat.maxDepthNodes;
915        }
916
917        // store maximal and minimal depth
918        if (data.mDepth > mStat.maxDepth)
919                mStat.maxDepth = data.mDepth;
920        if (data.mDepth < mStat.minDepth)
921                mStat.minDepth = data.mDepth;
922
923        // accumulate depth to compute average
924        mStat.accumDepth += data.mDepth;
925
926        if (leaf->mViewCell)
927                ++ mStat.viewCellLeaves;
928
929#ifdef _DEBUG
930        Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), #polygons: " <<
931          data.mPolygons->size() << " (max: " << mTermMaxPolygons << ")" << endl;
932#endif
933}
934
935int BspTree::CastRay(Ray &ray)
936{
937        int hits = 0;
938 
939        stack<BspRayTraversalData> tStack;
940 
941        float maxt = 1e6;
942        float mint = 0;
943
944        Intersectable::NewMail();
945
946        // test with tree bounding box
947        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
948                return 0;
949
950        if (mint < 0)
951                mint = 0;
952 
953        maxt += Limits::Threshold;
954 
955        Vector3 entp = ray.Extrap(mint);
956        Vector3 extp = ray.Extrap(maxt);
957 
958        BspNode *node = mRoot;
959        BspNode *farChild;
960       
961        while (1)
962        {
963                if (!node->IsLeaf())
964                {
965                        BspInterior *in = (BspInterior *) node;
966                       
967                        Plane3 *splitPlane = in->GetPlane();
968
969                        float t = 0;
970                        bool coplanar = false;
971               
972                        int entSide = splitPlane->Side(entp);
973                        int extSide = splitPlane->Side(extp);
974
975                        Vector3 intersection;
976
977                        if (entSide < 0)
978                        {
979                                node = in->GetBack();
980
981                                if(extSide <= 0)
982                                        continue;
983                                       
984                                farChild = in->GetFront(); // plane splits ray
985
986                        } else if (entSide > 0)
987                        {
988                                node = in->GetFront();
989
990                                if (extSide >= 0)
991                                        continue;
992
993                                farChild = in->GetBack();        // plane splits ray                   
994                        }
995                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
996                        {
997                                node = in->GetFront();
998                                continue;
999                        }
1000
1001                        //-- split
1002
1003                        // push data for far child
1004                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1005
1006                        // find intersection with plane between ray origin and exit point
1007                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
1008
1009                } else // compute intersections with objects in leaf
1010                {
1011                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1012                        //ray.leaves.push_back(leaf);
1013      // TODO
1014                        /*ObjectContainer::const_iterator mi;
1015                        for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++mi)
1016                        {
1017                                Intersectable *object = *mi;
1018                                if (!object->Mailed())
1019                                {
1020                                        object->Mail();
1021                                        //ray.meshes.push_back(mesh);
1022                                        hits += object->CastRay(ray);
1023                                }
1024                        }*/
1025
1026                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
1027                                if (ray.intersections[0].mT <= maxt)
1028                                        break;
1029     
1030                        // get the next node from the stack
1031                        if (tStack.empty())
1032                                break;
1033     
1034                        entp = extp;
1035                        mint = maxt;
1036                        BspRayTraversalData &s  = tStack.top();
1037
1038                        node = s.mNode;
1039                        extp = s.mExitPoint;
1040                        maxt = s.mMaxT;
1041
1042                        tStack.pop();
1043                }
1044        }
1045
1046        return hits;
1047}
1048
1049bool BspTree::Export(const string filename)
1050{
1051        Exporter *exporter = Exporter::GetExporter(filename);
1052
1053        if (exporter)
1054        {
1055                exporter->ExportBspTree(*this);
1056                return true;
1057        }       
1058
1059        return false;
1060}
1061//} // GtpVisibilityPreprocessor
Note: See TracBrowser for help on using the repository browser.