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

Revision 1640, 41.7 KB checked in by mattausch, 18 years ago (diff)

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