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

Revision 327, 35.4 KB checked in by mattausch, 19 years ago (diff)

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