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

Revision 1313, 18.5 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 "KdIntersectable.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(VspTree *vspTree,
37                                                                   const int objectSpaceSubdivisionType):
38mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
39mVspTree(vspTree),
40mOspTree(NULL),
41mBvHierarchy(NULL)
42{
43        switch(mObjectSpaceSubdivisionType)
44        {
45        case KD_BASED_OBJ_SUBDIV:
46                mOspTree = new OspTree();
47                mOspTree->mVspTree = mVspTree;
48                //mOspTree->mHierarchyManager = this;
49                Debug << "creating osp tree" << endl;
50                break;
51        case BV_BASED_OBJ_SUBDIV:
52        mBvHierarchy = new BvHierarchy();
53                mBvHierarchy->mVspTree = mVspTree;
54                //mBvHierarchy->mHierarchyManager = this;
55                Debug << "creating bv hierachy" << endl;
56                break;
57        default:
58                break;
59        }
60
61        if (mVspTree)
62                mVspTree->mHierarchyManager = this;
63
64        ParseEnvironment();
65}
66
67
68HierarchyManager::HierarchyManager(VspTree *vspTree, KdTree *kdTree):
69mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
70mVspTree(vspTree),
71mBvHierarchy(NULL)
72{
73        mOspTree = new OspTree(*kdTree);
74        mOspTree->mVspTree = mVspTree;
75
76        //mOspTree->mHierarchyManager = this;
77        Debug << "creating osp tree" << endl;
78
79        if (mVspTree)
80                mVspTree->mHierarchyManager = this;
81
82        ParseEnvironment();
83}
84
85
86void HierarchyManager::ParseEnvironment()
87{
88        char subdivisionStatsLog[100];
89        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
90                subdivisionStatsLog);
91        mSubdivisionStats.open(subdivisionStatsLog);
92
93        Environment::GetSingleton()->GetFloatValue(
94                "Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
95        Environment::GetSingleton()->GetIntValue(
96                "Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
97
98        Environment::GetSingleton()->GetIntValue(
99                "Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
100
101        Environment::GetSingleton()->GetIntValue(
102                "Hierarchy.Construction.type", mConstructionType);
103
104        Environment::GetSingleton()->GetIntValue(
105                "Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
106       
107        Debug << "******** Hierachy Manager Parameters ***********" << endl;
108        Debug << "max leaves: " << mTermMaxLeaves << endl;
109        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
110        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
111}
112
113
114HierarchyManager::~HierarchyManager()
115{
116        DEL_PTR(mOspTree);
117        //DEL_PTR(mVspTree);
118        DEL_PTR(mBvHierarchy);
119}
120
121
122void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
123{
124        mVspTree->SetViewCellsManager(vcm);
125
126        if (mOspTree)
127                mOspTree->SetViewCellsManager(vcm);
128        if (mBvHierarchy)
129                mBvHierarchy->SetViewCellsManager(vcm);
130}
131
132
133void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
134{
135        mVspTree->SetViewCellsTree(vcTree);
136}
137
138
139SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
140{
141        SubdivisionCandidate *splitCandidate = mTQueue.Top();
142        mTQueue.Pop();
143
144        return splitCandidate;
145}
146
147
148void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
149{
150        const float costDecr = tData.GetRenderCostDecrease();
151
152        switch (mObjectSpaceSubdivisionType)
153        {
154        case KD_BASED_OBJ_SUBDIV:
155                AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
156                                                        costDecr,
157                                                        mTotalCost
158                                                        );
159                break;
160        case BV_BASED_OBJ_SUBDIV:
161                AddSubdivisionStats(mBvHierarchy->mBvhStats.Leaves() + mVspTree->mVspStats.Leaves(),
162                                                        costDecr,
163                                                        mTotalCost
164                                                        );
165                break;
166        default:
167                AddSubdivisionStats(mVspTree->mVspStats.Leaves(),
168                                                        costDecr,
169                                                        mTotalCost
170                                                        );
171                break;
172        }
173}
174
175
176void HierarchyManager::AddSubdivisionStats(const int splits,
177                                                                                   const float renderCostDecr,
178                                                                                   const float totalRenderCost)
179{
180        mSubdivisionStats
181                        << "#Splits\n" << splits << endl
182                        << "#RenderCostDecrease\n" << renderCostDecr << endl
183                        << "#TotalRenderCost\n" << totalRenderCost << endl;
184                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
185}
186
187
188bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
189{
190        return (0
191                || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
192                //|| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
193                ||      candidate->GlobalTerminationCriteriaMet()
194                );
195}
196
197
198void HierarchyManager::Construct(const VssRayContainer &sampleRays,
199                                                                 const ObjectContainer &objects,
200                                                                 AxisAlignedBox3 *forcedViewSpace)
201{
202       
203        mHierarchyStats.Reset();
204        mHierarchyStats.Start();
205       
206        mTotalCost = (float)objects.size();
207        Debug << "setting total cost to " << mTotalCost << endl;
208
209        const long startTime = GetTime();
210        cout << "Constructing view space / object space tree ... \n";
211       
212        // process object space candidates
213        RunConstruction(sampleRays, objects, forcedViewSpace);
214       
215        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
216        mHierarchyStats.Stop();
217        mVspTree->mVspStats.Stop();
218}
219
220
221void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
222                                                                                                   const ObjectContainer &objects,
223                                                                                                   AxisAlignedBox3 *forcedViewSpace)
224{
225        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
226        SubdivisionCandidate *vsc =
227                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
228
229        mTQueue.Push(vsc);
230}
231
232
233void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
234                                                                                                         const ObjectContainer &objects)
235{
236        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
237        {
238                PrepareOspTree(sampleRays, objects);
239        }
240        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
241        {
242                PrepareBvHierarchy(sampleRays, objects);
243        }
244}
245
246
247void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
248                                                                                  const ObjectContainer &objects)
249
250{
251        cout << "starting bv hierarchy construction ... " << endl;
252
253        mBvHierarchy->CreateRoot(objects);
254
255        // compute first candidate
256        SubdivisionCandidate *sc =
257                mBvHierarchy->PrepareConstruction(sampleRays, objects);
258
259        mTotalCost = mBvHierarchy->mTotalCost;
260        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
261
262    mTQueue.Push(sc);
263}
264
265
266void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
267                                                                          const ObjectContainer &objects)
268{
269        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
270
271        cout << "starting osp tree construction ... " << endl;
272
273        // start with one big kd cell - all objects can be seen from everywhere
274        // note: only true for view space = object space
275
276        // compute first candidate
277        SubdivisionCandidate *osc =
278                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
279
280        mTotalCost = mOspTree->mTotalCost;
281        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
282       
283    mTQueue.Push(osc);
284}
285
286
287bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc)
288{
289        const bool globalTerminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
290        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
291
292        if (vspSplit)
293        {
294                VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
295
296                if (n->IsLeaf()) // local or global termination criteria failed
297                        return false;
298        }
299        else
300        {
301                if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
302                {
303                        KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
304
305                        if (n->IsLeaf()) // local or global termination criteria failed
306                                return false;
307                }
308                else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
309                {
310                        BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
311
312                        if (n->IsLeaf()) // local or global termination criteria failed
313                                return false;
314                }
315        }
316        return true;//!globalTerminationCriteriaMet;
317}
318
319
320bool HierarchyManager::StartObjectSpaceSubdivision() const
321{
322        const bool ospDepthReached =
323                (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth);
324        const bool stillNotOsp = (mObjectSpaceSubdivisionType == NO_OBJ_SUBDIV);
325   
326        return stillNotOsp && (mTQueue.Empty() || ((mConstructionType == 1) && ospDepthReached));
327}
328
329
330void HierarchyManager::RunConstruction(const VssRayContainer &sampleRays,
331                                                                           const ObjectContainer &objects,
332                                                                           AxisAlignedBox3 *forcedViewSpace)
333{
334        mHierarchyStats.nodes = 0;
335        mGlobalCostMisses = 0;
336
337        // use objects for evaluating vsp tree construction in the first levels
338        // of the subdivision
339        const int savedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
340        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
341
342        // start with view space subdivison: prepare vsp tree for traversal
343        PrepareViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
344
345        //const bool repairQueue = false;
346        const bool repairQueue = true;
347cout << "here55 " << mVspTree->mVspStats.maxDepth << " (" << mMinDepthForObjectSpaceSubdivion << ") " << endl;
348        // start object space subdivision immediately?
349        if (StartObjectSpaceSubdivision())
350        {cout << "here1155 ";
351                mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
352                PrepareObjectSpaceSubdivision(sampleRays, objects);
353        }
354
355        int i = 0;
356        while (!FinishedConstruction())
357        {
358                mCurrentCandidate = NextSubdivisionCandidate();   
359                mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();
360
361                // cost ratio of cost decrease / totalCost
362                const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;
363
364                //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
365                if (costRatio < mTermMinGlobalCostRatio)
366                {
367                        ++ mGlobalCostMisses;
368                }
369               
370                //-- subdivide leaf node
371                if (ApplySubdivisionCandidate(mCurrentCandidate))
372                {
373                        cout << "subdividing candidate " << ++ i << " of type " << mCurrentCandidate->Type() << endl;
374                        mHierarchyStats.nodes += 2;
375
376                        // subdivision successful
377                        EvalSubdivisionStats(*mCurrentCandidate);
378               
379                        // reevaluate candidates affected by the split for view space splits,
380                        // this would be object space splits and other way round
381                        if (repairQueue) RepairQueue();
382                }
383
384                // we use objects for evaluating vsp tree construction until
385                // a certain depth once a certain depth existiert ....
386                if (StartObjectSpaceSubdivision())
387                {
388                        cout << "reseting queue ... ";
389                        ResetQueue();
390                        cout << "finished" << endl;
391
392                        cout << "starting object space subdivision at maximal view space subdivison depth " << mVspTree->mVspStats.maxDepth << " (" << mMinDepthForObjectSpaceSubdivion << ") " << endl;
393                                               
394                        mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
395                        PrepareObjectSpaceSubdivision(sampleRays, objects);
396                }
397
398                DEL_PTR(mCurrentCandidate);
399        }
400       
401        mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
402}
403
404
405bool HierarchyManager::FinishedConstruction() const
406{
407        return mTQueue.Empty();
408}
409
410
411bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
412{
413        switch (mObjectSpaceSubdivisionType)
414        {
415        case KD_BASED_OBJ_SUBDIV:
416                return mOspTree && mOspTree->GetRoot();
417        case BV_BASED_OBJ_SUBDIV:
418                return mBvHierarchy && mOspTree->GetRoot();
419        default:
420        return false;
421        }
422}
423
424
425void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
426{
427        switch (mObjectSpaceSubdivisionType)
428        {
429        case KD_BASED_OBJ_SUBDIV:
430                {
431                        OspTree::OspSubdivisionCandidate *sc =
432                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
433
434                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
435                        break;
436                }
437        case BV_BASED_OBJ_SUBDIV:
438                {
439                        BvHierarchy::BvhSubdivisionCandidate *sc =
440                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
441
442                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
443                        break;
444                }
445        default:
446                break;
447        }
448}
449
450
451void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
452{
453        VspTree::VspSubdivisionCandidate *sc =
454                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
455
456        mVspTree->CollectDirtyCandidates(sc, dirtyList);
457}
458
459
460void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
461{
462        // we have either a object space or view space split
463        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
464        {
465                CollectViewSpaceDirtyList(dirtyList);
466        }
467        else // object space split
468        {
469                CollectObjectSpaceDirtyList(dirtyList);
470        }
471}
472
473
474void HierarchyManager::RepairQueue()
475{
476        // for each update of the view space partition:
477        // the candidates from object space partition which
478        // have been afected by the view space split (the kd split candidates
479        // which saw the view cell which was split) must be reevaluated
480        // (maybe not locally, just reinsert them into the queue)
481        //
482        // vice versa for the view cells
483        // for each update of the object space partition
484        // reevaluate split candidate for view cells which saw the split kd cell
485        //
486        // the priority queue update can be solved by implementing a binary heap
487        // (explicit data structure, binary tree)
488        // *) inserting and removal is efficient
489        // *) search is not efficient => store queue position with each
490        // split candidate
491
492        // collect list of "dirty" candidates
493        long startTime = GetTime();
494   
495        vector<SubdivisionCandidate *> dirtyList;
496        CollectDirtyCandidates(dirtyList);
497        cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
498       
499        //-- reevaluate the dirty list
500        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
501       
502        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
503        {
504                SubdivisionCandidate* sc = *sit;
505                const float rcd = sc->GetRenderCostDecrease();
506               
507                mTQueue.Erase(sc); // erase from queue
508                sc->EvalPriority(); // reevaluate
509               
510                /*
511                Debug << "candidate " << sc << " reevaluated\n"
512                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
513                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;*/
514                if (0)
515                {
516                        const float rcDiff =  rcd - sc->GetRenderCostDecrease();
517                        mTotalCost += rcDiff;
518                }
519                mTQueue.Push(sc); // reinsert
520        }
521
522        long endTime = GetTime();
523        Real timeDiff = TimeDiff(startTime, endTime);
524
525        mHierarchyStats.repairTime += timeDiff;
526
527        cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
528}
529
530
531void HierarchyManager::ResetQueue()
532{
533        SubdivisionCandidateContainer mCandidateBuffer;
534
535        // remove from queue
536        while (!mTQueue.Empty())
537        {
538                SubdivisionCandidate *candidate = NextSubdivisionCandidate();
539                candidate->EvalPriority(); // reevaluate
540                cout << ".";
541                mCandidateBuffer.push_back(candidate);
542        }
543
544        // put back into queue
545        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
546    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
547        {cout << ":";
548                mTQueue.Push(*sit);
549        }
550}
551
552
553void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
554{
555        // the type of the view cells hierarchy
556        switch (mObjectSpaceSubdivisionType)
557        {
558        case KD_BASED_OBJ_SUBDIV:
559                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
560                mOspTree->Export(stream);
561                stream << endl << "</ObjectSpaceHierarchy>" << endl;
562                break;         
563        case BV_BASED_OBJ_SUBDIV:
564                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
565                mBvHierarchy->Export(stream);
566                stream << endl << "</ObjectSpaceHierarchy>" << endl;
567                break;
568        }
569}
570
571
572bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
573                                                                          const Vector3 &hitPoint,
574                                                                          ViewCell *vc,
575                                                                          const float pdf,
576                                                                          float &contribution) const
577{
578        if (!obj) return false;
579
580        switch (mObjectSpaceSubdivisionType)
581        {
582        case NO_OBJ_SUBDIV:
583                // potentially visible objects
584                return vc->AddPvsSample(obj, pdf, contribution);
585        case KD_BASED_OBJ_SUBDIV:
586                {
587                        // potentially visible kd cells
588                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
589                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
590                }
591        case BV_BASED_OBJ_SUBDIV:
592                {
593                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
594                        return mBvHierarchy->AddLeafToPvs(leaf, vc, pdf, contribution);
595                }
596        default:
597                return false;
598        }
599}
600
601
602void HierarchyManager::PrintHierarchyStatistics(ofstream &stream) const
603{
604        stream << mHierarchyStats << endl;
605
606        stream << "\nview space:" << endl << endl;
607        stream << mVspTree->GetStatistics() << endl;
608        stream << "\nobject space:" << endl << endl;
609        switch (mObjectSpaceSubdivisionType)
610        {
611        case KD_BASED_OBJ_SUBDIV:
612                {
613                        stream << mOspTree->GetStatistics() << endl;
614                        break;
615                }
616        case BV_BASED_OBJ_SUBDIV:
617                {
618                        stream << mBvHierarchy->GetStatistics() << endl;
619                        break;
620                }
621        default:
622                break;
623        }
624}
625
626
627void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
628                                                                                                  const ObjectContainer &objects) const
629{
630        switch (mObjectSpaceSubdivisionType)
631        {
632        case KD_BASED_OBJ_SUBDIV:
633                {
634                        ExportOspTree(exporter, objects);
635                        break;
636                }
637        case BV_BASED_OBJ_SUBDIV:
638                {
639                        ExportBvHierarchy(exporter, objects);
640                        break;
641                }
642        default:
643                break;
644        }
645}
646
647
648void HierarchyManager::ExportBvHierarchy(Exporter *exporter,
649                                                                                 const ObjectContainer &objects) const
650{
651        exporter->SetWireframe();
652        exporter->ExportBvHierarchy(*mBvHierarchy, 0);
653}
654
655
656void HierarchyManager::ExportOspTree(Exporter *exporter,
657                                                                         const ObjectContainer &objects) const
658{
659        if (0) exporter->ExportGeometry(objects);
660                       
661        exporter->SetWireframe();
662        exporter->ExportOspTree(*mOspTree, 0);
663}
664
665
666void HierarchyStatistics::Print(ostream &app) const
667{
668        app << "=========== Hierarchy statistics ===============\n";
669
670        app << setprecision(4);
671
672        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
673       
674        app << "#N_RTIME  ( Repair time [s] )\n" << repairTime * 1e-3f << " \n";
675
676        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
677
678        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
679
680        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
681
682        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
683       
684        app << "========== END OF Hierarchy statistics ==========\n";
685}
686
687
688}
Note: See TracBrowser for help on using the repository browser.