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

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