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

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