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

Revision 2588, 66.2 KB checked in by bittner, 17 years ago (diff)

sceneBox bugfix

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