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

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