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

Revision 1548, 27.6 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "ViewCell.h"
6#include "Plane3.h"
7#include "HierarchyManager.h"
8#include "Mesh.h"
9#include "common.h"
10#include "Environment.h"
11#include "Polygon3.h"
12#include "Ray.h"
13#include "AxisAlignedBox3.h"
14#include "Exporter.h"
15#include "Plane3.h"
16#include "ViewCellsManager.h"
17#include "Beam.h"
18#include "KdTree.h"
19#include "IntersectableWrapper.h"
20#include "VspTree.h"
21#include "OspTree.h"
22#include "BvHierarchy.h"
23
24
25namespace GtpVisibilityPreprocessor {
26
27
28#define USE_FIXEDPOINT_T 0
29
30
31/*******************************************************************/
32/*              class HierarchyManager implementation              */
33/*******************************************************************/
34
35
36HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
37mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
38mOspTree(NULL),
39mBvHierarchy(NULL)
40{
41        switch(mObjectSpaceSubdivisionType)
42        {
43        case KD_BASED_OBJ_SUBDIV:
44                mOspTree = new OspTree();
45                mOspTree->mVspTree = mVspTree;
46                mOspTree->mHierarchyManager = this;
47                break;
48        case BV_BASED_OBJ_SUBDIV:
49        mBvHierarchy = new BvHierarchy();
50                mBvHierarchy->mHierarchyManager = this;
51                break;
52        default:
53                break;
54        }
55
56        // hierarchy manager links view space partition and object space partition
57        mVspTree = new VspTree();
58        mVspTree->mHierarchyManager = this;
59       
60        ParseEnvironment();
61}
62
63
64HierarchyManager::HierarchyManager(KdTree *kdTree):
65mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
66mBvHierarchy(NULL)
67{
68        mOspTree = new OspTree(*kdTree);
69        mOspTree->mVspTree = mVspTree;
70
71        mVspTree = new VspTree();
72        mVspTree->mHierarchyManager = this;
73
74        ParseEnvironment();
75}
76
77
78void HierarchyManager::ParseEnvironment()
79{
80        char subdivisionStatsLog[100];
81        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
82                subdivisionStatsLog);
83        mSubdivisionStats.open(subdivisionStatsLog);
84
85        Environment::GetSingleton()->GetFloatValue(
86                "Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
87        Environment::GetSingleton()->GetIntValue(
88                "Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
89
90        Environment::GetSingleton()->GetBoolValue(
91                "Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
92
93        Environment::GetSingleton()->GetIntValue(
94                "Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
95
96        Environment::GetSingleton()->GetIntValue(
97                "Hierarchy.Construction.type", mConstructionType);
98
99        Environment::GetSingleton()->GetIntValue(
100                "Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
101
102        Environment::GetSingleton()->GetIntValue(
103                "Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
104       
105        Environment::GetSingleton()->GetBoolValue(
106                "Hierarchy.Construction.repairQueue", mRepairQueue);
107
108        Environment::GetSingleton()->GetBoolValue(
109                "Hierarchy.Construction.useMultiLevelConstruction", mUseMultiLevelConstruction);
110
111         mUseMultiLevelConstruction;
112        Debug << "******** Hierachy Manager Parameters ***********" << endl;
113        Debug << "max leaves: " << mTermMaxLeaves << endl;
114        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
115        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
116        Debug << "construction type: " << mConstructionType << endl;
117        Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
118        Debug << "repair queue: " << mRepairQueue << endl;
119        Debug << endl;
120}
121
122
123HierarchyManager::~HierarchyManager()
124{
125        DEL_PTR(mOspTree);
126        DEL_PTR(mVspTree);
127        DEL_PTR(mBvHierarchy);
128}
129
130
131int HierarchyManager::GetObjectSpaceSubdivisionType() const
132{
133        return mObjectSpaceSubdivisionType;
134}
135
136
137int HierarchyManager::GetViewSpaceSubdivisionType() const
138{
139        return mViewSpaceSubdivisionType;
140}
141
142
143void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
144{
145        mVspTree->SetViewCellsManager(vcm);
146
147        if (mOspTree)
148                mOspTree->SetViewCellsManager(vcm);
149        else if (mBvHierarchy)
150                mBvHierarchy->SetViewCellsManager(vcm);
151}
152
153
154void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
155{
156        mVspTree->SetViewCellsTree(vcTree);
157}
158
159
160VspTree *HierarchyManager::GetVspTree()
161{
162        return mVspTree;
163}
164
165
166AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
167{
168        return mVspTree->mBoundingBox;
169}
170
171
172AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
173{
174        switch (mObjectSpaceSubdivisionType)
175        {
176        case KD_BASED_OBJ_SUBDIV:
177                return mOspTree->mBoundingBox;
178        case BV_BASED_OBJ_SUBDIV:
179                return mBvHierarchy->mBoundingBox;
180        default:
181                // empty box
182                return AxisAlignedBox3();
183        }
184}
185
186
187SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
188{
189        SubdivisionCandidate *splitCandidate = mTQueue.Top();
190        mTQueue.Pop();
191
192        return splitCandidate;
193}
194
195
196void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
197{
198        const float costDecr = tData.GetRenderCostDecrease();
199
200        switch (mObjectSpaceSubdivisionType)
201        {
202        case KD_BASED_OBJ_SUBDIV:
203                AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
204                                                        costDecr,
205                                                        mTotalCost
206                                                        );
207                break;
208        case BV_BASED_OBJ_SUBDIV:
209                AddSubdivisionStats(mBvHierarchy->mBvhStats.Leaves() + mVspTree->mVspStats.Leaves(),
210                                                        costDecr,
211                                                        mTotalCost
212                                                        );
213                break;
214        default:
215                AddSubdivisionStats(mVspTree->mVspStats.Leaves(),
216                                                        costDecr,
217                                                        mTotalCost
218                                                        );
219                break;
220        }
221}
222
223
224void HierarchyManager::AddSubdivisionStats(const int splits,
225                                                                                   const float renderCostDecr,
226                                                                                   const float totalRenderCost)
227{
228        mSubdivisionStats
229                        << "#Splits\n" << splits << endl
230                        << "#RenderCostDecrease\n" << renderCostDecr << endl
231                        << "#TotalRenderCost\n" << totalRenderCost << endl;
232                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
233}
234
235
236bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
237{
238        const bool terminationCriteriaMet =
239                (0
240                || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
241                || (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
242                || (candidate->GlobalTerminationCriteriaMet())
243                );
244
245        if (0 && terminationCriteriaMet)
246        {
247                Debug << "hierarchy global termination criteria met:" << endl;
248                Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
249                Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
250        }
251        return terminationCriteriaMet;
252}
253
254
255void HierarchyManager::Construct(const VssRayContainer &sampleRays,
256                                                                 const ObjectContainer &objects,
257                                                                 AxisAlignedBox3 *forcedViewSpace)
258{
259        if (mUseMultiLevelConstruction)
260        {
261                ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
262        }
263        else
264        {
265                ConstructInterleaved(sampleRays, objects, forcedViewSpace);
266        }
267}
268
269
270void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
271                                                                                        const ObjectContainer &objects,
272                                                                                        AxisAlignedBox3 *forcedViewSpace)
273{
274        mHierarchyStats.Reset();
275        mHierarchyStats.Start();
276        mHierarchyStats.nodes = 2; // two nodes for view space and object space
277
278        mTotalCost = (float)objects.size();
279        Debug << "setting total cost to " << mTotalCost << endl;
280
281        const long startTime = GetTime();
282        cout << "Constructing view space / object space tree ... \n";
283       
284        // compute view space bounding box
285        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
286
287        // use objects for evaluating vsp tree construction in the first levels
288        // of the subdivision
289        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
290        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
291
292        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
293        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
294
295        // start with view space subdivison: prepare vsp tree for traversal
296        if (StartViewSpaceSubdivision())
297        {
298                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
299                PrepareViewSpaceSubdivision(sampleRays, objects);
300        }
301       
302        // start object space subdivision immediately?
303        if (StartObjectSpaceSubdivision())
304        {
305                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
306                PrepareObjectSpaceSubdivision(sampleRays, objects);
307        }
308
309        // process object space candidates
310        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
311       
312        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
313
314#if _DEBUG
315        cout << "view space: " << GetViewSpaceBox() << endl;
316        cout << "object space:  " << GetObjectSpaceBox() << endl;
317#endif
318
319        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
320        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
321
322        mHierarchyStats.Stop();
323        mVspTree->mVspStats.Stop();
324        FinishObjectSpaceSubdivision(objects);
325}
326
327
328void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
329                                                                                                   const ObjectContainer &objects)
330{
331        cout << "\nstarting view space hierarchy construction ... " << endl;
332         // hack: reset global cost misses
333        mHierarchyStats.mGlobalCostMisses = 0;
334
335        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
336        SubdivisionCandidate *vsc =
337                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
338
339        mTotalCost = mVspTree->mTotalCost;
340        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
341
342        mTQueue.Push(vsc);
343}
344
345
346void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
347                                                                                                         const ObjectContainer &objects)
348{
349        mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses
350
351        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
352        {
353                PrepareOspTree(sampleRays, objects);
354        }
355        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
356        {
357                PrepareBvHierarchy(sampleRays, objects);
358        }
359}
360
361
362void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
363                                                                                  const ObjectContainer &objects)
364
365{
366        const long startTime = GetTime();
367
368        cout << "preparing bv hierarchy construction ... " << endl;
369       
370        // compute first candidate
371        SubdivisionCandidate *sc =
372                mBvHierarchy->PrepareConstruction(sampleRays, objects);
373
374        mTotalCost = mBvHierarchy->mTotalCost;
375        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
376
377    mTQueue.Push(sc);
378        cout << "finished bv hierarchy preparation in "
379                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
380}
381
382
383void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
384                                                                          const ObjectContainer &objects)
385{
386        cout << "starting osp tree construction ... " << endl;
387
388        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
389
390        // start with one big kd cell - all objects can be seen from everywhere
391        // note: only true for view space = object space
392
393        // compute first candidate
394        SubdivisionCandidate *osc =
395                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
396
397        mTotalCost = mOspTree->mTotalCost;
398        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
399       
400    mTQueue.Push(osc);
401}
402
403
404bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc)
405{
406        const bool globalTerminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
407        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
408
409        if (!globalTerminationCriteriaMet)
410        {
411                // cost ratio of cost decrease / totalCost
412                const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;
413                //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
414       
415                if (costRatio < mTermMinGlobalCostRatio)
416                {
417                        ++ mHierarchyStats.mGlobalCostMisses;
418                }
419
420                mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();
421        }
422
423        if (vspSplit)
424        {
425                VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
426
427                if (n->IsLeaf()) // local or global termination criteria failed
428                        return false;
429        }
430        else
431        {
432                if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
433                {
434                        KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
435                        // local or global termination criteria failed
436                        if (n->IsLeaf())
437                                return false;
438                }
439                else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
440                {
441                        BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
442                        // local or global termination criteria failed
443                        if (n->IsLeaf())
444                                return false;
445                }
446        }
447
448        return true;
449}
450
451
452int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
453{
454        int maxDepth = 0;
455
456        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
457        {
458                maxDepth = mOspTree->mOspStats.maxDepth;
459        }
460        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
461        {
462                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
463        }
464
465        return maxDepth;
466}
467
468
469bool HierarchyManager::StartObjectSpaceSubdivision() const
470{
471        // view space construction already started
472        if (ObjectSpaceSubdivisionConstructed())
473                return false;
474
475        // start immediately with object space subdivision?
476        if (mStartWithObjectSpace)
477                return true;
478
479        // is the queue empty again?
480        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
481                return true;
482
483        // has the depth for subdivision been reached?
484        return
485                ((mConstructionType == INTERLEAVED) &&
486                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
487}
488
489
490bool HierarchyManager::StartViewSpaceSubdivision() const
491{
492        // view space construction already started
493        if (ViewSpaceSubdivisionConstructed())
494                return false;
495
496        // start immediately with view space subdivision?
497        if (!mStartWithObjectSpace)
498                return true;
499
500        // is the queue empty again?
501        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
502                return true;
503
504        // has the depth for subdivision been reached?
505        return
506                ((mConstructionType == INTERLEAVED) &&
507                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
508}
509
510
511void HierarchyManager::RunConstruction(const bool repairQueue,
512                                                                           const VssRayContainer &sampleRays,
513                                                                           const ObjectContainer &objects,
514                                                                           AxisAlignedBox3 *forcedViewSpace)
515{
516        int i = 0;
517        while (!FinishedConstruction())
518        {
519                mCurrentCandidate = NextSubdivisionCandidate();   
520                       
521                ///////////////////
522                //-- subdivide leaf node
523
524                if (ApplySubdivisionCandidate(mCurrentCandidate))
525                {
526                        cout << mCurrentCandidate->Type() << " ";
527                        if (0) cout << "subdividing candidate " << ++ i << " of type "
528                                                << mCurrentCandidate->Type() << endl;
529                        mHierarchyStats.nodes += 2;
530
531                        // subdivision successful
532                        EvalSubdivisionStats(*mCurrentCandidate);
533               
534                        // reevaluate candidates affected by the split for view space splits,
535                        // this would be object space splits and other way round
536                        if (repairQueue) RepairQueue();
537                }
538
539                // we use objects for evaluating vsp tree construction until
540                // a certain depth once a certain depth existiert ...
541                if (StartObjectSpaceSubdivision())
542                {
543                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
544
545                        cout << "\nstarting object space subdivision at depth "
546                                 << mVspTree->mVspStats.maxDepth << " ("
547                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl;
548
549                        PrepareObjectSpaceSubdivision(sampleRays, objects);
550
551                        cout << "reseting queue ... ";
552                        ResetQueue();
553                        cout << "finished" << endl;
554                }
555
556                if (StartViewSpaceSubdivision())
557                {
558                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
559
560                        cout << "\nstarting view space subdivision at depth "
561                                 << GetObjectSpaceSubdivisionDepth() << " ("
562                                 << mMinDepthForViewSpaceSubdivion << ") " << endl;
563
564                        PrepareViewSpaceSubdivision(sampleRays, objects);
565
566                        cout << "reseting queue ... ";
567                        ResetQueue();
568                        cout << "finished" << endl;
569                }
570
571                DEL_PTR(mCurrentCandidate);
572        }
573}
574
575
576
577void HierarchyManager::RunConstruction(const bool repairQueue)
578{
579        int i = 0;
580        while (!FinishedConstruction())
581        {
582                mCurrentCandidate = NextSubdivisionCandidate();   
583                       
584                ///////////////////
585                //-- subdivide leaf node
586
587                if (ApplySubdivisionCandidate(mCurrentCandidate))
588                {
589                        cout << mCurrentCandidate->Type() << " ";
590                        if (0) cout << "subdividing candidate " << ++ i << " of type "
591                                                << mCurrentCandidate->Type() << endl;
592                        mHierarchyStats.nodes += 2;
593
594                        // subdivision successful
595                        EvalSubdivisionStats(*mCurrentCandidate);
596               
597                        // reevaluate candidates affected by the split for view space splits,
598                        // this would be object space splits and other way round
599                        if (repairQueue) RepairQueue();
600                }
601
602                DEL_PTR(mCurrentCandidate);
603        }
604}
605
606
607void HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
608                                                                                                   const ObjectContainer &objects)
609{
610        switch (mObjectSpaceSubdivisionType)
611        {
612        case BV_BASED_OBJ_SUBDIV:
613        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
614                cout << "\nresetting bv hierarchy" << endl;
615                mHierarchyStats.nodes -= mBvHierarchy->mBvhStats.nodes;
616#if 0   
617                DEL_PTR(mBvHierarchy);
618                mBvHierarchy = new BvHierarchy();
619                mBvHierarchy->mHierarchyManager = this;
620
621                PrepareObjectSpaceSubdivision(sampleRays, objects);
622#else
623                mBvHierarchy->Reset(sampleRays, objects);
624#endif
625                break;
626        case KD_BASED_OBJ_SUBDIV:
627                // TODO
628                break;
629        default:
630                break;
631        }
632}
633
634
635void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
636                                                                                   const ObjectContainer &objects,
637                                                                                   AxisAlignedBox3 *forcedViewSpace)
638{
639        mHierarchyStats.Reset();
640        mHierarchyStats.Start();
641
642        mHierarchyStats.nodes = 2;
643       
644
645        mTotalCost = (float)objects.size();
646        Debug << "setting total cost to " << mTotalCost << endl;
647
648        const long startTime = GetTime();
649        cout << "Constructing view space / object space tree ... \n";
650       
651        // compute view space bounding box
652        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
653
654        // use sah for evaluating object space construction for the first run
655        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
656        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
657
658        // start with object space subdivision
659        PrepareObjectSpaceSubdivision(sampleRays, objects);
660       
661        // process object space candidates
662        RunConstruction(false);
663
664        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
665
666        const int limit = 2;
667        for (int i = 0; i < limit; ++ i)
668        {
669        // again run object space subdivision on the view cells
670                ResetObjectSpaceSubdivision(sampleRays, objects);
671       
672                // process object space candidates
673                RunConstruction(false);
674
675                 /////////////////
676                // now do view space subdivison using the current object space partition
677//              ResetViewSpaceSubdivision(sampleRays, objects);
678       
679                // process view space candidates
680                RunConstruction(false);
681       
682                cout << "íteration " << i << " of " << limit << " finished" << endl;
683        }
684       
685        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
686
687#if _DEBUG
688        cout << "view space: " << GetViewSpaceBox() << endl;
689        cout << "object space:  " << GetObjectSpaceBox() << endl;
690#endif
691
692        mHierarchyStats.Stop();
693        mVspTree->mVspStats.Stop();
694        FinishObjectSpaceSubdivision(objects);
695}
696
697
698bool HierarchyManager::FinishedConstruction() const
699{
700        return mTQueue.Empty();
701}
702
703
704bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
705{
706        switch (mObjectSpaceSubdivisionType)
707        {
708        case KD_BASED_OBJ_SUBDIV:
709                return mOspTree && mOspTree->GetRoot();
710        case BV_BASED_OBJ_SUBDIV:
711                return mBvHierarchy && mBvHierarchy->GetRoot();
712        default:
713        return false;
714        }
715}
716
717
718bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
719{
720        return mVspTree && mVspTree->GetRoot();
721}
722
723
724void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
725{
726        switch (mObjectSpaceSubdivisionType)
727        {
728        case KD_BASED_OBJ_SUBDIV:
729                {
730                        OspTree::OspSubdivisionCandidate *sc =
731                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
732
733                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
734                        break;
735                }
736        case BV_BASED_OBJ_SUBDIV:
737                {
738                        BvHierarchy::BvhSubdivisionCandidate *sc =
739                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
740
741                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
742                        break;
743                }
744        default:
745                break;
746        }
747}
748
749
750void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
751{
752        VspTree::VspSubdivisionCandidate *sc =
753                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
754
755        mVspTree->CollectDirtyCandidates(sc, dirtyList);
756}
757
758
759void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
760{
761        // we have either a object space or view space split
762        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
763        {
764                CollectViewSpaceDirtyList(dirtyList);
765        }
766        else // object space split
767        {
768                CollectObjectSpaceDirtyList(dirtyList);
769        }
770}
771
772
773void HierarchyManager::RepairQueue()
774{
775        // for each update of the view space partition:
776        // the candidates from object space partition which
777        // have been afected by the view space split (the kd split candidates
778        // which saw the view cell which was split) must be reevaluated
779        // (maybe not locally, just reinsert them into the queue)
780        //
781        // vice versa for the view cells
782        // for each update of the object space partition
783        // reevaluate split candidate for view cells which saw the split kd cell
784        //
785        // the priority queue update can be solved by implementing a binary heap
786        // (explicit data structure, binary tree)
787        // *) inserting and removal is efficient
788        // *) search is not efficient => store queue position with each
789        // split candidate
790
791        // collect list of "dirty" candidates
792        long startTime = GetTime();
793   
794        vector<SubdivisionCandidate *> dirtyList;
795        CollectDirtyCandidates(dirtyList);
796        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
797       
798        /////////////////////////////////
799        //-- reevaluate the dirty list
800
801        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
802       
803        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
804        {
805                SubdivisionCandidate* sc = *sit;
806                const float rcd = sc->GetRenderCostDecrease();
807               
808                mTQueue.Erase(sc); // erase from queue
809                sc->EvalPriority(); // reevaluate
810               
811                /*
812                Debug << "candidate " << sc << " reevaluated\n"
813                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
814                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;*/
815                if (0)
816                {
817                        const float rcDiff =  rcd - sc->GetRenderCostDecrease();
818                        mTotalCost += rcDiff;
819                }
820                mTQueue.Push(sc); // reinsert
821        }
822
823        long endTime = GetTime();
824        Real timeDiff = TimeDiff(startTime, endTime);
825
826        mHierarchyStats.repairTime += timeDiff;
827
828        if (0) cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
829}
830
831
832void HierarchyManager::ResetQueue()
833{
834        SubdivisionCandidateContainer mCandidateBuffer;
835
836        // remove from queue
837        while (!mTQueue.Empty())
838        {
839                SubdivisionCandidate *candidate = NextSubdivisionCandidate();
840                candidate->EvalPriority(); // reevaluate
841                cout << ".";
842                mCandidateBuffer.push_back(candidate);
843        }
844
845        // put back into queue
846        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
847    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
848        {cout << ":";
849                mTQueue.Push(*sit);
850        }
851}
852
853
854void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
855{
856        // the type of the view cells hierarchy
857        switch (mObjectSpaceSubdivisionType)
858        {
859        case KD_BASED_OBJ_SUBDIV:
860                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
861                mOspTree->Export(stream);
862                stream << endl << "</ObjectSpaceHierarchy>" << endl;
863                break;         
864        case BV_BASED_OBJ_SUBDIV:
865                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
866                mBvHierarchy->Export(stream);
867                stream << endl << "</ObjectSpaceHierarchy>" << endl;
868                break;
869        }
870}
871
872
873bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
874                                                                          const Vector3 &hitPoint,
875                                                                          ViewCell *vc,
876                                                                          const float pdf,
877                                                                          float &contribution) const
878{
879        if (!obj) return false;
880
881        switch (mObjectSpaceSubdivisionType)
882        {
883        case NO_OBJ_SUBDIV:
884                {
885                        // potentially visible objects
886                        return vc->AddPvsSample(obj, pdf, contribution);
887                }
888        case KD_BASED_OBJ_SUBDIV:
889                {
890                        // potentially visible kd cells
891                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
892                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
893                }
894        case BV_BASED_OBJ_SUBDIV:
895                {
896                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
897                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
898                       
899                        return vc->AddPvsSample(bvhObj, pdf, contribution);
900                }
901        default:
902                return false;
903        }
904}
905
906
907void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
908{
909        stream << mHierarchyStats << endl;
910        stream << "\nview space:" << endl << endl;
911        stream << mVspTree->GetStatistics() << endl;
912        stream << "\nobject space:" << endl << endl;
913
914        switch (mObjectSpaceSubdivisionType)
915        {
916        case KD_BASED_OBJ_SUBDIV:
917                {
918                        stream << mOspTree->GetStatistics() << endl;
919                        break;
920                }
921        case BV_BASED_OBJ_SUBDIV:
922                {
923                        stream << mBvHierarchy->GetStatistics() << endl;
924                        break;
925                }
926        default:
927                break;
928        }
929}
930
931
932void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
933                                                                                                  const ObjectContainer &objects,
934                                                                                                  const AxisAlignedBox3 *bbox,
935                                                                                                  const bool exportBounds) const
936{
937        switch (mObjectSpaceSubdivisionType)
938        {
939        case KD_BASED_OBJ_SUBDIV:
940                {
941                        ExportOspTree(exporter, objects);
942                        break;
943                }
944        case BV_BASED_OBJ_SUBDIV:
945                {
946                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
947                        break;
948                }
949        default:
950                break;
951        }
952}
953
954
955void HierarchyManager::ExportOspTree(Exporter *exporter,
956                                                                         const ObjectContainer &objects) const
957{
958        if (0) exporter->ExportGeometry(objects);
959                       
960        exporter->SetWireframe();
961        exporter->ExportOspTree(*mOspTree, 0);
962}
963
964
965Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
966                                                                                                  const bool isTermination) const
967{
968
969        Intersectable *obj;
970        Vector3 pt;
971        KdNode *node;
972
973        ray.GetSampleData(isTermination, pt, &obj, &node);
974       
975        if (!obj) return NULL;
976
977        switch (mObjectSpaceSubdivisionType)
978        {
979        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
980                {
981                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
982                        return mOspTree->GetOrCreateKdIntersectable(leaf);
983                }
984        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
985                {
986                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
987                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
988                }
989        default:
990                return obj;
991        }
992}
993
994
995void HierarchyStatistics::Print(ostream &app) const
996{
997        app << "=========== Hierarchy statistics ===============\n";
998
999        app << setprecision(4);
1000
1001        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1002       
1003        app << "#N_RTIME  ( Repair time [s] )\n" << repairTime * 1e-3f << " \n";
1004
1005        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
1006
1007        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1008
1009        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1010
1011        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
1012
1013        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1014       
1015        app << "========== END OF Hierarchy statistics ==========\n";
1016}
1017
1018
1019static void RemoveRayRefs(const ObjectContainer &objects)
1020{
1021        ObjectContainer::const_iterator oit, oit_end = objects.end();
1022        for (oit = objects.begin(); oit != oit_end; ++ oit)
1023        {
1024                (*oit)->mVssRays.clear();
1025        }
1026}
1027
1028
1029void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
1030{
1031        switch (mObjectSpaceSubdivisionType)
1032        {
1033        case KD_BASED_OBJ_SUBDIV:
1034                {
1035                        mOspTree->mOspStats.Stop();
1036                        break;
1037                }
1038        case BV_BASED_OBJ_SUBDIV:
1039                {
1040                        mBvHierarchy->mBvhStats.Stop();
1041                        RemoveRayRefs(objects);
1042                        break;
1043                }
1044        default:
1045                break;
1046        }
1047}
1048
1049}
Note: See TracBrowser for help on using the repository browser.