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

Revision 1486, 27.1 KB checked in by mattausch, 18 years ago (diff)

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