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

Revision 1692, 50.7 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, ospSteps;
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        bool lastSplitWasOsp = true;
454
455        while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
456        {
457                // decide upon next split type
458                const float vspPriority =  viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
459                const float ospPriority =  objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
460               
461                cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;
462
463                // should view or object space be subdivided further?
464                if (ospPriority >= vspPriority)
465                //if (!lastSplitWasOsp)
466                {
467                        lastSplitWasOsp = true;
468                        cout << "osp" << endl;
469                       
470                        // dirtied view space candidates
471                        SubdivisionCandidateContainer dirtyVspList;
472
473                        // subdivide object space first
474                        // for first round, use sah splits. Once view space partition
475                        // has started, use render cost heuristics instead
476                        const int ospSteps =
477                                RunConstruction(objectSpaceQueue, dirtyVspList, viewSpaceQueue.Top(), minSteps, maxSteps);
478
479                        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
480                        Debug << "\n" << ospSteps << " object space partition steps taken" << endl;
481
482                        /// Repair split queue, i.e., affected view space candidates
483                        cout << "repairing queue ... " << endl;
484                        RepairQueue(dirtyVspList, viewSpaceQueue, true);
485                        cout << "\nrepaired " << (int)dirtyVspList.size() << " candidates" << endl;
486                }
487                else
488                {
489                        lastSplitWasOsp = false;
490                        cout << "vsp" << endl;
491                       
492                        /////////////////
493                        // subdivide view space with respect to the objects
494
495                        // dirtied object space candidates
496                        SubdivisionCandidateContainer dirtyOspList;
497
498                        // process view space candidates
499                        const int vspSteps =
500                                RunConstruction(viewSpaceQueue, dirtyOspList, objectSpaceQueue.Top(), minSteps, maxSteps);
501
502                        cout << "\n" << vspSteps << " view space partition steps taken" << endl;
503                        Debug << "\n" << vspSteps << " view space partition steps taken" << endl;
504
505                        // view space subdivision constructed
506                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
507
508                        /// Repair split queue
509                        cout << "repairing queue ... " << endl;
510                        RepairQueue(dirtyOspList, objectSpaceQueue, true);
511                        cout << "repaired " << (int)dirtyOspList.size() << " candidates" << endl;
512                }
513        }
514
515        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
516
517        mHierarchyStats.Stop();
518        mVspTree->mVspStats.Stop();
519
520        FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
521}
522
523
524void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
525                                                                                        const ObjectContainer &objects,
526                                                                                        AxisAlignedBox3 *forcedViewSpace)
527{
528        mHierarchyStats.Reset();
529        mHierarchyStats.Start();
530
531        // two nodes for view space and object space
532        mHierarchyStats.mNodes = 2;
533        mHierarchyStats.mPvsEntries = 1;
534        mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
535        mHierarchyStats.mTotalCost = (float)objects.size();
536
537        mHierarchyStats.mRenderCostDecrease = 0;
538
539        EvalSubdivisionStats();
540        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
541
542        const long startTime = GetTime();
543        cout << "Constructing view space / object space tree ... \n";
544       
545        // create only roots
546        mVspTree->Initialise(sampleRays, forcedViewSpace);
547        InitialiseObjectSpaceSubdivision(objects);
548
549        // use objects for evaluating vsp tree construction in the
550        // first levels of the subdivision
551        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
552        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
553
554        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
555        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
556
557        // start view space subdivison immediately?
558        if (StartViewSpaceSubdivision())
559        {
560                // prepare vsp tree for traversal
561        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
562                SubdivisionCandidate *vspSc =
563                        PrepareViewSpaceSubdivision(sampleRays, objects);
564
565                mTQueue.Push(vspSc);
566        }
567       
568        // start object space subdivision immediately?
569        if (StartObjectSpaceSubdivision())
570        {
571                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
572                SubdivisionCandidate *ospSc =
573                        PrepareObjectSpaceSubdivision(sampleRays, objects);
574                mTQueue.Push(ospSc);
575        }
576
577        // begin subdivision
578        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
579       
580        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
581
582        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
583        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
584
585        mHierarchyStats.Stop();
586        mVspTree->mVspStats.Stop();
587       
588        FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
589}
590
591
592SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
593                                                                                                                                        const ObjectContainer &objects)
594{
595        cout << "\npreparing view space hierarchy construction ... " << endl;
596
597        // hack: reset global cost misses
598        mHierarchyStats.mGlobalCostMisses = 0;
599
600        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
601        SubdivisionCandidate *vsc =
602                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
603
604        /////////
605        //-- new stats
606
607        mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
608       
609        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
610
611        return vsc;
612}
613
614
615float HierarchyManager::GetObjectSpaceMemUsage() const
616{
617        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
618        {
619                // TODO;
620        }
621        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
622        {
623                return mBvHierarchy->GetMemUsage();
624        }
625
626        return -1;
627}
628
629void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
630{
631        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
632        {
633                // TODO;
634        }
635        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
636        {
637                mBvHierarchy->Initialise(objects);
638        }
639}
640
641
642SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
643                                                                                                                                          const ObjectContainer &objects)
644{
645        // hack: reset global cost misses
646        mHierarchyStats.mGlobalCostMisses = 0;
647
648        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
649        {
650                return PrepareOspTree(sampleRays, objects);
651        }
652        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
653        {
654                return PrepareBvHierarchy(sampleRays, objects);
655        }
656       
657        return NULL;
658}
659
660
661SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
662                                                                                                                   const ObjectContainer &objects)
663{
664        const long startTime = GetTime();
665
666        cout << "preparing bv hierarchy construction ... " << endl;
667       
668        // compute first candidate
669        SubdivisionCandidate *sc =
670                mBvHierarchy->PrepareConstruction(sampleRays, objects);
671
672        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
673        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
674
675        cout << "finished bv hierarchy preparation in "
676                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
677         
678        return sc;
679}
680
681
682SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
683                                                                                                           const ObjectContainer &objects)
684{
685        cout << "starting osp tree construction ... " << endl;
686
687        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
688
689        // start with one big kd cell - all objects can be seen from everywhere
690        // note: only true for view space = object space
691
692        // compute first candidate
693        SubdivisionCandidate *osc =
694                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
695
696        mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
697        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
698       
699    return osc;
700}
701
702
703bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
704                                                                                                 SplitQueue &splitQueue,
705                                                                                                 const bool repairQueue)
706{
707        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
708        const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
709
710        if (!success) // split was not taken
711        {
712                return false;
713        }
714
715        ///////////////
716        //-- split was successful => update stats and queue
717
718    // cost ratio of cost decrease / totalCost
719        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
720        //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
721       
722        if (costRatio < mTermMinGlobalCostRatio)
723        {
724                ++ mHierarchyStats.mGlobalCostMisses;
725        }
726       
727        cout << sc->Type() << " ";
728               
729        /////////////
730        // update stats
731
732        mHierarchyStats.mNodes += 2;
733        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
734
735        const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
736        mHierarchyStats.mPvsEntries += pvsEntriesIncr;
737        //cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;
738
739        // memory size in byte
740        mHierarchyStats.mMemory += (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
741        mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
742
743        static float memoryCount = 0;
744
745        if (mHierarchyStats.mMemory > memoryCount)
746        {
747                memoryCount += 100000;
748                cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
749                         << " MB, steps: " << mHierarchyStats.Leaves() << endl;
750        }
751
752        // output stats
753        EvalSubdivisionStats();
754               
755        if (repairQueue)
756        {
757                // reevaluate candidates affected by the split for view space splits,
758                // this would be object space splits and other way round
759                vector<SubdivisionCandidate *> dirtyList;
760                sc->CollectDirtyCandidates(dirtyList, false);
761
762                RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
763        }
764
765        return true;
766}
767
768
769int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
770{
771        int maxDepth = 0;
772
773        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
774        {
775                maxDepth = mOspTree->mOspStats.maxDepth;
776        }
777        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
778        {
779                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
780        }
781
782        return maxDepth;
783}
784
785
786int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
787{
788        int maxLeaves= 0;
789
790        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
791        {
792                maxLeaves = mOspTree->mOspStats.Leaves();
793        }
794        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
795        {
796                maxLeaves = mBvHierarchy->mBvhStats.Leaves();
797        }
798
799        return maxLeaves;
800}
801
802
803int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
804{
805        int maxLeaves = 0;
806
807        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
808        {
809                maxLeaves = mOspTree->mOspStats.nodes;
810        }
811        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
812        {
813                maxLeaves = mBvHierarchy->mBvhStats.nodes;
814        }
815
816        return maxLeaves;
817}
818
819bool HierarchyManager::StartObjectSpaceSubdivision() const
820{
821        // view space construction already started
822        if (ObjectSpaceSubdivisionConstructed())
823                return false;
824
825        // start immediately with object space subdivision?
826        if (mStartWithObjectSpace)
827                return true;
828
829        // is the queue empty again?
830        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
831                return true;
832
833        // has the depth for subdivision been reached?
834        return
835                ((mConstructionType == INTERLEAVED) &&
836                 (mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
837}
838
839
840bool HierarchyManager::StartViewSpaceSubdivision() const
841{
842        // view space construction already started
843        if (ViewSpaceSubdivisionConstructed())
844                return false;
845
846        // start immediately with view space subdivision?
847        if (!mStartWithObjectSpace)
848                return true;
849
850        // is the queue empty again?
851        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
852                return true;
853
854        // has the depth for subdivision been reached?
855        return
856                ((mConstructionType == INTERLEAVED) &&
857                 (mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
858}
859
860
861void HierarchyManager::RunConstruction(const bool repairQueue,
862                                                                           const VssRayContainer &sampleRays,
863                                                                           const ObjectContainer &objects,
864                                                                           AxisAlignedBox3 *forcedViewSpace)
865{
866        while (!FinishedConstruction())
867        {
868                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
869       
870                ///////////////////
871                //-- subdivide leaf node
872
873                ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
874                               
875                // we use objects for evaluating vsp tree construction until
876                // a certain depth once a certain depth existiert ...
877                if (StartObjectSpaceSubdivision())
878                {
879                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
880
881                        cout << "\nstarting object space subdivision after "
882                                 << mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") " << endl;
883
884                        SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
885                       
886                        cout << "reseting queue ... ";
887                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
888                        cout << "finished" << endl;
889
890                        mTQueue.Push(ospSc);
891                }
892
893                if (StartViewSpaceSubdivision())
894                {
895                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
896
897                        cout << "\nstarting view space subdivision at depth "
898                                 << GetObjectSpaceSubdivisionLeaves() << " ("
899                                 << mMinStepsOfSameType << ") " << endl;
900
901                        SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
902
903                        cout << "reseting queue ... ";
904                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
905                        cout << "finished" << endl;
906
907                        // push view space candidate                   
908                        mTQueue.Push(vspSc);
909                }
910
911                DEL_PTR(sc);
912        }
913}
914
915
916void HierarchyManager::RunConstruction(const bool repairQueue)
917{
918        // main loop
919        while (!FinishedConstruction())
920        {
921                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
922               
923                ////////
924                //-- subdivide leaf node of either type
925        ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
926               
927                DEL_PTR(sc);
928        }
929}
930
931
932int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
933                                                                          SubdivisionCandidateContainer &dirtyCandidates,
934                                                                          SubdivisionCandidate *oldCandidate,
935                                                                          const int minSteps,
936                                                                          const int maxSteps)
937{
938        if (minSteps >= maxSteps)
939                cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
940
941        int steps = 0;
942        SubdivisionCandidate::NewMail();
943
944        // main loop
945        while (!splitQueue.Empty())
946        {
947                const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
948                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
949               
950                float rc = (float)sc->GetRenderCostDecrease() / (mInitialRenderCost - mHierarchyStats.mTotalCost + 1.0f);
951                float mc = (float)sc->GetPvsEntriesIncr() / (float)mHierarchyStats.mPvsEntries;
952
953                //cout << "dRc: " << sc->GetRenderCostDecrease() << " dMem: " << sc->GetPvsEntriesIncr() << " ratio1 " << rc << " ratio2 " << mc << " const: " << 1.0f - GetMemoryConst() << endl;
954
955                // minimum slope reached
956                if ((steps > maxSteps) ||
957                        ((sc->GetPriority() < threshold) && !(steps < minSteps)))
958                {
959                        cout << "\n**************** breaking on " << sc->GetPriority() << " smaller than " << threshold << endl;
960                        break;
961                }
962
963                ////////
964                //-- subdivide leaf node of either type
965
966                const bool repairQueue = false;
967                const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
968
969                if (success)
970                {
971                        sc->CollectDirtyCandidates(dirtyCandidates, true);
972                        ++ steps;
973                }
974        }
975
976        return steps;
977}
978
979
980SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
981                                                                                                                                        const ObjectContainer &objects)
982{       
983        SubdivisionCandidate *firstCandidate;
984
985        // object space partition constructed => reconstruct
986        switch (mObjectSpaceSubdivisionType)
987        {
988        case BV_BASED_OBJ_SUBDIV:
989                {
990                        cout << "\nreseting bv hierarchy" << endl;
991                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
992                               
993                        // rather use this: remove previous nodes and add the two new ones
994                        //mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
995                        mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
996                       
997                        // create root
998                        mBvHierarchy->Initialise(objects);
999       
1000                        firstCandidate = mBvHierarchy->Reset(sampleRays, objects);
1001
1002                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
1003                       
1004                        //mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
1005                        mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
1006
1007                        mHierarchyStats.mMemory =
1008                                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1009
1010                        mHierarchyStats.mRenderCostDecrease = 0;
1011
1012                        // evaluate stats before first subdivision
1013                        EvalSubdivisionStats();
1014                        cout << "finished bv hierarchy preparation" << endl;
1015                }
1016                break;
1017
1018        case KD_BASED_OBJ_SUBDIV:
1019                // TODO
1020        default:
1021                firstCandidate = NULL;
1022                break;
1023        }
1024
1025        return firstCandidate;
1026}
1027
1028
1029SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
1030                                                                                                                                  const ObjectContainer &objects,
1031                                                                                                                                  AxisAlignedBox3 *forcedViewSpace)
1032{
1033        ViewCellsManager *vm = mVspTree->mViewCellsManager;
1034
1035        // HACK: rather not destroy vsp tree
1036        DEL_PTR(mVspTree);
1037        mVspTree = new VspTree();
1038
1039        mVspTree->mHierarchyManager = this;
1040        mVspTree->mViewCellsManager = vm;
1041
1042        mVspTree->Initialise(sampleRays, forcedViewSpace);
1043       
1044        //-- reset stats
1045    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1;
1046       
1047        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
1048       
1049        mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
1050        mHierarchyStats.mRenderCostDecrease = 0;
1051
1052        mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1053
1054        // evaluate new stats before first subdivsiion
1055        EvalSubdivisionStats();
1056
1057        return vsc;
1058}
1059
1060
1061void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
1062                                                                                   const ObjectContainer &objects,
1063                                                                                   AxisAlignedBox3 *forcedViewSpace)
1064{
1065        mHierarchyStats.Reset();
1066        mHierarchyStats.Start();
1067        mHierarchyStats.mNodes = 2;
1068       
1069        mHierarchyStats.mTotalCost = (float)objects.size();
1070        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
1071
1072        const long startTime = GetTime();
1073        cout << "Constructing view space / object space tree ... \n";
1074       
1075        // initialise view / object space
1076        mVspTree->Initialise(sampleRays, forcedViewSpace);
1077        InitialiseObjectSpaceSubdivision(objects);
1078
1079        // use sah for evaluating osp tree construction
1080        // in the first iteration of the subdivision
1081
1082        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
1083        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
1084
1085        SubdivisionCandidate *osc =
1086                PrepareObjectSpaceSubdivision(sampleRays, objects);
1087        mTQueue.Push(osc);
1088
1089        //////////////////////////
1090
1091
1092        const int limit = mNumMultiLevels;
1093        int i = 0;
1094
1095        // This method subdivides view space / object space
1096        // in order to converge to some optimal cost for this partition
1097        // start with object space partiton
1098        // then optimizate view space partition for the current osp
1099        // and vice versa until iteration depth is reached.
1100        while (1)
1101        {
1102                char subdivisionStatsLog[100];
1103                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1104                mSubdivisionStats.open(subdivisionStatsLog);
1105
1106                // subdivide object space first
1107                osc = ResetObjectSpaceSubdivision(sampleRays, objects);
1108                mTQueue.Push(osc);
1109
1110                // process object space candidates
1111                RunConstruction(false);
1112
1113                // object space subdivision constructed
1114                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1115
1116                cout << "iteration " << i << " of " << limit << " finished" << endl;
1117                mSubdivisionStats.close();
1118
1119                if ((i ++) >= limit)
1120                        break;
1121
1122                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1123                mSubdivisionStats.open(subdivisionStatsLog);
1124
1125
1126                /////////////////
1127                // subdivide view space with respect to the objects
1128
1129                SubdivisionCandidate *vspVc =
1130                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
1131                mTQueue.Push(vspVc);
1132
1133                // view space subdivision constructed
1134                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
1135               
1136                // process view space candidates
1137                RunConstruction(false);
1138
1139                cout << "iteration " << i << " of " << limit << " finished" << endl;
1140                mSubdivisionStats.close();
1141
1142                if ((i ++) >= limit)
1143                        break;
1144        }
1145       
1146        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1147
1148        mHierarchyStats.Stop();
1149        mVspTree->mVspStats.Stop();
1150        FinishObjectSpaceSubdivision(objects);
1151}
1152
1153
1154void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                     
1155                                                                                  const ObjectContainer &objects,
1156                                                                                  AxisAlignedBox3 *forcedViewSpace)
1157{
1158        // assume object space subdivision constructed
1159        //mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1160
1161        const long startTime = GetTime();
1162        const int limit = mNumMultiLevels;
1163
1164        // open up new subdivision
1165        mSubdivisionStats.close();
1166
1167        int steps = 0;
1168
1169        int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
1170        int maxObjectSpaceLeaves;
1171       
1172        // set the number of leaves 'evaluated' from the previous methods
1173        // we go for the same numbers, but we try to optimize both subdivisions
1174        switch (mObjectSpaceSubdivisionType)
1175        {
1176        case BV_BASED_OBJ_SUBDIV:
1177                maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
1178                break;
1179        case KD_BASED_OBJ_SUBDIV:
1180                maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
1181        default:
1182                maxObjectSpaceLeaves = 0;
1183                break;
1184        }
1185
1186        // This method subdivides view space / object space
1187        // in order to converge to some optimal cost for this partition
1188        // start with object space partiton
1189        // then optimizate view space partition for the current osp
1190        // and vice versa until iteration depth is reached.
1191        while (1)
1192        {
1193                char subdivisionStatsLog[100];
1194                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1195                mSubdivisionStats.open(subdivisionStatsLog);
1196
1197                // subdivide object space first
1198                SubdivisionCandidate *ospVc =
1199                        ResetObjectSpaceSubdivision(sampleRays, objects);
1200       
1201                // set the number of leaves 'evaluated' from the previous methods
1202                // we go for the same numbers, but we try to optimize both subdivisions
1203                mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
1204                mTQueue.Push(ospVc);
1205
1206                // process object space candidates
1207                RunConstruction(false);
1208
1209                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1210                mSubdivisionStats.close();
1211
1212                if ((++ steps) >= limit)
1213                        break;
1214
1215                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1216                mSubdivisionStats.open(subdivisionStatsLog);
1217
1218                /////////////////
1219                // subdivide view space with respect to the objects
1220
1221                SubdivisionCandidate *vspVc =
1222                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
1223
1224                mVspTree->mMaxViewCells = maxViewSpaceLeaves;
1225                mTQueue.Push(vspVc);
1226
1227                // process view space candidates
1228                RunConstruction(false);
1229
1230                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1231                mSubdivisionStats.close();
1232
1233                if ((++ steps) >= limit)
1234                        break;
1235        }
1236       
1237        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1238
1239        mHierarchyStats.Stop();
1240        mVspTree->mVspStats.Stop();
1241        FinishObjectSpaceSubdivision(objects);
1242}
1243
1244
1245
1246bool HierarchyManager::FinishedConstruction() const
1247{
1248        return mTQueue.Empty();
1249}
1250
1251
1252bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
1253{
1254        /*switch (mObjectSpaceSubdivisionType)
1255        {
1256        case KD_BASED_OBJ_SUBDIV:
1257                return mOspTree && mOspTree->GetRoot();
1258        case BV_BASED_OBJ_SUBDIV:
1259                return mBvHierarchy && mBvHierarchy->GetRoot();
1260        default:
1261                return false;
1262        }*/
1263        return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
1264}
1265
1266
1267bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
1268{
1269        return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
1270        //return mVspTree && mVspTree->GetRoot();
1271}
1272
1273
1274void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
1275                                                                                          SubdivisionCandidateContainer &dirtyList)
1276{
1277        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
1278        SubdivisionCandidate::NewMail();
1279
1280        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
1281        {
1282                (*sit)->CollectDirtyCandidates(dirtyList, true);
1283        }
1284}
1285
1286
1287void HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
1288                                                                   SplitQueue &splitQueue,
1289                                                                   const bool recomputeSplitPlaneOnRepair)
1290{
1291        // for each update of the view space partition:
1292        // the candidates from object space partition which
1293        // have been afected by the view space split (the kd split candidates
1294        // which saw the view cell which was split) must be reevaluated
1295        // (maybe not locally, just reinsert them into the queue)
1296        //
1297        // vice versa for the view cells
1298        // for each update of the object space partition
1299        // reevaluate split candidate for view cells which saw the split kd cell
1300        //
1301        // the priority queue update can be solved by implementing a binary heap
1302        // (explicit data structure, binary tree)
1303        // *) inserting and removal is efficient
1304        // *) search is not efficient => store queue position with each
1305        // split candidate
1306
1307        // collect list of "dirty" candidates
1308        const long startTime = GetTime();
1309        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
1310       
1311
1312        ///////////////////////////
1313        //-- reevaluate the dirty list
1314
1315        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
1316       
1317        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
1318        {
1319                SubdivisionCandidate* sc = *sit;
1320                const float rcd = sc->GetRenderCostDecrease();
1321               
1322                // erase from queue
1323                splitQueue.Erase(sc);
1324                // reevaluate candidate
1325                sc->EvalCandidate(recomputeSplitPlaneOnRepair);
1326                 // reinsert
1327                splitQueue.Push(sc);
1328
1329                cout << ".";
1330
1331#ifdef _DEBUG
1332                Debug << "candidate " << sc << " reevaluated\n"
1333                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
1334                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
1335#endif 
1336        }
1337
1338        const long endTime = GetTime();
1339        const Real timeDiff = TimeDiff(startTime, endTime);
1340
1341        mHierarchyStats.mRepairTime += timeDiff;
1342
1343        if (0) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
1344}
1345
1346
1347void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
1348{
1349        SubdivisionCandidateContainer mCandidateBuffer;
1350
1351        // remove from queue
1352        while (!splitQueue.Empty())
1353        {
1354                SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
1355                 // reevaluate local split plane and priority
1356                candidate->EvalCandidate(recomputeSplitPlane);
1357                cout << ".";
1358                mCandidateBuffer.push_back(candidate);
1359        }
1360
1361        // put back into queue
1362        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
1363    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
1364        {
1365                splitQueue.Push(*sit);
1366        }
1367}
1368
1369
1370void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
1371{
1372        // the type of the view cells hierarchy
1373        switch (mObjectSpaceSubdivisionType)
1374        {
1375        case KD_BASED_OBJ_SUBDIV:
1376                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
1377                mOspTree->Export(stream);
1378                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1379                break;         
1380        case BV_BASED_OBJ_SUBDIV:
1381                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
1382                mBvHierarchy->Export(stream);
1383                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1384                break;
1385        }
1386}
1387
1388
1389bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
1390                                                                          const Vector3 &hitPoint,
1391                                                                          ViewCell *vc,
1392                                                                          const float pdf,
1393                                                                          float &contribution) const
1394{
1395        if (!obj) return false;
1396
1397        switch (mObjectSpaceSubdivisionType)
1398        {
1399        case NO_OBJ_SUBDIV:
1400                {
1401                        // potentially visible objects
1402                        return vc->AddPvsSample(obj, pdf, contribution);
1403                }
1404        case KD_BASED_OBJ_SUBDIV:
1405                {
1406                        // potentially visible kd cells
1407                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
1408                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
1409                }
1410        case BV_BASED_OBJ_SUBDIV:
1411                {
1412                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1413                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1414                       
1415                        return vc->AddPvsSample(bvhObj, pdf, contribution);
1416                }
1417        default:
1418                return false;
1419        }
1420}
1421
1422
1423void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
1424{
1425        stream << mHierarchyStats << endl;
1426        stream << "\nview space:" << endl << endl;
1427        stream << mVspTree->GetStatistics() << endl;
1428        stream << "\nobject space:" << endl << endl;
1429
1430        switch (mObjectSpaceSubdivisionType)
1431        {
1432        case KD_BASED_OBJ_SUBDIV:
1433                {
1434                        stream << mOspTree->GetStatistics() << endl;
1435                        break;
1436                }
1437        case BV_BASED_OBJ_SUBDIV:
1438                {
1439                        stream << mBvHierarchy->GetStatistics() << endl;
1440                        break;
1441                }
1442        default:
1443                break;
1444        }
1445}
1446
1447
1448void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
1449                                                                                                  const ObjectContainer &objects,
1450                                                                                                  const AxisAlignedBox3 *bbox,
1451                                                                                                  const bool exportBounds) const
1452{
1453        switch (mObjectSpaceSubdivisionType)
1454        {
1455        case KD_BASED_OBJ_SUBDIV:
1456                {
1457                        ExportOspTree(exporter, objects);
1458                        break;
1459                }
1460        case BV_BASED_OBJ_SUBDIV:
1461                {
1462                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
1463                        break;
1464                }
1465        default:
1466                break;
1467        }
1468}
1469
1470
1471void HierarchyManager::ExportOspTree(Exporter *exporter,
1472                                                                         const ObjectContainer &objects) const
1473{
1474        if (0) exporter->ExportGeometry(objects);
1475                       
1476        exporter->SetWireframe();
1477        exporter->ExportOspTree(*mOspTree, 0);
1478}
1479
1480
1481Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1482                                                                                                  const bool isTermination) const
1483{
1484
1485        Intersectable *obj;
1486        Vector3 pt;
1487        KdNode *node;
1488
1489        ray.GetSampleData(isTermination, pt, &obj, &node);
1490       
1491        if (!obj) return NULL;
1492
1493        switch (mObjectSpaceSubdivisionType)
1494        {
1495        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1496                {
1497                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1498                        return mOspTree->GetOrCreateKdIntersectable(leaf);
1499                }
1500        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1501                {
1502                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1503                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1504                }
1505        default:
1506                return obj;
1507        }
1508}
1509
1510
1511void HierarchyStatistics::Print(ostream &app) const
1512{
1513        app << "=========== Hierarchy statistics ===============\n";
1514
1515        app << setprecision(4);
1516
1517        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1518       
1519        app << "#N_RTIME  ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1520
1521        app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1522
1523        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1524
1525        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1526
1527        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1528
1529        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1530       
1531        app << "========== END OF Hierarchy statistics ==========\n";
1532}
1533
1534
1535static void RemoveRayRefs(const ObjectContainer &objects)
1536{
1537        ObjectContainer::const_iterator oit, oit_end = objects.end();
1538        for (oit = objects.begin(); oit != oit_end; ++ oit)
1539        {
1540                (*oit)->mVssRays.clear();
1541        }
1542}
1543
1544
1545void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1546                                                                                                        const bool removeRayRefs) const
1547{
1548        switch (mObjectSpaceSubdivisionType)
1549        {
1550        case KD_BASED_OBJ_SUBDIV:
1551                {
1552                        mOspTree->mOspStats.Stop();
1553                        break;
1554                }
1555        case BV_BASED_OBJ_SUBDIV:
1556                {
1557                        mBvHierarchy->mBvhStats.Stop();
1558                        if (removeRayRefs)
1559                                RemoveRayRefs(objects);
1560                        break;
1561                }
1562        default:
1563                break;
1564        }
1565}
1566
1567
1568void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1569{
1570        stream << "<BoundingBoxes>" << endl;
1571           
1572        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1573        {
1574                KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1575
1576                int id = 0;
1577                for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1578                {
1579                        Intersectable *obj = (*kit).second;
1580                        const AxisAlignedBox3 box = obj->GetBox();
1581               
1582                        obj->SetId(id);
1583
1584                        stream << "<BoundingBox" << " id=\"" << id << "\""
1585                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1586                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1587                }
1588        }
1589        else
1590        {
1591                ObjectContainer::const_iterator oit, oit_end = objects.end();
1592
1593                for (oit = objects.begin(); oit != oit_end; ++ oit)
1594                {
1595                        const AxisAlignedBox3 box = (*oit)->GetBox();
1596               
1597                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1598                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1599                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1600                }
1601        }
1602               
1603        stream << "</BoundingBoxes>" << endl;
1604}
1605
1606/*typedef priority_queue<ViewCell *, vector<ViewCell *>,
1607                                           myless<vector<ViewCell *>::value_type> > ViewCellsQueue;
1608
1609typedef priority_queue<BvhNode *, vector<BvhNode *>,
1610                                           myless<vector<BvhNode *>::value_type> > BvhQueue;
1611
1612typedef priority_queue<VspNode *, vector<VspNode *>,
1613                                           myless<vector<VspNode *>::value_type> > VspQueue;
1614*/
1615static void UpdateStats(ofstream &stats,
1616                                                const int splits,
1617                                                const float totalRenderCost,
1618                                                const int entriesInPvs,
1619                                                const float memoryCost,
1620                                                const bool vsp)
1621{
1622        stats << "#Pass\n" << 0 << endl
1623                   << "#Splits\n" << splits << endl
1624                   << "#TotalRenderCost\n" << totalRenderCost << endl
1625                   << "#TotalEntriesInPvs\n" << entriesInPvs << endl
1626                   << "#Memory\n" << memoryCost << endl
1627                   << "#Vsp\n" << (vsp ? 1 : 0) << endl
1628                   << endl;
1629}
1630
1631
1632void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,                                                                                                                                             
1633                                                                                   const ObjectContainer &objects,
1634                                                                                   const string &filename)
1635{
1636        VspTree *oldVspTree = mVspTree;
1637        ViewCellsManager *vm = mVspTree->mViewCellsManager;
1638        BvHierarchy *oldHierarchy = mBvHierarchy;
1639
1640        mBvHierarchy = new BvHierarchy();
1641        mBvHierarchy->mHierarchyManager = this;
1642        mBvHierarchy->mViewCellsManager = vm;
1643
1644        mVspTree = new VspTree();
1645        mVspTree->mHierarchyManager = this;
1646        mVspTree->mViewCellsManager = vm;
1647
1648        // create first nodes
1649        mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
1650        InitialiseObjectSpaceSubdivision(objects);
1651
1652        const long startTime = GetTime();
1653        cout << "Constructing evaluation hierarchies ... \n";
1654       
1655        ofstream stats;
1656        stats.open(filename.c_str());
1657        SplitQueue tQueue;
1658
1659        BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
1660        VspNode *oldVspRoot = oldVspTree->GetRoot();
1661
1662        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
1663       
1664        SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
1665        SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects);
1666
1667    firstVsp->mEvaluationHack = oldVspRoot;
1668        firstBvh->mEvaluationHack = oldBvhRoot;
1669
1670        firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
1671        firstBvh->SetPriority((float)-oldBvhRoot->mTimeStamp);
1672
1673        tQueue.Push(firstVsp);
1674        tQueue.Push(firstBvh);
1675
1676        ExportStats(stats, tQueue, objects);
1677
1678        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1679        RemoveRayRefs(objects);
1680
1681        // view cells needed only for evaluation
1682        ViewCellContainer viewCells;
1683        mVspTree->CollectViewCells(viewCells, false);
1684       
1685        // helper trees can be destroyed
1686        DEL_PTR(mVspTree);
1687        DEL_PTR(mBvHierarchy);
1688
1689        CLEAR_CONTAINER(viewCells);
1690
1691        // reset hierarchies
1692        mVspTree = oldVspTree;
1693        mBvHierarchy = oldHierarchy;
1694
1695        // reinstall old bv refs
1696        vector<BvhLeaf *> leaves;
1697        mBvHierarchy->CollectLeaves(leaves);
1698        vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
1699
1700        for (bit = leaves.begin(); bit != bit_end; ++ bit)
1701        {
1702                mBvHierarchy->AssociateObjectsWithLeaf(*bit);
1703        }
1704}
1705
1706
1707void HierarchyManager::ExportStats(ofstream &stats,
1708                                                                   SplitQueue &tQueue,
1709                                                                   const ObjectContainer &objects)
1710{
1711        float totalRenderCost = (float)objects.size();
1712        int entriesInPvs = 1;
1713        int steps = 0;
1714
1715        cout << "exporting vsposp stats ... " << endl;
1716        const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
1717
1718        /////////////
1719        //-- first view cell
1720        UpdateStats(stats, 2, totalRenderCost, entriesInPvs, memoryCost, true);
1721
1722        //-- go through tree in the order of render cost decrease
1723        //-- which is the same order as the view cells were merged
1724        //-- or the reverse order of subdivision for subdivision-only
1725        //-- view cell hierarchies.
1726       
1727        while (!tQueue.Empty())
1728        {
1729                SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
1730                bool isLeaf;
1731                int timeStamp;
1732                float rcDecr;
1733                int entriesIncr;
1734
1735        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
1736                {
1737                        timeStamp = (int)-nextCandidate->GetPriority();
1738
1739                        VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
1740                        VspNode *oldNode = (VspNode *)nextCandidate->mEvaluationHack;
1741                       
1742                        isLeaf = newNode->IsLeaf();
1743                        rcDecr = oldNode->mRenderCostDecr;
1744                        entriesIncr = oldNode->mPvsEntriesIncr;
1745                }
1746                else
1747                {
1748                        timeStamp = (int)-nextCandidate->GetPriority();
1749                       
1750                        BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
1751                        BvhNode *oldNode = (BvhNode *)nextCandidate->mEvaluationHack;
1752                       
1753                        isLeaf = newNode->IsLeaf();
1754                        rcDecr = oldNode->mRenderCostDecr;
1755                        entriesIncr = oldNode->mPvsEntriesIncr;
1756                }               
1757                               
1758                if (!isLeaf)
1759                {
1760                        totalRenderCost -= rcDecr;
1761                        entriesInPvs += entriesIncr;
1762                        // if (rcDecr <= 0)
1763                        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
1764                                cout << "v";//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
1765                        else
1766                                cout << "o";//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
1767
1768                        ++ steps;
1769
1770                        if ((steps % 500) == 499)
1771                                cout << steps << " steps taken" << endl;
1772                        const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
1773                        UpdateStats(stats, steps, totalRenderCost, entriesInPvs, memoryCost, false);
1774                }
1775
1776                DEL_PTR(nextCandidate);
1777        }
1778
1779        stats.close();
1780}
1781
1782       
1783}
Note: See TracBrowser for help on using the repository browser.