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

Revision 1308, 15.3 KB checked in by mattausch, 18 years ago (diff)

changed hierarchy construction: up to a certain level view space split is taken
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        mMinDepthForObjectSpaceSubdivion = -1;
105
106        Debug << "******** Hierachy Manager Parameters ***********" << endl;
107        Debug << "max leaves: " << mTermMaxLeaves << endl;
108        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
109        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
110}
111
112
113HierarchyManager::~HierarchyManager()
114{
115        DEL_PTR(mOspTree);
116        //DEL_PTR(mVspTree);
117        DEL_PTR(mBvHierarchy);
118}
119
120
121void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
122{
123        mVspTree->SetViewCellsManager(vcm);
124
125        if (mOspTree)
126                mOspTree->SetViewCellsManager(vcm);
127        if (mBvHierarchy)
128                mBvHierarchy->SetViewCellsManager(vcm);
129}
130
131
132void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
133{
134        mVspTree->SetViewCellsTree(vcTree);
135}
136
137
138SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
139{
140        SubdivisionCandidate *splitCandidate = mTQueue.Top();
141        mTQueue.Pop();
142
143        return splitCandidate;
144}
145
146
147void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
148{
149        const float costDecr = tData.GetRenderCostDecrease();
150
151        switch (mObjectSpaceSubdivisionType)
152        {
153        case KD_BASED_OBJ_SUBDIV:
154                AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
155                                                        costDecr,
156                                                        mTotalCost
157                                                        );
158                break;
159        case BV_BASED_OBJ_SUBDIV:
160                AddSubdivisionStats(mBvHierarchy->mBvhStats.Leaves() + mVspTree->mVspStats.Leaves(),
161                                                        costDecr,
162                                                        mTotalCost
163                                                        );
164                break;
165        default:
166                AddSubdivisionStats(mVspTree->mVspStats.Leaves(),
167                                                        costDecr,
168                                                        mTotalCost
169                                                        );
170                break;
171        }
172}
173
174
175void HierarchyManager::AddSubdivisionStats(const int splits,
176                                                                                   const float renderCostDecr,
177                                                                                   const float totalRenderCost)
178{
179        mSubdivisionStats
180                        << "#Splits\n" << splits << endl
181                        << "#RenderCostDecrease\n" << renderCostDecr << endl
182                        << "#TotalRenderCost\n" << totalRenderCost << endl;
183                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
184}
185
186
187bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
188{
189        return (0
190                || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
191                //|| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
192                ||      candidate->GlobalTerminationCriteriaMet()
193                );
194}
195
196
197void HierarchyManager::Construct(const VssRayContainer &sampleRays,
198                                                                const ObjectContainer &objects,
199                                                                AxisAlignedBox3 *forcedViewSpace)
200{
201       
202        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
203
204        mHierarchyStats.Reset();
205        mHierarchyStats.Start();
206
207        // start with view space subdivison: prepare vsp tree for traversal
208        SubdivisionCandidate *vsc =
209                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
210        mTQueue.Push(vsc);
211
212        mTotalCost = (float)objects.size();
213        Debug << "setting total cost to " << mTotalCost << endl;
214
215        const long startTime = GetTime();       
216        cout << "Constructing view space / object space tree ... \n";
217       
218        // process object space candidates
219        RunConstruction();
220       
221        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
222        mVspTree->mVspStats.Stop();
223}
224
225
226void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
227                                                                                                         const ObjectContainer &objects)
228{
229        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
230        {
231                PrepareOspTree(sampleRays, objects);
232        }
233        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
234        {
235                PrepareBvHierarchy(sampleRays, objects);
236        }
237}
238
239
240void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
241                                                                                  const ObjectContainer &objects)
242
243{
244        cout << "starting bv hierarchy construction ... " << endl;
245
246        mBvHierarchy->CreateRoot(objects);
247
248        // compute first candidate
249        SubdivisionCandidate *sc =
250                mBvHierarchy->PrepareConstruction(sampleRays, objects);
251
252        mTotalCost = mBvHierarchy->mTotalCost;
253        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
254
255    mTQueue.Push(sc);
256}
257
258
259void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
260                                                                          const ObjectContainer &objects)
261{
262        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
263
264        cout << "starting osp tree construction ... " << endl;
265
266        // start with one big kd cell - all objects can be seen from everywhere
267        // note: only true for view space = object space
268
269        // compute first candidate
270        SubdivisionCandidate *osc =
271                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
272
273        mTotalCost = mOspTree->mTotalCost;
274        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
275       
276    mTQueue.Push(osc);
277}
278
279
280bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc)
281{
282        const bool globalTerminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
283        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
284
285        if (vspSplit)
286        {
287                VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
288
289                if (n->IsLeaf()) // local or global termination criteria failed
290                        return false;
291        }
292        else
293        {
294                if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
295                {
296                        KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
297
298                        if (n->IsLeaf()) // local or global termination criteria failed
299                                return false;
300                }
301                else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
302                {
303                        BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
304
305                        if (n->IsLeaf()) // local or global termination criteria failed
306                                return false;
307                }
308        }
309        return true;//!globalTerminationCriteriaMet;
310}
311
312
313bool HierarchyManager::StartObjectSpaceSubdivision() const
314{
315        const bool constructAfterViewSpace = (mConstructionType == 1) && mTQueue.Empty();
316
317        return
318                NO_OBJ_SUBDIV &&
319                ((mMinDepthForObjectSpaceSubdivion < 0/*mVspTree->mVspStats.mMaxDepth*/) || constructAfterViewSpace);
320}
321
322
323void HierarchyManager::RunConstruction()
324{
325        mHierarchyStats.nodes = 0;
326        mGlobalCostMisses = 0;
327
328        // use objects for evaluating vsp tree construction
329        const int savedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
330        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
331
332        //const bool repairQueue = false;
333        const bool repairQueue = true;
334
335        do
336        {
337                // use objects for evaluating vsp tree construction until a certain depth
338                if (StartObjectSpaceSubdivision())
339                {
340                        mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
341                        //PrepareObjectSpaceSubdivision();
342                }
343
344                mCurrentCandidate = NextSubdivisionCandidate();   
345                mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();
346
347                // cost ratio of cost decrease / totalCost
348                const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;
349
350                //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
351                if (costRatio < mTermMinGlobalCostRatio)
352                {
353                        ++ mGlobalCostMisses;
354                }
355
356                //-- subdivide leaf node
357                if (ApplySubdivisionCandidate(mCurrentCandidate))
358                {
359                        mHierarchyStats.nodes += 2;
360
361                        // subdivision successful
362                        EvalSubdivisionStats(*mCurrentCandidate);
363               
364                        // reevaluate candidates affected by the split for view space splits,
365                        // this would be object space splits and other way round
366                        if (repairQueue) RepairQueue();
367                }       
368                DEL_PTR(mCurrentCandidate);
369        }
370        while (!FinishedConstruction());
371
372        mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
373}
374
375
376bool HierarchyManager::FinishedConstruction() const
377{
378        return mTQueue.Empty();
379}
380
381
382void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
383{
384        switch (mObjectSpaceSubdivisionType)
385        {
386        case KD_BASED_OBJ_SUBDIV:
387                {
388                        OspTree::OspSubdivisionCandidate *sc =
389                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
390
391                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
392                        break;
393                }
394        case BV_BASED_OBJ_SUBDIV:
395                {
396                        BvHierarchy::BvhSubdivisionCandidate *sc =
397                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
398
399                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
400                        break;
401                }
402        default:
403                break;
404        }
405}
406
407
408void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
409{
410        VspTree::VspSubdivisionCandidate *sc =
411                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
412
413        mVspTree->CollectDirtyCandidates(sc, dirtyList);
414}
415
416
417void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
418{
419        // we have either a object space or view space split
420        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
421        {
422                CollectViewSpaceDirtyList(dirtyList);
423        }
424        else // object space split
425        {
426                CollectObjectSpaceDirtyList(dirtyList);
427        }
428}
429
430
431void HierarchyManager::RepairQueue()
432{
433        // for each update of the view space partition:
434        // the candidates from object space partition which
435        // have been afected by the view space split (the kd split candidates
436        // which saw the view cell which was split) must be reevaluated
437        // (maybe not locally, just reinsert them into the queue)
438        //
439        // vice versa for the view cells
440        // for each update of the object space partition
441        // reevaluate split candidate for view cells which saw the split kd cell
442        //
443        // the priority queue update can be solved by implementing a binary heap
444        // (explicit data structure, binary tree)
445        // *) inserting and removal is efficient
446        // *) search is not efficient => store queue position with each
447        // split candidate
448
449        // collect list of "dirty" candidates
450        vector<SubdivisionCandidate *> dirtyList;
451        CollectDirtyCandidates(dirtyList);
452        Debug << "collected " << (int)dirtyList.size() << " candidates for reevaluation" << endl;
453
454        //-- reevaluate the dirty list
455        vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();
456       
457        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
458        {
459                SubdivisionCandidate* sc = *sit;
460                const float rcd = sc->GetRenderCostDecrease();
461               
462                mTQueue.Erase(sc); // erase from queue
463                sc->EvalPriority(); // reevaluate
464               
465                /*
466                Debug << "candidate " << sc << " reevaluated\n"
467                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
468                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;*/
469                if (0)
470                {
471                        const float rcDiff =  rcd - sc->GetRenderCostDecrease();
472                        mTotalCost += rcDiff;
473                }
474                mTQueue.Push(sc); // reinsert
475        }
476}
477
478
479void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
480{
481        // the type of the view cells hierarchy
482        switch (mObjectSpaceSubdivisionType)
483        {
484        case KD_BASED_OBJ_SUBDIV:
485                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
486                mOspTree->Export(stream);
487                stream << endl << "</ObjectSpaceHierarchy>" << endl;
488                break;         
489        case BV_BASED_OBJ_SUBDIV:
490                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
491                mBvHierarchy->Export(stream);
492                stream << endl << "</ObjectSpaceHierarchy>" << endl;
493                break;
494        }
495}
496
497
498bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
499                                                                          const Vector3 &hitPoint,
500                                                                          ViewCell *vc,
501                                                                          const float pdf,
502                                                                          float &contribution) const
503{
504        if (!obj) return false;
505
506        switch (mObjectSpaceSubdivisionType)
507        {
508        case NO_OBJ_SUBDIV:
509                // potentially visible objects
510                return vc->AddPvsSample(obj, pdf, contribution);
511        case KD_BASED_OBJ_SUBDIV:
512                {
513                        // potentially visible kd cells
514                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
515                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
516                }
517        case BV_BASED_OBJ_SUBDIV:
518                {
519                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
520                        return mBvHierarchy->AddLeafToPvs(leaf, vc, pdf, contribution);
521                }
522        default:
523                return false;
524        }
525}
526
527
528void HierarchyManager::PrintObjectSpaceHierarchyStatistics(ofstream &stream) const
529{
530        switch (mObjectSpaceSubdivisionType)
531        {
532        case KD_BASED_OBJ_SUBDIV:
533                {
534                        stream << mOspTree->GetStatistics();
535                        break;
536                }
537        case BV_BASED_OBJ_SUBDIV:
538                {
539                        stream << mBvHierarchy->GetStatistics();
540                        break;
541                }
542        default:
543                break;
544        }
545}
546
547
548void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
549                                                                                                  const ObjectContainer &objects) const
550{
551        switch (mObjectSpaceSubdivisionType)
552        {
553        case KD_BASED_OBJ_SUBDIV:
554                {
555                        ExportOspTree(exporter, objects);
556                        break;
557                }
558        case BV_BASED_OBJ_SUBDIV:
559                {
560                        ExportBvHierarchy(exporter, objects);
561                        break;
562                }
563        default:
564                break;
565        }
566}
567
568
569void HierarchyManager::ExportBvHierarchy(Exporter *exporter,
570                                                                                 const ObjectContainer &objects) const
571{
572        exporter->SetWireframe();
573        exporter->ExportBvHierarchy(*mBvHierarchy, 0);
574}
575
576
577void HierarchyManager::ExportOspTree(Exporter *exporter,
578                                                                         const ObjectContainer &objects) const
579{
580        if (0) exporter->ExportGeometry(objects);
581                       
582        exporter->SetWireframe();
583        exporter->ExportOspTree(*mOspTree, 0);
584}
585
586
587}
Note: See TracBrowser for help on using the repository browser.