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

Revision 299, 29.5 KB checked in by mattausch, 19 years ago (diff)

added polygon area (debugged)
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;
20int BspTree::sTermMaxPolysForAxisAligned = 50;
21
22//-- factors for bsp tree split plane heuristics
23float BspTree::sLeastSplitsFactor = 1.0f;
24float BspTree::sBalancedPolysFactor = 2.0f;
25float BspTree::sBalancedViewCellsFactor = 2.0f;
26float BspTree::sVerticalSplitsFactor = 1.0f; // very important criterium for 2.5d scenes
27
28
29/** Evaluates split plane classification with respect to the plane's
30        contribution for a balanced tree.
31*/
32float BspTree::sLeastSplitsTable[] = {0, 0, 1, 0};
33/** Evaluates split plane classification with respect to the plane's
34        contribution for a minimum number splits in the tree.
35*/
36float BspTree::sBalancedPolysTable[] = {-1, 1, 0, 0};
37
38//int counter = 0;
39
40/****************************************************************/
41/*                  class BspNode implementation                */
42/****************************************************************/
43
44BspNode::BspNode(): mParent(NULL), mPolygons(NULL)//,mViewCellIdx(0)
45{}
46
47BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL)//,mViewCellIdx(0)
48{}
49
50BspNode::~BspNode()
51{
52        if (mPolygons)
53        {
54                CLEAR_CONTAINER(*mPolygons);
55                DEL_PTR(mPolygons);
56        }
57}
58
59bool BspNode::IsRoot() const
60{
61        return mParent == NULL;
62}
63
64BspInterior *BspNode::GetParent()
65{
66        return mParent;
67}
68
69void BspNode::SetParent(BspInterior *parent)
70{
71        mParent = parent;
72}
73
74PolygonContainer *BspNode::GetPolygons()
75{
76        if (!mPolygons)
77                mPolygons = new PolygonContainer();
78
79        return mPolygons;
80}
81
82void BspNode::ProcessPolygons(PolygonContainer *polys, bool storePolys)
83{
84        if (storePolys)
85        {
86                while (!polys->empty())
87                {
88                        GetPolygons()->push_back(polys->back());
89                        polys->pop_back();
90                }
91        }
92        else CLEAR_CONTAINER(*polys);
93}
94
95
96/****************************************************************/
97/*              class BspInterior implementation                */
98/****************************************************************/
99
100
101BspInterior::BspInterior(const Plane3 &plane):
102mPlane(plane), mFront(NULL), mBack(NULL)
103{}
104
105bool BspInterior::IsLeaf() const
106{
107        return false;
108}
109
110BspNode *BspInterior::GetBack()
111{
112        return mBack;
113}
114
115BspNode *BspInterior::GetFront()
116{
117        return mFront;
118}
119
120Plane3 *BspInterior::GetPlane()
121{
122        return &mPlane;
123}
124
125void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild)
126{
127        if (mBack == oldChild)
128                mBack = newChild;
129        else
130                mFront = newChild;
131}
132
133void BspInterior::SetupChildLinks(BspNode *b, BspNode *f)
134{
135    mBack = b;
136    mFront = f;
137}
138
139void BspInterior::ProcessPolygon(Polygon3 **poly, const bool storePolys)
140{
141        if (storePolys)
142                GetPolygons()->push_back(*poly);
143        else
144                DEL_PTR(*poly);
145}
146
147void BspInterior::SplitPolygons(PolygonContainer *polys,
148                                                                PolygonContainer *frontPolys,
149                                                                PolygonContainer *backPolys,
150                                                                PolygonContainer *coincident,
151                                                                int &splits,
152                                                                bool storePolys)
153{
154        Polygon3 *splitPoly = NULL;
155#ifdef _Debug
156        Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
157#endif
158        while (!polys->empty())
159        {
160                Polygon3 *poly = polys->back();
161                polys->pop_back();
162
163                //Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
164
165                // get polygon classification
166                int classification = poly->ClassifyPlane(mPlane);
167
168                Polygon3 *front_piece = NULL;
169                Polygon3 *back_piece = NULL;
170       
171                switch (classification)
172                {
173                        case Polygon3::COINCIDENT:
174                                //Debug << "coincident" << endl;       
175                                coincident->push_back(poly);
176                                break;                 
177                        case Polygon3::FRONT_SIDE:     
178                                //Debug << "front" << endl;
179                                frontPolys->push_back(poly);
180                                break;
181                        case Polygon3::BACK_SIDE:
182                                //Debug << "back" << endl;
183                                backPolys->push_back(poly);
184                                break;
185                        case Polygon3::SPLIT:
186                                front_piece = new Polygon3(poly->mParent);
187                                back_piece = new Polygon3(poly->mParent);
188
189                                //-- split polygon into front and back part
190                                poly->Split(&mPlane, front_piece, back_piece);
191
192                                ++ splits; // increase number of splits
193
194                                // check if polygons still valid
195                                if (front_piece->Valid())
196                                        frontPolys->push_back(front_piece);
197                                else
198                                        DEL_PTR(front_piece);
199                               
200                                if (back_piece->Valid())
201                                        backPolys->push_back(back_piece);
202                                else                           
203                                        DEL_PTR(back_piece);
204                               
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}
217
218/****************************************************************/
219/*                  class BspLeaf implementation                */
220/****************************************************************/
221BspLeaf::BspLeaf(): mViewCell(NULL)
222{
223}
224
225BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell)
226{
227}
228
229BspLeaf::BspLeaf(BspInterior *parent): BspNode(parent), mViewCell(NULL)
230{}
231
232BspLeaf::BspLeaf(BspInterior *parent, ViewCell *viewCell):
233BspNode(parent), mViewCell(viewCell)
234{
235}
236ViewCell *BspLeaf::GetViewCell()
237{
238        return mViewCell;
239}
240
241void BspLeaf::SetViewCell(ViewCell *viewCell)
242{
243        mViewCell = viewCell;
244}
245
246bool BspLeaf::IsLeaf() const
247{
248        return true;
249}
250
251/****************************************************************/
252/*                  class BspTree implementation                */
253/****************************************************************/
254
255BspTree::BspTree(ViewCell *viewCell):
256mRoot(NULL),
257mViewCell(viewCell),
258//mStorePolys(true)
259mStorePolys(false)
260{
261        Randomize(); // initialise random generator for heuristics
262}
263 
264const BspTreeStatistics &BspTree::GetStatistics() const
265{
266        return mStat;
267}
268
269void BspTreeStatistics::Print(ostream &app) const
270{
271        app << "===== BspTree statistics ===============\n";
272
273        app << setprecision(4);
274
275        app << "#N_RAYS Number of rays )\n"
276                << rays << endl;
277        app << "#N_DOMAINS  ( Number of query domains )\n"
278                << queryDomains <<endl;
279
280        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
281
282        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
283
284        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
285
286        app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
287
288        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
289        rayRefs << "\n";
290
291        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
292        rayRefs/(double)rays << "\n";
293
294        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
295        rayRefs/(double)Leaves() << "\n";
296
297        app << "#N_MAXOBJECTREFS  ( Max number of rayRefs / leaf )\n" <<
298        maxObjectRefs << "\n";
299
300        app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
301        rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
302
303        app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
304        objectRefs/(double)Leaves() << "\n";
305
306        app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
307        zeroQueryNodes*100/(double)Leaves() << endl;
308
309        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
310        maxDepthNodes * 100 / (double)Leaves() << endl;
311
312        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
313
314        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
315
316        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
317
318        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
319        addedRayRefs << endl;
320
321        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n" <<
322        removedRayRefs << endl;
323
324        app << "#N_INPUT_POLYGONS (number of input polygons )\n" <<
325                polys << endl;
326
327        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
328                 (polys + splits) / (double)polys << endl;
329       
330        app << "===== END OF BspTree statistics ==========\n";
331}
332
333BspTree::~BspTree()
334{
335        std::stack<BspNode *> tStack;
336
337        tStack.push(mRoot);
338
339        while (!tStack.empty())
340        {
341                BspNode *node = tStack.top();
342
343            tStack.pop();
344       
345                if (!node->IsLeaf())
346                {
347                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
348
349                        // push the children on the stack (there are always two children)
350                        tStack.push(interior->GetBack());
351                        tStack.push(interior->GetFront());
352                }
353
354                DEL_PTR(node);
355        }
356}
357
358void BspTree::InsertViewCell(ViewCell *viewCell)
359{
360        PolygonContainer *polys = new PolygonContainer();
361
362        // extract polygons that guide the split process
363        mStat.polys += AddMesh2Polygons(viewCell->GetMesh(), *polys);
364        mBox.Include(viewCell->GetBox()); // add to BSP aabb
365
366        InsertPolygons(polys);
367}
368
369void BspTree::InsertPolygons(PolygonContainer *polys, ViewCellContainer *viewCells)
370{       
371        std::stack<BspTraversalData> tStack;
372               
373        // traverse tree or create new one
374        BspNode *firstNode = mRoot ? mRoot : new BspLeaf();
375
376        tStack.push(BspTraversalData(firstNode, polys, 0, mViewCell));
377
378        while (!tStack.empty())
379        {
380                // filter polygons donw the tree
381                BspTraversalData tData = tStack.top();
382            tStack.pop();
383                       
384                if (!tData.mNode->IsLeaf())
385                {
386                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
387
388                        //-- filter view cell polygons down the tree until a leaf is reached
389                        if ((int)tData.mPolygons->size() > 0)
390                        {
391                                PolygonContainer *frontPolys = new PolygonContainer();
392                                PolygonContainer *backPolys = new PolygonContainer();
393                                PolygonContainer coincident;
394
395                                int splits = 0;
396               
397                                // split viecell polygons with respect to split plane
398                                interior->SplitPolygons(tData.mPolygons,
399                                                                                frontPolys,
400                                                                                backPolys,
401                                                                                &coincident,
402                                                                                splits,
403                                                                                mStorePolys);
404                               
405                                // extract view cells associated with the split polygons
406                                ViewCell *frontViewCell = mViewCell;
407                                ViewCell *backViewCell = mViewCell;
408       
409                                if (!viewCells)
410                                {
411                                        ExtractViewCells(&backViewCell,
412                                                                         &frontViewCell,
413                                                                         coincident,
414                                                                         interior->mPlane,
415                                                                         frontPolys->empty(),
416                                                                         backPolys->empty());
417                                }
418
419                                // don't need coincident polygons anymore
420                                interior->ProcessPolygons(&coincident, mStorePolys);
421
422                                //Debug << "split node on level " << tData.mDepth << " bk: " << backPolys->size() << " frnt: " << frontPolys->size() << endl;
423                                mStat.splits += splits;
424
425                                // push the children on the stack
426                                tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, frontViewCell));
427                                tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, backViewCell));
428                        }
429
430                        // cleanup
431                        DEL_PTR(tData.mPolygons);
432                }
433                else // reached leaf => subdivide current viewcell
434                {
435                        if (tData.mPolygons->size() > 0)
436                                Debug << "Subdividing further: polygon size: " << (int)tData.mPolygons->size() << ", view cell: " << tData.mViewCell << endl;
437
438                        BspNode *root = Subdivide(tStack, tData, viewCells);           
439
440                        if (!mRoot) // tree empty => new root
441                                mRoot = root;
442                }
443        }
444}
445
446int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent)
447{
448        FaceContainer::const_iterator fi;
449        int polysNum = 0;
450
451        // copy the face data to polygons
452        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
453        {
454                Polygon3 *poly = new Polygon3((*fi), mesh);
455                poly->mParent = parent; // set parent intersectable
456                polys.push_back(poly);
457
458                if (!poly->Valid())
459                        Debug << "Input polygon not valid: " << *poly << endl;
460
461                ++ polysNum;
462        }
463        return polysNum;
464}
465
466int BspTree::Copy2PolygonSoup(const ViewCellContainer &viewCells, PolygonContainer &polys, int maxObjects)
467{
468        int limit = (maxObjects > 0) ? Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
469 
470        for (int i = 0; i < limit; ++i)
471        {//if ((i == 12) ||(i==14))
472                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
473                {
474                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
475                        AddMesh2Polygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
476                }
477        }
478
479        return (int)polys.size();
480}
481
482int BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
483{
484        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
485 
486        for (int i = 0; i < limit; ++i)
487        {
488                Intersectable *object = objects[i];//*it;
489                Mesh *mesh = NULL;
490
491                switch (object->Type()) // extract the meshes
492                {
493                case Intersectable::MESH_INSTANCE:
494                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
495                        break;
496                case Intersectable::VIEWCELL:
497                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
498                        break;
499                        // TODO: handle transformed mesh instances
500                default:
501                        break;
502                }
503               
504        if (mesh) // copy the mesh data to polygons
505                {
506                        mBox.Include(object->GetBox()); // add to BSP tree aabb
507                        AddMesh2Polygons(mesh, polys);
508                }
509        }
510
511        return (int)polys.size();
512}
513
514void BspTree::Construct(const ViewCellContainer &viewCells)
515{
516        mStat.nodes = 1;
517        mBox.Initialize();      // initialise bsp tree bounding box
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        mStat.nodes = 1;
532        mBox.Initialize();      // initialise bsp tree bounding box
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, mViewCell);
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() <= sTermMaxPolygons) || (tData.mDepth >= sTermMaxDepth))
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
600                {
601                        if (leaf->GetViewCell())
602                                Debug << "ERROR: leaf already has view cell " << endl;//leaf->mViewCellIdx << endl;
603
604                        //leaf->mViewCellIdx = counter; Debug << "insert view cell " << tData.mViewCell << endl;
605                        leaf->SetViewCell(tData.mViewCell);
606                }
607       
608                // remaining polygons are discarded or added to node
609                tData.mNode->ProcessPolygons(tData.mPolygons, mStorePolys);
610                DEL_PTR(tData.mPolygons);
611
612                return tData.mNode;
613        }
614
615        //-- continue subdivision
616        PolygonContainer *backPolys = new PolygonContainer();
617        PolygonContainer *frontPolys = new PolygonContainer();
618        PolygonContainer coincident;
619       
620        // create new interior node and two leaf nodes
621        BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
622                                                                                  tData.mPolygons,
623                                                                                  frontPolys,
624                                                                                  backPolys,
625                                                                                  &coincident);
626
627        //-- extract view cells from coincident polygons according to plane normal
628        ViewCell *frontViewCell = mViewCell;
629        ViewCell *backViewCell = mViewCell;
630       
631    if (!viewCells)
632        {
633                ExtractViewCells(&backViewCell,
634                                                 &frontViewCell,
635                                                 coincident,
636                                                 interior->mPlane,
637                                                 frontPolys->empty(),
638                                                 backPolys->empty());
639        }
640   
641        // don't need coincident polygons anymore
642        interior->ProcessPolygons(&coincident, mStorePolys);
643
644        // push the children on the stack
645        // split polygon is only needed in the back leaf
646        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, frontViewCell));
647        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, backViewCell));
648
649        // cleanup
650        DEL_PTR(tData.mNode);
651        DEL_PTR(tData.mPolygons);
652
653        return interior;
654}
655
656void BspTree::ExtractViewCells(ViewCell **backViewCell,
657                                                           ViewCell **frontViewCell,
658                                                           const PolygonContainer &coincident,
659                                                           const Plane3 splitPlane,
660                                                           const bool extractFront,
661                                                           const bool extractBack) const
662{
663        bool foundFront = !extractFront, foundBack = !extractBack;
664
665        PolygonContainer::const_iterator it, it_end = coincident.end();
666
667        for (it = coincident.begin(); !(foundFront && foundBack) &&
668                (it < coincident.end()); ++it)
669        {
670                if (DotProd((*it)->GetSupportingPlane().mNormal, splitPlane.mNormal > 0))
671                {
672                        *backViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
673                        foundBack = true;
674                }
675                else
676                {
677                        *frontViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
678                        foundFront = true;
679                }
680        }
681}
682
683BspInterior *BspTree::SubdivideNode(BspLeaf *leaf,
684                                                                        PolygonContainer *polys,
685                                                                        PolygonContainer *frontPolys,
686                                                                        PolygonContainer *backPolys,
687                                                                        PolygonContainer *coincident)
688{
689        mStat.nodes += 2;
690
691        // add the new nodes to the tree + select subdivision plane
692        BspInterior *interior = new BspInterior(SelectPlane(*polys));
693
694#ifdef _DEBUG
695        Debug << interior << endl;
696#endif
697
698        // split polygon according to current plane
699        int splits = 0;
700       
701        interior->SplitPolygons(polys, frontPolys, backPolys, coincident, splits, mStorePolys);
702       
703        mStat.splits += splits;
704
705        BspInterior *parent = leaf->GetParent();
706
707        // replace a link from node's parent
708        if (parent)
709        {
710                parent->ReplaceChildLink(leaf, interior);
711                interior->SetParent(parent);
712        }
713
714        // and setup child links
715        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
716       
717        return interior;
718}
719
720Plane3 BspTree::SelectPlane(const PolygonContainer &polys)  const
721{
722        if (polys.size() == 0)
723        {
724                Debug << "Warning: No split candidate available\n";
725                return Plane3();
726        }
727
728        if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
729                ((int)polys.size() > sTermMaxPolysForAxisAligned))
730        {
731                AxisAlignedBox3 box;
732                box.Initialize();
733       
734                // todo: area subdivision
735                Polygon3::IncludeInBox(polys, box);
736       
737                int axis = box.Size().DrivingAxis();
738                Vector3 norm(0,0,0); norm[axis] = 1;
739
740                Vector3 pt = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
741
742                return Plane3(norm, pt);
743        }
744
745        // simplest strategy: just take next polygon
746        if (sSplitPlaneStrategy & NEXT_POLYGON)
747        {
748                return polys.front()->GetSupportingPlane();
749        }
750
751        /*if (sSplitPlaneStrategy & VERTICAL_AXIS)
752        {
753                const float dot_thres = 0.999;
754                PolygonContainer::const_iterator it, it_end = polys->end();
755               
756                for (it = polys->begin(); it != it_end; ++ it)
757                {
758                        if (DotProd((*it)->GetSupportingPlane().mNormal, mVerticalAxis) > dot_thres)
759                                return (*it)->GetSupportingPlane();
760                }
761        }*/
762       
763        // use heuristics to find appropriate plane
764        return SelectPlaneHeuristics(polys, sMaxCandidates);
765}
766
767Plane3 BspTree::SelectPlaneHeuristics(const PolygonContainer &polys, int maxTests) const
768{
769        float lowestCost = MAX_FLOAT;
770        int bestPlaneIdx = 0;
771       
772        int limit = Min((int)polys.size(), maxTests);
773
774        for (int i = 0; i < limit; ++ i)
775        {
776                int candidateIdx = GetNextCandidateIdx((int)polys.size());
777                Plane3 candidatePlane = polys[candidateIdx]->GetSupportingPlane();
778               
779                // evaluate current candidate
780                float candidateCost = EvalSplitPlane(polys, candidatePlane);
781                       
782                if (candidateCost < lowestCost)
783                {
784                        bestPlaneIdx = candidateIdx;
785                        lowestCost = candidateCost;
786                }
787        }
788        Debug << "Plane lowest cost: " << lowestCost << endl;
789       
790        return polys[bestPlaneIdx]->GetSupportingPlane();
791}
792
793int BspTree::GetNextCandidateIdx(const int max) const
794{
795        return Random(max); // TODO: avoid testing same plane 2 times
796}
797
798float BspTree::EvalSplitPlane(const PolygonContainer &polys, const Plane3 &candidatePlane) const
799{
800        float sumBalancedPolys = 0;
801        float sumBalancedViewCells = 0;
802        float sumSplits = 0;
803        float sumPolyArea = 0;
804        float verticalAxis = 0;
805       
806        if (sSplitPlaneStrategy & VERTICAL_AXIS)
807        {
808                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
809                // want to put a penalty on the dot product between the "tiny" vertical axis
810                // and the split plane axis
811                verticalAxis = fabs(DotProd(candidatePlane.mNormal, tinyAxis)) * (float)polys.size();
812        }
813        //-- strategies where the effect of the split plane on the polygons is tested
814        if ((sSplitPlaneStrategy & BALANCED_POLYS)      ||
815                (sSplitPlaneStrategy & LEAST_SPLITS)        ||
816                (sSplitPlaneStrategy & LARGEST_POLY_AREA))
817        {
818                PolygonContainer::const_iterator it, it_end = polys.end();
819               
820                for (it = polys.begin(); it != it_end; ++ it)
821                {
822                        int classification = (*it)->ClassifyPlane(candidatePlane);
823
824                        if (sSplitPlaneStrategy & BALANCED_POLYS)
825                                sumBalancedPolys += sBalancedPolysTable[classification];
826                               
827                        if (sSplitPlaneStrategy & LEAST_SPLITS)
828                                sumSplits += sLeastSplitsTable[classification];
829
830                        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
831                        {
832                                Debug << "polygon area: " << (*it)->GetArea() << " ";
833                                sumPolyArea += (*it)->GetArea();
834                        }
835                }Debug << "\n";
836        }
837       
838        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
839        {
840                // store view cells
841                ObjectContainer frontViewCells;
842                ObjectContainer backViewCells;
843
844                PolygonContainer::const_iterator it, it_end = polys.end();
845               
846                for (it = polys.begin(); it != it_end; ++ it)
847                {
848                        int classification = (*it)->ClassifyPlane(candidatePlane);
849                        Intersectable *viewCell = (*it)->mParent;
850                       
851                        if (viewCell && (classification == Polygon3::FRONT_SIDE))
852                                frontViewCells.push_back(viewCell);
853                        else if (viewCell && (classification == Polygon3::BACK_SIDE))
854                                backViewCells.push_back(viewCell);
855                }
856
857                // count number of unique view cells
858                sort(frontViewCells.begin(), frontViewCells.end());
859                sort(backViewCells.begin(), backViewCells.end());
860
861                ObjectContainer::const_iterator frontIt, frontIt_end = frontViewCells.end();
862               
863                Intersectable *intersect = NULL;
864                // increase counter for view cells in front of plane
865        for (frontIt = frontViewCells.begin(); frontIt != frontIt_end; ++frontIt)
866                {
867                        if (*frontIt != intersect)
868                        {
869                                intersect = *frontIt;
870                                sumBalancedViewCells += 1;
871                        }
872                }
873
874                ObjectContainer::const_iterator backIt, backIt_end = backViewCells.end();
875                intersect = NULL;
876                // decrease counter for view cells on back side of plane
877        for (backIt = backViewCells.begin(); backIt != backIt_end; ++backIt)
878                {
879                        if (*backIt != intersect)
880                        {
881                                intersect = *backIt;
882                                sumBalancedViewCells -= 1;
883                        }
884                }
885        }
886
887        // return linear combination of the sums
888        return sBalancedPolysFactor * fabs(sumBalancedPolys) +
889                   sBalancedViewCellsFactor * fabs(sumBalancedViewCells) +
890                   sLeastSplitsFactor * sumSplits +
891                   sVerticalSplitsFactor * verticalAxis +
892                   sumPolyArea;
893}
894
895void BspTree::ParseEnvironment()
896{
897        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
898        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
899        environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned",
900                                                         sTermMaxPolysForAxisAligned);
901        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
902        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
903
904    Debug << "BSP max depth: " << sTermMaxDepth << endl;
905        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
906        Debug << "BSP max candidates: " << sMaxCandidates << endl;
907       
908        Debug << "Split plane strategy: ";
909        if (sSplitPlaneStrategy & NEXT_POLYGON)
910                Debug << "next polygon ";
911        if (sSplitPlaneStrategy & AXIS_ALIGNED)
912                Debug << "axis aligned ";
913        if (sSplitPlaneStrategy & LEAST_SPLITS)     
914                Debug << "least splits ";
915        if (sSplitPlaneStrategy & BALANCED_POLYS)
916                Debug << "balanced polygons ";
917        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
918                Debug << "balanced view cells ";
919        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
920                Debug << "largest polygon area ";
921        if (sSplitPlaneStrategy & VERTICAL_AXIS)
922                Debug << "vertical axis ";
923
924        Debug << endl;
925
926        //-- parse BSP tree construction method
927        char constructionMethodStr[60];
928       
929        environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr);
930
931        sConstructionMethod = BspTree::VIEW_CELLS;
932       
933        if (strcmp(constructionMethodStr, "viewCells") == 0)
934                sConstructionMethod = BspTree::VIEW_CELLS;
935        else if (strcmp(constructionMethodStr, "sceneGeometry") == 0)
936                sConstructionMethod = BspTree::SCENE_GEOMETRY;
937        else if (strcmp(constructionMethodStr, "rays") == 0)
938                sConstructionMethod = BspTree::RAYS;
939        else
940        {
941                cerr << "Wrong bsp construction method " << constructionMethodStr << endl;
942                exit(1);
943    }
944
945        Debug << "Construction method: " << constructionMethodStr << endl;
946}
947
948void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
949{
950        stack<BspNode *> nodeStack;
951        nodeStack.push(mRoot);
952 
953        while (!nodeStack.empty())
954        {
955                BspNode *node = nodeStack.top();
956   
957                nodeStack.pop();
958   
959                if (node->IsLeaf())
960                {
961                        BspLeaf *leaf = (BspLeaf *)node;
962                       
963                        leaves.push_back(leaf);
964                } else
965                {
966                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
967                        nodeStack.push(interior->GetBack());
968                        nodeStack.push(interior->GetFront());
969                }
970        }
971}
972
973int BspTree::CollectLeafPvs()
974{
975        int totalPvsSize = 0;
976 
977        stack<BspNode *> nodeStack;
978 
979        nodeStack.push(mRoot);
980 
981        while (!nodeStack.empty())
982        {
983                BspNode *node = nodeStack.top();
984               
985                nodeStack.pop();
986               
987                if (node->IsLeaf())
988                {
989                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
990
991                        ViewCell *viewcell = leaf->GetViewCell();
992                       
993                        if (!viewcell->Mailed())
994                        {
995                                viewcell->Mail(); // what does mail mean?
996                                       
997                                // add this node to pvs of all nodes it can see
998                                BspPvsMap::iterator ni;
999         
1000        /*                      for (ni = object->mBspPvs.mEntries.begin(); ni != object->mKdPvs.mEntries.end(); ni++)
1001                                {
1002                                        BspNode *node = (*ni).first;
1003           
1004                                        // $$ JB TEMPORARY solution -> should add object PVS or explictly computed
1005                                        // BSP tree PVS
1006                                if (leaf->mBspPvs.AddNodeSample(node))
1007                                                totalPvsSize++;
1008                                }*/
1009                        }
1010                } else
1011                {
1012                        // traverse tree
1013                        BspInterior *interior = (BspInterior *)node;
1014     
1015                        nodeStack.push(interior->GetFront());
1016                        nodeStack.push(interior->GetBack());
1017                }
1018        }
1019
1020        return totalPvsSize;
1021}
1022
1023AxisAlignedBox3 BspTree::GetBoundingBox() const
1024{
1025        return mBox;
1026}
1027
1028BspNode *BspTree::GetRoot() const
1029{
1030        return mRoot;
1031}
1032
1033bool BspTree::StorePolys() const
1034{
1035        return mStorePolys;
1036}
1037
1038void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1039{
1040        // the node became a leaf -> evaluate stats for leafs
1041        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1042
1043        if (data.mDepth >= sTermMaxDepth)
1044        {
1045                ++ mStat.maxDepthNodes;
1046        }
1047
1048        // store maximal and minimal depth
1049        if (data.mDepth > mStat.maxDepth)
1050                mStat.maxDepth = data.mDepth;
1051        if (data.mDepth < mStat.minDepth)
1052                mStat.minDepth = data.mDepth;
1053
1054        // accumulate depth to compute average
1055        mStat.accumDepth += data.mDepth;
1056
1057        if (leaf->mViewCell)
1058                ++ mStat.viewCellLeaves;
1059
1060#ifdef _DEBUG
1061        Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), #polygons: " <<
1062          data.mPolygons->size() << " (max: " << sTermMaxPolygons << ")" << endl;
1063#endif
1064}
1065
1066int BspTree::CastRay(Ray &ray)
1067{
1068        int hits = 0;
1069 
1070        stack<BspRayTraversalData> tStack;
1071 
1072        float maxt = 1e6;
1073        float mint = 0;
1074
1075        Intersectable::NewMail();
1076
1077        // test with tree bounding box
1078        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
1079                return 0;
1080
1081        if (mint < 0)
1082                mint = 0;
1083 
1084        maxt += Limits::Threshold;
1085 
1086        Vector3 entp = ray.Extrap(mint);
1087        Vector3 extp = ray.Extrap(maxt);
1088 
1089        BspNode *node = mRoot;
1090        BspNode *farChild;
1091       
1092        while (1)
1093        {
1094                if (!node->IsLeaf())
1095                {
1096                        BspInterior *in = (BspInterior *) node;
1097                       
1098                        Plane3 *splitPlane = in->GetPlane();
1099
1100                        float t = 0;
1101                        bool coplanar = false;
1102               
1103                        int entSide = splitPlane->Side(entp);
1104                        int extSide = splitPlane->Side(extp);
1105
1106                        Vector3 intersection;
1107
1108                        if (entSide < 0)
1109                        {
1110                                node = in->GetBack();
1111
1112                                if(extSide <= 0)
1113                                        continue;
1114                                       
1115                                farChild = in->GetFront(); // plane splits ray
1116
1117                        } else if (entSide > 0)
1118                        {
1119                                node = in->GetFront();
1120
1121                                if (extSide >= 0)
1122                                        continue;
1123
1124                                farChild = in->GetBack();        // plane splits ray                   
1125                        }
1126                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
1127                        {
1128                                node = in->GetFront();
1129                                continue;
1130                        }
1131
1132                        //-- split
1133
1134                        // push data for far child
1135                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1136
1137                        // find intersection with plane between ray origin and exit point
1138                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
1139
1140                } else // compute intersections with objects in leaf
1141                {
1142                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1143                        //ray.leaves.push_back(leaf);
1144      // TODO
1145                        /*ObjectContainer::const_iterator mi;
1146                        for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++mi)
1147                        {
1148                                Intersectable *object = *mi;
1149                                if (!object->Mailed())
1150                                {
1151                                        object->Mail();
1152                                        //ray.meshes.push_back(mesh);
1153                                        hits += object->CastRay(ray);
1154                                }
1155                        }*/
1156
1157                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
1158                                if (ray.intersections[0].mT <= maxt)
1159                                        break;
1160     
1161                        // get the next node from the stack
1162                        if (tStack.empty())
1163                                break;
1164     
1165                        entp = extp;
1166                        mint = maxt;
1167                        BspRayTraversalData &s  = tStack.top();
1168
1169                        node = s.mNode;
1170                        extp = s.mExitPoint;
1171                        maxt = s.mMaxT;
1172
1173                        tStack.pop();
1174                }
1175        }
1176
1177        return hits;
1178}
1179
1180bool BspTree::Export(const string filename)
1181{
1182        Exporter *exporter = Exporter::GetExporter(filename);
1183
1184        if (exporter)
1185        {
1186                exporter->ExportBspTree(*this);
1187                return true;
1188        }       
1189
1190        return false;
1191}
1192//} // GtpVisibilityPreprocessor
Note: See TracBrowser for help on using the repository browser.