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

Revision 1576, 27.8 KB checked in by mattausch, 18 years ago (diff)

added measurement for pvs entries size decrease during subdivision
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "ViewCell.h"
6#include "Plane3.h"
7#include "HierarchyManager.h"
8#include "Mesh.h"
9#include "common.h"
10#include "Environment.h"
11#include "Polygon3.h"
12#include "Ray.h"
13#include "AxisAlignedBox3.h"
14#include "Exporter.h"
15#include "Plane3.h"
16#include "ViewCellsManager.h"
17#include "Beam.h"
18#include "KdTree.h"
19#include "IntersectableWrapper.h"
20#include "VspTree.h"
21#include "OspTree.h"
22#include "BvHierarchy.h"
23
24
25namespace GtpVisibilityPreprocessor {
26
27
28#define USE_FIXEDPOINT_T 0
29
30
31/*******************************************************************/
32/*              class HierarchyManager implementation              */
33/*******************************************************************/
34
35
36HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
37mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
38mOspTree(NULL),
39mBvHierarchy(NULL)
40{
41        switch(mObjectSpaceSubdivisionType)
42        {
43        case KD_BASED_OBJ_SUBDIV:
44                mOspTree = new OspTree();
45                mOspTree->mVspTree = mVspTree;
46                mOspTree->mHierarchyManager = this;
47                break;
48        case BV_BASED_OBJ_SUBDIV:
49        mBvHierarchy = new BvHierarchy();
50                mBvHierarchy->mHierarchyManager = this;
51                break;
52        default:
53                break;
54        }
55
56        // hierarchy manager links view space partition and object space partition
57        mVspTree = new VspTree();
58        mVspTree->mHierarchyManager = this;
59       
60        ParseEnvironment();
61}
62
63
64HierarchyManager::HierarchyManager(KdTree *kdTree):
65mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
66mBvHierarchy(NULL)
67{
68        mOspTree = new OspTree(*kdTree);
69        mOspTree->mVspTree = mVspTree;
70
71        mVspTree = new VspTree();
72        mVspTree->mHierarchyManager = this;
73
74        ParseEnvironment();
75}
76
77
78void HierarchyManager::ParseEnvironment()
79{
80        char subdivisionStatsLog[100];
81        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
82                subdivisionStatsLog);
83        mSubdivisionStats.open(subdivisionStatsLog);
84
85        Environment::GetSingleton()->GetFloatValue(
86                "Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
87        Environment::GetSingleton()->GetIntValue(
88                "Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
89
90        Environment::GetSingleton()->GetBoolValue(
91                "Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
92
93        Environment::GetSingleton()->GetIntValue(
94                "Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
95
96        Environment::GetSingleton()->GetIntValue(
97                "Hierarchy.Construction.type", mConstructionType);
98
99        Environment::GetSingleton()->GetIntValue(
100                "Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
101
102        Environment::GetSingleton()->GetIntValue(
103                "Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
104       
105        Environment::GetSingleton()->GetBoolValue(
106                "Hierarchy.Construction.repairQueue", mRepairQueue);
107
108        Environment::GetSingleton()->GetBoolValue(
109                "Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);
110
111         mUseMultiLevelConstruction;
112        Debug << "******** Hierachy Manager Parameters ***********" << endl;
113        Debug << "max leaves: " << mTermMaxLeaves << endl;
114        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
115        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
116        Debug << "construction type: " << mConstructionType << endl;
117        Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
118        Debug << "repair queue: " << mRepairQueue << endl;
119        Debug << endl;
120}
121
122
123HierarchyManager::~HierarchyManager()
124{
125        DEL_PTR(mOspTree);
126        DEL_PTR(mVspTree);
127        DEL_PTR(mBvHierarchy);
128}
129
130
131int HierarchyManager::GetObjectSpaceSubdivisionType() const
132{
133        return mObjectSpaceSubdivisionType;
134}
135
136
137int HierarchyManager::GetViewSpaceSubdivisionType() const
138{
139        return mViewSpaceSubdivisionType;
140}
141
142
143void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
144{
145        mVspTree->SetViewCellsManager(vcm);
146
147        if (mOspTree)
148        {
149                mOspTree->SetViewCellsManager(vcm);
150        }
151        else if (mBvHierarchy)
152        {
153                mBvHierarchy->SetViewCellsManager(vcm);
154        }
155}
156
157
158void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
159{
160        mVspTree->SetViewCellsTree(vcTree);
161}
162
163
164VspTree *HierarchyManager::GetVspTree()
165{
166        return mVspTree;
167}
168
169/*
170AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
171{
172        return mVspTree->mBoundingBox;
173}*/
174
175
176AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
177{
178        switch (mObjectSpaceSubdivisionType)
179        {
180        case KD_BASED_OBJ_SUBDIV:
181                return mOspTree->mBoundingBox;
182        case BV_BASED_OBJ_SUBDIV:
183                return mBvHierarchy->mBoundingBox;
184        default:
185                // hack: empty box
186                return AxisAlignedBox3();
187        }
188}
189
190
191SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
192{
193        SubdivisionCandidate *splitCandidate = mTQueue.Top();
194        mTQueue.Pop();
195
196        return splitCandidate;
197}
198
199
200void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
201{
202        const float costDecr = tData.GetRenderCostDecrease();
203
204        AddSubdivisionStats(mHierarchyStats.Leaves(),
205                                                costDecr,
206                                                mTotalCost,
207                                                mTotalPvsEntries
208                                                );
209}
210
211
212void HierarchyManager::AddSubdivisionStats(const int splits,
213                                                                                   const float renderCostDecr,
214                                                                                   const float totalRenderCost,
215                                                                                   const int pvsEntries)
216{
217        mSubdivisionStats
218                        << "#Splits\n" << splits << endl
219                        << "#RenderCostDecrease\n" << renderCostDecr << endl
220                        << "#TotalPvsEntries\n" << pvsEntries << endl
221                        << "#TotalRenderCost\n" << totalRenderCost << endl;
222}
223
224
225bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
226{
227        const bool terminationCriteriaMet =
228                (0
229                || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
230                || (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
231                || (candidate->GlobalTerminationCriteriaMet())
232                );
233
234        if (0 && terminationCriteriaMet)
235        {
236                Debug << "hierarchy global termination criteria met:" << endl;
237                Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
238                Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
239        }
240        return terminationCriteriaMet;
241}
242
243
244void HierarchyManager::Construct(const VssRayContainer &sampleRays,
245                                                                 const ObjectContainer &objects,
246                                                                 AxisAlignedBox3 *forcedViewSpace)
247{
248        if (mUseMultiLevelConstruction)
249        {
250                ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
251        }
252        else
253        {
254                ConstructInterleaved(sampleRays, objects, forcedViewSpace);
255        }
256}
257
258
259void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
260                                                                                        const ObjectContainer &objects,
261                                                                                        AxisAlignedBox3 *forcedViewSpace)
262{
263        mHierarchyStats.Reset();
264        mHierarchyStats.Start();
265        mHierarchyStats.nodes = 2; // two nodes for view space and object space
266
267        mTotalCost = (float)objects.size();
268        Debug << "setting total cost to " << mTotalCost << endl;
269
270        const long startTime = GetTime();
271        cout << "Constructing view space / object space tree ... \n";
272       
273        // compute view space bounding box
274        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
275
276        // use objects for evaluating vsp tree construction in the first levels
277        // of the subdivision
278        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
279        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
280
281        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
282        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
283
284        // start with view space subdivison: prepare vsp tree for traversal
285        if (StartViewSpaceSubdivision())
286        {
287                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
288                PrepareViewSpaceSubdivision(sampleRays, objects);
289        }
290       
291        // start object space subdivision immediately?
292        if (StartObjectSpaceSubdivision())
293        {
294                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
295                PrepareObjectSpaceSubdivision(sampleRays, objects);
296        }
297
298        // process object space candidates
299        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
300       
301        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
302
303/*#if _DEBUG
304        cout << "view space: " << GetViewSpaceBox() << endl;
305        cout << "object space:  " << GetObjectSpaceBox() << endl;
306#endif*/
307
308        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
309        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
310
311        mHierarchyStats.Stop();
312        mVspTree->mVspStats.Stop();
313        FinishObjectSpaceSubdivision(objects);
314}
315
316
317void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
318                                                                                                   const ObjectContainer &objects)
319{
320        cout << "\nstarting view space hierarchy construction ... " << endl;
321         // hack: reset global cost misses
322        mHierarchyStats.mGlobalCostMisses = 0;
323
324        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
325        SubdivisionCandidate *vsc =
326                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
327
328        mTotalCost = mVspTree->mTotalCost;
329        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
330
331        mTQueue.Push(vsc);
332}
333
334
335void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
336                                                                                                         const ObjectContainer &objects)
337{
338        mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses
339
340        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
341        {
342                PrepareOspTree(sampleRays, objects);
343        }
344        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
345        {
346                PrepareBvHierarchy(sampleRays, objects);
347        }
348}
349
350
351void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
352                                                                                  const ObjectContainer &objects)
353
354{
355        const long startTime = GetTime();
356
357        cout << "preparing bv hierarchy construction ... " << endl;
358       
359        // compute first candidate
360        SubdivisionCandidate *sc =
361                mBvHierarchy->PrepareConstruction(sampleRays, objects);
362
363        mTotalCost = mBvHierarchy->mTotalCost;
364        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
365
366    mTQueue.Push(sc);
367        cout << "finished bv hierarchy preparation in "
368                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
369}
370
371
372void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
373                                                                          const ObjectContainer &objects)
374{
375        cout << "starting osp tree construction ... " << endl;
376
377        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
378
379        // start with one big kd cell - all objects can be seen from everywhere
380        // note: only true for view space = object space
381
382        // compute first candidate
383        SubdivisionCandidate *osc =
384                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
385
386        mTotalCost = mOspTree->mTotalCost;
387        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
388       
389    mTQueue.Push(osc);
390}
391
392
393bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc)
394{
395        const bool globalTerminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
396        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
397
398        if (!globalTerminationCriteriaMet)
399        {
400                // cost ratio of cost decrease / totalCost
401                const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;
402                //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
403       
404                if (costRatio < mTermMinGlobalCostRatio)
405                {
406                        ++ mHierarchyStats.mGlobalCostMisses;
407                }
408
409                mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();
410        }
411
412        if (vspSplit)
413        {
414                VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
415
416                if (n->IsLeaf()) // local or global termination criteria failed
417                        return false;
418        }
419        else
420        {
421                if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
422                {
423                        KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
424                        // local or global termination criteria failed
425                        if (n->IsLeaf())
426                                return false;
427                }
428                else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
429                {
430                        BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
431                        // local or global termination criteria failed
432                        if (n->IsLeaf())
433                                return false;
434                }
435        }
436
437        return true;
438}
439
440
441int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
442{
443        int maxDepth = 0;
444
445        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
446        {
447                maxDepth = mOspTree->mOspStats.maxDepth;
448        }
449        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
450        {
451                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
452        }
453
454        return maxDepth;
455}
456
457
458bool HierarchyManager::StartObjectSpaceSubdivision() const
459{
460        // view space construction already started
461        if (ObjectSpaceSubdivisionConstructed())
462                return false;
463
464        // start immediately with object space subdivision?
465        if (mStartWithObjectSpace)
466                return true;
467
468        // is the queue empty again?
469        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
470                return true;
471
472        // has the depth for subdivision been reached?
473        return
474                ((mConstructionType == INTERLEAVED) &&
475                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
476}
477
478
479bool HierarchyManager::StartViewSpaceSubdivision() const
480{
481        // view space construction already started
482        if (ViewSpaceSubdivisionConstructed())
483                return false;
484
485        // start immediately with view space subdivision?
486        if (!mStartWithObjectSpace)
487                return true;
488
489        // is the queue empty again?
490        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
491                return true;
492
493        // has the depth for subdivision been reached?
494        return
495                ((mConstructionType == INTERLEAVED) &&
496                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
497}
498
499
500void HierarchyManager::RunConstruction(const bool repairQueue,
501                                                                           const VssRayContainer &sampleRays,
502                                                                           const ObjectContainer &objects,
503                                                                           AxisAlignedBox3 *forcedViewSpace)
504{
505        int i = 0;
506        while (!FinishedConstruction())
507        {
508                mCurrentCandidate = NextSubdivisionCandidate();   
509                       
510                ///////////////////
511                //-- subdivide leaf node
512
513                if (ApplySubdivisionCandidate(mCurrentCandidate))
514                {
515                        cout << mCurrentCandidate->Type() << " ";
516               
517                        // update stats
518                        mHierarchyStats.nodes += 2;
519                        mHierarchyStats.pvsEntries += mCurrentCandidate->GetPvsEntriesIncr();
520                        mHierarchyStats.memory += 0; // TODO
521                        // subdivision successful
522                        EvalSubdivisionStats(*mCurrentCandidate);
523               
524                        // reevaluate candidates affected by the split for view space splits,
525                        // this would be object space splits and other way round
526                        if (repairQueue)
527                        {       
528                                RepairQueue();
529                        }
530                }
531
532                // we use objects for evaluating vsp tree construction until
533                // a certain depth once a certain depth existiert ...
534                if (StartObjectSpaceSubdivision())
535                {
536                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
537
538                        cout << "\nstarting object space subdivision at depth "
539                                 << mVspTree->mVspStats.maxDepth << " ("
540                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl;
541
542                        PrepareObjectSpaceSubdivision(sampleRays, objects);
543
544                        cout << "reseting queue ... ";
545                        ResetQueue();
546                        cout << "finished" << endl;
547                }
548
549                if (StartViewSpaceSubdivision())
550                {
551                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
552
553                        cout << "\nstarting view space subdivision at depth "
554                                 << GetObjectSpaceSubdivisionDepth() << " ("
555                                 << mMinDepthForViewSpaceSubdivion << ") " << endl;
556
557                        PrepareViewSpaceSubdivision(sampleRays, objects);
558
559                        cout << "reseting queue ... ";
560                        ResetQueue();
561                        cout << "finished" << endl;
562                }
563
564                DEL_PTR(mCurrentCandidate);
565        }
566}
567
568
569
570void HierarchyManager::RunConstruction(const bool repairQueue)
571{
572        int i = 0;
573        while (!FinishedConstruction())
574        {
575                mCurrentCandidate = NextSubdivisionCandidate();   
576                       
577                ///////////////////
578                //-- subdivide leaf node
579
580                if (ApplySubdivisionCandidate(mCurrentCandidate))
581                {
582                        cout << mCurrentCandidate->Type() << " ";
583                        if (0) cout << "subdividing candidate " << ++ i << " of type "
584                                                << mCurrentCandidate->Type() << endl;
585                        mHierarchyStats.nodes += 2;
586
587                        // subdivision successful
588                        EvalSubdivisionStats(*mCurrentCandidate);
589               
590                        // reevaluate candidates affected by the split for view space splits,
591                        // this would be object space splits and other way round
592                        if (repairQueue) RepairQueue();
593                }
594
595                DEL_PTR(mCurrentCandidate);
596        }
597}
598
599
600void HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
601                                                                                                   const ObjectContainer &objects)
602{
603#if 0   
604                DEL_PTR(mBvHierarchy);
605                mBvHierarchy = new BvHierarchy();
606                mBvHierarchy->mHierarchyManager = this;
607
608                PrepareObjectSpaceSubdivision(sampleRays, objects);
609                return;
610#endif
611
612        if (!ObjectSpaceSubdivisionConstructed())
613        {
614                return PrepareObjectSpaceSubdivision(sampleRays, objects);
615        }
616
617        switch (mObjectSpaceSubdivisionType)
618        {
619        case BV_BASED_OBJ_SUBDIV:
620                cout << "\nreseting bv hierarchy" << endl;
621        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
622       
623                mHierarchyStats.nodes -= mBvHierarchy->mBvhStats.nodes;
624                mTQueue.Push(mBvHierarchy->Reset(sampleRays, objects));
625                mTotalCost = mBvHierarchy->mTotalCost;
626                break;
627
628        case KD_BASED_OBJ_SUBDIV:
629                // TODO
630                break;
631        default:
632                break;
633        }
634}
635
636
637void HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
638                                                                                                 const ObjectContainer &objects)
639{
640        DEL_PTR(mBvHierarchy);
641        mBvHierarchy = new BvHierarchy();
642        mBvHierarchy->mHierarchyManager = this;
643
644        PrepareViewSpaceSubdivision(sampleRays, objects);
645        return;
646}
647
648
649void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
650                                                                                   const ObjectContainer &objects,
651                                                                                   AxisAlignedBox3 *forcedViewSpace)
652{
653        mHierarchyStats.Reset();
654        mHierarchyStats.Start();
655        mHierarchyStats.nodes = 2;
656       
657        mTotalCost = (float)objects.size();
658        Debug << "setting total cost to " << mTotalCost << endl;
659
660        const long startTime = GetTime();
661        cout << "Constructing view space / object space tree ... \n";
662       
663        // compute view space bounding box
664        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
665
666        // use sah for evaluating object space construction for the first run
667        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
668        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
669       
670        const int limit = 4;
671        int i = 0;
672
673        // render cost optimization
674        // start with object space partiton
675        // then optimizate view space partition for the current osp
676        // and vice versa until iteration depth is reached.
677        while (1)
678        {
679        // first run object space subdivision
680                ResetObjectSpaceSubdivision(sampleRays, objects);
681
682                // process object space candidates
683                RunConstruction(false);
684
685                if ((++ i) >= limit)
686                        break;
687
688                /////////////////
689                // do view space subdivison with respect to the object space partition
690                ResetViewSpaceSubdivision(sampleRays, objects);
691
692                // process view space candidates
693                RunConstruction(false);
694                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
695               
696                if ((++ i) >= limit)
697                        break;
698
699                cout << "iteration " << i << " of " << limit << " finished" << endl;
700        }
701       
702        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
703
704/*#if _DEBUG
705        cout << "view space: " << GetViewSpaceBox() << endl;
706        cout << "object space:  " << GetObjectSpaceBox() << endl;
707#endif*/
708
709        mHierarchyStats.Stop();
710        mVspTree->mVspStats.Stop();
711        FinishObjectSpaceSubdivision(objects);
712}
713
714
715bool HierarchyManager::FinishedConstruction() const
716{
717        return mTQueue.Empty();
718}
719
720
721bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
722{
723        switch (mObjectSpaceSubdivisionType)
724        {
725        case KD_BASED_OBJ_SUBDIV:
726                return mOspTree && mOspTree->GetRoot();
727        case BV_BASED_OBJ_SUBDIV:
728                return mBvHierarchy && mBvHierarchy->GetRoot();
729        default:
730        return false;
731        }
732}
733
734
735bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
736{
737        return mVspTree && mVspTree->GetRoot();
738}
739
740
741void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
742{
743        switch (mObjectSpaceSubdivisionType)
744        {
745        case KD_BASED_OBJ_SUBDIV:
746                {
747                        OspTree::OspSubdivisionCandidate *sc =
748                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
749
750                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
751                        break;
752                }
753        case BV_BASED_OBJ_SUBDIV:
754                {
755                        BvHierarchy::BvhSubdivisionCandidate *sc =
756                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
757
758                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
759                        break;
760                }
761        default:
762                break;
763        }
764}
765
766
767void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
768{
769        VspTree::VspSubdivisionCandidate *sc =
770                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
771
772        mVspTree->CollectDirtyCandidates(sc, dirtyList);
773}
774
775
776void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
777{
778        // we have either a object space or view space split
779        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
780        {
781                CollectViewSpaceDirtyList(dirtyList);
782        }
783        else // object space split
784        {
785                CollectObjectSpaceDirtyList(dirtyList);
786        }
787}
788
789
790void HierarchyManager::RepairQueue()
791{
792        // for each update of the view space partition:
793        // the candidates from object space partition which
794        // have been afected by the view space split (the kd split candidates
795        // which saw the view cell which was split) must be reevaluated
796        // (maybe not locally, just reinsert them into the queue)
797        //
798        // vice versa for the view cells
799        // for each update of the object space partition
800        // reevaluate split candidate for view cells which saw the split kd cell
801        //
802        // the priority queue update can be solved by implementing a binary heap
803        // (explicit data structure, binary tree)
804        // *) inserting and removal is efficient
805        // *) search is not efficient => store queue position with each
806        // split candidate
807
808        // collect list of "dirty" candidates
809        long startTime = GetTime();
810   
811        vector<SubdivisionCandidate *> dirtyList;
812        CollectDirtyCandidates(dirtyList);
813        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
814       
815        /////////////////////////////////
816        //-- reevaluate the dirty list
817
818        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
819       
820        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
821        {
822                SubdivisionCandidate* sc = *sit;
823                const float rcd = sc->GetRenderCostDecrease();
824               
825                mTQueue.Erase(sc); // erase from queue
826                sc->EvalPriority(); // reevaluate
827               
828                /*
829                Debug << "candidate " << sc << " reevaluated\n"
830                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
831                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;*/
832                if (0)
833                {
834                        const float rcDiff =  rcd - sc->GetRenderCostDecrease();
835                        mTotalCost += rcDiff;
836                }
837                mTQueue.Push(sc); // reinsert
838        }
839
840        long endTime = GetTime();
841        Real timeDiff = TimeDiff(startTime, endTime);
842
843        mHierarchyStats.repairTime += timeDiff;
844
845        if (0) cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
846}
847
848
849void HierarchyManager::ResetQueue()
850{
851        SubdivisionCandidateContainer mCandidateBuffer;
852
853        // remove from queue
854        while (!mTQueue.Empty())
855        {
856                SubdivisionCandidate *candidate = NextSubdivisionCandidate();
857                candidate->EvalPriority(); // reevaluate
858                cout << ".";
859                mCandidateBuffer.push_back(candidate);
860        }
861
862        // put back into queue
863        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
864    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
865        {cout << ":";
866                mTQueue.Push(*sit);
867        }
868}
869
870
871void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
872{
873        // the type of the view cells hierarchy
874        switch (mObjectSpaceSubdivisionType)
875        {
876        case KD_BASED_OBJ_SUBDIV:
877                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
878                mOspTree->Export(stream);
879                stream << endl << "</ObjectSpaceHierarchy>" << endl;
880                break;         
881        case BV_BASED_OBJ_SUBDIV:
882                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
883                mBvHierarchy->Export(stream);
884                stream << endl << "</ObjectSpaceHierarchy>" << endl;
885                break;
886        }
887}
888
889
890bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
891                                                                          const Vector3 &hitPoint,
892                                                                          ViewCell *vc,
893                                                                          const float pdf,
894                                                                          float &contribution) const
895{
896        if (!obj) return false;
897
898        switch (mObjectSpaceSubdivisionType)
899        {
900        case NO_OBJ_SUBDIV:
901                {
902                        // potentially visible objects
903                        return vc->AddPvsSample(obj, pdf, contribution);
904                }
905        case KD_BASED_OBJ_SUBDIV:
906                {
907                        // potentially visible kd cells
908                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
909                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
910                }
911        case BV_BASED_OBJ_SUBDIV:
912                {
913                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
914                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
915                       
916                        return vc->AddPvsSample(bvhObj, pdf, contribution);
917                }
918        default:
919                return false;
920        }
921}
922
923
924void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
925{
926        stream << mHierarchyStats << endl;
927        stream << "\nview space:" << endl << endl;
928        stream << mVspTree->GetStatistics() << endl;
929        stream << "\nobject space:" << endl << endl;
930
931        switch (mObjectSpaceSubdivisionType)
932        {
933        case KD_BASED_OBJ_SUBDIV:
934                {
935                        stream << mOspTree->GetStatistics() << endl;
936                        break;
937                }
938        case BV_BASED_OBJ_SUBDIV:
939                {
940                        stream << mBvHierarchy->GetStatistics() << endl;
941                        break;
942                }
943        default:
944                break;
945        }
946}
947
948
949void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
950                                                                                                  const ObjectContainer &objects,
951                                                                                                  const AxisAlignedBox3 *bbox,
952                                                                                                  const bool exportBounds) const
953{
954        switch (mObjectSpaceSubdivisionType)
955        {
956        case KD_BASED_OBJ_SUBDIV:
957                {
958                        ExportOspTree(exporter, objects);
959                        break;
960                }
961        case BV_BASED_OBJ_SUBDIV:
962                {
963                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
964                        break;
965                }
966        default:
967                break;
968        }
969}
970
971
972void HierarchyManager::ExportOspTree(Exporter *exporter,
973                                                                         const ObjectContainer &objects) const
974{
975        if (0) exporter->ExportGeometry(objects);
976                       
977        exporter->SetWireframe();
978        exporter->ExportOspTree(*mOspTree, 0);
979}
980
981
982Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
983                                                                                                  const bool isTermination) const
984{
985
986        Intersectable *obj;
987        Vector3 pt;
988        KdNode *node;
989
990        ray.GetSampleData(isTermination, pt, &obj, &node);
991       
992        if (!obj) return NULL;
993
994        switch (mObjectSpaceSubdivisionType)
995        {
996        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
997                {
998                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
999                        return mOspTree->GetOrCreateKdIntersectable(leaf);
1000                }
1001        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1002                {
1003                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1004                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1005                }
1006        default:
1007                return obj;
1008        }
1009}
1010
1011
1012void HierarchyStatistics::Print(ostream &app) const
1013{
1014        app << "=========== Hierarchy statistics ===============\n";
1015
1016        app << setprecision(4);
1017
1018        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1019       
1020        app << "#N_RTIME  ( Repair time [s] )\n" << repairTime * 1e-3f << " \n";
1021
1022        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
1023
1024        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1025
1026        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1027
1028        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
1029
1030        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1031       
1032        app << "========== END OF Hierarchy statistics ==========\n";
1033}
1034
1035
1036static void RemoveRayRefs(const ObjectContainer &objects)
1037{
1038        ObjectContainer::const_iterator oit, oit_end = objects.end();
1039        for (oit = objects.begin(); oit != oit_end; ++ oit)
1040        {
1041                (*oit)->mVssRays.clear();
1042        }
1043}
1044
1045
1046void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
1047{
1048        switch (mObjectSpaceSubdivisionType)
1049        {
1050        case KD_BASED_OBJ_SUBDIV:
1051                {
1052                        mOspTree->mOspStats.Stop();
1053                        break;
1054                }
1055        case BV_BASED_OBJ_SUBDIV:
1056                {
1057                        mBvHierarchy->mBvhStats.Stop();
1058                        RemoveRayRefs(objects);
1059                        break;
1060                }
1061        default:
1062                break;
1063        }
1064}
1065
1066}
Note: See TracBrowser for help on using the repository browser.