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

Revision 2003, 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       
229        /** The type of view space space subdivison
230        */
231        int GetViewSpaceSubdivisionType() const;
232       
233        /** Sets a pointer to the view cells manager.
234        */             
235        void SetViewCellsManager(ViewCellsManager *vcm);
236       
237        /** Sets a pointer to the view cells tree.
238        */
239        void SetViewCellsTree(ViewCellsTree *vcTree);
240
241        /** Exports the object hierarchy to disc.
242        */
243        void ExportObjectSpaceHierarchy(OUT_STREAM &stream);
244       
245        /** Print out statistics.
246        */
247        void PrintHierarchyStatistics(ostream &stream) const;
248
249        /** Returns the view space partition tree.
250        */
251        VspTree *GetVspTree();
252
253        /** Returns object space bounding box.
254        */
255        AxisAlignedBox3 GetObjectSpaceBox() const;
256
257        /** Exports object space hierarchy for visualization.
258        */
259        void ExportObjectSpaceHierarchy(Exporter *exporter,
260                                                                        const ObjectContainer &objects,
261                                                                        AxisAlignedBox3 *bbox,
262                                                                        const float maxRenderCost,
263                                                                        const bool exportBounds = true) const;
264
265        /** Returns intersectable pierced by this ray.
266        */
267        Intersectable *GetIntersectable(const VssRay &ray, const bool isTermination) const;
268 
269        Intersectable *GetIntersectable(Intersectable *obj, const Vector3 &point) const;
270
271        /** Export object space partition bounding boxes.
272        */
273        void ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects);
274
275        friend ostream &operator<<(ostream &s, const HierarchyManager &hm)
276        {
277                hm.PrintHierarchyStatistics(s);
278                return s;
279        }
280
281        HierarchyStatistics &GetHierarchyStats() { return mHierarchyStats; };
282
283        inline bool ConsiderMemory() const { return mConsiderMemory; }
284       
285        void EvaluateSubdivision(const VssRayContainer &sampleRays,                                                                                     
286                                                         const ObjectContainer &objects,
287                                                         const string &filename);
288
289        void EvaluateSubdivision2(ofstream &splitsStats,
290                                                          const int splitsStepSize,
291                                                          const bool useFilter,
292                                                          const bool useHisto,
293                                                          const int histoMem,
294                                                          const int pass);
295
296
297        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
298
299        int CompressObjectSpace();
300        void CreateUniqueObjectIds();
301
302        float EvalCorrectedPvs(const float pvsFront,
303                                                   const float totalPvs,
304                                                   const float avgRayContri) const;
305
306
307protected:
308
309        /** Returns true if the global termination criteria were met.
310        */
311        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;
312
313        /** Prepare construction of the hierarchies, set parameters, compute
314                first split candidates.
315        */
316        void PrepareObjectSpaceSubdivision(SplitQueue &tQueue,
317                                                                           const VssRayContainer &sampleRays,
318                                                                           const ObjectContainer &objects);
319
320
321        /** Create bounding box and root.
322        */
323        void InitialiseObjectSpaceSubdivision(const ObjectContainer &objects);
324
325        /** Returns memory usage of object space hierarchy.
326        */
327        float GetObjectSpaceMemUsage() const;
328
329
330        //////////////////////////////
331        // the main loop
332
333        /** This is for interleaved construction / sequential construction.
334        */
335        void RunConstruction(const bool repairQueue,
336                                                 const VssRayContainer &sampleRays,
337                                                 const ObjectContainer &objects,
338                                                 AxisAlignedBox3 *forcedViewSpace);
339       
340        /** This is for interleaved construction using some objects
341                and some view space splits.
342        */
343        int RunConstruction(SplitQueue &splitQueue,
344                                                SubdivisionCandidateContainer &chosenCandidates,
345                                                //const float minRenderCostDecr,
346                                                SubdivisionCandidate *oldCandidate,
347                                                const int minSteps,
348                                                const int maxSteps);
349
350        /** Default subdivision method.
351        */
352        void RunConstruction(const bool repairQueue);
353               
354        ////////////////////////////////////////////////
355
356        /** Evaluates the subdivision candidate and executes the split.
357        */
358        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc,
359                                                                   SplitQueue &splitQueue,
360                                                                   const bool repairQueue);
361
362        /** Tests if hierarchy construction is finished.
363        */
364        bool FinishedConstruction() const;
365
366        /** Returns next subdivision candidate from the split queue.
367        */
368        SubdivisionCandidate *NextSubdivisionCandidate(SplitQueue &splitQueue);
369
370        /** Repairs the dirty entries of the subdivision candidate queue. The
371                list of entries is given in the dirty list.
372
373                @returns number of repaired candidates
374        */
375        int RepairQueue(const SubdivisionCandidateContainer &dirtyList,
376                                        SplitQueue &splitQueue,
377                                        const bool recomputeSplitPlaneOnRepair);
378
379        /** Collect subdivision candidates which were affected by the splits from the
380                chosenCandidates list.
381        */
382        void CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
383                                                                SubdivisionCandidateContainer &dirtyList);
384
385        /** Evaluate subdivision stats for log.
386        */
387        void EvalSubdivisionStats();
388
389        void AddSubdivisionStats(const int splits,
390                                                         const float renderCostDecr,
391                                                         const float totalRenderCost,
392                                                         const int totalPvsEntries,
393                                                         const float memory,
394                                                         const float renderCostPerStorage,
395                                                         const float vspOspRatio);
396
397        /** Collect affected view space candidates.
398        */
399        void CollectViewSpaceDirtyList(SubdivisionCandidate *sc,
400                                                                   SubdivisionCandidateContainer &dirtyList);
401
402        /** Collect affected object space candidates.
403        */
404        void CollectObjectSpaceDirtyList(SubdivisionCandidate *sc,
405                                                                         SubdivisionCandidateContainer &dirtyList);
406               
407        /** Export object space partition tree.
408        */
409        void ExportOspTree(Exporter *exporter,
410                                           const ObjectContainer &objects) const;
411
412        /** Parse the environment variables.
413        */
414        void ParseEnvironment();
415
416        bool StartObjectSpaceSubdivision() const;
417        bool StartViewSpaceSubdivision() const;
418
419
420        ////////////////////////////
421        // Helper function for preparation of subdivision
422
423        /** Prepare bv hierarchy for subdivision
424        */
425        void PrepareBvHierarchy(SplitQueue &tQueue,
426                                                        const VssRayContainer &sampleRays,
427                                                        const ObjectContainer &objects);
428
429        /** Prepare object space kd tree for subdivision.
430        */
431        void PrepareOspTree(SplitQueue &tQueue,
432                                                const VssRayContainer &sampleRays,
433                                                const ObjectContainer &objects);
434
435        /** Prepare view space subdivision and add candidate to queue.
436        */
437        void PrepareViewSpaceSubdivision(SplitQueue &tQueue,
438                                                                         const VssRayContainer &sampleRays,
439                                                                         const ObjectContainer &objects);
440
441        /** Was object space subdivision already constructed?
442        */
443        bool ObjectSpaceSubdivisionConstructed() const;
444       
445        /** Was view space subdivision already constructed?
446        */
447        bool ViewSpaceSubdivisionConstructed() const;
448
449        /** Reset the split queue, i.e., reevaluate the split candidates.
450        */
451    void ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane);
452
453        /** After the suddivision has ended, do some final tasks.
454        */
455        void FinishObjectSpaceSubdivision(const ObjectContainer &objects,
456                                                                          const bool removeRayRefs = true) const;
457
458        /** Returns depth of object space subdivision.
459        */
460        int GetObjectSpaceSubdivisionDepth() const;
461
462        /** Returns number of leaves in object space subdivision.
463        */
464        int GetObjectSpaceSubdivisionLeaves() const;
465        int GetObjectSpaceSubdivisionNodes() const;
466
467        /** Construct object space partition interleaved with view space partition.
468                Each time the best object or view space candidate is selected
469                for the next split.
470        */
471        void ConstructInterleaved(const VssRayContainer &sampleRays,
472                                                          const ObjectContainer &objects,
473                                                          AxisAlignedBox3 *forcedViewSpace);
474
475        /** Construct object space partition interleaved with view space partition.
476                The method chooses a number candidates of each type for subdivision.
477                The number is determined by the "gradient", i.e., the render cost decrease.
478                Once this render cost decrease is lower than the render cost decrease
479                for the splits of previous type, the method will stop current subdivision and
480                evaluate if view space or object space would be the beneficial for the
481                next number of split.
482        */
483        void ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
484                                                                                  const ObjectContainer &objects,
485                                                                                  AxisAlignedBox3 *forcedViewSpace);
486
487        /** Use iteration to construct the object space hierarchy.
488        */
489        void ConstructMultiLevel(const VssRayContainer &sampleRays,
490                                                         const ObjectContainer &objects,
491                                                         AxisAlignedBox3 *forcedViewSpace);
492
493        /** Based on a given subdivision, we try to optimize using an
494                multiple iteration over view and object space.
495        */
496        void OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                       
497                                                        const ObjectContainer &objects,
498                                                        AxisAlignedBox3 *forcedViewSpace);
499
500        /** Reset the object space subdivision.
501                E.g., deletes hierarchy and resets stats.
502                so construction can be restarted.
503        */
504        void ResetObjectSpaceSubdivision(SplitQueue &tQueue,
505                                                                         const VssRayContainer &rays,
506                                                                         const ObjectContainer &objects);
507
508        void ResetViewSpaceSubdivision(SplitQueue &tQueue,
509                                                                   const VssRayContainer &rays,
510                                                                   const ObjectContainer &objects,
511                                                                   AxisAlignedBox3 *forcedViewSpace);
512
513
514        ///////////////////////////
515
516        void ExportStats(ofstream &stats,
517                                         SplitQueue &tQueue,
518                                         const ObjectContainer &objects);
519
520        void CollectBestSet(const int maxSplits,
521                                                const float maxMemoryCost,
522                                                ViewCellContainer &viewCells,
523                                                vector<BvhNode *> &bvhNodes);
524
525        int ExtractStatistics(const int maxSplits,
526                                                  const float maxMemoryCost,
527                                                  float &renderCost,
528                                                  float &memory,
529                                                  int &pvsEntries,
530                                                  int &viewSpaceSplits,
531                                                  int &objectSpaceSplits,
532                                                  const bool useFilter,
533                                                  const bool useHisto,
534                                                  const int histoMem,
535                                                  const int pass,
536                                                  bool &histoUsed);
537
538        void ComputePvs(const ObjectPvs &pvs, float &rc, int &pvsEntries);
539        void GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const;
540        void PullUpPvsIncrementally(ViewCell *viewCell) const;
541        void GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const;
542        void GetPvsEfficiently(ViewCell *vc, ObjectPvs &pvs) const;
543
544        float EvalFullMem() const;
545
546
547protected:
548
549        /** construction types
550                sequential: construct first view space, then object space
551                interleaved: construct view space and object space fully interleaved
552                gradient: construct view space / object space until a threshold is reached
553                multilevel: iterate until subdivisions converge to the optimum.
554        */
555        enum {SEQUENTIAL, INTERLEAVED, GRADIENT, MULTILEVEL};
556
557        /// type of hierarchy construction
558        int mConstructionType;
559
560        /// Type of object space partition
561        int mObjectSpaceSubdivisionType;
562        /// Type of view space partition
563    int mViewSpaceSubdivisionType;
564
565        /// the traversal queue
566        SplitQueue mTQueue;
567       
568        ////////////
569        //-- helper variables
570       
571        // the original osp type
572        int mSavedObjectSpaceSubdivisionType;
573        // the original vsp type
574        int mSavedViewSpaceSubdivisionType;
575       
576
577        ///////////////////
578        // Hierarchies
579
580        /// view space hierarchy
581        VspTree *mVspTree;
582        /// object space partition kd tree
583        OspTree *mOspTree;
584
585        float mInitialRenderCost;
586       
587        float mMaxAvgRayContri;
588
589        float mMinAvgRayContri;
590
591        // quick hack:
592public:
593        /// bounding volume hierarchy
594        BvHierarchy *mBvHierarchy;
595       
596protected:
597
598
599        //////////
600        //-- global termination criteria
601
602        /// the mininal acceptable cost ratio for a split
603        float mTermMinGlobalCostRatio;
604        /// the threshold for global cost miss tolerance
605        int mTermGlobalCostMissTolerance;
606        /// maximum number of leaves
607        int mTermMaxLeaves;
608        /// Maximal allowed memory consumption.
609        float mTermMaxMemory;
610
611
612        ////////////////////
613
614        /// number of minimal steps of the same type
615        int mMinStepsOfSameType;
616        int mMaxStepsOfSameType;
617
618        /// statistics about the hierarchy
619        HierarchyStatistics mHierarchyStats;
620
621        int mMinDepthForObjectSpaceSubdivion;
622        int mMinDepthForViewSpaceSubdivion;
623       
624        //int mMinRenderCostDecrease;
625
626        ofstream mSubdivisionStats;
627
628        /// if the queue should be repaired after a subdivision steps
629        bool mRepairQueue;
630
631        bool mStartWithObjectSpace;
632        /** if multi level construction method should be used
633                where we iterate over both hierarchies until we
634                converge to the optimum.
635        */
636        bool mUseMultiLevelConstruction;
637
638        /// number of iteration steps for multilevel approach   
639        int mNumMultiLevels;
640
641        /** if split plane should be recomputed for the repair.
642                Otherwise only the priority is recomputed, the
643                split plane itself stays the same
644        */
645        bool mRecomputeSplitPlaneOnRepair;
646
647        /** If memory should be considered during choosing
648                of the next split type during gradient method.
649        */
650        bool mConsiderMemory;
651
652        int mMaxRepairs;
653
654        int mTimeStamp;
655        friend VspTree;
656        friend OspTree;
657        friend BvHierarchy;
658
659        float mPriority;
660
661        friend ViewCellsParseHandlers;
662
663        ViewCellContainer mOldViewCells;
664
665        ObjectPvs mOldPvs;
666};
667
668}
669
670#endif
Note: See TracBrowser for help on using the repository browser.