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

Revision 1020, 96.4 KB checked in by mattausch, 18 years ago (diff)

worked on view-object space partition
fixed some loading bugs
fixeds some exporting bugs using line segments
enabling other methods for view space sampling in ViewCellsManager? OBJECT_DIRECTION_BASED_DISTRIBUTION)
added class interface for a sampling strategy

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