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

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