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

Revision 1919, 82.6 KB checked in by mattausch, 18 years ago (diff)

added mechanism for histogram on certain MB in hierarchymanager
no more bug in undersampling estimation
added sampling strategy to spatial box based (also for eval)
added testing scripts

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