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

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