source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp @ 1315

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