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

Revision 1741, 58.5 KB checked in by mattausch, 18 years ago (diff)

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