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

Revision 1664, 44.4 KB checked in by mattausch, 18 years ago (diff)

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