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

Revision 312, 33.1 KB checked in by mattausch, 19 years ago (diff)

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