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

Revision 481, 53.1 KB checked in by mattausch, 19 years ago (diff)

removed axis aligned options for vsp bsp.
updated axis aligned heuristics for vsp bsp
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                                                                                  const 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        const bool useCostHeuristics = false;
727
728        //-- regular split
729        float nPosition[3];
730        float nCostRatio[3];
731        int bestAxis = -1;
732
733        bool mOnlyDrivingAxis = false;
734
735        const int sAxis = box.Size().DrivingAxis();
736               
737        for (int axis = 0; axis < 3; ++ axis)
738        {
739                if (!mOnlyDrivingAxis || axis == sAxis)
740                {
741                        if (!useCostHeuristics)
742                        {
743                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
744                                Vector3 normal(0,0,0); normal[axis] = 1;
745
746                                nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), tData);
747                        }
748                        else
749                        {
750                                nCostRatio[axis] =
751                                        BestCostRatioHeuristics(*tData.mRays,
752                                                                                    box,
753                                                                                        tData.mPvs,
754                                                                                        axis,
755                                                                                        nPosition[axis]);
756                        }
757
758                        if (bestAxis == -1)
759                        {
760                                bestAxis = axis;
761                        }
762
763                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
764                        {
765                                /*Debug << "pvs front " << nPvsBack[axis]
766                                          << " pvs back " << nPvsFront[axis]
767                                          << " overall pvs " << leaf->GetPvsSize() << endl;*/
768                                bestAxis = axis;
769                        }
770
771                }
772        }
773
774        //-- assign best axis
775        Vector3 normal(0,0,0); normal[bestAxis] = 1;
776        plane = Plane3(normal, nPosition[bestAxis]);
777
778        return nCostRatio[bestAxis];
779}
780
781
782bool VspBspTree::SelectPlane(Plane3 &plane,
783                                                         BspLeaf *leaf,
784                                                         VspBspTraversalData &data)
785{
786        // simplest strategy: just take next polygon
787        if (mSplitPlaneStrategy & RANDOM_POLYGON)
788        {
789        if (!data.mPolygons->empty())
790                {
791                        const int randIdx = (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
792                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
793
794                        plane = nextPoly->GetSupportingPlane();
795                        return true;
796                }
797                else
798                {
799                        //-- choose plane on midpoint of a ray
800                        const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1));
801                                                                       
802                        const Vector3 minPt = (*data.mRays)[candidateIdx].ExtrapOrigin();
803                        const Vector3 maxPt = (*data.mRays)[candidateIdx].ExtrapTermination();
804
805                        const Vector3 pt = (maxPt + minPt) * 0.5;
806
807                        const Vector3 normal = (*data.mRays)[candidateIdx].mRay->GetDir();
808                       
809                        plane = Plane3(normal, pt);
810                        return true;
811                }
812
813                return false;
814        }
815
816        // use heuristics to find appropriate plane
817        return SelectPlaneHeuristics(plane, leaf, data);
818}
819
820
821Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
822{       
823        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
824       
825        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
826        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
827
828        const Vector3 pt = (maxPt + minPt) * 0.5;
829        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
830
831        return Plane3(normal, pt);
832}
833
834
835Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
836{       
837        Vector3 pt[3];
838       
839        int idx[3];
840        int cmaxT = 0;
841        int cminT = 0;
842        bool chooseMin = false;
843
844        for (int j = 0; j < 3; ++ j)
845        {
846                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
847                       
848                if (idx[j] >= (int)rays.size())
849                {
850                        idx[j] -= (int)rays.size();
851                               
852                        chooseMin = (cminT < 2);
853                }
854                else
855                        chooseMin = (cmaxT < 2);
856
857                RayInfo rayInf = rays[idx[j]];
858                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
859        }       
860
861        return Plane3(pt[0], pt[1], pt[2]);
862}
863
864Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
865{       
866        Vector3 pt[3];
867       
868        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
869        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
870
871        // check if rays different
872        if (idx1 == idx2)
873                idx2 = (idx2 + 1) % (int)rays.size();
874
875        const RayInfo ray1 = rays[idx1];
876        const RayInfo ray2 = rays[idx2];
877
878        // normal vector of the plane parallel to both lines
879        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
880
881        // vector from line 1 to line 2
882        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
883       
884        // project vector on normal to get distance
885        const float dist = DotProd(vd, norm);
886
887        // point on plane lies halfway between the two planes
888        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
889
890        return Plane3(norm, planePt);
891}
892
893bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane,
894                                                                           BspLeaf *leaf,
895                                                                           VspBspTraversalData &data)
896{
897        float lowestCost = MAX_FLOAT;
898        // intermediate plane
899        Plane3 plane;
900
901        const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
902        int maxIdx = (int)data.mPolygons->size();
903       
904        float candidateCost;
905
906        for (int i = 0; i < limit; ++ i)
907        {
908                // assure that no index is taken twice
909                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
910                //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl;
911               
912                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
913
914                // swap candidate to the end to avoid testing same plane
915                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
916       
917                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
918
919                // evaluate current candidate
920                candidateCost = SplitPlaneCost(poly->GetSupportingPlane(), data);
921
922                if (candidateCost < lowestCost)
923                {
924                        bestPlane = poly->GetSupportingPlane();
925                        lowestCost = candidateCost;
926                }
927        }
928       
929#if 0
930        //-- choose candidate planes extracted from rays
931        //-- different methods are available
932        for (int i = 0; i < mMaxRayCandidates; ++ i)
933        {
934                plane = ChooseCandidatePlane3(*data.mRays);
935                candidateCost = SplitPlaneCost(plane, data);
936
937                if (candidateCost < lowestCost)
938                {
939                        bestPlane = plane;     
940                        lowestCost = candidateCost;
941                }
942        }
943#endif
944
945        // axis aligned splits
946        candidateCost = SelectAxisAlignedPlane(plane, data);
947
948        if (candidateCost < lowestCost)
949        {
950                bestPlane = plane;     
951                lowestCost = candidateCost;
952        }
953
954#ifdef _DEBUG
955        Debug << "plane lowest cost: " << lowestCost << endl;
956#endif
957
958        // cost ratio miss
959        if (lowestCost > mTermMaxCostRatio)
960                return false;
961
962        return true;
963}
964
965
966inline void VspBspTree::GenerateUniqueIdsForPvs()
967{
968        Intersectable::NewMail(); sBackId = ViewCell::sMailId;
969        Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
970        Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
971}
972
973float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,
974                                                                 const VspBspTraversalData &data) const
975{
976        float cost = 0;
977
978        float sumBalancedRays = 0;
979        float sumRaySplits = 0;
980       
981        int frontPvs = 0;
982        int backPvs = 0;
983
984        // probability that view point lies in child
985        float pOverall = 0;
986        float pFront = 0;
987        float pBack = 0;
988
989        const bool pvsUseLen = false;
990
991        if (mSplitPlaneStrategy & PVS)
992        {
993                // create unique ids for pvs heuristics
994                GenerateUniqueIdsForPvs();
995       
996                if (mPvsUseArea) // use front and back cell areas to approximate volume
997                {       
998                        // construct child geometry with regard to the candidate split plane
999                        BspNodeGeometry frontCell;
1000                        BspNodeGeometry backCell;
1001               
1002                        data.mGeometry->SplitGeometry(frontCell,
1003                                                                                  backCell,
1004                                                                                  candidatePlane,
1005                                                                                  mBox,
1006                                                                                  mEpsilon);
1007               
1008                        pFront = frontCell.GetArea();
1009                        pBack = backCell.GetArea();
1010
1011                        pOverall = data.mArea;
1012                }
1013        }
1014               
1015        int limit;
1016        bool useRand;
1017
1018        // choose test polyongs randomly if over threshold
1019        if ((int)data.mRays->size() > mMaxTests)
1020        {
1021                useRand = true;
1022                limit = mMaxTests;
1023        }
1024        else
1025        {
1026                useRand = false;
1027                limit = (int)data.mRays->size();
1028        }
1029
1030        for (int i = 0; i < limit; ++ i)
1031        {
1032                const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i;
1033                RayInfo rayInf = (*data.mRays)[testIdx];
1034
1035                VssRay *ray = rayInf.mRay;
1036                float t;
1037                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1038
1039                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1040                {
1041                        sumBalancedRays += cf;
1042                }
1043               
1044                if (mSplitPlaneStrategy & BALANCED_RAYS)
1045                {
1046                        if (cf == 0)
1047                                ++ sumRaySplits;
1048                }
1049
1050                if (mSplitPlaneStrategy & PVS)
1051                {
1052                        // in case the ray intersects an object
1053                        // assure that we only count the object
1054                        // once for the front and once for the back side of the plane
1055                       
1056                        // add the termination object
1057                        AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
1058                       
1059                        // add the source object
1060                        AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
1061                       
1062                        // use number or length of rays to approximate volume
1063                        if (!mPvsUseArea)
1064                        {
1065                                float len = 1;
1066
1067                                if (pvsUseLen) // use length of rays
1068                                        len = rayInf.SqrSegmentLength();
1069                       
1070                                pOverall += len;
1071
1072                                if (cf == 1)
1073                                        pFront += len;
1074                                if (cf == -1)
1075                                        pBack += len;
1076                                if (cf == 0)
1077                                {
1078                                        // use length of rays to approximate volume
1079                                        if (pvsUseLen)
1080                                        {
1081                                                float newLen = len *
1082                                                        (rayInf.GetMaxT() - t) /
1083                                                        (rayInf.GetMaxT() - rayInf.GetMinT());
1084               
1085                                                if (candidatePlane.Side(rayInf.ExtrapOrigin()) <= 0)
1086                                                {
1087                                                        pBack += newLen;
1088                                                        pFront += len - newLen;
1089                                                }
1090                                                else
1091                                                {
1092                                                        pFront += newLen;
1093                                                        pBack += len - newLen;
1094                                                }
1095                                        }
1096                                        else
1097                                        {
1098                                                ++ pFront;
1099                                                ++ pBack;
1100                                        }
1101                                }
1102                        }
1103                }
1104        }
1105
1106        const float raysSize = (float)data.mRays->size() + Limits::Small;
1107       
1108        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1109                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1110
1111        if (mSplitPlaneStrategy & BALANCED_RAYS)
1112                cost += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
1113       
1114        // pvs criterium
1115        if (mSplitPlaneStrategy & PVS)
1116        {
1117                const float oldCost = pOverall * (float)data.mPvs + Limits::Small;
1118                cost += mPvsFactor * (frontPvs * pFront + backPvs * pBack) / oldCost;
1119
1120                //cost += mPvsFactor * 0.5 * (frontPvs * pFront + backPvs * pBack) / oldCost;
1121                //Debug << "new cost: " << cost << " over" << frontPvs * pFront + backPvs * pBack << " old cost " << oldCost << endl;
1122       
1123                if (0) // give penalty to unbalanced split
1124                        if (((pFront * 0.2 + Limits::Small) > pBack) ||
1125                                (pFront < (pBack * 0.2 + Limits::Small)))
1126                                        cost += 0.5;
1127        }
1128
1129#ifdef _DEBUG
1130        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
1131                  << " frontpvs: " << frontPvs << " pFront: " << pFront
1132                  << " backpvs: " << backPvs << " pBack: " << pBack << endl << endl;
1133#endif
1134       
1135        // normalize cost by sum of linear factors
1136        return cost / (float)mCostNormalizer;
1137}
1138
1139void VspBspTree::AddObjToPvs(Intersectable *obj,
1140                                                         const int cf,
1141                                                         int &frontPvs,
1142                                                         int &backPvs) const
1143{
1144        if (!obj)
1145                return;
1146        // TODO: does this really belong to no pvs?
1147        //if (cf == Ray::COINCIDENT) return;
1148
1149        // object belongs to both PVS
1150        if (cf >= 0)
1151        {
1152                if ((obj->mMailbox != sFrontId) &&
1153                        (obj->mMailbox != sFrontAndBackId))
1154                {
1155                        ++ frontPvs;
1156
1157                        if (obj->mMailbox == sBackId)
1158                                obj->mMailbox = sFrontAndBackId;       
1159                        else
1160                                obj->mMailbox = sFrontId;                                                               
1161                }
1162        }
1163       
1164        if (cf <= 0)
1165        {
1166                if ((obj->mMailbox != sBackId) &&
1167                        (obj->mMailbox != sFrontAndBackId))
1168                {
1169                        ++ backPvs;
1170
1171                        if (obj->mMailbox == sFrontId)
1172                                obj->mMailbox = sFrontAndBackId;
1173                        else
1174                                obj->mMailbox = sBackId;                               
1175                }
1176        }
1177}
1178
1179void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1180{
1181        stack<BspNode *> nodeStack;
1182        nodeStack.push(mRoot);
1183 
1184        while (!nodeStack.empty())
1185        {
1186                BspNode *node = nodeStack.top();
1187   
1188                nodeStack.pop();
1189   
1190                if (node->IsLeaf())
1191                {
1192                        BspLeaf *leaf = (BspLeaf *)node;               
1193                        leaves.push_back(leaf);
1194                }
1195                else
1196                {
1197                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1198
1199                        nodeStack.push(interior->GetBack());
1200                        nodeStack.push(interior->GetFront());
1201                }
1202        }
1203}
1204
1205AxisAlignedBox3 VspBspTree::GetBoundingBox() const
1206{
1207        return mBox;
1208}
1209
1210BspNode *VspBspTree::GetRoot() const
1211{
1212        return mRoot;
1213}
1214
1215void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
1216{
1217        // the node became a leaf -> evaluate stats for leafs
1218        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1219
1220        // store maximal and minimal depth
1221        if (data.mDepth > mStat.maxDepth)
1222                mStat.maxDepth = data.mDepth;
1223
1224        if (data.mDepth < mStat.minDepth)
1225                mStat.minDepth = data.mDepth;
1226       
1227        if (data.mDepth >= mTermMaxDepth)
1228                ++ mStat.maxDepthNodes;
1229
1230        if (data.mPvs < mTermMinPvs)
1231                ++ mStat.minPvsNodes;
1232
1233        if ((int)data.mRays->size() < mTermMinRays)
1234                ++ mStat.minRaysNodes;
1235
1236        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1237                ++ mStat.maxRayContribNodes;
1238       
1239        if (data.mArea <= mTermMinArea)
1240        {
1241                //Debug << "area: " << data.mArea / mBox.SurfaceArea() << " min area: " << mTermMinArea / mBox.SurfaceArea() << endl;
1242                ++ mStat.minAreaNodes;
1243        }
1244        // accumulate depth to compute average depth
1245        mStat.accumDepth += data.mDepth;
1246
1247#ifdef _DEBUG
1248        Debug << "BSP stats: "
1249                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1250                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1251                  << "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
1252                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1253                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1254                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1255#endif
1256}
1257
1258int VspBspTree::CastRay(Ray &ray)
1259{
1260        int hits = 0;
1261 
1262        stack<BspRayTraversalData> tStack;
1263 
1264        float maxt, mint;
1265
1266        if (!mBox.GetRaySegment(ray, mint, maxt))
1267                return 0;
1268
1269        Intersectable::NewMail();
1270
1271        Vector3 entp = ray.Extrap(mint);
1272        Vector3 extp = ray.Extrap(maxt);
1273 
1274        BspNode *node = mRoot;
1275        BspNode *farChild = NULL;
1276       
1277        while (1)
1278        {
1279                if (!node->IsLeaf())
1280                {
1281                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1282
1283                        Plane3 splitPlane = in->GetPlane();
1284                        const int entSide = splitPlane.Side(entp);
1285                        const int extSide = splitPlane.Side(extp);
1286
1287                        if (entSide < 0)
1288                        {
1289                                node = in->GetBack();
1290
1291                                if(extSide <= 0) // plane does not split ray => no far child
1292                                        continue;
1293                                       
1294                                farChild = in->GetFront(); // plane splits ray
1295
1296                        } else if (entSide > 0)
1297                        {
1298                                node = in->GetFront();
1299
1300                                if (extSide >= 0) // plane does not split ray => no far child
1301                                        continue;
1302
1303                                farChild = in->GetBack(); // plane splits ray                   
1304                        }
1305                        else // ray and plane are coincident
1306                        {
1307                                // WHAT TO DO IN THIS CASE ?
1308                                //break;
1309                                node = in->GetFront();
1310                                continue;
1311                        }
1312
1313                        // push data for far child
1314                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1315
1316                        // find intersection of ray segment with plane
1317                        float t;
1318                        extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1319                        maxt *= t;
1320                       
1321                } else // reached leaf => intersection with view cell
1322                {
1323                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1324     
1325                        if (!leaf->GetViewCell()->Mailed())
1326                        {
1327                                //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
1328                                leaf->GetViewCell()->Mail();
1329                                ++ hits;
1330                        }
1331                       
1332                        //-- fetch the next far child from the stack
1333                        if (tStack.empty())
1334                                break;
1335     
1336                        entp = extp;
1337                        mint = maxt; // NOTE: need this?
1338
1339                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1340                                break;
1341
1342                        BspRayTraversalData &s = tStack.top();
1343
1344                        node = s.mNode;
1345                        extp = s.mExitPoint;
1346                        maxt = s.mMaxT;
1347
1348                        tStack.pop();
1349                }
1350        }
1351
1352        return hits;
1353}
1354
1355bool VspBspTree::Export(const string filename)
1356{
1357        Exporter *exporter = Exporter::GetExporter(filename);
1358
1359        if (exporter)
1360        {
1361                //exporter->ExportVspBspTree(*this);
1362                return true;
1363        }       
1364
1365        return false;
1366}
1367
1368void VspBspTree::CollectViewCells(ViewCellContainer &viewCells) const
1369{
1370        stack<BspNode *> nodeStack;
1371        nodeStack.push(mRoot);
1372
1373        ViewCell::NewMail();
1374
1375        while (!nodeStack.empty())
1376        {
1377                BspNode *node = nodeStack.top();
1378                nodeStack.pop();
1379
1380                if (node->IsLeaf())
1381                {
1382                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1383
1384                        if (!viewCell->Mailed())
1385                        {
1386                                viewCell->Mail();
1387                                viewCells.push_back(viewCell);
1388                        }
1389                }
1390                else
1391                {
1392                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1393
1394                        nodeStack.push(interior->GetFront());
1395                        nodeStack.push(interior->GetBack());
1396                }
1397        }
1398}
1399
1400
1401BspTreeStatistics &VspBspTree::GetStat()
1402{
1403        return mStat;
1404}
1405
1406
1407float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1408{
1409        float len = 0;
1410
1411        RayInfoContainer::const_iterator it, it_end = rays.end();
1412
1413        for (it = rays.begin(); it != it_end; ++ it)
1414                len += (*it).SegmentLength();
1415
1416        return len;
1417}
1418
1419
1420int VspBspTree::SplitRays(const Plane3 &plane,
1421                                                  RayInfoContainer &rays,
1422                                                  RayInfoContainer &frontRays,
1423                                                  RayInfoContainer &backRays)
1424{
1425        int splits = 0;
1426
1427        while (!rays.empty())
1428        {
1429                RayInfo bRay = rays.back();
1430                rays.pop_back();
1431
1432                VssRay *ray = bRay.mRay;
1433                float t;
1434
1435                        // get classification and receive new t
1436                const int cf = bRay.ComputeRayIntersection(plane, t);
1437       
1438                switch (cf)
1439                {
1440                case -1:
1441                        backRays.push_back(bRay);
1442                        break;
1443                case 1:
1444                        frontRays.push_back(bRay);
1445                        break;
1446                case 0:
1447                        //-- split ray
1448                        //--  look if start point behind or in front of plane
1449                        if (plane.Side(bRay.ExtrapOrigin()) <= 0)
1450                        {       
1451                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1452                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1453                        }
1454                        else
1455                        {
1456                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1457                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1458                        }
1459                        break;
1460                default:
1461                        Debug << "Should not come here 4" << endl;
1462                        break;
1463                }
1464        }
1465
1466        return splits;
1467}
1468
1469
1470void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1471{
1472        BspNode *lastNode;
1473
1474        do
1475        {
1476                lastNode = n;
1477
1478                // want to get planes defining geometry of this node => don't take
1479                // split plane of node itself
1480                n = n->GetParent();
1481               
1482                if (n)
1483                {
1484                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
1485                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1486
1487            if (interior->GetFront() != lastNode)
1488                                halfSpace.ReverseOrientation();
1489
1490                        halfSpaces.push_back(halfSpace);
1491                }
1492        }
1493        while (n);
1494}
1495
1496void VspBspTree::ConstructGeometry(BspNode *n,
1497                                                                   BspNodeGeometry &cell) const
1498{
1499        PolygonContainer polys;
1500        ConstructGeometry(n, polys);
1501        cell.mPolys = polys;
1502}
1503
1504void VspBspTree::ConstructGeometry(BspNode *n,
1505                                                                   PolygonContainer &cell) const
1506{
1507        vector<Plane3> halfSpaces;
1508        ExtractHalfSpaces(n, halfSpaces);
1509
1510        PolygonContainer candidatePolys;
1511
1512        // bounded planes are added to the polygons (reverse polygons
1513        // as they have to be outfacing
1514        for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1515        {
1516                Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1517               
1518                if (p->Valid(mEpsilon))
1519                {
1520                        candidatePolys.push_back(p->CreateReversePolygon());
1521                        DEL_PTR(p);
1522                }
1523        }
1524
1525        // add faces of bounding box (also could be faces of the cell)
1526        for (int i = 0; i < 6; ++ i)
1527        {
1528                VertexContainer vertices;
1529       
1530                for (int j = 0; j < 4; ++ j)
1531                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
1532
1533                candidatePolys.push_back(new Polygon3(vertices));
1534        }
1535
1536        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
1537        {
1538                // polygon is split by all other planes
1539                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
1540                {
1541                        if (i == j) // polygon and plane are coincident
1542                                continue;
1543
1544                        VertexContainer splitPts;
1545                        Polygon3 *frontPoly, *backPoly;
1546
1547                        const int cf =
1548                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
1549                                                                                                 mEpsilon);
1550                       
1551                        switch (cf)
1552                        {
1553                                case Polygon3::SPLIT:
1554                                        frontPoly = new Polygon3();
1555                                        backPoly = new Polygon3();
1556
1557                                        candidatePolys[i]->Split(halfSpaces[j],
1558                                                                                         *frontPoly,
1559                                                                                         *backPoly,
1560                                                                                         mEpsilon);
1561
1562                                        DEL_PTR(candidatePolys[i]);
1563
1564                                        if (frontPoly->Valid(mEpsilon))
1565                                                candidatePolys[i] = frontPoly;
1566                                        else
1567                                                DEL_PTR(frontPoly);
1568
1569                                        DEL_PTR(backPoly);
1570                                        break;
1571                                case Polygon3::BACK_SIDE:
1572                                        DEL_PTR(candidatePolys[i]);
1573                                        break;
1574                                // just take polygon as it is
1575                                case Polygon3::FRONT_SIDE:
1576                                case Polygon3::COINCIDENT:
1577                                default:
1578                                        break;
1579                        }
1580                }
1581               
1582                if (candidatePolys[i])
1583                        cell.push_back(candidatePolys[i]);
1584        }
1585}
1586
1587void VspBspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &vcGeom) const
1588{
1589        vector<BspLeaf *> leaves = vc->mLeaves;
1590
1591        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
1592
1593        for (it = leaves.begin(); it != it_end; ++ it)
1594                ConstructGeometry(*it, vcGeom);
1595}
1596
1597int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
1598                                                   const bool onlyUnmailed) const
1599{
1600        PolygonContainer cell;
1601
1602        ConstructGeometry(n, cell);
1603
1604        stack<BspNode *> nodeStack;
1605        nodeStack.push(mRoot);
1606               
1607        // planes needed to verify that we found neighbor leaf.
1608        vector<Plane3> halfSpaces;
1609        ExtractHalfSpaces(n, halfSpaces);
1610
1611        while (!nodeStack.empty())
1612        {
1613                BspNode *node = nodeStack.top();
1614                nodeStack.pop();
1615
1616                if (node->IsLeaf())
1617                {
1618            if (node != n && (!onlyUnmailed || !node->Mailed()))
1619                        {
1620                                // test all planes of current node if candidate really
1621                                // is neighbour
1622                                PolygonContainer neighborCandidate;
1623                                ConstructGeometry(node, neighborCandidate);
1624                               
1625                                bool isAdjacent = true;
1626                                for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
1627                                {
1628                                        const int cf =
1629                                                Polygon3::ClassifyPlane(neighborCandidate,
1630                                                                                                halfSpaces[i],
1631                                                                                                mEpsilon);
1632
1633                                        if (cf == Polygon3::BACK_SIDE)
1634                                                isAdjacent = false;
1635                                }
1636
1637                                if (isAdjacent)
1638                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
1639
1640                                CLEAR_CONTAINER(neighborCandidate);
1641                        }
1642                }
1643                else
1644                {
1645                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1646       
1647                        const int cf = Polygon3::ClassifyPlane(cell,
1648                                                                                                   interior->GetPlane(),
1649                                                                                                   mEpsilon);
1650
1651                        if (cf == Polygon3::FRONT_SIDE)
1652                                nodeStack.push(interior->GetFront());
1653                        else
1654                                if (cf == Polygon3::BACK_SIDE)
1655                                        nodeStack.push(interior->GetBack());
1656                                else
1657                                {
1658                                        // random decision
1659                                        nodeStack.push(interior->GetBack());
1660                                        nodeStack.push(interior->GetFront());
1661                                }
1662                }
1663        }
1664       
1665        CLEAR_CONTAINER(cell);
1666        return (int)neighbors.size();
1667}
1668
1669BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
1670{
1671    stack<BspNode *> nodeStack;
1672        nodeStack.push(mRoot);
1673       
1674        int mask = rand();
1675 
1676        while (!nodeStack.empty())
1677        {
1678                BspNode *node = nodeStack.top();
1679                nodeStack.pop();
1680         
1681                if (node->IsLeaf())
1682                {
1683                        return dynamic_cast<BspLeaf *>(node);
1684                }
1685                else
1686                {
1687                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1688                       
1689                        BspNode *next;
1690       
1691                        PolygonContainer cell;
1692
1693                        // todo: not very efficient: constructs full cell everytime
1694                        ConstructGeometry(interior, cell);
1695
1696                        const int cf = Polygon3::ClassifyPlane(cell, halfspace, mEpsilon);
1697
1698                        if (cf == Polygon3::BACK_SIDE)
1699                                next = interior->GetFront();
1700                        else
1701                                if (cf == Polygon3::FRONT_SIDE)
1702                                        next = interior->GetFront();
1703                        else
1704                        {
1705                                // random decision
1706                                if (mask & 1)
1707                                        next = interior->GetBack();
1708                                else
1709                                        next = interior->GetFront();
1710                                mask = mask >> 1;
1711                        }
1712
1713                        nodeStack.push(next);
1714                }
1715        }
1716       
1717        return NULL;
1718}
1719
1720BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
1721{
1722        stack<BspNode *> nodeStack;
1723       
1724        nodeStack.push(mRoot);
1725
1726        int mask = rand();
1727       
1728        while (!nodeStack.empty())
1729        {
1730                BspNode *node = nodeStack.top();
1731                nodeStack.pop();
1732               
1733                if (node->IsLeaf())
1734                {
1735                        if ( (!onlyUnmailed || !node->Mailed()) )
1736                                return dynamic_cast<BspLeaf *>(node);
1737                }
1738                else
1739                {
1740                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1741
1742                        // random decision
1743                        if (mask & 1)
1744                                nodeStack.push(interior->GetBack());
1745                        else
1746                                nodeStack.push(interior->GetFront());
1747
1748                        mask = mask >> 1;
1749                }
1750        }
1751       
1752        return NULL;
1753}
1754
1755int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
1756{
1757        int pvsSize = 0;
1758
1759        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1760
1761        Intersectable::NewMail();
1762
1763        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1764        {
1765                VssRay *ray = (*rit).mRay;
1766               
1767                if (ray->mOriginObject)
1768                {
1769                        if (!ray->mOriginObject->Mailed())
1770                        {
1771                                ray->mOriginObject->Mail();
1772                                ++ pvsSize;
1773                        }
1774                }
1775                if (ray->mTerminationObject)
1776                {
1777                        if (!ray->mTerminationObject->Mailed())
1778                        {
1779                                ray->mTerminationObject->Mail();
1780                                ++ pvsSize;
1781                        }
1782                }
1783        }
1784
1785        return pvsSize;
1786}
1787
1788float VspBspTree::GetEpsilon() const
1789{
1790        return mEpsilon;
1791}
1792
1793BspViewCell *VspBspTree::GetRootCell() const
1794{
1795        return mRootCell;
1796}
1797
1798int VspBspTree::SplitPolygons(const Plane3 &plane,
1799                                                          PolygonContainer &polys,
1800                                                          PolygonContainer &frontPolys,
1801                                                          PolygonContainer &backPolys,
1802                                                          PolygonContainer &coincident) const
1803{
1804        int splits = 0;
1805
1806        while (!polys.empty())
1807        {
1808                Polygon3 *poly = polys.back();
1809                polys.pop_back();
1810
1811                // classify polygon
1812                const int cf = poly->ClassifyPlane(plane, mEpsilon);
1813
1814                switch (cf)
1815                {
1816                        case Polygon3::COINCIDENT:
1817                                coincident.push_back(poly);
1818                                break;                 
1819                        case Polygon3::FRONT_SIDE:     
1820                                frontPolys.push_back(poly);
1821                                break;
1822                        case Polygon3::BACK_SIDE:
1823                                backPolys.push_back(poly);
1824                                break;
1825                        case Polygon3::SPLIT:
1826                                backPolys.push_back(poly);
1827                                frontPolys.push_back(poly);
1828                                ++ splits;
1829                                break;
1830                        default:
1831                Debug << "SHOULD NEVER COME HERE\n";
1832                                break;
1833                }
1834        }
1835
1836        return splits;
1837}
1838
1839
1840int VspBspTree::CastLineSegment(const Vector3 &origin,
1841                                                                const Vector3 &termination,
1842                                                                vector<ViewCell *> &viewcells)
1843{
1844        int hits = 0;
1845        stack<BspRayTraversalData> tStack;
1846 
1847        float mint = 0.0f, maxt = 1.0f;
1848 
1849        Intersectable::NewMail();
1850 
1851        Vector3 entp = origin;
1852        Vector3 extp = termination;
1853 
1854        BspNode *node = mRoot;
1855        BspNode *farChild = NULL;
1856 
1857        while (1)
1858        {
1859                if (!node->IsLeaf()) 
1860                {
1861                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1862         
1863                        Plane3 splitPlane = in->GetPlane();
1864                        const int entSide = splitPlane.Side(entp);
1865                        const int extSide = splitPlane.Side(extp);
1866         
1867                        if (entSide < 0)
1868                        {
1869                                node = in->GetBack();
1870               
1871                                if(extSide <= 0) // plane does not split ray => no far child
1872                                        continue;
1873               
1874                                farChild = in->GetFront(); // plane splits ray
1875                        } else if (entSide > 0)
1876                        {
1877                                node = in->GetFront();
1878                 
1879                                if (extSide >= 0) // plane does not split ray => no far child
1880                                        continue;
1881                 
1882                                farChild = in->GetBack(); // plane splits ray                   
1883                        }
1884                        else // ray and plane are coincident
1885                        {
1886                                // WHAT TO DO IN THIS CASE ?
1887                                //break;
1888                                node = in->GetFront();
1889                                continue;
1890                        }
1891         
1892                        // push data for far child
1893                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1894         
1895                        // find intersection of ray segment with plane
1896                        float t;
1897                        extp = splitPlane.FindIntersection(origin, extp, &t);
1898                        maxt *= t;
1899         
1900                } else
1901                {
1902                        // reached leaf => intersection with view cell
1903                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1904         
1905                        if (!leaf->GetViewCell()->Mailed())
1906                        {
1907                                viewcells.push_back(leaf->GetViewCell());
1908                                leaf->GetViewCell()->Mail();
1909                                ++ hits;
1910                        }
1911         
1912                        //-- fetch the next far child from the stack
1913                        if (tStack.empty())
1914                                break;
1915     
1916                        entp = extp;
1917                        mint = maxt; // NOTE: need this?
1918         
1919                       
1920                        BspRayTraversalData &s = tStack.top();
1921           
1922                        node = s.mNode;
1923                        extp = s.mExitPoint;
1924                        maxt = s.mMaxT;
1925         
1926                        tStack.pop();
1927                }
1928        }
1929        return hits;
1930}
1931
1932
1933BspNode *VspBspTree::CollapseTree(BspNode *node)
1934{
1935    if (node->IsLeaf())
1936                return node;
1937
1938        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1939
1940        BspNode *front = CollapseTree(interior->GetFront());
1941        BspNode *back = CollapseTree(interior->GetBack());
1942
1943        if (front->IsLeaf() && back->IsLeaf())
1944        {
1945                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
1946                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
1947
1948                //-- collapse tree
1949                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
1950                {
1951                        BspViewCell *vc = frontLeaf->GetViewCell();
1952
1953                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
1954                       
1955                        // replace a link from node's parent
1956                        if (leaf->GetParent())
1957                                leaf->GetParent()->ReplaceChildLink(node, leaf);
1958
1959                        delete interior;
1960
1961                        return leaf;
1962                }
1963        }
1964
1965        return node;
1966}
1967
1968
1969void VspBspTree::RepairVcLeafLists()
1970{
1971        // list not valid anymore => clear
1972        stack<BspNode *> nodeStack;
1973        nodeStack.push(mRoot);
1974
1975        ViewCell::NewMail();
1976
1977        while (!nodeStack.empty())
1978        {
1979                BspNode *node = nodeStack.top();
1980                nodeStack.pop();
1981
1982                if (node->IsLeaf())
1983                {
1984                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1985
1986                        BspViewCell *viewCell = leaf->GetViewCell();
1987
1988                        if (!viewCell->Mailed())
1989                        {
1990                                viewCell->mLeaves.clear();
1991                                viewCell->Mail();
1992                        }
1993
1994                        viewCell->mLeaves.push_back(leaf);
1995                }
1996                else
1997                {
1998                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1999
2000                        nodeStack.push(interior->GetFront());
2001                        nodeStack.push(interior->GetBack());
2002                }
2003        }
2004}
2005
2006
2007int VspBspTree::MergeLeaves()
2008{
2009        vector<BspLeaf *> leaves;
2010        priority_queue<BspMergeCandidate> mergeQueue;
2011
2012        // collect the leaves, e.g., the "voxels" that will build the view cells
2013        CollectLeaves(leaves);
2014
2015        int vcSize = (int)leaves.size();
2016        int savedVcSize = vcSize;
2017
2018        BspLeaf::NewMail();
2019
2020        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2021
2022        // find merge candidates and push them into queue
2023        for (it = leaves.begin(); it != it_end; ++ it)
2024        {
2025                BspLeaf *leaf = *it;
2026
2027                // no leaf is part of two merge candidates
2028                if (!leaf->Mailed())
2029                {
2030                        leaf->Mail();
2031
2032                        vector<BspLeaf *> neighbors;
2033                        FindNeighbors(leaf, neighbors, true);
2034
2035                        vector<BspLeaf *>::const_iterator nit,
2036                                nit_end = neighbors.end();
2037
2038                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2039                        {
2040                                BspMergeCandidate mc = BspMergeCandidate(leaf, *nit);
2041                                mergeQueue.push(mc);
2042
2043                                BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
2044                                BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
2045                        }
2046                }
2047        }
2048
2049        int merged = 0;
2050
2051        //-- use priority queue to merge leaf pairs
2052        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
2053                   (mergeQueue.top().GetMergeCost() <
2054                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2055        {
2056                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
2057                BspMergeCandidate mc = mergeQueue.top();
2058                mergeQueue.pop();
2059
2060                // both view cells equal!
2061                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2062                        continue;
2063
2064                if (mc.Valid())
2065                {
2066                        ViewCell::NewMail();
2067                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2068
2069                        ++ merged;
2070                        -- vcSize;
2071                        // increase absolute merge cost
2072                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2073                }
2074                // merge candidate not valid, because one of the leaves was already
2075                // merged with another one
2076                else
2077                {
2078                        // validate and reinsert into queue
2079                        mc.SetValid();
2080                        mergeQueue.push(mc);
2081                        //Debug << "validate " << mc.GetMergeCost() << endl;
2082                }
2083        }
2084
2085        // collapse tree according to view cell partition
2086        CollapseTree(mRoot);
2087        // revalidate leaves
2088        RepairVcLeafLists();
2089
2090        //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
2091
2092        //TODO: should return sample contributions
2093        return merged;
2094}
2095
2096
2097bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2)
2098{
2099        //-- change pointer to view cells of all leaves associated
2100        //-- with the previous view cells
2101        BspViewCell *fVc = l1->GetViewCell();
2102        BspViewCell *bVc = l2->GetViewCell();
2103
2104        BspViewCell *vc = dynamic_cast<BspViewCell *>(
2105                mViewCellsManager->MergeViewCells(*fVc, *bVc));
2106
2107        // if merge was unsuccessful
2108        if (!vc) return false;
2109
2110        // set new size of view cell
2111        vc->SetArea(fVc->GetArea() + bVc->GetArea());
2112
2113        vector<BspLeaf *> fLeaves = fVc->mLeaves;
2114        vector<BspLeaf *> bLeaves = bVc->mLeaves;
2115
2116        vector<BspLeaf *>::const_iterator it;
2117
2118        //-- change view cells of all the other leaves the view cell belongs to
2119        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2120        {
2121                (*it)->SetViewCell(vc);
2122                vc->mLeaves.push_back(*it);
2123        }
2124
2125        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2126        {
2127                (*it)->SetViewCell(vc);
2128                vc->mLeaves.push_back(*it);
2129        }
2130
2131        vc->Mail();
2132
2133        // clean up old view cells
2134        DEL_PTR(fVc);
2135        DEL_PTR(bVc);
2136
2137        return true;
2138}
2139
2140
2141void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2142{
2143        mViewCellsManager = vcm;
2144}
2145
2146/************************************************************************/
2147/*                BspMergeCandidate implementation                      */
2148/************************************************************************/
2149
2150
2151BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
2152mMergeCost(0),
2153mLeaf1(l1),
2154mLeaf2(l2),
2155mLeaf1Id(l1->GetViewCell()->mMailbox),
2156mLeaf2Id(l2->GetViewCell()->mMailbox)
2157{
2158        EvalMergeCost();
2159}
2160
2161float BspMergeCandidate::GetLeaf1Cost() const
2162{
2163        BspViewCell *vc = mLeaf1->GetViewCell();
2164        return vc->GetPvs().GetSize() * vc->GetArea();
2165}
2166
2167float BspMergeCandidate::GetLeaf2Cost() const
2168{
2169        BspViewCell *vc = mLeaf2->GetViewCell();
2170        return vc->GetPvs().GetSize() * vc->GetVolume();
2171}
2172
2173void BspMergeCandidate::EvalMergeCost()
2174{
2175        //-- compute pvs difference
2176        BspViewCell *vc1 = mLeaf1->GetViewCell();
2177        BspViewCell *vc2 = mLeaf2->GetViewCell();
2178
2179        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
2180        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
2181
2182        //-- compute ratio of old cost
2183        //-- (added size of left and right view cell times pvs size)
2184        //-- to new rendering cost (size of merged view cell times pvs size)
2185        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
2186       
2187        const float newCost =
2188                (float)vcPvs * (vc1->GetArea() + vc2->GetArea());
2189
2190        mMergeCost = newCost - oldCost;
2191
2192//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
2193//              mMergeCost += 1.0;
2194}
2195
2196void BspMergeCandidate::SetLeaf1(BspLeaf *l)
2197{
2198        mLeaf1 = l;
2199}
2200
2201void BspMergeCandidate::SetLeaf2(BspLeaf *l)
2202{
2203        mLeaf2 = l;
2204}
2205
2206BspLeaf *BspMergeCandidate::GetLeaf1()
2207{
2208        return mLeaf1;
2209}
2210
2211BspLeaf *BspMergeCandidate::GetLeaf2()
2212{
2213        return mLeaf2;
2214}
2215
2216bool BspMergeCandidate::Valid() const
2217{
2218        return
2219                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
2220                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
2221}
2222
2223float BspMergeCandidate::GetMergeCost() const
2224{
2225        return mMergeCost;
2226}
2227
2228void BspMergeCandidate::SetValid()
2229{
2230        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
2231        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
2232
2233        EvalMergeCost();
2234}
Note: See TracBrowser for help on using the repository browser.