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

Revision 2575, 18.4 KB checked in by bittner, 17 years ago (diff)

big merge: preparation for havran ray caster, check if everything works

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