source: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp @ 1719

Revision 1719, 57.2 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "ViewCell.h"
6#include "Plane3.h"
7#include "HierarchyManager.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 "VspTree.h"
21#include "OspTree.h"
22#include "BvHierarchy.h"
23#include "ViewCell.h"
24
25
26namespace GtpVisibilityPreprocessor {
27
28
29#define USE_FIXEDPOINT_T 0
30
31
32/*******************************************************************/
33/*              class HierarchyManager implementation              */
34/*******************************************************************/
35
36
37HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
38mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
39mOspTree(NULL),
40mBvHierarchy(NULL)
41{
42        switch(mObjectSpaceSubdivisionType)
43        {
44        case KD_BASED_OBJ_SUBDIV:
45                mOspTree = new OspTree();
46                mOspTree->mVspTree = mVspTree;
47                mOspTree->mHierarchyManager = this;
48                break;
49        case BV_BASED_OBJ_SUBDIV:
50        mBvHierarchy = new BvHierarchy();
51                mBvHierarchy->mHierarchyManager = this;
52                break;
53        default:
54                break;
55        }
56
57        // hierarchy manager links view space partition and object space partition
58        mVspTree = new VspTree();
59        mVspTree->mHierarchyManager = this;
60       
61        mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
62        ParseEnvironment();
63}
64
65
66HierarchyManager::HierarchyManager(KdTree *kdTree):
67mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
68mBvHierarchy(NULL)
69{
70        mOspTree = new OspTree(*kdTree);
71        mOspTree->mVspTree = mVspTree;
72
73        mVspTree = new VspTree();
74        mVspTree->mHierarchyManager = this;
75
76        mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
77        ParseEnvironment();
78}
79
80
81void HierarchyManager::ParseEnvironment()
82{
83        Environment::GetSingleton()->GetFloatValue(
84                "Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
85        Environment::GetSingleton()->GetIntValue(
86                "Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
87
88        Environment::GetSingleton()->GetBoolValue(
89                "Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
90
91        Environment::GetSingleton()->GetIntValue(
92                "Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
93
94        Environment::GetSingleton()->GetIntValue(
95                "Hierarchy.Construction.type", mConstructionType);
96
97        Environment::GetSingleton()->GetIntValue(
98                "Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
99
100        Environment::GetSingleton()->GetIntValue(
101                "Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
102       
103        Environment::GetSingleton()->GetBoolValue(
104                "Hierarchy.Construction.repairQueue", mRepairQueue);
105
106        Environment::GetSingleton()->GetBoolValue(
107                "Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);
108
109        Environment::GetSingleton()->GetIntValue(
110                "Hierarchy.Construction.levels", mNumMultiLevels);
111
112        Environment::GetSingleton()->GetIntValue(
113                "Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
114       
115        Environment::GetSingleton()->GetIntValue(
116                "Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);
117
118        char subdivisionStatsLog[100];
119        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
120        mSubdivisionStats.open(subdivisionStatsLog);
121
122        Environment::GetSingleton()->GetBoolValue(
123                "Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);
124
125        Environment::GetSingleton()->GetBoolValue(
126                "Hierarchy.Construction.considerMemory", mConsiderMemory);
127
128        Environment::GetSingleton()->GetBoolValue(
129                "Hierarchy.Construction.considerMemory2", mConsiderMemory2);
130
131        Environment::GetSingleton()->GetFloatValue(
132                "Hierarchy.Termination.maxMemory", mTermMaxMemory);
133
134        if (1 && mConsiderMemory2)
135        {
136                mMemoryConst = (float)(sizeof(VspLeaf *) + sizeof (VspViewCell *));
137        }
138        else
139        {
140                Environment::GetSingleton()->GetFloatValue(
141                        "Hierarchy.Termination.memoryConst", mMemoryConst);
142        }
143
144        // compare to bytes
145        mTermMaxMemory *= (1024.0f * 1024.0f);
146
147        Debug << "******** Hierarchy Manager Options ***********" << endl;
148        Debug << "max leaves: " << mTermMaxLeaves << endl;
149        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
150        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
151        Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
152        Debug << "repair queue: " << mRepairQueue << endl;
153        Debug << "number of multilevels: " << mNumMultiLevels << endl;
154        Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
155        Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
156        Debug << "maximal allowed memory: " << mTermMaxMemory << endl;
157        Debug << "consider memory: " << mConsiderMemory << endl;
158        Debug << "consider memory2: " << mConsiderMemory << endl;
159        Debug << "mem const: " << mMemoryConst << endl;
160        Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
161        Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
162
163        switch (mConstructionType)
164        {
165        case 0:
166                Debug << "construction type: sequential" << endl;
167                break;
168        case 1:
169                Debug << "construction type: interleaved" << endl;
170                break;
171        case 2:
172                Debug << "construction type: gradient" << endl;
173                break;
174        case 3:
175                Debug << "construction type: multilevel" << endl;
176                break;
177        default:
178                Debug << "construction type " << mConstructionType << " unknown" << endl;
179                break;
180        }
181
182        //Debug << "min render cost " << mMinRenderCostDecrease << endl;
183        Debug << endl;
184}
185
186
187HierarchyManager::~HierarchyManager()
188{
189        DEL_PTR(mOspTree);
190        DEL_PTR(mVspTree);
191        DEL_PTR(mBvHierarchy);
192}
193
194
195int HierarchyManager::GetObjectSpaceSubdivisionType() const
196{
197        return mObjectSpaceSubdivisionType;
198}
199
200
201int HierarchyManager::GetViewSpaceSubdivisionType() const
202{
203        return mViewSpaceSubdivisionType;
204}
205
206
207void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
208{
209        mVspTree->SetViewCellsManager(vcm);
210
211        if (mOspTree)
212        {
213                mOspTree->SetViewCellsManager(vcm);
214        }
215        else if (mBvHierarchy)
216        {
217                mBvHierarchy->SetViewCellsManager(vcm);
218        }
219}
220
221
222void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
223{
224        mVspTree->SetViewCellsTree(vcTree);
225}
226
227
228VspTree *HierarchyManager::GetVspTree()
229{
230        return mVspTree;
231}
232
233/*
234AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
235{
236        return mVspTree->mBoundingBox;
237}*/
238
239
240AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
241{
242        switch (mObjectSpaceSubdivisionType)
243        {
244        case KD_BASED_OBJ_SUBDIV:
245                return mOspTree->mBoundingBox;
246        case BV_BASED_OBJ_SUBDIV:
247                return mBvHierarchy->mBoundingBox;
248        default:
249                // hack: empty box
250                return AxisAlignedBox3();
251        }
252}
253
254
255SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue)
256{
257        SubdivisionCandidate *splitCandidate = splitQueue.Top();
258        splitQueue.Pop();
259
260        return splitCandidate;
261}
262
263
264void HierarchyManager::EvalSubdivisionStats()
265{
266        // question: should I also add the mem usage of the hierarchies?
267        const float objectSpaceMem = 0;//GetObjectSpaceMemUsage();
268        const float viewSpaceMem = 0;//mVspTree->GetMemUsage();
269       
270        // calculate cost in MB
271        const float memoryCost = mHierarchyStats.mMemory  / float(1024 * 1024)
272                                                         + objectSpaceMem + viewSpaceMem;
273
274        //cout << "pvs entries " << mHierarchyStats.pvsEntries << endl;
275        AddSubdivisionStats(mHierarchyStats.Leaves(),
276                                                mHierarchyStats.mRenderCostDecrease,
277                                                mHierarchyStats.mTotalCost,
278                                                mHierarchyStats.mPvsEntries,
279                                                memoryCost,
280                                                1.0f / (mHierarchyStats.mTotalCost * memoryCost),
281                                                (float)mVspTree->mVspStats.Leaves() / (float)GetObjectSpaceSubdivisionLeaves()
282                                                );
283}
284
285
286void HierarchyManager::AddSubdivisionStats(const int splits,
287                                                                                   const float renderCostDecr,
288                                                                                   const float totalRenderCost,
289                                                                                   const int pvsEntries,
290                                                                                   const float memory,
291                                                                                   const float renderCostPerStorage,
292                                                                                   const float vspOspRatio)
293{
294        mSubdivisionStats
295                        << "#Splits\n" << splits << endl
296                        << "#RenderCostDecrease\n" << renderCostDecr << endl
297                        << "#TotalEntriesInPvs\n" << pvsEntries << endl
298                        << "#TotalRenderCost\n" << totalRenderCost << endl
299                        << "#Memory\n" << memory << endl
300                        << "#FpsPerMb\n" << renderCostPerStorage << endl
301                        << "#VspOspRatio\n" << vspOspRatio << endl;
302}
303
304
305bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
306{
307        const bool terminationCriteriaMet =
308                (0
309                || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
310                || (mHierarchyStats.mMemory >= mTermMaxMemory)
311                || candidate->GlobalTerminationCriteriaMet()
312                //|| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
313                //|| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
314                );
315
316#if GTP_DEBUG
317        if (terminationCriteriaMet)
318        {
319                Debug << "hierarchy global termination criteria met:" << endl;
320                Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
321                Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
322                Debug << "memory: " << mHierarchyStats.mMemory << " " << mTermMaxMemory << endl;
323        }
324#endif
325
326        return terminationCriteriaMet;
327}
328
329
330void HierarchyManager::Construct(const VssRayContainer &sampleRays,
331                                                                 const ObjectContainer &objects,
332                                                                 AxisAlignedBox3 *forcedViewSpace)
333{
334        mTimeStamp = 1;
335
336        switch (mConstructionType)
337        {
338        case MULTILEVEL:
339                ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
340                break;
341        case INTERLEAVED:
342        case SEQUENTIAL:
343                ConstructInterleaved(sampleRays, objects, forcedViewSpace);
344                break;
345        case GRADIENT:
346                ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
347                break;
348        default:
349                break;
350        }
351
352        // hack: should be different parameter name
353        if (mUseMultiLevelConstruction)
354        {
355                cout << "starting optimizing multilevel ... " << endl;
356                // try to optimize on the above hierarchy
357                OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
358               
359                cout << "finished" << endl;
360        }
361}
362
363
364void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
365                                                                                                                const ObjectContainer &objects,
366                                                                                                                AxisAlignedBox3 *forcedViewSpace)
367{
368        mHierarchyStats.Reset();
369        mHierarchyStats.Start();
370       
371        mHierarchyStats.mNodes = 2;
372
373        // create first nodes
374        mVspTree->Initialise(sampleRays, forcedViewSpace);
375        InitialiseObjectSpaceSubdivision(objects);
376
377        // hack: assume that object space can be seen from view space
378        mHierarchyStats.mTotalCost = mInitialRenderCost = (float)objects.size();
379        // only one entry for start
380        mHierarchyStats.mPvsEntries = 1;
381        mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
382
383        EvalSubdivisionStats();
384        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
385
386        const long startTime = GetTime();
387        cout << "Constructing view space / object space tree ... \n";
388       
389        SplitQueue objectSpaceQueue;
390        SplitQueue viewSpaceQueue;
391
392        int vspSteps = 0, ospSteps = 0;
393
394        // use sah for evaluating osp tree construction
395        // in the first iteration of the subdivision
396        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
397        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
398        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
399
400        // number of initial splits
401        const int minSteps = mMinStepsOfSameType;
402        const int maxSteps = mMaxStepsOfSameType;
403
404        SubdivisionCandidate *osc = PrepareObjectSpaceSubdivision(sampleRays, objects);
405        objectSpaceQueue.Push(osc);
406
407
408        /////////////////////////
409        // calulcate initial object space splits
410       
411        SubdivisionCandidateContainer dirtyList;
412
413        // subdivide object space first
414        // for first round, use sah splits. Once view space partition
415        // has started, use render cost heuristics instead
416        ospSteps = RunConstruction(objectSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
417        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
418
419        // create view space
420        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
421        viewSpaceQueue.Push(vsc);
422
423        dirtyList.clear();
424
425        // view space subdivision started
426        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
427
428        if (1)
429        {
430                // rather also start with 100 view space splits to avoid initial bias.
431                vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
432                cout << "\n" << vspSteps << " view space partition steps taken" << endl;
433               
434                /// Repair split queue
435                cout << "repairing queue ... " << endl;
436                RepairQueue(dirtyList, objectSpaceQueue, true);
437                cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;
438
439                dirtyList.clear();
440        }
441        else
442        {
443                // the priorities were calculated for driving sah.
444                // => recalculate "real" priorities taking visibility into
445                // account so we can compare to view space splits
446                ResetQueue(objectSpaceQueue, false);
447        }
448
449        // This method subdivides view space / object space
450        // in order to converge to some optimal cost for this partition
451        // start with object space partiton
452        // then optimizate view space partition for the current osp
453        // and vice versa until iteration depth is reached.
454
455        bool lastSplitWasOsp = true;
456
457        while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
458        {
459                // decide upon next split type
460                const float vspPriority = viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
461                const float ospPriority = objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
462               
463                cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;
464
465                // should view or object space be subdivided further?
466                if (ospPriority >= vspPriority)
467                //if (!lastSplitWasOsp)
468                {
469                        lastSplitWasOsp = true;
470                        cout << "osp" << endl;
471                       
472                        // dirtied view space candidates
473                        SubdivisionCandidateContainer dirtyVspList;
474
475                        // subdivide object space first
476                        // for first round, use sah splits. Once view space partition
477                        // has started, use render cost heuristics instead
478                        const int ospSteps =
479                                RunConstruction(objectSpaceQueue, dirtyVspList, viewSpaceQueue.Top(), minSteps, maxSteps);
480
481                        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
482                        Debug << "\n" << ospSteps << " object space partition steps taken" << endl;
483
484                        /// Repair split queue, i.e., affected view space candidates
485                        cout << "repairing queue ... " << endl;
486                        RepairQueue(dirtyVspList, viewSpaceQueue, true);
487                        cout << "\nrepaired " << (int)dirtyVspList.size() << " candidates" << endl;
488                }
489                else
490                {
491                        lastSplitWasOsp = false;
492                        cout << "vsp" << endl;
493                       
494                        /////////////////
495                        // subdivide view space with respect to the objects
496
497                        // dirtied object space candidates
498                        SubdivisionCandidateContainer dirtyOspList;
499
500                        // process view space candidates
501                        const int vspSteps =
502                                RunConstruction(viewSpaceQueue, dirtyOspList, objectSpaceQueue.Top(), minSteps, maxSteps);
503
504                        cout << "\n" << vspSteps << " view space partition steps taken" << endl;
505                        Debug << "\n" << vspSteps << " view space partition steps taken" << endl;
506
507                        // view space subdivision constructed
508                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
509
510                        /// Repair split queue
511                        cout << "repairing queue ... " << endl;
512                        RepairQueue(dirtyOspList, objectSpaceQueue, true);
513                        cout << "repaired " << (int)dirtyOspList.size() << " candidates" << endl;
514                }
515        }
516
517        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
518
519        mHierarchyStats.Stop();
520        mVspTree->mVspStats.Stop();
521
522        FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
523}
524
525
526void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
527                                                                                        const ObjectContainer &objects,
528                                                                                        AxisAlignedBox3 *forcedViewSpace)
529{
530        mHierarchyStats.Reset();
531        mHierarchyStats.Start();
532
533        // two nodes for view space and object space
534        mHierarchyStats.mNodes = 2;
535        mHierarchyStats.mPvsEntries = 1;
536        mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
537        mHierarchyStats.mTotalCost = (float)objects.size();
538
539        mHierarchyStats.mRenderCostDecrease = 0;
540
541        EvalSubdivisionStats();
542        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
543
544        const long startTime = GetTime();
545        cout << "Constructing view space / object space tree ... \n";
546       
547        // create only roots
548        mVspTree->Initialise(sampleRays, forcedViewSpace);
549        InitialiseObjectSpaceSubdivision(objects);
550
551        // use objects for evaluating vsp tree construction in the
552        // first levels of the subdivision
553        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
554        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
555
556        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
557        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
558
559        // start view space subdivison immediately?
560        if (StartViewSpaceSubdivision())
561        {
562                // prepare vsp tree for traversal
563        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
564                SubdivisionCandidate *vspSc =
565                        PrepareViewSpaceSubdivision(sampleRays, objects);
566
567                mTQueue.Push(vspSc);
568        }
569       
570        // start object space subdivision immediately?
571        if (StartObjectSpaceSubdivision())
572        {
573                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
574                SubdivisionCandidate *ospSc =
575                        PrepareObjectSpaceSubdivision(sampleRays, objects);
576                mTQueue.Push(ospSc);
577        }
578
579        // begin subdivision
580        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
581       
582        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
583
584        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
585        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
586
587        mHierarchyStats.Stop();
588        mVspTree->mVspStats.Stop();
589       
590        FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
591}
592
593
594SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
595                                                                                                                                        const ObjectContainer &objects)
596{
597        cout << "\npreparing view space hierarchy construction ... " << endl;
598
599        // hack: reset global cost misses
600        mHierarchyStats.mGlobalCostMisses = 0;
601
602        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
603        SubdivisionCandidate *vsc =
604                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
605
606        /////////
607        //-- new stats
608
609        mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
610       
611        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
612
613        return vsc;
614}
615
616
617float HierarchyManager::GetObjectSpaceMemUsage() const
618{
619        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
620        {
621                // TODO;
622        }
623        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
624        {
625                return mBvHierarchy->GetMemUsage();
626        }
627
628        return -1;
629}
630
631void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
632{
633        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
634        {
635                // TODO;
636        }
637        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
638        {
639                mBvHierarchy->Initialise(objects);
640        }
641}
642
643
644SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
645                                                                                                                                          const ObjectContainer &objects)
646{
647        // hack: reset global cost misses
648        mHierarchyStats.mGlobalCostMisses = 0;
649
650        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
651        {
652                return PrepareOspTree(sampleRays, objects);
653        }
654        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
655        {
656                return PrepareBvHierarchy(sampleRays, objects);
657        }
658       
659        return NULL;
660}
661
662
663SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
664                                                                                                                   const ObjectContainer &objects)
665{
666        const long startTime = GetTime();
667
668        cout << "preparing bv hierarchy construction ... " << endl;
669       
670        // compute first candidate
671        SubdivisionCandidate *sc =
672                mBvHierarchy->PrepareConstruction(sampleRays, objects);
673
674        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
675        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
676
677        cout << "finished bv hierarchy preparation in "
678                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
679         
680        return sc;
681}
682
683
684SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
685                                                                                                           const ObjectContainer &objects)
686{
687        cout << "starting osp tree construction ... " << endl;
688
689        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
690
691        // start with one big kd cell - all objects can be seen from everywhere
692        // note: only true for view space = object space
693
694        // compute first candidate
695        SubdivisionCandidate *osc =
696                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
697
698        mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
699        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
700       
701    return osc;
702}
703
704
705bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
706                                                                                                 SplitQueue &splitQueue,
707                                                                                                 const bool repairQueue)
708{
709        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
710        const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
711
712        if (!success) // split was not taken
713        {
714                return false;
715        }
716
717        ///////////////
718        //-- split was successful => update stats and queue
719
720    // cost ratio of cost decrease / totalCost
721        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
722        //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
723       
724        if (costRatio < mTermMinGlobalCostRatio)
725        {
726                ++ mHierarchyStats.mGlobalCostMisses;
727        }
728       
729        cout << sc->Type() << " ";
730               
731        /////////////
732        // update stats
733
734        mHierarchyStats.mNodes += 2;
735        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
736
737        const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
738        mHierarchyStats.mPvsEntries += pvsEntriesIncr;
739        //cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;
740
741        // memory size in byte
742        mHierarchyStats.mMemory += (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
743        mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
744
745        static float memoryCount = 0;
746
747        if (mHierarchyStats.mMemory > memoryCount)
748        {
749                memoryCount += 100000;
750                cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
751                         << " MB, steps: " << mHierarchyStats.Leaves() << endl;
752        }
753
754        // output stats
755        EvalSubdivisionStats();
756               
757        if (repairQueue)
758        {
759                // reevaluate candidates affected by the split for view space splits,
760                // this would be object space splits and other way round
761                vector<SubdivisionCandidate *> dirtyList;
762                sc->CollectDirtyCandidates(dirtyList, false);
763
764                RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
765        }
766
767        return true;
768}
769
770
771int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
772{
773        int maxDepth = 0;
774
775        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
776        {
777                maxDepth = mOspTree->mOspStats.maxDepth;
778        }
779        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
780        {
781                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
782        }
783
784        return maxDepth;
785}
786
787
788int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
789{
790        int maxLeaves= 0;
791
792        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
793        {
794                maxLeaves = mOspTree->mOspStats.Leaves();
795        }
796        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
797        {
798                maxLeaves = mBvHierarchy->mBvhStats.Leaves();
799        }
800
801        return maxLeaves;
802}
803
804
805int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
806{
807        int maxLeaves = 0;
808
809        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
810        {
811                maxLeaves = mOspTree->mOspStats.nodes;
812        }
813        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
814        {
815                maxLeaves = mBvHierarchy->mBvhStats.nodes;
816        }
817
818        return maxLeaves;
819}
820
821bool HierarchyManager::StartObjectSpaceSubdivision() const
822{
823        // view space construction already started
824        if (ObjectSpaceSubdivisionConstructed())
825                return false;
826
827        // start immediately with object space subdivision?
828        if (mStartWithObjectSpace)
829                return true;
830
831        // is the queue empty again?
832        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
833                return true;
834
835        // has the depth for subdivision been reached?
836        return
837                ((mConstructionType == INTERLEAVED) &&
838                 (mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
839}
840
841
842bool HierarchyManager::StartViewSpaceSubdivision() const
843{
844        // view space construction already started
845        if (ViewSpaceSubdivisionConstructed())
846                return false;
847
848        // start immediately with view space subdivision?
849        if (!mStartWithObjectSpace)
850                return true;
851
852        // is the queue empty again?
853        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
854                return true;
855
856        // has the depth for subdivision been reached?
857        return
858                ((mConstructionType == INTERLEAVED) &&
859                 (mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
860}
861
862
863void HierarchyManager::RunConstruction(const bool repairQueue,
864                                                                           const VssRayContainer &sampleRays,
865                                                                           const ObjectContainer &objects,
866                                                                           AxisAlignedBox3 *forcedViewSpace)
867{
868        while (!FinishedConstruction())
869        {
870                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
871       
872                ///////////////////
873                //-- subdivide leaf node
874
875                ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
876                               
877                // we use objects for evaluating vsp tree construction until
878                // a certain depth once a certain depth existiert ...
879                if (StartObjectSpaceSubdivision())
880                {
881                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
882
883                        cout << "\nstarting object space subdivision after "
884                                 << mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") " << endl;
885
886                        SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
887                       
888                        cout << "reseting queue ... ";
889                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
890                        cout << "finished" << endl;
891
892                        mTQueue.Push(ospSc);
893                }
894
895                if (StartViewSpaceSubdivision())
896                {
897                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
898
899                        cout << "\nstarting view space subdivision at depth "
900                                 << GetObjectSpaceSubdivisionLeaves() << " ("
901                                 << mMinStepsOfSameType << ") " << endl;
902
903                        SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
904
905                        cout << "reseting queue ... ";
906                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
907                        cout << "finished" << endl;
908
909                        // push view space candidate                   
910                        mTQueue.Push(vspSc);
911                }
912
913                DEL_PTR(sc);
914        }
915}
916
917
918void HierarchyManager::RunConstruction(const bool repairQueue)
919{
920        // main loop
921        while (!FinishedConstruction())
922        {
923                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
924               
925                ////////
926                //-- subdivide leaf node of either type
927        ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
928               
929                DEL_PTR(sc);
930        }
931}
932
933
934int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
935                                                                          SubdivisionCandidateContainer &dirtyCandidates,
936                                                                          SubdivisionCandidate *oldCandidate,
937                                                                          const int minSteps,
938                                                                          const int maxSteps)
939{
940        if (minSteps >= maxSteps)
941                cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
942
943        int steps = 0;
944        SubdivisionCandidate::NewMail();
945
946        // main loop
947        while (!splitQueue.Empty())
948        {
949                const float priority = splitQueue.Top()->GetPriority();
950                const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
951
952                // minimum slope reached
953                if ((steps >= maxSteps) || ((priority < threshold) && !(steps < minSteps)))
954                {
955                        cout << "\n**************** breaking on " << priority << " smaller than " << threshold << endl;
956                        break;
957                }
958               
959                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
960                               
961                ////////
962                //-- subdivide leaf node of either type
963
964                const bool repairQueue = false;
965                const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
966
967                if (success)
968                {
969                        sc->CollectDirtyCandidates(dirtyCandidates, true);
970                        ++ steps;
971                }
972
973                DEL_PTR(sc);
974        }
975
976        return steps;
977}
978
979
980SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
981                                                                                                                                        const ObjectContainer &objects)
982{       
983        SubdivisionCandidate *firstCandidate;
984
985        // object space partition constructed => reconstruct
986        switch (mObjectSpaceSubdivisionType)
987        {
988        case BV_BASED_OBJ_SUBDIV:
989                {
990                        cout << "\nreseting bv hierarchy" << endl;
991                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
992                               
993                        // rather use this: remove previous nodes and add the two new ones
994                        //mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
995                        mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
996                       
997                        // create root
998                        mBvHierarchy->Initialise(objects);
999       
1000                        firstCandidate = mBvHierarchy->Reset(sampleRays, objects);
1001
1002                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
1003                       
1004                        //mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
1005                        mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
1006
1007                        mHierarchyStats.mMemory =
1008                                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1009
1010                        mHierarchyStats.mRenderCostDecrease = 0;
1011
1012                        // evaluate stats before first subdivision
1013                        EvalSubdivisionStats();
1014                        cout << "finished bv hierarchy preparation" << endl;
1015                }
1016                break;
1017
1018        case KD_BASED_OBJ_SUBDIV:
1019                // TODO
1020        default:
1021                firstCandidate = NULL;
1022                break;
1023        }
1024
1025        return firstCandidate;
1026}
1027
1028
1029SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
1030                                                                                                                                  const ObjectContainer &objects,
1031                                                                                                                                  AxisAlignedBox3 *forcedViewSpace)
1032{
1033        ViewCellsManager *vm = mVspTree->mViewCellsManager;
1034
1035        // HACK: rather not destroy vsp tree
1036        DEL_PTR(mVspTree);
1037        mVspTree = new VspTree();
1038
1039        mVspTree->mHierarchyManager = this;
1040        mVspTree->mViewCellsManager = vm;
1041
1042        mVspTree->Initialise(sampleRays, forcedViewSpace);
1043       
1044        //-- reset stats
1045    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1;
1046       
1047        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
1048       
1049        mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
1050        mHierarchyStats.mRenderCostDecrease = 0;
1051
1052        mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1053
1054        // evaluate new stats before first subdivsiion
1055        EvalSubdivisionStats();
1056
1057        return vsc;
1058}
1059
1060
1061void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
1062                                                                                   const ObjectContainer &objects,
1063                                                                                   AxisAlignedBox3 *forcedViewSpace)
1064{
1065        mHierarchyStats.Reset();
1066        mHierarchyStats.Start();
1067        mHierarchyStats.mNodes = 2;
1068       
1069        mHierarchyStats.mTotalCost = (float)objects.size();
1070        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
1071
1072        const long startTime = GetTime();
1073        cout << "Constructing view space / object space tree ... \n";
1074       
1075        // initialise view / object space
1076        mVspTree->Initialise(sampleRays, forcedViewSpace);
1077        InitialiseObjectSpaceSubdivision(objects);
1078
1079        // use sah for evaluating osp tree construction
1080        // in the first iteration of the subdivision
1081
1082        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
1083        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
1084
1085        SubdivisionCandidate *osc =
1086                PrepareObjectSpaceSubdivision(sampleRays, objects);
1087        mTQueue.Push(osc);
1088
1089        //////////////////////////
1090
1091
1092        const int limit = mNumMultiLevels;
1093        int i = 0;
1094
1095        // This method subdivides view space / object space
1096        // in order to converge to some optimal cost for this partition
1097        // start with object space partiton
1098        // then optimizate view space partition for the current osp
1099        // and vice versa until iteration depth is reached.
1100        while (1)
1101        {
1102                char subdivisionStatsLog[100];
1103                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1104                mSubdivisionStats.open(subdivisionStatsLog);
1105
1106                // subdivide object space first
1107                osc = ResetObjectSpaceSubdivision(sampleRays, objects);
1108                mTQueue.Push(osc);
1109
1110                // process object space candidates
1111                RunConstruction(false);
1112
1113                // object space subdivision constructed
1114                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1115
1116                cout << "iteration " << i << " of " << limit << " finished" << endl;
1117                mSubdivisionStats.close();
1118
1119                if ((i ++) >= limit)
1120                        break;
1121
1122                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1123                mSubdivisionStats.open(subdivisionStatsLog);
1124
1125
1126                /////////////////
1127                // subdivide view space with respect to the objects
1128
1129                SubdivisionCandidate *vspVc =
1130                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
1131                mTQueue.Push(vspVc);
1132
1133                // view space subdivision constructed
1134                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
1135               
1136                // process view space candidates
1137                RunConstruction(false);
1138
1139                cout << "iteration " << i << " of " << limit << " finished" << endl;
1140                mSubdivisionStats.close();
1141
1142                if ((i ++) >= limit)
1143                        break;
1144        }
1145       
1146        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1147
1148        mHierarchyStats.Stop();
1149        mVspTree->mVspStats.Stop();
1150        FinishObjectSpaceSubdivision(objects);
1151}
1152
1153
1154void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                     
1155                                                                                  const ObjectContainer &objects,
1156                                                                                  AxisAlignedBox3 *forcedViewSpace)
1157{
1158        const long startTime = GetTime();
1159        const int limit = mNumMultiLevels;
1160
1161        // open up new subdivision
1162        mSubdivisionStats.close();
1163
1164        int steps = 0;
1165
1166        int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
1167        int maxObjectSpaceLeaves;
1168       
1169        // set the number of leaves 'evaluated' from the previous methods
1170        // we go for the same numbers, but we try to optimize both subdivisions
1171        switch (mObjectSpaceSubdivisionType)
1172        {
1173        case BV_BASED_OBJ_SUBDIV:
1174                maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
1175                break;
1176        case KD_BASED_OBJ_SUBDIV:
1177                maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
1178        default:
1179                maxObjectSpaceLeaves = 0;
1180                break;
1181        }
1182
1183        // This method subdivides view space / object space
1184        // in order to converge to some optimal cost for this partition
1185        // start with object space partiton
1186        // then optimizate view space partition for the current osp
1187        // and vice versa until iteration depth is reached.
1188        while (1)
1189        {
1190                char subdivisionStatsLog[100];
1191                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1192                mSubdivisionStats.open(subdivisionStatsLog);
1193
1194                // subdivide object space first
1195                SubdivisionCandidate *ospVc =
1196                        ResetObjectSpaceSubdivision(sampleRays, objects);
1197       
1198                // set the number of leaves 'evaluated' from the previous methods
1199                // we go for the same numbers, but we try to optimize both subdivisions
1200                mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
1201                mTQueue.Push(ospVc);
1202
1203                // process object space candidates
1204                RunConstruction(false);
1205
1206                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1207                mSubdivisionStats.close();
1208
1209                if ((++ steps) >= limit)
1210                        break;
1211
1212                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1213                mSubdivisionStats.open(subdivisionStatsLog);
1214
1215                /////////////////
1216                // subdivide view space with respect to the objects
1217
1218                SubdivisionCandidate *vspVc =
1219                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
1220
1221                mVspTree->mMaxViewCells = maxViewSpaceLeaves;
1222                mTQueue.Push(vspVc);
1223
1224                // process view space candidates
1225                RunConstruction(false);
1226
1227                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1228                mSubdivisionStats.close();
1229
1230                if ((++ steps) >= limit)
1231                        break;
1232        }
1233       
1234        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1235
1236        mHierarchyStats.Stop();
1237        mVspTree->mVspStats.Stop();
1238        FinishObjectSpaceSubdivision(objects);
1239}
1240
1241
1242
1243bool HierarchyManager::FinishedConstruction() const
1244{
1245        return mTQueue.Empty();
1246}
1247
1248
1249bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
1250{
1251        /*switch (mObjectSpaceSubdivisionType)
1252        {
1253        case KD_BASED_OBJ_SUBDIV:
1254                return mOspTree && mOspTree->GetRoot();
1255        case BV_BASED_OBJ_SUBDIV:
1256                return mBvHierarchy && mBvHierarchy->GetRoot();
1257        default:
1258                return false;
1259        }*/
1260        return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
1261}
1262
1263
1264bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
1265{
1266        return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
1267        //return mVspTree && mVspTree->GetRoot();
1268}
1269
1270
1271void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
1272                                                                                          SubdivisionCandidateContainer &dirtyList)
1273{
1274        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
1275        SubdivisionCandidate::NewMail();
1276
1277        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
1278        {
1279                (*sit)->CollectDirtyCandidates(dirtyList, true);
1280        }
1281}
1282
1283
1284void HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
1285                                                                   SplitQueue &splitQueue,
1286                                                                   const bool recomputeSplitPlaneOnRepair)
1287{
1288        // for each update of the view space partition:
1289        // the candidates from object space partition which
1290        // have been afected by the view space split (the kd split candidates
1291        // which saw the view cell which was split) must be reevaluated
1292        // (maybe not locally, just reinsert them into the queue)
1293        //
1294        // vice versa for the view cells
1295        // for each update of the object space partition
1296        // reevaluate split candidate for view cells which saw the split kd cell
1297        //
1298        // the priority queue update can be solved by implementing a binary heap
1299        // (explicit data structure, binary tree)
1300        // *) inserting and removal is efficient
1301        // *) search is not efficient => store queue position with each
1302        // split candidate
1303
1304        // collect list of "dirty" candidates
1305        const long startTime = GetTime();
1306        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
1307       
1308
1309        ///////////////////////////
1310        //-- reevaluate the dirty list
1311
1312        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
1313       
1314        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
1315        {
1316                SubdivisionCandidate* sc = *sit;
1317                const float rcd = sc->GetRenderCostDecrease();
1318               
1319                // erase from queue
1320                splitQueue.Erase(sc);
1321                // reevaluate candidate
1322                sc->EvalCandidate(recomputeSplitPlaneOnRepair);
1323                 // reinsert
1324                splitQueue.Push(sc);
1325
1326                cout << ".";
1327
1328#ifdef GTP_DEBUG
1329                Debug << "candidate " << sc << " reevaluated\n"
1330                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
1331                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
1332#endif 
1333        }
1334
1335        const long endTime = GetTime();
1336        const Real timeDiff = TimeDiff(startTime, endTime);
1337
1338        mHierarchyStats.mRepairTime += timeDiff;
1339
1340        if (0) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
1341}
1342
1343
1344void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
1345{
1346        SubdivisionCandidateContainer mCandidateBuffer;
1347
1348        // remove from queue
1349        while (!splitQueue.Empty())
1350        {
1351                SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
1352                 // reevaluate local split plane and priority
1353                candidate->EvalCandidate(recomputeSplitPlane);
1354                cout << ".";
1355                mCandidateBuffer.push_back(candidate);
1356        }
1357
1358        // put back into queue
1359        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
1360    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
1361        {
1362                splitQueue.Push(*sit);
1363        }
1364}
1365
1366
1367void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
1368{
1369        // the type of the view cells hierarchy
1370        switch (mObjectSpaceSubdivisionType)
1371        {
1372        case KD_BASED_OBJ_SUBDIV:
1373                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
1374                mOspTree->Export(stream);
1375                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1376                break;         
1377        case BV_BASED_OBJ_SUBDIV:
1378                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
1379                mBvHierarchy->Export(stream);
1380                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1381                break;
1382        }
1383}
1384
1385
1386bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
1387                                                                          const Vector3 &hitPoint,
1388                                                                          ViewCell *vc,
1389                                                                          const float pdf,
1390                                                                          float &contribution) const
1391{
1392        if (!obj) return false;
1393
1394        switch (mObjectSpaceSubdivisionType)
1395        {
1396        case NO_OBJ_SUBDIV:
1397                {
1398                        // potentially visible objects
1399                        return vc->AddPvsSample(obj, pdf, contribution);
1400                }
1401        case KD_BASED_OBJ_SUBDIV:
1402                {
1403                        // potentially visible kd cells
1404                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
1405                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
1406                }
1407        case BV_BASED_OBJ_SUBDIV:
1408                {
1409                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1410                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1411                       
1412                        return vc->AddPvsSample(bvhObj, pdf, contribution);
1413                }
1414        default:
1415                return false;
1416        }
1417}
1418
1419
1420void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
1421{
1422        stream << mHierarchyStats << endl;
1423        stream << "\nview space:" << endl << endl;
1424        stream << mVspTree->GetStatistics() << endl;
1425        stream << "\nobject space:" << endl << endl;
1426
1427        switch (mObjectSpaceSubdivisionType)
1428        {
1429        case KD_BASED_OBJ_SUBDIV:
1430                {
1431                        stream << mOspTree->GetStatistics() << endl;
1432                        break;
1433                }
1434        case BV_BASED_OBJ_SUBDIV:
1435                {
1436                        stream << mBvHierarchy->GetStatistics() << endl;
1437                        break;
1438                }
1439        default:
1440                break;
1441        }
1442}
1443
1444
1445void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
1446                                                                                                  const ObjectContainer &objects,
1447                                                                                                  const AxisAlignedBox3 *bbox,
1448                                                                                                  const bool exportBounds) const
1449{
1450        switch (mObjectSpaceSubdivisionType)
1451        {
1452        case KD_BASED_OBJ_SUBDIV:
1453                {
1454                        ExportOspTree(exporter, objects);
1455                        break;
1456                }
1457        case BV_BASED_OBJ_SUBDIV:
1458                {
1459                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
1460                        break;
1461                }
1462        default:
1463                break;
1464        }
1465}
1466
1467
1468void HierarchyManager::ExportOspTree(Exporter *exporter,
1469                                                                         const ObjectContainer &objects) const
1470{
1471        if (0) exporter->ExportGeometry(objects);
1472                       
1473        exporter->SetWireframe();
1474        exporter->ExportOspTree(*mOspTree, 0);
1475}
1476
1477
1478Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1479                                                                                                  const bool isTermination) const
1480{
1481
1482        Intersectable *obj;
1483        Vector3 pt;
1484        KdNode *node;
1485
1486        ray.GetSampleData(isTermination, pt, &obj, &node);
1487       
1488        if (!obj) return NULL;
1489
1490        switch (mObjectSpaceSubdivisionType)
1491        {
1492        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1493                {
1494                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1495                        return mOspTree->GetOrCreateKdIntersectable(leaf);
1496                }
1497        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1498                {
1499                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1500                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1501                }
1502        default:
1503                return obj;
1504        }
1505}
1506
1507
1508void HierarchyStatistics::Print(ostream &app) const
1509{
1510        app << "=========== Hierarchy statistics ===============\n";
1511
1512        app << setprecision(4);
1513
1514        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1515       
1516        app << "#N_RTIME  ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1517
1518        app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1519
1520        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1521
1522        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1523
1524        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1525
1526        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1527       
1528        app << "========== END OF Hierarchy statistics ==========\n";
1529}
1530
1531
1532static void RemoveRayRefs(const ObjectContainer &objects)
1533{
1534        ObjectContainer::const_iterator oit, oit_end = objects.end();
1535        for (oit = objects.begin(); oit != oit_end; ++ oit)
1536        {
1537                (*oit)->DelRayRefs();
1538        }
1539}
1540
1541
1542void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1543                                                                                                        const bool removeRayRefs) const
1544{
1545        switch (mObjectSpaceSubdivisionType)
1546        {
1547        case KD_BASED_OBJ_SUBDIV:
1548                {
1549                        mOspTree->mOspStats.Stop();
1550                        break;
1551                }
1552        case BV_BASED_OBJ_SUBDIV:
1553                {
1554                        mBvHierarchy->mBvhStats.Stop();
1555                        if (removeRayRefs)
1556                                RemoveRayRefs(objects);
1557                        break;
1558                }
1559        default:
1560                break;
1561        }
1562}
1563
1564
1565void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1566{
1567        stream << "<BoundingBoxes>" << endl;
1568           
1569        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1570        {
1571                KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1572
1573                int id = 0;
1574                for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1575                {
1576                        Intersectable *obj = (*kit).second;
1577                        const AxisAlignedBox3 box = obj->GetBox();
1578               
1579                        obj->SetId(id);
1580
1581                        stream << "<BoundingBox" << " id=\"" << id << "\""
1582                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1583                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1584                }
1585        }
1586        else
1587        {
1588                ObjectContainer::const_iterator oit, oit_end = objects.end();
1589
1590                for (oit = objects.begin(); oit != oit_end; ++ oit)
1591                {
1592                        const AxisAlignedBox3 box = (*oit)->GetBox();
1593               
1594                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1595                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1596                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1597                }
1598        }
1599               
1600        stream << "</BoundingBoxes>" << endl;
1601}
1602
1603
1604static void UpdateStats(ofstream &stats,
1605                                                const int splits,
1606                                                const float totalRenderCost,
1607                                                const int entriesInPvs,
1608                                                const float memoryCost,
1609                                                const int viewSpaceSplits,
1610                                                const int objectSpaceSplits)
1611{
1612        stats << "#Pass\n" << 0 << endl
1613                   << "#Splits\n" << splits << endl
1614                   << "#TotalRenderCost\n" << totalRenderCost << endl
1615                   << "#TotalEntriesInPvs\n" << entriesInPvs << endl
1616                   << "#Memory\n" << memoryCost << endl
1617                   << "#ViewSpaceSplits\n" << viewSpaceSplits << endl
1618                   << "#ObjectSpaceSplits\n" << objectSpaceSplits << endl
1619                   << "#VspOspRatio\n" << (float)viewSpaceSplits / (float)objectSpaceSplits << endl
1620                   << endl;
1621}
1622
1623
1624class HierarchyNodeWrapper;
1625
1626
1627template <typename T> class myless
1628{
1629public:
1630        bool operator() (T v1, T v2) const
1631        {
1632                return (v1->GetMergeCost() < v2->GetMergeCost());
1633        }
1634};
1635
1636
1637typedef priority_queue<HierarchyNodeWrapper *, vector<HierarchyNodeWrapper *>,
1638                                           myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
1639
1640class HierarchyNodeWrapper
1641{
1642public:
1643        enum {VSP_NODE, BVH_NODE, VIEW_CELL};
1644
1645        virtual float GetMergeCost() const = 0;
1646        virtual int Type() const  = 0;
1647        virtual bool IsLeaf() const = 0;
1648
1649        virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
1650};
1651
1652
1653class VspNodeWrapper: public HierarchyNodeWrapper
1654{
1655public:
1656        VspNodeWrapper(VspNode *node): mNode(node) {}
1657
1658        int Type() const { return VSP_NODE; }
1659
1660        float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
1661
1662        bool IsLeaf() const { return mNode->IsLeaf(); }
1663
1664        void PushChildren(HierarchyNodeQueue &tQueue)
1665        {
1666                if (!mNode->IsLeaf())
1667                {
1668                        VspInterior *interior = dynamic_cast<VspInterior *>(mNode);
1669
1670                        tQueue.push(new VspNodeWrapper(interior->GetFront()));
1671                        tQueue.push(new VspNodeWrapper(interior->GetBack()));
1672                }
1673        }
1674
1675        VspNode *mNode;
1676};
1677
1678
1679class BvhNodeWrapper: public HierarchyNodeWrapper
1680{
1681public:
1682        BvhNodeWrapper(BvhNode *node): mNode(node) {}
1683       
1684        int Type()  const { return BVH_NODE; }
1685
1686        float GetMergeCost() const { return (float)-mNode->mTimeStamp; };
1687
1688        bool IsLeaf() const { return mNode->IsLeaf(); }
1689
1690        void PushChildren(HierarchyNodeQueue &tQueue)
1691        {
1692                if (!mNode->IsLeaf())
1693                {
1694                        BvhInterior *interior = dynamic_cast<BvhInterior *>(mNode);
1695
1696                        tQueue.push(new BvhNodeWrapper(interior->GetFront()));
1697                        tQueue.push(new BvhNodeWrapper(interior->GetBack()));
1698                }
1699        }
1700
1701        BvhNode *mNode;
1702};
1703
1704
1705class ViewCellWrapper: public HierarchyNodeWrapper
1706{
1707public:
1708
1709        ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
1710       
1711        int Type()  const { return VIEW_CELL; }
1712
1713        float GetMergeCost() const { return mViewCell->GetMergeCost(); };
1714
1715        bool IsLeaf() const { return mViewCell->IsLeaf(); }
1716
1717        void PushChildren(HierarchyNodeQueue &tQueue)
1718        {
1719                if (!mViewCell->IsLeaf())
1720                {
1721                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(mViewCell);
1722
1723                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1724
1725                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1726                        {
1727                                tQueue.push(new ViewCellWrapper(*it));
1728                        }
1729                }
1730        }
1731
1732        ViewCell *mViewCell;
1733};
1734
1735
1736void HierarchyManager::CollectBestSet(const int maxSplits,
1737                                                                          const float maxMemoryCost,
1738                                                                          ViewCellContainer &viewCells,
1739                                                                          vector<BvhNode *> &bvhNodes)
1740{
1741        HierarchyNodeQueue tqueue;
1742        //tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
1743        tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
1744        tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
1745       
1746        float memCost = 0;
1747
1748        while (!tqueue.empty())
1749        {
1750                HierarchyNodeWrapper *nodeWrapper = tqueue.top();
1751                tqueue.pop();
1752                //cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
1753                // save the view cells if it is a leaf or if enough view cells have already been traversed
1754                // because of the priority queue, this will be the optimal set of v
1755                if (nodeWrapper->IsLeaf() ||
1756                        ((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) ||
1757                        (memCost > maxMemoryCost)
1758                        )
1759                {
1760                        if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
1761                        {
1762                                //cout << "1";
1763                                ViewCellWrapper *viewCellWrapper = dynamic_cast<ViewCellWrapper *>(nodeWrapper);
1764                                viewCells.push_back(viewCellWrapper->mViewCell);
1765                        }
1766                        else
1767                        {
1768                                //cout << "0";
1769                                BvhNodeWrapper *bvhNodeWrapper = dynamic_cast<BvhNodeWrapper *>(nodeWrapper);
1770                                bvhNodes.push_back(bvhNodeWrapper->mNode);
1771                        }
1772                }
1773                else
1774                {       
1775                        nodeWrapper->PushChildren(tqueue);
1776                }
1777
1778                delete nodeWrapper;
1779        }
1780}
1781
1782
1783int HierarchyManager::ExtractStatistics(const int maxSplits,
1784                                                                                const float maxMemoryCost,
1785                                                                                float &renderCost,
1786                                                                                float &memory,
1787                                                                                int &pvsEntries,
1788                                                                                int &viewSpaceSplits,
1789                                                                                int &objectSpaceSplits)
1790{
1791        ViewCellContainer viewCells;
1792        vector<BvhNode *> bvhNodes;
1793
1794        // collect best set of view cells for this #splits
1795    CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
1796        //cout << "here5 " << bvhNodes.size() << endl;
1797        vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
1798       
1799        // set new nodes to be active
1800        for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
1801        {
1802                mBvHierarchy->SetActive(*bit);
1803        }
1804
1805        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1806
1807        pvsEntries = 0;
1808        renderCost = 0.0f;
1809
1810        //BvhNode::NewMail();
1811        //int dummy = 0;
1812        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1813        {
1814                float rc = 0;
1815                ViewCell *vc = *vit;
1816                ObjectPvs pvs;
1817                mVspTree->mViewCellsTree->GetPvs(vc, pvs);
1818                //dummy+=pvs.GetSize();
1819                BvhNode::NewMail();
1820
1821                // hack: should not be done here
1822                ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
1823
1824                for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
1825                {
1826                        BvhIntersectable *intersect = dynamic_cast<BvhIntersectable *>((*oit).first);
1827
1828                        BvhLeaf *leaf = intersect->GetItem();
1829                        BvhNode *activeNode = leaf->GetActiveNode();
1830
1831                        if (!activeNode->Mailed())
1832                        {
1833                                activeNode->Mail();
1834
1835                                ObjectContainer objects;
1836                                activeNode->CollectObjects(objects);
1837
1838                                ++ pvsEntries;
1839                                rc += mBvHierarchy->EvalAbsCost(objects);
1840                                //cout << " pvs: " << mBvHierarchy->EvalAbsCost(leaf->mObjects);
1841                        }
1842                }
1843
1844                rc *= vc->GetVolume();
1845                renderCost += rc;
1846        }
1847
1848        renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
1849
1850        memory = pvsEntries * ObjectPvs::GetEntrySize();
1851
1852        viewSpaceSplits = (int)viewCells.size();
1853        objectSpaceSplits = (int)bvhNodes.size();
1854
1855        //cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
1856
1857        return viewCells.size() + bvhNodes.size();
1858}
1859
1860
1861void HierarchyManager::ExportStats(ofstream &stats,
1862                                                                   SplitQueue &tQueue,
1863                                                                   const ObjectContainer &objects)
1864{
1865        float totalRenderCost = (float)objects.size();
1866        int entriesInPvs = 1;
1867        int steps = 0;
1868        int viewSpaceSplits = 0;
1869        int objectSpaceSplits = 0;
1870
1871        cout << "exporting vsposp stats ... " << endl;
1872        const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
1873
1874        /////////////
1875        //-- first view cell
1876
1877        UpdateStats(stats, 2, totalRenderCost, entriesInPvs, memoryCost, viewSpaceSplits, objectSpaceSplits);
1878
1879        //-- go through tree in the order of render cost decrease
1880        //-- which is the same order as the view cells were merged
1881        //-- or the reverse order of subdivision for subdivision-only
1882        //-- view cell hierarchies.
1883       
1884        while (!tQueue.Empty())
1885        {
1886                SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
1887                bool isLeaf;
1888                int timeStamp;
1889                float rcDecr;
1890                int entriesIncr;
1891
1892        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
1893                {
1894                        timeStamp = (int)-nextCandidate->GetPriority();
1895
1896                        VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
1897                        VspNode *oldNode = (VspNode *)nextCandidate->mEvaluationHack;
1898                       
1899                        isLeaf = newNode->IsLeaf();
1900                        rcDecr = oldNode->mRenderCostDecr;
1901                        entriesIncr = oldNode->mPvsEntriesIncr;
1902                }
1903                else
1904                {
1905                        timeStamp = (int)-nextCandidate->GetPriority();
1906                       
1907                        BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
1908                        BvhNode *oldNode = (BvhNode *)nextCandidate->mEvaluationHack;
1909                       
1910                        isLeaf = newNode->IsLeaf();
1911                        rcDecr = oldNode->mRenderCostDecr;
1912                        entriesIncr = oldNode->mPvsEntriesIncr;
1913                }               
1914                               
1915                if (!isLeaf)
1916                {
1917                        totalRenderCost -= rcDecr;
1918                        entriesInPvs += entriesIncr;
1919                        // if (rcDecr <= 0)
1920                        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
1921                        {
1922                                ++ viewSpaceSplits;
1923                                cout << "v";//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
1924                        }
1925                        else
1926                        {
1927                                ++ objectSpaceSplits;
1928                                cout << "o";//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
1929                        }
1930
1931                        ++ steps;
1932
1933                        if ((steps % 500) == 499)
1934                                cout << steps << " steps taken" << endl;
1935
1936                        const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
1937                        UpdateStats(stats, steps, totalRenderCost, entriesInPvs, memoryCost, viewSpaceSplits, objectSpaceSplits);
1938                }
1939
1940                DEL_PTR(nextCandidate);
1941        }
1942
1943        stats.close();
1944}
1945
1946
1947void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,                                                                                                                                             
1948                                                                                   const ObjectContainer &objects,
1949                                                                                   const string &filename)
1950{
1951        VspTree *oldVspTree = mVspTree;
1952        ViewCellsManager *vm = mVspTree->mViewCellsManager;
1953        BvHierarchy *oldHierarchy = mBvHierarchy;
1954
1955        mBvHierarchy = new BvHierarchy();
1956        mBvHierarchy->mHierarchyManager = this;
1957        mBvHierarchy->mViewCellsManager = vm;
1958
1959        mVspTree = new VspTree();
1960        mVspTree->mHierarchyManager = this;
1961        mVspTree->mViewCellsManager = vm;
1962
1963        // create first nodes
1964        mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
1965        InitialiseObjectSpaceSubdivision(objects);
1966
1967        const long startTime = GetTime();
1968        cout << "Constructing evaluation hierarchies ... \n";
1969       
1970        ofstream stats;
1971        stats.open(filename.c_str());
1972        SplitQueue tQueue;
1973
1974        BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
1975        VspNode *oldVspRoot = oldVspTree->GetRoot();
1976
1977        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
1978       
1979        SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
1980        SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects);
1981
1982    firstVsp->mEvaluationHack = oldVspRoot;
1983        firstBvh->mEvaluationHack = oldBvhRoot;
1984
1985        firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
1986        firstBvh->SetPriority((float)-oldBvhRoot->mTimeStamp);
1987
1988        tQueue.Push(firstVsp);
1989        tQueue.Push(firstBvh);
1990
1991        ExportStats(stats, tQueue, objects);
1992
1993        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1994        RemoveRayRefs(objects);
1995
1996        // view cells needed only for evaluation
1997        ViewCellContainer viewCells;
1998        mVspTree->CollectViewCells(viewCells, false);
1999       
2000        // helper trees can be destroyed
2001        DEL_PTR(mVspTree);
2002        DEL_PTR(mBvHierarchy);
2003
2004        CLEAR_CONTAINER(viewCells);
2005
2006        // reset hierarchies
2007        mVspTree = oldVspTree;
2008        mBvHierarchy = oldHierarchy;
2009
2010        // reinstall old bv refs
2011        vector<BvhLeaf *> leaves;
2012        mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
2013        vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
2014
2015        for (bit = leaves.begin(); bit != bit_end; ++ bit)
2016        {
2017                mBvHierarchy->AssociateObjectsWithLeaf(*bit);
2018        }
2019}
2020
2021
2022void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
2023                                                                                        const int splitsStepSize)
2024{
2025        int splits = 0;
2026
2027        float renderCost;
2028        float memory;
2029        int pvsEntries;
2030        int viewSpaceSplits;
2031        int objectSpaceSplits;
2032
2033        while (1)
2034        {
2035                const int numSplits = ExtractStatistics(splits,
2036                                                                                                99999.0,
2037                                                                                                renderCost,
2038                                                                                                memory,
2039                                                                                                pvsEntries,
2040                                                                                                viewSpaceSplits,
2041                                                                                                objectSpaceSplits);
2042               
2043                UpdateStats(splitsStats,
2044                                        numSplits,
2045                                        renderCost,
2046                                        pvsEntries,
2047                                        memory,
2048                                        viewSpaceSplits,
2049                                        objectSpaceSplits);
2050
2051                splits += splitsStepSize;
2052
2053                if (numSplits == mHierarchyStats.Leaves())
2054                        break;
2055        }
2056}
2057
2058
2059void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
2060{
2061        mBvHierarchy->CollectObjects(box, objects);
2062}
2063
2064}
Note: See TracBrowser for help on using the repository browser.