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

RevLine 
[1237]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"
[1239]12#include "SubdivisionCandidate.h"
[1237]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;
[1259]41class BvHierarchy;
[1287]42class Exporter;
[1667]43class ViewCellsParseHandlers;
[2094]44class TraversalTree;
[2116]45class ObjectPvs;
[1237]46
[1667]47
[2237]48#define COUNT_ORIGIN_OBJECTS 1
[2227]49#define USE_AVGRAYCONTRI 0
[1911]50
51
[2227]52
[1551]53/** View space / object space hierarchy statistics.
[1288]54*/
55class HierarchyStatistics: public StatisticsBase
56{
57public:
[1576]58        /// total number of entries in the pvs
[1624]59        int mPvsEntries;
[1640]60        /// storage cost in MB
61        float mMemory;
[1288]62        /// total number of nodes
[1624]63        int mNodes;
[1288]64        /// maximal reached depth
[1624]65        int mMaxDepth;
[1288]66        /// accumulated depth
[1624]67        int mAccumDepth;
[1449]68        /// time spent for queue repair
[1624]69        float mRepairTime;
70
[1449]71        // global cost ratio violations
72        int mGlobalCostMisses;
[1624]73        /// total cost of subdivision
74        float mTotalCost;
75        /// render cost decrease of subdivision
76        float mRenderCostDecrease;
[1313]77
[1288]78        // Constructor
79        HierarchyStatistics()
80        {
81                Reset();
82        }
83
[1624]84        int Nodes() const {return mNodes;}
[1640]85        int Interior() const { return mNodes / 2 - 1; }
[1624]86        int Leaves() const { return (mNodes / 2) + 1; }
[1288]87       
88        // TODO: computation wrong
[1624]89        double AvgDepth() const { return mAccumDepth / (double)Leaves();}
[1288]90
[1449]91        void Reset()
[1288]92        {
[1449]93                mGlobalCostMisses = 0;
[1624]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;
[1288]103        }
104
[2176]105        void Print(std::ostream &app) const;
[1288]106
[2176]107        friend std::ostream &operator<<(std::ostream &s, const HierarchyStatistics &stat)
[1288]108        {
109                stat.Print(s);
110                return s;
111        }
112};
113
114
[1723]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
[1744]135        float mPriority;
[1723]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;
[1744]153                mPriority = 0;
[1723]154        }
155
156
[2176]157        void Print(std::ostream &app) const;
[1723]158
[2176]159        friend std::ostream &operator<<(std::ostream &s, const HierarchySubdivisionStats &stat)
[1723]160        {
161                stat.Print(s);
162                return s;
163        }
164};
165
166
[1237]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{
[2124]191        friend class VspOspViewCellsManager;
192
[1237]193public:
[2124]194       
[1421]195        /** Constructor with the view space partition tree and
196                the object space hierarchy type as argument.
[1237]197        */
[1421]198        HierarchyManager(const int objectSpaceHierarchyType);
199        /** Deletes space partition and view space partition.
200        */
[1286]201        ~HierarchyManager();
[1237]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        */
[1308]207        void Construct(
[1293]208                const VssRayContainer &sampleRays,
209                const ObjectContainer &objects,
210                AxisAlignedBox3 *forcedViewSpace);
[1237]211
[1259]212        enum
213        {
214                NO_OBJ_SUBDIV,
215                KD_BASED_OBJ_SUBDIV,
216                BV_BASED_OBJ_SUBDIV
217        };
[1237]218
[1370]219        enum
220        {
221                NO_VIEWSPACE_SUBDIV,
222                KD_BASED_VIEWSPACE_SUBDIV
223        };
224
[1259]225        /** The type of object space subdivison
226        */
[1370]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        */             
[1279]233        void SetViewCellsManager(ViewCellsManager *vcm);
[1370]234        /** Sets a pointer to the view cells tree.
235        */
[1279]236        void SetViewCellsTree(ViewCellsTree *vcTree);
[2543]237        /** Sets a pointer to the vsp tree.
238        */
239        void SetVspTree(VspTree *vspTree);
[1370]240        /** Exports the object hierarchy to disc.
241        */
[1279]242        void ExportObjectSpaceHierarchy(OUT_STREAM &stream);
[1421]243        /** Print out statistics.
244        */
[2176]245        void PrintHierarchyStatistics(std::ostream &stream) const;
[1421]246        /** Returns the view space partition tree.
247        */
[1379]248        VspTree *GetVspTree();
[1421]249        /** Returns object space bounding box.
250        */
[1416]251        AxisAlignedBox3 GetObjectSpaceBox() const;
[1421]252        /** Exports object space hierarchy for visualization.
253        */
[1626]254        void ExportObjectSpaceHierarchy(Exporter *exporter,
255                                                                        const ObjectContainer &objects,
[1764]256                                                                        AxisAlignedBox3 *bbox,
[1920]257                                                                        const float maxRenderCost,
[1626]258                                                                        const bool exportBounds = true) const;
[1279]259
[1421]260        /** Returns intersectable pierced by this ray.
261        */
[1626]262        Intersectable *GetIntersectable(const VssRay &ray, const bool isTermination) const;
[1743]263 
[1889]264        Intersectable *GetIntersectable(Intersectable *obj, const Vector3 &point) const;
[1626]265        /** Export object space partition bounding boxes.
266        */
267        void ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects);
268
[2176]269        friend std::ostream &operator<<(std::ostream &s, const HierarchyManager &hm)
[1419]270        {
[1421]271                hm.PrintHierarchyStatistics(s);
[1419]272                return s;
273        }
274
[1667]275        HierarchyStatistics &GetHierarchyStats() { return mHierarchyStats; };
276
277        inline bool ConsiderMemory() const { return mConsiderMemory; }
[1686]278       
[2332]279        void EvaluateSubdivision(std::ofstream &splitsStats,
[1745]280                                                          const int splitsStepSize,
[1919]281                                                          const bool useFilter,
282                                                          const bool useHisto,
283                                                          const int histoMem,
284                                                          const int pass);
[1709]285
286
[1718]287        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
288
[1845]289        int CompressObjectSpace();
[1843]290        void CreateUniqueObjectIds();
291
[1912]292        float EvalCorrectedPvs(const float pvsFront,
293                                                   const float totalPvs,
[2227]294                                                   const float raysPerObjects) const;
[2094]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);
[2342]304
305        int CastLineSegment(RayPacket &packet);
306
307
[1237]308protected:
309
[2187]310        void PrintTimings(const bool osp);
311
[1625]312        /** Returns true if the global termination criteria were met.
313        */
[1237]314        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;
315
316        /** Prepare construction of the hierarchies, set parameters, compute
317                first split candidates.
318        */
[1779]319        void PrepareObjectSpaceSubdivision(SplitQueue &tQueue,
320                                                                           const VssRayContainer &sampleRays,
321                                                                           const ObjectContainer &objects);
[1237]322
[1625]323
[1640]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
[1667]332
[2530]333        //////////////
334        // these functions implement the main loop
[1625]335
336        /** This is for interleaved construction / sequential construction.
337        */
338        void RunConstruction(const bool repairQueue,
339                                                 const VssRayContainer &sampleRays,
340                                                 const ObjectContainer &objects,
[1640]341                                                 AxisAlignedBox3 *forcedViewSpace);
[1625]342        /** This is for interleaved construction using some objects
343                and some view space splits.
344        */
345        int RunConstruction(SplitQueue &splitQueue,
346                                                SubdivisionCandidateContainer &chosenCandidates,
[1667]347                                                //const float minRenderCostDecr,
348                                                SubdivisionCandidate *oldCandidate,
[1676]349                                                const int minSteps,
350                                                const int maxSteps);
[1625]351        /** Default subdivision method.
352        */
[1449]353        void RunConstruction(const bool repairQueue);
[2094]354       
355       
[2530]356        //////////////////////////
[1625]357
[1580]358        /** Evaluates the subdivision candidate and executes the split.
359        */
[1625]360        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc,
361                                                                   SplitQueue &splitQueue,
[2224]362                                                                   //const bool repairQueue,
363                                                                   std::vector<SubdivisionCandidate *> &dirtyList
364                                                                   );
[1625]365        /** Tests if hierarchy construction is finished.
366        */
[1237]367        bool FinishedConstruction() const;
[1625]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.
[1736]373
374                @returns number of repaired candidates
[1580]375        */
[1736]376        int RepairQueue(const SubdivisionCandidateContainer &dirtyList,
377                                        SplitQueue &splitQueue,
378                                        const bool recomputeSplitPlaneOnRepair);
[1625]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);
[2332]384        /** Print subdivision stats for log.
[1580]385        */
[2332]386        void PrintSubdivisionStats();
[1237]387
[1625]388        void AddSubdivisionStats(const int splits,
389                                                         const float renderCostDecr,
390                                                         const float totalRenderCost,
391                                                         const int totalPvsEntries,
[1640]392                                                         const float memory,
[1654]393                                                         const float renderCostPerStorage,
394                                                         const float vspOspRatio);
[1237]395
[1625]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        */
[1418]410        void ParseEnvironment();
[1415]411
[1418]412        bool StartObjectSpaceSubdivision() const;
413        bool StartViewSpaceSubdivision() const;
414
[1667]415
[1625]416        ////////////////////////////
417        // Helper function for preparation of subdivision
[1286]418
[1625]419        /** Prepare bv hierarchy for subdivision
420        */
[1779]421        void PrepareBvHierarchy(SplitQueue &tQueue,
422                                                        const VssRayContainer &sampleRays,
423                                                        const ObjectContainer &objects);
[1286]424
[1625]425        /** Prepare object space kd tree for subdivision.
426        */
[1779]427        void PrepareOspTree(SplitQueue &tQueue,
428                                                const VssRayContainer &sampleRays,
429                                                const ObjectContainer &objects);
[1308]430
[1625]431        /** Prepare view space subdivision and add candidate to queue.
432        */
[1779]433        void PrepareViewSpaceSubdivision(SplitQueue &tQueue,
434                                                                         const VssRayContainer &sampleRays,
435                                                                         const ObjectContainer &objects);
[1625]436
437        /** Was object space subdivision already constructed?
438        */
[1313]439        bool ObjectSpaceSubdivisionConstructed() const;
[1625]440        /** Was view space subdivision already constructed?
441        */
[1329]442        bool ViewSpaceSubdivisionConstructed() const;
[1625]443        /** Reset the split queue, i.e., reevaluate the split candidates.
444        */
[1640]445    void ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane);
[1625]446        /** After the suddivision has ended, do some final tasks.
447        */
[1654]448        void FinishObjectSpaceSubdivision(const ObjectContainer &objects,
449                                                                          const bool removeRayRefs = true) const;
[1625]450        /** Returns depth of object space subdivision.
451        */
[1370]452        int GetObjectSpaceSubdivisionDepth() const;
[1640]453        /** Returns number of leaves in object space subdivision.
454        */
455        int GetObjectSpaceSubdivisionLeaves() const;
[1663]456        int GetObjectSpaceSubdivisionNodes() const;
[1625]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        */
[1626]461        void ConstructInterleaved(const VssRayContainer &sampleRays,
462                                                          const ObjectContainer &objects,
463                                                          AxisAlignedBox3 *forcedViewSpace);
[1625]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        */
[1626]472        void ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
473                                                                                  const ObjectContainer &objects,
474                                                                                  AxisAlignedBox3 *forcedViewSpace);
[1548]475        /** Use iteration to construct the object space hierarchy.
476        */
[1626]477        void ConstructMultiLevel(const VssRayContainer &sampleRays,
478                                                         const ObjectContainer &objects,
479                                                         AxisAlignedBox3 *forcedViewSpace);
[1640]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);
[1548]486        /** Reset the object space subdivision.
487                E.g., deletes hierarchy and resets stats.
488                so construction can be restarted.
489        */
[1779]490        void ResetObjectSpaceSubdivision(SplitQueue &tQueue,
491                                                                         const VssRayContainer &rays,
492                                                                         const ObjectContainer &objects);
[1449]493
[1779]494        void ResetViewSpaceSubdivision(SplitQueue &tQueue,
495                                                                   const VssRayContainer &rays,
496                                                                   const ObjectContainer &objects,
497                                                                   AxisAlignedBox3 *forcedViewSpace);
[1557]498
[2073]499        void CreateTraversalTree();
[1614]500
[2530]501
[1686]502        ///////////////////////////
[1680]503
[2176]504        void ExportStats(std::ofstream &stats,
[1779]505                                         SplitQueue &tQueue,
506                                         const ObjectContainer &objects);
[1686]507
[1706]508        void CollectBestSet(const int maxSplits,
509                                                const float maxMemoryCost,
[1707]510                                                ViewCellContainer &viewCells,
[1706]511                                                vector<BvhNode *> &bvhNodes);
512
[1713]513        int ExtractStatistics(const int maxSplits,
514                                                  const float maxMemoryCost,
515                                                  float &renderCost,
516                                                  float &memory,
[1718]517                                                  int &pvsEntries,
518                                                  int &viewSpaceSplits,
[1745]519                                                  int &objectSpaceSplits,
[1919]520                                                  const bool useFilter,
521                                                  const bool useHisto,
522                                                  const int histoMem,
523                                                  const int pass,
524                                                  bool &histoUsed);
[1709]525
[2332]526        void ComputePvs(const ObjectPvs &pvs, float &triangles, int &pvsEntries);
[1787]527        void GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const;
[1786]528        void PullUpPvsIncrementally(ViewCell *viewCell) const;
529        void GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const;
[1787]530        void GetPvsEfficiently(ViewCell *vc, ObjectPvs &pvs) const;
531
[1830]532        float EvalFullMem() const;
533
[2332]534        ViewCellsManager *GetViewCellsManager();
[1843]535
[1237]536protected:
537
[2575]538        friend class VspTree;
539        friend class OspTree;
540        friend class BvHierarchy;
541        friend class ViewCellsParseHandlers;
[2530]542
543
[1627]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
[1580]552        /// type of hierarchy construction
553        int mConstructionType;
554        /// Type of object space partition
[1308]555        int mObjectSpaceSubdivisionType;
[1580]556        /// Type of view space partition
[1329]557    int mViewSpaceSubdivisionType;
558
[2530]559        /// the queue maintains the split candidates during traversal
[1589]560        SplitQueue mTQueue;
561       
[1323]562
[1580]563        ///////////////////
564        // Hierarchies
565
[2530]566        /// the bounding volume hierarchy
567        BvHierarchy *mBvHierarchy;
[1580]568        /// view space hierarchy
[1259]569        VspTree *mVspTree;
[1580]570        /// object space partition kd tree
[1259]571        OspTree *mOspTree;
[1625]572
[1911]573        float mInitialRenderCost;
574       
[2227]575        float mMaxAvgRaysPerObject;
576        float mMinAvgRaysPerObject;
[1911]577
[2530]578
579        /// an internal tree optimized for view cell traversal
[2130]580        bool mUseTraversalTree;
581
[2228]582
[1580]583        //////////
[1576]584        //-- global termination criteria
585
[1580]586        /// the mininal acceptable cost ratio for a split
[1237]587        float mTermMinGlobalCostRatio;
[1580]588        /// the threshold for global cost miss tolerance
[1237]589        int mTermGlobalCostMissTolerance;
[1580]590        /// maximum number of leaves
591        int mTermMaxLeaves;
[1649]592        /// Maximal allowed memory consumption.
593        float mTermMaxMemory;
[1580]594
[2530]595        float mMinRenderCost;
[1667]596
[2530]597
[1576]598        ////////////////////
599
[1667]600        /// number of minimal steps of the same type
[1640]601        int mMinStepsOfSameType;
[1684]602        int mMaxStepsOfSameType;
[1640]603
[1580]604        /// statistics about the hierarchy
[1288]605        HierarchyStatistics mHierarchyStats;
606
[1308]607        int mMinDepthForObjectSpaceSubdivion;
[1370]608        int mMinDepthForViewSpaceSubdivion;
[1580]609       
610        /// if the queue should be repaired after a subdivision steps
[1314]611        bool mRepairQueue;
[1370]612
613        bool mStartWithObjectSpace;
[2530]614        /** multi level construction method  means that
615                we iterate over both hierarchies until we
616                converge to the optimum.
[1580]617        */
[1449]618        bool mUseMultiLevelConstruction;
[1580]619        /// number of iteration steps for multilevel approach   
620        int mNumMultiLevels;
[1633]621        /** if split plane should be recomputed for the repair.
622                Otherwise only the priority is recomputed, the
[2530]623                split plane itself stays the same.
[1633]624        */
625        bool mRecomputeSplitPlaneOnRepair;
[1662]626
627        /** If memory should be considered during choosing
[2530]628                of the next split type during gradient method.
[1662]629        */
630        bool mConsiderMemory;
[1666]631
[2094]632        TraversalTree *mTraversalTree;
633
[1727]634        int mMaxRepairs;
635
[1679]636        int mTimeStamp;
[1744]637
638        float mPriority;
639
[1667]640
[2530]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
[1750]651        ViewCellContainer mOldViewCells;
[2530]652
653        std::ofstream mSubdivisionStats;
[1237]654};
655
656}
657
658#endif
Note: See TracBrowser for help on using the repository browser.