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

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