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

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