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

Revision 1713, 16.2 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        float mInitialRenderCost;
247
248
249protected:
250
251        /** Returns true if the global termination criteria were met.
252        */
253        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;
254
255        /** Prepare construction of the hierarchies, set parameters, compute
256                first split candidates.
257        */
258        SubdivisionCandidate *PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
259                                                                                                                const ObjectContainer &objects);
260
261
262        /** Create bounding box and root.
263        */
264        void InitialiseObjectSpaceSubdivision(const ObjectContainer &objects);
265
266        /** Returns memory usage of object space hierarchy.
267        */
268        float GetObjectSpaceMemUsage() const;
269
270
271        //////////////////////////////
272        // the main loop
273
274        /** This is for interleaved construction / sequential construction.
275        */
276        void RunConstruction(const bool repairQueue,
277                                                 const VssRayContainer &sampleRays,
278                                                 const ObjectContainer &objects,
279                                                 AxisAlignedBox3 *forcedViewSpace);
280       
281        /** This is for interleaved construction using some objects
282                and some view space splits.
283        */
284        int RunConstruction(SplitQueue &splitQueue,
285                                                SubdivisionCandidateContainer &chosenCandidates,
286                                                //const float minRenderCostDecr,
287                                                SubdivisionCandidate *oldCandidate,
288                                                const int minSteps,
289                                                const int maxSteps);
290
291        /** Default subdivision method.
292        */
293        void RunConstruction(const bool repairQueue);
294               
295        ////////////////////////////////////////////////
296
297        /** Evaluates the subdivision candidate and executes the split.
298        */
299        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc,
300                                                                   SplitQueue &splitQueue,
301                                                                   const bool repairQueue);
302
303        /** Tests if hierarchy construction is finished.
304        */
305        bool FinishedConstruction() const;
306
307        /** Returns next subdivision candidate from the split queue.
308        */
309        SubdivisionCandidate *NextSubdivisionCandidate(SplitQueue &splitQueue);
310
311        /** Repairs the dirty entries of the subdivision candidate queue. The
312                list of entries is given in the dirty list.
313        */
314        void RepairQueue(const SubdivisionCandidateContainer &dirtyList,
315                                         SplitQueue &splitQueue,
316                                         const bool recomputeSplitPlaneOnRepair);
317
318        /** Collect subdivision candidates which were affected by the splits from the
319                chosenCandidates list.
320        */
321        void CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
322                                                                SubdivisionCandidateContainer &dirtyList);
323
324        /** Evaluate subdivision stats for log.
325        */
326        void EvalSubdivisionStats();
327
328        void AddSubdivisionStats(const int splits,
329                                                         const float renderCostDecr,
330                                                         const float totalRenderCost,
331                                                         const int totalPvsEntries,
332                                                         const float memory,
333                                                         const float renderCostPerStorage,
334                                                         const float vspOspRatio);
335
336        bool AddSampleToPvs(Intersectable *obj,
337                                                const float pdf,
338                                                float &contribution) const;
339
340        /** Collect affected view space candidates.
341        */
342        void CollectViewSpaceDirtyList(SubdivisionCandidate *sc,
343                                                                   SubdivisionCandidateContainer &dirtyList);
344
345        /** Collect affected object space candidates.
346        */
347        void CollectObjectSpaceDirtyList(SubdivisionCandidate *sc,
348                                                                         SubdivisionCandidateContainer &dirtyList);
349               
350        /** Export object space partition tree.
351        */
352        void ExportOspTree(Exporter *exporter,
353                                           const ObjectContainer &objects) const;
354
355        /** Parse the environment variables.
356        */
357        void ParseEnvironment();
358
359        bool StartObjectSpaceSubdivision() const;
360        bool StartViewSpaceSubdivision() const;
361
362
363        ////////////////////////////
364        // Helper function for preparation of subdivision
365
366        /** Prepare bv hierarchy for subdivision
367        */
368        SubdivisionCandidate *PrepareBvHierarchy(const VssRayContainer &sampleRays,
369                                                                           const ObjectContainer &objects);
370
371        /** Prepare object space kd tree for subdivision.
372        */
373        SubdivisionCandidate *PrepareOspTree(const VssRayContainer &sampleRays,
374                                                                   const ObjectContainer &objects);
375
376        /** Prepare view space subdivision and add candidate to queue.
377        */
378        SubdivisionCandidate *PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
379                                                                                                          const ObjectContainer &objects);
380
381        /** Was object space subdivision already constructed?
382        */
383        bool ObjectSpaceSubdivisionConstructed() const;
384       
385        /** Was view space subdivision already constructed?
386        */
387        bool ViewSpaceSubdivisionConstructed() const;
388
389        /** Reset the split queue, i.e., reevaluate the split candidates.
390        */
391    void ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane);
392
393        /** After the suddivision has ended, do some final tasks.
394        */
395        void FinishObjectSpaceSubdivision(const ObjectContainer &objects,
396                                                                          const bool removeRayRefs = true) const;
397
398        /** Returns depth of object space subdivision.
399        */
400        int GetObjectSpaceSubdivisionDepth() const;
401
402        /** Returns number of leaves in object space subdivision.
403        */
404        int GetObjectSpaceSubdivisionLeaves() const;
405        int GetObjectSpaceSubdivisionNodes() const;
406
407        /** Construct object space partition interleaved with view space partition.
408                Each time the best object or view space candidate is selected
409                for the next split.
410        */
411        void ConstructInterleaved(const VssRayContainer &sampleRays,
412                                                          const ObjectContainer &objects,
413                                                          AxisAlignedBox3 *forcedViewSpace);
414
415        /** Construct object space partition interleaved with view space partition.
416                The method chooses a number candidates of each type for subdivision.
417                The number is determined by the "gradient", i.e., the render cost decrease.
418                Once this render cost decrease is lower than the render cost decrease
419                for the splits of previous type, the method will stop current subdivision and
420                evaluate if view space or object space would be the beneficial for the
421                next number of split.
422        */
423        void ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
424                                                                                  const ObjectContainer &objects,
425                                                                                  AxisAlignedBox3 *forcedViewSpace);
426
427        /** Use iteration to construct the object space hierarchy.
428        */
429        void ConstructMultiLevel(const VssRayContainer &sampleRays,
430                                                         const ObjectContainer &objects,
431                                                         AxisAlignedBox3 *forcedViewSpace);
432
433        /** Based on a given subdivision, we try to optimize using an
434                multiple iteration over view and object space.
435        */
436        void OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                       
437                                                        const ObjectContainer &objects,
438                                                        AxisAlignedBox3 *forcedViewSpace);
439
440        /** Reset the object space subdivision.
441                E.g., deletes hierarchy and resets stats.
442                so construction can be restarted.
443        */
444        SubdivisionCandidate *ResetObjectSpaceSubdivision(const VssRayContainer &rays,
445                                                                                                          const ObjectContainer &objects);
446
447        SubdivisionCandidate *ResetViewSpaceSubdivision(const VssRayContainer &rays,
448                                                                                                        const ObjectContainer &objects,
449                                                                                                        AxisAlignedBox3 *forcedViewSpace);
450
451
452        ///////////////////////////
453
454        void ExportStats(ofstream &stats, SplitQueue &tQueue, const ObjectContainer &objects);
455
456        void CollectBestSet(const int maxSplits,
457                                                const float maxMemoryCost,
458                                                ViewCellContainer &viewCells,
459                                                vector<BvhNode *> &bvhNodes);
460
461        int ExtractStatistics(const int maxSplits,
462                                                  const float maxMemoryCost,
463                                                  float &renderCost,
464                                                  float &memory,
465                                                  int &pvsEntries);
466
467
468protected:
469
470        /** construction types
471                sequential: construct first view space, then object space
472                interleaved: construct view space and object space fully interleaved
473                gradient: construct view space / object space until a threshold is reached
474                multilevel: iterate until subdivisions converge to the optimum.
475        */
476        enum {SEQUENTIAL, INTERLEAVED, GRADIENT, MULTILEVEL};
477
478        /// type of hierarchy construction
479        int mConstructionType;
480
481        /// Type of object space partition
482        int mObjectSpaceSubdivisionType;
483        /// Type of view space partition
484    int mViewSpaceSubdivisionType;
485
486        /// the traversal queue
487        SplitQueue mTQueue;
488       
489        ////////////
490        //-- helper variables
491       
492        // the original osp type
493        int mSavedObjectSpaceSubdivisionType;
494        // the original vsp type
495        int mSavedViewSpaceSubdivisionType;
496        /// the current subdivision candidate
497        //SubdivisionCandidate *mCurrentCandidate;
498
499
500        ///////////////////
501        // Hierarchies
502
503        /// view space hierarchy
504        VspTree *mVspTree;
505        /// object space partition kd tree
506        OspTree *mOspTree;
507
508        public:
509        /// bounding volume hierarchy
510        BvHierarchy *mBvHierarchy;
511       
512protected:
513
514
515        //////////
516        //-- global termination criteria
517
518        /// the mininal acceptable cost ratio for a split
519        float mTermMinGlobalCostRatio;
520        /// the threshold for global cost miss tolerance
521        int mTermGlobalCostMissTolerance;
522        /// maximum number of leaves
523        int mTermMaxLeaves;
524        /// Maximal allowed memory consumption.
525        float mTermMaxMemory;
526
527
528        ////////////////////
529
530        /// number of minimal steps of the same type
531        int mMinStepsOfSameType;
532        int mMaxStepsOfSameType;
533
534        /// statistics about the hierarchy
535        HierarchyStatistics mHierarchyStats;
536
537        int mMinDepthForObjectSpaceSubdivion;
538        int mMinDepthForViewSpaceSubdivion;
539       
540        //int mMinRenderCostDecrease;
541
542        ofstream mSubdivisionStats;
543
544        /// if the queue should be repaired after a subdivision steps
545        bool mRepairQueue;
546
547        bool mStartWithObjectSpace;
548        /** if multi level construction method should be used
549                where we iterate over both hierarchies until we
550                converge to the optimum.
551        */
552        bool mUseMultiLevelConstruction;
553
554        /// number of iteration steps for multilevel approach   
555        int mNumMultiLevels;
556
557        /** if split plane should be recomputed for the repair.
558                Otherwise only the priority is recomputed, the
559                split plane itself stays the same
560        */
561        bool mRecomputeSplitPlaneOnRepair;
562
563        /** If memory should be considered during choosing
564                of the next split type during gradient method.
565        */
566        bool mConsiderMemory;
567
568        /// constant value for driving the heuristics
569        float mMemoryConst;
570       
571        bool mConsiderMemory2;
572
573        int mTimeStamp;
574        friend VspTree;
575        friend OspTree;
576        friend BvHierarchy;
577        friend ViewCellsParseHandlers;
578
579};
580
581}
582
583#endif
Note: See TracBrowser for help on using the repository browser.