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

Revision 1449, 27.0 KB checked in by mattausch, 18 years ago (diff)
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 << "starting 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: " << mBvHierarchy->mBvhStats << endl;
606        mHierarchyStats.nodes -= mBvHierarchy->mBvhStats.nodes;
607        mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses
608        DEL_PTR(mBvHierarchy);
609        mBvHierarchy = new BvHierarchy();
610        mBvHierarchy->mHierarchyManager = this;
611}
612
613
614void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
615                                                                                   const ObjectContainer &objects,
616                                                                                   AxisAlignedBox3 *forcedViewSpace)
617{
618        mHierarchyStats.Reset();
619        mHierarchyStats.Start();
620
621        mHierarchyStats.nodes = 2;
622       
623
624        mTotalCost = (float)objects.size();
625        Debug << "setting total cost to " << mTotalCost << endl;
626
627        const long startTime = GetTime();
628        cout << "Constructing view space / object space tree ... \n";
629       
630        // compute view space bounding box
631        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
632
633        // use sah for evaluating object space construction for the first run
634        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
635        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
636
637        // start with object space subdivision
638        PrepareObjectSpaceSubdivision(sampleRays, objects);
639       
640        // process object space candidates
641        RunConstruction(false);
642
643        /////////////////
644    // now do view space subdivison on the sah bvh nodes
645        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
646        PrepareViewSpaceSubdivision(sampleRays, objects);
647       
648        // process view space candidates
649        RunConstruction(false);
650       
651        // again run object space subdivision on the view cells
652        ResetObjectSpaceSubdivision(objects);
653        PrepareObjectSpaceSubdivision(sampleRays, objects);
654
655        // process object space candidates
656        RunConstruction(false);
657       
658        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
659
660#if _DEBUG
661        cout << "view space: " << GetViewSpaceBox() << endl;
662        cout << "object space:  " << GetObjectSpaceBox() << endl;
663#endif
664
665        mHierarchyStats.Stop();
666        mVspTree->mVspStats.Stop();
667        FinishObjectSpaceSubdivision(objects);
668}
669
670
671bool HierarchyManager::FinishedConstruction() const
672{
673        return mTQueue.Empty();
674}
675
676
677bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
678{
679        switch (mObjectSpaceSubdivisionType)
680        {
681        case KD_BASED_OBJ_SUBDIV:
682                return mOspTree && mOspTree->GetRoot();
683        case BV_BASED_OBJ_SUBDIV:
684                return mBvHierarchy && mBvHierarchy->GetRoot();
685        default:
686        return false;
687        }
688}
689
690
691bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
692{
693        return mVspTree && mVspTree->GetRoot();
694}
695
696
697void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
698{
699        switch (mObjectSpaceSubdivisionType)
700        {
701        case KD_BASED_OBJ_SUBDIV:
702                {
703                        OspTree::OspSubdivisionCandidate *sc =
704                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
705
706                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
707                        break;
708                }
709        case BV_BASED_OBJ_SUBDIV:
710                {
711                        BvHierarchy::BvhSubdivisionCandidate *sc =
712                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
713
714                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
715                        break;
716                }
717        default:
718                break;
719        }
720}
721
722
723void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
724{
725        VspTree::VspSubdivisionCandidate *sc =
726                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
727
728        mVspTree->CollectDirtyCandidates(sc, dirtyList);
729}
730
731
732void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
733{
734        // we have either a object space or view space split
735        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
736        {
737                CollectViewSpaceDirtyList(dirtyList);
738        }
739        else // object space split
740        {
741                CollectObjectSpaceDirtyList(dirtyList);
742        }
743}
744
745
746void HierarchyManager::RepairQueue()
747{
748        // for each update of the view space partition:
749        // the candidates from object space partition which
750        // have been afected by the view space split (the kd split candidates
751        // which saw the view cell which was split) must be reevaluated
752        // (maybe not locally, just reinsert them into the queue)
753        //
754        // vice versa for the view cells
755        // for each update of the object space partition
756        // reevaluate split candidate for view cells which saw the split kd cell
757        //
758        // the priority queue update can be solved by implementing a binary heap
759        // (explicit data structure, binary tree)
760        // *) inserting and removal is efficient
761        // *) search is not efficient => store queue position with each
762        // split candidate
763
764        // collect list of "dirty" candidates
765        long startTime = GetTime();
766   
767        vector<SubdivisionCandidate *> dirtyList;
768        CollectDirtyCandidates(dirtyList);
769        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
770       
771        /////////////////////////////////
772        //-- reevaluate the dirty list
773
774        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
775       
776        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
777        {
778                SubdivisionCandidate* sc = *sit;
779                const float rcd = sc->GetRenderCostDecrease();
780               
781                mTQueue.Erase(sc); // erase from queue
782                sc->EvalPriority(); // reevaluate
783               
784                /*
785                Debug << "candidate " << sc << " reevaluated\n"
786                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
787                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;*/
788                if (0)
789                {
790                        const float rcDiff =  rcd - sc->GetRenderCostDecrease();
791                        mTotalCost += rcDiff;
792                }
793                mTQueue.Push(sc); // reinsert
794        }
795
796        long endTime = GetTime();
797        Real timeDiff = TimeDiff(startTime, endTime);
798
799        mHierarchyStats.repairTime += timeDiff;
800
801        if (0) cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
802}
803
804
805void HierarchyManager::ResetQueue()
806{
807        SubdivisionCandidateContainer mCandidateBuffer;
808
809        // remove from queue
810        while (!mTQueue.Empty())
811        {
812                SubdivisionCandidate *candidate = NextSubdivisionCandidate();
813                candidate->EvalPriority(); // reevaluate
814                cout << ".";
815                mCandidateBuffer.push_back(candidate);
816        }
817
818        // put back into queue
819        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
820    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
821        {cout << ":";
822                mTQueue.Push(*sit);
823        }
824}
825
826
827void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
828{
829        // the type of the view cells hierarchy
830        switch (mObjectSpaceSubdivisionType)
831        {
832        case KD_BASED_OBJ_SUBDIV:
833                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
834                mOspTree->Export(stream);
835                stream << endl << "</ObjectSpaceHierarchy>" << endl;
836                break;         
837        case BV_BASED_OBJ_SUBDIV:
838                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
839                mBvHierarchy->Export(stream);
840                stream << endl << "</ObjectSpaceHierarchy>" << endl;
841                break;
842        }
843}
844
845
846bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
847                                                                          const Vector3 &hitPoint,
848                                                                          ViewCell *vc,
849                                                                          const float pdf,
850                                                                          float &contribution) const
851{
852        if (!obj) return false;
853
854        switch (mObjectSpaceSubdivisionType)
855        {
856        case NO_OBJ_SUBDIV:
857                // potentially visible objects
858                return vc->AddPvsSample(obj, pdf, contribution);
859        case KD_BASED_OBJ_SUBDIV:
860                {
861                        // potentially visible kd cells
862                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
863                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
864                }
865        case BV_BASED_OBJ_SUBDIV:
866                {
867                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
868                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
869                       
870                        return vc->AddPvsSample(bvhObj, pdf, contribution);
871                }
872        default:
873                return false;
874        }
875}
876
877
878void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
879{
880        stream << mHierarchyStats << endl;
881        stream << "\nview space:" << endl << endl;
882        stream << mVspTree->GetStatistics() << endl;
883        stream << "\nobject space:" << endl << endl;
884
885        switch (mObjectSpaceSubdivisionType)
886        {
887        case KD_BASED_OBJ_SUBDIV:
888                {
889                        stream << mOspTree->GetStatistics() << endl;
890                        break;
891                }
892        case BV_BASED_OBJ_SUBDIV:
893                {
894                        stream << mBvHierarchy->GetStatistics() << endl;
895                        break;
896                }
897        default:
898                break;
899        }
900}
901
902
903void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
904                                                                                                  const ObjectContainer &objects,
905                                                                                                  const AxisAlignedBox3 *bbox,
906                                                                                                  const bool exportBounds) const
907{
908        switch (mObjectSpaceSubdivisionType)
909        {
910        case KD_BASED_OBJ_SUBDIV:
911                {
912                        ExportOspTree(exporter, objects);
913                        break;
914                }
915        case BV_BASED_OBJ_SUBDIV:
916                {
917                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
918                        break;
919                }
920        default:
921                break;
922        }
923}
924
925
926void HierarchyManager::ExportOspTree(Exporter *exporter,
927                                                                         const ObjectContainer &objects) const
928{
929        if (0) exporter->ExportGeometry(objects);
930                       
931        exporter->SetWireframe();
932        exporter->ExportOspTree(*mOspTree, 0);
933}
934
935
936Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
937                                                                                                  const bool isTermination) const
938{
939
940        Intersectable *obj;
941        Vector3 pt;
942        KdNode *node;
943
944        ray.GetSampleData(isTermination, pt, &obj, &node);
945       
946        if (!obj) return NULL;
947
948        switch (mObjectSpaceSubdivisionType)
949        {
950        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
951                {
952                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
953                        return mOspTree->GetOrCreateKdIntersectable(leaf);
954                }
955        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
956                {
957                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
958                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
959                }
960        default:
961                return obj;
962        }
963}
964
965
966void HierarchyStatistics::Print(ostream &app) const
967{
968        app << "=========== Hierarchy statistics ===============\n";
969
970        app << setprecision(4);
971
972        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
973       
974        app << "#N_RTIME  ( Repair time [s] )\n" << repairTime * 1e-3f << " \n";
975
976        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
977
978        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
979
980        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
981
982        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
983
984        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
985       
986        app << "========== END OF Hierarchy statistics ==========\n";
987}
988
989
990static void RemoveRayRefs(const ObjectContainer &objects)
991{
992        ObjectContainer::const_iterator oit, oit_end = objects.end();
993        for (oit = objects.begin(); oit != oit_end; ++ oit)
994        {
995                (*oit)->mVssRays.clear();
996        }
997}
998
999
1000void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
1001{
1002        switch (mObjectSpaceSubdivisionType)
1003        {
1004        case KD_BASED_OBJ_SUBDIV:
1005                {
1006                        mOspTree->mOspStats.Stop();
1007                        break;
1008                }
1009        case BV_BASED_OBJ_SUBDIV:
1010                {
1011                        mBvHierarchy->mBvhStats.Stop();
1012                        RemoveRayRefs(objects);
1013                        break;
1014                }
1015        default:
1016                break;
1017        }
1018}
1019
1020}
Note: See TracBrowser for help on using the repository browser.