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

Revision 1697, 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 = 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 threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
949                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
950               
951                const float priority = sc->GetPriority();
952               
953                //float rc = (float)sc->GetRenderCostDecrease() / (mInitialRenderCost - mHierarchyStats.mTotalCost + 1.0f);
954                //float mc = (float)sc->GetPvsEntriesIncr() / (float)mHierarchyStats.mPvsEntries;       
955                //cout << "dRc: " << sc->GetRenderCostDecrease() << " dMem: " << sc->GetPvsEntriesIncr() << " ratio1 " << rc << " ratio2 " << mc << " const: " << 1.0f - GetMemoryConst() << endl;
956
957                ////////
958                //-- subdivide leaf node of either type
959
960                const bool repairQueue = false;
961                const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
962
963                if (success)
964                {
965                        sc->CollectDirtyCandidates(dirtyCandidates, true);
966                        ++ steps;
967                }
968
969                DEL_PTR(sc);
970
971                // minimum slope reached
972                if ((steps >= maxSteps) ||
973                        ((priority < threshold) && !(steps < minSteps)))
974                {
975                        cout << "\n**************** breaking on " << priority << " smaller than " << threshold << endl;
976                        break;
977                }
978
979        }
980
981        return steps;
982}
983
984
985SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
986                                                                                                                                        const ObjectContainer &objects)
987{       
988        SubdivisionCandidate *firstCandidate;
989
990        // object space partition constructed => reconstruct
991        switch (mObjectSpaceSubdivisionType)
992        {
993        case BV_BASED_OBJ_SUBDIV:
994                {
995                        cout << "\nreseting bv hierarchy" << endl;
996                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
997                               
998                        // rather use this: remove previous nodes and add the two new ones
999                        //mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
1000                        mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
1001                       
1002                        // create root
1003                        mBvHierarchy->Initialise(objects);
1004       
1005                        firstCandidate = mBvHierarchy->Reset(sampleRays, objects);
1006
1007                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
1008                       
1009                        //mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
1010                        mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
1011
1012                        mHierarchyStats.mMemory =
1013                                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1014
1015                        mHierarchyStats.mRenderCostDecrease = 0;
1016
1017                        // evaluate stats before first subdivision
1018                        EvalSubdivisionStats();
1019                        cout << "finished bv hierarchy preparation" << endl;
1020                }
1021                break;
1022
1023        case KD_BASED_OBJ_SUBDIV:
1024                // TODO
1025        default:
1026                firstCandidate = NULL;
1027                break;
1028        }
1029
1030        return firstCandidate;
1031}
1032
1033
1034SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
1035                                                                                                                                  const ObjectContainer &objects,
1036                                                                                                                                  AxisAlignedBox3 *forcedViewSpace)
1037{
1038        ViewCellsManager *vm = mVspTree->mViewCellsManager;
1039
1040        // HACK: rather not destroy vsp tree
1041        DEL_PTR(mVspTree);
1042        mVspTree = new VspTree();
1043
1044        mVspTree->mHierarchyManager = this;
1045        mVspTree->mViewCellsManager = vm;
1046
1047        mVspTree->Initialise(sampleRays, forcedViewSpace);
1048       
1049        //-- reset stats
1050    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1;
1051       
1052        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
1053       
1054        mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
1055        mHierarchyStats.mRenderCostDecrease = 0;
1056
1057        mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1058
1059        // evaluate new stats before first subdivsiion
1060        EvalSubdivisionStats();
1061
1062        return vsc;
1063}
1064
1065
1066void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
1067                                                                                   const ObjectContainer &objects,
1068                                                                                   AxisAlignedBox3 *forcedViewSpace)
1069{
1070        mHierarchyStats.Reset();
1071        mHierarchyStats.Start();
1072        mHierarchyStats.mNodes = 2;
1073       
1074        mHierarchyStats.mTotalCost = (float)objects.size();
1075        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
1076
1077        const long startTime = GetTime();
1078        cout << "Constructing view space / object space tree ... \n";
1079       
1080        // initialise view / object space
1081        mVspTree->Initialise(sampleRays, forcedViewSpace);
1082        InitialiseObjectSpaceSubdivision(objects);
1083
1084        // use sah for evaluating osp tree construction
1085        // in the first iteration of the subdivision
1086
1087        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
1088        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
1089
1090        SubdivisionCandidate *osc =
1091                PrepareObjectSpaceSubdivision(sampleRays, objects);
1092        mTQueue.Push(osc);
1093
1094        //////////////////////////
1095
1096
1097        const int limit = mNumMultiLevels;
1098        int i = 0;
1099
1100        // This method subdivides view space / object space
1101        // in order to converge to some optimal cost for this partition
1102        // start with object space partiton
1103        // then optimizate view space partition for the current osp
1104        // and vice versa until iteration depth is reached.
1105        while (1)
1106        {
1107                char subdivisionStatsLog[100];
1108                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1109                mSubdivisionStats.open(subdivisionStatsLog);
1110
1111                // subdivide object space first
1112                osc = ResetObjectSpaceSubdivision(sampleRays, objects);
1113                mTQueue.Push(osc);
1114
1115                // process object space candidates
1116                RunConstruction(false);
1117
1118                // object space subdivision constructed
1119                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1120
1121                cout << "iteration " << i << " of " << limit << " finished" << endl;
1122                mSubdivisionStats.close();
1123
1124                if ((i ++) >= limit)
1125                        break;
1126
1127                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1128                mSubdivisionStats.open(subdivisionStatsLog);
1129
1130
1131                /////////////////
1132                // subdivide view space with respect to the objects
1133
1134                SubdivisionCandidate *vspVc =
1135                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
1136                mTQueue.Push(vspVc);
1137
1138                // view space subdivision constructed
1139                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
1140               
1141                // process view space candidates
1142                RunConstruction(false);
1143
1144                cout << "iteration " << i << " of " << limit << " finished" << endl;
1145                mSubdivisionStats.close();
1146
1147                if ((i ++) >= limit)
1148                        break;
1149        }
1150       
1151        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1152
1153        mHierarchyStats.Stop();
1154        mVspTree->mVspStats.Stop();
1155        FinishObjectSpaceSubdivision(objects);
1156}
1157
1158
1159void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                     
1160                                                                                  const ObjectContainer &objects,
1161                                                                                  AxisAlignedBox3 *forcedViewSpace)
1162{
1163        const long startTime = GetTime();
1164        const int limit = mNumMultiLevels;
1165
1166        // open up new subdivision
1167        mSubdivisionStats.close();
1168
1169        int steps = 0;
1170
1171        int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
1172        int maxObjectSpaceLeaves;
1173       
1174        // set the number of leaves 'evaluated' from the previous methods
1175        // we go for the same numbers, but we try to optimize both subdivisions
1176        switch (mObjectSpaceSubdivisionType)
1177        {
1178        case BV_BASED_OBJ_SUBDIV:
1179                maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
1180                break;
1181        case KD_BASED_OBJ_SUBDIV:
1182                maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
1183        default:
1184                maxObjectSpaceLeaves = 0;
1185                break;
1186        }
1187
1188        // This method subdivides view space / object space
1189        // in order to converge to some optimal cost for this partition
1190        // start with object space partiton
1191        // then optimizate view space partition for the current osp
1192        // and vice versa until iteration depth is reached.
1193        while (1)
1194        {
1195                char subdivisionStatsLog[100];
1196                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1197                mSubdivisionStats.open(subdivisionStatsLog);
1198
1199                // subdivide object space first
1200                SubdivisionCandidate *ospVc =
1201                        ResetObjectSpaceSubdivision(sampleRays, objects);
1202       
1203                // set the number of leaves 'evaluated' from the previous methods
1204                // we go for the same numbers, but we try to optimize both subdivisions
1205                mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
1206                mTQueue.Push(ospVc);
1207
1208                // process object space candidates
1209                RunConstruction(false);
1210
1211                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1212                mSubdivisionStats.close();
1213
1214                if ((++ steps) >= limit)
1215                        break;
1216
1217                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1218                mSubdivisionStats.open(subdivisionStatsLog);
1219
1220                /////////////////
1221                // subdivide view space with respect to the objects
1222
1223                SubdivisionCandidate *vspVc =
1224                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
1225
1226                mVspTree->mMaxViewCells = maxViewSpaceLeaves;
1227                mTQueue.Push(vspVc);
1228
1229                // process view space candidates
1230                RunConstruction(false);
1231
1232                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1233                mSubdivisionStats.close();
1234
1235                if ((++ steps) >= limit)
1236                        break;
1237        }
1238       
1239        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1240
1241        mHierarchyStats.Stop();
1242        mVspTree->mVspStats.Stop();
1243        FinishObjectSpaceSubdivision(objects);
1244}
1245
1246
1247
1248bool HierarchyManager::FinishedConstruction() const
1249{
1250        return mTQueue.Empty();
1251}
1252
1253
1254bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
1255{
1256        /*switch (mObjectSpaceSubdivisionType)
1257        {
1258        case KD_BASED_OBJ_SUBDIV:
1259                return mOspTree && mOspTree->GetRoot();
1260        case BV_BASED_OBJ_SUBDIV:
1261                return mBvHierarchy && mBvHierarchy->GetRoot();
1262        default:
1263                return false;
1264        }*/
1265        return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
1266}
1267
1268
1269bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
1270{
1271        return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
1272        //return mVspTree && mVspTree->GetRoot();
1273}
1274
1275
1276void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
1277                                                                                          SubdivisionCandidateContainer &dirtyList)
1278{
1279        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
1280        SubdivisionCandidate::NewMail();
1281
1282        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
1283        {
1284                (*sit)->CollectDirtyCandidates(dirtyList, true);
1285        }
1286}
1287
1288
1289void HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
1290                                                                   SplitQueue &splitQueue,
1291                                                                   const bool recomputeSplitPlaneOnRepair)
1292{
1293        // for each update of the view space partition:
1294        // the candidates from object space partition which
1295        // have been afected by the view space split (the kd split candidates
1296        // which saw the view cell which was split) must be reevaluated
1297        // (maybe not locally, just reinsert them into the queue)
1298        //
1299        // vice versa for the view cells
1300        // for each update of the object space partition
1301        // reevaluate split candidate for view cells which saw the split kd cell
1302        //
1303        // the priority queue update can be solved by implementing a binary heap
1304        // (explicit data structure, binary tree)
1305        // *) inserting and removal is efficient
1306        // *) search is not efficient => store queue position with each
1307        // split candidate
1308
1309        // collect list of "dirty" candidates
1310        const long startTime = GetTime();
1311        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
1312       
1313
1314        ///////////////////////////
1315        //-- reevaluate the dirty list
1316
1317        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
1318       
1319        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
1320        {
1321                SubdivisionCandidate* sc = *sit;
1322                const float rcd = sc->GetRenderCostDecrease();
1323               
1324                // erase from queue
1325                splitQueue.Erase(sc);
1326                // reevaluate candidate
1327                sc->EvalCandidate(recomputeSplitPlaneOnRepair);
1328                 // reinsert
1329                splitQueue.Push(sc);
1330
1331                cout << ".";
1332
1333#ifdef _DEBUG
1334                Debug << "candidate " << sc << " reevaluated\n"
1335                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
1336                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
1337#endif 
1338        }
1339
1340        const long endTime = GetTime();
1341        const Real timeDiff = TimeDiff(startTime, endTime);
1342
1343        mHierarchyStats.mRepairTime += timeDiff;
1344
1345        if (0) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
1346}
1347
1348
1349void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
1350{
1351        SubdivisionCandidateContainer mCandidateBuffer;
1352
1353        // remove from queue
1354        while (!splitQueue.Empty())
1355        {
1356                SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
1357                 // reevaluate local split plane and priority
1358                candidate->EvalCandidate(recomputeSplitPlane);
1359                cout << ".";
1360                mCandidateBuffer.push_back(candidate);
1361        }
1362
1363        // put back into queue
1364        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
1365    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
1366        {
1367                splitQueue.Push(*sit);
1368        }
1369}
1370
1371
1372void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
1373{
1374        // the type of the view cells hierarchy
1375        switch (mObjectSpaceSubdivisionType)
1376        {
1377        case KD_BASED_OBJ_SUBDIV:
1378                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
1379                mOspTree->Export(stream);
1380                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1381                break;         
1382        case BV_BASED_OBJ_SUBDIV:
1383                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
1384                mBvHierarchy->Export(stream);
1385                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1386                break;
1387        }
1388}
1389
1390
1391bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
1392                                                                          const Vector3 &hitPoint,
1393                                                                          ViewCell *vc,
1394                                                                          const float pdf,
1395                                                                          float &contribution) const
1396{
1397        if (!obj) return false;
1398
1399        switch (mObjectSpaceSubdivisionType)
1400        {
1401        case NO_OBJ_SUBDIV:
1402                {
1403                        // potentially visible objects
1404                        return vc->AddPvsSample(obj, pdf, contribution);
1405                }
1406        case KD_BASED_OBJ_SUBDIV:
1407                {
1408                        // potentially visible kd cells
1409                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
1410                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
1411                }
1412        case BV_BASED_OBJ_SUBDIV:
1413                {
1414                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1415                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1416                       
1417                        return vc->AddPvsSample(bvhObj, pdf, contribution);
1418                }
1419        default:
1420                return false;
1421        }
1422}
1423
1424
1425void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
1426{
1427        stream << mHierarchyStats << endl;
1428        stream << "\nview space:" << endl << endl;
1429        stream << mVspTree->GetStatistics() << endl;
1430        stream << "\nobject space:" << endl << endl;
1431
1432        switch (mObjectSpaceSubdivisionType)
1433        {
1434        case KD_BASED_OBJ_SUBDIV:
1435                {
1436                        stream << mOspTree->GetStatistics() << endl;
1437                        break;
1438                }
1439        case BV_BASED_OBJ_SUBDIV:
1440                {
1441                        stream << mBvHierarchy->GetStatistics() << endl;
1442                        break;
1443                }
1444        default:
1445                break;
1446        }
1447}
1448
1449
1450void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
1451                                                                                                  const ObjectContainer &objects,
1452                                                                                                  const AxisAlignedBox3 *bbox,
1453                                                                                                  const bool exportBounds) const
1454{
1455        switch (mObjectSpaceSubdivisionType)
1456        {
1457        case KD_BASED_OBJ_SUBDIV:
1458                {
1459                        ExportOspTree(exporter, objects);
1460                        break;
1461                }
1462        case BV_BASED_OBJ_SUBDIV:
1463                {
1464                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
1465                        break;
1466                }
1467        default:
1468                break;
1469        }
1470}
1471
1472
1473void HierarchyManager::ExportOspTree(Exporter *exporter,
1474                                                                         const ObjectContainer &objects) const
1475{
1476        if (0) exporter->ExportGeometry(objects);
1477                       
1478        exporter->SetWireframe();
1479        exporter->ExportOspTree(*mOspTree, 0);
1480}
1481
1482
1483Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1484                                                                                                  const bool isTermination) const
1485{
1486
1487        Intersectable *obj;
1488        Vector3 pt;
1489        KdNode *node;
1490
1491        ray.GetSampleData(isTermination, pt, &obj, &node);
1492       
1493        if (!obj) return NULL;
1494
1495        switch (mObjectSpaceSubdivisionType)
1496        {
1497        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1498                {
1499                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1500                        return mOspTree->GetOrCreateKdIntersectable(leaf);
1501                }
1502        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1503                {
1504                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1505                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1506                }
1507        default:
1508                return obj;
1509        }
1510}
1511
1512
1513void HierarchyStatistics::Print(ostream &app) const
1514{
1515        app << "=========== Hierarchy statistics ===============\n";
1516
1517        app << setprecision(4);
1518
1519        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1520       
1521        app << "#N_RTIME  ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1522
1523        app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1524
1525        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1526
1527        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1528
1529        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1530
1531        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1532       
1533        app << "========== END OF Hierarchy statistics ==========\n";
1534}
1535
1536
1537static void RemoveRayRefs(const ObjectContainer &objects)
1538{
1539        ObjectContainer::const_iterator oit, oit_end = objects.end();
1540        for (oit = objects.begin(); oit != oit_end; ++ oit)
1541        {
1542                (*oit)->DelRayRefs();
1543        }
1544}
1545
1546
1547void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1548                                                                                                        const bool removeRayRefs) const
1549{
1550        switch (mObjectSpaceSubdivisionType)
1551        {
1552        case KD_BASED_OBJ_SUBDIV:
1553                {
1554                        mOspTree->mOspStats.Stop();
1555                        break;
1556                }
1557        case BV_BASED_OBJ_SUBDIV:
1558                {
1559                        mBvHierarchy->mBvhStats.Stop();
1560                        if (removeRayRefs)
1561                                RemoveRayRefs(objects);
1562                        break;
1563                }
1564        default:
1565                break;
1566        }
1567}
1568
1569
1570void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1571{
1572        stream << "<BoundingBoxes>" << endl;
1573           
1574        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1575        {
1576                KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1577
1578                int id = 0;
1579                for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1580                {
1581                        Intersectable *obj = (*kit).second;
1582                        const AxisAlignedBox3 box = obj->GetBox();
1583               
1584                        obj->SetId(id);
1585
1586                        stream << "<BoundingBox" << " id=\"" << id << "\""
1587                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1588                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1589                }
1590        }
1591        else
1592        {
1593                ObjectContainer::const_iterator oit, oit_end = objects.end();
1594
1595                for (oit = objects.begin(); oit != oit_end; ++ oit)
1596                {
1597                        const AxisAlignedBox3 box = (*oit)->GetBox();
1598               
1599                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1600                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1601                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1602                }
1603        }
1604               
1605        stream << "</BoundingBoxes>" << endl;
1606}
1607
1608/*typedef priority_queue<ViewCell *, vector<ViewCell *>,
1609                                           myless<vector<ViewCell *>::value_type> > ViewCellsQueue;
1610
1611typedef priority_queue<BvhNode *, vector<BvhNode *>,
1612                                           myless<vector<BvhNode *>::value_type> > BvhQueue;
1613
1614typedef priority_queue<VspNode *, vector<VspNode *>,
1615                                           myless<vector<VspNode *>::value_type> > VspQueue;
1616*/
1617static void UpdateStats(ofstream &stats,
1618                                                const int splits,
1619                                                const float totalRenderCost,
1620                                                const int entriesInPvs,
1621                                                const float memoryCost,
1622                                                const bool vsp)
1623{
1624        stats << "#Pass\n" << 0 << endl
1625                   << "#Splits\n" << splits << endl
1626                   << "#TotalRenderCost\n" << totalRenderCost << endl
1627                   << "#TotalEntriesInPvs\n" << entriesInPvs << endl
1628                   << "#Memory\n" << memoryCost << endl
1629                   << "#Vsp\n" << (vsp ? 1 : 0) << endl
1630                   << endl;
1631}
1632
1633
1634void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,                                                                                                                                             
1635                                                                                   const ObjectContainer &objects,
1636                                                                                   const string &filename)
1637{
1638        VspTree *oldVspTree = mVspTree;
1639        ViewCellsManager *vm = mVspTree->mViewCellsManager;
1640        BvHierarchy *oldHierarchy = mBvHierarchy;
1641
1642        mBvHierarchy = new BvHierarchy();
1643        mBvHierarchy->mHierarchyManager = this;
1644        mBvHierarchy->mViewCellsManager = vm;
1645
1646        mVspTree = new VspTree();
1647        mVspTree->mHierarchyManager = this;
1648        mVspTree->mViewCellsManager = vm;
1649
1650        // create first nodes
1651        mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
1652        InitialiseObjectSpaceSubdivision(objects);
1653
1654        const long startTime = GetTime();
1655        cout << "Constructing evaluation hierarchies ... \n";
1656       
1657        ofstream stats;
1658        stats.open(filename.c_str());
1659        SplitQueue tQueue;
1660
1661        BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
1662        VspNode *oldVspRoot = oldVspTree->GetRoot();
1663
1664        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
1665       
1666        SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
1667        SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects);
1668
1669    firstVsp->mEvaluationHack = oldVspRoot;
1670        firstBvh->mEvaluationHack = oldBvhRoot;
1671
1672        firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
1673        firstBvh->SetPriority((float)-oldBvhRoot->mTimeStamp);
1674
1675        tQueue.Push(firstVsp);
1676        tQueue.Push(firstBvh);
1677
1678        ExportStats(stats, tQueue, objects);
1679
1680        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1681        RemoveRayRefs(objects);
1682
1683        // view cells needed only for evaluation
1684        ViewCellContainer viewCells;
1685        mVspTree->CollectViewCells(viewCells, false);
1686       
1687        // helper trees can be destroyed
1688        DEL_PTR(mVspTree);
1689        DEL_PTR(mBvHierarchy);
1690
1691        CLEAR_CONTAINER(viewCells);
1692
1693        // reset hierarchies
1694        mVspTree = oldVspTree;
1695        mBvHierarchy = oldHierarchy;
1696
1697        // reinstall old bv refs
1698        vector<BvhLeaf *> leaves;
1699        mBvHierarchy->CollectLeaves(leaves);
1700        vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
1701
1702        for (bit = leaves.begin(); bit != bit_end; ++ bit)
1703        {
1704                mBvHierarchy->AssociateObjectsWithLeaf(*bit);
1705        }
1706}
1707
1708
1709void HierarchyManager::ExportStats(ofstream &stats,
1710                                                                   SplitQueue &tQueue,
1711                                                                   const ObjectContainer &objects)
1712{
1713        float totalRenderCost = (float)objects.size();
1714        int entriesInPvs = 1;
1715        int steps = 0;
1716
1717        cout << "exporting vsposp stats ... " << endl;
1718        const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
1719
1720        /////////////
1721        //-- first view cell
1722        UpdateStats(stats, 2, totalRenderCost, entriesInPvs, memoryCost, true);
1723
1724        //-- go through tree in the order of render cost decrease
1725        //-- which is the same order as the view cells were merged
1726        //-- or the reverse order of subdivision for subdivision-only
1727        //-- view cell hierarchies.
1728       
1729        while (!tQueue.Empty())
1730        {
1731                SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
1732                bool isLeaf;
1733                int timeStamp;
1734                float rcDecr;
1735                int entriesIncr;
1736
1737        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
1738                {
1739                        timeStamp = (int)-nextCandidate->GetPriority();
1740
1741                        VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
1742                        VspNode *oldNode = (VspNode *)nextCandidate->mEvaluationHack;
1743                       
1744                        isLeaf = newNode->IsLeaf();
1745                        rcDecr = oldNode->mRenderCostDecr;
1746                        entriesIncr = oldNode->mPvsEntriesIncr;
1747                }
1748                else
1749                {
1750                        timeStamp = (int)-nextCandidate->GetPriority();
1751                       
1752                        BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
1753                        BvhNode *oldNode = (BvhNode *)nextCandidate->mEvaluationHack;
1754                       
1755                        isLeaf = newNode->IsLeaf();
1756                        rcDecr = oldNode->mRenderCostDecr;
1757                        entriesIncr = oldNode->mPvsEntriesIncr;
1758                }               
1759                               
1760                if (!isLeaf)
1761                {
1762                        totalRenderCost -= rcDecr;
1763                        entriesInPvs += entriesIncr;
1764                        // if (rcDecr <= 0)
1765                        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
1766                                cout << "v";//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
1767                        else
1768                                cout << "o";//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
1769
1770                        ++ steps;
1771
1772                        if ((steps % 500) == 499)
1773                                cout << steps << " steps taken" << endl;
1774                        const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
1775                        UpdateStats(stats, steps, totalRenderCost, entriesInPvs, memoryCost, false);
1776                }
1777
1778                DEL_PTR(nextCandidate);
1779        }
1780
1781        stats.close();
1782}
1783
1784       
1785}
Note: See TracBrowser for help on using the repository browser.