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

Revision 551, 78.4 KB checked in by mattausch, 19 years ago (diff)
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#include "Beam.h"
19
20//-- static members
21
22/** Evaluates split plane classification with respect to the plane's
23        contribution for a minimum number of ray splits.
24*/
25const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
26/** Evaluates split plane classification with respect to the plane's
27        contribution for balanced rays.
28*/
29const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
30
31int BspMergeCandidate::sMaxPvsSize = 0;
32
33int VspBspTree::sFrontId = 0;
34int VspBspTree::sBackId = 0;
35int VspBspTree::sFrontAndBackId = 0;
36
37float BspMergeCandidate::sOverallCost = 0;
38bool BspMergeCandidate::sUseArea = false;
39
40/********************************************************************/
41/*                  class VspBspTree implementation                 */
42/********************************************************************/
43
44VspBspTree::VspBspTree():
45mRoot(NULL),
46mUseAreaForPvs(false),
47mCostNormalizer(Limits::Small),
48mViewCellsManager(NULL),
49mOutOfBoundsCell(NULL),
50mStoreRays(false)
51{
52        bool randomize = false;
53        environment->GetBoolValue("VspBspTree.Construction.randomize", randomize);
54        if (randomize)
55                Randomize(); // initialise random generator for heuristics
56
57        //-- termination criteria for autopartition
58        environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
59        environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
60        environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
61        environment->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
62        environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
63        environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
64        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
65        environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
66
67        //-- factors for bsp tree split plane heuristics
68        environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
69        environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
70        environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
71
72        //-- max cost ratio for early tree termination
73        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
74
75        //-- partition criteria
76        environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
77        environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
78        environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
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
86        environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
87
88        //-- merge options
89        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
90        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
91        environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
92
93
94        //-- termination criteria for axis aligned split
95        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
96                mTermMaxRayContriForAxisAligned);
97        environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
98                mTermMinRaysForAxisAligned);
99
100        //environment->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
101        environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
102
103       
104        mStats.open("bspStats.log");
105
106        //-- debug output
107        Debug << "******* VSP BSP options ******** " << endl;
108    Debug << "max depth: " << mTermMaxDepth << endl;
109        Debug << "min PVS: " << mTermMinPvs << endl;
110        Debug << "min probabiliy: " << mTermMinProbability << endl;
111        Debug << "min rays: " << mTermMinRays << endl;
112        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
113        //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
114        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
115        Debug << "miss tolerance: " << mTermMissTolerance << endl;
116        Debug << "max view cells: " << mMaxViewCells << endl;
117        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
118        Debug << "max plane candidates: " << mMaxRayCandidates << endl;
119        Debug << "randomize: " << randomize << endl;
120        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
121        Debug << "using area for pvs: " << mUseAreaForPvs << endl;
122        Debug << "Split plane strategy: ";
123        if (mSplitPlaneStrategy & RANDOM_POLYGON)
124        {
125                Debug << "random polygon ";
126        }
127        if (mSplitPlaneStrategy & AXIS_ALIGNED)
128        {
129                Debug << "axis aligned ";
130        }
131        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
132        {
133                mCostNormalizer += mLeastRaySplitsFactor;
134                Debug << "least ray splits ";
135        }
136        if (mSplitPlaneStrategy & BALANCED_RAYS)
137        {
138                mCostNormalizer += mBalancedRaysFactor;
139                Debug << "balanced rays ";
140        }
141        if (mSplitPlaneStrategy & PVS)
142        {
143                mCostNormalizer += mPvsFactor;
144                Debug << "pvs";
145        }
146
147
148        mSplitCandidates = new vector<SortableEntry>;
149
150        Debug << endl;
151}
152
153BspViewCell *VspBspTree::GetOutOfBoundsCell()
154{
155        return mOutOfBoundsCell;
156}
157
158
159BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
160{
161        if (!mOutOfBoundsCell)
162        {
163                mOutOfBoundsCell = new BspViewCell();
164                mOutOfBoundsCell->SetId(-1);
165                mOutOfBoundsCell->SetValid(false);
166        }
167
168        return mOutOfBoundsCell;
169}
170
171
172const BspTreeStatistics &VspBspTree::GetStatistics() const
173{
174        return mStat;
175}
176
177
178VspBspTree::~VspBspTree()
179{
180        DEL_PTR(mRoot);
181        DEL_PTR(mSplitCandidates);
182}
183
184int VspBspTree::AddMeshToPolygons(Mesh *mesh,
185                                                                  PolygonContainer &polys,
186                                                                  MeshInstance *parent)
187{
188        FaceContainer::const_iterator fi;
189
190        // copy the face data to polygons
191        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
192        {
193                Polygon3 *poly = new Polygon3((*fi), mesh);
194
195                if (poly->Valid(mEpsilon))
196                {
197                        poly->mParent = parent; // set parent intersectable
198                        polys.push_back(poly);
199                }
200                else
201                        DEL_PTR(poly);
202        }
203        return (int)mesh->mFaces.size();
204}
205
206int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
207                                                          PolygonContainer &polys,
208                                                          int maxObjects)
209{
210        int limit = (maxObjects > 0) ?
211                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
212
213        int polysSize = 0;
214
215        for (int i = 0; i < limit; ++ i)
216        {
217                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
218                {
219                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
220                        polysSize +=
221                                AddMeshToPolygons(viewCells[i]->GetMesh(),
222                                                                  polys,
223                                                                  viewCells[i]);
224                }
225        }
226
227        return polysSize;
228}
229
230int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
231                                                                 PolygonContainer &polys,
232                                                                 int maxObjects)
233{
234        int limit = (maxObjects > 0) ?
235                Min((int)objects.size(), maxObjects) : (int)objects.size();
236
237        for (int i = 0; i < limit; ++i)
238        {
239                Intersectable *object = objects[i];//*it;
240                Mesh *mesh = NULL;
241
242                switch (object->Type()) // extract the meshes
243                {
244                case Intersectable::MESH_INSTANCE:
245                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
246                        break;
247                case Intersectable::VIEW_CELL:
248                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
249                        break;
250                        // TODO: handle transformed mesh instances
251                default:
252                        Debug << "intersectable type not supported" << endl;
253                        break;
254                }
255
256        if (mesh) // copy the mesh data to polygons
257                {
258                        mBox.Include(object->GetBox()); // add to BSP tree aabb
259                        AddMeshToPolygons(mesh, polys, NULL);
260                }
261        }
262
263        return (int)polys.size();
264}
265
266void VspBspTree::Construct(const VssRayContainer &sampleRays,
267                                                   AxisAlignedBox3 *forcedBoundingBox)
268{
269    mStat.nodes = 1;
270        mBox.Initialize();      // initialise BSP tree bounding box
271
272        if (forcedBoundingBox)
273                mBox = *forcedBoundingBox;
274       
275        PolygonContainer polys;
276        RayInfoContainer *rays = new RayInfoContainer();
277
278        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
279
280        long startTime = GetTime();
281
282        cout << "Extracting polygons from rays ... ";
283
284        Intersectable::NewMail();
285
286        int numObj = 0;
287
288        //-- extract polygons intersected by the rays
289        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
290        {
291                VssRay *ray = *rit;
292
293                if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
294                        ray->mTerminationObject &&
295                        !ray->mTerminationObject->Mailed())
296                {
297                        ray->mTerminationObject->Mail();
298                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
299                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
300                        ++ numObj;
301                        //-- compute bounding box
302                        if (!forcedBoundingBox)
303                                mBox.Include(ray->mTermination);
304                }
305
306                if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
307                        ray->mOriginObject &&
308                        !ray->mOriginObject->Mailed())
309                {
310                        ray->mOriginObject->Mail();
311                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
312                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
313                        ++ numObj;
314
315                        //-- compute bounding box
316                        if (!forcedBoundingBox)
317                                mBox.Include(ray->mOrigin);
318                }
319        }
320       
321        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
322        //-- store rays
323        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
324        {
325                VssRay *ray = *rit;
326
327                float minT, maxT;
328
329                // TODO: not very efficient to implictly cast between rays types
330                if (mBox.GetRaySegment(*ray, minT, maxT))
331                {
332                        float len = ray->Length();
333
334                        if (!len)
335                                len = Limits::Small;
336
337                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
338                }
339        }
340
341        if (mUseAreaForPvs)
342                mTermMinProbability *= mBox.SurfaceArea(); // normalize
343        else
344                mTermMinProbability *= mBox.GetVolume();
345
346        mStat.polys = (int)polys.size();
347
348        cout << "finished" << endl;
349
350        Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
351                  << (int)sampleRays.size() << " rays in "
352                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
353
354        Construct(polys, rays);
355
356        // clean up polygons
357        CLEAR_CONTAINER(polys);
358}
359
360
361// return memory usage in MB
362float VspBspTree::GetMemUsage() const
363{
364        return
365                (sizeof(VspBspTree) +
366                 mStat.Leaves() * sizeof(BspLeaf) +
367                 mStat.Interior() * sizeof(BspInterior) +
368                 mStat.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
369}
370
371
372
373void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
374{
375        VspBspTraversalStack tStack;
376
377        mRoot = new BspLeaf();
378
379        // constrruct root node geometry
380        BspNodeGeometry *geom = new BspNodeGeometry();
381        ConstructGeometry(mRoot, *geom);
382
383        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
384
385        VspBspTraversalData tData(mRoot,
386                                                          new PolygonContainer(polys),
387                                                          0,
388                                                          rays,
389                              ComputePvsSize(*rays),
390                                                          prop,
391                                                          geom);
392
393        tStack.push(tData);
394
395        mStat.Start();
396        cout << "Contructing vsp bsp tree ... \n";
397
398        long startTime = GetTime();     
399        // used for intermediate time measurements
400        long interTime = GetTime();     
401
402        mOutOfMemory = false;
403
404        int nleaves = 500;
405
406        while (!tStack.empty())
407        {
408                tData = tStack.top();
409            tStack.pop();               
410
411                if (0 && !mOutOfMemory)
412                {
413                        float mem = GetMemUsage();
414
415                        if (mem > mMaxMemory)
416                        {
417                                mOutOfMemory = true;
418                                Debug << "memory limit reached: " << mem << endl;
419                        }
420                }
421
422                        // subdivide leaf node
423                BspNode *r = Subdivide(tStack, tData);
424
425                if (r == mRoot)
426                        Debug << "VSP BSP tree construction time spent at root: "
427                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
428
429                if (mStat.Leaves() >= nleaves)
430                {
431                        nleaves += 500;
432                               
433                        cout << "leaves=" << mStat.Leaves() << endl;
434                        Debug << "needed "
435                          << TimeDiff(interTime, GetTime())*1e-3 << " secs to create 500 leaves" << endl;
436                        interTime = GetTime();
437                }
438        }
439
440        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
441        cout << "finished\n";
442
443        mStat.Stop();
444}
445
446
447bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
448{
449        return
450                (((int)data.mRays->size() <= mTermMinRays) ||
451                 (data.mPvs <= mTermMinPvs)   ||
452                 (data.mProbability <= mTermMinProbability) ||
453                 (mStat.Leaves() >= mMaxViewCells) ||
454                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
455                 (data.mDepth >= mTermMaxDepth));
456}
457
458
459BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
460                                                           VspBspTraversalData &tData)
461{
462        BspNode *newNode = tData.mNode;
463
464        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
465        {
466                PolygonContainer coincident;
467
468                VspBspTraversalData tFrontData;
469                VspBspTraversalData tBackData;
470
471                // create new interior node and two leaf nodes
472                // or return leaf as it is (if maxCostRatio missed)
473                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
474
475                if (!newNode->IsLeaf()) //-- continue subdivision
476                {
477                        // push the children on the stack
478                        tStack.push(tFrontData);
479                        tStack.push(tBackData);
480
481                        // delete old leaf node
482                        DEL_PTR(tData.mNode);
483                }
484        }
485
486        //-- terminate traversal and create new view cell
487        if (newNode->IsLeaf())
488        {
489                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
490                BspViewCell *viewCell = new BspViewCell();
491               
492                leaf->SetViewCell(viewCell);
493       
494                //-- update pvs
495                int conSamp = 0, sampCon = 0;
496                AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
497
498                mStat.contributingSamples += conSamp;
499                mStat.sampleContributions += sampCon;
500
501                //-- store additional info
502                if (mStoreRays)
503                {
504                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
505                        for (it = tData.mRays->begin(); it != it_end; ++ it)
506                                leaf->mVssRays.push_back((*it).mRay);
507                }
508               
509                if (!mViewCellsManager->CheckValid(viewCell))
510                {
511                        viewCell->SetValid(false);
512
513                        leaf->SetTreeValid(false);
514                        PropagateUpValidity(leaf);
515
516                        ++ mStat.invalidLeaves;
517                }
518               
519        viewCell->mLeaves.push_back(leaf);
520
521                if (mUseAreaForPvs)
522                        viewCell->SetArea(tData.mProbability);
523                else
524                        viewCell->SetVolume(tData.mProbability);
525
526                leaf->mProbability = tData.mProbability;
527
528                EvaluateLeafStats(tData);               
529        }
530
531        //-- cleanup
532        tData.Clear();
533
534        return newNode;
535}
536
537
538
539
540BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
541                                                                   VspBspTraversalData &frontData,
542                                                                   VspBspTraversalData &backData,
543                                                                   PolygonContainer &coincident)
544{
545        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
546       
547        // select subdivision plane
548        Plane3 splitPlane;
549       
550        int maxCostMisses = tData.mMaxCostMisses;
551
552        const bool success =
553                SelectPlane(splitPlane, leaf, tData, frontData, backData);
554
555        if (!success)
556        {
557                ++ maxCostMisses;
558
559                if (maxCostMisses > mTermMissTolerance)
560                {
561                        // terminate branch because of max cost
562                        ++ mStat.maxCostNodes;
563            return leaf;
564                }
565        }
566
567        mStat.nodes += 2;
568
569        //-- subdivide further
570        BspInterior *interior = new BspInterior(splitPlane);
571
572#ifdef _DEBUG
573        Debug << interior << endl;
574#endif
575
576        //-- the front and back traversal data is filled with the new values
577        frontData.mDepth = tData.mDepth + 1;
578        frontData.mPolygons = new PolygonContainer();
579        frontData.mRays = new RayInfoContainer();
580       
581        backData.mDepth = tData.mDepth + 1;
582        backData.mPolygons = new PolygonContainer();
583        backData.mRays = new RayInfoContainer();
584       
585        // subdivide rays
586        SplitRays(interior->GetPlane(),
587                          *tData.mRays,
588                          *frontData.mRays,
589                          *backData.mRays);
590
591        // subdivide polygons
592        SplitPolygons(interior->GetPlane(),
593                                  *tData.mPolygons,
594                      *frontData.mPolygons,
595                                  *backData.mPolygons,
596                                  coincident);
597
598
599        // how often was max cost ratio missed in this branch?
600        frontData.mMaxCostMisses = maxCostMisses;
601        backData.mMaxCostMisses = maxCostMisses;
602
603        // compute pvs
604        frontData.mPvs = ComputePvsSize(*frontData.mRays);
605        backData.mPvs = ComputePvsSize(*backData.mRays);
606
607        // split front and back node geometry and compute area
608       
609        // if geometry was not already computed
610        if (!frontData.mGeometry && !backData.mGeometry)
611        {
612                frontData.mGeometry = new BspNodeGeometry();
613                backData.mGeometry = new BspNodeGeometry();
614
615                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
616                                                                           *backData.mGeometry,
617                                                                           interior->GetPlane(),
618                                                                           mBox,
619                                                                           mEpsilon);
620               
621                if (mUseAreaForPvs)
622                {
623                        frontData.mProbability = frontData.mGeometry->GetArea();
624                        backData.mProbability = backData.mGeometry->GetArea();
625                }
626                else
627                {
628                        frontData.mProbability = frontData.mGeometry->GetVolume();
629                        backData.mProbability = backData.mGeometry->GetVolume();
630                }
631        }
632       
633
634        //-- create front and back leaf
635
636        BspInterior *parent = leaf->GetParent();
637
638        // replace a link from node's parent
639        if (parent)
640        {
641                parent->ReplaceChildLink(leaf, interior);
642                interior->SetParent(parent);
643        }
644        else // new root
645        {
646                mRoot = interior;
647        }
648
649        // and setup child links
650        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
651
652        frontData.mNode = interior->GetFront();
653        backData.mNode = interior->GetBack();
654
655        //DEL_PTR(leaf);
656        return interior;
657}
658
659
660void VspBspTree::AddToPvs(BspLeaf *leaf,
661                                                  const RayInfoContainer &rays,
662                                                  int &sampleContributions,
663                                                  int &contributingSamples)
664{
665        sampleContributions = 0;
666        contributingSamples = 0;
667
668    RayInfoContainer::const_iterator it, it_end = rays.end();
669
670        ViewCell *vc = leaf->GetViewCell();
671
672        // add contributions from samples to the PVS
673        for (it = rays.begin(); it != it_end; ++ it)
674        {
675                int contribution = 0;
676                VssRay *ray = (*it).mRay;
677
678                if (ray->mTerminationObject)
679                        contribution += vc->GetPvs().AddSample(ray->mTerminationObject);
680
681                if (ray->mOriginObject)
682                        contribution += vc->GetPvs().AddSample(ray->mOriginObject);
683
684                if (contribution)
685                {
686                        sampleContributions += contribution;
687                        ++ contributingSamples;
688                }
689                //leaf->mVssRays.push_back(ray);
690        }
691}
692
693void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
694{
695        mSplitCandidates->clear();
696
697        int requestedSize = 2 * (int)(rays.size());
698        // creates a sorted split candidates array
699        if (mSplitCandidates->capacity() > 500000 &&
700                requestedSize < (int)(mSplitCandidates->capacity()/10) )
701        {
702        delete mSplitCandidates;
703                mSplitCandidates = new vector<SortableEntry>;
704        }
705
706        mSplitCandidates->reserve(requestedSize);
707
708        // insert all queries
709        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
710        {
711                bool positive = (*ri).mRay->HasPosDir(axis);
712                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
713                                                                                                  (*ri).ExtrapOrigin(axis), (*ri).mRay));
714
715                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
716                                                                                                  (*ri).ExtrapTermination(axis), (*ri).mRay));
717        }
718
719        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
720}
721
722float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
723                                                                                  const AxisAlignedBox3 &box,
724                                                                                  const int pvsSize,
725                                                                                  const int &axis,
726                                          float &position)
727{
728        int raysBack;
729        int raysFront;
730        int pvsBack;
731        int pvsFront;
732
733        SortSplitCandidates(rays, axis);
734
735        // go through the lists, count the number of objects left and right
736        // and evaluate the following cost funcion:
737        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
738
739        int rl = 0, rr = (int)rays.size();
740        int pl = 0, pr = pvsSize;
741
742        float minBox = box.Min(axis);
743        float maxBox = box.Max(axis);
744        float sizeBox = maxBox - minBox;
745
746        float minBand = minBox + 0.1f*(maxBox - minBox);
747        float maxBand = minBox + 0.9f*(maxBox - minBox);
748
749        float sum = rr*sizeBox;
750        float minSum = 1e20f;
751
752        Intersectable::NewMail();
753
754        // set all object as belonging to the fron pvs
755        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
756        {
757                if ((*ri).mRay->IsActive())
758                {
759                        Intersectable *object = (*ri).mRay->mTerminationObject;
760
761                        if (object)
762                        {
763                                if (!object->Mailed())
764                                {
765                                        object->Mail();
766                                        object->mCounter = 1;
767                                }
768                                else
769                                        ++ object->mCounter;
770                        }
771                }
772        }
773
774        Intersectable::NewMail();
775
776        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
777                ci < mSplitCandidates->end(); ++ ci)
778        {
779                VssRay *ray;
780
781                switch ((*ci).type)
782                {
783                        case SortableEntry::ERayMin:
784                                {
785                                        ++ rl;
786                                        ray = (VssRay *) (*ci).ray;
787
788                                        Intersectable *object = ray->mTerminationObject;
789
790                                        if (object && !object->Mailed())
791                                        {
792                                                object->Mail();
793                                                ++ pl;
794                                        }
795                                        break;
796                                }
797                        case SortableEntry::ERayMax:
798                                {
799                                        -- rr;
800                                        ray = (VssRay *) (*ci).ray;
801
802                                        Intersectable *object = ray->mTerminationObject;
803
804                                        if (object)
805                                        {
806                                                if (-- object->mCounter == 0)
807                                                        -- pr;
808                                        }
809
810                                        break;
811                                }
812                }
813
814                // Note: sufficient to compare size of bounding boxes of front and back side?
815                if ((*ci).value > minBand && (*ci).value < maxBand)
816                {
817                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
818
819                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
820                        // cout<<"cost= "<<sum<<endl;
821
822                        if (sum < minSum)
823                        {
824                                minSum = sum;
825                                position = (*ci).value;
826
827                                raysBack = rl;
828                                raysFront = rr;
829
830                                pvsBack = pl;
831                                pvsFront = pr;
832
833                        }
834                }
835        }
836
837        float oldCost = (float)pvsSize;
838        float newCost = mCtDivCi + minSum / sizeBox;
839        float ratio = newCost / oldCost;
840
841        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
842        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
843
844        return ratio;
845}
846
847
848float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
849                                                                                 const VspBspTraversalData &tData,
850                                                                                 int &axis,
851                                                                                 BspNodeGeometry **frontGeom,
852                                                                                 BspNodeGeometry **backGeom,
853                                                                                 float &pFront,
854                                                                                 float &pBack,
855                                                                                 const bool useKdSplit)
856{
857        const bool useCostHeuristics = false;
858
859        //-- regular split
860        float nPosition[3];
861        float nCostRatio[3];
862        float nProbFront[3];
863        float nProbBack[3];
864
865        BspNodeGeometry *nFrontGeom[3];
866        BspNodeGeometry *nBackGeom[3];
867
868        int bestAxis = -1;
869
870        // create bounding box of node geometry
871        AxisAlignedBox3 box;
872        box.Initialize();
873       
874        //TODO: for kd split geometry already is box
875        if (1)
876        {
877                PolygonContainer::const_iterator it, it_end = tData.mGeometry->mPolys.end();
878
879                for(it = tData.mGeometry->mPolys.begin(); it < it_end; ++ it)
880                        box.Include(*(*it));
881        }
882        else
883        {
884                RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
885
886                for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
887                        box.Include((*ri).ExtrapTermination());
888        }
889
890        const int sAxis = box.Size().DrivingAxis();
891
892        for (axis = 0; axis < 3; ++ axis)
893        {
894                nFrontGeom[axis] = new BspNodeGeometry();
895                nBackGeom[axis] = new BspNodeGeometry();
896
897                if (!mOnlyDrivingAxis || (axis == sAxis))
898                {
899                        if (!useCostHeuristics)
900                        {
901                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
902                                Vector3 normal(0,0,0); normal[axis] = 1.0f;
903
904                                // allows faster split because we have axis aligned kd tree boxes
905                                if (useKdSplit)
906                                {
907                                        nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
908                                                                                                                                box,
909                                                                                                                                axis,
910                                                                                                                                nPosition[axis],
911                                                                                                                                nProbFront[axis],
912                                                                                                                                nProbBack[axis]);
913                                       
914                                        Vector3 pos;
915                                       
916                                        pos = box.Max(); pos[axis] = nPosition[axis];
917                                        AxisAlignedBox3 bBox(box.Min(), pos);
918                                        bBox.ExtractPolys(nBackGeom[axis]->mPolys);
919                                       
920                                        pos = box.Min(); pos[axis] = nPosition[axis];
921                                        AxisAlignedBox3 fBox(pos, box.Max());
922                                        fBox.ExtractPolys(nFrontGeom[axis]->mPolys);
923                                }
924                                else
925                                {
926                                        nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]),
927                                                                                                          tData, *nFrontGeom[axis], *nBackGeom[axis],
928                                                                                                          nProbFront[axis], nProbBack[axis]);
929                                }
930                        }
931                        else
932                        {
933                                nCostRatio[axis] =
934                                        BestCostRatioHeuristics(*tData.mRays,
935                                                                                    box,
936                                                                                        tData.mPvs,
937                                                                                        axis,
938                                                                                        nPosition[axis]);
939                        }
940
941                        if (bestAxis == -1)
942                        {
943                                bestAxis = axis;
944                        }
945
946                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
947                        {
948                                bestAxis = axis;
949                        }
950
951                }
952        }
953
954        //-- assign values
955        axis = bestAxis;
956        pFront = nProbFront[bestAxis];
957        pBack = nProbBack[bestAxis];
958
959        // assign best split nodes geometry
960        *frontGeom = nFrontGeom[bestAxis];
961        *backGeom = nBackGeom[bestAxis];
962
963        // and delete other geometry
964        delete nFrontGeom[(bestAxis + 1) % 3];
965        delete nBackGeom[(bestAxis + 2) % 3];
966
967        //-- split plane
968    Vector3 normal(0,0,0); normal[bestAxis] = 1;
969        plane = Plane3(normal, nPosition[bestAxis]);
970
971        return nCostRatio[bestAxis];
972}
973
974
975float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
976                                                                                   const AxisAlignedBox3 &box,
977                                                                                   const int axis,
978                                                                                   const float &position,                                                                                 
979                                                                                   float &pFront,
980                                                                                   float &pBack) const
981{
982        int pvsTotal = 0;
983        int pvsFront = 0;
984        int pvsBack = 0;
985       
986        // create unique ids for pvs heuristics
987        GenerateUniqueIdsForPvs();
988
989        const int pvsSize = data.mPvs;
990
991        // this is the main ray classification loop!
992        for(RayInfoContainer::iterator ri = data.mRays->begin();
993                ri != data.mRays->end(); ++ ri)
994        {
995                if (!(*ri).mRay->IsActive())
996                        continue;
997
998                // determine the side of this ray with respect to the plane
999                float t;
1000                int side = (*ri).ComputeRayIntersection(axis, position, t);
1001       
1002                AddObjToPvs((*ri).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1003                AddObjToPvs((*ri).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1004        }
1005
1006        //-- pvs heuristics
1007        float pOverall;
1008
1009        // -- simplified computation for mid split
1010       
1011       
1012        pOverall = data.mProbability;
1013
1014        if (!mUseAreaForPvs)
1015        {   // volume
1016                pBack = pFront = pOverall * 0.5f;
1017               
1018#if 0
1019                // box length substitute for probability
1020                const float minBox = box.Min(axis);
1021                const float maxBox = box.Max(axis);
1022
1023                pBack = position - minBox;
1024                pFront = maxBox - position;
1025                pOverall = maxBox - minBox;
1026#endif
1027        }
1028        else //-- area substitute for probability
1029        {
1030                const int axis2 = (axis + 1) % 3;
1031                const int axis3 = (axis + 2) % 3;
1032
1033                const float faceArea =
1034                        (box.Max(axis2) - box.Min(axis2)) *
1035                        (box.Max(axis3) - box.Min(axis3));
1036
1037                pBack = pFront = pOverall * 0.5f + faceArea;
1038        }
1039
1040        //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1041        //Debug << pFront << " " << pBack << " " << pOverall << endl;
1042
1043        const float newCost = pvsBack * pBack + pvsFront * pFront;
1044        const float oldCost = (float)pvsSize * pOverall;
1045
1046        return  (mCtDivCi + newCost) / oldCost;
1047}
1048
1049
1050
1051bool VspBspTree::SelectPlane(Plane3 &bestPlane,
1052                                                         BspLeaf *leaf,
1053                                                         VspBspTraversalData &data,
1054                                                         VspBspTraversalData &frontData,
1055                                                         VspBspTraversalData &backData)
1056{
1057        // simplest strategy: just take next polygon
1058        if (mSplitPlaneStrategy & RANDOM_POLYGON)
1059        {
1060        if (!data.mPolygons->empty())
1061                {
1062                        const int randIdx =
1063                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
1064                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
1065
1066                        bestPlane = nextPoly->GetSupportingPlane();
1067                        return true;
1068                }
1069        }
1070
1071        //-- use heuristics to find appropriate plane
1072
1073        // intermediate plane
1074        Plane3 plane;
1075        float lowestCost = MAX_FLOAT;
1076       
1077        // decides if the first few splits should be only axisAligned
1078        const bool onlyAxisAligned  =
1079                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
1080                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1081                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
1082       
1083        const int limit = onlyAxisAligned ? 0 :
1084                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1085
1086        float candidateCost;
1087
1088        int maxIdx = (int)data.mPolygons->size();
1089
1090        for (int i = 0; i < limit; ++ i)
1091        {
1092                //-- assure that no index is taken twice
1093                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
1094                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
1095
1096                // swap candidate to the end to avoid testing same plane
1097                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
1098                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
1099
1100                // evaluate current candidate
1101                BspNodeGeometry fGeom, bGeom;
1102                float fArea, bArea;
1103                plane = poly->GetSupportingPlane();
1104                candidateCost = SplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
1105               
1106                if (candidateCost < lowestCost)
1107                {
1108                        bestPlane = plane;
1109                        lowestCost = candidateCost;
1110                }
1111        }
1112
1113        //-- evaluate axis aligned splits
1114        int axis;
1115        BspNodeGeometry *fGeom, *bGeom;
1116        float pFront, pBack;
1117
1118        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
1119                                                                                   &fGeom, &bGeom,
1120                                                                                   pFront, pBack,
1121                                                                                   onlyAxisAligned);     
1122
1123        if (candidateCost < lowestCost)
1124        {       
1125                bestPlane = plane;
1126                lowestCost = candidateCost;
1127
1128                // assign already computed values
1129                // we can do this because we always save the
1130                // computed values from the axis aligned splits
1131               
1132                frontData.mGeometry = fGeom;
1133                backData.mGeometry = bGeom;
1134       
1135                frontData.mProbability = pFront;
1136                backData.mProbability = pBack;
1137               
1138                //! error also computed if cost ratio is missed
1139                ++ mStat.splits[axis];
1140        }
1141        else
1142        {
1143                DEL_PTR(fGeom);
1144                DEL_PTR(bGeom);
1145        }
1146
1147#ifdef _DEBUG
1148        Debug << "plane lowest cost: " << lowestCost << endl;
1149#endif
1150
1151        // cost ratio miss
1152        if (lowestCost > mTermMaxCostRatio)
1153                return false;
1154
1155        return true;
1156}
1157
1158
1159Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
1160{
1161        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1162
1163        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
1164        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
1165
1166        const Vector3 pt = (maxPt + minPt) * 0.5;
1167        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
1168
1169        return Plane3(normal, pt);
1170}
1171
1172
1173Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
1174{
1175        Vector3 pt[3];
1176
1177        int idx[3];
1178        int cmaxT = 0;
1179        int cminT = 0;
1180        bool chooseMin = false;
1181
1182        for (int j = 0; j < 3; ++ j)
1183        {
1184                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
1185
1186                if (idx[j] >= (int)rays.size())
1187                {
1188                        idx[j] -= (int)rays.size();
1189
1190                        chooseMin = (cminT < 2);
1191                }
1192                else
1193                        chooseMin = (cmaxT < 2);
1194
1195                RayInfo rayInf = rays[idx[j]];
1196                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
1197        }
1198
1199        return Plane3(pt[0], pt[1], pt[2]);
1200}
1201
1202Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
1203{
1204        Vector3 pt[3];
1205
1206        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1207        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1208
1209        // check if rays different
1210        if (idx1 == idx2)
1211                idx2 = (idx2 + 1) % (int)rays.size();
1212
1213        const RayInfo ray1 = rays[idx1];
1214        const RayInfo ray2 = rays[idx2];
1215
1216        // normal vector of the plane parallel to both lines
1217        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
1218
1219        // vector from line 1 to line 2
1220        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
1221
1222        // project vector on normal to get distance
1223        const float dist = DotProd(vd, norm);
1224
1225        // point on plane lies halfway between the two planes
1226        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
1227
1228        return Plane3(norm, planePt);
1229}
1230
1231
1232inline void VspBspTree::GenerateUniqueIdsForPvs()
1233{
1234        Intersectable::NewMail(); sBackId = ViewCell::sMailId;
1235        Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
1236        Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
1237}
1238
1239
1240float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1241                                                                 const VspBspTraversalData &data,
1242                                                                 BspNodeGeometry &geomFront,
1243                                                                 BspNodeGeometry &geomBack,
1244                                                                 float &pFront,
1245                                                                 float &pBack) const
1246{
1247        float cost = 0;
1248
1249        float sumBalancedRays = 0;
1250        float sumRaySplits = 0;
1251
1252        int pvsFront = 0;
1253        int pvsBack = 0;
1254
1255        // probability that view point lies in back / front node
1256        float pOverall = 0;
1257        pFront = 0;
1258        pBack = 0;
1259
1260        int raysFront = 0;
1261        int raysBack = 0;
1262        int totalPvs = 0;
1263
1264        int limit;
1265        bool useRand;
1266
1267        // choose test rays randomly if too much
1268        if ((int)data.mRays->size() > mMaxTests)
1269        {
1270                useRand = true;
1271                limit = mMaxTests;
1272        }
1273        else
1274        {
1275                useRand = false;
1276                limit = (int)data.mRays->size();
1277        }
1278       
1279        for (int i = 0; i < limit; ++ i)
1280        {
1281                const int testIdx = useRand ?
1282                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
1283                RayInfo rayInf = (*data.mRays)[testIdx];
1284
1285                float t;
1286                VssRay *ray = rayInf.mRay;
1287                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1288
1289        if (cf >= 0)
1290                        ++ raysFront;
1291                if (cf <= 0)
1292                        ++ raysBack;
1293
1294                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1295                {
1296                        sumBalancedRays += cf;
1297                }
1298
1299                if (mSplitPlaneStrategy & BALANCED_RAYS)
1300                {
1301                        if (cf == 0)
1302                                ++ sumRaySplits;
1303                }
1304
1305                if (mSplitPlaneStrategy & PVS)
1306                {
1307                        // find front and back pvs for origing and termination object
1308                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1309                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1310                }
1311        }
1312
1313        const float raysSize = (float)data.mRays->size() + Limits::Small;
1314
1315        if (mSplitPlaneStrategy & PVS)
1316        {
1317                // create unique ids for pvs heuristics
1318                GenerateUniqueIdsForPvs();
1319
1320                // construct child geometry with regard to the candidate split plane
1321                data.mGeometry->SplitGeometry(geomFront,
1322                                                                          geomBack,
1323                                                                          candidatePlane,
1324                                                                          mBox,
1325                                                                          mEpsilon);
1326
1327                pOverall = data.mProbability;
1328
1329                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
1330                {
1331                        pFront = geomFront.GetVolume();
1332                        pBack = pOverall - geomFront.GetVolume();
1333                }
1334                else
1335                {
1336                        pFront = geomFront.GetArea();
1337                        pBack = geomBack.GetArea();
1338                }
1339        }
1340
1341
1342        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1343                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1344
1345        if (mSplitPlaneStrategy & BALANCED_RAYS)
1346                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
1347
1348        // pvs criterium
1349        if (mSplitPlaneStrategy & PVS)
1350        {
1351                const float oldCost = pOverall * (float)totalPvs + Limits::Small;
1352                cost += mPvsFactor * (pvsFront * pFront + pvsBack * pBack) / oldCost;
1353        }
1354
1355#ifdef _DEBUG
1356        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
1357                  << " frontpvs: " << pvsFront << " pFront: " << pFront
1358                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
1359#endif
1360
1361        // normalize cost by sum of linear factors
1362        return cost / (float)mCostNormalizer;
1363}
1364
1365
1366void VspBspTree::AddObjToPvs(Intersectable *obj,
1367                                                         const int cf,
1368                                                         int &frontPvs,
1369                                                         int &backPvs,
1370                                                         int &totalPvs) const
1371{
1372        if (!obj)
1373                return;
1374       
1375        if ((obj->mMailbox != sFrontId) &&
1376                (obj->mMailbox != sBackId) &&
1377                (obj->mMailbox != sFrontAndBackId))
1378        {
1379                ++ totalPvs;
1380        }
1381
1382        // TODO: does this really belong to no pvs?
1383        //if (cf == Ray::COINCIDENT) return;
1384
1385        // object belongs to both PVS
1386        if (cf >= 0)
1387        {
1388                if ((obj->mMailbox != sFrontId) &&
1389                        (obj->mMailbox != sFrontAndBackId))
1390                {
1391                        ++ frontPvs;
1392               
1393                        if (obj->mMailbox == sBackId)
1394                                obj->mMailbox = sFrontAndBackId;
1395                        else
1396                                obj->mMailbox = sFrontId;
1397                }
1398        }
1399
1400        if (cf <= 0)
1401        {
1402                if ((obj->mMailbox != sBackId) &&
1403                        (obj->mMailbox != sFrontAndBackId))
1404                {
1405                        ++ backPvs;
1406               
1407                        if (obj->mMailbox == sFrontId)
1408                                obj->mMailbox = sFrontAndBackId;
1409                        else
1410                                obj->mMailbox = sBackId;
1411                }
1412        }
1413}
1414
1415
1416void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
1417                                                           const bool onlyUnmailed,
1418                                                           const int maxPvsSize) const
1419{
1420        stack<BspNode *> nodeStack;
1421        nodeStack.push(mRoot);
1422
1423        while (!nodeStack.empty())
1424        {
1425                BspNode *node = nodeStack.top();
1426                nodeStack.pop();
1427               
1428                if (node->IsLeaf())
1429                {
1430                        // test if this leaf is in valid view space
1431                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1432                        if (leaf->TreeValid() &&
1433                                (!onlyUnmailed || !leaf->Mailed()) &&
1434                                ((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
1435                        {
1436                                leaves.push_back(leaf);
1437                        }
1438                }
1439                else
1440                {
1441                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1442
1443                        nodeStack.push(interior->GetBack());
1444                        nodeStack.push(interior->GetFront());
1445                }
1446        }
1447}
1448
1449
1450AxisAlignedBox3 VspBspTree::GetBoundingBox() const
1451{
1452        return mBox;
1453}
1454
1455
1456BspNode *VspBspTree::GetRoot() const
1457{
1458        return mRoot;
1459}
1460
1461
1462void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
1463{
1464        // the node became a leaf -> evaluate stats for leafs
1465        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1466
1467        // store maximal and minimal depth
1468        if (data.mDepth > mStat.maxDepth)
1469                mStat.maxDepth = data.mDepth;
1470
1471        if (data.mPvs > mStat.maxPvs)
1472                mStat.maxPvs = data.mPvs;
1473       
1474        if (data.mDepth < mStat.minDepth)
1475                mStat.minDepth = data.mDepth;
1476
1477        if (data.mDepth >= mTermMaxDepth)
1478                ++ mStat.maxDepthNodes;
1479        // accumulate rays to compute rays /  leaf
1480        mStat.accumRays += (int)data.mRays->size();
1481
1482        if (data.mPvs < mTermMinPvs)
1483                ++ mStat.minPvsNodes;
1484
1485        if ((int)data.mRays->size() < mTermMinRays)
1486                ++ mStat.minRaysNodes;
1487
1488        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1489                ++ mStat.maxRayContribNodes;
1490
1491        if (data.mProbability <= mTermMinProbability)
1492                ++ mStat.minProbabilityNodes;
1493       
1494        // accumulate depth to compute average depth
1495        mStat.accumDepth += data.mDepth;
1496
1497#ifdef _DEBUG
1498        Debug << "BSP stats: "
1499                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1500                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1501                  << "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
1502                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1503                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1504                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1505#endif
1506}
1507
1508int VspBspTree::CastRay(Ray &ray)
1509{
1510        int hits = 0;
1511
1512        stack<BspRayTraversalData> tStack;
1513
1514        float maxt, mint;
1515
1516        if (!mBox.GetRaySegment(ray, mint, maxt))
1517                return 0;
1518
1519        Intersectable::NewMail();
1520
1521        Vector3 entp = ray.Extrap(mint);
1522        Vector3 extp = ray.Extrap(maxt);
1523
1524        BspNode *node = mRoot;
1525        BspNode *farChild = NULL;
1526
1527        while (1)
1528        {
1529                if (!node->IsLeaf())
1530                {
1531                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1532
1533                        Plane3 splitPlane = in->GetPlane();
1534                        const int entSide = splitPlane.Side(entp);
1535                        const int extSide = splitPlane.Side(extp);
1536
1537                        if (entSide < 0)
1538                        {
1539                                node = in->GetBack();
1540
1541                                if(extSide <= 0) // plane does not split ray => no far child
1542                                        continue;
1543
1544                                farChild = in->GetFront(); // plane splits ray
1545
1546                        } else if (entSide > 0)
1547                        {
1548                                node = in->GetFront();
1549
1550                                if (extSide >= 0) // plane does not split ray => no far child
1551                                        continue;
1552
1553                                farChild = in->GetBack(); // plane splits ray
1554                        }
1555                        else // ray and plane are coincident
1556                        {
1557                                // WHAT TO DO IN THIS CASE ?
1558                                //break;
1559                                node = in->GetFront();
1560                                continue;
1561                        }
1562
1563                        // push data for far child
1564                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1565
1566                        // find intersection of ray segment with plane
1567                        float t;
1568                        extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1569                        maxt *= t;
1570
1571                } else // reached leaf => intersection with view cell
1572                {
1573                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1574
1575                        if (!leaf->GetViewCell()->Mailed())
1576                        {
1577                                //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
1578                                leaf->GetViewCell()->Mail();
1579                                ++ hits;
1580                        }
1581
1582                        //-- fetch the next far child from the stack
1583                        if (tStack.empty())
1584                                break;
1585
1586                        entp = extp;
1587                        mint = maxt; // NOTE: need this?
1588
1589                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1590                                break;
1591
1592                        BspRayTraversalData &s = tStack.top();
1593
1594                        node = s.mNode;
1595                        extp = s.mExitPoint;
1596                        maxt = s.mMaxT;
1597
1598                        tStack.pop();
1599                }
1600        }
1601
1602        return hits;
1603}
1604
1605
1606void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1607{
1608        ViewCell::NewMail();
1609       
1610        CollectViewCells(mRoot, onlyValid, viewCells, true);
1611}
1612
1613
1614void VspBspTree::ValidateTree()
1615{
1616        stack<BspNode *> nodeStack;
1617
1618        if (!mRoot)
1619                return;
1620
1621        nodeStack.push(mRoot);
1622       
1623        const bool addToUnbounded = false;
1624
1625        while (!nodeStack.empty())
1626        {
1627                BspNode *node = nodeStack.top();
1628                nodeStack.pop();
1629               
1630                if (node->IsLeaf())
1631                {
1632                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1633
1634                        if (!addToUnbounded && node->TreeValid())
1635                        {
1636                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1637                       
1638                                if (!mViewCellsManager->CheckValid(viewCell))
1639                                {
1640                                        vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
1641                                        for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
1642                                        {
1643                                                BspLeaf *l = *it;
1644                                               
1645                                                l->SetTreeValid(false);
1646                                                PropagateUpValidity(l);
1647                                               
1648                                                if (addToUnbounded)
1649                                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
1650
1651                                                ++ mStat.invalidLeaves;
1652                                        }
1653
1654                                        // add to unbounded view cell or set to invalid
1655                                        if (addToUnbounded)
1656                                        {
1657                                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1658                                                DEL_PTR(viewCell);
1659                                        }
1660                                        else
1661                                        {
1662                                                viewCell->SetValid(false);
1663                                        }
1664                                }
1665                        }
1666                }
1667                else
1668                {
1669                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1670               
1671                        nodeStack.push(interior->GetFront());
1672                        nodeStack.push(interior->GetBack());
1673                }
1674        }
1675}
1676
1677
1678void VspBspTree::CollectViewCells(BspNode *root,
1679                                                                  bool onlyValid,
1680                                                                  ViewCellContainer &viewCells,
1681                                                                  bool onlyUnmailed) const
1682{
1683        stack<BspNode *> nodeStack;
1684
1685        if (!root)
1686                return;
1687
1688        nodeStack.push(root);
1689       
1690        while (!nodeStack.empty())
1691        {
1692                BspNode *node = nodeStack.top();
1693                nodeStack.pop();
1694               
1695                if (node->IsLeaf())
1696                {
1697                        if (!onlyValid ||node->TreeValid())
1698                        {
1699                                ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1700                       
1701                                if (!onlyUnmailed || !viewCell->Mailed())
1702                                {
1703                                        viewCell->Mail();
1704                                        viewCells.push_back(viewCell);
1705                                }
1706                        }
1707                }
1708                else
1709                {
1710                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1711               
1712                        nodeStack.push(interior->GetFront());
1713                        nodeStack.push(interior->GetBack());
1714                }
1715        }
1716}
1717
1718
1719float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1720{
1721        float len = 0;
1722
1723        RayInfoContainer::const_iterator it, it_end = rays.end();
1724
1725        for (it = rays.begin(); it != it_end; ++ it)
1726                len += (*it).SegmentLength();
1727
1728        return len;
1729}
1730
1731
1732int VspBspTree::SplitRays(const Plane3 &plane,
1733                                                  RayInfoContainer &rays,
1734                                                  RayInfoContainer &frontRays,
1735                                                  RayInfoContainer &backRays)
1736{
1737        int splits = 0;
1738
1739        while (!rays.empty())
1740        {
1741                RayInfo bRay = rays.back();
1742                rays.pop_back();
1743
1744                VssRay *ray = bRay.mRay;
1745                float t;
1746
1747                // get classification and receive new t
1748                const int cf = bRay.ComputeRayIntersection(plane, t);
1749
1750                switch (cf)
1751                {
1752                case -1:
1753                        backRays.push_back(bRay);
1754                        break;
1755                case 1:
1756                        frontRays.push_back(bRay);
1757                        break;
1758                case 0:
1759                        {
1760                                //-- split ray
1761                                //-- test if start point behind or in front of plane
1762                                const int side = plane.Side(bRay.ExtrapOrigin());
1763
1764                                if (side <= 0)
1765                                {
1766                                        backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1767                                        frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1768                                }
1769                                else
1770                                {
1771                                        frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1772                                        backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1773                                }
1774                        }
1775                        break;
1776                default:
1777                        Debug << "Should not come here" << endl;
1778                        break;
1779                }
1780        }
1781
1782        return splits;
1783}
1784
1785
1786void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1787{
1788        BspNode *lastNode;
1789
1790        do
1791        {
1792                lastNode = n;
1793
1794                // want to get planes defining geometry of this node => don't take
1795                // split plane of node itself
1796                n = n->GetParent();
1797
1798                if (n)
1799                {
1800                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
1801                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1802
1803            if (interior->GetFront() != lastNode)
1804                                halfSpace.ReverseOrientation();
1805
1806                        halfSpaces.push_back(halfSpace);
1807                }
1808        }
1809        while (n);
1810}
1811
1812
1813void VspBspTree::ConstructGeometry(BspNode *n,
1814                                                                   BspNodeGeometry &geom) const
1815{
1816        vector<Plane3> halfSpaces;
1817        ExtractHalfSpaces(n, halfSpaces);
1818
1819        PolygonContainer candidatePolys;
1820
1821        // bounded planes are added to the polygons (reverse polygons
1822        // as they have to be outfacing
1823        for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1824        {
1825                Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1826
1827                if (p->Valid(mEpsilon))
1828                {
1829                        candidatePolys.push_back(p->CreateReversePolygon());
1830                        DEL_PTR(p);
1831                }
1832        }
1833
1834        // add faces of bounding box (also could be faces of the cell)
1835        for (int i = 0; i < 6; ++ i)
1836        {
1837                VertexContainer vertices;
1838
1839                for (int j = 0; j < 4; ++ j)
1840                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
1841
1842                candidatePolys.push_back(new Polygon3(vertices));
1843        }
1844
1845        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
1846        {
1847                // polygon is split by all other planes
1848                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
1849                {
1850                        if (i == j) // polygon and plane are coincident
1851                                continue;
1852
1853                        VertexContainer splitPts;
1854                        Polygon3 *frontPoly, *backPoly;
1855
1856                        const int cf =
1857                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
1858                                                                                                 mEpsilon);
1859
1860                        switch (cf)
1861                        {
1862                                case Polygon3::SPLIT:
1863                                        frontPoly = new Polygon3();
1864                                        backPoly = new Polygon3();
1865
1866                                        candidatePolys[i]->Split(halfSpaces[j],
1867                                                                                         *frontPoly,
1868                                                                                         *backPoly,
1869                                                                                         mEpsilon);
1870
1871                                        DEL_PTR(candidatePolys[i]);
1872
1873                                        if (frontPoly->Valid(mEpsilon))
1874                                                candidatePolys[i] = frontPoly;
1875                                        else
1876                                                DEL_PTR(frontPoly);
1877
1878                                        DEL_PTR(backPoly);
1879                                        break;
1880                                case Polygon3::BACK_SIDE:
1881                                        DEL_PTR(candidatePolys[i]);
1882                                        break;
1883                                // just take polygon as it is
1884                                case Polygon3::FRONT_SIDE:
1885                                case Polygon3::COINCIDENT:
1886                                default:
1887                                        break;
1888                        }
1889                }
1890
1891                if (candidatePolys[i])
1892                        geom.mPolys.push_back(candidatePolys[i]);
1893        }
1894}
1895
1896
1897void VspBspTree::ConstructGeometry(BspViewCell *vc,
1898                                                                   BspNodeGeometry &vcGeom) const
1899{
1900        vector<BspLeaf *> leaves = vc->mLeaves;
1901        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
1902
1903        for (it = leaves.begin(); it != it_end; ++ it)
1904                ConstructGeometry(*it, vcGeom);
1905}
1906
1907
1908typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
1909
1910int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
1911                                                   const bool onlyUnmailed) const
1912{
1913        stack<bspNodePair> nodeStack;
1914       
1915        BspNodeGeometry nodeGeom;
1916        ConstructGeometry(n, nodeGeom);
1917       
1918        // split planes from the root to this node
1919        // needed to verify that we found neighbor leaf
1920        vector<Plane3> halfSpaces;
1921        ExtractHalfSpaces(n, halfSpaces);
1922
1923
1924        BspNodeGeometry *rgeom = new BspNodeGeometry();
1925        ConstructGeometry(mRoot, *rgeom);
1926
1927        nodeStack.push(bspNodePair(mRoot, rgeom));
1928
1929
1930        while (!nodeStack.empty())
1931        {
1932                BspNode *node = nodeStack.top().first;
1933                BspNodeGeometry *geom = nodeStack.top().second;
1934
1935                nodeStack.pop();
1936
1937                bool isAdjacent = true;
1938
1939                // test all planes of current node if still adjacent
1940                for (int i = 0; (i < halfSpaces.size()) && isAdjacent && (node != n); ++ i)
1941                {
1942                        const int cf =
1943                                Polygon3::ClassifyPlane(geom->mPolys,
1944                                                                                halfSpaces[i],
1945                                                                                mEpsilon);
1946
1947                        if (cf == Polygon3::BACK_SIDE)
1948                        {
1949                                isAdjacent = false;
1950                        }
1951                }
1952
1953                if (isAdjacent)
1954                {
1955               
1956                        if (node->IsLeaf())
1957                        {       
1958                                // test if this leaf is in valid view space
1959                                if (node->TreeValid() &&
1960                                        node != n &&
1961                                        (!onlyUnmailed || !node->Mailed()))
1962                                {
1963                                        // neighbor was found
1964                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
1965                                }
1966                        }
1967                        else
1968                        {
1969                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
1970
1971                                const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
1972                                                                                                           interior->GetPlane(),
1973                                                                                                           mEpsilon);
1974                       
1975                                BspNode *front = interior->GetFront();
1976                                BspNode *back = interior->GetBack();
1977           
1978                                BspNodeGeometry *fGeom = new BspNodeGeometry();
1979                                BspNodeGeometry *bGeom = new BspNodeGeometry();
1980
1981                                geom->SplitGeometry(*fGeom,
1982                                                                        *bGeom,
1983                                                                        interior->GetPlane(),
1984                                                                        mBox,
1985                                                                        mEpsilon);
1986               
1987                                if (cf == Polygon3::FRONT_SIDE)
1988                                {
1989                                        nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
1990                                        DEL_PTR(bGeom);
1991                                }
1992                                else
1993                                {
1994                                        if (cf == Polygon3::BACK_SIDE)
1995                                        {
1996                                                nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
1997                                                DEL_PTR(fGeom);
1998                                        }
1999                                        else
2000                                        {       // random decision
2001                                                nodeStack.push(bspNodePair(front, fGeom));
2002                                                nodeStack.push(bspNodePair(back, bGeom));
2003                                        }
2004                                }
2005                        }
2006                }
2007
2008                DEL_PTR(geom);
2009        }
2010
2011        return (int)neighbors.size();
2012}
2013
2014
2015BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
2016{
2017    stack<BspNode *> nodeStack;
2018        nodeStack.push(mRoot);
2019
2020        int mask = rand();
2021
2022        while (!nodeStack.empty())
2023        {
2024                BspNode *node = nodeStack.top();
2025                nodeStack.pop();
2026
2027                if (node->IsLeaf())
2028                {
2029                        return dynamic_cast<BspLeaf *>(node);
2030                }
2031                else
2032                {
2033                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2034                        BspNode *next;
2035                        BspNodeGeometry geom;
2036
2037                        // todo: not very efficient: constructs full cell everytime
2038                        ConstructGeometry(interior, geom);
2039
2040                        const int cf =
2041                                Polygon3::ClassifyPlane(geom.mPolys, halfspace, mEpsilon);
2042
2043                        if (cf == Polygon3::BACK_SIDE)
2044                                next = interior->GetFront();
2045                        else
2046                                if (cf == Polygon3::FRONT_SIDE)
2047                                        next = interior->GetFront();
2048                        else
2049                        {
2050                                // random decision
2051                                if (mask & 1)
2052                                        next = interior->GetBack();
2053                                else
2054                                        next = interior->GetFront();
2055                                mask = mask >> 1;
2056                        }
2057
2058                        nodeStack.push(next);
2059                }
2060        }
2061
2062        return NULL;
2063}
2064
2065BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
2066{
2067        stack<BspNode *> nodeStack;
2068
2069        nodeStack.push(mRoot);
2070
2071        int mask = rand();
2072
2073        while (!nodeStack.empty())
2074        {
2075                BspNode *node = nodeStack.top();
2076                nodeStack.pop();
2077
2078                if (node->IsLeaf())
2079                {
2080                        if ( (!onlyUnmailed || !node->Mailed()) )
2081                                return dynamic_cast<BspLeaf *>(node);
2082                }
2083                else
2084                {
2085                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2086
2087                        // random decision
2088                        if (mask & 1)
2089                                nodeStack.push(interior->GetBack());
2090                        else
2091                                nodeStack.push(interior->GetFront());
2092
2093                        mask = mask >> 1;
2094                }
2095        }
2096
2097        return NULL;
2098}
2099
2100int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
2101{
2102        int pvsSize = 0;
2103
2104        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2105
2106        Intersectable::NewMail();
2107
2108        for (rit = rays.begin(); rit != rays.end(); ++ rit)
2109        {
2110                VssRay *ray = (*rit).mRay;
2111
2112                if (ray->mOriginObject)
2113                {
2114                        if (!ray->mOriginObject->Mailed())
2115                        {
2116                                ray->mOriginObject->Mail();
2117                                ++ pvsSize;
2118                        }
2119                }
2120                if (ray->mTerminationObject)
2121                {
2122                        if (!ray->mTerminationObject->Mailed())
2123                        {
2124                                ray->mTerminationObject->Mail();
2125                                ++ pvsSize;
2126                        }
2127                }
2128        }
2129
2130        return pvsSize;
2131}
2132
2133float VspBspTree::GetEpsilon() const
2134{
2135        return mEpsilon;
2136}
2137
2138
2139int VspBspTree::SplitPolygons(const Plane3 &plane,
2140                                                          PolygonContainer &polys,
2141                                                          PolygonContainer &frontPolys,
2142                                                          PolygonContainer &backPolys,
2143                                                          PolygonContainer &coincident) const
2144{
2145        int splits = 0;
2146
2147        while (!polys.empty())
2148        {
2149                Polygon3 *poly = polys.back();
2150                polys.pop_back();
2151
2152                // classify polygon
2153                const int cf = poly->ClassifyPlane(plane, mEpsilon);
2154
2155                switch (cf)
2156                {
2157                        case Polygon3::COINCIDENT:
2158                                coincident.push_back(poly);
2159                                break;
2160                        case Polygon3::FRONT_SIDE:
2161                                frontPolys.push_back(poly);
2162                                break;
2163                        case Polygon3::BACK_SIDE:
2164                                backPolys.push_back(poly);
2165                                break;
2166                        case Polygon3::SPLIT:
2167                                backPolys.push_back(poly);
2168                                frontPolys.push_back(poly);
2169                                ++ splits;
2170                                break;
2171                        default:
2172                Debug << "SHOULD NEVER COME HERE\n";
2173                                break;
2174                }
2175        }
2176
2177        return splits;
2178}
2179
2180
2181int VspBspTree::CastLineSegment(const Vector3 &origin,
2182                                                                const Vector3 &termination,
2183                                                                vector<ViewCell *> &viewcells)
2184{
2185        int hits = 0;
2186        stack<BspRayTraversalData> tStack;
2187
2188        float mint = 0.0f, maxt = 1.0f;
2189
2190        Intersectable::NewMail();
2191
2192        Vector3 entp = origin;
2193        Vector3 extp = termination;
2194
2195        BspNode *node = mRoot;
2196        BspNode *farChild = NULL;
2197
2198        float t;
2199        while (1)
2200        {
2201                if (!node->IsLeaf())
2202                {
2203                        BspInterior *in = dynamic_cast<BspInterior *>(node);
2204
2205                        Plane3 splitPlane = in->GetPlane();
2206                       
2207                        const int entSide = splitPlane.Side(entp);
2208                        const int extSide = splitPlane.Side(extp);
2209
2210                        if (entSide < 0)
2211                        {
2212                                node = in->GetBack();
2213                                // plane does not split ray => no far child
2214                                if (extSide <= 0)
2215                                        continue;
2216
2217                                farChild = in->GetFront(); // plane splits ray
2218                        }
2219                        else if (entSide > 0)
2220                        {
2221                                node = in->GetFront();
2222
2223                                if (extSide >= 0) // plane does not split ray => no far child
2224                                        continue;
2225
2226                                farChild = in->GetBack(); // plane splits ray
2227                        }
2228                        else // ray end point on plane
2229                        {       // NOTE: what to do if ray is coincident with plane?
2230                                if (extSide < 0)
2231                                        node = in->GetBack();
2232                                else
2233                                        node = in->GetFront();
2234                                                               
2235                                continue; // no far child
2236                        }
2237
2238                        // push data for far child
2239                        tStack.push(BspRayTraversalData(farChild, extp));
2240
2241                        // find intersection of ray segment with plane
2242                        extp = splitPlane.FindIntersection(origin, extp, &t);
2243                }
2244                else
2245                {
2246                        // reached leaf => intersection with view cell
2247                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2248
2249                        if (!leaf->GetViewCell()->Mailed())
2250                        {
2251                                viewcells.push_back(leaf->GetViewCell());
2252                                leaf->GetViewCell()->Mail();
2253                                ++ hits;
2254                        }
2255
2256                        //-- fetch the next far child from the stack
2257                        if (tStack.empty())
2258                                break;
2259
2260                        entp = extp;
2261                       
2262                        BspRayTraversalData &s = tStack.top();
2263
2264                        node = s.mNode;
2265                        extp = s.mExitPoint;
2266
2267                        tStack.pop();
2268                }
2269        }
2270
2271        return hits;
2272}
2273
2274int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
2275{
2276        std::deque<BspNode *> path1;
2277        BspNode *p1 = n1;
2278
2279        // create path from node 1 to root
2280        while (p1)
2281        {
2282                if (p1 == n2) // second node on path
2283                        return (int)path1.size();
2284
2285                path1.push_front(p1);
2286                p1 = p1->GetParent();
2287        }
2288
2289        int depth = n2->GetDepth();
2290        int d = depth;
2291
2292        BspNode *p2 = n2;
2293
2294        // compare with same depth
2295        while (1)
2296        {
2297                if ((d < (int)path1.size()) && (p2 == path1[d]))
2298                        return (depth - d) + ((int)path1.size() - 1 - d);
2299
2300                -- d;
2301                p2 = p2->GetParent();
2302        }
2303
2304        return 0; // never come here
2305}
2306
2307BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
2308{
2309        if (node->IsLeaf())
2310                return node;
2311
2312        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2313
2314        BspNode *front = CollapseTree(interior->GetFront(), collapsed);
2315        BspNode *back = CollapseTree(interior->GetBack(), collapsed);
2316
2317        if (front->IsLeaf() && back->IsLeaf())
2318        {
2319                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
2320                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
2321
2322                //-- collapse tree
2323                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
2324                {
2325                        BspViewCell *vc = frontLeaf->GetViewCell();
2326
2327                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
2328                        leaf->SetTreeValid(frontLeaf->TreeValid());
2329
2330                        // replace a link from node's parent
2331                        if (leaf->GetParent())
2332                                leaf->GetParent()->ReplaceChildLink(node, leaf);
2333                        else
2334                                mRoot = leaf;
2335
2336                        ++ collapsed;
2337                        delete interior;
2338
2339                        return leaf;
2340                }
2341        }
2342
2343        return node;
2344}
2345
2346
2347int VspBspTree::CollapseTree()
2348{
2349        int collapsed = 0;
2350       
2351        (void)CollapseTree(mRoot, collapsed);
2352
2353        // revalidate leaves
2354        RepairViewCellsLeafLists();
2355
2356        return collapsed;
2357}
2358
2359
2360void VspBspTree::RepairViewCellsLeafLists()
2361{
2362        // list not valid anymore => clear
2363        stack<BspNode *> nodeStack;
2364        nodeStack.push(mRoot);
2365
2366        ViewCell::NewMail();
2367
2368        while (!nodeStack.empty())
2369        {
2370                BspNode *node = nodeStack.top();
2371                nodeStack.pop();
2372
2373                if (node->IsLeaf())
2374                {
2375                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2376
2377                        BspViewCell *viewCell = leaf->GetViewCell();
2378
2379                        if (!viewCell->Mailed())
2380                        {
2381                                viewCell->mLeaves.clear();
2382                                viewCell->Mail();
2383                        }
2384
2385                        viewCell->mLeaves.push_back(leaf);
2386                }
2387                else
2388                {
2389                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2390
2391                        nodeStack.push(interior->GetFront());
2392                        nodeStack.push(interior->GetBack());
2393                }
2394        }
2395}
2396
2397
2398typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
2399
2400
2401int VspBspTree::CastBeam(Beam &beam)
2402{
2403    stack<bspNodePair> nodeStack;
2404        BspNodeGeometry *rgeom = new BspNodeGeometry();
2405        ConstructGeometry(mRoot, *rgeom);
2406
2407        nodeStack.push(bspNodePair(mRoot, rgeom));
2408 
2409        ViewCell::NewMail();
2410
2411        while (!nodeStack.empty())
2412        {
2413                BspNode *node = nodeStack.top().first;
2414                BspNodeGeometry *geom = nodeStack.top().second;
2415                nodeStack.pop();
2416               
2417                AxisAlignedBox3 box;
2418                box.Initialize();
2419                geom->IncludeInBox(box);
2420
2421                const int side = beam.ComputeIntersection(box);
2422               
2423                switch (side)
2424                {
2425                case -1:
2426                        CollectViewCells(node, true, beam.mViewCells, true);
2427                        break;
2428                case 0:
2429                       
2430                        if (node->IsLeaf())
2431                        {
2432                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2433                       
2434                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2435                                {
2436                                        leaf->GetViewCell()->Mail();
2437                                        beam.mViewCells.push_back(leaf->GetViewCell());
2438                                }
2439                        }
2440                        else
2441                        {
2442                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
2443                       
2444                                BspNode *first = interior->GetFront();
2445                                BspNode *second = interior->GetBack();
2446           
2447                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
2448                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
2449
2450                                geom->SplitGeometry(*firstGeom,
2451                                                                        *secondGeom,
2452                                                                        interior->GetPlane(),
2453                                                                        mBox,
2454                                                                        mEpsilon);
2455
2456                                // decide on the order of the nodes
2457                                if (DotProd(beam.mPlanes[0].mNormal,
2458                                        interior->GetPlane().mNormal) > 0)
2459                                {
2460                                        swap(first, second);
2461                                        swap(firstGeom, secondGeom);
2462                                }
2463
2464                                nodeStack.push(bspNodePair(first, firstGeom));
2465                                nodeStack.push(bspNodePair(second, secondGeom));
2466                        }
2467                       
2468                        break;
2469                default:
2470                        // default: cull
2471                        break;
2472                }
2473               
2474                DEL_PTR(geom);
2475               
2476        }
2477
2478        return (int)beam.mViewCells.size();
2479}
2480
2481
2482bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) const
2483{
2484        //-- change pointer to view cells of all leaves associated
2485        //-- with the previous view cells
2486        BspViewCell *fVc = l1->GetViewCell();
2487        BspViewCell *bVc = l2->GetViewCell();
2488
2489        BspViewCell *vc = dynamic_cast<BspViewCell *>(
2490                mViewCellsManager->MergeViewCells(*fVc, *bVc));
2491
2492        // if merge was unsuccessful
2493        if (!vc) return false;
2494
2495        // set new size of view cell
2496        if (mUseAreaForPvs)
2497                vc->SetArea(fVc->GetArea() + bVc->GetArea());
2498        else
2499                vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
2500       
2501        vector<BspLeaf *> fLeaves = fVc->mLeaves;
2502        vector<BspLeaf *> bLeaves = bVc->mLeaves;
2503
2504        vector<BspLeaf *>::const_iterator it;
2505
2506        //-- change view cells of all the other leaves the view cell belongs to
2507        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2508        {
2509                (*it)->SetViewCell(vc);
2510                vc->mLeaves.push_back(*it);
2511        }
2512
2513        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2514        {
2515                (*it)->SetViewCell(vc);
2516                vc->mLeaves.push_back(*it);
2517        }
2518
2519        vc->Mail();
2520
2521        // clean up old view cells
2522        DEL_PTR(fVc);
2523        DEL_PTR(bVc);
2524
2525        return true;
2526}
2527
2528
2529void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2530{
2531        mViewCellsManager = vcm;
2532}
2533
2534
2535int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
2536{
2537        BspLeaf::NewMail();
2538       
2539        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2540
2541        int candidates = 0;
2542
2543        // find merge candidates and push them into queue
2544        for (it = leaves.begin(); it != it_end; ++ it)
2545        {
2546                BspLeaf *leaf = *it;
2547               
2548                /// create leaf pvs (needed for post processing
2549                leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
2550
2551                BspMergeCandidate::sOverallCost +=
2552                        leaf->mProbability * leaf->mPvs->GetSize();
2553
2554                // the same leaves must not be part of two merge candidates
2555                leaf->Mail();
2556                vector<BspLeaf *> neighbors;
2557                FindNeighbors(leaf, neighbors, true);
2558
2559                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
2560
2561                // TODO: test if at least one ray goes from one leaf to the other
2562                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2563                {
2564                        if ((*nit)->GetViewCell() != leaf->GetViewCell())
2565                        {
2566                                mMergeQueue.push(BspMergeCandidate(leaf, *nit));
2567                                ++ candidates;
2568                        }
2569                }
2570        }
2571
2572        Debug << "found " << candidates << " new merge candidates" << endl;
2573
2574        return (int)leaves.size();
2575}
2576
2577
2578int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
2579{
2580        vector<BspRay *> bspRays;
2581
2582        ViewCell::NewMail();
2583        long startTime = GetTime();
2584        ConstructBspRays(bspRays, rays);
2585        Debug << (int)bspRays.size() << " bsp rays constructed in "
2586                  << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
2587
2588        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
2589        vector<BspIntersection>::const_iterator iit;
2590
2591        int numLeaves = 0;
2592       
2593        BspLeaf::NewMail();
2594
2595        for (int i = 0; i < (int)bspRays.size(); ++ i)
2596        { 
2597                BspRay *ray = bspRays[i];
2598       
2599                // traverse leaves stored in the rays and compare and
2600                // merge consecutive leaves (i.e., the neighbors in the tree)
2601                if (ray->intersections.size() < 2)
2602                        continue;
2603         
2604                iit = ray->intersections.begin();
2605                BspLeaf *leaf = (*(iit ++)).mLeaf;
2606               
2607                // create leaf pvs (needed for post processing)
2608                if (!leaf->mPvs)
2609                {
2610                        leaf->mPvs =
2611                                new ObjectPvs(leaf->GetViewCell()->GetPvs());
2612
2613                        BspMergeCandidate::sOverallCost +=
2614                                leaf->mProbability * leaf->mPvs->GetSize();
2615                       
2616                        ++ numLeaves;
2617                }
2618               
2619                // traverse intersections
2620                // consecutive leaves are neighbors => add them to queue
2621                for (; iit != ray->intersections.end(); ++ iit)
2622                {
2623                        // next pair
2624                        BspLeaf *prevLeaf = leaf;
2625            leaf = (*iit).mLeaf;
2626
2627                        // view space not valid or same view cell
2628                        if (!leaf->TreeValid() || !prevLeaf->TreeValid() ||
2629                                (leaf->GetViewCell() == prevLeaf->GetViewCell()))
2630                                continue;
2631
2632            // create leaf pvs (needed for post processing)
2633                        if (!leaf->mPvs)
2634                        {
2635                                leaf->mPvs =
2636                                        new ObjectPvs(leaf->GetViewCell()->GetPvs());
2637                               
2638                                BspMergeCandidate::sOverallCost +=
2639                                        leaf->mProbability * leaf->mPvs->GetSize();
2640
2641                                ++ numLeaves;
2642                        }
2643               
2644                        vector<BspLeaf *> &neighbors = neighborMap[leaf];
2645                       
2646                        bool found = false;
2647
2648                        // both leaves inserted in queue already =>
2649                        // look if double pair already exists
2650                        if (leaf->Mailed() && prevLeaf->Mailed())
2651                        {
2652                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
2653                               
2654                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
2655                                        if (*it == prevLeaf)
2656                                                found = true; // already in queue
2657                        }
2658               
2659                        if (!found)
2660                        {
2661                                // this pair is not in map already
2662                                // => insert into the neighbor map and the queue
2663                                neighbors.push_back(prevLeaf);
2664                                neighborMap[prevLeaf].push_back(leaf);
2665
2666                                leaf->Mail();
2667                                prevLeaf->Mail();
2668               
2669                                mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
2670                        }
2671        }
2672        }
2673        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
2674        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
2675        Debug << "leaves in queue: " << numLeaves << endl;
2676        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
2677
2678        CLEAR_CONTAINER(bspRays);
2679
2680        //-- collect the leaves which haven't been found by ray casting
2681        if (0)
2682        {
2683                cout << "finding additional merge candidates using geometry" << endl;
2684                vector<BspLeaf *> leaves;
2685                CollectLeaves(leaves, true);
2686                Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
2687                CollectMergeCandidates(leaves);
2688        }
2689
2690        return numLeaves;
2691}
2692
2693
2694void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
2695                                                                  const VssRayContainer &rays)
2696{
2697        VssRayContainer::const_iterator it, it_end = rays.end();
2698
2699        for (it = rays.begin(); it != rays.end(); ++ it)
2700        {
2701                VssRay *vssRay = *it;
2702                BspRay *ray = new BspRay(vssRay);
2703
2704                ViewCellContainer viewCells;
2705
2706                Ray hray(*vssRay);
2707                float tmin = 0, tmax = 1.0;
2708                // matt TODO: remove this!!
2709                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
2710                if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
2711                        continue;
2712
2713                Vector3 origin = hray.Extrap(tmin);
2714                Vector3 termination = hray.Extrap(tmax);
2715       
2716                // cast line segment to get intersections with bsp leaves
2717                CastLineSegment(origin, termination, viewCells);
2718
2719                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2720                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2721                {
2722                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
2723                        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2724                        //NOTE: not sorted!
2725                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
2726                        {
2727                                ray->intersections.push_back(BspIntersection(0, *it));
2728                        }
2729                }
2730
2731                bspRays.push_back(ray);
2732        }
2733}
2734
2735
2736int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
2737{
2738        BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
2739        BspMergeCandidate::sUseArea = mUseAreaForPvs;
2740
2741        MergeStatistics mergeStats;
2742        mergeStats.Start();
2743        // TODO: REMOVE LATER for performance!
2744        const bool showMergeStats = false;
2745        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
2746        long startTime = GetTime();
2747
2748        if (mUseRaysForMerge)
2749        {
2750                cout << "collecting merge candidates (rays) ... ";
2751                mergeStats.nodes = CollectMergeCandidates(rays);
2752                cout << "fininshed collecting candidates" << endl;
2753        }
2754        else
2755        {
2756                vector<BspLeaf *> leaves;
2757                CollectLeaves(leaves);
2758                mergeStats.nodes = CollectMergeCandidates(leaves);
2759        }
2760       
2761
2762        mergeStats.collectTime = TimeDiff(startTime, GetTime());
2763        mergeStats.candidates = (int)mMergeQueue.size();
2764        startTime = GetTime();
2765
2766        int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
2767        int pass = 0;
2768        const int nextPass = 200;
2769
2770        cout << "starting merge ... ";
2771
2772        //-- use priority queue to merge leaf pairs
2773        while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
2774                   (mMergeQueue.top().GetMergeCost() <
2775                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2776        {
2777                /*Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
2778                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost
2779                          << " max ratio: " << mMergeMaxCostRatio << endl;*/
2780                BspMergeCandidate mc = mMergeQueue.top();
2781                mMergeQueue.pop();
2782
2783                // both view cells equal!
2784                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2785                        continue;
2786
2787                if (mc.Valid())
2788                {
2789                        ViewCell::NewMail();
2790                        const float mergeCost = mc.GetMergeCost();
2791
2792                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2793                                               
2794                       
2795                        // increase absolute merge cost
2796                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2797                       
2798
2799                        if (showMergeStats)
2800                        {
2801                                if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
2802                                        ++ mergeStats.siblings;
2803
2804                                const int dist =
2805                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
2806                                if (dist > mergeStats.maxTreeDist)
2807                                        mergeStats.maxTreeDist = dist;
2808                                mergeStats.accTreeDist += dist;
2809
2810
2811                                if (((mergeStats.merged % nextPass) == 0) || (nViewCells == mMergeMinViewCells))
2812                                {
2813                                        mStats
2814                                                << "#Pass\n" << pass ++ << endl
2815                                                << "#Merged\n" << mergeStats.merged << endl
2816                                                << "#Viewcells\n" << nViewCells << endl
2817                                                << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
2818                                                << "#CurrentCost\n" << mergeCost << endl
2819                                                << "#RelCost\n" << mc.GetMergeCost() / BspMergeCandidate::sOverallCost << endl
2820                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl;
2821
2822                                        cout << "exporting view cells ... ";
2823                                        ViewCellContainer viewCells;   
2824                                        CollectViewCells(mRoot, false, viewCells);
2825                       
2826                                       
2827                                        char s[64];
2828                                        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
2829                                        Exporter *exporter = Exporter::GetExporter(s);
2830                               
2831                                        if (exporter)
2832                                        {
2833                                                exporter->ExportGeometry(objects);
2834                                                Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
2835                                                ViewCellContainer::const_iterator it, it_end = viewCells.end();
2836               
2837                                                for (it = viewCells.begin(); it != it_end; ++ it)
2838                                                {
2839                                                        mViewCellsManager->ExportVcGeometry(exporter, *it);
2840                                                }
2841                                       
2842                                                delete exporter;
2843                                        }
2844                                        cout << "finished " << endl;
2845                                }
2846                        }
2847
2848                        -- nViewCells;
2849                        ++ mergeStats.merged;
2850                }
2851                // merge candidate not valid, because one of the leaves was already
2852                // merged with another one => validate and reinsert into queue
2853                else
2854                {
2855                        mc.SetValid();
2856                        mMergeQueue.push(mc);
2857                }
2858        }
2859        cout << "finished merge" << endl;
2860        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
2861        mergeStats.Stop();
2862
2863        if (showMergeStats)
2864                Debug << mergeStats << endl << endl;
2865       
2866
2867        //TODO: should return sample contributions?
2868        return mergeStats.merged;
2869}
2870
2871
2872ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
2873{
2874  if (mRoot == NULL)
2875        return NULL;
2876 
2877  stack<BspNode *> nodeStack;
2878  nodeStack.push(mRoot);
2879 
2880  ViewCell *viewcell = NULL;
2881 
2882  while (!nodeStack.empty())  {
2883        BspNode *node = nodeStack.top();
2884        nodeStack.pop();
2885       
2886        if (node->IsLeaf()) {
2887          viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
2888          break;
2889        } else {
2890         
2891          BspInterior *interior = dynamic_cast<BspInterior *>(node);
2892               
2893          // random decision
2894          if (interior->GetPlane().Side(point) < 0)
2895                nodeStack.push(interior->GetBack());
2896          else
2897                nodeStack.push(interior->GetFront());
2898        }
2899  }
2900 
2901  return viewcell;
2902}
2903
2904
2905int VspBspTree::RefineViewCells(const VssRayContainer &rays)
2906{
2907        int shuffled = 0;
2908
2909        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
2910        BspLeaf::NewMail();
2911
2912        // Use priority queue of remaining leaf pairs
2913        // These candidates either share the same view cells or
2914        // are border leaves which share a boundary.
2915        // We test if they can be shuffled, i.e.,
2916        // either one leaf is made part of one view cell or the other
2917        // leaf is made part of the other view cell. It is tested if the
2918        // remaining view cells are "better" than the old ones.
2919        while (!mMergeQueue.empty())
2920        {
2921                BspMergeCandidate mc = mMergeQueue.top();
2922                mMergeQueue.pop();
2923
2924                // both view cells equal or already shuffled
2925                if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) ||
2926                        (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
2927                        continue;
2928               
2929                // candidate for shuffling
2930                const bool wasShuffled =
2931                        ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
2932               
2933                //-- stats
2934                if (wasShuffled)
2935                        ++ shuffled;
2936        }
2937
2938        return shuffled;
2939}
2940
2941
2942inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2943{
2944        return pvs1.AddPvs(pvs2);
2945}
2946
2947/*inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
2948{
2949        ObjectPvs pvs;
2950        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2951        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
2952                if (*it != l)
2953                        pvs.AddPvs(*(*it)->mPvs);
2954        return pvs.GetSize();
2955}*/
2956
2957inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
2958{
2959        return pvs1.SubtractPvs(pvs2);
2960}
2961
2962
2963float VspBspTree::GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const
2964{
2965        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
2966        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
2967        const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
2968
2969        if (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())
2970                return 1e15f;
2971
2972        float p1, p2;
2973
2974    if (mUseAreaForPvs)
2975        {
2976                p1 = vc1->GetArea() - leaf->mProbability;
2977                p2 = vc2->GetArea() + leaf->mProbability;
2978        }
2979        else
2980        {
2981                p1 = vc1->GetVolume() - leaf->mProbability;
2982                p2 = vc2->GetVolume() + leaf->mProbability;
2983        }
2984
2985        const float cost1 = pvs1 * p1;
2986        const float cost2 = pvs2 * p2;
2987
2988        return cost1 + cost2;
2989}
2990
2991
2992void VspBspTree::ShuffleLeaf(BspLeaf *leaf,
2993                                                         BspViewCell *vc1,
2994                                                         BspViewCell *vc2) const
2995{
2996        // compute new pvs and area
2997        vc1->GetPvs().SubtractPvs(*leaf->mPvs);
2998        vc2->GetPvs().AddPvs(*leaf->mPvs);
2999       
3000        if (mUseAreaForPvs)
3001        {
3002                vc1->SetArea(vc1->GetArea() - leaf->mProbability);
3003                vc2->SetArea(vc2->GetArea() + leaf->mProbability);
3004        }
3005        else
3006        {
3007                vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
3008                vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
3009        }
3010
3011        /// add to second view cell
3012        vc2->mLeaves.push_back(leaf);
3013
3014        // erase leaf from old view cell
3015        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
3016
3017        for (; *it != leaf; ++ it);
3018        vc1->mLeaves.erase(it);
3019
3020        /*vc1->GetPvs().mEntries.clear();
3021        for (; it != vc1->mLeaves.end(); ++ it)
3022        {
3023                if (*it == leaf)
3024                        vc1->mLeaves.erase(it);
3025                else
3026                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
3027        }*/
3028
3029        leaf->SetViewCell(vc2); // finally change view cell
3030}
3031
3032
3033bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
3034{
3035        BspViewCell *vc1 = leaf1->GetViewCell();
3036        BspViewCell *vc2 = leaf2->GetViewCell();
3037
3038        float cost1;
3039        float cost2;
3040
3041        if (mUseAreaForPvs)
3042        {
3043                cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
3044                cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
3045        }
3046        else
3047        {
3048                cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
3049                cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
3050        }
3051
3052        const float oldCost = cost1 + cost2;
3053       
3054        float shuffledCost1 = Limits::Infinity;
3055        float shuffledCost2 = Limits::Infinity;
3056
3057        // the view cell should not be empty after the shuffle
3058        if (vc1->mLeaves.size() > 1)
3059                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
3060        if (vc2->mLeaves.size() > 1)
3061                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
3062
3063        // shuffling unsuccessful
3064        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
3065                return false;
3066       
3067        if (shuffledCost1 < shuffledCost2)
3068        {
3069                ShuffleLeaf(leaf1, vc1, vc2);
3070                leaf1->Mail();
3071        }
3072        else
3073        {
3074                ShuffleLeaf(leaf2, vc2, vc1);
3075                leaf2->Mail();
3076        }
3077
3078        return true;
3079}
3080
3081
3082bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
3083{
3084        BspNode *node = mRoot;
3085
3086        while (1)
3087        {
3088                // early exit
3089                if (node->TreeValid())
3090                        return true;
3091
3092                if (node->IsLeaf())
3093                        return false;
3094                       
3095                BspInterior *in = dynamic_cast<BspInterior *>(node);
3096                                       
3097                if (in->GetPlane().Side(viewPoint) <= 0)
3098                {
3099                        node = in->GetBack();
3100                }
3101                else
3102                {
3103                        node = in->GetFront();
3104                }
3105        }
3106
3107        // should never come here
3108        return false;
3109}
3110
3111
3112void VspBspTree::PropagateUpValidity(BspNode *node)
3113{
3114        while (!node->IsRoot() && node->GetParent()->TreeValid())
3115        {
3116                node = node->GetParent();
3117                node->SetTreeValid(false);
3118        }
3119}
3120
3121
3122bool VspBspTree::Export(ofstream &stream)
3123{
3124        ExportNode(mRoot, stream);
3125
3126        return true;
3127}
3128
3129
3130void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
3131{
3132        if (node->IsLeaf())
3133        {
3134                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
3135                       
3136                int id = -1;
3137                if (leaf->GetViewCell() != mOutOfBoundsCell)
3138                        id = leaf->GetViewCell()->GetId();
3139
3140                stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
3141        }
3142        else
3143        {
3144                BspInterior *interior = dynamic_cast<BspInterior *>(node);
3145       
3146                Plane3 plane = interior->GetPlane();
3147                stream << "<Interior plane=\"" << plane.mNormal.x << " "
3148                           << plane.mNormal.y << " " << plane.mNormal.z << " "
3149                           << plane.mD << "\">" << endl;
3150
3151                ExportNode(interior->GetBack(), stream);
3152                ExportNode(interior->GetFront(), stream);
3153
3154                stream << "</Interior>" << endl;
3155        }
3156}
3157
3158/************************************************************************/
3159/*                BspMergeCandidate implementation                      */
3160/************************************************************************/
3161
3162
3163BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
3164mMergeCost(0),
3165mLeaf1(l1),
3166mLeaf2(l2),
3167mLeaf1Id(l1->GetViewCell()->mMailbox),
3168mLeaf2Id(l2->GetViewCell()->mMailbox)
3169{
3170        EvalMergeCost();
3171}
3172
3173
3174float BspMergeCandidate::GetCost(ViewCell *vc) const
3175{
3176        if (sUseArea)
3177                return vc->GetPvs().GetSize() * vc->GetArea();
3178
3179        return vc->GetPvs().GetSize() * vc->GetVolume();
3180}
3181
3182
3183float BspMergeCandidate::GetLeaf1Cost() const
3184{
3185        BspViewCell *vc = mLeaf1->GetViewCell();
3186        return GetCost(vc);
3187}
3188
3189
3190float BspMergeCandidate::GetLeaf2Cost() const
3191{
3192        BspViewCell *vc = mLeaf2->GetViewCell();
3193        return GetCost(vc);
3194}
3195
3196
3197void BspMergeCandidate::EvalMergeCost()
3198{
3199        //-- compute pvs difference
3200        BspViewCell *vc1 = mLeaf1->GetViewCell();
3201        BspViewCell *vc2 = mLeaf2->GetViewCell();
3202
3203        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
3204        const int newPvs = diff1 + vc1->GetPvs().GetSize();
3205
3206        //-- compute ratio of old cost
3207        //   (i.e., added size of left and right view cell times pvs size)
3208        //   to new rendering cost (i.e, size of merged view cell times pvs size)
3209        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
3210
3211    const float newCost = sUseArea ?
3212                (float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
3213                (float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
3214
3215
3216        if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
3217        {
3218                mMergeCost = 1e15f;
3219        }
3220        else
3221        {
3222                mMergeCost = newCost - oldCost;
3223        }
3224}
3225
3226
3227void BspMergeCandidate::SetLeaf1(BspLeaf *l)
3228{
3229        mLeaf1 = l;
3230}
3231
3232
3233void BspMergeCandidate::SetLeaf2(BspLeaf *l)
3234{
3235        mLeaf2 = l;
3236}
3237
3238
3239BspLeaf *BspMergeCandidate::GetLeaf1()
3240{
3241        return mLeaf1;
3242}
3243
3244
3245BspLeaf *BspMergeCandidate::GetLeaf2()
3246{
3247        return mLeaf2;
3248}
3249
3250
3251bool BspMergeCandidate::Valid() const
3252{
3253        return
3254                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
3255                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
3256}
3257
3258
3259float BspMergeCandidate::GetMergeCost() const
3260{
3261        return mMergeCost;
3262}
3263
3264
3265void BspMergeCandidate::SetValid()
3266{
3267        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
3268        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
3269
3270        EvalMergeCost();
3271}
3272
3273
3274/************************************************************************/
3275/*                  MergeStatistics implementation                      */
3276/************************************************************************/
3277
3278
3279void MergeStatistics::Print(ostream &app) const
3280{
3281        app << "===== Merge statistics ===============\n";
3282
3283        app << setprecision(4);
3284
3285        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
3286
3287        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
3288
3289        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
3290
3291        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
3292
3293        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
3294
3295        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
3296        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
3297
3298        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
3299
3300        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
3301
3302        app << "===== END OF BspTree statistics ==========\n";
3303}
Note: See TracBrowser for help on using the repository browser.