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

Revision 328, 36.1 KB checked in by mattausch, 19 years ago (diff)

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