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

Revision 1636, 36.4 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        char subdivisionStatsLog[100];
112        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
113        mSubdivisionStats.open(subdivisionStatsLog);
114
115        Environment::GetSingleton()->GetBoolValue(
116                "Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);
117
118        Debug << "******** Hierachy Manager Parameters ***********" << endl;
119        Debug << "max leaves: " << mTermMaxLeaves << endl;
120        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
121        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
122        Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
123        Debug << "repair queue: " << mRepairQueue << endl;
124        Debug << "number of multilevels: " << mNumMultiLevels << endl;
125        Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
126
127        switch (mConstructionType)
128        {
129        case 0:
130                Debug << "construction type: sequential" << endl;
131                break;
132        case 1:
133                Debug << "construction type: interleaved" << endl;
134                break;
135        case 2:
136                Debug << "construction type: gradient" << endl;
137                break;
138        case 3:
139                Debug << "construction type: multilevel" << endl;
140                break;
141        default:
142                Debug << "construction type " << mConstructionType << " unknown" << endl;
143                break;
144        }
145
146        //Debug << "min render cost " << mMinRenderCostDecrease << endl;
147        Debug << endl;
148}
149
150
151HierarchyManager::~HierarchyManager()
152{
153        DEL_PTR(mOspTree);
154        DEL_PTR(mVspTree);
155        DEL_PTR(mBvHierarchy);
156}
157
158
159int HierarchyManager::GetObjectSpaceSubdivisionType() const
160{
161        return mObjectSpaceSubdivisionType;
162}
163
164
165int HierarchyManager::GetViewSpaceSubdivisionType() const
166{
167        return mViewSpaceSubdivisionType;
168}
169
170
171void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
172{
173        mVspTree->SetViewCellsManager(vcm);
174
175        if (mOspTree)
176        {
177                mOspTree->SetViewCellsManager(vcm);
178        }
179        else if (mBvHierarchy)
180        {
181                mBvHierarchy->SetViewCellsManager(vcm);
182        }
183}
184
185
186void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
187{
188        mVspTree->SetViewCellsTree(vcTree);
189}
190
191
192VspTree *HierarchyManager::GetVspTree()
193{
194        return mVspTree;
195}
196
197/*
198AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
199{
200        return mVspTree->mBoundingBox;
201}*/
202
203
204AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
205{
206        switch (mObjectSpaceSubdivisionType)
207        {
208        case KD_BASED_OBJ_SUBDIV:
209                return mOspTree->mBoundingBox;
210        case BV_BASED_OBJ_SUBDIV:
211                return mBvHierarchy->mBoundingBox;
212        default:
213                // hack: empty box
214                return AxisAlignedBox3();
215        }
216}
217
218
219SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue)
220{
221        SubdivisionCandidate *splitCandidate = splitQueue.Top();
222        splitQueue.Pop();
223
224        return splitCandidate;
225}
226
227
228void HierarchyManager::EvalSubdivisionStats()
229{
230        //cout << "pvs entries " << mHierarchyStats.pvsEntries << endl;
231        AddSubdivisionStats(mHierarchyStats.Leaves(),
232                                                mHierarchyStats.mRenderCostDecrease,
233                                                mHierarchyStats.mTotalCost,
234                                                mHierarchyStats.mPvsEntries,
235                                                mHierarchyStats.mMemory,
236                                                1.0f / (mHierarchyStats.mTotalCost * mHierarchyStats.mMemory)
237                                                );
238}
239
240
241void HierarchyManager::AddSubdivisionStats(const int splits,
242                                                                                   const float renderCostDecr,
243                                                                                   const float totalRenderCost,
244                                                                                   const int pvsEntries,
245                                                                                   const int memory,
246                                                                                   const float renderCostPerStorage)
247{
248        mSubdivisionStats
249                        << "#Splits\n" << splits << endl
250                        << "#RenderCostDecrease\n" << renderCostDecr << endl
251                        << "#TotalEntriesInPvs\n" << pvsEntries << endl
252                        << "#TotalRenderCost\n" << totalRenderCost << endl
253                        << "#Memory\n" << memory << endl
254                        << "#RcPerMb\n" << renderCostPerStorage << endl;
255}
256
257
258bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
259{
260        const bool terminationCriteriaMet =
261                (0
262                || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
263                //|| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
264                || (candidate->GlobalTerminationCriteriaMet())
265                //|| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
266                );
267
268#if _DEBUG
269        if (terminationCriteriaMet)
270        {
271                Debug << "hierarchy global termination criteria met:" << endl;
272                Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
273                Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
274        }
275#endif
276
277        return terminationCriteriaMet;
278}
279
280
281void HierarchyManager::Construct(const VssRayContainer &sampleRays,
282                                                                 const ObjectContainer &objects,
283                                                                 AxisAlignedBox3 *forcedViewSpace)
284{
285        switch (mConstructionType)
286        {
287        case MULTILEVEL:
288                ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
289                break;
290        case INTERLEAVED:
291        case SEQUENTIAL:
292                ConstructInterleaved(sampleRays, objects, forcedViewSpace);
293                break;
294        case GRADIENT:
295                ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
296                break;
297        default:
298                break;
299        }
300}
301
302
303void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,                                                                                       
304                                                                                                                const ObjectContainer &objects,
305                                                                                                                AxisAlignedBox3 *forcedViewSpace)
306{
307        mHierarchyStats.Reset();
308        mHierarchyStats.Start();
309       
310        mHierarchyStats.mNodes = 2;
311       
312        mHierarchyStats.mTotalCost = (float)objects.size();
313        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
314
315        const long startTime = GetTime();
316        cout << "Constructing view space / object space tree ... \n";
317       
318        // compute view space bounding box
319        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
320
321        SplitQueue objectSpaceQueue;
322        SplitQueue viewSpaceQueue;
323
324        // use sah for evaluating osp tree construction
325        // in the first iteration of the subdivision
326        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
327        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
328
329        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
330
331        // number of initial splits
332        int minSteps = 200;
333        float renderCostDecr = Limits::Infinity;
334
335        SubdivisionCandidate *osc =
336                PrepareObjectSpaceSubdivision(sampleRays, objects);
337       
338        objectSpaceQueue.Push(osc);
339
340        /////////////////////////
341        // calulcate initial object space splits
342       
343        SubdivisionCandidateContainer dirtyVspList;
344
345        // subdivide object space first
346        // for first round, use sah splits. Once view space partition
347        // has started, use render cost heuristics instead
348        const int ospSteps =
349                RunConstruction(objectSpaceQueue, dirtyVspList, renderCostDecr, minSteps);
350
351        cout << ospSteps << " object space partition steps taken" << endl;
352
353        SubdivisionCandidate *vsc =
354                        PrepareViewSpaceSubdivision(sampleRays, objects);
355
356        viewSpaceQueue.Push(vsc);
357
358        // view space subdivision was constructed
359        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
360
361        // don't terminate on max steps
362        //maxSteps = mTermMaxLeaves;
363
364        // This method subdivides view space / object space
365        // in order to converge to some optimal cost for this partition
366        // start with object space partiton
367        // then optimizate view space partition for the current osp
368        // and vice versa until iteration depth is reached.
369
370        while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
371        {
372                // should view or object space be subdivided further?
373                if (viewSpaceQueue.Empty() ||
374                        (!objectSpaceQueue.Empty() &&
375                        (objectSpaceQueue.Top()->GetPriority() > viewSpaceQueue.Top()->GetPriority())))
376                {
377                        // use splits of one kind until rendercost slope is reached
378                        //renderCostDecr = mHierarchyStats.mRenderCostDecrease;
379                       
380                        // lower number of minsteps: this should be solved
381                        // with render cost decrease from now
382                        //minSteps = 5;
383
384                        // dirtied view space candidates
385                        SubdivisionCandidateContainer dirtyVspList;
386
387                        // subdivide object space first
388                        // for first round, use sah splits. Once view space partition
389                        // has started, use render cost heuristics instead
390                        const int ospSteps =
391                                RunConstruction(objectSpaceQueue, dirtyVspList, renderCostDecr, minSteps);
392
393                        cout << ospSteps << " object space partition steps taken" << endl;
394               
395                        // object space subdivision constructed
396                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
397
398                        /// Repair split queue
399                        cout << "repairing queue ... " << endl;
400                        RepairQueue(dirtyVspList, viewSpaceQueue, true);
401                        cout << "repaired " << dirtyVspList.size() << " candidates" << endl;
402                }
403                else
404                {
405                        // use splits of one kind until rendercost slope is reached
406                //      renderCostDecr = mHierarchyStats.mRenderCostDecrease;
407
408                        /////////////////
409                        // subdivide view space with respect to the objects
410
411                        SubdivisionCandidateContainer dirtyOspList;
412
413                        // process view space candidates
414                        const int vspSteps =
415                                RunConstruction(viewSpaceQueue, dirtyOspList, renderCostDecr, minSteps);
416
417                        cout << vspSteps << " view space partition steps taken" << endl;
418
419                        // view space subdivision constructed
420                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
421
422                        /// Repair split queue
423                        cout << "repairing queue ... " << endl;
424                        RepairQueue(dirtyOspList, objectSpaceQueue, true);
425                        cout << "repaired " << dirtyOspList.size() << " candidates" << endl;
426                }
427        }
428
429        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
430
431        mHierarchyStats.Stop();
432        mVspTree->mVspStats.Stop();
433
434        FinishObjectSpaceSubdivision(objects);
435}
436
437
438void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
439                                                                                        const ObjectContainer &objects,
440                                                                                        AxisAlignedBox3 *forcedViewSpace)
441{
442        mHierarchyStats.Reset();
443        mHierarchyStats.Start();
444        mHierarchyStats.mNodes = 2; // two nodes for view space and object space
445
446        mHierarchyStats.mTotalCost = (float)objects.size();
447        mHierarchyStats.mRenderCostDecrease = 0;
448
449        EvalSubdivisionStats();
450        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
451
452        const long startTime = GetTime();
453        cout << "Constructing view space / object space tree ... \n";
454       
455        // compute view space bounding box
456        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
457
458        // use objects for evaluating vsp tree construction in the
459        // first levels of the subdivision
460        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
461        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
462
463        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
464        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
465
466        // create just one view cell
467        SubdivisionCandidate *vspSc =
468                PrepareViewSpaceSubdivision(sampleRays, objects);
469
470        // start view space subdivison immediately?
471        if (StartViewSpaceSubdivision())
472        {
473                // prepare vsp tree for traversal
474                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
475                mTQueue.Push(vspSc);
476        }
477       
478        // start object space subdivision immediately?
479        if (StartObjectSpaceSubdivision())
480        {
481                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
482                SubdivisionCandidate *ospSc =
483                        PrepareObjectSpaceSubdivision(sampleRays, objects);
484                mTQueue.Push(ospSc);
485        }
486
487        // begin subdivision
488        RunConstruction(mRepairQueue,
489                                        sampleRays,
490                                        objects,
491                                        forcedViewSpace,//
492                                        vspSc);
493       
494        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
495
496        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
497        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
498
499        mHierarchyStats.Stop();
500        mVspTree->mVspStats.Stop();
501        FinishObjectSpaceSubdivision(objects);
502}
503
504
505SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
506                                                                                                                                        const ObjectContainer &objects)
507{
508        cout << "\npreparing view space hierarchy construction ... " << endl;
509
510        // hack: reset global cost misses
511        mHierarchyStats.mGlobalCostMisses = 0;
512
513        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
514        SubdivisionCandidate *vsc =
515                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
516
517        mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
518        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
519
520        return vsc;
521}
522
523
524SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
525                                                                                                                                          const ObjectContainer &objects)
526{
527        // hack: reset global cost misses
528        mHierarchyStats.mGlobalCostMisses = 0;
529
530        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
531        {
532                return PrepareOspTree(sampleRays, objects);
533        }
534        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
535        {
536                return PrepareBvHierarchy(sampleRays, objects);
537        }
538       
539        return NULL;
540}
541
542
543SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
544                                                                                                                   const ObjectContainer &objects)
545{
546        const long startTime = GetTime();
547
548        cout << "preparing bv hierarchy construction ... " << endl;
549       
550        // compute first candidate
551        SubdivisionCandidate *sc =
552                mBvHierarchy->PrepareConstruction(sampleRays, objects);
553
554        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
555        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
556
557        cout << "finished bv hierarchy preparation in "
558                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
559         
560        return sc;
561}
562
563
564SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
565                                                                                                           const ObjectContainer &objects)
566{
567        cout << "starting osp tree construction ... " << endl;
568
569        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
570
571        // start with one big kd cell - all objects can be seen from everywhere
572        // note: only true for view space = object space
573
574        // compute first candidate
575        SubdivisionCandidate *osc =
576                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
577
578        mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
579        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
580       
581    return osc;
582}
583
584
585bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
586                                                                                                 SplitQueue &splitQueue,
587                                                                                                 const bool repairQueue)
588{
589        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
590
591        const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
592
593        if (!success) // split was not taken
594        {
595                return false;
596        }
597
598        ///////////////
599        //-- split was successful => update stats and queue
600
601    // cost ratio of cost decrease / totalCost
602        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
603        //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
604       
605        if (costRatio < mTermMinGlobalCostRatio)
606        {
607                ++ mHierarchyStats.mGlobalCostMisses;
608        }
609       
610        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
611       
612        cout << sc->Type() << " ";
613               
614        // update stats
615        mHierarchyStats.mNodes += 2;
616       
617        const int pvsEntries = sc->GetPvsEntriesIncr();
618        mHierarchyStats.mPvsEntries += pvsEntries;
619       
620        //cout << "pvs entries: " << pvsEntries << " " << mHierarchyStats.pvsEntries << endl;
621        mHierarchyStats.mMemory += 0; // TODO
622        mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
623
624        // subdivision successful
625        EvalSubdivisionStats();
626               
627        if (repairQueue)
628        {
629                // reevaluate candidates affected by the split for view space splits,
630                // this would be object space splits and other way round
631                vector<SubdivisionCandidate *> dirtyList;
632                sc->CollectDirtyCandidates(dirtyList, false);
633
634                RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
635        }
636
637        return true;
638}
639
640
641int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
642{
643        int maxDepth = 0;
644
645        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
646        {
647                maxDepth = mOspTree->mOspStats.maxDepth;
648        }
649        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
650        {
651                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
652        }
653
654        return maxDepth;
655}
656
657
658bool HierarchyManager::StartObjectSpaceSubdivision() const
659{
660        // view space construction already started
661        if (ObjectSpaceSubdivisionConstructed())
662                return false;
663
664        // start immediately with object space subdivision?
665        if (mStartWithObjectSpace)
666                return true;
667
668        // is the queue empty again?
669        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
670                return true;
671
672        // has the depth for subdivision been reached?
673        return
674                ((mConstructionType == INTERLEAVED) &&
675                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
676}
677
678
679bool HierarchyManager::StartViewSpaceSubdivision() const
680{
681        // view space construction already started
682        if (ViewSpaceSubdivisionConstructed())
683                return false;
684
685        // start immediately with view space subdivision?
686        if (!mStartWithObjectSpace)
687                return true;
688
689        // is the queue empty again?
690        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
691                return true;
692
693        // has the depth for subdivision been reached?
694        return
695                ((mConstructionType == INTERLEAVED) &&
696                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
697}
698
699
700void HierarchyManager::RunConstruction(const bool repairQueue,
701                                                                           const VssRayContainer &sampleRays,
702                                                                           const ObjectContainer &objects,
703                                                                           AxisAlignedBox3 *forcedViewSpace,
704                                                                           SubdivisionCandidate *firstVsp)
705{
706        while (!FinishedConstruction())
707        {
708                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
709       
710                ///////////////////
711                //-- subdivide leaf node
712
713                ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
714                               
715                // we use objects for evaluating vsp tree construction until
716                // a certain depth once a certain depth existiert ...
717                if (StartObjectSpaceSubdivision())
718                {
719                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
720
721                        cout << "\nstarting object space subdivision at depth "
722                                 << mVspTree->mVspStats.maxDepth << " ("
723                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl;
724
725                        SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
726                        mTQueue.Push(ospSc);
727
728                        cout << "reseting queue ... ";
729                        ResetQueue();
730                        cout << "finished" << endl;
731                }
732
733                if (StartViewSpaceSubdivision())
734                {
735                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
736
737                        cout << "\nstarting view space subdivision at depth "
738                                 << GetObjectSpaceSubdivisionDepth() << " ("
739                                 << mMinDepthForViewSpaceSubdivion << ") " << endl;
740
741                        //SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
742                        mTQueue.Push(firstVsp);
743
744                        cout << "reseting queue ... ";
745                        ResetQueue();
746                        cout << "finished" << endl;
747                }
748
749                DEL_PTR(sc);
750        }
751}
752
753
754void HierarchyManager::RunConstruction(const bool repairQueue)
755{
756        //int i = 0;
757        // main loop
758        while (!FinishedConstruction())
759        {
760                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);   
761                       
762                ////////
763                //-- subdivide leaf node of either type
764                ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
765                DEL_PTR(sc);
766        }
767}
768
769
770int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
771                                                                          SubdivisionCandidateContainer &dirtyCandidates,
772                                                                          const float minRenderCostDecr,
773                                                                          const int minSteps)
774{
775        int steps = 0;
776        SubdivisionCandidate::NewMail();
777
778        // main loop
779        while (!splitQueue.Empty())
780        {
781                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
782               
783                // minimum slope reached
784                if ((sc->GetRenderCostDecrease() < minRenderCostDecr) &&
785                        !(steps < minSteps))
786                        break;
787
788                ////////
789                //-- subdivide leaf node of either type
790
791                const bool repairQueue = false;
792                const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
793
794                if (success)
795                {
796                        sc->CollectDirtyCandidates(dirtyCandidates, true);
797                        //cout << "collected " << dirtyCandidates.size() << "dirty candidates" << endl;
798                        ++ steps;
799                }
800        }
801
802        return steps;
803}
804
805
806SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
807                                                                                                                                        const ObjectContainer &objects)
808{       
809        // no object space subdivision yet
810        if (!ObjectSpaceSubdivisionConstructed())
811        {
812                return PrepareObjectSpaceSubdivision(sampleRays, objects);
813        }
814
815        SubdivisionCandidate *firstCandidate;
816
817        // object space partition constructed => reconstruct
818        switch (mObjectSpaceSubdivisionType)
819        {
820        case BV_BASED_OBJ_SUBDIV:
821                {
822                        cout << "\nreseting bv hierarchy" << endl;
823                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
824       
825                        firstCandidate = mBvHierarchy->Reset(sampleRays, objects);
826               
827                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
828
829                        mHierarchyStats.mNodes = 2;
830                        mHierarchyStats.mPvsEntries = 0;
831                        mHierarchyStats.mRenderCostDecrease = 0;
832
833                        // evaluate stats before first subdivision
834                        EvalSubdivisionStats();
835                }
836                break;
837
838        case KD_BASED_OBJ_SUBDIV:
839                // TODO
840        default:
841                firstCandidate = NULL;
842                break;
843        }
844
845        return firstCandidate;
846}
847
848
849SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
850                                                                                                                                  const ObjectContainer &objects)
851{
852        ViewCellsManager *vc = mVspTree->mViewCellsManager;
853
854        // HACK: rather not destroy vsp tree
855        DEL_PTR(mVspTree);
856        mVspTree = new VspTree();
857        mVspTree->mHierarchyManager = this;
858        mVspTree->mViewCellsManager = vc;
859
860        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
861       
862        mHierarchyStats.mNodes = 2;
863        mHierarchyStats.mPvsEntries = 0;
864        mHierarchyStats.mRenderCostDecrease = 0;
865
866        EvalSubdivisionStats();
867
868        return vsc;
869}
870
871
872void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                   
873                                                                                   const ObjectContainer &objects,
874                                                                                   AxisAlignedBox3 *forcedViewSpace)
875{
876        mHierarchyStats.Reset();
877        mHierarchyStats.Start();
878        mHierarchyStats.mNodes = 2;
879       
880        mHierarchyStats.mTotalCost = (float)objects.size();
881        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
882
883        const long startTime = GetTime();
884        cout << "Constructing view space / object space tree ... \n";
885       
886        // compute view space bounding box
887        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
888
889        // use sah for evaluating osp tree construction
890        // in the first iteration of the subdivision
891       
892        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
893        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
894       
895        // first view cell
896        SubdivisionCandidate *vspVc = PrepareViewSpaceSubdivision(sampleRays, objects);
897
898        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
899        //mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
900
901        const int limit = mNumMultiLevels;
902        int i = 0;
903
904        // This method subdivides view space / object space
905        // in order to converge to some optimal cost for this partition
906        // start with object space partiton
907        // then optimizate view space partition for the current osp
908        // and vice versa until iteration depth is reached.
909        while (1)
910        {
911                char subdivisionStatsLog[100];
912                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
913                mSubdivisionStats.open(subdivisionStatsLog);
914
915                // subdivide object space first
916                ResetObjectSpaceSubdivision(sampleRays, objects);
917
918                // process object space candidates
919                RunConstruction(false);
920
921                // object space subdivision constructed
922                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
923
924                cout << "iteration " << i << " of " << limit << " finished" << endl;
925
926                mSubdivisionStats.close();
927
928                if ((i ++) >= limit)
929                        break;
930
931                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
932                mSubdivisionStats.open(subdivisionStatsLog);
933
934                /////////////////
935                // subdivide view space with respect to the objects
936
937                if (!ViewSpaceSubdivisionConstructed())
938                {
939                        mTQueue.Push(vspVc);
940                       
941                        // view space subdivision constructed
942                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
943                }
944                else
945                {
946                        ResetViewSpaceSubdivision(sampleRays, objects);
947                }
948
949                // process view space candidates
950                RunConstruction(false);
951
952                cout << "iteration " << i << " of " << limit << " finished" << endl;
953
954                mSubdivisionStats.close();
955
956                if ((i ++) >= limit)
957                        break;
958        }
959       
960        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
961
962/*#if _DEBUG
963        cout << "view space: " << GetViewSpaceBox() << endl;
964        cout << "object space:  " << GetObjectSpaceBox() << endl;
965#endif*/
966
967        mHierarchyStats.Stop();
968        mVspTree->mVspStats.Stop();
969        FinishObjectSpaceSubdivision(objects);
970}
971
972
973bool HierarchyManager::FinishedConstruction() const
974{
975        return mTQueue.Empty();
976}
977
978
979bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
980{
981        switch (mObjectSpaceSubdivisionType)
982        {
983        case KD_BASED_OBJ_SUBDIV:
984                return mOspTree && mOspTree->GetRoot();
985        case BV_BASED_OBJ_SUBDIV:
986                return mBvHierarchy && mBvHierarchy->GetRoot();
987        default:
988                return false;
989        }
990}
991
992
993bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
994{
995        return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
996        //return mVspTree && mVspTree->GetRoot();
997}
998
999
1000void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
1001                                                                                          SubdivisionCandidateContainer &dirtyList)
1002{
1003        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
1004        SubdivisionCandidate::NewMail();
1005
1006        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
1007        {
1008                (*sit)->CollectDirtyCandidates(dirtyList, true);
1009        }
1010}
1011
1012
1013void HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
1014                                                                   SplitQueue &splitQueue,
1015                                                                   const bool recomputeSplitPlaneOnRepair)
1016{
1017        // for each update of the view space partition:
1018        // the candidates from object space partition which
1019        // have been afected by the view space split (the kd split candidates
1020        // which saw the view cell which was split) must be reevaluated
1021        // (maybe not locally, just reinsert them into the queue)
1022        //
1023        // vice versa for the view cells
1024        // for each update of the object space partition
1025        // reevaluate split candidate for view cells which saw the split kd cell
1026        //
1027        // the priority queue update can be solved by implementing a binary heap
1028        // (explicit data structure, binary tree)
1029        // *) inserting and removal is efficient
1030        // *) search is not efficient => store queue position with each
1031        // split candidate
1032
1033        // collect list of "dirty" candidates
1034        const long startTime = GetTime();
1035        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
1036       
1037
1038        /////////////////////////////////
1039        //-- reevaluate the dirty list
1040
1041        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
1042       
1043        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
1044        {
1045                SubdivisionCandidate* sc = *sit;
1046                const float rcd = sc->GetRenderCostDecrease();
1047               
1048                splitQueue.Erase(sc); // erase from queue
1049                sc->EvalPriority(recomputeSplitPlaneOnRepair); // reevaluate
1050               
1051#ifdef _DEBUG
1052                Debug << "candidate " << sc << " reevaluated\n"
1053                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
1054                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
1055#endif 
1056                splitQueue.Push(sc); // reinsert
1057                cout << ".";
1058        }
1059
1060        const long endTime = GetTime();
1061        const Real timeDiff = TimeDiff(startTime, endTime);
1062
1063        mHierarchyStats.mRepairTime += timeDiff;
1064
1065        if (0) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
1066}
1067
1068
1069void HierarchyManager::ResetQueue()
1070{
1071        SubdivisionCandidateContainer mCandidateBuffer;
1072
1073        // remove from queue
1074        while (!mTQueue.Empty())
1075        {
1076                SubdivisionCandidate *candidate = NextSubdivisionCandidate(mTQueue);
1077                 // reevaluate local split plane and priority
1078                candidate->EvalPriority();
1079                cout << ".";
1080                mCandidateBuffer.push_back(candidate);
1081        }
1082
1083        // put back into queue
1084        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
1085    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
1086        {
1087                mTQueue.Push(*sit);
1088        }
1089}
1090
1091
1092void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
1093{
1094        // the type of the view cells hierarchy
1095        switch (mObjectSpaceSubdivisionType)
1096        {
1097        case KD_BASED_OBJ_SUBDIV:
1098                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
1099                mOspTree->Export(stream);
1100                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1101                break;         
1102        case BV_BASED_OBJ_SUBDIV:
1103                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
1104                mBvHierarchy->Export(stream);
1105                stream << endl << "</ObjectSpaceHierarchy>" << endl;
1106                break;
1107        }
1108}
1109
1110
1111bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
1112                                                                          const Vector3 &hitPoint,
1113                                                                          ViewCell *vc,
1114                                                                          const float pdf,
1115                                                                          float &contribution) const
1116{
1117        if (!obj) return false;
1118
1119        switch (mObjectSpaceSubdivisionType)
1120        {
1121        case NO_OBJ_SUBDIV:
1122                {
1123                        // potentially visible objects
1124                        return vc->AddPvsSample(obj, pdf, contribution);
1125                }
1126        case KD_BASED_OBJ_SUBDIV:
1127                {
1128                        // potentially visible kd cells
1129                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
1130                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
1131                }
1132        case BV_BASED_OBJ_SUBDIV:
1133                {
1134                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1135                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1136                       
1137                        return vc->AddPvsSample(bvhObj, pdf, contribution);
1138                }
1139        default:
1140                return false;
1141        }
1142}
1143
1144
1145void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
1146{
1147        stream << mHierarchyStats << endl;
1148        stream << "\nview space:" << endl << endl;
1149        stream << mVspTree->GetStatistics() << endl;
1150        stream << "\nobject space:" << endl << endl;
1151
1152        switch (mObjectSpaceSubdivisionType)
1153        {
1154        case KD_BASED_OBJ_SUBDIV:
1155                {
1156                        stream << mOspTree->GetStatistics() << endl;
1157                        break;
1158                }
1159        case BV_BASED_OBJ_SUBDIV:
1160                {
1161                        stream << mBvHierarchy->GetStatistics() << endl;
1162                        break;
1163                }
1164        default:
1165                break;
1166        }
1167}
1168
1169
1170void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
1171                                                                                                  const ObjectContainer &objects,
1172                                                                                                  const AxisAlignedBox3 *bbox,
1173                                                                                                  const bool exportBounds) const
1174{
1175        switch (mObjectSpaceSubdivisionType)
1176        {
1177        case KD_BASED_OBJ_SUBDIV:
1178                {
1179                        ExportOspTree(exporter, objects);
1180                        break;
1181                }
1182        case BV_BASED_OBJ_SUBDIV:
1183                {
1184                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
1185                        break;
1186                }
1187        default:
1188                break;
1189        }
1190}
1191
1192
1193void HierarchyManager::ExportOspTree(Exporter *exporter,
1194                                                                         const ObjectContainer &objects) const
1195{
1196        if (0) exporter->ExportGeometry(objects);
1197                       
1198        exporter->SetWireframe();
1199        exporter->ExportOspTree(*mOspTree, 0);
1200}
1201
1202
1203Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1204                                                                                                  const bool isTermination) const
1205{
1206
1207        Intersectable *obj;
1208        Vector3 pt;
1209        KdNode *node;
1210
1211        ray.GetSampleData(isTermination, pt, &obj, &node);
1212       
1213        if (!obj) return NULL;
1214
1215        switch (mObjectSpaceSubdivisionType)
1216        {
1217        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1218                {
1219                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1220                        return mOspTree->GetOrCreateKdIntersectable(leaf);
1221                }
1222        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1223                {
1224                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1225                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1226                }
1227        default:
1228                return obj;
1229        }
1230}
1231
1232
1233void HierarchyStatistics::Print(ostream &app) const
1234{
1235        app << "=========== Hierarchy statistics ===============\n";
1236
1237        app << setprecision(4);
1238
1239        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1240       
1241        app << "#N_RTIME  ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1242
1243        app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1244
1245        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1246
1247        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1248
1249        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1250
1251        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1252       
1253        app << "========== END OF Hierarchy statistics ==========\n";
1254}
1255
1256
1257static void RemoveRayRefs(const ObjectContainer &objects)
1258{
1259        ObjectContainer::const_iterator oit, oit_end = objects.end();
1260        for (oit = objects.begin(); oit != oit_end; ++ oit)
1261        {
1262                (*oit)->mVssRays.clear();
1263        }
1264}
1265
1266
1267void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
1268{
1269        switch (mObjectSpaceSubdivisionType)
1270        {
1271        case KD_BASED_OBJ_SUBDIV:
1272                {
1273                        mOspTree->mOspStats.Stop();
1274                        break;
1275                }
1276        case BV_BASED_OBJ_SUBDIV:
1277                {
1278                        mBvHierarchy->mBvhStats.Stop();
1279                        RemoveRayRefs(objects);
1280                        break;
1281                }
1282        default:
1283                break;
1284        }
1285}
1286
1287
1288void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1289{
1290        stream << "<BoundingBoxes>" << endl;
1291           
1292        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1293        {
1294                KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1295
1296                int id = 0;
1297                for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1298                {
1299                        Intersectable *obj = (*kit).second;
1300                        const AxisAlignedBox3 box = obj->GetBox();
1301               
1302                        obj->SetId(id);
1303
1304                        stream << "<BoundingBox" << " id=\"" << id << "\""
1305                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1306                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1307                }
1308        }
1309        else
1310        {
1311                ObjectContainer::const_iterator oit, oit_end = objects.end();
1312
1313                for (oit = objects.begin(); oit != oit_end; ++ oit)
1314                {
1315                        const AxisAlignedBox3 box = (*oit)->GetBox();
1316               
1317                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1318                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1319                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1320                }
1321        }
1322               
1323        stream << "</BoundingBoxes>" << endl;
1324}
1325
1326}
Note: See TracBrowser for help on using the repository browser.