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

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