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

Revision 2575, 98.6 KB checked in by bittner, 17 years ago (diff)

big merge: preparation for havran ray caster, check if everything works

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