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

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