source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp @ 676

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