source: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h @ 1920

Revision 1920, 17.8 KB checked in by mattausch, 18 years ago (diff)
Line 
1#ifndef _HierarchyManager_H__
2#define _HierarchyManager_H__
3
4#include <stack>
5
6#include "Mesh.h"
7#include "Containers.h"
8#include "Statistics.h"
9#include "VssRay.h"
10#include "RayInfo.h"
11#include "gzstream.h"
12#include "SubdivisionCandidate.h"
13
14
15
16namespace GtpVisibilityPreprocessor {
17
18class ViewCellLeaf;
19class OspTree;
20class VspTree;
21class Plane3;
22class AxisAlignedBox3;
23class Ray;
24class ViewCellsStatistics;
25class ViewCellsManager;
26class MergeCandidate;
27class Beam;
28class ViewCellsTree;
29class Environment;
30class VspInterior;
31class VspLeaf;
32class VspNode;
33class KdNode;
34class KdInterior;
35class KdLeaf;
36class OspTree;
37class KdIntersectable;
38class KdTree;
39class VspTree;
40class KdTreeStatistics;
41class BvHierarchy;
42class Exporter;
43class ViewCellsParseHandlers;
44
45
46#define COUNT_ORIGIN_OBJECTS 1
47#define USE_AVGRAYCONTRI 1
48
49
50/** View space / object space hierarchy statistics.
51*/
52class HierarchyStatistics: public StatisticsBase
53{
54public:
55        /// total number of entries in the pvs
56        int mPvsEntries;
57        /// storage cost in MB
58        float mMemory;
59        /// total number of nodes
60        int mNodes;
61        /// maximal reached depth
62        int mMaxDepth;
63        /// accumulated depth
64        int mAccumDepth;
65        /// time spent for queue repair
66        float mRepairTime;
67
68        // global cost ratio violations
69        int mGlobalCostMisses;
70        /// total cost of subdivision
71        float mTotalCost;
72        /// render cost decrease of subdivision
73        float mRenderCostDecrease;
74
75        // Constructor
76        HierarchyStatistics()
77        {
78                Reset();
79        }
80
81        int Nodes() const {return mNodes;}
82        int Interior() const { return mNodes / 2 - 1; }
83        int Leaves() const { return (mNodes / 2) + 1; }
84       
85        // TODO: computation wrong
86        double AvgDepth() const { return mAccumDepth / (double)Leaves();}
87
88        void Reset()
89        {
90                mGlobalCostMisses = 0;
91                mTotalCost = 0;
92                mRenderCostDecrease = 0;
93
94                mNodes = 0;
95                mMaxDepth = 0;
96                mAccumDepth = 0;
97                mRepairTime = 0;
98                mMemory = 0;
99                mPvsEntries = 0;
100        }
101
102        void Print(ostream &app) const;
103
104        friend ostream &operator<<(ostream &s, const HierarchyStatistics &stat)
105        {
106                stat.Print(s);
107                return s;
108        }
109};
110
111
112class HierarchySubdivisionStats
113{
114public:
115           
116        int mNumSplits;
117               
118        float mRenderCostDecrease;
119
120    float mTotalRenderCost;
121   
122        int mEntriesInPvs;
123   
124        float mMemoryCost;
125       
126        float mFullMemory;
127
128        int mViewSpaceSplits;
129
130        int mObjectSpaceSplits;
131
132        float mPriority;
133
134        float VspOspRatio() const { return (float)mViewSpaceSplits / (float)mObjectSpaceSplits; }
135
136        float FpsPerMb() const { return 1.0f / (mTotalRenderCost * mMemoryCost); }
137
138        HierarchySubdivisionStats() { Reset(); }
139
140        void Reset()
141        {
142                mNumSplits = 0;
143                mRenderCostDecrease = 0;
144                mTotalRenderCost = 0;
145                mEntriesInPvs = 0;
146                mMemoryCost = 0;
147                mFullMemory = 0;
148                mViewSpaceSplits = 0;
149                mObjectSpaceSplits = 0;
150                mPriority = 0;
151        }
152
153
154        void Print(ostream &app) const;
155
156        friend ostream &operator<<(ostream &s, const HierarchySubdivisionStats &stat)
157        {
158                stat.Print(s);
159                return s;
160        }
161};
162
163
164/** This class implements a structure holding two different hierarchies,
165        one for object space partitioning and one for view space partitioning.
166
167        The object space and the view space are subdivided using a cost heuristics.
168        If an object space split or a view space split is chosen is also evaluated
169        based on the heuristics.
170       
171        The view space heuristics is evaluated by weighting and adding the pvss of the back and
172        front node of each specific split. unlike for the standalone method vspbsp tree,
173        the pvs of an object would not be the pvs of single object but that of all objects
174        which are contained in the same leaf of the object subdivision. This could be done
175        by storing the pointer to the object space partition parent, which would allow access to all children.
176        Another possibility is to include traced kd-cells in the ray casing process.
177
178        Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object.
179        the contribution to an object to the pvs is the number of view cells it can be seen from.
180
181        @note
182        There is a potential efficiency problem involved in a sense that once a certain type
183        of split is chosen for view space / object space, the candidates for the next split of
184        object space / view space must be reevaluated.
185*/
186class HierarchyManager
187{
188public:
189        /** Constructor with the view space partition tree and
190                the object space hierarchy type as argument.
191        */
192        HierarchyManager(const int objectSpaceHierarchyType);
193        /** Hack: OspTree will copy the content from this kd tree.
194                Only view space hierarchy will be constructed.
195        */
196        HierarchyManager(KdTree *kdTree);
197
198        /** Deletes space partition and view space partition.
199        */
200        ~HierarchyManager();
201
202        /** Constructs the view space and object space subdivision from a given set of rays
203                and a set of objects.
204                @param sampleRays the set of sample rays the construction is based on
205                @param objects the set of objects
206        */
207        void Construct(
208                const VssRayContainer &sampleRays,
209                const ObjectContainer &objects,
210                AxisAlignedBox3 *forcedViewSpace);
211
212        enum
213        {
214                NO_OBJ_SUBDIV,
215                KD_BASED_OBJ_SUBDIV,
216                BV_BASED_OBJ_SUBDIV
217        };
218
219        enum
220        {
221                NO_VIEWSPACE_SUBDIV,
222                KD_BASED_VIEWSPACE_SUBDIV
223        };
224
225        /** The type of object space subdivison
226        */
227        int GetObjectSpaceSubdivisionType() const;     
228        /** The type of view space space subdivison
229        */
230        int GetViewSpaceSubdivisionType() const;
231        /** Sets a pointer to the view cells manager.
232        */             
233        void SetViewCellsManager(ViewCellsManager *vcm);
234        /** Sets a pointer to the view cells tree.
235        */
236        void SetViewCellsTree(ViewCellsTree *vcTree);
237        /** Exports the object hierarchy to disc.
238        */
239        void ExportObjectSpaceHierarchy(OUT_STREAM &stream);
240       
241        /** Print out statistics.
242        */
243        void PrintHierarchyStatistics(ostream &stream) const;
244
245        /** Returns the view space partition tree.
246        */
247        VspTree *GetVspTree();
248
249        /** Returns object space bounding box.
250        */
251        AxisAlignedBox3 GetObjectSpaceBox() const;
252
253        /** Exports object space hierarchy for visualization.
254        */
255        void ExportObjectSpaceHierarchy(Exporter *exporter,
256                                                                        const ObjectContainer &objects,
257                                                                        AxisAlignedBox3 *bbox,
258                                                                        const float maxRenderCost,
259                                                                        const bool exportBounds = true) const;
260
261        /** Returns intersectable pierced by this ray.
262        */
263        Intersectable *GetIntersectable(const VssRay &ray, const bool isTermination) const;
264 
265        Intersectable *GetIntersectable(Intersectable *obj, const Vector3 &point) const;
266
267        /** Export object space partition bounding boxes.
268        */
269        void ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects);
270
271        friend ostream &operator<<(ostream &s, const HierarchyManager &hm)
272        {
273                hm.PrintHierarchyStatistics(s);
274                return s;
275        }
276
277        HierarchyStatistics &GetHierarchyStats() { return mHierarchyStats; };
278
279        inline bool ConsiderMemory() const { return mConsiderMemory; }
280       
281        void EvaluateSubdivision(const VssRayContainer &sampleRays,                                                                                     
282                                                         const ObjectContainer &objects,
283                                                         const string &filename);
284
285        void EvaluateSubdivision2(ofstream &splitsStats,
286                                                          const int splitsStepSize,
287                                                          const bool useFilter,
288                                                          const bool useHisto,
289                                                          const int histoMem,
290                                                          const int pass);
291
292
293        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
294
295        int CompressObjectSpace();
296        void CreateUniqueObjectIds();
297
298        float EvalCorrectedPvs(const float pvsFront,
299                                                   const float totalPvs,
300                                                   const float avgRayContri) const;
301
302
303protected:
304
305        /** Returns true if the global termination criteria were met.
306        */
307        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;
308
309        /** Prepare construction of the hierarchies, set parameters, compute
310                first split candidates.
311        */
312        void PrepareObjectSpaceSubdivision(SplitQueue &tQueue,
313                                                                           const VssRayContainer &sampleRays,
314                                                                           const ObjectContainer &objects);
315
316
317        /** Create bounding box and root.
318        */
319        void InitialiseObjectSpaceSubdivision(const ObjectContainer &objects);
320
321        /** Returns memory usage of object space hierarchy.
322        */
323        float GetObjectSpaceMemUsage() const;
324
325
326        //////////////////////////////
327        // the main loop
328
329        /** This is for interleaved construction / sequential construction.
330        */
331        void RunConstruction(const bool repairQueue,
332                                                 const VssRayContainer &sampleRays,
333                                                 const ObjectContainer &objects,
334                                                 AxisAlignedBox3 *forcedViewSpace);
335       
336        /** This is for interleaved construction using some objects
337                and some view space splits.
338        */
339        int RunConstruction(SplitQueue &splitQueue,
340                                                SubdivisionCandidateContainer &chosenCandidates,
341                                                //const float minRenderCostDecr,
342                                                SubdivisionCandidate *oldCandidate,
343                                                const int minSteps,
344                                                const int maxSteps);
345
346        /** Default subdivision method.
347        */
348        void RunConstruction(const bool repairQueue);
349               
350        ////////////////////////////////////////////////
351
352        /** Evaluates the subdivision candidate and executes the split.
353        */
354        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc,
355                                                                   SplitQueue &splitQueue,
356                                                                   const bool repairQueue);
357
358        /** Tests if hierarchy construction is finished.
359        */
360        bool FinishedConstruction() const;
361
362        /** Returns next subdivision candidate from the split queue.
363        */
364        SubdivisionCandidate *NextSubdivisionCandidate(SplitQueue &splitQueue);
365
366        /** Repairs the dirty entries of the subdivision candidate queue. The
367                list of entries is given in the dirty list.
368
369                @returns number of repaired candidates
370        */
371        int RepairQueue(const SubdivisionCandidateContainer &dirtyList,
372                                        SplitQueue &splitQueue,
373                                        const bool recomputeSplitPlaneOnRepair);
374
375        /** Collect subdivision candidates which were affected by the splits from the
376                chosenCandidates list.
377        */
378        void CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
379                                                                SubdivisionCandidateContainer &dirtyList);
380
381        /** Evaluate subdivision stats for log.
382        */
383        void EvalSubdivisionStats();
384
385        void AddSubdivisionStats(const int splits,
386                                                         const float renderCostDecr,
387                                                         const float totalRenderCost,
388                                                         const int totalPvsEntries,
389                                                         const float memory,
390                                                         const float renderCostPerStorage,
391                                                         const float vspOspRatio);
392
393        /** Collect affected view space candidates.
394        */
395        void CollectViewSpaceDirtyList(SubdivisionCandidate *sc,
396                                                                   SubdivisionCandidateContainer &dirtyList);
397
398        /** Collect affected object space candidates.
399        */
400        void CollectObjectSpaceDirtyList(SubdivisionCandidate *sc,
401                                                                         SubdivisionCandidateContainer &dirtyList);
402               
403        /** Export object space partition tree.
404        */
405        void ExportOspTree(Exporter *exporter,
406                                           const ObjectContainer &objects) const;
407
408        /** Parse the environment variables.
409        */
410        void ParseEnvironment();
411
412        bool StartObjectSpaceSubdivision() const;
413        bool StartViewSpaceSubdivision() const;
414
415
416        ////////////////////////////
417        // Helper function for preparation of subdivision
418
419        /** Prepare bv hierarchy for subdivision
420        */
421        void PrepareBvHierarchy(SplitQueue &tQueue,
422                                                        const VssRayContainer &sampleRays,
423                                                        const ObjectContainer &objects);
424
425        /** Prepare object space kd tree for subdivision.
426        */
427        void PrepareOspTree(SplitQueue &tQueue,
428                                                const VssRayContainer &sampleRays,
429                                                const ObjectContainer &objects);
430
431        /** Prepare view space subdivision and add candidate to queue.
432        */
433        void PrepareViewSpaceSubdivision(SplitQueue &tQueue,
434                                                                         const VssRayContainer &sampleRays,
435                                                                         const ObjectContainer &objects);
436
437        /** Was object space subdivision already constructed?
438        */
439        bool ObjectSpaceSubdivisionConstructed() const;
440       
441        /** Was view space subdivision already constructed?
442        */
443        bool ViewSpaceSubdivisionConstructed() const;
444
445        /** Reset the split queue, i.e., reevaluate the split candidates.
446        */
447    void ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane);
448
449        /** After the suddivision has ended, do some final tasks.
450        */
451        void FinishObjectSpaceSubdivision(const ObjectContainer &objects,
452                                                                          const bool removeRayRefs = true) const;
453
454        /** Returns depth of object space subdivision.
455        */
456        int GetObjectSpaceSubdivisionDepth() const;
457
458        /** Returns number of leaves in object space subdivision.
459        */
460        int GetObjectSpaceSubdivisionLeaves() const;
461        int GetObjectSpaceSubdivisionNodes() const;
462
463        /** Construct object space partition interleaved with view space partition.
464                Each time the best object or view space candidate is selected
465                for the next split.
466        */
467        void ConstructInterleaved(const VssRayContainer &sampleRays,
468                                                          const ObjectContainer &objects,
469                                                          AxisAlignedBox3 *forcedViewSpace);
470
471        /** Construct object space partition interleaved with view space partition.
472                The method chooses a number candidates of each type for subdivision.
473                The number is determined by the "gradient", i.e., the render cost decrease.
474                Once this render cost decrease is lower than the render cost decrease
475                for the splits of previous type, the method will stop current subdivision and
476                evaluate if view space or object space would be the beneficial for the
477                next number of split.
478        */
479        void ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
480                                                                                  const ObjectContainer &objects,
481                                                                                  AxisAlignedBox3 *forcedViewSpace);
482
483        /** Use iteration to construct the object space hierarchy.
484        */
485        void ConstructMultiLevel(const VssRayContainer &sampleRays,
486                                                         const ObjectContainer &objects,
487                                                         AxisAlignedBox3 *forcedViewSpace);
488
489        /** Based on a given subdivision, we try to optimize using an
490                multiple iteration over view and object space.
491        */
492        void OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                       
493                                                        const ObjectContainer &objects,
494                                                        AxisAlignedBox3 *forcedViewSpace);
495
496        /** Reset the object space subdivision.
497                E.g., deletes hierarchy and resets stats.
498                so construction can be restarted.
499        */
500        void ResetObjectSpaceSubdivision(SplitQueue &tQueue,
501                                                                         const VssRayContainer &rays,
502                                                                         const ObjectContainer &objects);
503
504        void ResetViewSpaceSubdivision(SplitQueue &tQueue,
505                                                                   const VssRayContainer &rays,
506                                                                   const ObjectContainer &objects,
507                                                                   AxisAlignedBox3 *forcedViewSpace);
508
509
510        ///////////////////////////
511
512        void ExportStats(ofstream &stats,
513                                         SplitQueue &tQueue,
514                                         const ObjectContainer &objects);
515
516        void CollectBestSet(const int maxSplits,
517                                                const float maxMemoryCost,
518                                                ViewCellContainer &viewCells,
519                                                vector<BvhNode *> &bvhNodes);
520
521        int ExtractStatistics(const int maxSplits,
522                                                  const float maxMemoryCost,
523                                                  float &renderCost,
524                                                  float &memory,
525                                                  int &pvsEntries,
526                                                  int &viewSpaceSplits,
527                                                  int &objectSpaceSplits,
528                                                  const bool useFilter,
529                                                  const bool useHisto,
530                                                  const int histoMem,
531                                                  const int pass,
532                                                  bool &histoUsed);
533
534        void ComputePvs(const ObjectPvs &pvs, float &rc, int &pvsEntries);
535        void GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const;
536        void PullUpPvsIncrementally(ViewCell *viewCell) const;
537        void GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const;
538        void GetPvsEfficiently(ViewCell *vc, ObjectPvs &pvs) const;
539
540        float EvalFullMem() const;
541
542
543protected:
544
545        /** construction types
546                sequential: construct first view space, then object space
547                interleaved: construct view space and object space fully interleaved
548                gradient: construct view space / object space until a threshold is reached
549                multilevel: iterate until subdivisions converge to the optimum.
550        */
551        enum {SEQUENTIAL, INTERLEAVED, GRADIENT, MULTILEVEL};
552
553        /// type of hierarchy construction
554        int mConstructionType;
555
556        /// Type of object space partition
557        int mObjectSpaceSubdivisionType;
558        /// Type of view space partition
559    int mViewSpaceSubdivisionType;
560
561        /// the traversal queue
562        SplitQueue mTQueue;
563       
564        ////////////
565        //-- helper variables
566       
567        // the original osp type
568        int mSavedObjectSpaceSubdivisionType;
569        // the original vsp type
570        int mSavedViewSpaceSubdivisionType;
571       
572
573        ///////////////////
574        // Hierarchies
575
576        /// view space hierarchy
577        VspTree *mVspTree;
578        /// object space partition kd tree
579        OspTree *mOspTree;
580
581        float mInitialRenderCost;
582       
583        float mMaxAvgRayContri;
584
585        float mMinAvgRayContri;
586
587        // quick hack:
588public:
589        /// bounding volume hierarchy
590        BvHierarchy *mBvHierarchy;
591       
592protected:
593
594
595        //////////
596        //-- global termination criteria
597
598        /// the mininal acceptable cost ratio for a split
599        float mTermMinGlobalCostRatio;
600        /// the threshold for global cost miss tolerance
601        int mTermGlobalCostMissTolerance;
602        /// maximum number of leaves
603        int mTermMaxLeaves;
604        /// Maximal allowed memory consumption.
605        float mTermMaxMemory;
606
607
608        ////////////////////
609
610        /// number of minimal steps of the same type
611        int mMinStepsOfSameType;
612        int mMaxStepsOfSameType;
613
614        /// statistics about the hierarchy
615        HierarchyStatistics mHierarchyStats;
616
617        int mMinDepthForObjectSpaceSubdivion;
618        int mMinDepthForViewSpaceSubdivion;
619       
620        //int mMinRenderCostDecrease;
621
622        ofstream mSubdivisionStats;
623
624        /// if the queue should be repaired after a subdivision steps
625        bool mRepairQueue;
626
627        bool mStartWithObjectSpace;
628        /** if multi level construction method should be used
629                where we iterate over both hierarchies until we
630                converge to the optimum.
631        */
632        bool mUseMultiLevelConstruction;
633
634        /// number of iteration steps for multilevel approach   
635        int mNumMultiLevels;
636
637        /** if split plane should be recomputed for the repair.
638                Otherwise only the priority is recomputed, the
639                split plane itself stays the same
640        */
641        bool mRecomputeSplitPlaneOnRepair;
642
643        /** If memory should be considered during choosing
644                of the next split type during gradient method.
645        */
646        bool mConsiderMemory;
647
648        int mMaxRepairs;
649
650        int mTimeStamp;
651        friend VspTree;
652        friend OspTree;
653        friend BvHierarchy;
654
655        float mPriority;
656
657        friend ViewCellsParseHandlers;
658
659        ViewCellContainer mOldViewCells;
660
661        ObjectPvs mOldPvs;
662};
663
664}
665
666#endif
Note: See TracBrowser for help on using the repository browser.