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

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