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

Revision 313, 33.3 KB checked in by mattausch, 19 years ago (diff)

bsp viewcells now work
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),
263mRootCell(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, mRootCell));
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 = mRootCell;
413                                ViewCell *backViewCell = mRootCell;
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, mRootCell);
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, mRootCell);
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                EvaluateLeafStats(tData);
604                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
605
606                // add view cell to leaf
607                leaf->SetViewCell(tData.mViewCell);
608               
609                // remaining polygons are discarded or added to node
610                leaf->ProcessPolygons(tData.mPolygons, mStoreSplitPolys);
611                DEL_PTR(tData.mPolygons);
612
613                return leaf;
614        }
615
616        //-- continue subdivision
617        PolygonContainer *backPolys = new PolygonContainer();
618        PolygonContainer *frontPolys = new PolygonContainer();
619        PolygonContainer coincident;
620       
621        // create new interior node and two leaf nodes
622        BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
623                                                                                  tData.mPolygons,
624                                                                                  frontPolys,
625                                                                                  backPolys,
626                                                                                  &coincident);
627
628        ViewCell *frontViewCell = mRootCell;
629        ViewCell *backViewCell = mRootCell;
630
631#ifdef _DEBUG   
632        if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
633        {       for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
634                        Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ;
635                Debug << endl;}
636#endif
637
638        // extract view cells from coincident polygons according to plane normal
639    // only if front or back polygons are empty
640        ExtractViewCells(&backViewCell,
641                                         &frontViewCell,
642                                         coincident,
643                                         interior->mPlane,
644                                         backPolys->empty(),
645                                         frontPolys->empty());
646       
647        // don't need coincident polygons anymore
648        interior->ProcessPolygons(&coincident, mStoreSplitPolys);
649
650        // push the children on the stack
651        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, backViewCell));
652        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, frontViewCell));
653
654        // cleanup
655        DEL_PTR(tData.mNode);
656        DEL_PTR(tData.mPolygons);
657
658        return interior;
659}
660
661void BspTree::ExtractViewCells(ViewCell **backViewCell,
662                                                           ViewCell **frontViewCell,
663                                                           const PolygonContainer &coincident,
664                                                           const Plane3 splitPlane,
665                                                           const bool extractBack,
666                                                           const bool extractFront) const
667{
668        bool foundFront = !extractFront, foundBack = !extractBack;
669
670        PolygonContainer::const_iterator it, it_end = coincident.end();
671
672        //-- find first view cells in front and back leafs
673        for (it = coincident.begin(); !(foundFront && foundBack) &&
674                (it != it_end); ++ it)
675        {
676                if (DotProd((*it)->GetSupportingPlane().mNormal, splitPlane.mNormal) > 0)
677                {
678                        *backViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
679                        foundBack = true;
680                }
681                else
682                {
683                        *frontViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
684                        foundFront = true;
685                }
686                //if (foundFront) Debug << "front viewCell: " << *frontViewCell << endl;
687                //if (foundBack) Debug << "back viewCell: " << *backViewCell << endl;
688        }
689}
690
691BspInterior *BspTree::SubdivideNode(BspLeaf *leaf,
692                                                                        PolygonContainer *polys,
693                                                                        PolygonContainer *frontPolys,
694                                                                        PolygonContainer *backPolys,
695                                                                        PolygonContainer *coincident)
696{
697        mStat.nodes += 2;
698
699        // add the new nodes to the tree + select subdivision plane
700        BspInterior *interior = new BspInterior(SelectPlane(leaf, *polys));
701
702#ifdef _DEBUG
703        Debug << interior << endl;
704#endif
705
706        // split polygon according to current plane
707        int splits = 0;
708       
709        interior->SplitPolygons(polys, frontPolys, backPolys, coincident, splits, mStoreSplitPolys);
710       
711        mStat.splits += splits;
712
713        BspInterior *parent = leaf->GetParent();
714
715        // replace a link from node's parent
716        if (parent)
717        {
718                parent->ReplaceChildLink(leaf, interior);
719                interior->SetParent(parent);
720        }
721
722        // and setup child links
723        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
724       
725        return interior;
726}
727
728void BspTree::SortSplitCandidates(const PolygonContainer &polys,
729                                                                  const int axis,
730                                                                  vector<SortableEntry> &splitCandidates) const
731{
732  splitCandidates.clear();
733 
734  int requestedSize = 2 * (int)polys.size();
735  // creates a sorted split candidates array 
736  splitCandidates.reserve(requestedSize);
737 
738  PolygonContainer::const_iterator it, it_end = polys.end();
739
740  AxisAlignedBox3 box;
741
742  // insert all queries
743  for(it = polys.begin(); it != it_end; ++ it)
744  {
745          box.Initialize();
746          box.Include(*(*it));
747         
748          splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
749      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
750  }
751 
752  stable_sort(splitCandidates.begin(), splitCandidates.end());
753}
754
755
756float BspTree::BestCostRatio(const PolygonContainer &polys,
757                                                         const AxisAlignedBox3 &box,
758                                                         const int axis,
759                                                         float &position,
760                                                         int &objectsBack,
761                                                         int &objectsFront) const
762{
763        vector<SortableEntry> splitCandidates;
764
765        SortSplitCandidates(polys, axis, splitCandidates);
766       
767        // go through the lists, count the number of objects left and right
768        // and evaluate the following cost funcion:
769        // C = ct_div_ci  + (ol + or)/queries
770       
771        int objectsLeft = 0, objectsRight = (int)polys.size();
772       
773        float minBox = box.Min(axis);
774        float maxBox = box.Max(axis);
775        float boxArea = box.SurfaceArea();
776 
777        float minBand = minBox + sSplitBorder * (maxBox - minBox);
778        float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
779       
780        float minSum = 1e20f;
781        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
782
783        for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
784        {
785                switch ((*ci).type)
786                {
787                        case SortableEntry::POLY_MIN:
788                                ++ objectsLeft;
789                                break;
790                        case SortableEntry::POLY_MAX:
791                            -- objectsRight;
792                                break;
793                        default:
794                                break;
795                }
796               
797                if ((*ci).value > minBand && (*ci).value < maxBand)
798                {
799                        AxisAlignedBox3 lbox = box;
800                        AxisAlignedBox3 rbox = box;
801                        lbox.SetMax(axis, (*ci).value);
802                        rbox.SetMin(axis, (*ci).value);
803
804                        float sum = objectsLeft * lbox.SurfaceArea() +
805                                                objectsRight * rbox.SurfaceArea();
806     
807                        if (sum < minSum)
808                        {
809                                minSum = sum;
810                                position = (*ci).value;
811
812                                objectsBack = objectsLeft;
813                                objectsFront = objectsRight;
814                        }
815                }
816        }
817 
818        float oldCost = (float)polys.size();
819        float newCost = sCt_div_ci + minSum / boxArea;
820        float ratio = newCost / oldCost;
821
822
823#if 0
824  Debug << "====================" << endl;
825  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
826      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
827#endif
828  return ratio;
829}
830
831Plane3 BspTree::SelectPlane(BspLeaf *leaf, PolygonContainer &polys)
832{
833        if (polys.size() == 0)
834        {
835                Debug << "Warning: No split candidate available\n";
836                return Plane3();
837        }
838
839        if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
840                ((int)polys.size() > sTermMaxPolysForAxisAligned))
841        {
842                AxisAlignedBox3 box;
843                box.Initialize();
844       
845                // todo: area subdivision
846                Polygon3::IncludeInBox(polys, box);
847       
848                int objectsBack = 0, objectsFront = 0;
849                int axis = 0;
850                float costRatio = MAX_FLOAT;
851                Vector3 position;
852
853                for (int i = 0; i < 3; ++ i)
854                {
855                        float p = 0;
856                        float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
857                       
858                        if (r < costRatio)
859                        {
860                                costRatio = r;
861                                axis = i;
862                                position = p;
863                        }
864                }
865               
866                if (costRatio < sMaxCostRatio)
867                {
868                        Vector3 norm(0,0,0); norm[axis] = 1.0f;
869                        return Plane3(norm, position);
870                }
871                /*int axis = box.Size().DrivingAxis();
872                Vector3 norm(0,0,0); norm[axis] = 1;
873                Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
874                return Plane3(norm, position);*/
875        }
876
877        // simplest strategy: just take next polygon
878        if (sSplitPlaneStrategy & NEXT_POLYGON)
879        {
880                return polys.front()->GetSupportingPlane();
881        }
882
883        // use heuristics to find appropriate plane
884        return SelectPlaneHeuristics(polys, sMaxCandidates);
885}
886
887Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer &polys, int maxTests)
888{
889        float lowestCost = MAX_FLOAT;
890        int bestPlaneIdx = 0;
891       
892        int limit = maxTests > 0 ? Min((int)polys.size(), maxTests) : (int)polys.size();
893       
894        int candidateIdx = limit;
895       
896        for (int i = 0; i < limit; ++ i)
897        {
898                candidateIdx = GetNextCandidateIdx(candidateIdx, polys);
899
900                Plane3 candidatePlane = polys[candidateIdx]->GetSupportingPlane();
901               
902                // evaluate current candidate
903                float candidateCost = EvalSplitPlane(polys, candidatePlane);
904                       
905                if (candidateCost < lowestCost)
906                {
907                        bestPlaneIdx = candidateIdx;
908                        lowestCost = candidateCost;
909                }
910        }
911       
912        //Debug << "Plane lowest cost: " << lowestCost << endl;
913        return polys[bestPlaneIdx]->GetSupportingPlane();
914}
915
916int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
917{
918        int candidateIdx = Random(currentIdx--);
919       
920        //Debug << "new candidate " << candidateIdx << endl;
921
922        // swap candidates to avoid testing same plane 2 times
923        Polygon3 *p = polys[candidateIdx];
924        polys[candidateIdx] = polys[currentIdx];
925        polys[currentIdx] = p;
926       
927        return currentIdx;
928}
929
930float BspTree::EvalSplitPlane(PolygonContainer &polys, const Plane3 &candidatePlane)
931{
932        float val = 0;
933       
934        if (sSplitPlaneStrategy & VERTICAL_AXIS)
935        {
936                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
937                // we put a penalty on the dot product between the "tiny" vertical axis
938                // and the split plane axis
939                val += sVerticalSplitsFactor *
940                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
941        }
942
943        //-- strategies where the effect of the split plane on the polygons is tested
944        if (!((sSplitPlaneStrategy & BALANCED_POLYS) ||
945                  (sSplitPlaneStrategy & LEAST_SPLITS)   ||
946                  (sSplitPlaneStrategy & LARGEST_POLY_AREA) ||
947                  (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)))
948                return val;
949       
950        PolygonContainer::const_iterator it, it_end = polys.end();
951        float sumBalancedPolys = 0;
952        float sumSplits = 0;
953        float sumPolyArea = 0;
954        float sumBalancedViewCells = 0;
955        //float totalArea = 0;
956
957        // container for view cells
958        ObjectContainer frontViewCells;
959        ObjectContainer backViewCells;
960
961        for (it = polys.begin(); it != it_end; ++ it)
962        {
963                int classification = (*it)->ClassifyPlane(candidatePlane);
964
965                if (sSplitPlaneStrategy & BALANCED_POLYS)
966                        sumBalancedPolys += sBalancedPolysTable[classification];
967               
968                if (sSplitPlaneStrategy & LEAST_SPLITS)
969                        sumSplits += sLeastSplitsTable[classification];
970
971                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
972                {
973                        if (classification == Polygon3::COINCIDENT)
974                        {               
975                                float area = (*it)->GetArea();
976                                //Debug << "polygon area: " << area << " ";
977                                sumPolyArea += area;
978                        }
979                        //totalArea += area;
980                }
981
982                // assign view cells to back or front according to classificaion
983                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
984                {
985                        MeshInstance *viewCell = (*it)->mParent;
986               
987                        if (classification == Polygon3::FRONT_SIDE)
988                                frontViewCells.push_back(viewCell);
989                        else if (viewCell && (classification == Polygon3::BACK_SIDE))
990                                backViewCells.push_back(viewCell);
991                }
992        }
993
994        if (sSplitPlaneStrategy & BALANCED_POLYS)
995                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
996
997        if (sSplitPlaneStrategy & LEAST_SPLITS)   
998                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
999
1000        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1001                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea; // HACK
1002
1003        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1004        {
1005                // count number of unique view cells
1006                sort(frontViewCells.begin(), frontViewCells.end());
1007                sort(backViewCells.begin(), backViewCells.end());
1008
1009                ObjectContainer::const_iterator frontIt, frontIt_end = frontViewCells.end();
1010       
1011                Intersectable *vc = NULL;
1012                // increase counter for view cells in front of plane
1013                for (frontIt = frontViewCells.begin(); frontIt != frontIt_end; ++frontIt)
1014                {
1015                        if (*frontIt != vc)
1016                        {
1017                                vc = *frontIt;
1018                                sumBalancedViewCells += 1.0f;
1019                        }
1020                }
1021
1022                ObjectContainer::const_iterator backIt, backIt_end = backViewCells.end();
1023                vc = NULL;
1024                // decrease counter for view cells on back side of plane
1025                for (backIt = backViewCells.begin(); backIt != backIt_end; ++backIt)
1026                {
1027                        if (*backIt != vc)
1028                        {
1029                                vc = *backIt;
1030                                sumBalancedViewCells -= 1.0f;
1031                        }
1032                }
1033
1034                val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1035                        (float)(frontViewCells.size() + backViewCells.size());
1036        }
1037
1038        // return linear combination of the sums
1039        return val;
1040}
1041
1042void BspTree::ParseEnvironment()
1043{
1044        //-- parse bsp cell tree construction method
1045        char constructionMethodStr[60];
1046       
1047        environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr);
1048
1049        sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1050       
1051        if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1052                sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1053        else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1054                sConstructionMethod = FROM_SCENE_GEOMETRY;
1055        else if (strcmp(constructionMethodStr, "fromRays") == 0)
1056                sConstructionMethod = FROM_RAYS;
1057        else
1058        {
1059                cerr << "Wrong construction method " << constructionMethodStr << endl;
1060                exit(1);
1061    }
1062
1063        Debug << "Construction method: " << constructionMethodStr << endl;
1064
1065        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1066        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1067        environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned",
1068                                                         sTermMaxPolysForAxisAligned);
1069        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
1070        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1071
1072        // need kdtree criteria for axis aligned split
1073        environment->GetFloatValue("MeshKdTree.Termination.ct_div_ci", sCt_div_ci);
1074        environment->GetFloatValue("MeshKdTree.splitBorder", sSplitBorder);
1075        environment->GetFloatValue("MeshKdTree.Termination.maxCostRatio", sMaxCostRatio);
1076
1077    Debug << "BSP max depth: " << sTermMaxDepth << endl;
1078        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1079        Debug << "BSP max candidates: " << sMaxCandidates << endl;
1080       
1081        Debug << "Split plane strategy: ";
1082        if (sSplitPlaneStrategy & NEXT_POLYGON)
1083                Debug << "next polygon ";
1084        if (sSplitPlaneStrategy & AXIS_ALIGNED)
1085                Debug << "axis aligned ";
1086        if (sSplitPlaneStrategy & LEAST_SPLITS)     
1087                Debug << "least splits ";
1088        if (sSplitPlaneStrategy & BALANCED_POLYS)
1089                Debug << "balanced polygons ";
1090        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1091                Debug << "balanced view cells ";
1092        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1093                Debug << "largest polygon area ";
1094        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1095                Debug << "vertical axis ";
1096
1097        Debug << endl;
1098}
1099
1100void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
1101{
1102        stack<BspNode *> nodeStack;
1103        nodeStack.push(mRoot);
1104 
1105        while (!nodeStack.empty())
1106        {
1107                BspNode *node = nodeStack.top();
1108   
1109                nodeStack.pop();
1110   
1111                if (node->IsLeaf())
1112                {
1113                        BspLeaf *leaf = (BspLeaf *)node;
1114                       
1115                        leaves.push_back(leaf);
1116                } else
1117                {
1118                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1119                        nodeStack.push(interior->GetBack());
1120                        nodeStack.push(interior->GetFront());
1121                }
1122        }
1123}
1124
1125AxisAlignedBox3 BspTree::GetBoundingBox() const
1126{
1127        return mBox;
1128}
1129
1130BspNode *BspTree::GetRoot() const
1131{
1132        return mRoot;
1133}
1134
1135bool BspTree::StorePolys() const
1136{
1137        return mStoreSplitPolys;
1138}
1139
1140void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1141{
1142        // the node became a leaf -> evaluate stats for leafs
1143        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1144
1145        if (data.mDepth >= sTermMaxDepth)
1146        {
1147                ++ mStat.maxDepthNodes;
1148        }
1149
1150        // store maximal and minimal depth
1151        if (data.mDepth > mStat.maxDepth)
1152                mStat.maxDepth = data.mDepth;
1153        if (data.mDepth < mStat.minDepth)
1154                mStat.minDepth = data.mDepth;
1155
1156        // accumulate depth to compute average
1157        mStat.accumDepth += data.mDepth;
1158
1159        if (leaf->mViewCell)
1160                ++ mStat.viewCellLeaves;
1161
1162#ifdef _DEBUG
1163        Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), #polygons: " <<
1164          data.mPolygons->size() << " (max: " << sTermMaxPolygons << ")" << endl;
1165#endif
1166}
1167
1168int BspTree::CastRay(Ray &ray)
1169{
1170        int hits = 0;
1171 
1172        stack<BspRayTraversalData> tStack;
1173 
1174        float maxt = 1e6;
1175        float mint = 0;
1176       
1177        Intersectable::NewMail();
1178
1179        // test with tree bounding box
1180        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
1181                return 0;
1182
1183        if (mint < 0) // start ray from origin
1184                mint = 0;
1185
1186        // bound ray
1187        if ((ray.GetType() == Ray::LOCAL_RAY)   &&
1188                ((int)ray.intersections.size() > 0) &&
1189            (ray.intersections[0].mT <= maxt))
1190        {
1191                maxt = ray.intersections[0].mT;
1192    }
1193 
1194        Vector3 entp = ray.Extrap(mint);
1195        Vector3 extp = ray.Extrap(maxt);
1196 
1197        BspNode *node = mRoot;
1198        BspNode *farChild = NULL;
1199       
1200        while (1)
1201        {
1202                if (!node->IsLeaf())
1203                {
1204                        BspInterior *in = (BspInterior *) node;
1205                       
1206                        Plane3 *splitPlane = in->GetPlane();
1207
1208                        float t = 0;
1209                        bool coplanar = false;
1210               
1211                        int entSide = splitPlane->Side(entp);
1212                        int extSide = splitPlane->Side(extp);
1213
1214                        Vector3 intersection;
1215
1216                        if (entSide < 0)
1217                        {
1218                                node = in->GetBack();
1219
1220                                if(extSide <= 0) // plane does not split ray => no far child
1221                                        continue;
1222                                       
1223                                farChild = in->GetFront(); // plane splits ray
1224
1225                        } else if (entSide > 0)
1226                        {
1227                                node = in->GetFront();
1228
1229                                if (extSide >= 0) // plane does not split ray => no far child
1230                                        continue;
1231
1232                                farChild = in->GetBack(); // plane splits ray                   
1233                        }
1234                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
1235                        {
1236                                node = in->GetFront();
1237                                continue;
1238                        }
1239
1240                        // push data for far child
1241                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1242
1243                        // find intersection of ray segment with plane
1244                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
1245                       
1246                } else // reached leaf => intersection with view cell
1247                {
1248                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1249     
1250                        if (!leaf->mViewCell->Mailed())
1251                        {
1252                                ray.viewCells.push_back(leaf->mViewCell);
1253                                leaf->mViewCell->Mail();
1254                                ++ hits;
1255                        }
1256                       
1257                        //-- fetch the next far child from the stack
1258                        if (tStack.empty())
1259                                break;
1260     
1261                        entp = extp;
1262                        mint = maxt; // NOTE: need this?
1263                        BspRayTraversalData &s = tStack.top();
1264
1265                        node = s.mNode;
1266                        extp = s.mExitPoint;
1267                        maxt = s.mMaxT;
1268
1269                        //Debug << "leaf: new entrypt: " << entp << " new extp: " << extp << endl;
1270
1271                        tStack.pop();
1272                }
1273        }
1274
1275        return hits;
1276}
1277
1278bool BspTree::Export(const string filename)
1279{
1280        Exporter *exporter = Exporter::GetExporter(filename);
1281
1282        if (exporter)
1283        {
1284                exporter->ExportBspTree(*this);
1285                return true;
1286        }       
1287
1288        return false;
1289}
1290
1291void BspTree::CollectViewCells(BspNode *n, ViewCellContainer &viewCells)
1292{
1293        stack<BspNode *> nodeStack;
1294
1295        nodeStack.push(n);
1296
1297        while (!nodeStack.empty())
1298        {
1299                BspNode *node = nodeStack.top();
1300                nodeStack.pop();
1301
1302                if (node->IsLeaf())
1303                {
1304                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1305
1306                        if (!viewCell->Mailed())
1307                        {
1308                                viewCell->Mail();
1309                                viewCells.push_back(viewCell);
1310                        }
1311                }
1312                else
1313                {
1314                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1315                        nodeStack.push(interior->mFront);
1316                        nodeStack.push(interior->mBack);
1317                }
1318        }
1319}
1320//} // GtpVisibilityPreprocessor
Note: See TracBrowser for help on using the repository browser.