source: obsolete/trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 612

Revision 612, 74.2 KB checked in by mattausch, 19 years ago (diff)

really last checkin before svn change

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