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

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