source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 480

Revision 480, 53.3 KB checked in by mattausch, 19 years ago (diff)

axis aligned split for vsp bsp view cells
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "Plane3.h"
6#include "VspBspTree.h"
7#include "Mesh.h"
8#include "common.h"
9#include "ViewCell.h"
10#include "Environment.h"
11#include "Polygon3.h"
12#include "Ray.h"
13#include "AxisAlignedBox3.h"
14#include "Exporter.h"
15#include "Plane3.h"
16#include "ViewCellBsp.h"
17#include "ViewCellsManager.h"
18
19
20//-- static members
21/** Evaluates split plane classification with respect to the plane's
22        contribution for a minimum number of ray splits.
23*/
24const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
25/** Evaluates split plane classification with respect to the plane's
26        contribution for balanced rays.
27*/
28const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
29
30
31int VspBspTree::sFrontId = 0;
32int VspBspTree::sBackId = 0;
33int VspBspTree::sFrontAndBackId = 0;
34
35float BspMergeCandidate::sOverallCost = Limits::Small;
36
37/****************************************************************/
38/*                  class VspBspTree implementation             */
39/****************************************************************/
40
41VspBspTree::VspBspTree():
42mRoot(NULL),
43mPvsUseArea(true),
44mCostNormalizer(Limits::Small),
45mViewCellsManager(NULL),
46mStoreRays(true)
47{
48        mRootCell = new BspViewCell();
49
50        Randomize(); // initialise random generator for heuristics
51
52        //-- termination criteria for autopartition
53        environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
54        environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
55        environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
56        environment->GetFloatValue("VspBspTree.Termination.minArea", mTermMinArea);     
57        environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
58        environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
59        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
60        environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
61
62        //-- factors for bsp tree split plane heuristics
63        environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
64        environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
65        environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
66
67        //-- termination criteria for axis aligned split
68        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
69        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
70       
71        environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
72                                                         mTermMinRaysForAxisAligned);
73       
74        //-- partition criteria
75        environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
76        environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
77        environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
78        environment->GetFloatValue("VspBspTree.AxisAligned.splitBorder", mAxisAlignedSplitBorder);
79
80        environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
81        environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
82
83        // maximum and minimum number of view cells
84        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
85        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
86        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
87
88
89        //-- debug output
90        Debug << "******* VSP BSP options ******** " << endl;
91    Debug << "max depth: " << mTermMaxDepth << endl;
92        Debug << "min PVS: " << mTermMinPvs << endl;
93        Debug << "min area: " << mTermMinArea << endl;
94        Debug << "min rays: " << mTermMinRays << endl;
95        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
96        //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
97        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
98        Debug << "miss tolerance: " << mTermMissTolerance << endl;
99        Debug << "max view cells: " << mMaxViewCells << endl;
100        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
101        Debug << "max plane candidates: " << mMaxRayCandidates << endl;
102       
103        Debug << "Split plane strategy: ";
104        if (mSplitPlaneStrategy & RANDOM_POLYGON)
105        {
106                Debug << "random polygon ";
107        }
108        if (mSplitPlaneStrategy & AXIS_ALIGNED)
109        {
110                Debug << "axis aligned ";
111        }
112        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
113        {
114                mCostNormalizer += mLeastRaySplitsFactor;
115                Debug << "least ray splits ";
116        }
117        if (mSplitPlaneStrategy & BALANCED_RAYS)
118        {
119                mCostNormalizer += mBalancedRaysFactor;
120                Debug << "balanced rays ";
121        }
122        if (mSplitPlaneStrategy & PVS)
123        {
124                mCostNormalizer += mPvsFactor;
125                Debug << "pvs";
126        }
127       
128        mSplitCandidates = new vector<SortableEntry>;
129
130        Debug << endl;
131}
132
133
134const BspTreeStatistics &VspBspTree::GetStatistics() const
135{
136        return mStat;
137}
138
139
140VspBspTree::~VspBspTree()
141{
142        DEL_PTR(mRoot);
143        DEL_PTR(mRootCell);
144        DEL_PTR(mSplitCandidates);
145}
146
147int VspBspTree::AddMeshToPolygons(Mesh *mesh,
148                                                                  PolygonContainer &polys,
149                                                                  MeshInstance *parent)
150{
151        FaceContainer::const_iterator fi;
152       
153        // copy the face data to polygons
154        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
155        {
156                Polygon3 *poly = new Polygon3((*fi), mesh);
157               
158                if (poly->Valid(mEpsilon))
159                {
160                        poly->mParent = parent; // set parent intersectable
161                        polys.push_back(poly);
162                }
163                else
164                        DEL_PTR(poly);
165        }
166        return (int)mesh->mFaces.size();
167}
168
169int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
170                                                          PolygonContainer &polys,
171                                                          int maxObjects)
172{
173        int limit = (maxObjects > 0) ?
174                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
175 
176        int polysSize = 0;
177
178        for (int i = 0; i < limit; ++ i)
179        {
180                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
181                {
182                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
183                        polysSize +=
184                                AddMeshToPolygons(viewCells[i]->GetMesh(),
185                                                                  polys,
186                                                                  viewCells[i]);
187                }
188        }
189
190        return polysSize;
191}
192
193int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
194                                                                 PolygonContainer &polys,
195                                                                 int maxObjects)
196{
197        int limit = (maxObjects > 0) ?
198                Min((int)objects.size(), maxObjects) : (int)objects.size();
199 
200        for (int i = 0; i < limit; ++i)
201        {
202                Intersectable *object = objects[i];//*it;
203                Mesh *mesh = NULL;
204
205                switch (object->Type()) // extract the meshes
206                {
207                case Intersectable::MESH_INSTANCE:
208                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
209                        break;
210                case Intersectable::VIEW_CELL:
211                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
212                        break;
213                        // TODO: handle transformed mesh instances
214                default:
215                        Debug << "intersectable type not supported" << endl;
216                        break;
217                }
218               
219        if (mesh) // copy the mesh data to polygons
220                {
221                        mBox.Include(object->GetBox()); // add to BSP tree aabb
222                        AddMeshToPolygons(mesh, polys, mRootCell);
223                }
224        }
225
226        return (int)polys.size();
227}
228
229void VspBspTree::Construct(const VssRayContainer &sampleRays)
230{
231    mStat.nodes = 1;
232        mBox.Initialize();      // initialise BSP tree bounding box
233       
234        PolygonContainer polys;
235        RayInfoContainer *rays = new RayInfoContainer();
236
237        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
238
239        long startTime = GetTime();
240
241        cout << "Extracting polygons from rays ... ";
242
243        Intersectable::NewMail();
244
245        //-- extract polygons intersected by the rays
246        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
247        {
248                VssRay *ray = *rit;
249       
250                if (ray->mTerminationObject && !ray->mTerminationObject->Mailed())
251                {
252                        ray->mTerminationObject->Mail();
253                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
254                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
255                }
256
257                if (ray->mOriginObject && !ray->mOriginObject->Mailed())
258                {
259                        ray->mOriginObject->Mail();
260                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
261                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
262                }
263        }
264
265        // compute bounding box
266        Polygon3::IncludeInBox(polys, mBox);
267
268        //-- store rays
269        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
270        {
271                VssRay *ray = *rit;
272               
273                float minT, maxT;
274
275                // TODO: not very efficient to implictly cast between rays types ...
276                if (mBox.GetRaySegment(*ray, minT, maxT))
277                {
278                        float len = ray->Length();
279                       
280                        if (!len)
281                                len = Limits::Small;
282                       
283                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
284                }
285        }
286
287        mTermMinArea *= mBox.SurfaceArea(); // normalize
288        mStat.polys = (int)polys.size();
289
290        cout << "finished" << endl;
291
292        Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
293                  << (int)sampleRays.size() << " rays in "
294                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
295
296        Construct(polys, rays);
297
298        // clean up polygons
299        CLEAR_CONTAINER(polys);
300}
301
302void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
303{
304        VspBspTraversalStack tStack;
305
306        mRoot = new BspLeaf();
307
308        // constrruct root node geometry
309        BspNodeGeometry *geom = new BspNodeGeometry();
310        ConstructGeometry(mRoot, *geom);
311
312        VspBspTraversalData tData(mRoot,
313                                                          new PolygonContainer(polys),
314                                                          0,
315                                                          rays,
316                              ComputePvsSize(*rays),
317                                                          geom->GetArea(),
318                                                          geom);
319
320        tStack.push(tData);
321
322        mStat.Start();
323        cout << "Contructing vsp bsp tree ... ";
324
325        long startTime = GetTime();
326       
327        while (!tStack.empty())
328        {
329                tData = tStack.top();
330
331            tStack.pop();
332
333                // subdivide leaf node
334                BspNode *r = Subdivide(tStack, tData);
335
336                if (r == mRoot)
337                        Debug << "VSP BSP tree construction time spent at root: "
338                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl << endl;
339        }
340
341        cout << "finished\n";
342
343        mStat.Stop();
344}
345
346bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
347{
348        return
349                (((int)data.mRays->size() <= mTermMinRays) ||
350                 (data.mPvs <= mTermMinPvs)   ||
351                 (data.mArea <= mTermMinArea) ||
352                 (mStat.nodes / 2 + 1 >= mMaxViewCells) ||
353                // (data.GetAvgRayContribution() >= mTermMaxRayContribution) ||
354                 (data.mDepth >= mTermMaxDepth));
355}
356
357BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
358                                                           VspBspTraversalData &tData)
359{
360        BspNode *newNode = tData.mNode;
361
362        if (!TerminationCriteriaMet(tData))
363        {
364                PolygonContainer coincident;
365       
366                VspBspTraversalData tFrontData;
367                VspBspTraversalData tBackData;
368
369                // create new interior node and two leaf nodes
370                // or return leaf as it is (if maxCostRatio missed)
371                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
372
373                if (!newNode->IsLeaf()) //-- continue subdivision
374                {
375                        // push the children on the stack
376                        tStack.push(tFrontData);
377                        tStack.push(tBackData);
378
379                        // delete old leaf node
380                        DEL_PTR(tData.mNode);   
381                }
382        }
383       
384        //-- terminate traversal and create new view cell
385        if (newNode->IsLeaf())
386        {
387                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
388       
389                // create new view cell for this leaf
390                BspViewCell *viewCell = new BspViewCell();
391                leaf->SetViewCell(viewCell);
392               
393                if (mStoreRays)
394                {
395                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
396                        for (it = tData.mRays->begin(); it != it_end; ++ it)
397                                leaf->mVssRays.push_back((*it).mRay);
398                }
399
400                viewCell->mLeaves.push_back(leaf);
401                viewCell->SetArea(tData.mArea);
402
403                //-- update pvs
404                int conSamp = 0, sampCon = 0;
405                AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
406                       
407                mStat.contributingSamples += conSamp;
408                mStat.sampleContributions += sampCon;
409               
410                EvaluateLeafStats(tData);
411        }
412       
413               
414        //-- cleanup
415        tData.Clear();
416
417        return newNode;
418}
419
420BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
421                                                                   VspBspTraversalData &frontData,
422                                                                   VspBspTraversalData &backData,
423                                                                   PolygonContainer &coincident)
424{
425        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
426
427        int maxCostMisses = tData.mMaxCostMisses;
428
429        // select subdivision plane
430        Plane3 splitPlane;
431        if (!SelectPlane(splitPlane, leaf, tData))
432        {
433                ++ maxCostMisses;
434
435                if (maxCostMisses > mTermMissTolerance)
436                {
437                        // terminate branch because of max cost
438                        ++ mStat.maxCostNodes;
439            return leaf;
440                }
441        }
442
443        mStat.nodes += 2;
444
445        //-- subdivide further
446        BspInterior *interior = new BspInterior(splitPlane);
447
448#ifdef _DEBUG
449        Debug << interior << endl;
450#endif
451       
452        //-- the front and back traversal data is filled with the new values
453        frontData.mPolygons = new PolygonContainer();
454        frontData.mDepth = tData.mDepth + 1;
455        frontData.mRays = new RayInfoContainer();
456        frontData.mGeometry = new BspNodeGeometry();
457
458        backData.mPolygons = new PolygonContainer();
459        backData.mDepth = tData.mDepth + 1;
460        backData.mRays = new RayInfoContainer();
461        backData.mGeometry = new BspNodeGeometry();
462
463        // subdivide rays
464        SplitRays(interior->GetPlane(),
465                          *tData.mRays,
466                          *frontData.mRays,
467                          *backData.mRays);
468       
469        // subdivide polygons
470        mStat.splits += SplitPolygons(interior->GetPlane(),
471                                                                  *tData.mPolygons,
472                                          *frontData.mPolygons,
473                                                                  *backData.mPolygons,
474                                                                  coincident);
475
476       
477        // how often was max cost ratio missed in this branch?
478        frontData.mMaxCostMisses = maxCostMisses;
479        backData.mMaxCostMisses = maxCostMisses;
480
481        // compute pvs
482        frontData.mPvs = ComputePvsSize(*frontData.mRays);
483        backData.mPvs = ComputePvsSize(*backData.mRays);
484
485        // split geometry and compute area
486        if (1)
487        {
488                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
489                                                                           *backData.mGeometry,
490                                                                           interior->GetPlane(),
491                                                                           mBox,
492                                                                           mEpsilon);
493       
494                frontData.mArea = frontData.mGeometry->GetArea();
495                backData.mArea = backData.mGeometry->GetArea();
496        }
497
498        // compute accumulated ray length
499        //frontData.mAccRayLength = AccumulatedRayLength(*frontData.mRays);
500        //backData.mAccRayLength = AccumulatedRayLength(*backData.mRays);
501
502        //-- create front and back leaf
503
504        BspInterior *parent = leaf->GetParent();
505
506        // replace a link from node's parent
507        if (!leaf->IsRoot())
508        {
509                parent->ReplaceChildLink(leaf, interior);
510                interior->SetParent(parent);
511        }
512        else // new root
513        {
514                mRoot = interior;
515        }
516
517        // and setup child links
518        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
519       
520        frontData.mNode = interior->GetFront();
521        backData.mNode = interior->GetBack();
522
523        //DEL_PTR(leaf);
524        return interior;
525}
526
527void VspBspTree::AddToPvs(BspLeaf *leaf,
528                                                  const RayInfoContainer &rays,
529                                                  int &sampleContributions,
530                                                  int &contributingSamples)
531{
532        sampleContributions = 0;
533        contributingSamples = 0;
534
535    RayInfoContainer::const_iterator it, it_end = rays.end();
536
537        ViewCell *vc = leaf->GetViewCell();
538
539        // add contributions from samples to the PVS
540        for (it = rays.begin(); it != it_end; ++ it)
541        {
542                int contribution = 0;
543                VssRay *ray = (*it).mRay;
544                       
545                if (ray->mTerminationObject)
546                        contribution += vc->GetPvs().AddSample(ray->mTerminationObject);
547               
548                if (ray->mOriginObject)
549                        contribution += vc->GetPvs().AddSample(ray->mOriginObject);
550
551                if (contribution)
552                {
553                        sampleContributions += contribution;
554                        ++ contributingSamples;
555                }
556                //leaf->mVssRays.push_back(ray);
557        }
558}
559
560void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
561{
562        mSplitCandidates->clear();
563
564        int requestedSize = 2 * (int)(rays.size());
565        // creates a sorted split candidates array
566        if (mSplitCandidates->capacity() > 500000 &&
567                requestedSize < (int)(mSplitCandidates->capacity()/10) )
568        {
569        DEL_PTR(mSplitCandidates);
570                mSplitCandidates = new vector<SortableEntry>;
571        }
572
573        mSplitCandidates->reserve(requestedSize);
574
575        // insert all queries
576        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
577        {
578                bool positive = (*ri).mRay->HasPosDir(axis);
579                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
580                                                                                                  (*ri).ExtrapOrigin(axis), (void *)&*ri));
581
582                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
583                                                                                                  (*ri).ExtrapTermination(axis), (void *)&*ri));
584        }
585
586        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
587}
588
589float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
590                                                                                  const AxisAlignedBox3 &box,
591                                                                                  const int pvsSize,
592                                                                                  int &axis,
593                                          float &position)
594{
595        //      AxisAlignedBox3 dirBox = GetDirBBox(node);
596        int raysBack;
597        int raysFront;
598        int pvsBack;
599        int pvsFront;
600
601        axis = box.Size().DrivingAxis();
602
603        SortSplitCandidates(rays, axis);
604
605        // go through the lists, count the number of objects left and right
606        // and evaluate the following cost funcion:
607        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
608
609        int rl = 0, rr = (int)rays.size();
610        int pl = 0, pr = pvsSize;
611
612        float minBox = box.Min(axis);
613        float maxBox = box.Max(axis);
614        float sizeBox = maxBox - minBox;
615
616        float minBand = minBox + 0.1f*(maxBox - minBox);
617        float maxBand = minBox + 0.9f*(maxBox - minBox);
618
619        float sum = rr*sizeBox;
620        float minSum = 1e20f;
621
622        Intersectable::NewMail();
623
624        // set all object as belonging to the fron pvs
625        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
626        {
627                if ((*ri).mRay->IsActive())
628                {
629                        Intersectable *object = (*ri).mRay->mTerminationObject;
630
631                        if (object)
632                                if (!object->Mailed())
633                                {
634                                        object->Mail();
635                                        object->mCounter = 1;
636                                }
637                                else
638                                        ++ object->mCounter;
639                }
640        }
641
642        Intersectable::NewMail();
643
644        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
645                ci < mSplitCandidates->end(); ++ ci)
646        {
647                VssRay *ray;
648
649                switch ((*ci).type)
650                {
651                        case SortableEntry::ERayMin:
652                                {
653                                        ++ rl;
654                                        ray = (VssRay *) (*ci).data;
655                                        Intersectable *object = ray->mTerminationObject;
656                                        if (object && !object->Mailed())
657                                        {
658                                                object->Mail();
659                                                ++ pl;
660                                        }
661                                        break;
662                                }
663                        case SortableEntry::ERayMax:
664                                {
665                                        -- rr;
666
667                                        ray = (VssRay *) (*ci).data;
668                                        Intersectable *object = ray->mTerminationObject;
669
670                                        if (object)
671                                        {
672                                                if (-- object->mCounter == 0)
673                                                -- pr;
674                                        }
675
676                                        break;
677                                }
678                }
679
680                // Note: sufficient to compare size of bounding boxes of front and back side?
681                if ((*ci).value > minBand && (*ci).value < maxBand)
682                {
683                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
684
685                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
686                        // cout<<"cost= "<<sum<<endl;
687
688                        if (sum < minSum)
689                        {
690                                minSum = sum;
691                                position = (*ci).value;
692
693                                raysBack = rl;
694                                raysFront = rr;
695
696                                pvsBack = pl;
697                                pvsFront = pr;
698
699                        }
700                }
701        }
702
703        float oldCost = (float)pvsSize;
704        float newCost = mCtDivCi + minSum / sizeBox;
705        float ratio = newCost / oldCost;
706
707        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
708        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
709
710        return ratio;
711}
712
713
714float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
715                                                                                 const VspBspTraversalData &tData)
716{
717        AxisAlignedBox3 box;
718        box.Initialize();
719       
720        // create bounding box of region
721        RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
722
723        for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
724                box.Include((*ri).ExtrapTermination());
725
726        int axis = 0;
727        const bool useCostHeuristics = false;
728
729        if (useCostHeuristics)
730        {
731                float position;
732
733                const float ratio =
734                        BestCostRatioHeuristics(*tData.mRays,
735                                                                    box,
736                                                                        tData.mPvs,
737                                                                        axis,
738                                                                        position);
739
740                Vector3 normal(0,0,0); normal[axis] = 1;
741                plane = Plane3(normal, position);
742
743                return ratio;
744        }
745
746        //-- regular split
747        float nPosition[3];
748        float nCostRatio[3];
749        int bestAxis = -1;
750
751        bool mOnlyDrivingAxis = false;
752
753        const int sAxis = box.Size().DrivingAxis();
754               
755        for (axis = 0; axis < 3; ++ axis)
756        {
757                if (!mOnlyDrivingAxis || axis == sAxis)
758                {
759                        if (!useCostHeuristics)
760                        {
761                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
762                                Vector3 normal(0,0,0); normal[axis] = 1;
763
764                                nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), tData);
765                        }
766                       
767                        if (bestAxis == -1)
768                        {
769                                bestAxis = axis;
770                        }
771
772                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
773                        {
774                                /*Debug << "pvs front " << nPvsBack[axis]
775                                          << " pvs back " << nPvsFront[axis]
776                                          << " overall pvs " << leaf->GetPvsSize() << endl;*/
777                                bestAxis = axis;
778                        }
779
780                }
781        }
782
783        //-- assign best axis
784        Vector3 normal(0,0,0); normal[bestAxis] = 1;
785        plane = Plane3(normal, nPosition[bestAxis]);
786
787        return nCostRatio[bestAxis];
788}
789
790
791bool VspBspTree::SelectPlane(Plane3 &plane,
792                                                         BspLeaf *leaf,
793                                                         VspBspTraversalData &data)
794{
795        // simplest strategy: just take next polygon
796        if (mSplitPlaneStrategy & RANDOM_POLYGON)
797        {
798        if (!data.mPolygons->empty())
799                {
800                        const int randIdx = (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
801                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
802
803                        plane = nextPoly->GetSupportingPlane();
804                        return true;
805                }
806                else
807                {
808                        //-- choose plane on midpoint of a ray
809                        const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1));
810                                                                       
811                        const Vector3 minPt = (*data.mRays)[candidateIdx].ExtrapOrigin();
812                        const Vector3 maxPt = (*data.mRays)[candidateIdx].ExtrapTermination();
813
814                        const Vector3 pt = (maxPt + minPt) * 0.5;
815
816                        const Vector3 normal = (*data.mRays)[candidateIdx].mRay->GetDir();
817                       
818                        plane = Plane3(normal, pt);
819                        return true;
820                }
821
822                return false;
823        }
824
825        // use heuristics to find appropriate plane
826        return SelectPlaneHeuristics(plane, leaf, data);
827}
828
829
830Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
831{       
832        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
833       
834        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
835        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
836
837        const Vector3 pt = (maxPt + minPt) * 0.5;
838        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
839
840        return Plane3(normal, pt);
841}
842
843
844Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
845{       
846        Vector3 pt[3];
847       
848        int idx[3];
849        int cmaxT = 0;
850        int cminT = 0;
851        bool chooseMin = false;
852
853        for (int j = 0; j < 3; ++ j)
854        {
855                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
856                       
857                if (idx[j] >= (int)rays.size())
858                {
859                        idx[j] -= (int)rays.size();
860                               
861                        chooseMin = (cminT < 2);
862                }
863                else
864                        chooseMin = (cmaxT < 2);
865
866                RayInfo rayInf = rays[idx[j]];
867                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
868        }       
869
870        return Plane3(pt[0], pt[1], pt[2]);
871}
872
873Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
874{       
875        Vector3 pt[3];
876       
877        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
878        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
879
880        // check if rays different
881        if (idx1 == idx2)
882                idx2 = (idx2 + 1) % (int)rays.size();
883
884        const RayInfo ray1 = rays[idx1];
885        const RayInfo ray2 = rays[idx2];
886
887        // normal vector of the plane parallel to both lines
888        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
889
890        // vector from line 1 to line 2
891        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
892       
893        // project vector on normal to get distance
894        const float dist = DotProd(vd, norm);
895
896        // point on plane lies halfway between the two planes
897        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
898
899        return Plane3(norm, planePt);
900}
901
902bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane,
903                                                                           BspLeaf *leaf,
904                                                                           VspBspTraversalData &data)
905{
906        float lowestCost = MAX_FLOAT;
907        // intermediate plane
908        Plane3 plane;
909
910        const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
911        int maxIdx = (int)data.mPolygons->size();
912       
913        float candidateCost;
914
915        for (int i = 0; i < limit; ++ i)
916        {
917                // assure that no index is taken twice
918                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
919                //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl;
920               
921                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
922
923                // swap candidate to the end to avoid testing same plane
924                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
925       
926                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
927
928                // evaluate current candidate
929                candidateCost = SplitPlaneCost(poly->GetSupportingPlane(), data);
930
931                if (candidateCost < lowestCost)
932                {
933                        bestPlane = poly->GetSupportingPlane();
934                        lowestCost = candidateCost;
935                }
936        }
937       
938#if 0
939        //-- choose candidate planes extracted from rays
940        //-- different methods are available
941        for (int i = 0; i < mMaxRayCandidates; ++ i)
942        {
943                plane = ChooseCandidatePlane3(*data.mRays);
944                candidateCost = SplitPlaneCost(plane, data);
945
946                if (candidateCost < lowestCost)
947                {
948                        bestPlane = plane;     
949                        lowestCost = candidateCost;
950                }
951        }
952#endif
953
954        // axis aligned splits
955        candidateCost = SelectAxisAlignedPlane(plane, data);
956
957        if (candidateCost < lowestCost)
958        {
959                bestPlane = plane;     
960                lowestCost = candidateCost;
961        }
962
963#ifdef _DEBUG
964        Debug << "plane lowest cost: " << lowestCost << endl;
965#endif
966
967        // cost ratio miss
968        if (lowestCost > mTermMaxCostRatio)
969                return false;
970
971        return true;
972}
973
974
975inline void VspBspTree::GenerateUniqueIdsForPvs()
976{
977        Intersectable::NewMail(); sBackId = ViewCell::sMailId;
978        Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
979        Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
980}
981
982float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,
983                                                                 const VspBspTraversalData &data) const
984{
985        float cost = 0;
986
987        float sumBalancedRays = 0;
988        float sumRaySplits = 0;
989       
990        int frontPvs = 0;
991        int backPvs = 0;
992
993        // probability that view point lies in child
994        float pOverall = 0;
995        float pFront = 0;
996        float pBack = 0;
997
998        const bool pvsUseLen = false;
999
1000        if (mSplitPlaneStrategy & PVS)
1001        {
1002                // create unique ids for pvs heuristics
1003                GenerateUniqueIdsForPvs();
1004       
1005                if (mPvsUseArea) // use front and back cell areas to approximate volume
1006                {       
1007                        // construct child geometry with regard to the candidate split plane
1008                        BspNodeGeometry frontCell;
1009                        BspNodeGeometry backCell;
1010               
1011                        data.mGeometry->SplitGeometry(frontCell,
1012                                                                                  backCell,
1013                                                                                  candidatePlane,
1014                                                                                  mBox,
1015                                                                                  mEpsilon);
1016               
1017                        pFront = frontCell.GetArea();
1018                        pBack = backCell.GetArea();
1019
1020                        pOverall = data.mArea;
1021                }
1022        }
1023               
1024        int limit;
1025        bool useRand;
1026
1027        // choose test polyongs randomly if over threshold
1028        if ((int)data.mRays->size() > mMaxTests)
1029        {
1030                useRand = true;
1031                limit = mMaxTests;
1032        }
1033        else
1034        {
1035                useRand = false;
1036                limit = (int)data.mRays->size();
1037        }
1038
1039        for (int i = 0; i < limit; ++ i)
1040        {
1041                const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i;
1042                RayInfo rayInf = (*data.mRays)[testIdx];
1043
1044                VssRay *ray = rayInf.mRay;
1045                float t;
1046                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1047
1048                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1049                {
1050                        sumBalancedRays += cf;
1051                }
1052               
1053                if (mSplitPlaneStrategy & BALANCED_RAYS)
1054                {
1055                        if (cf == 0)
1056                                ++ sumRaySplits;
1057                }
1058
1059                if (mSplitPlaneStrategy & PVS)
1060                {
1061                        // in case the ray intersects an object
1062                        // assure that we only count the object
1063                        // once for the front and once for the back side of the plane
1064                       
1065                        // add the termination object
1066                        AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
1067                       
1068                        // add the source object
1069                        AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
1070                       
1071                        // use number or length of rays to approximate volume
1072                        if (!mPvsUseArea)
1073                        {
1074                                float len = 1;
1075
1076                                if (pvsUseLen) // use length of rays
1077                                        len = rayInf.SqrSegmentLength();
1078                       
1079                                pOverall += len;
1080
1081                                if (cf == 1)
1082                                        pFront += len;
1083                                if (cf == -1)
1084                                        pBack += len;
1085                                if (cf == 0)
1086                                {
1087                                        // use length of rays to approximate volume
1088                                        if (pvsUseLen)
1089                                        {
1090                                                float newLen = len *
1091                                                        (rayInf.GetMaxT() - t) /
1092                                                        (rayInf.GetMaxT() - rayInf.GetMinT());
1093               
1094                                                if (candidatePlane.Side(rayInf.ExtrapOrigin()) <= 0)
1095                                                {
1096                                                        pBack += newLen;
1097                                                        pFront += len - newLen;
1098                                                }
1099                                                else
1100                                                {
1101                                                        pFront += newLen;
1102                                                        pBack += len - newLen;
1103                                                }
1104                                        }
1105                                        else
1106                                        {
1107                                                ++ pFront;
1108                                                ++ pBack;
1109                                        }
1110                                }
1111                        }
1112                }
1113        }
1114
1115        const float raysSize = (float)data.mRays->size() + Limits::Small;
1116       
1117        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1118                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1119
1120        if (mSplitPlaneStrategy & BALANCED_RAYS)
1121                cost += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
1122       
1123        // pvs criterium
1124        if (mSplitPlaneStrategy & PVS)
1125        {
1126                const float oldCost = pOverall * (float)data.mPvs + Limits::Small;
1127                cost += mPvsFactor * (frontPvs * pFront + backPvs * pBack) / oldCost;
1128
1129                //cost += mPvsFactor * 0.5 * (frontPvs * pFront + backPvs * pBack) / oldCost;
1130                //Debug << "new cost: " << cost << " over" << frontPvs * pFront + backPvs * pBack << " old cost " << oldCost << endl;
1131       
1132                if (0) // give penalty to unbalanced split
1133                        if (((pFront * 0.2 + Limits::Small) > pBack) ||
1134                                (pFront < (pBack * 0.2 + Limits::Small)))
1135                                        cost += 0.5;
1136        }
1137
1138#ifdef _DEBUG
1139        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
1140                  << " frontpvs: " << frontPvs << " pFront: " << pFront
1141                  << " backpvs: " << backPvs << " pBack: " << pBack << endl << endl;
1142#endif
1143       
1144        // normalize cost by sum of linear factors
1145        return cost / (float)mCostNormalizer;
1146}
1147
1148void VspBspTree::AddObjToPvs(Intersectable *obj,
1149                                                         const int cf,
1150                                                         int &frontPvs,
1151                                                         int &backPvs) const
1152{
1153        if (!obj)
1154                return;
1155        // TODO: does this really belong to no pvs?
1156        //if (cf == Ray::COINCIDENT) return;
1157
1158        // object belongs to both PVS
1159        if (cf >= 0)
1160        {
1161                if ((obj->mMailbox != sFrontId) &&
1162                        (obj->mMailbox != sFrontAndBackId))
1163                {
1164                        ++ frontPvs;
1165
1166                        if (obj->mMailbox == sBackId)
1167                                obj->mMailbox = sFrontAndBackId;       
1168                        else
1169                                obj->mMailbox = sFrontId;                                                               
1170                }
1171        }
1172       
1173        if (cf <= 0)
1174        {
1175                if ((obj->mMailbox != sBackId) &&
1176                        (obj->mMailbox != sFrontAndBackId))
1177                {
1178                        ++ backPvs;
1179
1180                        if (obj->mMailbox == sFrontId)
1181                                obj->mMailbox = sFrontAndBackId;
1182                        else
1183                                obj->mMailbox = sBackId;                               
1184                }
1185        }
1186}
1187
1188void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1189{
1190        stack<BspNode *> nodeStack;
1191        nodeStack.push(mRoot);
1192 
1193        while (!nodeStack.empty())
1194        {
1195                BspNode *node = nodeStack.top();
1196   
1197                nodeStack.pop();
1198   
1199                if (node->IsLeaf())
1200                {
1201                        BspLeaf *leaf = (BspLeaf *)node;               
1202                        leaves.push_back(leaf);
1203                }
1204                else
1205                {
1206                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1207
1208                        nodeStack.push(interior->GetBack());
1209                        nodeStack.push(interior->GetFront());
1210                }
1211        }
1212}
1213
1214AxisAlignedBox3 VspBspTree::GetBoundingBox() const
1215{
1216        return mBox;
1217}
1218
1219BspNode *VspBspTree::GetRoot() const
1220{
1221        return mRoot;
1222}
1223
1224void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
1225{
1226        // the node became a leaf -> evaluate stats for leafs
1227        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1228
1229        // store maximal and minimal depth
1230        if (data.mDepth > mStat.maxDepth)
1231                mStat.maxDepth = data.mDepth;
1232
1233        if (data.mDepth < mStat.minDepth)
1234                mStat.minDepth = data.mDepth;
1235       
1236        if (data.mDepth >= mTermMaxDepth)
1237                ++ mStat.maxDepthNodes;
1238
1239        if (data.mPvs < mTermMinPvs)
1240                ++ mStat.minPvsNodes;
1241
1242        if ((int)data.mRays->size() < mTermMinRays)
1243                ++ mStat.minRaysNodes;
1244
1245        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1246                ++ mStat.maxRayContribNodes;
1247       
1248        if (data.mArea <= mTermMinArea)
1249        {
1250                //Debug << "area: " << data.mArea / mBox.SurfaceArea() << " min area: " << mTermMinArea / mBox.SurfaceArea() << endl;
1251                ++ mStat.minAreaNodes;
1252        }
1253        // accumulate depth to compute average depth
1254        mStat.accumDepth += data.mDepth;
1255
1256#ifdef _DEBUG
1257        Debug << "BSP stats: "
1258                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1259                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1260                  << "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
1261                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1262                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1263                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1264#endif
1265}
1266
1267int VspBspTree::CastRay(Ray &ray)
1268{
1269        int hits = 0;
1270 
1271        stack<BspRayTraversalData> tStack;
1272 
1273        float maxt, mint;
1274
1275        if (!mBox.GetRaySegment(ray, mint, maxt))
1276                return 0;
1277
1278        Intersectable::NewMail();
1279
1280        Vector3 entp = ray.Extrap(mint);
1281        Vector3 extp = ray.Extrap(maxt);
1282 
1283        BspNode *node = mRoot;
1284        BspNode *farChild = NULL;
1285       
1286        while (1)
1287        {
1288                if (!node->IsLeaf())
1289                {
1290                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1291
1292                        Plane3 splitPlane = in->GetPlane();
1293                        const int entSide = splitPlane.Side(entp);
1294                        const int extSide = splitPlane.Side(extp);
1295
1296                        if (entSide < 0)
1297                        {
1298                                node = in->GetBack();
1299
1300                                if(extSide <= 0) // plane does not split ray => no far child
1301                                        continue;
1302                                       
1303                                farChild = in->GetFront(); // plane splits ray
1304
1305                        } else if (entSide > 0)
1306                        {
1307                                node = in->GetFront();
1308
1309                                if (extSide >= 0) // plane does not split ray => no far child
1310                                        continue;
1311
1312                                farChild = in->GetBack(); // plane splits ray                   
1313                        }
1314                        else // ray and plane are coincident
1315                        {
1316                                // WHAT TO DO IN THIS CASE ?
1317                                //break;
1318                                node = in->GetFront();
1319                                continue;
1320                        }
1321
1322                        // push data for far child
1323                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1324
1325                        // find intersection of ray segment with plane
1326                        float t;
1327                        extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1328                        maxt *= t;
1329                       
1330                } else // reached leaf => intersection with view cell
1331                {
1332                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1333     
1334                        if (!leaf->GetViewCell()->Mailed())
1335                        {
1336                                //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
1337                                leaf->GetViewCell()->Mail();
1338                                ++ hits;
1339                        }
1340                       
1341                        //-- fetch the next far child from the stack
1342                        if (tStack.empty())
1343                                break;
1344     
1345                        entp = extp;
1346                        mint = maxt; // NOTE: need this?
1347
1348                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1349                                break;
1350
1351                        BspRayTraversalData &s = tStack.top();
1352
1353                        node = s.mNode;
1354                        extp = s.mExitPoint;
1355                        maxt = s.mMaxT;
1356
1357                        tStack.pop();
1358                }
1359        }
1360
1361        return hits;
1362}
1363
1364bool VspBspTree::Export(const string filename)
1365{
1366        Exporter *exporter = Exporter::GetExporter(filename);
1367
1368        if (exporter)
1369        {
1370                //exporter->ExportVspBspTree(*this);
1371                return true;
1372        }       
1373
1374        return false;
1375}
1376
1377void VspBspTree::CollectViewCells(ViewCellContainer &viewCells) const
1378{
1379        stack<BspNode *> nodeStack;
1380        nodeStack.push(mRoot);
1381
1382        ViewCell::NewMail();
1383
1384        while (!nodeStack.empty())
1385        {
1386                BspNode *node = nodeStack.top();
1387                nodeStack.pop();
1388
1389                if (node->IsLeaf())
1390                {
1391                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1392
1393                        if (!viewCell->Mailed())
1394                        {
1395                                viewCell->Mail();
1396                                viewCells.push_back(viewCell);
1397                        }
1398                }
1399                else
1400                {
1401                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1402
1403                        nodeStack.push(interior->GetFront());
1404                        nodeStack.push(interior->GetBack());
1405                }
1406        }
1407}
1408
1409
1410BspTreeStatistics &VspBspTree::GetStat()
1411{
1412        return mStat;
1413}
1414
1415
1416float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1417{
1418        float len = 0;
1419
1420        RayInfoContainer::const_iterator it, it_end = rays.end();
1421
1422        for (it = rays.begin(); it != it_end; ++ it)
1423                len += (*it).SegmentLength();
1424
1425        return len;
1426}
1427
1428
1429int VspBspTree::SplitRays(const Plane3 &plane,
1430                                                  RayInfoContainer &rays,
1431                                                  RayInfoContainer &frontRays,
1432                                                  RayInfoContainer &backRays)
1433{
1434        int splits = 0;
1435
1436        while (!rays.empty())
1437        {
1438                RayInfo bRay = rays.back();
1439                rays.pop_back();
1440
1441                VssRay *ray = bRay.mRay;
1442                float t;
1443
1444                        // get classification and receive new t
1445                const int cf = bRay.ComputeRayIntersection(plane, t);
1446       
1447                switch (cf)
1448                {
1449                case -1:
1450                        backRays.push_back(bRay);
1451                        break;
1452                case 1:
1453                        frontRays.push_back(bRay);
1454                        break;
1455                case 0:
1456                        //-- split ray
1457                        //--  look if start point behind or in front of plane
1458                        if (plane.Side(bRay.ExtrapOrigin()) <= 0)
1459                        {       
1460                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1461                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1462                        }
1463                        else
1464                        {
1465                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1466                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1467                        }
1468                        break;
1469                default:
1470                        Debug << "Should not come here 4" << endl;
1471                        break;
1472                }
1473        }
1474
1475        return splits;
1476}
1477
1478
1479void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1480{
1481        BspNode *lastNode;
1482
1483        do
1484        {
1485                lastNode = n;
1486
1487                // want to get planes defining geometry of this node => don't take
1488                // split plane of node itself
1489                n = n->GetParent();
1490               
1491                if (n)
1492                {
1493                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
1494                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1495
1496            if (interior->GetFront() != lastNode)
1497                                halfSpace.ReverseOrientation();
1498
1499                        halfSpaces.push_back(halfSpace);
1500                }
1501        }
1502        while (n);
1503}
1504
1505void VspBspTree::ConstructGeometry(BspNode *n,
1506                                                                   BspNodeGeometry &cell) const
1507{
1508        PolygonContainer polys;
1509        ConstructGeometry(n, polys);
1510        cell.mPolys = polys;
1511}
1512
1513void VspBspTree::ConstructGeometry(BspNode *n,
1514                                                                   PolygonContainer &cell) const
1515{
1516        vector<Plane3> halfSpaces;
1517        ExtractHalfSpaces(n, halfSpaces);
1518
1519        PolygonContainer candidatePolys;
1520
1521        // bounded planes are added to the polygons (reverse polygons
1522        // as they have to be outfacing
1523        for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1524        {
1525                Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1526               
1527                if (p->Valid(mEpsilon))
1528                {
1529                        candidatePolys.push_back(p->CreateReversePolygon());
1530                        DEL_PTR(p);
1531                }
1532        }
1533
1534        // add faces of bounding box (also could be faces of the cell)
1535        for (int i = 0; i < 6; ++ i)
1536        {
1537                VertexContainer vertices;
1538       
1539                for (int j = 0; j < 4; ++ j)
1540                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
1541
1542                candidatePolys.push_back(new Polygon3(vertices));
1543        }
1544
1545        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
1546        {
1547                // polygon is split by all other planes
1548                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
1549                {
1550                        if (i == j) // polygon and plane are coincident
1551                                continue;
1552
1553                        VertexContainer splitPts;
1554                        Polygon3 *frontPoly, *backPoly;
1555
1556                        const int cf =
1557                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
1558                                                                                                 mEpsilon);
1559                       
1560                        switch (cf)
1561                        {
1562                                case Polygon3::SPLIT:
1563                                        frontPoly = new Polygon3();
1564                                        backPoly = new Polygon3();
1565
1566                                        candidatePolys[i]->Split(halfSpaces[j],
1567                                                                                         *frontPoly,
1568                                                                                         *backPoly,
1569                                                                                         mEpsilon);
1570
1571                                        DEL_PTR(candidatePolys[i]);
1572
1573                                        if (frontPoly->Valid(mEpsilon))
1574                                                candidatePolys[i] = frontPoly;
1575                                        else
1576                                                DEL_PTR(frontPoly);
1577
1578                                        DEL_PTR(backPoly);
1579                                        break;
1580                                case Polygon3::BACK_SIDE:
1581                                        DEL_PTR(candidatePolys[i]);
1582                                        break;
1583                                // just take polygon as it is
1584                                case Polygon3::FRONT_SIDE:
1585                                case Polygon3::COINCIDENT:
1586                                default:
1587                                        break;
1588                        }
1589                }
1590               
1591                if (candidatePolys[i])
1592                        cell.push_back(candidatePolys[i]);
1593        }
1594}
1595
1596void VspBspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &vcGeom) const
1597{
1598        vector<BspLeaf *> leaves = vc->mLeaves;
1599
1600        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
1601
1602        for (it = leaves.begin(); it != it_end; ++ it)
1603                ConstructGeometry(*it, vcGeom);
1604}
1605
1606int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
1607                                                   const bool onlyUnmailed) const
1608{
1609        PolygonContainer cell;
1610
1611        ConstructGeometry(n, cell);
1612
1613        stack<BspNode *> nodeStack;
1614        nodeStack.push(mRoot);
1615               
1616        // planes needed to verify that we found neighbor leaf.
1617        vector<Plane3> halfSpaces;
1618        ExtractHalfSpaces(n, halfSpaces);
1619
1620        while (!nodeStack.empty())
1621        {
1622                BspNode *node = nodeStack.top();
1623                nodeStack.pop();
1624
1625                if (node->IsLeaf())
1626                {
1627            if (node != n && (!onlyUnmailed || !node->Mailed()))
1628                        {
1629                                // test all planes of current node if candidate really
1630                                // is neighbour
1631                                PolygonContainer neighborCandidate;
1632                                ConstructGeometry(node, neighborCandidate);
1633                               
1634                                bool isAdjacent = true;
1635                                for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
1636                                {
1637                                        const int cf =
1638                                                Polygon3::ClassifyPlane(neighborCandidate,
1639                                                                                                halfSpaces[i],
1640                                                                                                mEpsilon);
1641
1642                                        if (cf == Polygon3::BACK_SIDE)
1643                                                isAdjacent = false;
1644                                }
1645
1646                                if (isAdjacent)
1647                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
1648
1649                                CLEAR_CONTAINER(neighborCandidate);
1650                        }
1651                }
1652                else
1653                {
1654                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1655       
1656                        const int cf = Polygon3::ClassifyPlane(cell,
1657                                                                                                   interior->GetPlane(),
1658                                                                                                   mEpsilon);
1659
1660                        if (cf == Polygon3::FRONT_SIDE)
1661                                nodeStack.push(interior->GetFront());
1662                        else
1663                                if (cf == Polygon3::BACK_SIDE)
1664                                        nodeStack.push(interior->GetBack());
1665                                else
1666                                {
1667                                        // random decision
1668                                        nodeStack.push(interior->GetBack());
1669                                        nodeStack.push(interior->GetFront());
1670                                }
1671                }
1672        }
1673       
1674        CLEAR_CONTAINER(cell);
1675        return (int)neighbors.size();
1676}
1677
1678BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
1679{
1680    stack<BspNode *> nodeStack;
1681        nodeStack.push(mRoot);
1682       
1683        int mask = rand();
1684 
1685        while (!nodeStack.empty())
1686        {
1687                BspNode *node = nodeStack.top();
1688                nodeStack.pop();
1689         
1690                if (node->IsLeaf())
1691                {
1692                        return dynamic_cast<BspLeaf *>(node);
1693                }
1694                else
1695                {
1696                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1697                       
1698                        BspNode *next;
1699       
1700                        PolygonContainer cell;
1701
1702                        // todo: not very efficient: constructs full cell everytime
1703                        ConstructGeometry(interior, cell);
1704
1705                        const int cf = Polygon3::ClassifyPlane(cell, halfspace, mEpsilon);
1706
1707                        if (cf == Polygon3::BACK_SIDE)
1708                                next = interior->GetFront();
1709                        else
1710                                if (cf == Polygon3::FRONT_SIDE)
1711                                        next = interior->GetFront();
1712                        else
1713                        {
1714                                // random decision
1715                                if (mask & 1)
1716                                        next = interior->GetBack();
1717                                else
1718                                        next = interior->GetFront();
1719                                mask = mask >> 1;
1720                        }
1721
1722                        nodeStack.push(next);
1723                }
1724        }
1725       
1726        return NULL;
1727}
1728
1729BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
1730{
1731        stack<BspNode *> nodeStack;
1732       
1733        nodeStack.push(mRoot);
1734
1735        int mask = rand();
1736       
1737        while (!nodeStack.empty())
1738        {
1739                BspNode *node = nodeStack.top();
1740                nodeStack.pop();
1741               
1742                if (node->IsLeaf())
1743                {
1744                        if ( (!onlyUnmailed || !node->Mailed()) )
1745                                return dynamic_cast<BspLeaf *>(node);
1746                }
1747                else
1748                {
1749                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1750
1751                        // random decision
1752                        if (mask & 1)
1753                                nodeStack.push(interior->GetBack());
1754                        else
1755                                nodeStack.push(interior->GetFront());
1756
1757                        mask = mask >> 1;
1758                }
1759        }
1760       
1761        return NULL;
1762}
1763
1764int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
1765{
1766        int pvsSize = 0;
1767
1768        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1769
1770        Intersectable::NewMail();
1771
1772        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1773        {
1774                VssRay *ray = (*rit).mRay;
1775               
1776                if (ray->mOriginObject)
1777                {
1778                        if (!ray->mOriginObject->Mailed())
1779                        {
1780                                ray->mOriginObject->Mail();
1781                                ++ pvsSize;
1782                        }
1783                }
1784                if (ray->mTerminationObject)
1785                {
1786                        if (!ray->mTerminationObject->Mailed())
1787                        {
1788                                ray->mTerminationObject->Mail();
1789                                ++ pvsSize;
1790                        }
1791                }
1792        }
1793
1794        return pvsSize;
1795}
1796
1797float VspBspTree::GetEpsilon() const
1798{
1799        return mEpsilon;
1800}
1801
1802BspViewCell *VspBspTree::GetRootCell() const
1803{
1804        return mRootCell;
1805}
1806
1807int VspBspTree::SplitPolygons(const Plane3 &plane,
1808                                                          PolygonContainer &polys,
1809                                                          PolygonContainer &frontPolys,
1810                                                          PolygonContainer &backPolys,
1811                                                          PolygonContainer &coincident) const
1812{
1813        int splits = 0;
1814
1815        while (!polys.empty())
1816        {
1817                Polygon3 *poly = polys.back();
1818                polys.pop_back();
1819
1820                // classify polygon
1821                const int cf = poly->ClassifyPlane(plane, mEpsilon);
1822
1823                switch (cf)
1824                {
1825                        case Polygon3::COINCIDENT:
1826                                coincident.push_back(poly);
1827                                break;                 
1828                        case Polygon3::FRONT_SIDE:     
1829                                frontPolys.push_back(poly);
1830                                break;
1831                        case Polygon3::BACK_SIDE:
1832                                backPolys.push_back(poly);
1833                                break;
1834                        case Polygon3::SPLIT:
1835                                backPolys.push_back(poly);
1836                                frontPolys.push_back(poly);
1837                                ++ splits;
1838                                break;
1839                        default:
1840                Debug << "SHOULD NEVER COME HERE\n";
1841                                break;
1842                }
1843        }
1844
1845        return splits;
1846}
1847
1848
1849int VspBspTree::CastLineSegment(const Vector3 &origin,
1850                                                                const Vector3 &termination,
1851                                                                vector<ViewCell *> &viewcells)
1852{
1853        int hits = 0;
1854        stack<BspRayTraversalData> tStack;
1855 
1856        float mint = 0.0f, maxt = 1.0f;
1857 
1858        Intersectable::NewMail();
1859 
1860        Vector3 entp = origin;
1861        Vector3 extp = termination;
1862 
1863        BspNode *node = mRoot;
1864        BspNode *farChild = NULL;
1865 
1866        while (1)
1867        {
1868                if (!node->IsLeaf()) 
1869                {
1870                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1871         
1872                        Plane3 splitPlane = in->GetPlane();
1873                        const int entSide = splitPlane.Side(entp);
1874                        const int extSide = splitPlane.Side(extp);
1875         
1876                        if (entSide < 0)
1877                        {
1878                                node = in->GetBack();
1879               
1880                                if(extSide <= 0) // plane does not split ray => no far child
1881                                        continue;
1882               
1883                                farChild = in->GetFront(); // plane splits ray
1884                        } else if (entSide > 0)
1885                        {
1886                                node = in->GetFront();
1887                 
1888                                if (extSide >= 0) // plane does not split ray => no far child
1889                                        continue;
1890                 
1891                                farChild = in->GetBack(); // plane splits ray                   
1892                        }
1893                        else // ray and plane are coincident
1894                        {
1895                                // WHAT TO DO IN THIS CASE ?
1896                                //break;
1897                                node = in->GetFront();
1898                                continue;
1899                        }
1900         
1901                        // push data for far child
1902                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1903         
1904                        // find intersection of ray segment with plane
1905                        float t;
1906                        extp = splitPlane.FindIntersection(origin, extp, &t);
1907                        maxt *= t;
1908         
1909                } else
1910                {
1911                        // reached leaf => intersection with view cell
1912                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1913         
1914                        if (!leaf->GetViewCell()->Mailed())
1915                        {
1916                                viewcells.push_back(leaf->GetViewCell());
1917                                leaf->GetViewCell()->Mail();
1918                                ++ hits;
1919                        }
1920         
1921                        //-- fetch the next far child from the stack
1922                        if (tStack.empty())
1923                                break;
1924     
1925                        entp = extp;
1926                        mint = maxt; // NOTE: need this?
1927         
1928                       
1929                        BspRayTraversalData &s = tStack.top();
1930           
1931                        node = s.mNode;
1932                        extp = s.mExitPoint;
1933                        maxt = s.mMaxT;
1934         
1935                        tStack.pop();
1936                }
1937        }
1938        return hits;
1939}
1940
1941
1942BspNode *VspBspTree::CollapseTree(BspNode *node)
1943{
1944    if (node->IsLeaf())
1945                return node;
1946
1947        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1948
1949        BspNode *front = CollapseTree(interior->GetFront());
1950        BspNode *back = CollapseTree(interior->GetBack());
1951
1952        if (front->IsLeaf() && back->IsLeaf())
1953        {
1954                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
1955                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
1956
1957                //-- collapse tree
1958                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
1959                {
1960                        BspViewCell *vc = frontLeaf->GetViewCell();
1961
1962                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
1963                       
1964                        // replace a link from node's parent
1965                        if (leaf->GetParent())
1966                                leaf->GetParent()->ReplaceChildLink(node, leaf);
1967
1968                        delete interior;
1969
1970                        return leaf;
1971                }
1972        }
1973
1974        return node;
1975}
1976
1977
1978void VspBspTree::RepairVcLeafLists()
1979{
1980        // list not valid anymore => clear
1981        stack<BspNode *> nodeStack;
1982        nodeStack.push(mRoot);
1983
1984        ViewCell::NewMail();
1985
1986        while (!nodeStack.empty())
1987        {
1988                BspNode *node = nodeStack.top();
1989                nodeStack.pop();
1990
1991                if (node->IsLeaf())
1992                {
1993                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1994
1995                        BspViewCell *viewCell = leaf->GetViewCell();
1996
1997                        if (!viewCell->Mailed())
1998                        {
1999                                viewCell->mLeaves.clear();
2000                                viewCell->Mail();
2001                        }
2002
2003                        viewCell->mLeaves.push_back(leaf);
2004                }
2005                else
2006                {
2007                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2008
2009                        nodeStack.push(interior->GetFront());
2010                        nodeStack.push(interior->GetBack());
2011                }
2012        }
2013}
2014
2015
2016int VspBspTree::MergeLeaves()
2017{
2018        vector<BspLeaf *> leaves;
2019        priority_queue<BspMergeCandidate> mergeQueue;
2020
2021        // collect the leaves, e.g., the "voxels" that will build the view cells
2022        CollectLeaves(leaves);
2023
2024        int vcSize = (int)leaves.size();
2025        int savedVcSize = vcSize;
2026
2027        BspLeaf::NewMail();
2028
2029        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2030
2031        // find merge candidates and push them into queue
2032        for (it = leaves.begin(); it != it_end; ++ it)
2033        {
2034                BspLeaf *leaf = *it;
2035
2036                // no leaf is part of two merge candidates
2037                if (!leaf->Mailed())
2038                {
2039                        leaf->Mail();
2040
2041                        vector<BspLeaf *> neighbors;
2042                        FindNeighbors(leaf, neighbors, true);
2043
2044                        vector<BspLeaf *>::const_iterator nit,
2045                                nit_end = neighbors.end();
2046
2047                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2048                        {
2049                                BspMergeCandidate mc = BspMergeCandidate(leaf, *nit);
2050                                mergeQueue.push(mc);
2051
2052                                BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
2053                                BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
2054                        }
2055                }
2056        }
2057
2058        int merged = 0;
2059
2060        //-- use priority queue to merge leaf pairs
2061        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
2062                   (mergeQueue.top().GetMergeCost() <
2063                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2064        {
2065                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
2066                BspMergeCandidate mc = mergeQueue.top();
2067                mergeQueue.pop();
2068
2069                // both view cells equal!
2070                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2071                        continue;
2072
2073                if (mc.Valid())
2074                {
2075                        ViewCell::NewMail();
2076                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2077
2078                        ++ merged;
2079                        -- vcSize;
2080                        // increase absolute merge cost
2081                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2082                }
2083                // merge candidate not valid, because one of the leaves was already
2084                // merged with another one
2085                else
2086                {
2087                        // validate and reinsert into queue
2088                        mc.SetValid();
2089                        mergeQueue.push(mc);
2090                        //Debug << "validate " << mc.GetMergeCost() << endl;
2091                }
2092        }
2093
2094        // collapse tree according to view cell partition
2095        CollapseTree(mRoot);
2096        // revalidate leaves
2097        RepairVcLeafLists();
2098
2099        //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
2100
2101        //TODO: should return sample contributions
2102        return merged;
2103}
2104
2105
2106bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2)
2107{
2108        //-- change pointer to view cells of all leaves associated
2109        //-- with the previous view cells
2110        BspViewCell *fVc = l1->GetViewCell();
2111        BspViewCell *bVc = l2->GetViewCell();
2112
2113        BspViewCell *vc = dynamic_cast<BspViewCell *>(
2114                mViewCellsManager->MergeViewCells(*fVc, *bVc));
2115
2116        // if merge was unsuccessful
2117        if (!vc) return false;
2118
2119        // set new size of view cell
2120        vc->SetArea(fVc->GetArea() + bVc->GetArea());
2121
2122        vector<BspLeaf *> fLeaves = fVc->mLeaves;
2123        vector<BspLeaf *> bLeaves = bVc->mLeaves;
2124
2125        vector<BspLeaf *>::const_iterator it;
2126
2127        //-- change view cells of all the other leaves the view cell belongs to
2128        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2129        {
2130                (*it)->SetViewCell(vc);
2131                vc->mLeaves.push_back(*it);
2132        }
2133
2134        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2135        {
2136                (*it)->SetViewCell(vc);
2137                vc->mLeaves.push_back(*it);
2138        }
2139
2140        vc->Mail();
2141
2142        // clean up old view cells
2143        DEL_PTR(fVc);
2144        DEL_PTR(bVc);
2145
2146        return true;
2147}
2148
2149
2150void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2151{
2152        mViewCellsManager = vcm;
2153}
2154
2155/************************************************************************/
2156/*                BspMergeCandidate implementation                      */
2157/************************************************************************/
2158
2159
2160BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
2161mMergeCost(0),
2162mLeaf1(l1),
2163mLeaf2(l2),
2164mLeaf1Id(l1->GetViewCell()->mMailbox),
2165mLeaf2Id(l2->GetViewCell()->mMailbox)
2166{
2167        EvalMergeCost();
2168}
2169
2170float BspMergeCandidate::GetLeaf1Cost() const
2171{
2172        BspViewCell *vc = mLeaf1->GetViewCell();
2173        return vc->GetPvs().GetSize() * vc->GetArea();
2174}
2175
2176float BspMergeCandidate::GetLeaf2Cost() const
2177{
2178        BspViewCell *vc = mLeaf2->GetViewCell();
2179        return vc->GetPvs().GetSize() * vc->GetVolume();
2180}
2181
2182void BspMergeCandidate::EvalMergeCost()
2183{
2184        //-- compute pvs difference
2185        BspViewCell *vc1 = mLeaf1->GetViewCell();
2186        BspViewCell *vc2 = mLeaf2->GetViewCell();
2187
2188        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
2189        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
2190
2191        //-- compute ratio of old cost
2192        //-- (added size of left and right view cell times pvs size)
2193        //-- to new rendering cost (size of merged view cell times pvs size)
2194        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
2195       
2196        const float newCost =
2197                (float)vcPvs * (vc1->GetArea() + vc2->GetArea());
2198
2199        mMergeCost = newCost - oldCost;
2200
2201//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
2202//              mMergeCost += 1.0;
2203}
2204
2205void BspMergeCandidate::SetLeaf1(BspLeaf *l)
2206{
2207        mLeaf1 = l;
2208}
2209
2210void BspMergeCandidate::SetLeaf2(BspLeaf *l)
2211{
2212        mLeaf2 = l;
2213}
2214
2215BspLeaf *BspMergeCandidate::GetLeaf1()
2216{
2217        return mLeaf1;
2218}
2219
2220BspLeaf *BspMergeCandidate::GetLeaf2()
2221{
2222        return mLeaf2;
2223}
2224
2225bool BspMergeCandidate::Valid() const
2226{
2227        return
2228                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
2229                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
2230}
2231
2232float BspMergeCandidate::GetMergeCost() const
2233{
2234        return mMergeCost;
2235}
2236
2237void BspMergeCandidate::SetValid()
2238{
2239        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
2240        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
2241
2242        EvalMergeCost();
2243}
Note: See TracBrowser for help on using the repository browser.