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

Revision 1421, 8.6 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;
43
44#if 0
45template <typename T> class GtPriority
46{
47public:
48        bool operator() (const T c1, const T c2) const
49        {
50                //return false;
51                return c1->GetPriority() < c2->GetPriority();
52        }
53};
54
55typedef std::priority_queue<SubdivisionCandidate *,
56                                                        std::vector<SubdivisionCandidate *>,
57                                                        GtPriority<std::vector<SubdivisionCandidate *>::value_type> > SplitQueue;
58#endif
59
60
61
62/** View space partition statistics.
63*/
64class HierarchyStatistics: public StatisticsBase
65{
66public:
67
68        /// total number of nodes
69        int nodes;
70        /// maximal reached depth
71        int maxDepth;
72        /// accumulated depth
73        int accumDepth;
74
75        float repairTime;
76
77        // Constructor
78        HierarchyStatistics()
79        {
80                Reset();
81        }
82
83        int Nodes() const {return nodes;}
84        int Interior() const { return nodes / 2; }
85        int Leaves() const { return (nodes / 2) + 1; }
86       
87        // TODO: computation wrong
88        double AvgDepth() const { return accumDepth / (double)Leaves();}
89
90        void Reset()
91        {
92                nodes = 0;
93                maxDepth = 0;
94                accumDepth = 0;
95                repairTime = 0;
96        }
97
98        void Print(ostream &app) const;
99
100        friend ostream &operator<<(ostream &s, const HierarchyStatistics &stat)
101        {
102                stat.Print(s);
103                return s;
104        }
105};
106
107
108typedef FlexibleHeap<SubdivisionCandidate *> SplitQueue;
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       
132*/
133class HierarchyManager
134{
135        friend VspTree;
136        friend OspTree;
137        friend BvHierarchy;
138        friend ViewCellsParseHandlers;
139
140public:
141        /** Constructor with the view space partition tree and
142                the object space hierarchy type as argument.
143        */
144        HierarchyManager(const int objectSpaceHierarchyType);
145        /** Hack: OspTree will copy the content from this kd tree.
146                Only view space hierarchy will be constructed.
147        */
148        HierarchyManager(KdTree *kdTree);
149
150        /** Deletes space partition and view space partition.
151        */
152        ~HierarchyManager();
153
154        /** Constructs the view space and object space subdivision from a given set of rays
155                and a set of objects.
156                @param sampleRays the set of sample rays the construction is based on
157                @param objects the set of objects
158        */
159        void Construct(
160                const VssRayContainer &sampleRays,
161                const ObjectContainer &objects,
162                AxisAlignedBox3 *forcedViewSpace);
163
164        enum
165        {
166                NO_OBJ_SUBDIV,
167                KD_BASED_OBJ_SUBDIV,
168                BV_BASED_OBJ_SUBDIV
169        };
170
171        enum
172        {
173                NO_VIEWSPACE_SUBDIV,
174                KD_BASED_VIEWSPACE_SUBDIV
175        };
176
177        /** The type of object space subdivison
178        */
179        int GetObjectSpaceSubdivisionType() const;     
180        /** The type of view space space subdivison
181        */
182        int GetViewSpaceSubdivisionType() const;
183        /** Sets a pointer to the view cells manager.
184        */             
185        void SetViewCellsManager(ViewCellsManager *vcm);
186        /** Sets a pointer to the view cells tree.
187        */
188        void SetViewCellsTree(ViewCellsTree *vcTree);
189        /** Exports the object hierarchy to disc.
190        */
191        void ExportObjectSpaceHierarchy(OUT_STREAM &stream);
192        /** Adds a sample to the pvs of the specified view cell.
193        */
194        bool AddSampleToPvs(
195                Intersectable *obj,
196                const Vector3 &hitPoint,
197                ViewCell *vc,
198                const float pdf,
199                float &contribution) const;
200
201        /** Print out statistics.
202        */
203        void PrintHierarchyStatistics(ostream &stream) const;
204
205        /** Returns the view space partition tree.
206        */
207        VspTree *GetVspTree();
208
209        /** Returns view space bounding box.
210        */
211        AxisAlignedBox3 GetViewSpaceBox() const;
212        /** Returns object space bounding box.
213        */
214        AxisAlignedBox3 GetObjectSpaceBox() const;
215
216        /** Exports object space hierarchy for visualization.
217        */
218        void ExportObjectSpaceHierarchy(
219                Exporter *exporter,
220                const ObjectContainer &objects,
221                const AxisAlignedBox3 *bbox,
222                const bool exportBounds = true) const;
223
224        /** Returns intersectable pierced by this ray.
225        */
226        Intersectable *GetIntersectable(
227                const VssRay &ray,
228                const bool isTermination) const;
229
230        friend ostream &operator<<(ostream &s, const HierarchyManager &hm)
231        {
232                hm.PrintHierarchyStatistics(s);
233                return s;
234        }
235
236
237protected:
238
239        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;
240
241        /** Prepare construction of the hierarchies, set parameters, compute
242                first split candidates.
243        */
244        void PrepareObjectSpaceSubdivision(
245                const VssRayContainer &sampleRays,
246                const ObjectContainer &objects);
247
248        void RunConstruction(
249                const VssRayContainer &sampleRays,
250                const ObjectContainer &objects,
251                AxisAlignedBox3 *forcedViewSpace);
252
253        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc);
254
255        bool FinishedConstruction() const;
256
257        SubdivisionCandidate *NextSubdivisionCandidate();
258
259        void RepairQueue();
260
261        void CollectDirtyCandidates(vector<SubdivisionCandidate *> &dirtyList);
262
263        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
264
265        void AddSubdivisionStats(
266                const int splits,
267                const float renderCostDecr,
268                const float totalRenderCost);
269
270        void CollectObjectSpaceDirtyList();
271        void CollectViewSpaceDirtyList();
272
273        bool AddSampleToPvs(Intersectable *obj,
274                                                const float pdf,
275                                                float &contribution) const;
276
277        void CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
278        void CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
279               
280        void ExportOspTree(Exporter *exporter, const ObjectContainer &objects) const;
281
282        void ParseEnvironment();
283
284        bool StartObjectSpaceSubdivision() const;
285        bool StartViewSpaceSubdivision() const;
286
287        void PrepareBvHierarchy(
288                const VssRayContainer &sampleRays,
289                const ObjectContainer &objects);
290
291        void PrepareOspTree(
292                const VssRayContainer &sampleRays,
293                const ObjectContainer &objects);
294
295        void PrepareViewSpaceSubdivision(
296                const VssRayContainer &sampleRays,
297                const ObjectContainer &objects);
298
299        bool ObjectSpaceSubdivisionConstructed() const;
300        bool ViewSpaceSubdivisionConstructed() const;
301
302    void ResetQueue();
303
304        void FinishObjectSpaceSubdivision(const ObjectContainer &objects) const;
305
306        int GetObjectSpaceSubdivisionDepth() const;
307
308protected:
309
310        enum {SEQUENTIAL, INTERLEAVED};
311       
312        int mObjectSpaceSubdivisionType;
313    int mViewSpaceSubdivisionType;
314
315        /// the original osp type
316        int mSavedObjectSpaceSubdivisionType;
317        int mSavedViewSpaceSubdivisionType;
318
319        int mConstructionType;
320
321        VspTree *mVspTree;
322        OspTree *mOspTree;
323        BvHierarchy *mBvHierarchy;
324
325        AxisAlignedBox3 mBoundingBox;
326
327        SplitQueue mTQueue;
328
329        SubdivisionCandidate *mCurrentCandidate;
330
331        //-- global criteria
332        float mTermMinGlobalCostRatio;
333        int mTermGlobalCostMissTolerance;
334        int mGlobalCostMisses;
335
336        /// keeps track of cost during subdivision
337        float mTotalCost;
338
339        HierarchyStatistics mHierarchyStats;
340
341        int mMinDepthForObjectSpaceSubdivion;
342        int mMinDepthForViewSpaceSubdivion;
343
344        int mTermMaxLeaves;
345        ofstream mSubdivisionStats;
346
347        bool mRepairQueue;
348
349        bool mStartWithObjectSpace;
350};
351
352}
353
354#endif
Note: See TracBrowser for help on using the repository browser.