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

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