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

Revision 1522, 27.2 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        mHierarchyStats.Stop();
320        mVspTree->mVspStats.Stop();
321        FinishObjectSpaceSubdivision(objects);
322
323        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
324        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
325}
326
327
328void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
329                                                                                                   const ObjectContainer &objects)
330{
331        cout << "\nstarting view space hierarchy construction ... " << endl;
332
333        mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses
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                mBvHierarchy->CreateRoot(objects);
370
371        // compute first candidate
372        SubdivisionCandidate *sc =
373                mBvHierarchy->PrepareConstruction(sampleRays, objects);
374
375        mTotalCost = mBvHierarchy->mTotalCost;
376        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
377
378    mTQueue.Push(sc);
379        cout << "finished bv hierarchy preparation in " << 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 ObjectContainer &objects)
608{
609        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
610        cout << "\nresetting bv hierarchy" << endl;
611        mHierarchyStats.nodes -= mBvHierarchy->mBvhStats.nodes;
612       
613        DEL_PTR(mBvHierarchy);
614        mBvHierarchy = new BvHierarchy();
615        mBvHierarchy->mHierarchyManager = this;
616}
617
618
619void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
620                                                                                   const ObjectContainer &objects,
621                                                                                   AxisAlignedBox3 *forcedViewSpace)
622{
623        mHierarchyStats.Reset();
624        mHierarchyStats.Start();
625
626        mHierarchyStats.nodes = 2;
627       
628
629        mTotalCost = (float)objects.size();
630        Debug << "setting total cost to " << mTotalCost << endl;
631
632        const long startTime = GetTime();
633        cout << "Constructing view space / object space tree ... \n";
634       
635        // compute view space bounding box
636        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
637
638        // use sah for evaluating object space construction for the first run
639        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
640        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
641
642        // start with object space subdivision
643        PrepareObjectSpaceSubdivision(sampleRays, objects);
644       
645        // process object space candidates
646        RunConstruction(false);
647
648        /////////////////
649    // now do view space subdivison on the sah bvh nodes
650        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
651        PrepareViewSpaceSubdivision(sampleRays, objects);
652       
653        // process view space candidates
654        RunConstruction(false);
655       
656        // again run object space subdivision on the view cells
657        ResetObjectSpaceSubdivision(objects);
658        PrepareObjectSpaceSubdivision(sampleRays, objects);
659
660        // process object space candidates
661        RunConstruction(false);
662       
663        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
664
665#if _DEBUG
666        cout << "view space: " << GetViewSpaceBox() << endl;
667        cout << "object space:  " << GetObjectSpaceBox() << endl;
668#endif
669
670        mHierarchyStats.Stop();
671        mVspTree->mVspStats.Stop();
672        FinishObjectSpaceSubdivision(objects);
673}
674
675
676bool HierarchyManager::FinishedConstruction() const
677{
678        return mTQueue.Empty();
679}
680
681
682bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
683{
684        switch (mObjectSpaceSubdivisionType)
685        {
686        case KD_BASED_OBJ_SUBDIV:
687                return mOspTree && mOspTree->GetRoot();
688        case BV_BASED_OBJ_SUBDIV:
689                return mBvHierarchy && mBvHierarchy->GetRoot();
690        default:
691        return false;
692        }
693}
694
695
696bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
697{
698        return mVspTree && mVspTree->GetRoot();
699}
700
701
702void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
703{
704        switch (mObjectSpaceSubdivisionType)
705        {
706        case KD_BASED_OBJ_SUBDIV:
707                {
708                        OspTree::OspSubdivisionCandidate *sc =
709                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
710
711                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
712                        break;
713                }
714        case BV_BASED_OBJ_SUBDIV:
715                {
716                        BvHierarchy::BvhSubdivisionCandidate *sc =
717                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
718
719                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
720                        break;
721                }
722        default:
723                break;
724        }
725}
726
727
728void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
729{
730        VspTree::VspSubdivisionCandidate *sc =
731                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
732
733        mVspTree->CollectDirtyCandidates(sc, dirtyList);
734}
735
736
737void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
738{
739        // we have either a object space or view space split
740        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
741        {
742                CollectViewSpaceDirtyList(dirtyList);
743        }
744        else // object space split
745        {
746                CollectObjectSpaceDirtyList(dirtyList);
747        }
748}
749
750
751void HierarchyManager::RepairQueue()
752{
753        // for each update of the view space partition:
754        // the candidates from object space partition which
755        // have been afected by the view space split (the kd split candidates
756        // which saw the view cell which was split) must be reevaluated
757        // (maybe not locally, just reinsert them into the queue)
758        //
759        // vice versa for the view cells
760        // for each update of the object space partition
761        // reevaluate split candidate for view cells which saw the split kd cell
762        //
763        // the priority queue update can be solved by implementing a binary heap
764        // (explicit data structure, binary tree)
765        // *) inserting and removal is efficient
766        // *) search is not efficient => store queue position with each
767        // split candidate
768
769        // collect list of "dirty" candidates
770        long startTime = GetTime();
771   
772        vector<SubdivisionCandidate *> dirtyList;
773        CollectDirtyCandidates(dirtyList);
774        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
775       
776        /////////////////////////////////
777        //-- reevaluate the dirty list
778
779        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
780       
781        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
782        {
783                SubdivisionCandidate* sc = *sit;
784                const float rcd = sc->GetRenderCostDecrease();
785               
786                mTQueue.Erase(sc); // erase from queue
787                sc->EvalPriority(); // reevaluate
788               
789                /*
790                Debug << "candidate " << sc << " reevaluated\n"
791                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
792                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;*/
793                if (0)
794                {
795                        const float rcDiff =  rcd - sc->GetRenderCostDecrease();
796                        mTotalCost += rcDiff;
797                }
798                mTQueue.Push(sc); // reinsert
799        }
800
801        long endTime = GetTime();
802        Real timeDiff = TimeDiff(startTime, endTime);
803
804        mHierarchyStats.repairTime += timeDiff;
805
806        if (0) cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
807}
808
809
810void HierarchyManager::ResetQueue()
811{
812        SubdivisionCandidateContainer mCandidateBuffer;
813
814        // remove from queue
815        while (!mTQueue.Empty())
816        {
817                SubdivisionCandidate *candidate = NextSubdivisionCandidate();
818                candidate->EvalPriority(); // reevaluate
819                cout << ".";
820                mCandidateBuffer.push_back(candidate);
821        }
822
823        // put back into queue
824        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
825    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
826        {cout << ":";
827                mTQueue.Push(*sit);
828        }
829}
830
831
832void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
833{
834        // the type of the view cells hierarchy
835        switch (mObjectSpaceSubdivisionType)
836        {
837        case KD_BASED_OBJ_SUBDIV:
838                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
839                mOspTree->Export(stream);
840                stream << endl << "</ObjectSpaceHierarchy>" << endl;
841                break;         
842        case BV_BASED_OBJ_SUBDIV:
843                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
844                mBvHierarchy->Export(stream);
845                stream << endl << "</ObjectSpaceHierarchy>" << endl;
846                break;
847        }
848}
849
850
851bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
852                                                                          const Vector3 &hitPoint,
853                                                                          ViewCell *vc,
854                                                                          const float pdf,
855                                                                          float &contribution) const
856{
857        if (!obj) return false;
858
859        switch (mObjectSpaceSubdivisionType)
860        {
861        case NO_OBJ_SUBDIV:
862                {
863                        // potentially visible objects
864                        return vc->AddPvsSample(obj, pdf, contribution);
865                }
866        case KD_BASED_OBJ_SUBDIV:
867                {
868                        // potentially visible kd cells
869                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
870                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
871                }
872        case BV_BASED_OBJ_SUBDIV:
873                {
874                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
875                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
876                       
877                        return vc->AddPvsSample(bvhObj, pdf, contribution);
878                }
879        default:
880                return false;
881        }
882}
883
884
885void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
886{
887        stream << mHierarchyStats << endl;
888        stream << "\nview space:" << endl << endl;
889        stream << mVspTree->GetStatistics() << endl;
890        stream << "\nobject space:" << endl << endl;
891
892        switch (mObjectSpaceSubdivisionType)
893        {
894        case KD_BASED_OBJ_SUBDIV:
895                {
896                        stream << mOspTree->GetStatistics() << endl;
897                        break;
898                }
899        case BV_BASED_OBJ_SUBDIV:
900                {
901                        stream << mBvHierarchy->GetStatistics() << endl;
902                        break;
903                }
904        default:
905                break;
906        }
907}
908
909
910void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
911                                                                                                  const ObjectContainer &objects,
912                                                                                                  const AxisAlignedBox3 *bbox,
913                                                                                                  const bool exportBounds) const
914{
915        switch (mObjectSpaceSubdivisionType)
916        {
917        case KD_BASED_OBJ_SUBDIV:
918                {
919                        ExportOspTree(exporter, objects);
920                        break;
921                }
922        case BV_BASED_OBJ_SUBDIV:
923                {
924                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
925                        break;
926                }
927        default:
928                break;
929        }
930}
931
932
933void HierarchyManager::ExportOspTree(Exporter *exporter,
934                                                                         const ObjectContainer &objects) const
935{
936        if (0) exporter->ExportGeometry(objects);
937                       
938        exporter->SetWireframe();
939        exporter->ExportOspTree(*mOspTree, 0);
940}
941
942
943Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
944                                                                                                  const bool isTermination) const
945{
946
947        Intersectable *obj;
948        Vector3 pt;
949        KdNode *node;
950
951        ray.GetSampleData(isTermination, pt, &obj, &node);
952       
953        if (!obj) return NULL;
954
955        switch (mObjectSpaceSubdivisionType)
956        {
957        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
958                {
959                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
960                        return mOspTree->GetOrCreateKdIntersectable(leaf);
961                }
962        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
963                {
964                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
965                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
966                }
967        default:
968                return obj;
969        }
970}
971
972
973void HierarchyStatistics::Print(ostream &app) const
974{
975        app << "=========== Hierarchy statistics ===============\n";
976
977        app << setprecision(4);
978
979        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
980       
981        app << "#N_RTIME  ( Repair time [s] )\n" << repairTime * 1e-3f << " \n";
982
983        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
984
985        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
986
987        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
988
989        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
990
991        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
992       
993        app << "========== END OF Hierarchy statistics ==========\n";
994}
995
996
997static void RemoveRayRefs(const ObjectContainer &objects)
998{
999        ObjectContainer::const_iterator oit, oit_end = objects.end();
1000        for (oit = objects.begin(); oit != oit_end; ++ oit)
1001        {
1002                (*oit)->mVssRays.clear();
1003        }
1004}
1005
1006
1007void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
1008{
1009        switch (mObjectSpaceSubdivisionType)
1010        {
1011        case KD_BASED_OBJ_SUBDIV:
1012                {
1013                        mOspTree->mOspStats.Stop();
1014                        break;
1015                }
1016        case BV_BASED_OBJ_SUBDIV:
1017                {
1018                        mBvHierarchy->mBvhStats.Stop();
1019                        RemoveRayRefs(objects);
1020                        break;
1021                }
1022        default:
1023                break;
1024        }
1025}
1026
1027}
Note: See TracBrowser for help on using the repository browser.