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

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