source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 602

Revision 602, 71.7 KB checked in by mattausch, 18 years ago (diff)

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