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

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