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

Revision 1676, 44.1 KB checked in by mattausch, 18 years ago (diff)

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