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

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