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

Revision 484, 53.9 KB checked in by mattausch, 19 years ago (diff)

work around preprocessor bug

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),
47mOnlyDrivingAxis(false)
48{
49        mRootCell = new BspViewCell();
50
51        Randomize(); // initialise random generator for heuristics
52
53        //-- termination criteria for autopartition
54        environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
55        environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
56        environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
57        environment->GetFloatValue("VspBspTree.Termination.minArea", mTermMinArea);
58        environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
59        environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
60        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
61        environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
62
63        //-- factors for bsp tree split plane heuristics
64        environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
65        environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
66        environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
67
68        //-- max cost ratio for early tree termination
69        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
70
71        //-- partition criteria
72        environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
73        environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
74        environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
75
76        environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
77        environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
78
79        // maximum and minimum number of view cells
80        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
81        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
82        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
83
84
85        //-- debug output
86        Debug << "******* VSP BSP options ******** " << endl;
87    Debug << "max depth: " << mTermMaxDepth << endl;
88        Debug << "min PVS: " << mTermMinPvs << endl;
89        Debug << "min area: " << mTermMinArea << endl;
90        Debug << "min rays: " << mTermMinRays << endl;
91        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
92        //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
93        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
94        Debug << "miss tolerance: " << mTermMissTolerance << endl;
95        Debug << "max view cells: " << mMaxViewCells << endl;
96        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
97        Debug << "max plane candidates: " << mMaxRayCandidates << endl;
98
99        Debug << "Split plane strategy: ";
100        if (mSplitPlaneStrategy & RANDOM_POLYGON)
101        {
102                Debug << "random polygon ";
103        }
104        if (mSplitPlaneStrategy & AXIS_ALIGNED)
105        {
106                Debug << "axis aligned ";
107        }
108        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
109        {
110                mCostNormalizer += mLeastRaySplitsFactor;
111                Debug << "least ray splits ";
112        }
113        if (mSplitPlaneStrategy & BALANCED_RAYS)
114        {
115                mCostNormalizer += mBalancedRaysFactor;
116                Debug << "balanced rays ";
117        }
118        if (mSplitPlaneStrategy & PVS)
119        {
120                mCostNormalizer += mPvsFactor;
121                Debug << "pvs";
122        }
123
124        mSplitCandidates = new vector<SortableEntry>;
125
126        Debug << endl;
127}
128
129
130const BspTreeStatistics &VspBspTree::GetStatistics() const
131{
132        return mStat;
133}
134
135
136VspBspTree::~VspBspTree()
137{
138        DEL_PTR(mRoot);
139        DEL_PTR(mRootCell);
140        DEL_PTR(mSplitCandidates);
141}
142
143int VspBspTree::AddMeshToPolygons(Mesh *mesh,
144                                                                  PolygonContainer &polys,
145                                                                  MeshInstance *parent)
146{
147        FaceContainer::const_iterator fi;
148
149        // copy the face data to polygons
150        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
151        {
152                Polygon3 *poly = new Polygon3((*fi), mesh);
153
154                if (poly->Valid(mEpsilon))
155                {
156                        poly->mParent = parent; // set parent intersectable
157                        polys.push_back(poly);
158                }
159                else
160                        DEL_PTR(poly);
161        }
162        return (int)mesh->mFaces.size();
163}
164
165int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
166                                                          PolygonContainer &polys,
167                                                          int maxObjects)
168{
169        int limit = (maxObjects > 0) ?
170                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
171
172        int polysSize = 0;
173
174        for (int i = 0; i < limit; ++ i)
175        {
176                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
177                {
178                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
179                        polysSize +=
180                                AddMeshToPolygons(viewCells[i]->GetMesh(),
181                                                                  polys,
182                                                                  viewCells[i]);
183                }
184        }
185
186        return polysSize;
187}
188
189int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
190                                                                 PolygonContainer &polys,
191                                                                 int maxObjects)
192{
193        int limit = (maxObjects > 0) ?
194                Min((int)objects.size(), maxObjects) : (int)objects.size();
195
196        for (int i = 0; i < limit; ++i)
197        {
198                Intersectable *object = objects[i];//*it;
199                Mesh *mesh = NULL;
200
201                switch (object->Type()) // extract the meshes
202                {
203                case Intersectable::MESH_INSTANCE:
204                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
205                        break;
206                case Intersectable::VIEW_CELL:
207                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
208                        break;
209                        // TODO: handle transformed mesh instances
210                default:
211                        Debug << "intersectable type not supported" << endl;
212                        break;
213                }
214
215        if (mesh) // copy the mesh data to polygons
216                {
217                        mBox.Include(object->GetBox()); // add to BSP tree aabb
218                        AddMeshToPolygons(mesh, polys, mRootCell);
219                }
220        }
221
222        return (int)polys.size();
223}
224
225void VspBspTree::Construct(const VssRayContainer &sampleRays,
226                                                   AxisAlignedBox3 *forcedBoundingBox)
227{
228    mStat.nodes = 1;
229        mBox.Initialize();      // initialise BSP tree bounding box
230
231        if (forcedBoundingBox)
232                mBox = *forcedBoundingBox;
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 ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
251                        ray->mTerminationObject &&
252                        !ray->mTerminationObject->Mailed())
253                {
254                        ray->mTerminationObject->Mail();
255                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
256                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
257                        //-- compute bounding box
258                        if (!forcedBoundingBox)
259                                mBox.Include(ray->mTermination);
260                }
261
262                if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
263                        ray->mOriginObject &&
264                        !ray->mOriginObject->Mailed())
265                {
266                        ray->mOriginObject->Mail();
267                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
268                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
269                        //-- compute bounding box
270                        if (!forcedBoundingBox)
271                                mBox.Include(ray->mOrigin);
272                }
273        }
274
275        //-- compute bounding box
276        //if (!forcedBoundingBox) Polygon3::IncludeInBox(polys, mBox);
277
278        //-- store rays
279        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
280        {
281                VssRay *ray = *rit;
282
283                float minT, maxT;
284
285                // TODO: not very efficient to implictly cast between rays types
286                if (mBox.GetRaySegment(*ray, minT, maxT))
287                {
288                        float len = ray->Length();
289
290                        if (!len)
291                                len = Limits::Small;
292
293                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
294                }
295        }
296
297        mTermMinArea *= mBox.SurfaceArea(); // normalize
298        mStat.polys = (int)polys.size();
299
300        cout << "finished" << endl;
301
302        Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
303                  << (int)sampleRays.size() << " rays in "
304                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
305
306        Construct(polys, rays);
307
308        // clean up polygons
309        CLEAR_CONTAINER(polys);
310}
311
312void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
313{
314        VspBspTraversalStack tStack;
315
316        mRoot = new BspLeaf();
317
318        // constrruct root node geometry
319        BspNodeGeometry *geom = new BspNodeGeometry();
320        ConstructGeometry(mRoot, *geom);
321
322        VspBspTraversalData tData(mRoot,
323                                                          new PolygonContainer(polys),
324                                                          0,
325                                                          rays,
326                              ComputePvsSize(*rays),
327                                                          geom->GetArea(),
328                                                          geom);
329
330        tStack.push(tData);
331
332        mStat.Start();
333        cout << "Contructing vsp bsp tree ... ";
334
335        long startTime = GetTime();
336
337        while (!tStack.empty())
338        {
339                tData = tStack.top();
340
341            tStack.pop();
342
343                // subdivide leaf node
344                BspNode *r = Subdivide(tStack, tData);
345
346                if (r == mRoot)
347                        Debug << "VSP BSP tree construction time spent at root: "
348                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl << endl;
349        }
350
351        cout << "finished\n";
352
353        mStat.Stop();
354}
355
356bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
357{
358        return
359                (((int)data.mRays->size() <= mTermMinRays) ||
360                 (data.mPvs <= mTermMinPvs)   ||
361                 (data.mArea <= mTermMinArea) ||
362                 (mStat.nodes / 2 + 1 >= mMaxViewCells) ||
363                // (data.GetAvgRayContribution() >= mTermMaxRayContribution) ||
364                 (data.mDepth >= mTermMaxDepth));
365}
366
367BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
368                                                           VspBspTraversalData &tData)
369{
370        BspNode *newNode = tData.mNode;
371
372        if (!TerminationCriteriaMet(tData))
373        {
374                PolygonContainer coincident;
375
376                VspBspTraversalData tFrontData;
377                VspBspTraversalData tBackData;
378
379                // create new interior node and two leaf nodes
380                // or return leaf as it is (if maxCostRatio missed)
381                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
382
383                if (!newNode->IsLeaf()) //-- continue subdivision
384                {
385                        // push the children on the stack
386                        tStack.push(tFrontData);
387                        tStack.push(tBackData);
388
389                        // delete old leaf node
390                        DEL_PTR(tData.mNode);
391                }
392        }
393
394        //-- terminate traversal and create new view cell
395        if (newNode->IsLeaf())
396        {
397                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
398
399                // create new view cell for this leaf
400                BspViewCell *viewCell = new BspViewCell();
401                leaf->SetViewCell(viewCell);
402
403                if (mStoreRays)
404                {
405                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
406                        for (it = tData.mRays->begin(); it != it_end; ++ it)
407                                leaf->mVssRays.push_back((*it).mRay);
408                }
409
410                viewCell->mLeaves.push_back(leaf);
411                viewCell->SetArea(tData.mArea);
412
413                //-- update pvs
414                int conSamp = 0, sampCon = 0;
415                AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
416
417                mStat.contributingSamples += conSamp;
418                mStat.sampleContributions += sampCon;
419
420                EvaluateLeafStats(tData);
421        }
422
423
424        //-- cleanup
425        tData.Clear();
426
427        return newNode;
428}
429
430BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
431                                                                   VspBspTraversalData &frontData,
432                                                                   VspBspTraversalData &backData,
433                                                                   PolygonContainer &coincident)
434{
435        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
436
437        int maxCostMisses = tData.mMaxCostMisses;
438
439        // select subdivision plane
440        Plane3 splitPlane;
441        if (!SelectPlane(splitPlane, leaf, tData))
442        {
443                ++ maxCostMisses;
444
445                if (maxCostMisses > mTermMissTolerance)
446                {
447                        // terminate branch because of max cost
448                        ++ mStat.maxCostNodes;
449            return leaf;
450                }
451        }
452
453        mStat.nodes += 2;
454
455        //-- subdivide further
456        BspInterior *interior = new BspInterior(splitPlane);
457
458#ifdef _DEBUG
459        Debug << interior << endl;
460#endif
461
462        //-- the front and back traversal data is filled with the new values
463        frontData.mPolygons = new PolygonContainer();
464        frontData.mDepth = tData.mDepth + 1;
465        frontData.mRays = new RayInfoContainer();
466        frontData.mGeometry = new BspNodeGeometry();
467
468        backData.mPolygons = new PolygonContainer();
469        backData.mDepth = tData.mDepth + 1;
470        backData.mRays = new RayInfoContainer();
471        backData.mGeometry = new BspNodeGeometry();
472
473        // subdivide rays
474        SplitRays(interior->GetPlane(),
475                          *tData.mRays,
476                          *frontData.mRays,
477                          *backData.mRays);
478
479        // subdivide polygons
480        mStat.splits += SplitPolygons(interior->GetPlane(),
481                                                                  *tData.mPolygons,
482                                          *frontData.mPolygons,
483                                                                  *backData.mPolygons,
484                                                                  coincident);
485
486
487        // how often was max cost ratio missed in this branch?
488        frontData.mMaxCostMisses = maxCostMisses;
489        backData.mMaxCostMisses = maxCostMisses;
490
491        // compute pvs
492        frontData.mPvs = ComputePvsSize(*frontData.mRays);
493        backData.mPvs = ComputePvsSize(*backData.mRays);
494
495        // split geometry and compute area
496        if (1)
497        {
498                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
499                                                                           *backData.mGeometry,
500                                                                           interior->GetPlane(),
501                                                                           mBox,
502                                                                           mEpsilon);
503
504                frontData.mArea = frontData.mGeometry->GetArea();
505                backData.mArea = backData.mGeometry->GetArea();
506        }
507
508        // compute accumulated ray length
509        //frontData.mAccRayLength = AccumulatedRayLength(*frontData.mRays);
510        //backData.mAccRayLength = AccumulatedRayLength(*backData.mRays);
511
512        //-- create front and back leaf
513
514        BspInterior *parent = leaf->GetParent();
515
516        // replace a link from node's parent
517        if (!leaf->IsRoot())
518        {
519                parent->ReplaceChildLink(leaf, interior);
520                interior->SetParent(parent);
521        }
522        else // new root
523        {
524                mRoot = interior;
525        }
526
527        // and setup child links
528        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
529
530        frontData.mNode = interior->GetFront();
531        backData.mNode = interior->GetBack();
532
533        //DEL_PTR(leaf);
534        return interior;
535}
536
537void VspBspTree::AddToPvs(BspLeaf *leaf,
538                                                  const RayInfoContainer &rays,
539                                                  int &sampleContributions,
540                                                  int &contributingSamples)
541{
542        sampleContributions = 0;
543        contributingSamples = 0;
544
545    RayInfoContainer::const_iterator it, it_end = rays.end();
546
547        ViewCell *vc = leaf->GetViewCell();
548
549        // add contributions from samples to the PVS
550        for (it = rays.begin(); it != it_end; ++ it)
551        {
552                int contribution = 0;
553                VssRay *ray = (*it).mRay;
554
555                if (ray->mTerminationObject)
556                        contribution += vc->GetPvs().AddSample(ray->mTerminationObject);
557
558                if (ray->mOriginObject)
559                        contribution += vc->GetPvs().AddSample(ray->mOriginObject);
560
561                if (contribution)
562                {
563                        sampleContributions += contribution;
564                        ++ contributingSamples;
565                }
566                //leaf->mVssRays.push_back(ray);
567        }
568}
569
570void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
571{
572        mSplitCandidates->clear();
573
574        int requestedSize = 2 * (int)(rays.size());
575        // creates a sorted split candidates array
576        if (mSplitCandidates->capacity() > 500000 &&
577                requestedSize < (int)(mSplitCandidates->capacity()/10) )
578        {
579        delete mSplitCandidates;
580                mSplitCandidates = new vector<SortableEntry>;
581        }
582
583        mSplitCandidates->reserve(requestedSize);
584
585        // insert all queries
586        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
587        {
588                bool positive = (*ri).mRay->HasPosDir(axis);
589                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
590                                                                                                  (*ri).ExtrapOrigin(axis), (*ri).mRay));
591
592                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
593                                                                                                  (*ri).ExtrapTermination(axis), (*ri).mRay));
594        }
595
596        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
597}
598
599float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
600                                                                                  const AxisAlignedBox3 &box,
601                                                                                  const int pvsSize,
602                                                                                  const int &axis,
603                                          float &position)
604{
605        int raysBack;
606        int raysFront;
607        int pvsBack;
608        int pvsFront;
609
610        SortSplitCandidates(rays, axis);
611
612        // go through the lists, count the number of objects left and right
613        // and evaluate the following cost funcion:
614        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
615
616        int rl = 0, rr = (int)rays.size();
617        int pl = 0, pr = pvsSize;
618
619        float minBox = box.Min(axis);
620        float maxBox = box.Max(axis);
621        float sizeBox = maxBox - minBox;
622
623        float minBand = minBox + 0.1f*(maxBox - minBox);
624        float maxBand = minBox + 0.9f*(maxBox - minBox);
625
626        float sum = rr*sizeBox;
627        float minSum = 1e20f;
628
629        Intersectable::NewMail();
630
631        // set all object as belonging to the fron pvs
632        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
633        {
634                if ((*ri).mRay->IsActive())
635                {
636                        Intersectable *object = (*ri).mRay->mTerminationObject;
637
638                        if (object)
639                        {
640                                if (!object->Mailed())
641                                {
642                                        object->Mail();
643                                        object->mCounter = 1;
644                                }
645                                else
646                                        ++ object->mCounter;
647                        }
648                }
649        }
650
651        Intersectable::NewMail();
652
653        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
654                ci < mSplitCandidates->end(); ++ ci)
655        {
656                VssRay *ray;
657
658                switch ((*ci).type)
659                {
660                        case SortableEntry::ERayMin:
661                                {
662                                        ++ rl;
663                                        ray = (VssRay *) (*ci).ray;
664
665                                        Intersectable *object = ray->mTerminationObject;
666
667                                        if (object && !object->Mailed())
668                                        {
669                                                object->Mail();
670                                                ++ pl;
671                                        }
672                                        break;
673                                }
674                        case SortableEntry::ERayMax:
675                                {
676                                        -- rr;
677                                        ray = (VssRay *) (*ci).ray;
678
679                                        Intersectable *object = ray->mTerminationObject;
680
681                                        if (object)
682                                        {
683                                                if (-- object->mCounter == 0)
684                                                        -- pr;
685                                        }
686
687                                        break;
688                                }
689                }
690
691                // Note: sufficient to compare size of bounding boxes of front and back side?
692                if ((*ci).value > minBand && (*ci).value < maxBand)
693                {
694                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
695
696                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
697                        // cout<<"cost= "<<sum<<endl;
698
699                        if (sum < minSum)
700                        {
701                                minSum = sum;
702                                position = (*ci).value;
703
704                                raysBack = rl;
705                                raysFront = rr;
706
707                                pvsBack = pl;
708                                pvsFront = pr;
709
710                        }
711                }
712        }
713
714        float oldCost = (float)pvsSize;
715        float newCost = mCtDivCi + minSum / sizeBox;
716        float ratio = newCost / oldCost;
717
718        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
719        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
720
721        return ratio;
722}
723
724
725float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
726                                                                                 const VspBspTraversalData &tData)
727{
728        AxisAlignedBox3 box;
729        box.Initialize();
730
731        // create bounding box of region
732        RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
733
734        for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
735                box.Include((*ri).ExtrapTermination());
736
737        const bool useCostHeuristics = false;
738
739        //-- regular split
740        float nPosition[3];
741        float nCostRatio[3];
742        int bestAxis = -1;
743
744        const int sAxis = box.Size().DrivingAxis();
745
746        for (int axis = 0; axis < 3; ++ axis)
747        {
748                if (!mOnlyDrivingAxis || axis == sAxis)
749                {
750                        if (!useCostHeuristics)
751                        {
752                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
753                                Vector3 normal(0,0,0); normal[axis] = 1;
754
755                                nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), tData);
756                        }
757                        else
758                        {
759                                nCostRatio[axis] =
760                                        BestCostRatioHeuristics(*tData.mRays,
761                                                                                    box,
762                                                                                        tData.mPvs,
763                                                                                        axis,
764                                                                                        nPosition[axis]);
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
1410float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1411{
1412        float len = 0;
1413
1414        RayInfoContainer::const_iterator it, it_end = rays.end();
1415
1416        for (it = rays.begin(); it != it_end; ++ it)
1417                len += (*it).SegmentLength();
1418
1419        return len;
1420}
1421
1422
1423int VspBspTree::SplitRays(const Plane3 &plane,
1424                                                  RayInfoContainer &rays,
1425                                                  RayInfoContainer &frontRays,
1426                                                  RayInfoContainer &backRays)
1427{
1428        int splits = 0;
1429
1430        while (!rays.empty())
1431        {
1432                RayInfo bRay = rays.back();
1433                rays.pop_back();
1434
1435                VssRay *ray = bRay.mRay;
1436                float t;
1437
1438                        // get classification and receive new t
1439                const int cf = bRay.ComputeRayIntersection(plane, t);
1440
1441                switch (cf)
1442                {
1443                case -1:
1444                        backRays.push_back(bRay);
1445                        break;
1446                case 1:
1447                        frontRays.push_back(bRay);
1448                        break;
1449                case 0:
1450                        //-- split ray
1451                        //--  look if start point behind or in front of plane
1452                        if (plane.Side(bRay.ExtrapOrigin()) <= 0)
1453                        {
1454                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1455                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1456                        }
1457                        else
1458                        {
1459                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1460                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1461                        }
1462                        break;
1463                default:
1464                        Debug << "Should not come here 4" << endl;
1465                        break;
1466                }
1467        }
1468
1469        return splits;
1470}
1471
1472
1473void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1474{
1475        BspNode *lastNode;
1476
1477        do
1478        {
1479                lastNode = n;
1480
1481                // want to get planes defining geometry of this node => don't take
1482                // split plane of node itself
1483                n = n->GetParent();
1484
1485                if (n)
1486                {
1487                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
1488                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1489
1490            if (interior->GetFront() != lastNode)
1491                                halfSpace.ReverseOrientation();
1492
1493                        halfSpaces.push_back(halfSpace);
1494                }
1495        }
1496        while (n);
1497}
1498
1499void VspBspTree::ConstructGeometry(BspNode *n,
1500                                                                   BspNodeGeometry &cell) const
1501{
1502        PolygonContainer polys;
1503        ConstructGeometry(n, polys);
1504        cell.mPolys = polys;
1505}
1506
1507void VspBspTree::ConstructGeometry(BspNode *n,
1508                                                                   PolygonContainer &cell) const
1509{
1510        vector<Plane3> halfSpaces;
1511        ExtractHalfSpaces(n, halfSpaces);
1512
1513        PolygonContainer candidatePolys;
1514
1515        // bounded planes are added to the polygons (reverse polygons
1516        // as they have to be outfacing
1517        for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1518        {
1519                Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1520
1521                if (p->Valid(mEpsilon))
1522                {
1523                        candidatePolys.push_back(p->CreateReversePolygon());
1524                        DEL_PTR(p);
1525                }
1526        }
1527
1528        // add faces of bounding box (also could be faces of the cell)
1529        for (int i = 0; i < 6; ++ i)
1530        {
1531                VertexContainer vertices;
1532
1533                for (int j = 0; j < 4; ++ j)
1534                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
1535
1536                candidatePolys.push_back(new Polygon3(vertices));
1537        }
1538
1539        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
1540        {
1541                // polygon is split by all other planes
1542                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
1543                {
1544                        if (i == j) // polygon and plane are coincident
1545                                continue;
1546
1547                        VertexContainer splitPts;
1548                        Polygon3 *frontPoly, *backPoly;
1549
1550                        const int cf =
1551                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
1552                                                                                                 mEpsilon);
1553
1554                        switch (cf)
1555                        {
1556                                case Polygon3::SPLIT:
1557                                        frontPoly = new Polygon3();
1558                                        backPoly = new Polygon3();
1559
1560                                        candidatePolys[i]->Split(halfSpaces[j],
1561                                                                                         *frontPoly,
1562                                                                                         *backPoly,
1563                                                                                         mEpsilon);
1564
1565                                        DEL_PTR(candidatePolys[i]);
1566
1567                                        if (frontPoly->Valid(mEpsilon))
1568                                                candidatePolys[i] = frontPoly;
1569                                        else
1570                                                DEL_PTR(frontPoly);
1571
1572                                        DEL_PTR(backPoly);
1573                                        break;
1574                                case Polygon3::BACK_SIDE:
1575                                        DEL_PTR(candidatePolys[i]);
1576                                        break;
1577                                // just take polygon as it is
1578                                case Polygon3::FRONT_SIDE:
1579                                case Polygon3::COINCIDENT:
1580                                default:
1581                                        break;
1582                        }
1583                }
1584
1585                if (candidatePolys[i])
1586                        cell.push_back(candidatePolys[i]);
1587        }
1588}
1589
1590void VspBspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &vcGeom) const
1591{
1592        vector<BspLeaf *> leaves = vc->mLeaves;
1593
1594        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
1595
1596        for (it = leaves.begin(); it != it_end; ++ it)
1597                ConstructGeometry(*it, vcGeom);
1598}
1599
1600int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
1601                                                   const bool onlyUnmailed) const
1602{
1603        PolygonContainer cell;
1604
1605        ConstructGeometry(n, cell);
1606
1607        stack<BspNode *> nodeStack;
1608        nodeStack.push(mRoot);
1609
1610        // planes needed to verify that we found neighbor leaf.
1611        vector<Plane3> halfSpaces;
1612        ExtractHalfSpaces(n, halfSpaces);
1613
1614        while (!nodeStack.empty())
1615        {
1616                BspNode *node = nodeStack.top();
1617                nodeStack.pop();
1618
1619                if (node->IsLeaf())
1620                {
1621            if (node != n && (!onlyUnmailed || !node->Mailed()))
1622                        {
1623                                // test all planes of current node if candidate really
1624                                // is neighbour
1625                                PolygonContainer neighborCandidate;
1626                                ConstructGeometry(node, neighborCandidate);
1627
1628                                bool isAdjacent = true;
1629                                for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
1630                                {
1631                                        const int cf =
1632                                                Polygon3::ClassifyPlane(neighborCandidate,
1633                                                                                                halfSpaces[i],
1634                                                                                                mEpsilon);
1635
1636                                        if (cf == Polygon3::BACK_SIDE)
1637                                                isAdjacent = false;
1638                                }
1639
1640                                if (isAdjacent)
1641                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
1642
1643                                CLEAR_CONTAINER(neighborCandidate);
1644                        }
1645                }
1646                else
1647                {
1648                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1649
1650                        const int cf = Polygon3::ClassifyPlane(cell,
1651                                                                                                   interior->GetPlane(),
1652                                                                                                   mEpsilon);
1653
1654                        if (cf == Polygon3::FRONT_SIDE)
1655                                nodeStack.push(interior->GetFront());
1656                        else
1657                                if (cf == Polygon3::BACK_SIDE)
1658                                        nodeStack.push(interior->GetBack());
1659                                else
1660                                {
1661                                        // random decision
1662                                        nodeStack.push(interior->GetBack());
1663                                        nodeStack.push(interior->GetFront());
1664                                }
1665                }
1666        }
1667
1668        CLEAR_CONTAINER(cell);
1669        return (int)neighbors.size();
1670}
1671
1672BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
1673{
1674    stack<BspNode *> nodeStack;
1675        nodeStack.push(mRoot);
1676
1677        int mask = rand();
1678
1679        while (!nodeStack.empty())
1680        {
1681                BspNode *node = nodeStack.top();
1682                nodeStack.pop();
1683
1684                if (node->IsLeaf())
1685                {
1686                        return dynamic_cast<BspLeaf *>(node);
1687                }
1688                else
1689                {
1690                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1691
1692                        BspNode *next;
1693
1694                        PolygonContainer cell;
1695
1696                        // todo: not very efficient: constructs full cell everytime
1697                        ConstructGeometry(interior, cell);
1698
1699                        const int cf = Polygon3::ClassifyPlane(cell, halfspace, mEpsilon);
1700
1701                        if (cf == Polygon3::BACK_SIDE)
1702                                next = interior->GetFront();
1703                        else
1704                                if (cf == Polygon3::FRONT_SIDE)
1705                                        next = interior->GetFront();
1706                        else
1707                        {
1708                                // random decision
1709                                if (mask & 1)
1710                                        next = interior->GetBack();
1711                                else
1712                                        next = interior->GetFront();
1713                                mask = mask >> 1;
1714                        }
1715
1716                        nodeStack.push(next);
1717                }
1718        }
1719
1720        return NULL;
1721}
1722
1723BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
1724{
1725        stack<BspNode *> nodeStack;
1726
1727        nodeStack.push(mRoot);
1728
1729        int mask = rand();
1730
1731        while (!nodeStack.empty())
1732        {
1733                BspNode *node = nodeStack.top();
1734                nodeStack.pop();
1735
1736                if (node->IsLeaf())
1737                {
1738                        if ( (!onlyUnmailed || !node->Mailed()) )
1739                                return dynamic_cast<BspLeaf *>(node);
1740                }
1741                else
1742                {
1743                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1744
1745                        // random decision
1746                        if (mask & 1)
1747                                nodeStack.push(interior->GetBack());
1748                        else
1749                                nodeStack.push(interior->GetFront());
1750
1751                        mask = mask >> 1;
1752                }
1753        }
1754
1755        return NULL;
1756}
1757
1758int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
1759{
1760        int pvsSize = 0;
1761
1762        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1763
1764        Intersectable::NewMail();
1765
1766        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1767        {
1768                VssRay *ray = (*rit).mRay;
1769
1770                if (ray->mOriginObject)
1771                {
1772                        if (!ray->mOriginObject->Mailed())
1773                        {
1774                                ray->mOriginObject->Mail();
1775                                ++ pvsSize;
1776                        }
1777                }
1778                if (ray->mTerminationObject)
1779                {
1780                        if (!ray->mTerminationObject->Mailed())
1781                        {
1782                                ray->mTerminationObject->Mail();
1783                                ++ pvsSize;
1784                        }
1785                }
1786        }
1787
1788        return pvsSize;
1789}
1790
1791float VspBspTree::GetEpsilon() const
1792{
1793        return mEpsilon;
1794}
1795
1796BspViewCell *VspBspTree::GetRootCell() const
1797{
1798        return mRootCell;
1799}
1800
1801int VspBspTree::SplitPolygons(const Plane3 &plane,
1802                                                          PolygonContainer &polys,
1803                                                          PolygonContainer &frontPolys,
1804                                                          PolygonContainer &backPolys,
1805                                                          PolygonContainer &coincident) const
1806{
1807        int splits = 0;
1808
1809        while (!polys.empty())
1810        {
1811                Polygon3 *poly = polys.back();
1812                polys.pop_back();
1813
1814                // classify polygon
1815                const int cf = poly->ClassifyPlane(plane, mEpsilon);
1816
1817                switch (cf)
1818                {
1819                        case Polygon3::COINCIDENT:
1820                                coincident.push_back(poly);
1821                                break;
1822                        case Polygon3::FRONT_SIDE:
1823                                frontPolys.push_back(poly);
1824                                break;
1825                        case Polygon3::BACK_SIDE:
1826                                backPolys.push_back(poly);
1827                                break;
1828                        case Polygon3::SPLIT:
1829                                backPolys.push_back(poly);
1830                                frontPolys.push_back(poly);
1831                                ++ splits;
1832                                break;
1833                        default:
1834                Debug << "SHOULD NEVER COME HERE\n";
1835                                break;
1836                }
1837        }
1838
1839        return splits;
1840}
1841
1842
1843int VspBspTree::CastLineSegment(const Vector3 &origin,
1844                                                                const Vector3 &termination,
1845                                                                vector<ViewCell *> &viewcells)
1846{
1847        int hits = 0;
1848        stack<BspRayTraversalData> tStack;
1849
1850        float mint = 0.0f, maxt = 1.0f;
1851
1852        Intersectable::NewMail();
1853
1854        Vector3 entp = origin;
1855        Vector3 extp = termination;
1856
1857        BspNode *node = mRoot;
1858        BspNode *farChild = NULL;
1859
1860        while (1)
1861        {
1862                if (!node->IsLeaf())
1863                {
1864                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1865
1866                        Plane3 splitPlane = in->GetPlane();
1867                        const int entSide = splitPlane.Side(entp);
1868                        const int extSide = splitPlane.Side(extp);
1869
1870                        if (entSide < 0)
1871                        {
1872                                node = in->GetBack();
1873
1874                                if (extSide <= 0) // plane does not split ray => no far child
1875                                        continue;
1876
1877                                farChild = in->GetFront(); // plane splits ray
1878                        } else if (entSide > 0)
1879                        {
1880                                node = in->GetFront();
1881
1882                                if (extSide >= 0) // plane does not split ray => no far child
1883                                        continue;
1884
1885                                farChild = in->GetBack(); // plane splits ray
1886                        }
1887                        else // ray and plane are coincident
1888                        {
1889                                // WHAT TO DO IN THIS CASE ?
1890                                //break;
1891                                node = in->GetFront();
1892                                continue;
1893                        }
1894
1895                        // push data for far child
1896                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1897
1898                        // find intersection of ray segment with plane
1899                        float t;
1900                        extp = splitPlane.FindIntersection(origin, extp, &t);
1901                        maxt *= t;
1902
1903                } else
1904                {
1905                        // reached leaf => intersection with view cell
1906                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1907
1908                        if (!leaf->GetViewCell()->Mailed())
1909                        {
1910                                viewcells.push_back(leaf->GetViewCell());
1911                                leaf->GetViewCell()->Mail();
1912                                ++ hits;
1913                        }
1914
1915                        //-- fetch the next far child from the stack
1916                        if (tStack.empty())
1917                                break;
1918
1919                        entp = extp;
1920                        mint = maxt; // NOTE: need this?
1921
1922
1923                        BspRayTraversalData &s = tStack.top();
1924
1925                        node = s.mNode;
1926                        extp = s.mExitPoint;
1927                        maxt = s.mMaxT;
1928
1929                        tStack.pop();
1930                }
1931        }
1932        return hits;
1933}
1934
1935int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2)
1936{
1937        std::deque<BspNode *> path1;
1938        BspNode *p1 = n1;
1939
1940        // create path from node 1 to root
1941        while (p1)
1942        {
1943                if (p1 == n2) // second node on path
1944                        return (int)path1.size();
1945
1946                path1.push_front(p1);
1947                p1 = p1->GetParent();
1948        }
1949
1950        int depth = n2->GetDepth();
1951        int d = depth;
1952
1953        BspNode *p2 = n2;
1954
1955        // compare with same depth
1956        while (1)
1957        {
1958                if ((d < (int)path1.size()) && (p2 == path1[d]))
1959                        return (depth - d) + ((int)path1.size() - 1 - d);
1960
1961                -- d;
1962                p2 = p2->GetParent();
1963        }
1964
1965        return 0; // never come here
1966}
1967
1968BspNode *VspBspTree::CollapseTree(BspNode *node)
1969{
1970    if (node->IsLeaf())
1971                return node;
1972
1973        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1974
1975        BspNode *front = CollapseTree(interior->GetFront());
1976        BspNode *back = CollapseTree(interior->GetBack());
1977
1978        if (front->IsLeaf() && back->IsLeaf())
1979        {
1980                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
1981                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
1982
1983                //-- collapse tree
1984                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
1985                {
1986                        BspViewCell *vc = frontLeaf->GetViewCell();
1987
1988                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
1989
1990                        // replace a link from node's parent
1991                        if (leaf->GetParent())
1992                                leaf->GetParent()->ReplaceChildLink(node, leaf);
1993
1994                        delete interior;
1995
1996                        return leaf;
1997                }
1998        }
1999
2000        return node;
2001}
2002
2003
2004void VspBspTree::RepairVcLeafLists()
2005{
2006        // list not valid anymore => clear
2007        stack<BspNode *> nodeStack;
2008        nodeStack.push(mRoot);
2009
2010        ViewCell::NewMail();
2011
2012        while (!nodeStack.empty())
2013        {
2014                BspNode *node = nodeStack.top();
2015                nodeStack.pop();
2016
2017                if (node->IsLeaf())
2018                {
2019                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2020
2021                        BspViewCell *viewCell = leaf->GetViewCell();
2022
2023                        if (!viewCell->Mailed())
2024                        {
2025                                viewCell->mLeaves.clear();
2026                                viewCell->Mail();
2027                        }
2028
2029                        viewCell->mLeaves.push_back(leaf);
2030                }
2031                else
2032                {
2033                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2034
2035                        nodeStack.push(interior->GetFront());
2036                        nodeStack.push(interior->GetBack());
2037                }
2038        }
2039}
2040
2041
2042int VspBspTree::MergeLeaves()
2043{
2044        vector<BspLeaf *> leaves;
2045        priority_queue<BspMergeCandidate> mergeQueue;
2046
2047        // collect the leaves, e.g., the "voxels" that will build the view cells
2048        CollectLeaves(leaves);
2049
2050        int vcSize = (int)leaves.size();
2051        int savedVcSize = vcSize;
2052
2053        BspLeaf::NewMail();
2054
2055        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2056
2057        // find merge candidates and push them into queue
2058        for (it = leaves.begin(); it != it_end; ++ it)
2059        {
2060                BspLeaf *leaf = *it;
2061
2062                // no leaf is part of two merge candidates
2063                if (!leaf->Mailed())
2064                {
2065                        leaf->Mail();
2066
2067                        vector<BspLeaf *> neighbors;
2068                        FindNeighbors(leaf, neighbors, true);
2069
2070                        vector<BspLeaf *>::const_iterator nit,
2071                                nit_end = neighbors.end();
2072
2073                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2074                        {
2075                                BspMergeCandidate mc = BspMergeCandidate(leaf, *nit);
2076                                mergeQueue.push(mc);
2077
2078                                BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
2079                                BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
2080                        }
2081                }
2082        }
2083
2084        int merged = 0;
2085        int mergedSiblings = 0;
2086        int accTreeDist = 0;
2087        int maxTreeDist = 0;
2088        const bool mergeStats = true;
2089
2090
2091        //-- use priority queue to merge leaf pairs
2092        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
2093                   (mergeQueue.top().GetMergeCost() <
2094                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2095        {
2096                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
2097                BspMergeCandidate mc = mergeQueue.top();
2098                mergeQueue.pop();
2099
2100                // both view cells equal!
2101                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2102                        continue;
2103
2104                if (mc.Valid())
2105                {
2106                        ViewCell::NewMail();
2107                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2108                        -- vcSize;
2109                        // increase absolute merge cost
2110                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2111
2112                        //-- stats
2113                        ++ merged;
2114
2115                        if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
2116                                ++ mergedSiblings;
2117
2118                        if (mergeStats)
2119                        {
2120                                const int dist = TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
2121
2122                                if (dist > maxTreeDist)
2123                                        maxTreeDist = dist;
2124
2125                                accTreeDist += dist;
2126                        }
2127                }
2128                // merge candidate not valid, because one of the leaves was already
2129                // merged with another one
2130                else
2131                {
2132                        // validate and reinsert into queue
2133                        mc.SetValid();
2134                        mergeQueue.push(mc);
2135                        //Debug << "validate " << mc.GetMergeCost() << endl;
2136                }
2137        }
2138
2139        // collapse tree according to view cell partition
2140        CollapseTree(mRoot);
2141        // revalidate leaves
2142        RepairVcLeafLists();
2143
2144        Debug << "Merged " << merged << " nodes of " << savedVcSize
2145                  << " (merged " << mergedSiblings << " siblings)" << endl;
2146
2147        if (mergeStats)
2148        {
2149                Debug << "maximal tree distance: " << maxTreeDist << endl;
2150                Debug << "Avg tree distance: " << (float)accTreeDist / (float)merged << endl;
2151        }
2152
2153        //TODO: should return sample contributions
2154        return merged;
2155}
2156
2157
2158bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2)
2159{
2160        //-- change pointer to view cells of all leaves associated
2161        //-- with the previous view cells
2162        BspViewCell *fVc = l1->GetViewCell();
2163        BspViewCell *bVc = l2->GetViewCell();
2164
2165        BspViewCell *vc = dynamic_cast<BspViewCell *>(
2166                mViewCellsManager->MergeViewCells(*fVc, *bVc));
2167
2168        // if merge was unsuccessful
2169        if (!vc) return false;
2170
2171        // set new size of view cell
2172        vc->SetArea(fVc->GetArea() + bVc->GetArea());
2173
2174        vector<BspLeaf *> fLeaves = fVc->mLeaves;
2175        vector<BspLeaf *> bLeaves = bVc->mLeaves;
2176
2177        vector<BspLeaf *>::const_iterator it;
2178
2179        //-- change view cells of all the other leaves the view cell belongs to
2180        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2181        {
2182                (*it)->SetViewCell(vc);
2183                vc->mLeaves.push_back(*it);
2184        }
2185
2186        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2187        {
2188                (*it)->SetViewCell(vc);
2189                vc->mLeaves.push_back(*it);
2190        }
2191
2192        vc->Mail();
2193
2194        // clean up old view cells
2195        DEL_PTR(fVc);
2196        DEL_PTR(bVc);
2197
2198        return true;
2199}
2200
2201
2202void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2203{
2204        mViewCellsManager = vcm;
2205}
2206
2207/************************************************************************/
2208/*                BspMergeCandidate implementation                      */
2209/************************************************************************/
2210
2211
2212BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
2213mMergeCost(0),
2214mLeaf1(l1),
2215mLeaf2(l2),
2216mLeaf1Id(l1->GetViewCell()->mMailbox),
2217mLeaf2Id(l2->GetViewCell()->mMailbox)
2218{
2219        EvalMergeCost();
2220}
2221
2222float BspMergeCandidate::GetLeaf1Cost() const
2223{
2224        BspViewCell *vc = mLeaf1->GetViewCell();
2225        return vc->GetPvs().GetSize() * vc->GetArea();
2226}
2227
2228float BspMergeCandidate::GetLeaf2Cost() const
2229{
2230        BspViewCell *vc = mLeaf2->GetViewCell();
2231        return vc->GetPvs().GetSize() * vc->GetVolume();
2232}
2233
2234void BspMergeCandidate::EvalMergeCost()
2235{
2236        //-- compute pvs difference
2237        BspViewCell *vc1 = mLeaf1->GetViewCell();
2238        BspViewCell *vc2 = mLeaf2->GetViewCell();
2239
2240        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
2241        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
2242
2243        //-- compute ratio of old cost
2244        //-- (added size of left and right view cell times pvs size)
2245        //-- to new rendering cost (size of merged view cell times pvs size)
2246        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
2247
2248        const float newCost =
2249                (float)vcPvs * (vc1->GetArea() + vc2->GetArea());
2250
2251        mMergeCost = newCost - oldCost;
2252
2253//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
2254//              mMergeCost += 1.0;
2255}
2256
2257void BspMergeCandidate::SetLeaf1(BspLeaf *l)
2258{
2259        mLeaf1 = l;
2260}
2261
2262void BspMergeCandidate::SetLeaf2(BspLeaf *l)
2263{
2264        mLeaf2 = l;
2265}
2266
2267BspLeaf *BspMergeCandidate::GetLeaf1()
2268{
2269        return mLeaf1;
2270}
2271
2272BspLeaf *BspMergeCandidate::GetLeaf2()
2273{
2274        return mLeaf2;
2275}
2276
2277bool BspMergeCandidate::Valid() const
2278{
2279        return
2280                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
2281                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
2282}
2283
2284float BspMergeCandidate::GetMergeCost() const
2285{
2286        return mMergeCost;
2287}
2288
2289void BspMergeCandidate::SetValid()
2290{
2291        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
2292        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
2293
2294        EvalMergeCost();
2295}
Note: See TracBrowser for help on using the repository browser.