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

Revision 1733, 58.3 KB checked in by mattausch, 18 years ago (diff)

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