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

Revision 1933, 67.2 KB checked in by mattausch, 18 years ago (diff)

worked on gvs reverse sampling (still in debug state)

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#include "ViewCell.h"
24
25
26namespace GtpVisibilityPreprocessor {
27
28
29#define USE_FIXEDPOINT_T 0
30
31#define STUPID_METHOD 0
32
33
34
35/*******************************************************************/
36/*              class HierarchyManager implementation              */
37/*******************************************************************/
38
39
40HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
41mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
42mOspTree(NULL),
43mBvHierarchy(NULL)
44{
45        switch(mObjectSpaceSubdivisionType)
46        {
47        case KD_BASED_OBJ_SUBDIV:
48                mOspTree = new OspTree();
49                mOspTree->mVspTree = mVspTree;
50                mOspTree->mHierarchyManager = this;
51                break;
52        case BV_BASED_OBJ_SUBDIV:
53        mBvHierarchy = new BvHierarchy();
54                mBvHierarchy->mHierarchyManager = this;
55                break;
56        default:
57                break;
58        }
59
60        // hierarchy manager links view space partition and object space partition
61        mVspTree = new VspTree();
62        mVspTree->mHierarchyManager = this;
63       
64        mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
65        ParseEnvironment();
66}
67
68
69HierarchyManager::HierarchyManager(KdTree *kdTree):
70mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
71mBvHierarchy(NULL)
72{
73        mOspTree = new OspTree(*kdTree);
74        mOspTree->mVspTree = mVspTree;
75
76        mVspTree = new VspTree();
77        mVspTree->mHierarchyManager = this;
78
79        mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
80        ParseEnvironment();
81}
82
83
84void HierarchySubdivisionStats::Print(ostream &app) const
85{
86        app << "#Pass\n" << 0 << endl
87                << "#Splits\n" << mNumSplits << endl
88                << "#TotalRenderCost\n" << mTotalRenderCost << endl
89                << "#TotalEntriesInPvs\n" << mEntriesInPvs << endl
90                << "#Memory\n" << mMemoryCost << endl
91                << "#StepsView\n" << mViewSpaceSplits << endl
92                << "#StepsObject\n" << mObjectSpaceSplits << endl
93                << "#VspOspRatio\n" << VspOspRatio() << endl
94                << "#FullMem\n" << mFullMemory << endl
95                << "#RenderCostDecrease\n" << mRenderCostDecrease << endl
96                << "#Priority\n" << mPriority << endl
97                << "#FpsPerMb\n" << FpsPerMb() << endl
98                << endl;
99}
100
101
102void HierarchyManager::ParseEnvironment()
103{
104        Environment::GetSingleton()->GetFloatValue(
105                "Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
106        Environment::GetSingleton()->GetIntValue(
107                "Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
108
109        Environment::GetSingleton()->GetBoolValue(
110                "Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
111
112        Environment::GetSingleton()->GetIntValue(
113                "Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
114
115        Environment::GetSingleton()->GetIntValue(
116                "Hierarchy.Construction.type", mConstructionType);
117
118        Environment::GetSingleton()->GetIntValue(
119                "Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
120
121        Environment::GetSingleton()->GetIntValue(
122                "Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
123       
124        Environment::GetSingleton()->GetBoolValue(
125                "Hierarchy.Construction.repairQueue", mRepairQueue);
126
127        Environment::GetSingleton()->GetBoolValue(
128                "Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);
129
130        Environment::GetSingleton()->GetIntValue(
131                "Hierarchy.Construction.levels", mNumMultiLevels);
132
133        Environment::GetSingleton()->GetIntValue(
134                "Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
135       
136        Environment::GetSingleton()->GetIntValue(
137                "Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);
138
139        char subdivisionStatsLog[100];
140        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
141        mSubdivisionStats.open(subdivisionStatsLog);
142
143        Environment::GetSingleton()->GetBoolValue(
144                "Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);
145
146        Environment::GetSingleton()->GetBoolValue(
147                "Hierarchy.Construction.considerMemory", mConsiderMemory);
148
149        Environment::GetSingleton()->GetFloatValue(
150                "Hierarchy.Termination.maxMemory", mTermMaxMemory);
151
152        Environment::GetSingleton()->GetIntValue(
153                "Hierarchy.Construction.maxRepairs", mMaxRepairs);
154
155        Environment::GetSingleton()->GetFloatValue(
156                "Hierarchy.Construction.maxAvgRayContri", mMaxAvgRayContri);
157
158        Environment::GetSingleton()->GetFloatValue(
159                "Hierarchy.Construction.minAvgRayContri", mMinAvgRayContri);
160
161        // for comparing it with byte - value
162        mTermMaxMemory *= (1024.0f * 1024.0f);
163
164        Debug << "******** Hierarchy Manager Options ***********" << endl;
165        Debug << "max leaves: " << mTermMaxLeaves << endl;
166        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
167        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
168        Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
169        Debug << "repair queue: " << mRepairQueue << endl;
170        Debug << "number of multilevels: " << mNumMultiLevels << endl;
171        Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
172        Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
173        Debug << "maximal allowed memory: " << mTermMaxMemory << endl;
174        Debug << "consider memory: " << mConsiderMemory << endl;
175        Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
176        Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
177        Debug << "max repairs: " << mMaxRepairs << endl;
178        Debug << "max avg ray contribution: " << mMaxAvgRayContri << endl;
179
180
181        switch (mConstructionType)
182        {
183        case 0:
184                Debug << "construction type: sequential" << endl;
185                break;
186        case 1:
187                Debug << "construction type: interleaved" << endl;
188                break;
189        case 2:
190                Debug << "construction type: gradient" << endl;
191                break;
192        case 3:
193                Debug << "construction type: multilevel" << endl;
194                break;
195        default:
196                Debug << "construction type " << mConstructionType << " unknown" << endl;
197                break;
198        }
199
200        //Debug << "min render cost " << mMinRenderCostDecrease << endl;
201        Debug << endl;
202}
203
204
205HierarchyManager::~HierarchyManager()
206{
207        DEL_PTR(mOspTree);
208        DEL_PTR(mVspTree);
209        DEL_PTR(mBvHierarchy);
210}
211
212
213int HierarchyManager::GetObjectSpaceSubdivisionType() const
214{
215        return mObjectSpaceSubdivisionType;
216}
217
218
219int HierarchyManager::GetViewSpaceSubdivisionType() const
220{
221        return mViewSpaceSubdivisionType;
222}
223
224
225void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
226{
227        mVspTree->SetViewCellsManager(vcm);
228
229        if (mOspTree)
230        {
231                mOspTree->SetViewCellsManager(vcm);
232        }
233        else if (mBvHierarchy)
234        {
235                mBvHierarchy->SetViewCellsManager(vcm);
236        }
237}
238
239
240void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
241{
242        mVspTree->SetViewCellsTree(vcTree);
243}
244
245
246VspTree *HierarchyManager::GetVspTree()
247{
248        return mVspTree;
249}
250
251/*
252AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
253{
254        return mVspTree->mBoundingBox;
255}*/
256
257
258AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
259{
260        switch (mObjectSpaceSubdivisionType)
261        {
262        case KD_BASED_OBJ_SUBDIV:
263                return mOspTree->mBoundingBox;
264        case BV_BASED_OBJ_SUBDIV:
265                return mBvHierarchy->mBoundingBox;
266        default:
267                // hack: empty box
268                return AxisAlignedBox3();
269        }
270}
271
272
273SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue)
274{
275        SubdivisionCandidate *splitCandidate = splitQueue.Top();
276        splitQueue.Pop();
277
278        // split was not reevaluated before => do it now
279        if (splitCandidate->IsDirty())
280                splitCandidate->EvalCandidate();
281
282        return splitCandidate;
283}
284
285
286float HierarchyManager::EvalFullMem() const
287{
288        // question: should I also add the mem usage of the hierarchies?
289        const float objectSpaceMem = 16;//GetObjectSpaceMemUsage();
290        const float viewSpaceMem = 16;//mVspTree->GetMemUsage();
291        // HACK: the same value is used for view and object space
292        return mHierarchyStats.mMemory + mHierarchyStats.Leaves() * objectSpaceMem;
293}
294
295
296void HierarchyManager::EvalSubdivisionStats()
297{
298       
299        HierarchySubdivisionStats stats;
300
301        stats.mNumSplits = mHierarchyStats.Leaves();
302        stats.mTotalRenderCost = mHierarchyStats.mTotalCost;
303        stats.mEntriesInPvs = mHierarchyStats.mPvsEntries;
304        stats.mMemoryCost = mHierarchyStats.mMemory  / float(1024 * 1024);
305        stats.mFullMemory = EvalFullMem() / float(1024 * 1024);
306        stats.mViewSpaceSplits = mVspTree->mVspStats.Leaves();
307        stats.mObjectSpaceSplits = GetObjectSpaceSubdivisionLeaves();
308        stats.mRenderCostDecrease = mHierarchyStats.mRenderCostDecrease;
309        stats.mPriority = mPriority;
310
311        stats.Print(mSubdivisionStats);
312}
313
314
315void HierarchyManager::AddSubdivisionStats(const int splits,
316                                                                                   const float renderCostDecr,
317                                                                                   const float totalRenderCost,
318                                                                                   const int pvsEntries,
319                                                                                   const float memory,
320                                                                                   const float renderCostPerStorage,
321                                                                                   const float vspOspRatio)
322{
323        mSubdivisionStats
324                        << "#Splits\n" << splits << endl
325                        << "#RenderCostDecrease\n" << renderCostDecr << endl
326                        << "#TotalEntriesInPvs\n" << pvsEntries << endl
327                        << "#TotalRenderCost\n" << totalRenderCost << endl
328                        << "#Memory\n" << memory << endl
329                        << "#FpsPerMb\n" << renderCostPerStorage << endl
330                        << "#VspOspRatio\n" << vspOspRatio << endl
331                        << endl;
332}
333
334
335bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
336{
337        const bool terminationCriteriaMet =
338                (0
339                || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
340                //|| (mHierarchyStats.mMemory >= mTermMaxMemory)
341                || (EvalFullMem() >= mTermMaxMemory)
342                || candidate->GlobalTerminationCriteriaMet()
343                //|| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
344                //|| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
345                );
346
347#if GTP_DEBUG
348        if (terminationCriteriaMet)
349        {
350                Debug << "hierarchy global termination criteria met:" << endl;
351                Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
352                Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
353                Debug << "memory: " << mHierarchyStats.mMemory << " " << mTermMaxMemory << endl;
354                Debug << "full memory: " << EvalFullMem() << " " << mTermMaxMemory << endl;
355        }
356#endif
357
358        return terminationCriteriaMet;
359}
360
361
362void HierarchyManager::Construct(const VssRayContainer &sampleRays,
363                                                                 const ObjectContainer &objects,
364                                                                 AxisAlignedBox3 *forcedViewSpace)
365{
366        mTimeStamp = 1;
367
368        switch (mConstructionType)
369        {
370        case MULTILEVEL:
371                ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
372                break;
373        case INTERLEAVED:
374        case SEQUENTIAL:
375                ConstructInterleaved(sampleRays, objects, forcedViewSpace);
376                break;
377        case GRADIENT:
378                ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
379                break;
380        default:
381                break;
382        }
383
384        // hack: should be different parameter name
385        if (mUseMultiLevelConstruction)
386        {
387                cout << "starting optimizing multilevel ... " << endl;
388                // try to optimize on the above hierarchy
389                OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
390               
391                cout << "finished" << endl;
392        }
393}
394
395
396void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
397                                                                                                                const ObjectContainer &objects,
398                                                                                                                AxisAlignedBox3 *forcedViewSpace)
399{
400        mHierarchyStats.Reset();
401        mHierarchyStats.Start();
402       
403        mHierarchyStats.mNodes = 2;
404
405        // create first nodes
406        mVspTree->Initialise(sampleRays, forcedViewSpace);
407        InitialiseObjectSpaceSubdivision(objects);
408
409        // hack: assume that object space can be seen from view space
410        mHierarchyStats.mTotalCost = mInitialRenderCost = (float)objects.size();
411        // only one entry for start
412        mHierarchyStats.mPvsEntries = 1;
413        mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
414
415        EvalSubdivisionStats();
416        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
417
418        const long startTime = GetTime();
419        cout << "Constructing view space / object space tree ... \n";
420       
421        SplitQueue objectSpaceQueue;
422        SplitQueue viewSpaceQueue;
423
424        int vspSteps = 0, ospSteps = 0;
425
426        // use sah for evaluating osp tree construction
427        // in the first iteration of the subdivision
428        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
429        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
430        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
431
432        // number of initial splits
433        const int minSteps = mMinStepsOfSameType;
434        const int maxSteps = mMaxStepsOfSameType;
435
436        PrepareObjectSpaceSubdivision(objectSpaceQueue, sampleRays, objects);
437       
438        /////////////////////////
439        // calulcate initial object space splits
440       
441        SubdivisionCandidateContainer dirtyList;
442
443        // subdivide object space first
444        // for first round, use sah splits. Once view space partition
445        // has started, use render cost heuristics instead
446        ospSteps = RunConstruction(objectSpaceQueue,
447                                                           dirtyList,
448                                                           NULL,
449                                                           minSteps,
450                                                           maxSteps);
451
452        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
453
454        // create view space
455        PrepareViewSpaceSubdivision(viewSpaceQueue, sampleRays, objects);
456
457        dirtyList.clear();
458
459        // view space subdivision started
460        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
461
462        if (1)
463        {
464                // rather also start with 100 view space splits to avoid initial bias.
465                vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
466                cout << "\n" << vspSteps << " view space partition steps taken" << endl;
467               
468                /// Repair split queue
469                cout << "repairing queue ... " << endl;
470                RepairQueue(dirtyList, objectSpaceQueue, true);
471                cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;
472
473                dirtyList.clear();
474        }
475        else
476        {
477                // the priorities were calculated for driving sah.
478                // => recalculate "real" priorities taking visibility into
479                // account so we can compare to view space splits
480                ResetQueue(objectSpaceQueue, false);
481        }
482
483        // This method subdivides view space / object space
484        // in order to converge to some optimal cost for this partition
485        // start with object space partiton
486        // then optimizate view space partition for the current osp
487        // and vice versa until iteration depth is reached.
488
489        bool lastSplitWasOsp = true;
490
491        while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
492        {
493                // decide upon next split type
494                const float vspPriority =
495                        viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
496                const float ospPriority =
497                        objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
498               
499                cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;
500
501                // should view or object space be subdivided further?
502                if (ospPriority >= vspPriority)
503                //if (!lastSplitWasOsp)
504                {
505                        lastSplitWasOsp = true;
506                        cout << "osp" << endl;
507                       
508                        // dirtied view space candidates
509                        SubdivisionCandidateContainer dirtyVspList;
510
511                        // subdivide object space first for first round,
512                        // use sah splits. Once view space partition
513                        // has started, use render cost heuristics instead
514                        const int ospSteps = RunConstruction(objectSpaceQueue,
515                                                                                                 dirtyVspList,
516                                                                                                 viewSpaceQueue.Top(),
517                                                                                                 minSteps,
518                                                                                                 maxSteps);
519
520                        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
521                        Debug << "\n" << ospSteps << " object space partition steps taken" << endl;
522
523                        /// Repair split queue, i.e., affected view space candidates
524                        cout << "repairing queue ... " << endl;
525                        const int repaired = RepairQueue(dirtyVspList, viewSpaceQueue, true);
526           
527                        cout << "\nrepaired " << repaired << " candidates from "
528                                 << (int)dirtyVspList.size() << " dirtied candidates" << endl;
529                }
530                else
531                {
532                        lastSplitWasOsp = false;
533                        cout << "vsp" << endl;
534                       
535                        /////////////////
536                        // subdivide view space with respect to the objects
537
538                        // dirtied object space candidates
539                        SubdivisionCandidateContainer dirtyOspList;
540
541                        // process view space candidates
542                        const int vspSteps = RunConstruction(viewSpaceQueue,
543                                                                                                 dirtyOspList,
544                                                                                                 objectSpaceQueue.Top(),
545                                                                                                 minSteps,
546                                                                                                 maxSteps);
547
548                        cout << "\n" << vspSteps << " view space partition steps taken" << endl;
549                        Debug << "\n" << vspSteps << " view space partition steps taken" << endl;
550
551                        // view space subdivision constructed
552                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
553
554                        /// Repair split queue
555                        cout << "repairing queue ... " << endl;
556                        const int repaired = RepairQueue(dirtyOspList, objectSpaceQueue, true);
557
558                        cout << "\nrepaired " << repaired << " candidates from "
559                                 << (int)dirtyOspList.size() << " dirtied candidates" << endl;
560                }
561        }
562
563        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
564
565        mHierarchyStats.Stop();
566        mVspTree->mVspStats.Stop();
567
568        FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
569}
570
571
572void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
573                                                                                        const ObjectContainer &objects,
574                                                                                        AxisAlignedBox3 *forcedViewSpace)
575{
576        mHierarchyStats.Reset();
577        mHierarchyStats.Start();
578
579        // two nodes for view space and object space
580        mHierarchyStats.mNodes = 2;
581        mHierarchyStats.mPvsEntries = 1;
582        mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
583        mHierarchyStats.mTotalCost = (float)objects.size();
584
585        mHierarchyStats.mRenderCostDecrease = 0;
586
587        EvalSubdivisionStats();
588        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
589
590        const long startTime = GetTime();
591        cout << "Constructing view space / object space tree ... \n";
592       
593        // create only roots
594        mVspTree->Initialise(sampleRays, forcedViewSpace);
595        InitialiseObjectSpaceSubdivision(objects);
596
597        // use objects for evaluating vsp tree construction in the
598        // first levels of the subdivision
599        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
600        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
601
602        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
603        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
604
605        // start view space subdivison immediately?
606        if (StartViewSpaceSubdivision())
607        {
608                // prepare vsp tree for traversal
609        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
610                PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
611        }
612       
613        // start object space subdivision immediately?
614        if (StartObjectSpaceSubdivision())
615        {
616                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
617                PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
618        }
619       
620        // begin subdivision
621        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
622       
623        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
624
625        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
626        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
627
628        mHierarchyStats.Stop();
629        mVspTree->mVspStats.Stop();
630       
631        FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
632}
633
634
635void HierarchyManager::PrepareViewSpaceSubdivision(SplitQueue &tQueue,
636                                                                                                   const VssRayContainer &sampleRays,
637                                                                                                   const ObjectContainer &objects)
638{
639        cout << "\npreparing view space hierarchy construction ... " << endl;
640
641        // hack: reset global cost misses
642        mHierarchyStats.mGlobalCostMisses = 0;
643
644        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
645        mVspTree->PrepareConstruction(tQueue, sampleRays, *viewSpaceRays);
646
647        /////////
648        //-- new stats
649
650        mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
651        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
652}
653
654
655float HierarchyManager::GetObjectSpaceMemUsage() const
656{
657        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
658        {
659                // TODO;
660        }
661        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
662        {
663                return mBvHierarchy->GetMemUsage();
664        }
665
666        return -1;
667}
668
669
670void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
671{
672        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
673        {
674                // TODO;
675        }
676        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
677        {
678                mBvHierarchy->Initialise(objects);
679        }
680}
681
682
683void HierarchyManager::PrepareObjectSpaceSubdivision(SplitQueue &tQueue,
684                                                                                                         const VssRayContainer &sampleRays,
685                                                                                                         const ObjectContainer &objects)
686{
687        // hack: reset global cost misses
688        mHierarchyStats.mGlobalCostMisses = 0;
689
690        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
691        {
692                return PrepareOspTree(tQueue, sampleRays, objects);
693        }
694        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
695        {
696                return PrepareBvHierarchy(tQueue, sampleRays, objects);
697        }
698}
699
700
701void HierarchyManager::PrepareBvHierarchy(SplitQueue &tQueue,
702                                                                                  const VssRayContainer &sampleRays,
703                                                                                  const ObjectContainer &objects)
704{
705        const long startTime = GetTime();
706
707        cout << "preparing bv hierarchy construction ... " << endl;
708       
709        // compute first candidate
710        mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
711
712        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
713        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
714
715        cout << "finished bv hierarchy preparation in "
716                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
717}
718
719
720void HierarchyManager::PrepareOspTree(SplitQueue &tQueue,
721                                                                          const VssRayContainer &sampleRays,
722                                                                          const ObjectContainer &objects)
723{
724        cout << "starting osp tree construction ... " << endl;
725
726        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
727
728        // start with one big kd cell - all objects can be seen from everywhere
729        // note: only true for view space = object space
730
731        // compute first candidate
732        mOspTree->PrepareConstruction(tQueue, sampleRays, objects, *objectSpaceRays);
733
734        mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
735        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
736}
737
738
739float HierarchyManager::EvalCorrectedPvs(const float childPvs,
740                                                                                 const float totalPvs,
741                                                                                 const float avgRayContri) const
742{
743        // assume pvs sampled sufficiently => take child pvs
744        if (avgRayContri < mMinAvgRayContri)
745        {
746                return childPvs;
747        }
748        // assume pvs not sampled sufficiently => take total pvs
749        if (avgRayContri >= mMaxAvgRayContri)
750        {
751                return totalPvs;
752        }
753
754        const float alpha = (mMaxAvgRayContri - avgRayContri) /
755                                                (mMaxAvgRayContri - mMinAvgRayContri);
756
757        const float beta = (1.0f - alpha) * (totalPvs - childPvs);
758#if 1
759        const float newPvs = childPvs + beta;
760#else
761        const float newPvs = alpha * childPvs + (1.0f - alpha) * totalPvs;
762#endif
763
764        //cout << "alpha " << alpha << " beta: " << beta << " child: " << childPvs << " parent: " << totalPvs << endl;
765       
766        if ((newPvs < childPvs - Limits::Small) || (newPvs > totalPvs + Limits::Small))
767                cout << "Error!! " << newPvs << endl;
768        return newPvs;
769}
770
771
772bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
773                                                                                                 SplitQueue &splitQueue,
774                                                                                                 const bool repairQueue)
775{
776        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
777        const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
778
779        if (sc->IsDirty())
780                cerr << "Error: Should never come here!" << endl;
781
782        if (!success) // split was not taken
783        {
784                cout << "x";
785                return false;
786        }
787
788        //cout << "priority: " << sc->GetPriority() << " rc decr: " << sc->GetRenderCostDecrease() << " | ";
789        ///////////////
790        //-- split was successful => update stats and queue
791
792    // cost ratio of cost decrease / totalCost
793        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
794        //cout << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
795       
796        if (costRatio < mTermMinGlobalCostRatio)
797        {
798                ++ mHierarchyStats.mGlobalCostMisses;
799        }
800       
801        cout << sc->Type() << " ";
802               
803        /////////////
804        // update stats
805
806        mHierarchyStats.mNodes += 2;
807        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
808
809        const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
810        mHierarchyStats.mPvsEntries += pvsEntriesIncr;
811        //cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;
812
813        // memory size in byte
814        float mem = (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
815
816        // high avg ray contri, the result is influenced by undersampling
817        // => decrease priority
818        if (0 && USE_AVGRAYCONTRI && (sc->GetAvgRayContribution() > mMaxAvgRayContri))
819        {
820                const float factor = 1.0f + sc->GetAvgRayContribution() - mMaxAvgRayContri;
821                cout << "h " << factor << endl;
822
823                mem *= factor;
824        }
825       
826        mHierarchyStats.mMemory += mem;
827        mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
828       
829        mPriority = sc->GetPriority();
830
831        //////////
832        // show current memory
833
834        static float memoryCount = 0;
835
836        if (mHierarchyStats.mMemory > memoryCount)
837        {
838                memoryCount += 100000;
839                cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
840                         << " MB, steps: " << mHierarchyStats.Leaves() << endl;
841        }
842
843        // output stats
844        EvalSubdivisionStats();
845               
846        if (repairQueue)
847        {
848                // reevaluate candidates affected by the split for view space splits,
849                // this would be object space splits and other way round
850                vector<SubdivisionCandidate *> dirtyList;
851                sc->CollectDirtyCandidates(dirtyList, false);
852
853                RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
854        }
855
856        return true;
857}
858
859
860int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
861{
862        int maxDepth = 0;
863
864        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
865        {
866                maxDepth = mOspTree->mOspStats.maxDepth;
867        }
868        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
869        {
870                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
871        }
872
873        return maxDepth;
874}
875
876
877int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
878{
879        int maxLeaves= 0;
880
881        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
882        {
883                maxLeaves = mOspTree->mOspStats.Leaves();
884        }
885        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
886        {
887                maxLeaves = mBvHierarchy->mBvhStats.Leaves();
888        }
889
890        return maxLeaves;
891}
892
893
894int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
895{
896        int maxLeaves = 0;
897
898        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
899        {
900                maxLeaves = mOspTree->mOspStats.nodes;
901        }
902        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
903        {
904                maxLeaves = mBvHierarchy->mBvhStats.nodes;
905        }
906
907        return maxLeaves;
908}
909
910bool HierarchyManager::StartObjectSpaceSubdivision() const
911{
912        // view space construction already started
913        if (ObjectSpaceSubdivisionConstructed())
914                return false;
915
916        // start immediately with object space subdivision?
917        if (mStartWithObjectSpace)
918                return true;
919
920        // is the queue empty again?
921        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
922                return true;
923
924        // has the depth for subdivision been reached?
925        return
926                ((mConstructionType == INTERLEAVED) &&
927                 (mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
928}
929
930
931bool HierarchyManager::StartViewSpaceSubdivision() const
932{
933        // view space construction already started
934        if (ViewSpaceSubdivisionConstructed())
935                return false;
936
937        // start immediately with view space subdivision?
938        if (!mStartWithObjectSpace)
939                return true;
940
941        // is the queue empty again?
942        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
943                return true;
944
945        // has the depth for subdivision been reached?
946        return
947                ((mConstructionType == INTERLEAVED) &&
948                 (mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
949}
950
951
952void HierarchyManager::RunConstruction(const bool repairQueue,
953                                                                           const VssRayContainer &sampleRays,
954                                                                           const ObjectContainer &objects,
955                                                                           AxisAlignedBox3 *forcedViewSpace)
956{
957        while (!FinishedConstruction())
958        {
959                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
960       
961                ///////////////////
962                //-- subdivide leaf node
963
964                ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
965                               
966                // we use objects for evaluating vsp tree construction until
967                // a certain depth once a certain depth existiert ...
968                if (StartObjectSpaceSubdivision())
969                {
970                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
971
972                        cout << "\nstarting object space subdivision after "
973                                 << mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") steps, mem="
974                                 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
975
976                        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
977                       
978                        cout << "reseting queue ... ";
979                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
980                        cout << "finished" << endl;
981                }
982
983                if (StartViewSpaceSubdivision())
984                {
985                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
986
987                        cout << "\nstarting view space subdivision at "
988                                 << GetObjectSpaceSubdivisionLeaves() << " ("
989                                 << mMinStepsOfSameType << ") , mem="
990                                 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
991
992                        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
993
994                        cout << "reseting queue ... ";
995                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
996                        cout << "finished" << endl;
997                }
998
999                DEL_PTR(sc);
1000        }
1001}
1002
1003
1004void HierarchyManager::RunConstruction(const bool repairQueue)
1005{
1006        // main loop
1007        while (!FinishedConstruction())
1008        {
1009                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
1010               
1011                ////////
1012                //-- subdivide leaf node of either type
1013
1014        ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
1015               
1016                DEL_PTR(sc);
1017        }
1018}
1019
1020
1021int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
1022                                                                          SubdivisionCandidateContainer &dirtyCandidates,
1023                                                                          SubdivisionCandidate *oldCandidate,
1024                                                                          const int minSteps,
1025                                                                          const int maxSteps)
1026{
1027        if (minSteps >= maxSteps)
1028                cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
1029
1030        int steps = 0;
1031        SubdivisionCandidate::NewMail();
1032
1033        // main loop
1034        while (!splitQueue.Empty())
1035        {
1036                const float priority = splitQueue.Top()->GetPriority();
1037                const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
1038
1039                // minimum slope reached
1040                if ((steps >= maxSteps) || ((priority < threshold) && !(steps < minSteps)))
1041                {
1042                        cout << "\nbreaking on " << priority << " smaller than " << threshold << endl;
1043                        break;
1044                }
1045               
1046                ////////
1047                //-- subdivide leaf node of either type
1048
1049                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
1050                       
1051                const bool repairQueue = false;
1052                const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
1053
1054                if (success)
1055                {
1056                        sc->CollectDirtyCandidates(dirtyCandidates, true);
1057                        ++ steps;
1058                }
1059
1060                DEL_PTR(sc);
1061        }
1062
1063        return steps;
1064}
1065
1066
1067void HierarchyManager::ResetObjectSpaceSubdivision(SplitQueue &tQueue,
1068                                                                                                   const VssRayContainer &sampleRays,
1069                                                                                                   const ObjectContainer &objects)
1070{       
1071        // object space partition constructed => reconstruct
1072        switch (mObjectSpaceSubdivisionType)
1073        {
1074        case BV_BASED_OBJ_SUBDIV:
1075                {
1076                        cout << "\nreseting bv hierarchy" << endl;
1077                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
1078                               
1079                        // rather use this: remove previous nodes and add the two new ones
1080                        //mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
1081                        mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
1082                       
1083                        // create root
1084                        mBvHierarchy->Initialise(objects);
1085       
1086                        mBvHierarchy->Reset(tQueue, sampleRays, objects);
1087
1088                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
1089                       
1090                        //mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
1091                        mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
1092
1093                        mHierarchyStats.mMemory =
1094                                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1095
1096                        mHierarchyStats.mRenderCostDecrease = 0;
1097
1098                        // evaluate stats before first subdivision
1099                        EvalSubdivisionStats();
1100                        cout << "finished bv hierarchy preparation" << endl;
1101                }
1102                break;
1103
1104        case KD_BASED_OBJ_SUBDIV:
1105                // TODO
1106        default:
1107                break;
1108        }
1109}
1110
1111
1112void HierarchyManager::ResetViewSpaceSubdivision(SplitQueue &tQueue,
1113                                                                                                 const VssRayContainer &sampleRays,
1114                                                                                                 const ObjectContainer &objects,
1115                                                                                                 AxisAlignedBox3 *forcedViewSpace)
1116{
1117        ViewCellsManager *vm = mVspTree->mViewCellsManager;
1118
1119        // HACK: rather not destroy vsp tree
1120        DEL_PTR(mVspTree);
1121        mVspTree = new VspTree();
1122
1123        mVspTree->mHierarchyManager = this;
1124        mVspTree->mViewCellsManager = vm;
1125
1126        mVspTree->Initialise(sampleRays, forcedViewSpace);
1127       
1128        //////////
1129        //-- reset stats
1130    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();
1131                //-mVspTree->mVspStats.nodes + 1;
1132       
1133        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
1134       
1135        mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
1136        mHierarchyStats.mRenderCostDecrease = 0;
1137
1138        mHierarchyStats.mMemory =
1139                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1140
1141        // evaluate new stats before first subdivsiion
1142        EvalSubdivisionStats();
1143}
1144
1145
1146void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
1147                                                                                   const ObjectContainer &objects,
1148                                                                                   AxisAlignedBox3 *forcedViewSpace)
1149{
1150        mHierarchyStats.Reset();
1151        mHierarchyStats.Start();
1152        mHierarchyStats.mNodes = 2;
1153       
1154        mHierarchyStats.mTotalCost = (float)objects.size();
1155        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
1156
1157        const long startTime = GetTime();
1158        cout << "Constructing view space / object space tree ... \n";
1159       
1160        // initialise view / object space
1161        mVspTree->Initialise(sampleRays, forcedViewSpace);
1162        InitialiseObjectSpaceSubdivision(objects);
1163
1164        // use sah for evaluating osp tree construction
1165        // in the first iteration of the subdivision
1166
1167        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
1168        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
1169
1170        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1171
1172        //////////////////////////
1173
1174
1175        const int limit = mNumMultiLevels;
1176        int i = 0;
1177
1178        // This method subdivides view space / object space
1179        // in order to converge to some optimal cost for this partition
1180        // start with object space partiton
1181        // then optimizate view space partition for the current osp
1182        // and vice versa until iteration depth is reached.
1183        while (1)
1184        {
1185                char subdivisionStatsLog[100];
1186                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1187                mSubdivisionStats.open(subdivisionStatsLog);
1188
1189                // subdivide object space first
1190                ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1191
1192                // process object space candidates
1193                RunConstruction(false);
1194
1195                // object space subdivision constructed
1196                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1197
1198                cout << "iteration " << i << " of " << limit << " finished" << endl;
1199                mSubdivisionStats.close();
1200
1201                if ((i ++) >= limit)
1202                        break;
1203
1204                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1205                mSubdivisionStats.open(subdivisionStatsLog);
1206
1207
1208                /////////////////
1209                // subdivide view space with respect to the objects
1210
1211                ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
1212               
1213                // view space subdivision constructed
1214                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
1215               
1216                // process view space candidates
1217                RunConstruction(false);
1218
1219                cout << "iteration " << i << " of " << limit << " finished" << endl;
1220                mSubdivisionStats.close();
1221
1222                if ((i ++) >= limit)
1223                        break;
1224        }
1225       
1226        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1227
1228        mHierarchyStats.Stop();
1229        mVspTree->mVspStats.Stop();
1230        FinishObjectSpaceSubdivision(objects);
1231}
1232
1233
1234void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                     
1235                                                                                  const ObjectContainer &objects,
1236                                                                                  AxisAlignedBox3 *forcedViewSpace)
1237{
1238        const long startTime = GetTime();
1239        const int limit = mNumMultiLevels;
1240
1241        // open up new subdivision
1242        mSubdivisionStats.close();
1243
1244        int steps = 0;
1245
1246        int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
1247        int maxObjectSpaceLeaves;
1248       
1249        // set the number of leaves 'evaluated' from the previous methods
1250        // we go for the same numbers, but we try to optimize both subdivisions
1251        switch (mObjectSpaceSubdivisionType)
1252        {
1253        case BV_BASED_OBJ_SUBDIV:
1254                maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
1255                break;
1256        case KD_BASED_OBJ_SUBDIV:
1257                maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
1258        default:
1259                maxObjectSpaceLeaves = 0;
1260                break;
1261        }
1262
1263        // This method subdivides view space / object space
1264        // in order to converge to some optimal cost for this partition
1265        // start with object space partiton
1266        // then optimizate view space partition for the current osp
1267        // and vice versa until iteration depth is reached.
1268        while (1)
1269        {
1270                char subdivisionStatsLog[100];
1271                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1272                mSubdivisionStats.open(subdivisionStatsLog);
1273
1274                // subdivide object space first
1275                ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1276       
1277                // set the number of leaves 'evaluated' from the previous methods
1278                // we go for the same numbers, but we try to optimize both subdivisions
1279                mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
1280
1281                // process object space candidates
1282                RunConstruction(false);
1283
1284                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1285                mSubdivisionStats.close();
1286
1287                if ((++ steps) >= limit)
1288                        break;
1289
1290                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1291                mSubdivisionStats.open(subdivisionStatsLog);
1292
1293                /////////////////
1294                // subdivide view space with respect to the objects
1295
1296                ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
1297
1298                mVspTree->mMaxViewCells = maxViewSpaceLeaves;
1299
1300                // process view space candidates
1301                RunConstruction(false);
1302
1303                cout << "iteration " << steps << " of " << limit << " finished" << endl;
1304                mSubdivisionStats.close();
1305
1306                if ((++ steps) >= limit)
1307                        break;
1308        }
1309       
1310        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1311
1312        mHierarchyStats.Stop();
1313        mVspTree->mVspStats.Stop();
1314        FinishObjectSpaceSubdivision(objects);
1315}
1316
1317
1318
1319bool HierarchyManager::FinishedConstruction() const
1320{
1321        return mTQueue.Empty();
1322}
1323
1324
1325bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
1326{
1327        /*switch (mObjectSpaceSubdivisionType)
1328        {
1329        case KD_BASED_OBJ_SUBDIV:
1330                return mOspTree && mOspTree->GetRoot();
1331        case BV_BASED_OBJ_SUBDIV:
1332                return mBvHierarchy && mBvHierarchy->GetRoot();
1333        default:
1334                return false;
1335        }*/
1336        return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
1337}
1338
1339
1340bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
1341{
1342        return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
1343        //return mVspTree && mVspTree->GetRoot();
1344}
1345
1346
1347void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
1348                                                                                          SubdivisionCandidateContainer &dirtyList)
1349{
1350        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
1351        SubdivisionCandidate::NewMail();
1352
1353        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
1354        {
1355                (*sit)->CollectDirtyCandidates(dirtyList, true);
1356        }
1357}
1358
1359
1360int HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
1361                                                                  SplitQueue &splitQueue,
1362                                                                  const bool recomputeSplitPlaneOnRepair)
1363{
1364        // for each update of the view space partition:
1365        // the candidates from object space partition which
1366        // have been afected by the view space split (the kd split candidates
1367        // which saw the view cell which was split) must be reevaluated
1368        // (maybe not locally, just reinsert them into the queue)
1369        //
1370        // vice versa for the view cells
1371        // for each update of the object space partition
1372        // reevaluate split candidate for view cells which saw the split kd cell
1373        //
1374        // the priority queue update can be solved by implementing a binary heap
1375        // (explicit data structure, binary tree)
1376        // *) inserting and removal is efficient
1377        // *) search is not efficient => store queue position with each
1378        // split candidate
1379
1380        int repaired = 0;
1381
1382        // collect list of "dirty" candidates
1383        const long startTime = GetTime();
1384        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
1385
1386        const float prop = (float)mMaxRepairs / (float)dirtyList.size();
1387
1388        ///////////////////////////
1389        //-- reevaluate the dirty list
1390
1391        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
1392       
1393        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
1394        {
1395                // only repair a certain number of candidates
1396                if ((mMaxRepairs < (int)dirtyList.size()) && (Random(1.0f) >= prop))
1397                        continue;
1398
1399                SubdivisionCandidate* sc = *sit;
1400                const float rcd = sc->GetRenderCostDecrease();
1401               
1402                // erase from queue
1403                splitQueue.Erase(sc);
1404                // reevaluate candidate
1405                sc->EvalCandidate(recomputeSplitPlaneOnRepair);
1406                 // reinsert
1407                splitQueue.Push(sc);
1408               
1409                ++ repaired;
1410                cout << ".";
1411
1412#ifdef GTP_DEBUG
1413                Debug << "candidate " << sc << " reevaluated\n"
1414                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
1415                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
1416#endif 
1417        }
1418
1419        const long endTime = GetTime();
1420        const Real timeDiff = TimeDiff(startTime, endTime);
1421
1422        mHierarchyStats.mRepairTime += timeDiff;
1423
1424        return repaired;
1425}
1426
1427
1428void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
1429{
1430        SubdivisionCandidateContainer mCandidateBuffer;
1431
1432        // remove from queue
1433        while (!splitQueue.Empty())
1434        {
1435                SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
1436               
1437                // reevaluate local split plane and priority
1438                candidate->EvalCandidate(recomputeSplitPlane);
1439                cout << ".";
1440                mCandidateBuffer.push_back(candidate);
1441        }
1442
1443        // put back into queue
1444        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
1445    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
1446        {
1447                splitQueue.Push(*sit);
1448        }
1449}
1450
1451
1452void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
1453{
1454        // the type of the view cells hierarchy
1455        switch (mObjectSpaceSubdivisionType)
1456        {
1457        case KD_BASED_OBJ_SUBDIV:
1458                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
1459                mOspTree->Export(stream);
1460                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1461                break;         
1462        case BV_BASED_OBJ_SUBDIV:
1463                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
1464                mBvHierarchy->Export(stream);
1465                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1466                break;
1467        }
1468}
1469
1470
1471void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
1472{
1473        stream << mHierarchyStats << endl;
1474        stream << "\nview space:" << endl << endl;
1475        stream << mVspTree->GetStatistics() << endl;
1476        stream << "\nobject space:" << endl << endl;
1477
1478        switch (mObjectSpaceSubdivisionType)
1479        {
1480        case KD_BASED_OBJ_SUBDIV:
1481                {
1482                        stream << mOspTree->GetStatistics() << endl;
1483                        break;
1484                }
1485        case BV_BASED_OBJ_SUBDIV:
1486                {
1487                        stream << mBvHierarchy->GetStatistics() << endl;
1488                        break;
1489                }
1490        default:
1491                break;
1492        }
1493}
1494
1495
1496void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
1497                                                                                                  const ObjectContainer &objects,
1498                                                                                                  AxisAlignedBox3 *bbox,
1499                                                                                                  const float maxRenderCost,
1500                                                                                                  const bool exportBounds) const
1501{
1502        switch (mObjectSpaceSubdivisionType)
1503        {
1504        case KD_BASED_OBJ_SUBDIV:
1505                {
1506                        ExportOspTree(exporter, objects);
1507                        break;
1508                }
1509        case BV_BASED_OBJ_SUBDIV:
1510                {
1511                        exporter->ExportBvHierarchy(*mBvHierarchy, maxRenderCost, bbox, exportBounds);
1512                        break;
1513                }
1514        default:
1515                break;
1516        }
1517}
1518
1519
1520void HierarchyManager::ExportOspTree(Exporter *exporter,
1521                                                                         const ObjectContainer &objects) const
1522{
1523        if (0) exporter->ExportGeometry(objects);
1524                       
1525        exporter->SetWireframe();
1526        exporter->ExportOspTree(*mOspTree, 0);
1527}
1528
1529
1530Intersectable *HierarchyManager::GetIntersectable(Intersectable *obj,
1531                                                                                                  const Vector3 &point) const
1532{
1533
1534        if (!obj)
1535                return NULL;
1536
1537        switch (mObjectSpaceSubdivisionType)
1538        {
1539        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1540                {
1541                        KdLeaf *leaf = mOspTree->GetLeaf(point, NULL);
1542                        return mOspTree->GetOrCreateKdIntersectable(leaf);
1543                }
1544        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1545                {
1546                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1547                        return leaf;
1548                }
1549        default:
1550                return obj;
1551        }
1552}
1553
1554Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1555                                                                                                  const bool isTermination) const
1556{
1557        Intersectable *obj = NULL;
1558        Vector3 pt;
1559        KdNode *node;
1560
1561        ray.GetSampleData(isTermination, pt, &obj, &node);
1562
1563        if (!obj)
1564                return NULL;
1565
1566        switch (mObjectSpaceSubdivisionType)
1567        {
1568        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1569                {
1570                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1571                        return mOspTree->GetOrCreateKdIntersectable(leaf);
1572                }
1573        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1574                {
1575                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1576                        return leaf;
1577                }
1578        default:
1579                break;
1580        }
1581
1582        return obj;
1583}
1584
1585
1586void HierarchyStatistics::Print(ostream &app) const
1587{
1588        app << "=========== Hierarchy statistics ===============\n";
1589
1590        app << setprecision(4);
1591
1592        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1593       
1594        app << "#N_RTIME  ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1595
1596        app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1597
1598        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1599
1600        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1601
1602        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1603
1604        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1605       
1606        app << "========== END OF Hierarchy statistics ==========\n";
1607}
1608
1609
1610static void RemoveRayRefs(const ObjectContainer &objects)
1611{
1612        ObjectContainer::const_iterator oit, oit_end = objects.end();
1613        for (oit = objects.begin(); oit != oit_end; ++ oit)
1614        {
1615                (*oit)->DelRayRefs();
1616        }
1617}
1618
1619
1620void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1621                                                                                                        const bool removeRayRefs) const
1622{
1623        switch (mObjectSpaceSubdivisionType)
1624        {
1625        case KD_BASED_OBJ_SUBDIV:
1626                {
1627                        mOspTree->mOspStats.Stop();
1628                        break;
1629                }
1630        case BV_BASED_OBJ_SUBDIV:
1631                {
1632                        mBvHierarchy->mBvhStats.Stop();
1633                        if (removeRayRefs)
1634                                RemoveRayRefs(objects);
1635                        break;
1636                }
1637        default:
1638                break;
1639        }
1640}
1641
1642
1643void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1644{
1645        stream << "<BoundingBoxes>" << endl;
1646           
1647        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1648        {
1649                KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1650
1651                int id = 0;
1652                for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1653                {
1654                        Intersectable *obj = (*kit).second;
1655                        const AxisAlignedBox3 box = obj->GetBox();
1656               
1657                        obj->SetId(id);
1658
1659                        stream << "<BoundingBox" << " id=\"" << id << "\""
1660                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1661                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1662                }
1663        }
1664        else
1665        {
1666                ObjectContainer::const_iterator oit, oit_end = objects.end();
1667
1668                for (oit = objects.begin(); oit != oit_end; ++ oit)
1669                {
1670                        const AxisAlignedBox3 box = (*oit)->GetBox();
1671               
1672                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1673                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1674                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1675                }
1676        }
1677               
1678        stream << "</BoundingBoxes>" << endl;
1679}
1680
1681
1682class HierarchyNodeWrapper;
1683
1684
1685template <typename T> class myless
1686{
1687public:
1688        bool operator() (T v1, T v2) const
1689        {
1690                return (v1->GetMergeCost() < v2->GetMergeCost());
1691        }
1692};
1693
1694
1695typedef priority_queue<HierarchyNodeWrapper *, vector<HierarchyNodeWrapper *>,
1696                                           myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
1697
1698class HierarchyNodeWrapper
1699{
1700public:
1701        enum {VSP_NODE, BVH_NODE, VIEW_CELL};
1702
1703        virtual float GetMergeCost() const = 0;
1704        virtual int Type() const  = 0;
1705        virtual bool IsLeaf() const = 0;
1706
1707        virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
1708};
1709
1710
1711class VspNodeWrapper: public HierarchyNodeWrapper
1712{
1713public:
1714        VspNodeWrapper(VspNode *node): mNode(node) {}
1715
1716        int Type() const { return VSP_NODE; }
1717
1718        float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
1719
1720        bool IsLeaf() const { return mNode->IsLeaf(); }
1721
1722        void PushChildren(HierarchyNodeQueue &tQueue)
1723        {
1724                if (!mNode->IsLeaf())
1725                {
1726                        VspInterior *interior = dynamic_cast<VspInterior *>(mNode);
1727
1728                        tQueue.push(new VspNodeWrapper(interior->GetFront()));
1729                        tQueue.push(new VspNodeWrapper(interior->GetBack()));
1730                }
1731        }
1732
1733        VspNode *mNode;
1734};
1735
1736
1737class BvhNodeWrapper: public HierarchyNodeWrapper
1738{
1739public:
1740        BvhNodeWrapper(BvhNode *node): mNode(node) {}
1741       
1742        int Type()  const { return BVH_NODE; }
1743
1744        float GetMergeCost() const { return (float)-mNode->GetTimeStamp(); };
1745
1746        bool IsLeaf() const { return mNode->IsLeaf(); }
1747
1748        void PushChildren(HierarchyNodeQueue &tQueue)
1749        {
1750                if (!mNode->IsLeaf())
1751                {
1752                        BvhInterior *interior = dynamic_cast<BvhInterior *>(mNode);
1753
1754                        tQueue.push(new BvhNodeWrapper(interior->GetFront()));
1755                        tQueue.push(new BvhNodeWrapper(interior->GetBack()));
1756                }
1757        }
1758
1759        BvhNode *mNode;
1760};
1761
1762
1763class ViewCellWrapper: public HierarchyNodeWrapper
1764{
1765public:
1766
1767        ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
1768       
1769        int Type()  const { return VIEW_CELL; }
1770
1771        float GetMergeCost() const { return mViewCell->GetMergeCost(); };
1772
1773        bool IsLeaf() const { return mViewCell->IsLeaf(); }
1774
1775        void PushChildren(HierarchyNodeQueue &tQueue)
1776        {
1777                if (!mViewCell->IsLeaf())
1778                {
1779                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(mViewCell);
1780
1781                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1782
1783                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1784                        {
1785                                tQueue.push(new ViewCellWrapper(*it));
1786                        }
1787                }
1788        }
1789
1790        ViewCell *mViewCell;
1791};
1792
1793
1794void HierarchyManager::CollectBestSet(const int maxSplits,
1795                                                                          const float maxMemoryCost,
1796                                                                          ViewCellContainer &viewCells,
1797                                                                          vector<BvhNode *> &bvhNodes)
1798{
1799        HierarchyNodeQueue tqueue;
1800        //tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
1801        tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
1802        tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
1803       
1804        float memCost = 0;
1805
1806        while (!tqueue.empty())
1807        {
1808                HierarchyNodeWrapper *nodeWrapper = tqueue.top();
1809                tqueue.pop();
1810                //cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
1811                // save the view cells if it is a leaf or if enough view cells have already been traversed
1812                // because of the priority queue, this will be the optimal set of v
1813                if (nodeWrapper->IsLeaf() ||
1814                        ((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) ||
1815                        (memCost > maxMemoryCost)
1816                        )
1817                {
1818                        if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
1819                        {
1820                                //cout << "1";
1821                                ViewCellWrapper *viewCellWrapper = dynamic_cast<ViewCellWrapper *>(nodeWrapper);
1822                                viewCells.push_back(viewCellWrapper->mViewCell);
1823                        }
1824                        else
1825                        {
1826                                //cout << "0";
1827                                BvhNodeWrapper *bvhNodeWrapper = dynamic_cast<BvhNodeWrapper *>(nodeWrapper);
1828                                bvhNodes.push_back(bvhNodeWrapper->mNode);
1829                        }
1830                }
1831                else
1832                {       
1833                        nodeWrapper->PushChildren(tqueue);
1834                }
1835
1836                delete nodeWrapper;
1837        }
1838}
1839
1840
1841void HierarchyManager::ComputePvs(const ObjectPvs &pvs,
1842                                                                  float &rc,
1843                                                                  int &pvsEntries)
1844{
1845        BvhNode::NewMail();
1846
1847        ObjectPvsIterator pit = pvs.GetIterator();
1848
1849        while (pit.HasMoreEntries())
1850        {
1851                const ObjectPvsEntry &entry = pit.Next();
1852
1853                if (entry.mObject->Type() != Intersectable::BVH_INTERSECTABLE)
1854                        cout << "error " << entry.mObject->Type() << endl;
1855
1856                BvhNode *intersect = dynamic_cast<BvhNode *>(entry.mObject);
1857                BvhNode *activeNode;
1858
1859                // hack for choosing which node to account for
1860                if (intersect->IsLeaf())
1861                {
1862                        activeNode =
1863                                dynamic_cast<BvhLeaf *>(intersect)->GetActiveNode();
1864                }
1865                else
1866                {
1867                        activeNode = intersect;
1868                }
1869
1870                if (!activeNode->Mailed())
1871                {
1872                        activeNode->Mail();
1873
1874#if STUPID_METHOD
1875
1876                        ObjectContainer objects;
1877            activeNode->CollectObjects(objects);
1878                        rc += mBvHierarchy->EvalAbsCost(objects);
1879#else
1880                        rc += mBvHierarchy->GetRenderCostIncrementially(activeNode);
1881#endif
1882                        ++ pvsEntries;
1883                }
1884        }
1885}
1886
1887
1888void HierarchyManager::GetPvsEfficiently(ViewCell *viewCell, ObjectPvs &pvs) const
1889{
1890        ////////////////
1891        //-- pvs is not stored with the interiors => reconstruct
1892       
1893        // add pvs from leaves
1894        stack<ViewCell *> tstack;
1895        tstack.push(viewCell);
1896
1897        Intersectable::NewMail();
1898
1899        while (!tstack.empty())
1900        {
1901                ViewCell *vc = tstack.top();
1902                tstack.pop();
1903       
1904                // add newly found pvs to merged pvs: break here even for interior
1905                if (!vc->GetPvs().Empty())
1906                {
1907                        ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1908
1909                        while (pit.HasMoreEntries())
1910                        {               
1911                                const ObjectPvsEntry &entry = pit.Next();
1912
1913                                Intersectable *object = entry.mObject;
1914                                if (!object->Mailed())
1915                                {
1916                                        object->Mail();
1917                                        pvs.AddSampleDirty(object, 1.0f);
1918                                }
1919                        }
1920                }
1921                else if (!vc->IsLeaf()) // interior cells: go down to leaf level
1922                {
1923                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1924                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1925
1926                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1927                        {
1928                                tstack.push(*it);
1929                        }               
1930                }
1931        }
1932}
1933
1934
1935// TODO matt: implement this function for different storing methods
1936void HierarchyManager::GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const
1937{
1938        ////////////////
1939        //-- pvs is not stored with the interiors => reconstruct
1940       
1941        // add pvs from leaves
1942        stack<ViewCell *> tstack;
1943        tstack.push(vc);
1944
1945        while (!tstack.empty())
1946        {
1947                vc = tstack.top();
1948                tstack.pop();
1949       
1950                // add newly found pvs to merged pvs: break here even for interior
1951                if (!vc->GetPvs().Empty())
1952                {
1953                        //if (vc->IsLeaf()) cout << " l " << pvs.GetSize();
1954                        //else cout << " i " << pvs.GetSize();
1955                        pvs.MergeInPlace(vc->GetPvs());
1956                }
1957                else if (!vc->IsLeaf()) // interior cells: go down to leaf level
1958                {
1959                        //cout <<" t";
1960                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1961                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1962
1963                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1964                        {
1965                                tstack.push(*it);
1966                        }               
1967                }
1968                else cout <<"k";
1969        }
1970}
1971
1972
1973// TODO matt: implement this function for different storing methods
1974void HierarchyManager::PullUpPvsIncrementally(ViewCell *viewCell) const
1975{
1976        ////////////////
1977        //-- pvs is not stored with the interiors => reconstruct
1978       
1979        // early exit: pvs is already pulled up to this view cell
1980        if (!viewCell->GetPvs().Empty())
1981                return;
1982
1983        // add pvs from leaves
1984        stack<ViewCell *> tstack;
1985        tstack.push(viewCell);
1986
1987        ViewCell *vc = viewCell;
1988
1989        while (!tstack.empty())
1990        {
1991                vc = tstack.top();
1992                tstack.pop();
1993       
1994                // add newly found pvs to merged pvs: break here even for interior
1995                if (!vc->GetPvs().Empty())
1996                {
1997                        viewCell->GetPvs().MergeInPlace(vc->GetPvs());
1998                }
1999                else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2000                {
2001                        //cout <<" t";
2002                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2003                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2004
2005                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2006                        {
2007                                tstack.push(*it);
2008                        }               
2009                }
2010        }
2011}
2012
2013
2014
2015// TODO matt: implement this function for different storing methods
2016void HierarchyManager::GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const
2017{
2018        ////////////////
2019        //-- pvs is not stored with the interiors => reconstruct
2020        if (vc->IsLeaf() || !vc->GetPvs().Empty())
2021        {
2022                pvs = vc->GetPvs();
2023        }
2024        else
2025        {
2026                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2027#if 0
2028                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2029                const int childPvsSize = (int)interior->mChildren.size();
2030                vector<ObjectPvs> childPvs;
2031                childPvs.resize((int)interior->mChildren.size());
2032
2033                int i = 0;
2034                for (it = interior->mChildren.begin(); it != it_end; ++ it, ++ i)
2035                {
2036                        GetPvsRecursive(*it, childPvs[i]);
2037                        pvs.MergeInPlace(childPvs[i]);
2038                }
2039#else
2040
2041                ObjectPvs leftPvs, rightPvs;
2042
2043                GetPvsRecursive(interior->mChildren[0], leftPvs);
2044                GetPvsRecursive(interior->mChildren[1], rightPvs);
2045
2046                ObjectPvs::Merge(pvs, leftPvs, rightPvs);
2047#endif
2048        }
2049}
2050
2051
2052int HierarchyManager::ExtractStatistics(const int maxSplits,
2053                                                                                const float maxMemoryCost,
2054                                                                                float &renderCost,
2055                                                                                float &memory,
2056                                                                                int &pvsEntries,
2057                                                                                int &viewSpaceSplits,
2058                                                                                int &objectSpaceSplits,
2059                                                                                const bool useFilter,
2060                                                                                const bool useHisto,
2061                                                                                const int histoMem,
2062                                                                                const int pass,
2063                                                                                bool &histoUsed)
2064{
2065        ViewCellContainer viewCells;
2066        vector<BvhNode *> bvhNodes;
2067
2068        // collect best set of view cells for this #splits
2069    CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
2070        vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
2071       
2072        // set new nodes to be active
2073        for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
2074        {
2075                mBvHierarchy->SetActive(*bit);
2076        }
2077
2078        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2079
2080        pvsEntries = 0;
2081        renderCost = 0.0f;
2082
2083        ViewCell::NewMail();
2084
2085        //cout << "\nviewcells: " << viewCells.size() << endl;
2086        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2087        {
2088                ViewCell *vc = *vit;
2089                float rc = 0;
2090       
2091#if STUPID_METHOD       
2092                ObjectPvs pvs;
2093                GetPvsIncrementially(vc, pvs);
2094                vc->SetPvs(pvs);
2095               
2096#else
2097       
2098                ObjectPvs pvs;
2099                               
2100                if (vc->GetPvs().Empty())
2101                {
2102                        // warning: uses mailing, pvs not sorted!!
2103                        GetPvsEfficiently(vc, pvs);
2104                        //GetPvsRecursive(vc, pvs);
2105                        vc->SetPvs(pvs);
2106                        //cout << "q";
2107                }
2108                //else cout << "t";
2109#endif
2110
2111                vc->Mail();
2112
2113                if (useFilter)
2114                {
2115                        const long startT = GetTime();
2116                        ObjectPvs filteredPvs;
2117                        mVspTree->mViewCellsManager->ApplyFilter2(vc, false, 1.0f, filteredPvs);
2118                        const long endT = GetTime();
2119
2120                        //cout << "filter computed in " << TimeDiff(startT, endT) * 1e-3f << " secs" << endl;
2121                        ComputePvs(filteredPvs, rc, pvsEntries);
2122                }
2123                else
2124                {
2125                        ComputePvs(vc->GetPvs(), rc, pvsEntries);
2126                        vc->SetPvsCost(rc);
2127                }
2128
2129                rc *= vc->GetVolume();
2130                renderCost += rc;
2131        }
2132
2133        renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
2134        memory = pvsEntries * ObjectPvs::GetEntrySize();
2135
2136        viewSpaceSplits = (int)viewCells.size();
2137        objectSpaceSplits = (int)bvhNodes.size();
2138
2139        ////////////////////////
2140    //-- evaluate histogram for pvs size
2141
2142        if (useHisto && (memory <= (float)histoMem))
2143        {
2144                char str[100];
2145                char statsPrefix[100];
2146                //int histoStepSize;
2147
2148                Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
2149       
2150                cout << "computing pvs histogram for " << histoMem << " memory" << endl;
2151                Debug << "computing pvs histogram for " << histoMem << " memory" << endl;
2152               
2153                sprintf(str, "-%05d-%05d-histo-pvs.log", pass, histoMem);
2154                const string filename = string(statsPrefix) + string(str);
2155
2156                mVspTree->mViewCellsManager->EvalViewCellHistogramForPvsSize(filename, viewCells);
2157
2158                histoUsed = true;
2159        }
2160
2161        //cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
2162
2163        // delete old "base" view cells if they are not leaves
2164        ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2165
2166        for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2167        {
2168                if (!(*oit)->Mailed() && !(*oit)->IsLeaf())
2169                {
2170                        (*oit)->GetPvs().Clear();
2171                }
2172        }
2173
2174        // store current level
2175        mOldViewCells = viewCells;
2176
2177        return (int)(viewCells.size() + bvhNodes.size());
2178}
2179
2180
2181void HierarchyManager::ExportStats(ofstream &stats,
2182                                                                   SplitQueue &tQueue,
2183                                                                   const ObjectContainer &objects)
2184{
2185        HierarchySubdivisionStats subStats;
2186        subStats.Reset();
2187
2188        /////////////
2189        //-- initial situation
2190
2191        subStats.mNumSplits = 0;
2192        subStats.mTotalRenderCost = (float)objects.size();
2193        subStats.mEntriesInPvs = 1;
2194        subStats.mMemoryCost = (float)ObjectPvs::GetEntrySize();
2195        subStats.mFullMemory = subStats.mMemoryCost;
2196        subStats.mViewSpaceSplits = 0;
2197        subStats.mObjectSpaceSplits = 0;
2198        subStats.mRenderCostDecrease = 0;
2199        subStats.Print(stats);
2200
2201        cout << "exporting vsposp stats ... " << endl;
2202
2203        //-- go through tree in the order of render cost decrease
2204        //-- which is the same order as the view cells were merged
2205        //-- or the reverse order of subdivision for subdivision-only
2206        //-- view cell hierarchies.
2207
2208        while (!tQueue.Empty())
2209        {
2210                SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
2211                bool isLeaf;
2212                int timeStamp;
2213                //float rcDecr;
2214                //int entriesIncr;
2215
2216                if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2217                {
2218                        timeStamp = (int)-nextCandidate->GetPriority();
2219
2220                        VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
2221                        VspNode *oldNode = (VspNode *)nextCandidate->mEvaluationHack;
2222
2223                        isLeaf = newNode->IsLeaf();
2224                        //subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2225                        //entriesIncr = oldNode->mPvsEntriesIncr;
2226                }
2227                else
2228                {
2229                        timeStamp = (int)-nextCandidate->GetPriority();
2230
2231                        BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
2232                        BvhNode *oldNode = (BvhNode *)nextCandidate->mEvaluationHack;
2233
2234                        isLeaf = newNode->IsLeaf();
2235                        //subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2236                        //entriesIncr = oldNode->mPvsEntriesIncr;
2237                }               
2238
2239                if (!isLeaf)
2240                {
2241                        subStats.mTotalRenderCost -= subStats.mRenderCostDecrease;
2242                        //subStats.mEntriesInPvs += entriesIncr;
2243
2244                        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2245                        {
2246                                ++ subStats.mViewSpaceSplits;
2247                                cout << "v";
2248                                //cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2249                        }
2250                        else
2251                        {
2252                                ++ subStats.mObjectSpaceSplits;
2253                                cout << "o";
2254                                //"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2255                        }
2256
2257                        ++ subStats.mNumSplits;
2258
2259                        if ((subStats.mNumSplits % 500) == 499)
2260                                cout << subStats.mNumSplits << " steps taken" << endl;
2261
2262                        subStats.mMemoryCost = (float)subStats.mEntriesInPvs * (float)ObjectPvs::GetEntrySize();
2263                        subStats.mFullMemory = subStats.mMemoryCost;
2264
2265                        subStats.Print(stats);
2266
2267                }
2268
2269                DEL_PTR(nextCandidate);
2270        }
2271
2272        stats.close();
2273}
2274
2275
2276void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
2277                                                                                   const ObjectContainer &objects,
2278                                                                                   const string &filename)
2279{
2280#if 0
2281        VspTree *oldVspTree = mVspTree;
2282        ViewCellsManager *vm = mVspTree->mViewCellsManager;
2283        BvHierarchy *oldHierarchy = mBvHierarchy;
2284
2285        mBvHierarchy = new BvHierarchy();
2286        mBvHierarchy->mHierarchyManager = this;
2287        mBvHierarchy->mViewCellsManager = vm;
2288
2289        mVspTree = new VspTree();
2290        mVspTree->mHierarchyManager = this;
2291        mVspTree->mViewCellsManager = vm;
2292
2293        // create first nodes
2294        mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
2295        InitialiseObjectSpaceSubdivision(objects);
2296
2297        const long startTime = GetTime();
2298        cout << "Constructing evaluation hierarchies ... \n";
2299       
2300        ofstream stats;
2301        stats.open(filename.c_str());
2302        SplitQueue tQueue;
2303
2304        BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
2305        VspNode *oldVspRoot = oldVspTree->GetRoot();
2306
2307        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
2308       
2309        SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
2310        tQueue.Push(firstVsp);
2311
2312        mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
2313
2314    firstVsp->mEvaluationHack = oldVspRoot;
2315        firstBvh->mEvaluationHack = oldBvhRoot;
2316
2317        firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
2318        firstBvh->SetPriority((float)-oldBvhRoot->GetTimeStamp());
2319       
2320        ExportStats(stats, tQueue, objects);
2321
2322        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2323        RemoveRayRefs(objects);
2324
2325        // view cells needed only for evaluation
2326        ViewCellContainer viewCells;
2327        mVspTree->CollectViewCells(viewCells, false);
2328       
2329        // helper trees can be destroyed
2330        DEL_PTR(mVspTree);
2331        DEL_PTR(mBvHierarchy);
2332
2333        CLEAR_CONTAINER(viewCells);
2334
2335        // reset hierarchies
2336        mVspTree = oldVspTree;
2337        mBvHierarchy = oldHierarchy;
2338
2339        // reinstall old bv refs
2340        vector<BvhLeaf *> leaves;
2341        mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
2342        vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
2343
2344        for (bit = leaves.begin(); bit != bit_end; ++ bit)
2345        {
2346                mBvHierarchy->AssociateObjectsWithLeaf(*bit);
2347        }
2348#endif
2349}
2350
2351
2352void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
2353                                                                                        const int splitsStepSize,
2354                                                                                        const bool useFilter,
2355                                                                                        const bool useHisto,
2356                                                                                        const int histoMem,
2357                                                                                        const int pass)
2358{
2359        vector<HierarchySubdivisionStats> subStatsContainer;
2360
2361        int splits = (1 + (mHierarchyStats.Leaves() - 1) / splitsStepSize) * splitsStepSize;
2362        cout << "splits: " << splits << endl;
2363
2364        bool histoUsed = false;
2365
2366        while (1)
2367        {
2368                HierarchySubdivisionStats subStats;
2369                subStats.mNumSplits = ExtractStatistics(splits,
2370                                                                                                99999.0,
2371                                                                                                subStats.mTotalRenderCost,
2372                                                                                                subStats.mMemoryCost,
2373                                                                                                subStats.mEntriesInPvs,
2374                                                                                                subStats.mViewSpaceSplits,
2375                                                                                                subStats.mObjectSpaceSplits,
2376                                                                                                useFilter,
2377                                                                                                useHisto && !histoUsed,
2378                                                                                                histoMem,
2379                                                                                                pass,
2380                                                                                                histoUsed);
2381
2382               
2383                const float objectSpaceHierarchyMem = float(
2384                                                                                          subStats.mObjectSpaceSplits * mBvHierarchy->mMemoryConst//sizeof(ObjectContainer)
2385                                                                                          //+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
2386                                                                                          //+sizeof(BvHierarchy)
2387                                                                                          ) / float(1024 * 1024);
2388
2389                       
2390                const float viewSpaceHierarchyMem = float(
2391                                                                                        subStats.mViewSpaceSplits * mVspTree->mMemoryConst//sizeof(ObjectPvs)
2392                                                                                        //+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
2393                                                                                        + sizeof(ObjectPvs)
2394                                                                                        //+ sizeof(VspTree)
2395                                                                                        )  / float(1024 * 1024);
2396
2397                subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
2398               
2399                subStatsContainer.push_back(subStats);
2400               
2401                if (splits == 0)
2402                {
2403                        break;
2404                }
2405                splits -= splitsStepSize;
2406
2407                cout << "splits: " << subStats.mNumSplits << " ";
2408        }
2409
2410        vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();
2411
2412        for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
2413        {
2414                (*hit).Print(splitsStats);
2415        }
2416
2417        // delete old "base" view cells: only pvss in the leaves are allowed
2418        ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2419        for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2420        {
2421                if (!(*oit)->IsLeaf())
2422                {
2423                        (*oit)->GetPvs().Clear();
2424                }
2425        }
2426
2427        mOldViewCells.clear();
2428
2429        // reset active nodes
2430        vector<BvhLeaf *> bvhLeaves;
2431
2432        mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), bvhLeaves);
2433
2434        vector<BvhLeaf *>::const_iterator bit, bit_end = bvhLeaves.end();
2435
2436        for (bit = bvhLeaves.begin(); bit != bit_end; ++ bit)
2437        {
2438                (*bit)->SetActiveNode(*bit);
2439        }
2440
2441        cout << endl;
2442}
2443
2444
2445void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
2446{
2447        mBvHierarchy->CollectObjects(box, objects);
2448}
2449
2450
2451int HierarchyManager::CompressObjectSpace()
2452{
2453        //mBvHierarchy->Compress();
2454        return mVspTree->CompressObjects();
2455}
2456
2457
2458void HierarchyManager::CreateUniqueObjectIds()
2459{
2460        mBvHierarchy->CreateUniqueObjectIds();
2461}
2462
2463
2464}
Note: See TracBrowser for help on using the repository browser.