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

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