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

Revision 2237, 18.7 KB checked in by mattausch, 18 years ago (diff)

worked on optimization. warning: not tested yet

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