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

Revision 402, 59.9 KB checked in by mattausch, 19 years ago (diff)

fixed pvs criterium
fixed pvs bug in bsp view cells
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::sTermMinPvs = 20;
18int BspTree::sTermMaxDepth = 20;
19float BspTree::sTermMinArea = 0.001f;
20int BspTree::sMaxPolyCandidates = 10;
21int BspTree::sMaxRayCandidates = 10;
22int BspTree::sSplitPlaneStrategy = BALANCED_POLYS;
23int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS;
24int BspTree::sTermMaxPolysForAxisAligned = 50;
25int BspTree::sTermMaxObjectsForAxisAligned = 50;
26int BspTree::sTermMaxRaysForAxisAligned = -1;
27int BspTree::sTermMaxRays = -1;
28int BspTree::sMinPvsDif = 10;
29int BspTree::sMinPvs = 10;
30int BspTree::sMaxPvs = 500;
31
32float BspTree::sCt_div_ci = 1.0f;
33float BspTree::sSplitBorder = 1.0f;
34float BspTree::sMaxCostRatio = 0.9f;
35
36//-- factors for bsp tree split plane heuristics
37
38float BspTree::sLeastSplitsFactor = 1.0f;
39float BspTree::sBalancedPolysFactor = 1.0f;
40float BspTree::sBalancedViewCellsFactor = 1.0f;
41
42// NOTE:  very important criterium for 2.5d scenes
43float BspTree::sVerticalSplitsFactor = 1.0f;
44float BspTree::sLargestPolyAreaFactor = 1.0f;
45float BspTree::sBlockedRaysFactor = 1.0f;
46float BspTree::sLeastRaySplitsFactor = 1.0f;
47float BspTree::sBalancedRaysFactor = 1.0f;
48float BspTree::sPvsFactor = 1.0f;
49
50int BspNode::mailID = 1;
51
52/** Evaluates split plane classification with respect to the plane's
53        contribution for a minimum number splits in the tree.
54*/
55float BspTree::sLeastPolySplitsTable[] = {0, 0, 1, 0};
56/** Evaluates split plane classification with respect to the plane's
57        contribution for a balanced tree.
58*/
59float BspTree::sBalancedPolysTable[] = {1, -1, 0, 0};
60
61/** Evaluates split plane classification with respect to the plane's
62        contribution for a minimum number of ray splits.
63*/
64float BspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
65/** Evaluates split plane classification with respect to the plane's
66        contribution for balanced rays.
67*/
68float BspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
69
70/****************************************************************/
71/*                  class BspNode implementation                */
72/****************************************************************/
73
74BspNode::BspNode():
75mParent(NULL)
76{}
77
78BspNode::BspNode(BspInterior *parent):
79mParent(parent)
80{}
81
82
83bool BspNode::IsRoot() const
84{
85        return mParent == NULL;
86}
87
88BspInterior *BspNode::GetParent()
89{
90        return mParent;
91}
92
93void BspNode::SetParent(BspInterior *parent)
94{
95        mParent = parent;
96}
97
98/****************************************************************/
99/*              class BspInterior implementation                */
100/****************************************************************/
101
102
103BspInterior::BspInterior(const Plane3 &plane):
104mPlane(plane), mFront(NULL), mBack(NULL)
105{}
106
107bool BspInterior::IsLeaf() const
108{
109        return false;
110}
111
112BspNode *BspInterior::GetBack()
113{
114        return mBack;
115}
116
117BspNode *BspInterior::GetFront()
118{
119        return mFront;
120}
121
122Plane3 *BspInterior::GetPlane()
123{
124        return &mPlane;
125}
126
127void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild)
128{
129        if (mBack == oldChild)
130                mBack = newChild;
131        else
132                mFront = newChild;
133}
134
135void BspInterior::SetupChildLinks(BspNode *b, BspNode *f)
136{
137    mBack = b;
138    mFront = f;
139}
140
141int BspInterior::SplitPolygons(PolygonContainer &polys,
142                                                           PolygonContainer &frontPolys,
143                                                           PolygonContainer &backPolys,
144                                                           PolygonContainer &coincident)
145{
146        Polygon3 *splitPoly = NULL;
147
148        int splits = 0;
149
150#ifdef _Debug
151        Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
152#endif
153        while (!polys.empty())
154        {
155                Polygon3 *poly = polys.back();
156                polys.pop_back();
157
158                //Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
159
160                // classify polygon
161                const int cf = poly->ClassifyPlane(mPlane);
162
163                Polygon3 *front_piece = NULL;
164                Polygon3 *back_piece = NULL;
165       
166                VertexContainer splitVertices;
167
168                switch (cf)
169                {
170                        case Polygon3::COINCIDENT:
171                                coincident.push_back(poly);
172                                break;                 
173                        case Polygon3::FRONT_SIDE:     
174                                frontPolys.push_back(poly);
175                                break;
176                        case Polygon3::BACK_SIDE:
177                                backPolys.push_back(poly);
178                                break;
179                        case Polygon3::SPLIT:
180                                front_piece = new Polygon3(poly->mParent);
181                                back_piece = new Polygon3(poly->mParent);
182
183                                //-- split polygon into front and back part
184                                poly->Split(mPlane,
185                                                        *front_piece,
186                                                        *back_piece,
187                                                        splitVertices);
188                                       
189                                ++ splits; // increase number of splits
190
191                                //-- inherit rays from parent polygon for blocked ray criterium
192                                poly->InheritRays(*front_piece, *back_piece);
193                                //Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl;
194                               
195                                // check if polygons still valid
196                                if (front_piece->Valid())
197                                        frontPolys.push_back(front_piece);
198                                else
199                                        DEL_PTR(front_piece);
200                               
201                                if (back_piece->Valid())
202                                        backPolys.push_back(back_piece);
203                                else                           
204                                        DEL_PTR(back_piece);
205                               
206#ifdef _DEBUG
207                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
208#endif
209                                DEL_PTR(poly);                 
210                                break;
211                        default:
212                Debug << "SHOULD NEVER COME HERE\n";
213                                break;
214                }
215        }
216
217        return splits;
218}
219
220/****************************************************************/
221/*                  class BspLeaf implementation                */
222/****************************************************************/
223BspLeaf::BspLeaf(): mViewCell(NULL)
224{
225}
226
227BspLeaf::BspLeaf(BspViewCell *viewCell):
228mViewCell(viewCell)
229{
230}
231
232BspLeaf::BspLeaf(BspInterior *parent):
233BspNode(parent), mViewCell(NULL)
234{}
235
236BspLeaf::BspLeaf(BspInterior *parent, BspViewCell *viewCell):
237BspNode(parent), mViewCell(viewCell)
238{
239}
240
241BspViewCell *BspLeaf::GetViewCell() const
242{
243        return mViewCell;
244}
245
246void BspLeaf::SetViewCell(BspViewCell *viewCell)
247{
248        mViewCell = viewCell;
249}
250
251bool BspLeaf::IsLeaf() const
252{
253        return true;
254}
255
256void BspLeaf::AddToPvs(const BoundedRayContainer &rays,
257                                           int &sampleContributions,
258                                           int &contributingSamples)
259{
260        sampleContributions = 0;
261        contributingSamples = 0;
262
263    BoundedRayContainer::const_iterator it, it_end = rays.end();
264
265        // add contributions from samples to the PVS
266        for (it = rays.begin(); it != it_end; ++ it)
267        {
268                int contribution = 0;
269                Ray *ray = (*it)->mRay;
270                       
271                if (!ray->intersections.empty())
272                {       
273            contribution += mViewCell->GetPvs().AddSample(ray->intersections[0].mObject);
274                }
275
276                if (ray->sourceObject.mObject)
277                        contribution += mViewCell->GetPvs().AddSample(ray->sourceObject.mObject);
278
279                if (contribution > 0)
280                {
281                        sampleContributions += contribution;
282                        ++ contributingSamples;
283                }
284                // warning: intersections not ordered
285                ray->bspIntersections.push_back(Ray::BspIntersection((*it)->mMinT, this));
286        }
287}
288
289
290/****************************************************************/
291/*                  class BspTree implementation                */
292/****************************************************************/
293
294BspTree::BspTree(BspViewCell *viewCell):
295mRootCell(viewCell), mRoot(NULL), mGenerateViewCells(false),
296mStorePiercingRays(true)
297{
298        Randomize(); // initialise random generator for heuristics
299}
300 
301const BspTreeStatistics &BspTree::GetStatistics() const
302{
303        return mStat;
304}
305
306void BspViewCellsStatistics::Print(ostream &app) const
307{
308        app << "===== BspViewCells statistics ===============\n";
309
310        app << setprecision(4);
311
312        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
313
314        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
315
316        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
317
318        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
319
320        app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;
321
322        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
323
324        app << "#N_AVGBSPLEAVES (average number of BSP leaves per view cell )\n" << AvgBspLeaves() << endl;
325
326        app << "#N_MAXBSPLEAVES ( maximal number of BSP leaves per view cell )\n" << maxBspLeaves << endl;
327       
328        app << "===== END OF BspViewCells statistics ==========\n";
329}
330
331void BspTreeStatistics::Print(ostream &app) const
332{
333        app << "===== BspTree statistics ===============\n";
334
335        app << setprecision(4);
336
337        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
338
339        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
340
341        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
342
343        app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
344
345        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
346        maxDepthNodes * 100 / (double)Leaves() << endl;
347
348        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
349
350        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
351
352        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
353
354        app << "#N_INPUT_POLYGONS (number of input polygons )\n" <<     polys << endl;
355
356        //app << "#N_PVS: " << pvs << endl;
357
358        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
359                 (polys + splits) / (double)polys << endl;
360       
361        app << "===== END OF BspTree statistics ==========\n";
362}
363
364
365BspTree::~BspTree()
366{
367        std::stack<BspNode *> tStack;
368
369        tStack.push(mRoot);
370
371        while (!tStack.empty())
372        {
373                BspNode *node = tStack.top();
374
375            tStack.pop();
376       
377                if (!node->IsLeaf())
378                {
379                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
380
381                        // push the children on the stack (there are always two children)
382                        tStack.push(interior->GetBack());
383                        tStack.push(interior->GetFront());
384                }
385
386                DEL_PTR(node);
387        }
388}
389
390void BspTree::InsertViewCell(ViewCell *viewCell)
391{
392        PolygonContainer *polys = new PolygonContainer();
393
394        // extract polygons that guide the split process
395        mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
396        mBox.Include(viewCell->GetBox()); // add to BSP aabb
397
398        InsertPolygons(polys);
399}
400
401void BspTree::InsertPolygons(PolygonContainer *polys)
402{       
403        std::stack<BspTraversalData> tStack;
404       
405        // traverse existing tree or create new tree
406    if (!mRoot)
407                mRoot = new BspLeaf();
408
409        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0,
410                                                                 mBox.SurfaceArea(), new BspNodeGeometry()));
411
412        while (!tStack.empty())
413        {
414                // filter polygons donw the tree
415                BspTraversalData tData = tStack.top();
416            tStack.pop();
417                       
418                if (!tData.mNode->IsLeaf())
419                {
420                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
421
422                        //-- filter view cell polygons down the tree until a leaf is reached
423                        if (!tData.mPolygons->empty())
424                        {
425                                PolygonContainer *frontPolys = new PolygonContainer();
426                                PolygonContainer *backPolys = new PolygonContainer();
427                                PolygonContainer coincident;
428
429                                int splits = 0;
430               
431                                // split viewcell polygons with respect to split plane
432                                splits += interior->SplitPolygons(*tData.mPolygons,
433                                                                                                  *frontPolys,
434                                                                                                  *backPolys,
435                                                                                                  coincident);
436                               
437                                // extract view cells associated with the split polygons
438                                ViewCell *frontViewCell = mRootCell;
439                                ViewCell *backViewCell = mRootCell;
440                       
441                                BspTraversalData frontData(interior->GetFront(),
442                                                                                   frontPolys,
443                                                                                   tData.mDepth + 1,
444                                                                                   mRootCell,   
445                                                                                   tData.mRays,
446                                                                                   tData.mPvs,
447                                                                                   mBox.SurfaceArea(),
448                                                                                   new BspNodeGeometry());
449
450                                BspTraversalData backData(interior->GetBack(),
451                                                                                  backPolys,
452                                                                                  tData.mDepth + 1,
453                                                                                  mRootCell,   
454                                                                                  tData.mRays,
455                                                                                  tData.mPvs,
456                                                                                  mBox.SurfaceArea(),
457                                                                                  new BspNodeGeometry());
458
459                                if (!mGenerateViewCells)
460                                {
461                                        ExtractViewCells(frontData,
462                                                                         backData,
463                                                                         coincident,
464                                                                         interior->mPlane);
465                                }
466
467                                // don't need coincident polygons anymore
468                                CLEAR_CONTAINER(coincident);
469
470                                mStat.splits += splits;
471
472                                // push the children on the stack
473                                tStack.push(frontData);
474                                tStack.push(backData);
475                        }
476
477                        // cleanup
478                        DEL_PTR(tData.mPolygons);
479                }
480                else
481                {
482                        // reached leaf => subdivide current viewcell
483                        BspNode *subRoot = Subdivide(tStack, tData);
484                }
485        }
486}
487
488int BspTree::AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent)
489{
490        FaceContainer::const_iterator fi;
491       
492        // copy the face data to polygons
493        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
494        {
495                Polygon3 *poly = new Polygon3((*fi), mesh);
496               
497                if (poly->Valid())
498                {
499                        poly->mParent = parent; // set parent intersectable
500                        polys.push_back(poly);
501                }
502                else
503                        DEL_PTR(poly);
504        }
505        return (int)mesh->mFaces.size();
506}
507
508int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
509                                                          PolygonContainer &polys,
510                                                          int maxObjects)
511{
512        int limit = (maxObjects > 0) ?
513                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
514 
515        int polysSize = 0;
516
517        for (int i = 0; i < limit; ++ i)
518        {
519                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
520                {
521                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
522                        polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
523                }
524        }
525
526        return polysSize;
527}
528
529int BspTree::AddToPolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
530{
531        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
532 
533        for (int i = 0; i < limit; ++i)
534        {
535                Intersectable *object = objects[i];//*it;
536                Mesh *mesh = NULL;
537
538                switch (object->Type()) // extract the meshes
539                {
540                case Intersectable::MESH_INSTANCE:
541                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
542                        break;
543                case Intersectable::VIEW_CELL:
544                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
545                        break;
546                        // TODO: handle transformed mesh instances
547                default:
548                        Debug << "intersectable type not supported" << endl;
549                        break;
550                }
551               
552        if (mesh) // copy the mesh data to polygons
553                {
554                        mBox.Include(object->GetBox()); // add to BSP tree aabb
555                        AddMeshToPolygons(mesh, polys, mRootCell);
556                }
557        }
558
559        return (int)polys.size();
560}
561
562void BspTree::Construct(const ViewCellContainer &viewCells)
563{
564        mStat.nodes = 1;
565        mBox.Initialize();      // initialise bsp tree bounding box
566
567        // copy view cell meshes into one big polygon soup
568        PolygonContainer *polys = new PolygonContainer();
569        mStat.polys = AddToPolygonSoup(viewCells, *polys);
570
571        // construct tree from the view cell polygons
572        Construct(polys, new BoundedRayContainer());
573}
574
575
576void BspTree::Construct(const ObjectContainer &objects)
577{
578        mStat.nodes = 1;
579        mBox.Initialize();      // initialise bsp tree bounding box
580       
581        PolygonContainer *polys = new PolygonContainer();
582       
583        // copy mesh instance polygons into one big polygon soup
584        mStat.polys = AddToPolygonSoup(objects, *polys);
585
586        // construct tree from polygon soup
587        Construct(polys, new BoundedRayContainer());
588}
589
590void BspTree::Construct(const RayContainer &sampleRays)
591{
592        mStat.nodes = 1;
593        mBox.Initialize();      // initialise BSP tree bounding box
594       
595        PolygonContainer *polys = new PolygonContainer();
596        BoundedRayContainer *rays = new BoundedRayContainer();
597
598        RayContainer::const_iterator rit, rit_end = sampleRays.end();
599
600        long startTime = GetTime();
601
602        Debug << "**** Extracting polygons from rays ****\n";
603
604        std::map<Face *, Polygon3 *> facePolyMap;
605
606        //-- extract polygons intersected by the rays
607        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
608        {
609                Ray *ray = *rit;
610       
611                // get ray-face intersection. Store polygon representing the rays together
612                // with rays intersecting the face.
613                if (!ray->intersections.empty())
614                {
615                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->intersections[0].mObject);
616                        Face *face = obj->GetMesh()->mFaces[ray->intersections[0].mFace];
617
618                        std::map<Face *, Polygon3 *>::iterator it = facePolyMap.find(face);
619
620                        if (it != facePolyMap.end())
621                        {
622                                //store rays if needed for heuristics
623                                if (sSplitPlaneStrategy & BLOCKED_RAYS)
624                                        (*it).second->mPiercingRays.push_back(ray);
625                        }
626                        else
627                        {       //store rays if needed for heuristics
628                                Polygon3 *poly = new Polygon3(face, obj->GetMesh());
629                                poly->mParent = obj;
630                                polys->push_back(poly);
631
632                                if (sSplitPlaneStrategy & BLOCKED_RAYS)
633                                        poly->mPiercingRays.push_back(ray);
634
635                                facePolyMap[face] = poly;
636                        }
637                }
638        }
639       
640        facePolyMap.clear();
641
642        // compue bounding box
643        Polygon3::IncludeInBox(*polys, mBox);
644
645        //-- store rays
646        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
647        {
648                Ray *ray = *rit;
649        ray->SetId(-1); // reset id
650
651                float minT, maxT;
652                if (BoundRay(*ray, minT, maxT))
653                        rays->push_back(new BoundedRay(ray, minT, maxT));
654        }
655
656        mStat.polys = (int)polys->size();
657
658        Debug << "**** Finished polygon extraction ****" << endl;
659        Debug << (int)polys->size() << " polys extracted from " << (int)sampleRays.size() << " rays" << endl;
660        Debug << "extraction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
661
662        Construct(polys, rays);
663}
664
665void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays)
666{
667        std::stack<BspTraversalData> tStack;
668
669        mRoot = new BspLeaf();
670
671        BspNodeGeometry *cell = new BspNodeGeometry();
672        ConstructGeometry(mRoot, *cell);
673
674        BspTraversalData tData(mRoot, polys, 0, mRootCell, rays,
675                                                   ComputePvsSize(*rays), cell->GetArea(), cell);
676
677        tStack.push(tData);
678
679        long startTime = GetTime();
680        cout << "**** Contructing bsp tree ****\n";
681
682        while (!tStack.empty())
683        {
684                tData = tStack.top();
685            tStack.pop();
686
687                // subdivide leaf node
688                BspNode *subRoot = Subdivide(tStack, tData);
689        }
690
691        cout << "**** Finished tree construction ****\n";
692        Debug << "BSP tree contruction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
693}
694
695inline bool BspTree::TerminationCriteriaMet(const BspTraversalData &data) const
696{
697        return
698                (((int)data.mPolygons->size() <= sTermMaxPolygons) ||
699                 ((int)data.mRays->size() <= sTermMaxRays) ||
700                 (data.mPvs <= sTermMinPvs) ||
701                 (data.mArea <= sTermMinArea) ||
702                 (data.mDepth >= sTermMaxDepth));
703}
704
705BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
706{
707        //-- terminate traversal 
708        if (TerminationCriteriaMet(tData))             
709        {
710                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
711       
712                BspViewCell *viewCell;
713
714                // generate new view cell for each leaf
715                if (mGenerateViewCells)
716                {
717                        viewCell = dynamic_cast<BspViewCell *>(ViewCell::Generate());
718                }
719                else
720                {
721                        // add view cell to leaf
722                        viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
723                }
724
725                leaf->SetViewCell(viewCell);
726                viewCell->mBspLeaves.push_back(leaf);
727
728                //-- add pvs
729                if (viewCell != mRootCell)
730                {
731                        int conSamp = 0, sampCon = 0;
732                        leaf->AddToPvs(*tData.mRays, conSamp, sampCon);
733                       
734                        mStat.contributingSamples += conSamp;
735                        mStat.sampleContributions += sampCon;
736                }
737
738                EvaluateLeafStats(tData);
739               
740                //-- clean up
741               
742                // discard polygons
743                CLEAR_CONTAINER(*tData.mPolygons);
744                // discard rays
745                CLEAR_CONTAINER(*tData.mRays);
746
747                DEL_PTR(tData.mPolygons);
748                DEL_PTR(tData.mRays);
749                DEL_PTR(tData.mGeometry);
750               
751                return leaf;
752        }
753
754        //-- continue subdivision
755        PolygonContainer coincident;
756       
757        PolygonContainer *frontPolys = new PolygonContainer();
758        PolygonContainer *backPolys = new PolygonContainer();
759
760        BoundedRayContainer *frontRays = new BoundedRayContainer();
761        BoundedRayContainer *backRays = new BoundedRayContainer();
762       
763        BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
764                                                                new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
765        BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
766                                                           new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
767
768        // create new interior node and two leaf nodes
769        BspInterior *interior = SubdivideNode(tData,
770                                                                                  tFrontData,
771                                                                                  tBackData,
772                                                                                  coincident);
773
774#ifdef _DEBUG   
775        if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
776        {       for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
777                        Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ;
778                Debug << endl;}
779#endif
780
781        // extract view cells from coincident polygons according to plane normal
782    // only if front or back polygons are empty
783        if (!mGenerateViewCells)
784        {
785                ExtractViewCells(tFrontData,
786                                                 tBackData,
787                                                 coincident,
788                                                 interior->mPlane);
789                                                 
790        }
791
792        // don't need coincident polygons anymory
793        CLEAR_CONTAINER(coincident);
794
795        // push the children on the stack
796        tStack.push(tFrontData);
797        tStack.push(tBackData);
798
799        // cleanup
800        DEL_PTR(tData.mNode);
801        DEL_PTR(tData.mPolygons);
802        DEL_PTR(tData.mRays);
803        DEL_PTR(tData.mGeometry);               
804
805        return interior;
806}
807
808void BspTree::ExtractViewCells(BspTraversalData &frontData,
809                                                           BspTraversalData &backData,
810                                                           const PolygonContainer &coincident,
811                                                           const Plane3 splitPlane) const
812{
813        // if not empty, tree is further subdivided => don't have to find view cell
814        bool foundFront = !frontData.mPolygons->empty();
815        bool foundBack = !frontData.mPolygons->empty();
816
817        PolygonContainer::const_iterator it =
818                coincident.begin(), it_end = coincident.end();
819
820        //-- find first view cells in front and back leafs
821        for (; !(foundFront && foundBack) && (it != it_end); ++ it)
822        {
823                if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
824                {
825                        backData.mViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
826                        foundBack = true;
827                }
828                else
829                {
830                        frontData.mViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
831                        foundFront = true;
832                }
833        }
834}
835
836BspInterior *BspTree::SubdivideNode(BspTraversalData &tData,
837                                                                        BspTraversalData &frontData,
838                                                                        BspTraversalData &backData,
839                                                                        PolygonContainer &coincident)
840{
841        mStat.nodes += 2;
842       
843        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
844        // select subdivision plane
845        BspInterior *interior =
846                new BspInterior(SelectPlane(leaf, tData));
847
848#ifdef _DEBUG
849        Debug << interior << endl;
850#endif
851       
852        // subdivide rays into front and back rays
853        SplitRays(interior->mPlane, *tData.mRays, *frontData.mRays, *backData.mRays);
854       
855        // subdivide polygons with plane
856        mStat.splits += interior->SplitPolygons(*tData.mPolygons,
857                                                    *frontData.mPolygons,
858                                                                                        *backData.mPolygons,
859                                                                                        coincident);
860
861        // split geometry
862        tData.mGeometry->SplitGeometry(*frontData.mGeometry, *backData.mGeometry,
863                                                                   *this, interior->mPlane);
864       
865        // compute area
866        frontData.mArea = frontData.mGeometry->GetArea();
867        backData.mArea = backData.mGeometry->GetArea();
868
869        // compute pvs
870        frontData.mPvs = ComputePvsSize(*frontData.mRays);
871        backData.mPvs = ComputePvsSize(*backData.mRays);
872
873
874
875        BspInterior *parent = leaf->GetParent();
876
877        // replace a link from node's parent
878        if (!leaf->IsRoot())
879        {
880                parent->ReplaceChildLink(leaf, interior);
881                interior->SetParent(parent);
882        }
883        else // new root
884        {
885                mRoot = interior;
886        }
887
888        // and setup child links
889        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
890       
891        frontData.mNode = interior->mFront;
892        backData.mNode = interior->mBack;
893       
894        return interior;
895}
896
897void BspTree::SortSplitCandidates(const PolygonContainer &polys,
898                                                                  const int axis,
899                                                                  vector<SortableEntry> &splitCandidates) const
900{
901  splitCandidates.clear();
902 
903  int requestedSize = 2 * (int)polys.size();
904  // creates a sorted split candidates array 
905  splitCandidates.reserve(requestedSize);
906 
907  PolygonContainer::const_iterator it, it_end = polys.end();
908
909  AxisAlignedBox3 box;
910
911  // insert all queries
912  for(it = polys.begin(); it != it_end; ++ it)
913  {
914          box.Initialize();
915          box.Include(*(*it));
916         
917          splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
918      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
919  }
920 
921  stable_sort(splitCandidates.begin(), splitCandidates.end());
922}
923
924
925float BspTree::BestCostRatio(const PolygonContainer &polys,
926                                                         const AxisAlignedBox3 &box,
927                                                         const int axis,
928                                                         float &position,
929                                                         int &objectsBack,
930                                                         int &objectsFront) const
931{
932        vector<SortableEntry> splitCandidates;
933
934        SortSplitCandidates(polys, axis, splitCandidates);
935       
936        // go through the lists, count the number of objects left and right
937        // and evaluate the following cost funcion:
938        // C = ct_div_ci  + (ol + or)/queries
939       
940        int objectsLeft = 0, objectsRight = (int)polys.size();
941       
942        float minBox = box.Min(axis);
943        float maxBox = box.Max(axis);
944        float boxArea = box.SurfaceArea();
945 
946        float minBand = minBox + sSplitBorder * (maxBox - minBox);
947        float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
948       
949        float minSum = 1e20f;
950        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
951
952        for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
953        {
954                switch ((*ci).type)
955                {
956                        case SortableEntry::POLY_MIN:
957                                ++ objectsLeft;
958                                break;
959                        case SortableEntry::POLY_MAX:
960                            -- objectsRight;
961                                break;
962                        default:
963                                break;
964                }
965               
966                if ((*ci).value > minBand && (*ci).value < maxBand)
967                {
968                        AxisAlignedBox3 lbox = box;
969                        AxisAlignedBox3 rbox = box;
970                        lbox.SetMax(axis, (*ci).value);
971                        rbox.SetMin(axis, (*ci).value);
972
973                        float sum = objectsLeft * lbox.SurfaceArea() +
974                                                objectsRight * rbox.SurfaceArea();
975     
976                        if (sum < minSum)
977                        {
978                                minSum = sum;
979                                position = (*ci).value;
980
981                                objectsBack = objectsLeft;
982                                objectsFront = objectsRight;
983                        }
984                }
985        }
986 
987        float oldCost = (float)polys.size();
988        float newCost = sCt_div_ci + minSum / boxArea;
989        float ratio = newCost / oldCost;
990
991
992#if 0
993  Debug << "====================" << endl;
994  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
995      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
996#endif
997  return ratio;
998}
999
1000bool BspTree::SelectAxisAlignedPlane(Plane3 &plane,
1001                                                                         const PolygonContainer &polys) const
1002{
1003        AxisAlignedBox3 box;
1004        box.Initialize();
1005       
1006        // create bounding box of region
1007        Polygon3::IncludeInBox(polys, box);
1008       
1009        int objectsBack = 0, objectsFront = 0;
1010        int axis = 0;
1011        float costRatio = MAX_FLOAT;
1012        Vector3 position;
1013
1014        //-- area subdivision
1015        for (int i = 0; i < 3; ++ i)
1016        {
1017                float p = 0;
1018                float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
1019               
1020                if (r < costRatio)
1021                {
1022                        costRatio = r;
1023                        axis = i;
1024                        position = p;
1025                }
1026        }
1027       
1028        if (costRatio >= sMaxCostRatio)
1029                return false;
1030
1031        Vector3 norm(0,0,0); norm[axis] = 1.0f;
1032        plane = Plane3(norm, position);
1033
1034        return true;
1035}
1036
1037Plane3 BspTree::SelectPlane(BspLeaf *leaf,
1038                                                        BspTraversalData &data)
1039{
1040        if (data.mPolygons->empty() && data.mRays->empty())
1041        {
1042                Debug << "Warning: No autopartition polygon candidate available\n";
1043       
1044                // return axis aligned split
1045                AxisAlignedBox3 box;
1046                box.Initialize();
1047       
1048                // create bounding box of region
1049                Polygon3::IncludeInBox(*data.mPolygons, box);
1050
1051                const int axis = box.Size().DrivingAxis();
1052                const Vector3 position = (box.Min()[axis] + box.Max()[axis])*0.5f;
1053
1054                Vector3 norm(0,0,0); norm[axis] = 1.0f;
1055                return Plane3(norm, position);
1056        }
1057       
1058        if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
1059                ((int)data.mPolygons->size() > sTermMaxPolysForAxisAligned) &&
1060                ((int)data.mRays->size() > sTermMaxRaysForAxisAligned) &&
1061                ((sTermMaxObjectsForAxisAligned < 0) ||
1062                  (Polygon3::ParentObjectsSize(*data.mPolygons) > sTermMaxObjectsForAxisAligned)))
1063        {
1064                Plane3 plane;
1065                if (SelectAxisAlignedPlane(plane, *data.mPolygons))
1066                        return plane;
1067        }
1068
1069        // simplest strategy: just take next polygon
1070        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1071        {
1072                if (!data.mPolygons->empty())
1073                {
1074                        Polygon3 *nextPoly = (*data.mPolygons)[Random((int)data.mPolygons->size())];
1075                        return nextPoly->GetSupportingPlane();
1076                }
1077               
1078                return Plane3();
1079        }
1080
1081        // use heuristics to find appropriate plane
1082        return SelectPlaneHeuristics(leaf, data);
1083}
1084
1085Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf,
1086                                                                          BspTraversalData &data)
1087{
1088        float lowestCost = MAX_FLOAT;
1089        Plane3 bestPlane;
1090       
1091        int limit = sMaxPolyCandidates > 0 ?
1092                Min((int)data.mPolygons->size(), sMaxPolyCandidates) : (int)data.mPolygons->size();
1093       
1094        int candidateIdx = limit;
1095
1096        for (int i = 0; i < limit; ++ i)
1097        {
1098                candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons);
1099               
1100                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
1101                // evaluate current candidate
1102                const float candidateCost =
1103                        SplitPlaneCost(poly->GetSupportingPlane(), data);
1104
1105                if (candidateCost < lowestCost)
1106                {
1107                        bestPlane = poly->GetSupportingPlane();
1108                        lowestCost = candidateCost;
1109                }
1110        }
1111       
1112        Debug << "lowest: " << lowestCost << endl;
1113
1114        //limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();   
1115        const BoundedRayContainer *rays = data.mRays;
1116
1117        for (int i = 0; i < sMaxRayCandidates; ++ i)
1118        {
1119                Plane3 plane;
1120
1121                if (1)
1122                {
1123                        Vector3 pt[3];
1124                        int idx[3];
1125               
1126                        for (int j = 0; j < 3; j ++)
1127                        {
1128                                idx[j] = Random((int)rays->size() * 2);
1129                               
1130                                if (idx[j] < (int)rays->size())
1131                                        pt[j] = (*rays)[idx[j]]->mRay->Extrap((*rays)[idx[j]]->mMinT);
1132                                else
1133                                {       
1134                                        idx[j] -= (int)rays->size();
1135                                        pt[j] = (*rays)[idx[j]]->mRay->Extrap((*rays)[idx[j]]->mMaxT);
1136                                }
1137                        }       
1138                       
1139                        plane = Plane3(pt[0], pt[1], pt[2]);
1140                }
1141                else
1142                {
1143                        candidateIdx = Random((int)rays->size());
1144                        BoundedRay *bRay = (*rays)[candidateIdx];
1145
1146                        Ray *ray = bRay->mRay;
1147                                               
1148                        const Vector3 minPt = ray->Extrap(bRay->mMinT);
1149                        const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1150
1151                        const Vector3 pt = (maxPt + minPt) * 0.5;
1152
1153                        const Vector3 normal = ray->GetDir();
1154                       
1155                        plane = Plane3(normal, pt);
1156                }
1157               
1158                const float candidateCost = SplitPlaneCost(plane, data);
1159
1160                if (candidateCost < lowestCost)
1161                {
1162                        Debug << "choose ray plane: " << candidateCost << endl;
1163                        bestPlane = plane;
1164                       
1165                        lowestCost = candidateCost;
1166                }
1167        }
1168
1169        Debug << "Plane lowest cost: " << lowestCost << endl;
1170        return bestPlane;
1171}
1172
1173int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
1174{
1175        const int candidateIdx = Random(currentIdx --);
1176
1177        // swap candidates to avoid testing same plane 2 times
1178        std::swap(polys[currentIdx], polys[candidateIdx]);
1179       
1180        return currentIdx;
1181        //return Random((int)polys.size());
1182}
1183
1184float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1185                                                          const PolygonContainer &polys) const
1186{
1187        float val = 0;
1188
1189        float sumBalancedPolys = 0;
1190        float sumSplits = 0;
1191        float sumPolyArea = 0;
1192        float sumBalancedViewCells = 0;
1193        float sumBlockedRays = 0;
1194        float totalBlockedRays = 0;
1195        //float totalArea = 0;
1196        int totalViewCells = 0;
1197
1198        // need three unique ids for each type of view cell
1199        // for balanced view cells criterium
1200        ViewCell::NewMail();
1201        const int backId = ViewCell::sMailId;
1202        ViewCell::NewMail();
1203        const int frontId = ViewCell::sMailId;
1204        ViewCell::NewMail();
1205        const int frontAndBackId = ViewCell::sMailId;
1206
1207        PolygonContainer::const_iterator it, it_end = polys.end();
1208
1209        for (it = polys.begin(); it != it_end; ++ it)
1210        {
1211                const int classification = (*it)->ClassifyPlane(candidatePlane);
1212
1213                if (sSplitPlaneStrategy & BALANCED_POLYS)
1214                        sumBalancedPolys += sBalancedPolysTable[classification];
1215               
1216                if (sSplitPlaneStrategy & LEAST_SPLITS)
1217                        sumSplits += sLeastPolySplitsTable[classification];
1218
1219                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1220                {
1221                        if (classification == Polygon3::COINCIDENT)
1222                                sumPolyArea += (*it)->GetArea();
1223                        //totalArea += area;
1224                }
1225               
1226                if (sSplitPlaneStrategy & BLOCKED_RAYS)
1227                {
1228                        const float blockedRays = (float)(*it)->mPiercingRays.size();
1229               
1230                        if (classification == Polygon3::COINCIDENT)
1231                                sumBlockedRays += blockedRays;
1232                       
1233                        totalBlockedRays += blockedRays;
1234                }
1235
1236                // assign view cells to back or front according to classificaion
1237                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1238                {
1239                        MeshInstance *viewCell = (*it)->mParent;
1240               
1241                        // assure that we only count a view cell
1242                        // once for the front and once for the back side of the plane
1243                        if (classification == Polygon3::FRONT_SIDE)
1244                        {
1245                                if ((viewCell->mMailbox != frontId) &&
1246                                        (viewCell->mMailbox != frontAndBackId))
1247                                {
1248                                        sumBalancedViewCells += 1.0;
1249
1250                                        if (viewCell->mMailbox != backId)
1251                                                viewCell->mMailbox = frontId;
1252                                        else
1253                                                viewCell->mMailbox = frontAndBackId;
1254                                       
1255                                        ++ totalViewCells;
1256                                }
1257                        }
1258                        else if (classification == Polygon3::BACK_SIDE)
1259                        {
1260                                if ((viewCell->mMailbox != backId) &&
1261                                    (viewCell->mMailbox != frontAndBackId))
1262                                {
1263                                        sumBalancedViewCells -= 1.0;
1264
1265                                        if (viewCell->mMailbox != frontId)
1266                                                viewCell->mMailbox = backId;
1267                                        else
1268                                                viewCell->mMailbox = frontAndBackId;
1269
1270                                        ++ totalViewCells;
1271                                }
1272                        }
1273                }
1274        }
1275
1276        // all values should be approx. between 0 and 1 so they can be combined
1277        // and scaled with the factors according to their importance
1278        if ((sSplitPlaneStrategy & BALANCED_POLYS) && (!polys.empty()))
1279                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
1280       
1281        if ((sSplitPlaneStrategy & LEAST_SPLITS) && (!polys.empty())) 
1282                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
1283
1284        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1285                // HACK: polys.size should be total area so scaling is between 0 and 1
1286                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1287
1288        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1289                if (totalBlockedRays != 0)
1290                        val += sBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
1291
1292        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1293                if (totalViewCells != 0)
1294                        val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) / (float)totalViewCells;
1295       
1296        return val;
1297}
1298
1299bool BspTree::BoundRay(const Ray &ray, float &minT, float &maxT) const
1300{
1301        maxT = 1e6;
1302        minT = 0;
1303       
1304        // test with tree bounding box
1305        if (!mBox.GetMinMaxT(ray, &minT, &maxT))
1306                return false;
1307
1308        if (minT < 0) // start ray from origin
1309                minT = 0;
1310
1311        // bound ray or line segment
1312        if ((ray.GetType() == Ray::LOCAL_RAY) &&
1313            !ray.intersections.empty() &&
1314                (ray.intersections[0].mT <= maxT))
1315        {
1316                maxT = ray.intersections[0].mT;
1317        }
1318
1319        return true;
1320}
1321
1322float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1323                                                          const BoundedRayContainer &rays,
1324                                                          const int pvs,
1325                                                          const float area,
1326                                                          const BspNodeGeometry &cell) const
1327{
1328        float val = 0;
1329
1330        float sumBalancedRays = 0;
1331        float sumRaySplits = 0;
1332       
1333        int backId = 0;
1334        int frontId = 0;
1335        int frontAndBackId = 0;
1336
1337        int frontPvs = 0;
1338        int backPvs = 0;
1339
1340        // probability that view point lies in child
1341        float pOverall = 0;
1342        float pFront = 0;
1343        float pBack = 0;
1344
1345        if (sSplitPlaneStrategy & PVS)
1346        {
1347                // create three unique ids for pvs heuristics
1348                Intersectable::NewMail(); backId = ViewCell::sMailId;
1349                Intersectable::NewMail(); frontId = ViewCell::sMailId;
1350                Intersectable::NewMail(); frontAndBackId = ViewCell::sMailId;
1351
1352                if (1) // use front and back cell areas to approximate volume
1353                {       
1354                        // construct child geometry with regard to the candidate split plane
1355                        BspNodeGeometry frontCell;
1356                        BspNodeGeometry backCell;
1357
1358                        cell.SplitGeometry(frontCell, backCell, *this, candidatePlane);
1359               
1360                        pFront = frontCell.GetArea();
1361                        pBack = backCell.GetArea();
1362
1363                        pOverall = area;
1364                }
1365                else
1366                {
1367                        pOverall = (float)rays.size();
1368                }
1369        }
1370                       
1371        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
1372
1373        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1374        {
1375                Ray *ray = (*rit)->mRay;
1376                const float minT = (*rit)->mMinT;
1377                const float maxT = (*rit)->mMaxT;
1378
1379                const int cf =
1380                        ray->ClassifyPlane(candidatePlane, minT, maxT);
1381
1382                if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1383                {
1384                        sumBalancedRays += sBalancedRaysTable[cf];
1385                }
1386               
1387                if (sSplitPlaneStrategy & BALANCED_RAYS)
1388                {
1389                        sumRaySplits += sLeastRaySplitsTable[cf];
1390                }
1391
1392                if (sSplitPlaneStrategy & PVS)
1393                {
1394                        if (!ray->intersections.empty())
1395                        {
1396                                // in case the ray intersects an objcrs
1397                                // assure that we only count a object
1398                                // once for the front and once for the back side of the plane
1399                                IncPvs(*ray->intersections[0].mObject, frontPvs, backPvs,
1400                                           cf, frontId, backId, frontAndBackId);
1401                        }
1402
1403                        // the source object in the origin of the ray
1404                        if (ray->sourceObject.mObject)
1405                        {
1406                                IncPvs(*ray->sourceObject.mObject, frontPvs, backPvs,
1407                                           cf, frontId, backId, frontAndBackId);
1408                        }
1409
1410                        // use #rays to approximate volume
1411                        if (0)
1412                        {
1413                                if ((cf == Ray::BACK) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
1414                                        ++ pFront;
1415                                if ((cf == Ray::FRONT) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
1416                                        ++ pBack;
1417                        }
1418                }
1419        }
1420
1421        if ((sSplitPlaneStrategy & LEAST_RAY_SPLITS) && !rays.empty())
1422                        val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
1423
1424        if ((sSplitPlaneStrategy & BALANCED_RAYS) && !rays.empty())
1425                        val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
1426
1427        if ((sSplitPlaneStrategy & PVS) && area && pvs)
1428        {
1429                val += sPvsFactor * (frontPvs * pFront + (backPvs * pBack)) /
1430                           (pOverall * (float)pvs * 2);
1431
1432                // give penalty for unbalanced cell
1433                if (((pFront * 0.2) > pBack) || (pFront < (pBack * 0.2)))
1434                        val += 0.5;
1435        }
1436/*      Debug << "totalpvs: " << pvs << " ptotal: " << pOverall
1437                  << " frontpvs: " << frontPvs << " pFront: " << pFront
1438                  << " backpvs: " << backPvs << " pBack: " << pBack
1439                  << " val " << val << endl;
1440*/
1441        return val;
1442}
1443
1444void BspTree::IncPvs(Intersectable &obj,
1445                                         int &frontPvs,
1446                                         int &backPvs,
1447                                         const int cf,
1448                                         const int frontId,
1449                                         const int backId,
1450                                         const int frontAndBackId) const
1451{
1452        if (cf == Ray::COINCIDENT) //TODO: really belongs to no pvs?
1453                return;
1454
1455        if (cf == Ray::FRONT)
1456        {
1457                if ((obj.mMailbox != frontId) &&
1458                        (obj.mMailbox != frontAndBackId))
1459                {
1460                        ++ frontPvs;
1461
1462                        if (obj.mMailbox != backId)
1463                                obj.mMailbox = frontId;
1464                        else
1465                                obj.mMailbox = frontAndBackId;                                 
1466                }
1467        }
1468        else if (cf == Ray::BACK)
1469        {
1470                if ((obj.mMailbox != backId) &&
1471                        (obj.mMailbox != frontAndBackId))
1472                {
1473                        ++ backPvs;
1474
1475                        if (obj.mMailbox != frontId)
1476                                obj.mMailbox = backId;
1477                        else
1478                                obj.mMailbox = frontAndBackId;
1479                }
1480        }
1481        // object belongs to both pvs
1482        else if ((cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
1483        {
1484                if (obj.mMailbox !=  frontAndBackId)
1485                {
1486                        if (obj.mMailbox != frontId)
1487                                ++ frontPvs;
1488                        if (obj.mMailbox != backId)
1489                                ++ backPvs;
1490               
1491                        obj.mMailbox = frontAndBackId;
1492                }
1493        }
1494}
1495
1496float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1497                                                          BspTraversalData &data) const
1498{
1499        float val = 0;
1500
1501        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1502        {
1503                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1504                // we put a penalty on the dot product between the "tiny" vertical axis
1505                // and the split plane axis
1506                val += sVerticalSplitsFactor *
1507                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1508        }
1509
1510        // the following criteria loop over all polygons to find the cost value
1511        if ((sSplitPlaneStrategy & BALANCED_POLYS)      ||
1512                (sSplitPlaneStrategy & LEAST_SPLITS)        ||
1513                (sSplitPlaneStrategy & LARGEST_POLY_AREA)   ||
1514                (sSplitPlaneStrategy & BALANCED_VIEW_CELLS) ||
1515                (sSplitPlaneStrategy & BLOCKED_RAYS))
1516        {
1517                val += SplitPlaneCost(candidatePlane, *data.mPolygons);
1518        }
1519
1520        // the following criteria loop over all rays to find the cost value
1521        if ((sSplitPlaneStrategy & BALANCED_RAYS)      ||
1522                (sSplitPlaneStrategy & LEAST_RAY_SPLITS)   ||
1523                (sSplitPlaneStrategy & PVS))
1524        {
1525                val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs,
1526                                                          data.mArea, *data.mGeometry);
1527        }
1528
1529        // return linear combination of the sums
1530        return val;
1531}
1532
1533void BspTree::ParseEnvironment()
1534{
1535        //-- parse bsp cell tree construction method
1536        char constructionMethodStr[60];
1537       
1538        environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
1539
1540        sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1541       
1542        if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1543                sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1544        else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1545                sConstructionMethod = FROM_SCENE_GEOMETRY;
1546        else if (strcmp(constructionMethodStr, "fromRays") == 0)
1547                sConstructionMethod = FROM_RAYS;
1548        else
1549        {
1550                cerr << "Wrong construction method " << constructionMethodStr << endl;
1551                exit(1);
1552    }
1553
1554        Debug << "Construction method: " << constructionMethodStr << endl;
1555
1556        //-- termination criteria for autopartition
1557        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1558        environment->GetIntValue("BspTree.Termination.minPvs", sTermMinPvs);
1559        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1560        environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
1561        environment->GetFloatValue("BspTree.Termination.minArea", sTermMinArea);
1562
1563        //-- termination criteria for axis aligned split
1564        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", sCt_div_ci);
1565        environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", sMaxCostRatio);
1566        environment->GetIntValue("BspTree.Termination.AxisAligned.maxPolys",
1567                                                         sTermMaxPolysForAxisAligned);
1568        environment->GetIntValue("BspTree.Termination.AxisAligned.maxRays",
1569                                                         sTermMaxRaysForAxisAligned);
1570        environment->GetIntValue("BspTree.Termination.AxisAligned.maxObjects",
1571                                                         sTermMaxObjectsForAxisAligned);
1572        //-- partition criteria
1573        environment->GetIntValue("BspTree.maxPolyCandidates", sMaxPolyCandidates);
1574        environment->GetIntValue("BspTree.maxRayCandidates", sMaxRayCandidates);
1575        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1576        environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
1577
1578        environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
1579        Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
1580
1581        // post processing stuff
1582        environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", sMinPvsDif);
1583        environment->GetIntValue("ViewCells.PostProcessing.minPvs", sMinPvs);
1584        environment->GetIntValue("ViewCells.PostProcessing.maxPvs", sMaxPvs);
1585
1586    Debug << "BSP max depth: " << sTermMaxDepth << endl;
1587        Debug << "BSP min PVS: " << sTermMinPvs << endl;
1588        Debug << "BSP min area: " << sTermMinArea << endl;
1589        Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1590        Debug << "BSP max rays: " << sTermMaxRays << endl;
1591        Debug << "BSP max polygon candidates: " << sMaxPolyCandidates << endl;
1592        Debug << "BSP max plane candidates: " << sMaxRayCandidates << endl;
1593
1594        Debug << "Split plane strategy: ";
1595        if (sSplitPlaneStrategy & RANDOM_POLYGON)
1596                Debug << "random polygon ";
1597        if (sSplitPlaneStrategy & AXIS_ALIGNED)
1598                Debug << "axis aligned ";
1599        if (sSplitPlaneStrategy & LEAST_SPLITS)     
1600                Debug << "least splits ";
1601        if (sSplitPlaneStrategy & BALANCED_POLYS)
1602                Debug << "balanced polygons ";
1603        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1604                Debug << "balanced view cells ";
1605        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1606                Debug << "largest polygon area ";
1607        if (sSplitPlaneStrategy & VERTICAL_AXIS)
1608                Debug << "vertical axis ";
1609        if (sSplitPlaneStrategy & BLOCKED_RAYS)
1610                Debug << "blocked rays ";
1611        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1612                Debug << "least ray splits ";
1613        if (sSplitPlaneStrategy & BALANCED_RAYS)
1614                Debug << "balanced rays ";
1615        if (sSplitPlaneStrategy & PVS)
1616                Debug << "pvs";
1617        Debug << endl;
1618}
1619
1620void BspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1621{
1622        stack<BspNode *> nodeStack;
1623        nodeStack.push(mRoot);
1624 
1625        while (!nodeStack.empty())
1626        {
1627                BspNode *node = nodeStack.top();
1628   
1629                nodeStack.pop();
1630   
1631                if (node->IsLeaf())
1632                {
1633                        BspLeaf *leaf = (BspLeaf *)node;               
1634                        leaves.push_back(leaf);
1635                }
1636                else
1637                {
1638                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1639
1640                        nodeStack.push(interior->GetBack());
1641                        nodeStack.push(interior->GetFront());
1642                }
1643        }
1644}
1645
1646AxisAlignedBox3 BspTree::GetBoundingBox() const
1647{
1648        return mBox;
1649}
1650
1651BspNode *BspTree::GetRoot() const
1652{
1653        return mRoot;
1654}
1655
1656void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1657{
1658        // the node became a leaf -> evaluate stats for leafs
1659        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1660
1661        if (data.mDepth >= sTermMaxDepth)
1662                ++ mStat.maxDepthNodes;
1663       
1664        // store maximal and minimal depth
1665        if (data.mDepth > mStat.maxDepth)
1666                mStat.maxDepth = data.mDepth;
1667
1668        if (data.mDepth < mStat.minDepth)
1669                mStat.minDepth = data.mDepth;
1670
1671        // store minimal and maximal pvs
1672        /*if (data.mPvs > mStat.pvs)mStat.pvs = data.mPvs;
1673        if (data.mPvs < mStat.pvs)      mStat.pvs = data.mPvs;*/
1674
1675        // accumulate depth to compute average
1676        mStat.accumDepth += data.mDepth;
1677       
1678//#ifdef _DEBUG
1679        Debug << "BSP stats: "
1680                  << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
1681                  << "PVS: " << data.mPvs << " (min: " << sTermMinPvs << "), "
1682                  << "Area: " << data.mArea << " (min: " << sTermMinArea << "), "
1683                  << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
1684                  << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << "), "
1685                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << endl;
1686//#endif
1687}
1688
1689int BspTree::CastRay(Ray &ray)
1690{
1691        int hits = 0;
1692 
1693        stack<BspRayTraversalData> tStack;
1694 
1695        float maxt, mint;
1696
1697        if (!BoundRay(ray, mint, maxt))
1698                return 0;
1699
1700        Intersectable::NewMail();
1701
1702        Vector3 entp = ray.Extrap(mint);
1703        Vector3 extp = ray.Extrap(maxt);
1704 
1705        BspNode *node = mRoot;
1706        BspNode *farChild = NULL;
1707       
1708        while (1)
1709        {
1710                if (!node->IsLeaf())
1711                {
1712                        BspInterior *in = (BspInterior *) node;
1713                       
1714                        Plane3 *splitPlane = in->GetPlane();
1715
1716                        int entSide = splitPlane->Side(entp);
1717                        int extSide = splitPlane->Side(extp);
1718
1719                        Vector3 intersection;
1720
1721                        if (entSide < 0)
1722                        {
1723                                node = in->GetBack();
1724
1725                                if(extSide <= 0) // plane does not split ray => no far child
1726                                        continue;
1727                                       
1728                                farChild = in->GetFront(); // plane splits ray
1729
1730                        } else if (entSide > 0)
1731                        {
1732                                node = in->GetFront();
1733
1734                                if (extSide >= 0) // plane does not split ray => no far child
1735                                        continue;
1736
1737                                farChild = in->GetBack(); // plane splits ray                   
1738                        }
1739                        else // ray and plane are coincident
1740                        // WHAT TO DO IN THIS CASE ?
1741                        {
1742                                break;
1743                                //node = in->GetFront();
1744                                //continue;
1745                        }
1746
1747                        // push data for far child
1748                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1749
1750                        // find intersection of ray segment with plane
1751                        float t;
1752                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t);
1753                        maxt *= t;
1754                       
1755                } else // reached leaf => intersection with view cell
1756                {
1757                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1758     
1759                        if (!leaf->mViewCell->Mailed())
1760                        {
1761                                ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
1762                                leaf->mViewCell->Mail();
1763                                ++ hits;
1764                        }
1765                       
1766                        //-- fetch the next far child from the stack
1767                        if (tStack.empty())
1768                                break;
1769     
1770                        entp = extp;
1771                        mint = maxt; // NOTE: need this?
1772
1773                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1774                                break;
1775
1776                        BspRayTraversalData &s = tStack.top();
1777
1778                        node = s.mNode;
1779                        extp = s.mExitPoint;
1780                        maxt = s.mMaxT;
1781
1782                        tStack.pop();
1783                }
1784        }
1785
1786        return hits;
1787}
1788
1789bool BspTree::Export(const string filename)
1790{
1791        Exporter *exporter = Exporter::GetExporter(filename);
1792
1793        if (exporter)
1794        {
1795                exporter->ExportBspTree(*this);
1796                return true;
1797        }       
1798
1799        return false;
1800}
1801
1802void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1803{
1804        stack<BspNode *> nodeStack;
1805        nodeStack.push(mRoot);
1806
1807        ViewCell::NewMail();
1808
1809        while (!nodeStack.empty())
1810        {
1811                BspNode *node = nodeStack.top();
1812                nodeStack.pop();
1813
1814                if (node->IsLeaf())
1815                {
1816                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1817
1818                        if (!viewCell->Mailed())
1819                        {
1820                                viewCell->Mail();
1821                                viewCells.push_back(viewCell);
1822                        }
1823                }
1824                else
1825                {
1826                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1827
1828                        nodeStack.push(interior->mFront);
1829                        nodeStack.push(interior->mBack);
1830                }
1831        }
1832}
1833
1834void BspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const
1835{
1836        stat.Reset();
1837
1838        stack<BspNode *> nodeStack;
1839        nodeStack.push(mRoot);
1840
1841        ViewCell::NewMail();
1842
1843        // exclude root cell
1844        mRootCell->Mail();
1845
1846        while (!nodeStack.empty())
1847        {
1848                BspNode *node = nodeStack.top();
1849                nodeStack.pop();
1850
1851                if (node->IsLeaf())
1852                {
1853                        ++ stat.bspLeaves;
1854
1855                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
1856
1857                        if (!viewCell->Mailed())
1858                        {
1859                                viewCell->Mail();
1860                               
1861                                ++ stat.viewCells;
1862                                int pvsSize = viewCell->GetPvs().GetSize();
1863
1864                stat.pvs += pvsSize;
1865
1866                                if (pvsSize < 2)
1867                                        ++ stat.emptyPvs;
1868
1869                                if (pvsSize > stat.maxPvs)
1870                                        stat.maxPvs = pvsSize;
1871
1872                                if (pvsSize < stat.minPvs)
1873                                        stat.minPvs = pvsSize;
1874
1875                                if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)
1876                                        stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();           
1877                        }
1878                }
1879                else
1880                {
1881                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1882
1883                        nodeStack.push(interior->mFront);
1884                        nodeStack.push(interior->mBack);
1885                }
1886        }
1887}
1888
1889bool BspTree::MergeViewCells(BspLeaf *front, BspLeaf *back) const
1890{
1891        BspViewCell *viewCell =
1892                dynamic_cast<BspViewCell *>(ViewCell::Merge(*front->mViewCell, *back->mViewCell));
1893       
1894        if (!viewCell)
1895                return false;
1896
1897        // change view cells of all leaves associated with the
1898        // previous view cells
1899
1900        BspViewCell *fVc = front->mViewCell;
1901        BspViewCell *bVc = back->mViewCell;
1902
1903        vector<BspLeaf *> fLeaves = fVc->mBspLeaves;
1904        vector<BspLeaf *> bLeaves = bVc->mBspLeaves;
1905
1906        vector<BspLeaf *>::const_iterator it;
1907       
1908        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
1909        {
1910                (*it)->SetViewCell(viewCell);
1911                viewCell->mBspLeaves.push_back(*it);
1912        }
1913        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
1914        {
1915                (*it)->SetViewCell(viewCell);
1916                viewCell->mBspLeaves.push_back(*it);
1917        }
1918       
1919        DEL_PTR(fVc);
1920        DEL_PTR(bVc);
1921
1922        return true;
1923}
1924
1925bool BspTree::ShouldMerge(BspLeaf *front, BspLeaf *back) const
1926{
1927        ViewCell *fvc = front->mViewCell;
1928        ViewCell *bvc = back->mViewCell;
1929
1930        if ((fvc == mRootCell) || (bvc == mRootCell) || (fvc == bvc))
1931                return false;
1932
1933        int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
1934
1935        if (fvc->GetPvs().GetSize() + fdiff < sMaxPvs)
1936        {
1937                if ((fvc->GetPvs().GetSize() < sMinPvs) ||     
1938                        (bvc->GetPvs().GetSize() < sMinPvs) ||
1939                        ((fdiff < sMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < sMinPvsDif)))
1940                {
1941                        return true;
1942                }
1943        }
1944       
1945        return false;
1946}
1947
1948void BspTree::SetGenerateViewCells(int generateViewCells)
1949{
1950        mGenerateViewCells = generateViewCells;
1951}
1952
1953BspTreeStatistics &BspTree::GetStat()
1954{
1955        return mStat;
1956}
1957
1958int BspTree::SplitRays(const Plane3 &plane,
1959                                           BoundedRayContainer &rays,
1960                                           BoundedRayContainer &frontRays,
1961                                           BoundedRayContainer &backRays)
1962{
1963        int splits = 0;
1964
1965        while (!rays.empty())
1966        {
1967                BoundedRay *bRay = rays.back();
1968                Ray *ray = bRay->mRay;
1969                rays.pop_back();
1970               
1971                const int cf =
1972                        ray->ClassifyPlane(plane, bRay->mMinT, bRay->mMaxT);
1973               
1974                ray->SetId(cf);
1975
1976                switch (cf)
1977                {
1978                case Ray::COINCIDENT:
1979                        //frontRays.push_back(bRay);
1980                        DEL_PTR(bRay);
1981                        break;
1982                case Ray::BACK:
1983                        backRays.push_back(bRay);
1984                        break;
1985                case Ray::FRONT:
1986                        frontRays.push_back(bRay);
1987                        break;
1988                case Ray::FRONT_BACK:
1989                        {
1990                                // find intersection of ray segment with plane
1991                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
1992                                const float t = plane.FindT(ray->GetLoc(), extp);
1993                               
1994                                const float newT = t * bRay->mMaxT;
1995
1996                                frontRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
1997                                backRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
1998
1999                                DEL_PTR(bRay);
2000
2001                                ++ splits;
2002                        }
2003                        break;
2004                case Ray::BACK_FRONT:
2005                        {
2006                                // find intersection of ray segment with plane
2007                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
2008                                const float t = plane.FindT(ray->GetLoc(), extp);
2009                                const float newT = t * bRay->mMaxT;
2010
2011                                backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
2012                                frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
2013                               
2014                                DEL_PTR(bRay);
2015
2016                                ++ splits;
2017                        }
2018                        break;
2019                default:
2020                        Debug << "Should not come here" << endl;
2021                        break;
2022                }
2023        }
2024
2025        return splits;
2026}
2027
2028void BspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
2029{
2030        BspNode *lastNode;
2031        do
2032        {
2033                lastNode = n;
2034
2035                // want to get planes defining geometry of this node => don't take
2036                // split plane of node itself
2037                n = n->GetParent();
2038               
2039                if (n)
2040                {
2041                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
2042                        Plane3 halfSpace = *dynamic_cast<BspInterior *>(interior)->GetPlane();
2043
2044            if (interior->mFront != lastNode)
2045                                halfSpace.ReverseOrientation();
2046
2047                        halfSpaces.push_back(halfSpace);
2048                }
2049        }
2050        while (n);
2051}
2052
2053void BspTree::ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const
2054{
2055        PolygonContainer polys;
2056        ConstructGeometry(n, polys);
2057        cell.mPolys = polys;
2058}
2059
2060void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
2061{
2062        vector<BspLeaf *> leaves = vc->mBspLeaves;
2063
2064        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2065
2066        for (it = leaves.begin(); it != it_end; ++ it)
2067                ConstructGeometry(*it, cell);
2068}
2069
2070
2071void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
2072{
2073        vector<Plane3> halfSpaces;
2074        ExtractHalfSpaces(n, halfSpaces);
2075
2076        PolygonContainer candidatePolys;
2077
2078        // bounded planes are added to the polygons (reverse polygons
2079        // as they have to be outfacing
2080        for (int i = 0; i < (int)halfSpaces.size(); ++ i)
2081        {
2082                Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
2083               
2084                if (p->Valid())
2085                {
2086                        candidatePolys.push_back(p->CreateReversePolygon());
2087                        DEL_PTR(p);
2088                }
2089        }
2090
2091        // add faces of bounding box (also could be faces of the cell)
2092        for (int i = 0; i < 6; ++ i)
2093        {
2094                VertexContainer vertices;
2095       
2096                for (int j = 0; j < 4; ++ j)
2097                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
2098
2099                candidatePolys.push_back(new Polygon3(vertices));
2100        }
2101
2102        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2103        {
2104                // polygon is split by all other planes
2105                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
2106                {
2107                        if (i == j) // polygon and plane are coincident
2108                                continue;
2109
2110                        VertexContainer splitPts;
2111                        Polygon3 *frontPoly, *backPoly;
2112
2113                        const int cf = candidatePolys[i]->ClassifyPlane(halfSpaces[j]);
2114                       
2115                        switch (cf)
2116                        {
2117                                case Polygon3::SPLIT:
2118                                        frontPoly = new Polygon3();
2119                                        backPoly = new Polygon3();
2120
2121                                        candidatePolys[i]->Split(halfSpaces[j], *frontPoly,
2122                                                                                         *backPoly, splitPts);
2123
2124                                        DEL_PTR(candidatePolys[i]);
2125
2126                                        if (frontPoly->Valid())
2127                                                candidatePolys[i] = frontPoly;
2128                                        else
2129                                                DEL_PTR(frontPoly);
2130
2131                                        DEL_PTR(backPoly);
2132                                        break;
2133                                case Polygon3::BACK_SIDE:
2134                                        DEL_PTR(candidatePolys[i]);
2135                                        break;
2136                                // just take polygon as it is
2137                                case Polygon3::FRONT_SIDE:
2138                                case Polygon3::COINCIDENT:
2139                                default:
2140                                        break;
2141                        }
2142                }
2143               
2144                if (candidatePolys[i])
2145                        cell.push_back(candidatePolys[i]);
2146        }
2147}
2148
2149
2150int BspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
2151                                                   const bool onlyUnmailed) const
2152{
2153        PolygonContainer cell;
2154
2155        ConstructGeometry(n, cell);
2156
2157        stack<BspNode *> nodeStack;
2158        nodeStack.push(mRoot);
2159               
2160        // planes needed to verify that we found neighbor leaf.
2161        vector<Plane3> halfSpaces;
2162        ExtractHalfSpaces(n, halfSpaces);
2163
2164        while (!nodeStack.empty())
2165        {
2166                BspNode *node = nodeStack.top();
2167                nodeStack.pop();
2168
2169                if (node->IsLeaf())
2170                {
2171            if (node != n && (!onlyUnmailed || !node->Mailed()))
2172                        {
2173                                // test all planes of current node if candidate really
2174                                // is neighbour
2175                                PolygonContainer neighborCandidate;
2176                                ConstructGeometry(node, neighborCandidate);
2177                               
2178                                bool isAdjacent = true;
2179                                for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
2180                                {
2181                                        const int cf =
2182                                                Polygon3::ClassifyPlane(neighborCandidate, halfSpaces[i]);
2183
2184                                        if (cf == Polygon3::BACK_SIDE)
2185                                                isAdjacent = false;
2186                                }
2187
2188                                if (isAdjacent)
2189                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2190
2191                                CLEAR_CONTAINER(neighborCandidate);
2192                        }
2193                }
2194                else
2195                {
2196                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2197       
2198                        const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
2199
2200                        if (cf == Polygon3::FRONT_SIDE)
2201                                nodeStack.push(interior->mFront);
2202                        else
2203                                if (cf == Polygon3::BACK_SIDE)
2204                                        nodeStack.push(interior->mBack);
2205                                else
2206                                {
2207                                        // random decision
2208                                        nodeStack.push(interior->mBack);
2209                                        nodeStack.push(interior->mFront);
2210                                }
2211                }
2212        }
2213       
2214        CLEAR_CONTAINER(cell);
2215        return (int)neighbors.size();
2216}
2217
2218BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
2219{
2220    stack<BspNode *> nodeStack;
2221        nodeStack.push(mRoot);
2222       
2223        int mask = rand();
2224 
2225        while (!nodeStack.empty())
2226        {
2227                BspNode *node = nodeStack.top();
2228                nodeStack.pop();
2229         
2230                if (node->IsLeaf())
2231                {
2232                        return dynamic_cast<BspLeaf *>(node);
2233                }
2234                else
2235                {
2236                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2237                       
2238                        BspNode *next;
2239       
2240                        PolygonContainer cell;
2241
2242                        // todo: not very efficient: constructs full cell everytime
2243                        ConstructGeometry(interior, cell);
2244
2245                        const int cf = Polygon3::ClassifyPlane(cell, halfspace);
2246
2247                        if (cf == Polygon3::BACK_SIDE)
2248                                next = interior->mFront;
2249                        else
2250                                if (cf == Polygon3::FRONT_SIDE)
2251                                        next = interior->mFront;
2252                        else
2253                        {
2254                                // random decision
2255                                if (mask & 1)
2256                                        next = interior->mBack;
2257                                else
2258                                        next = interior->mFront;
2259                                mask = mask >> 1;
2260                        }
2261
2262                        nodeStack.push(next);
2263                }
2264        }
2265       
2266        return NULL;
2267}
2268
2269BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
2270{
2271        stack<BspNode *> nodeStack;
2272       
2273        nodeStack.push(mRoot);
2274
2275        int mask = rand();
2276       
2277        while (!nodeStack.empty())
2278        {
2279                BspNode *node = nodeStack.top();
2280                nodeStack.pop();
2281               
2282                if (node->IsLeaf())
2283                {
2284                        if ( (!onlyUnmailed || !node->Mailed()) )
2285                                return dynamic_cast<BspLeaf *>(node);
2286                }
2287                else
2288                {
2289                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2290
2291                        // random decision
2292                        if (mask & 1)
2293                                nodeStack.push(interior->mBack);
2294                        else
2295                                nodeStack.push(interior->mFront);
2296
2297                        mask = mask >> 1;
2298                }
2299        }
2300       
2301        return NULL;
2302}
2303
2304int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
2305{
2306        int pvsSize = 0;
2307
2308        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
2309
2310        Intersectable::NewMail();
2311
2312        for (rit = rays.begin(); rit != rays.end(); ++ rit)
2313        {
2314                Ray *ray = (*rit)->mRay;
2315               
2316                if (!ray->intersections.empty())
2317                {
2318                        if (!ray->intersections[0].mObject->Mailed())
2319                        {
2320                                ray->intersections[0].mObject->Mail();
2321                                ++ pvsSize;
2322                        }
2323                }
2324                if (ray->sourceObject.mObject)
2325                {
2326                        if (!ray->sourceObject.mObject->Mailed())
2327                        {
2328                                ray->sourceObject.mObject->Mail();
2329                                ++ pvsSize;
2330                        }
2331                }
2332        }
2333
2334        return pvsSize;
2335}
2336
2337/*************************************************************
2338 *            BspNodeGeometry Implementation                 *
2339 *************************************************************/
2340
2341BspNodeGeometry::~BspNodeGeometry()
2342{
2343        CLEAR_CONTAINER(mPolys);
2344}
2345
2346float BspNodeGeometry::GetArea() const
2347{
2348        return Polygon3::GetArea(mPolys);
2349}
2350
2351void BspNodeGeometry::SplitGeometry(BspNodeGeometry &front,
2352                                                                        BspNodeGeometry &back,
2353                                                                        const BspTree &tree,                                             
2354                                                                        const Plane3 &splitPlane) const
2355{       
2356        // get cross section of new polygon
2357        Polygon3 *planePoly = tree.GetBoundingBox().CrossSection(splitPlane);
2358
2359        planePoly = SplitPolygon(planePoly, tree);
2360
2361        //-- plane poly splits all other cell polygons
2362        for (int i = 0; i < (int)mPolys.size(); ++ i)
2363        {
2364                const int cf = mPolys[i]->ClassifyPlane(splitPlane);
2365                       
2366                // split new polygon with all previous planes
2367                switch (cf)
2368                {
2369                        case Polygon3::SPLIT:
2370                                {
2371                                        Polygon3 *poly = new Polygon3(mPolys[i]->mVertices);
2372
2373                                        Polygon3 *frontPoly = new Polygon3();
2374                                        Polygon3 *backPoly = new Polygon3();
2375                               
2376                                        VertexContainer splitPts;
2377                                               
2378                                        poly->Split(splitPlane, *frontPoly, *backPoly, splitPts);
2379
2380                                        DEL_PTR(poly);
2381
2382                                        if (frontPoly->Valid())
2383                                                front.mPolys.push_back(frontPoly);
2384                                        if (backPoly->Valid())
2385                                                back.mPolys.push_back(backPoly);
2386                                }
2387                               
2388                                break;
2389                        case Polygon3::BACK_SIDE:
2390                                back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));                     
2391                                break;
2392                        case Polygon3::FRONT_SIDE:
2393                                front.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));     
2394                                break;
2395                        case Polygon3::COINCIDENT:
2396                                //front.mPolys.push_back(CreateReversePolygon(mPolys[i]));
2397                                //back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2398                                break;
2399                        default:
2400                                break;
2401                }
2402        }
2403
2404        //-- finally add the new polygon to the child cells
2405        if (planePoly)
2406        {
2407                // add polygon with normal pointing into positive half space to back cell
2408                back.mPolys.push_back(planePoly);
2409                // add polygon with reverse orientation to front cell
2410                front.mPolys.push_back(planePoly->CreateReversePolygon());
2411        }
2412
2413        //Debug << "returning new geometry " << mPolys.size() << " f: " << front.mPolys.size() << " b: " << back.mPolys.size() << endl;
2414        //Debug << "old area " << GetArea() << " f: " << front.GetArea() << " b: " << back.GetArea() << endl;
2415}
2416
2417Polygon3 *BspNodeGeometry::SplitPolygon(Polygon3 *planePoly,
2418                                                                                const BspTree &tree) const
2419{
2420        // polygon is split by all other planes
2421        for (int i = 0; (i < (int)mPolys.size()) && planePoly; ++ i)
2422        {
2423                Plane3 plane = mPolys[i]->GetSupportingPlane();
2424
2425                const int cf =
2426                        planePoly->ClassifyPlane(plane);
2427                       
2428                // split new polygon with all previous planes
2429                switch (cf)
2430                {
2431                        case Polygon3::SPLIT:
2432                                {
2433                                        VertexContainer splitPts;
2434                               
2435                                        Polygon3 *frontPoly = new Polygon3();
2436                                        Polygon3 *backPoly = new Polygon3();
2437
2438                                        planePoly->Split(plane, *frontPoly, *backPoly, splitPts);
2439                                        DEL_PTR(planePoly);
2440
2441                                        if (backPoly->Valid())
2442                                                planePoly = backPoly;
2443                                        else
2444                                                DEL_PTR(backPoly);
2445                                }
2446                                break;
2447                        case Polygon3::FRONT_SIDE:
2448                                DEL_PTR(planePoly);
2449                break;
2450                        // polygon is taken as it is
2451                        case Polygon3::BACK_SIDE:
2452                        case Polygon3::COINCIDENT:
2453                        default:
2454                                break;
2455                }
2456        }
2457
2458        return planePoly;
2459}
Note: See TracBrowser for help on using the repository browser.