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

Revision 1727, 58.6 KB checked in by mattausch, 18 years ago (diff)

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