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

Revision 1733, 58.3 KB checked in by mattausch, 18 years ago (diff)

removed bug from dirtycandidates

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