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

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