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

Revision 294, 24.8 KB checked in by mattausch, 19 years ago (diff)

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