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

Revision 2588, 89.2 KB checked in by bittner, 17 years ago (diff)

sceneBox bugfix

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