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

Revision 1667, 43.9 KB checked in by mattausch, 18 years ago (diff)

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