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

Revision 1329, 7.5 KB checked in by mattausch, 18 years ago (diff)
Line 
1#ifndef _HierarchyManager_H__
2#define _HierarchyManager_H__
3
4#include <stack>
5
6#include "Mesh.h"
7#include "Containers.h"
8#include "Statistics.h"
9#include "VssRay.h"
10#include "RayInfo.h"
11#include "gzstream.h"
12#include "SubdivisionCandidate.h"
13
14
15
16namespace GtpVisibilityPreprocessor {
17
18class ViewCellLeaf;
19class OspTree;
20class VspTree;
21class Plane3;
22class AxisAlignedBox3;
23class Ray;
24class ViewCellsStatistics;
25class ViewCellsManager;
26class MergeCandidate;
27class Beam;
28class ViewCellsTree;
29class Environment;
30class VspInterior;
31class VspLeaf;
32class VspNode;
33class KdNode;
34class KdInterior;
35class KdLeaf;
36class OspTree;
37class KdIntersectable;
38class KdTree;
39class VspTree;
40class KdTreeStatistics;
41class BvHierarchy;
42class Exporter;
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 object space hierarchy type as argument.
142        */
143        HierarchyManager(VspTree *vspTree, const int objectSpaceHierarchyType);
144        /** Hack: OspTree will copy the content from this kd tree.
145                Only view space hierarchy will be constructed.
146        */
147        HierarchyManager(VspTree *vspTree, KdTree *kdTree);
148
149        ~HierarchyManager();
150
151        /** Constructs the view space and object space subdivision from a given set of rays
152                and a set of objects.
153                @param sampleRays the set of sample rays the construction is based on
154                @param objects the set of objects
155        */
156        void Construct(
157                const VssRayContainer &sampleRays,
158                const ObjectContainer &objects,
159                AxisAlignedBox3 *forcedViewSpace);
160
161        enum
162        {
163                NO_OBJ_SUBDIV,
164                KD_BASED_OBJ_SUBDIV,
165                BV_BASED_OBJ_SUBDIV
166        };
167
168        /** The type of object space subdivison
169        */
170        int GetObjectSpaceSubdivisionType() const
171        {
172                return mObjectSpaceSubdivisionType;
173        }
174               
175        void SetViewCellsManager(ViewCellsManager *vcm);
176
177        void SetViewCellsTree(ViewCellsTree *vcTree);
178
179        void ExportObjectSpaceHierarchy(OUT_STREAM &stream);
180
181        bool AddSampleToPvs(
182                Intersectable *obj,
183                const Vector3 &hitPoint,
184                ViewCell *vc,
185                const float pdf,
186                float &contribution) const;
187
188        void PrintHierarchyStatistics(ofstream &stream) const;
189
190        VspTree *GetVspTree() { return mVspTree; }
191
192        void ExportObjectSpaceHierarchy(
193                Exporter *exporter,
194                const ObjectContainer &objects) const;
195
196
197protected:
198
199        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;
200
201        /** Prepare construction of the hierarchies, set parameters, compute
202                first split candidates.
203        */
204        void PrepareObjectSpaceSubdivision(
205                const VssRayContainer &sampleRays,
206                const ObjectContainer &objects);
207
208        void RunConstruction(
209                const VssRayContainer &sampleRays,
210                const ObjectContainer &objects,
211                AxisAlignedBox3 *forcedViewSpace);
212
213        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc);
214
215        bool FinishedConstruction() const;
216
217        SubdivisionCandidate *NextSubdivisionCandidate();
218
219        void RepairQueue();
220
221        void CollectDirtyCandidates(vector<SubdivisionCandidate *> &dirtyList);
222
223        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
224
225        void AddSubdivisionStats(
226                const int splits,
227                const float renderCostDecr,
228                const float totalRenderCost);
229
230        void CollectObjectSpaceDirtyList();
231        void CollectViewSpaceDirtyList();
232
233        bool AddSampleToPvs(Intersectable *obj,
234                                                const float pdf,
235                                                float &contribution) const;
236
237        void CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
238        void CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
239               
240        void ExportOspTree(Exporter *exporter, const ObjectContainer &objects) const;
241        void ExportBvHierarchy(Exporter *exporter, const ObjectContainer &objects) const;
242
243        void PrepareBvHierarchy(
244                const VssRayContainer &sampleRays,
245                const ObjectContainer &objects);
246
247        void PrepareOspTree(
248                const VssRayContainer &sampleRays,
249                const ObjectContainer &objects);
250
251        void ParseEnvironment();
252
253        bool StartObjectSpaceSubdivision() const;
254        bool StartViewSpaceSubdivision() const;
255
256        void PrepareViewSpaceSubdivision(
257                const VssRayContainer &sampleRays,
258                const ObjectContainer &objects,
259                AxisAlignedBox3 *forcedViewSpace = NULL);
260
261        bool ObjectSpaceSubdivisionConstructed() const;
262        bool ViewSpaceSubdivisionConstructed() const;
263
264    void ResetQueue();
265
266
267protected:
268
269        enum {SEQUENTIAL, INTERLEAVED};
270       
271        int mObjectSpaceSubdivisionType;
272    int mViewSpaceSubdivisionType;
273
274        /// the original osp type
275        int mSavedObjectSpaceSubdivisionType;
276        int mSavedViewSpaceSubdivisionType;
277
278        int mConstructionType;
279
280        VspTree *mVspTree;
281        OspTree *mOspTree;
282        BvHierarchy *mBvHierarchy;
283
284        AxisAlignedBox3 mBoundingBox;
285
286        SplitQueue mTQueue;
287
288        SubdivisionCandidate *mCurrentCandidate;
289
290        //-- global criteria
291        float mTermMinGlobalCostRatio;
292        int mTermGlobalCostMissTolerance;
293        int mGlobalCostMisses;
294
295        /// keeps track of cost during subdivision
296        float mTotalCost;
297
298        HierarchyStatistics mHierarchyStats;
299
300        int mMinDepthForObjectSpaceSubdivion;
301
302        int mTermMaxLeaves;
303        ofstream mSubdivisionStats;
304
305        bool mRepairQueue;
306};
307
308}
309
310#endif
Note: See TracBrowser for help on using the repository browser.