source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h @ 472

Revision 472, 16.1 KB checked in by mattausch, 19 years ago (diff)

added priority queue to vspbsptree

Line 
1#ifndef _VspBspTree_H__
2#define _VspBspTree_H__
3
4#include "Mesh.h"
5#include "Containers.h"
6#include "Polygon3.h"
7#include <stack>
8#include "Statistics.h"
9#include "VssRay.h"
10#include "RayInfo.h"
11#include "ViewCellBsp.h"
12
13class ViewCell;
14//class BspViewCell;
15class Plane3;
16class VspBspTree; 
17class BspInterior;
18class BspNode;
19class AxisAlignedBox3;
20class Ray;
21class ViewCellsStatistics;
22
23/*class BspNodeGeometry;
24class BspTreeStatistics;
25class ViewCellsStatistics;
26class BspNode;
27class BspLeaf;
28class BspInterior;
29*/
30
31/**
32        This is a view space partitioning specialised BSPtree. 
33        There are no polygon splits, but we split the sample rays.
34        The candidates for the next split plane are evaluated only
35        by checking the sampled visibility information.
36        The polygons are employed merely as candidates for the next split planes.
37*/
38class VspBspTree
39{
40public:
41       
42        /** Additional data which is passed down the BSP tree during traversal.
43        */
44        struct VspBspTraversalData
45        { 
46                /// the current node
47                BspNode *mNode;
48                /// polygonal data for splitting
49                PolygonContainer *mPolygons;
50                /// current depth
51                int mDepth;
52                /// rays piercing this node
53                RayInfoContainer *mRays;
54                /// area of current node
55                float mArea;
56                /// geometry of node as induced by planes
57                BspNodeGeometry *mGeometry;
58                /// pvs size
59                int mPvs;
60                /// how often this branch has missed the max-cost ratio
61                int mMaxCostMisses;
62                /** Returns average ray contribution.
63                */
64                float GetAvgRayContribution() const
65                {
66                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
67                }
68
69
70                VspBspTraversalData():
71                mNode(NULL),
72                mPolygons(NULL),
73                mDepth(0),
74                mRays(NULL),
75                mPvs(0),
76                mArea(0.0),
77                mGeometry(NULL),
78                mMaxCostMisses(0)
79                {}
80               
81                VspBspTraversalData(BspNode *node,
82                                                 PolygonContainer *polys,
83                                                 const int depth,
84                                                 RayInfoContainer *rays,
85                                                 int pvs,
86                                                 float area,
87                                                 BspNodeGeometry *geom):
88                mNode(node),
89                mPolygons(polys),
90                mDepth(depth),
91                mRays(rays),
92                mPvs(pvs),
93                mArea(area),
94                mGeometry(geom),
95                mMaxCostMisses(0)
96                {}
97
98                VspBspTraversalData(PolygonContainer *polys,
99                                                        const int depth,
100                                                        RayInfoContainer *rays,
101                                                        BspNodeGeometry *geom):
102                mNode(NULL),
103                mPolygons(polys),
104                mDepth(depth),
105                mRays(rays),
106                mPvs(0),
107                mArea(0),
108                mGeometry(geom),
109                mMaxCostMisses(0)
110                {}
111
112                friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
113                {
114#if 0
115                        return a.mPvs * a.mArea < b.mPvs * b.mArea;
116#endif
117#if 1
118                        return a.mPvs * (int)a.mRays->size() < b.mPvs * (int)b.mRays->size();
119#endif
120#if 0
121                        return a.mPvs < b.mPvs;
122#endif
123#if 0
124                        return
125                                a.mPvs / (float)(a.mRays->size() + Limits::Small())
126                                >
127                                b.mPvs / (float)(b.mRays->size() + Limits::Small());
128#endif
129#if 0
130                        return a.mPvs * (int)a.mRays->size() <  b.mPvs * (int)b.mRays->size();
131#endif
132                }
133    };
134       
135        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalStack;
136        //typedef std::stack<VspBspTraversalData> VspBspTraversalStack;
137
138        /** Default constructor creating an empty tree.
139        */
140        VspBspTree();
141
142        /** Default destructor.
143        */
144        ~VspBspTree();
145
146        /** Returns BSP Tree statistics.
147        */
148        const BspTreeStatistics &GetStatistics() const;
149 
150
151        /** Constructs the tree from a given set of rays.
152                @param sampleRays the set of sample rays the construction is based on
153                @param viewCells if not NULL, new view cells are
154                created in the leafs and stored in the container
155        */
156        void Construct(const VssRayContainer &sampleRays);
157
158        /** Returns list of BSP leaves.
159        */
160        void CollectLeaves(vector<BspLeaf *> &leaves) const;
161
162        /** Returns box which bounds the whole tree.
163        */
164        AxisAlignedBox3 GetBoundingBox()const;
165
166        /** Returns root of BSP tree.
167        */
168        BspNode *GetRoot() const;
169
170        /** Exports VspBsp tree to file.
171        */
172        bool Export(const string filename);
173
174        /** Collects the leaf view cells of the tree
175                @param viewCells returns the view cells
176        */
177        void CollectViewCells(ViewCellContainer &viewCells) const;
178
179        /** A ray is cast possible intersecting the tree.
180                @param the ray that is cast.
181                @returns the number of intersections with objects stored in the tree.
182        */
183        int CastRay(Ray &ray);
184
185        /// bsp tree construction types
186        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
187
188        /** Returns statistics.
189        */
190        BspTreeStatistics &GetStat();
191
192        /** finds neighbouring leaves of this tree node.
193        */
194        int FindNeighbors(BspNode *n,
195                                          vector<BspLeaf *> &neighbors,
196                                          const bool onlyUnmailed) const;
197
198        /** Constructs geometry associated with the half space intersections
199                leading to this node.
200        */
201        void ConstructGeometry(BspNode *n, PolygonContainer &cell) const;
202
203        /** Constructs geometry associated with the half space intersections
204                leading to this node.
205        */
206        void ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const;
207
208        /** Construct geometry and stores it in a geometry node container.
209        */
210        void ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const;
211
212        /** Returns random leaf of BSP tree.
213                @param halfspace defines the halfspace from which the leaf is taken.
214        */
215        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
216
217        /** Returns random leaf of BSP tree.
218                @param onlyUnmailed if only unmailed leaves should be returned.
219        */
220        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
221
222        /** Traverses tree and counts all view cells as well as their PVS size.
223        */
224        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
225
226
227        /** Returns view cell corresponding to unbounded space.
228        */
229        BspViewCell *GetRootCell() const;
230
231        /** Returns epsilon of this tree.
232        */
233        float GetEpsilon() const;
234
235
236    int
237        CastLineSegment(const Vector3 &origin,
238                                        const Vector3 &termination,
239                                        ViewCellContainer &viewcells
240                                        );
241
242protected:
243
244        // --------------------------------------------------------------
245        // For sorting objects
246        // --------------------------------------------------------------
247        struct SortableEntry
248        {
249                enum {POLY_MIN, POLY_MAX};
250   
251                int type;
252                float value;
253                Polygon3 *poly;
254                SortableEntry() {}
255                SortableEntry(const int t, const float v, Polygon3 *poly):
256                type(t), value(v), poly(poly) {}
257               
258                bool operator<(const SortableEntry &b) const
259                {
260                        return value < b.value;
261                } 
262        };
263
264        /** Evaluates tree stats in the BSP tree leafs.
265        */
266        void EvaluateLeafStats(const VspBspTraversalData &data);
267
268        /** Subdivides node with respect to the traversal data.
269            @param tStack current traversal stack
270                @param tData traversal data also holding node to be subdivided
271                @returns new root of the subtree
272        */
273        BspNode *Subdivide(VspBspTraversalStack &tStack,
274                                           VspBspTraversalData &tData);
275
276        /** Constructs the tree from the given traversal data.
277                @param polys stores set of polygons on which subdivision may be based
278                @param rays storesset of rays on which subdivision may be based
279        */
280        void Construct(const PolygonContainer &polys, RayInfoContainer *rays);
281
282        /** Selects the best possible splitting plane.
283                @param plane returns the split plane
284                @param leaf the leaf to be split
285                @param polys the polygon list on which the split decition is based
286                @param rays ray container on which selection may be based
287                @note the polygons can be reordered in the process
288                @returns true if the cost of the split is under maxCostRatio
289
290        */
291        bool SelectPlane(Plane3 &plane,
292                                         BspLeaf *leaf,
293                                         VspBspTraversalData &data);
294       
295        /** Strategies where the effect of the split plane is tested
296            on all input rays.
297
298                @returns the cost of the candidate split plane
299        */
300        float SplitPlaneCost(const Plane3 &candidatePlane,
301                                                 const VspBspTraversalData &data);
302
303
304        /** Subdivide leaf.
305                @param leaf the leaf to be subdivided
306               
307                @param polys the polygons to be split
308                @param frontPolys returns the polygons in front of the split plane
309                @param backPolys returns the polygons in the back of the split plane
310               
311                @param rays the polygons to be filtered
312                @param frontRays returns the polygons in front of the split plane
313                @param backRays returns the polygons in the back of the split plane
314
315                @returns the root of the subdivision
316        */
317
318        BspNode *SubdivideNode(VspBspTraversalData &tData,
319                                                   VspBspTraversalData &frontData,
320                                                   VspBspTraversalData &backData,
321                                                   PolygonContainer &coincident);
322
323        /** Selects the split plane in order to construct a tree with
324                certain characteristics (e.g., balanced tree, least splits,
325                2.5d aligned)
326                @param bestPlane returns the split plane
327                @param polygons container of polygons
328                @param rays bundle of rays on which the split can be based
329
330                @returns true if the overall cost is under maxCostRatio
331        */
332        bool SelectPlaneHeuristics(Plane3 &bestPlane,
333                                                           BspLeaf *leaf,
334                                                           VspBspTraversalData &data);
335
336        /** Extracts the meshes of the objects and adds them to polygons.
337                Adds object aabb to the aabb of the tree.
338                @param maxPolys the maximal number of objects to be stored as polygons
339                @returns the number of polygons
340        */
341        int AddToPolygonSoup(const ObjectContainer &objects,
342                                                 PolygonContainer &polys,
343                                                 int maxObjects = 0);
344
345        /** Extracts the meshes of the view cells and and adds them to polygons.
346                Adds view cell aabb to the aabb of the tree.
347                @param maxPolys the maximal number of objects to be stored as polygons
348                @returns the number of polygons
349        */
350        int AddToPolygonSoup(const ViewCellContainer &viewCells,
351                                                 PolygonContainer &polys,
352                                                 int maxObjects = 0);
353
354        /** Extract polygons of this mesh and add to polygon container.
355                @param mesh the mesh that drives the polygon construction
356                @param parent the parent intersectable this polygon is constructed from
357                @returns number of polygons
358        */
359        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
360
361        /** returns next candidate index and reorders polygons so no candidate is chosen two times
362                @param the current candidate index
363                @param max the range of candidates
364        */
365        int GetNextCandidateIdx(int currentIdx, PolygonContainer &polys);
366       
367        /** Computes best cost ratio for the suface area heuristics for axis aligned
368                splits. This heuristics minimizes the cost for ray traversal.
369                @param polys the polygons guiding the ratio computation
370                @param box the bounding box of the leaf
371                @param axis the current split axis
372                @param position returns the split position
373                @param objectsBack the number of objects in the back of the split plane
374                @param objectsFront the number of objects in the front of the split plane
375        */
376        float BestCostRatio(const PolygonContainer &polys,
377                                                const AxisAlignedBox3 &box,
378                                                const int axis,
379                                                float &position,
380                                                int &objectsBack,
381                                                int &objectsFront) const;
382       
383        /** Sorts split candidates for surface area heuristics for axis aligned splits.
384                @param polys the input for choosing split candidates
385                @param axis the current split axis
386                @param splitCandidates returns sorted list of split candidates
387        */
388        void SortSplitCandidates(const PolygonContainer &polys,
389                                                         const int axis,
390                                                         vector<SortableEntry> &splitCandidates) const;
391
392        /** Selects an axis aligned split plane.
393                Returns true if split is valied
394        */
395        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
396
397        /** Subdivides the rays into front and back rays according to the split plane.
398               
399                @param plane the split plane
400                @param rays contains the rays to be split. The rays are
401                           distributed into front and back rays.
402                @param frontRays returns rays on the front side of the plane
403                @param backRays returns rays on the back side of the plane
404               
405                @returns the number of splits
406        */
407        int SplitRays(const Plane3 &plane,
408                                  RayInfoContainer &rays,
409                              RayInfoContainer &frontRays,
410                                  RayInfoContainer &backRays);
411
412
413        /** Extracts the split planes representing the space bounded by node n.
414        */
415        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
416
417        /** Adds the object to the pvs of the front and back leaf with a given classification.
418
419                @param obj the object to be added
420                @param cf the ray classification regarding the split plane
421                @param frontPvs returns the PVS of the front partition
422                @param backPvs returns the PVS of the back partition
423       
424        */
425        void AddObjToPvs(Intersectable *obj, const int cf, int &frontPvs, int &backPvs) const;
426       
427        /** Computes PVS size induced by the rays.
428        */
429        int ComputePvsSize(const RayInfoContainer &rays) const;
430
431        /** Returns true if tree can be terminated.
432        */
433        inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;
434
435        /** Computes accumulated ray lenght of this rays.
436        */
437        float AccumulatedRayLength(const RayInfoContainer &rays) const;
438
439        /** Splits polygons with respect to the split plane.
440
441                @param plane the split plane
442                @param polys the polygons to be split. the polygons are consumed and
443                           distributed to the containers frontPolys, backPolys, coincident.
444                @param frontPolys returns the polygons in the front of the split plane
445                @param backPolys returns the polygons in the back of the split plane
446                @param coincident returns the polygons coincident to the split plane
447
448                @returns the number of splits   
449        */
450        int SplitPolygons(const Plane3 &plane,
451                                          PolygonContainer &polys,
452                                          PolygonContainer &frontPolys,
453                                          PolygonContainer &backPolys,
454                                          PolygonContainer &coincident) const;
455
456        /** Adds ray sample contributions to the PVS.
457                @param sampleContributions the number contributions of the samples
458                @param contributingSampels the number of contributing rays
459               
460        */
461        void AddToPvs(BspLeaf *leaf,
462                                  const RayInfoContainer &rays,
463                                  int &sampleContributions,
464                                  int &contributingSamples);
465
466
467
468 
469        /// Pointer to the root of the tree
470        BspNode *mRoot;
471               
472        BspTreeStatistics mStat;
473
474        /// Strategies for choosing next split plane.
475        enum {NO_STRATEGY = 0,
476                  RANDOM_POLYGON = 1,
477                  AXIS_ALIGNED = 2,
478                  LEAST_RAY_SPLITS = 256,
479                  BALANCED_RAYS = 512,
480                  PVS = 1024
481                };
482
483        /// box around the whole view domain
484        AxisAlignedBox3 mBox;
485
486        /// view cell corresponding to unbounded space
487        BspViewCell *mRootCell;
488
489        /// minimal number of rays before subdivision termination
490        int mTermMinRays;
491        /// maximal possible depth
492        int mTermMaxDepth;
493        /// mininum area
494        float mTermMinArea;
495        /// mininum PVS
496        int mTermMinPvs;
497
498        /// minimal number of rays for axis aligned split
499        int mTermMinRaysForAxisAligned;
500        /// minimal number of objects for axis aligned split
501        int mTermMinObjectsForAxisAligned;
502        /// maximal contribution per ray
503        float mTermMaxRayContribution;
504        /// minimal accumulated ray length
505        float mTermMinAccRayLength;
506
507        /// strategy to get the best split plane
508        int mSplitPlaneStrategy;
509        /// number of candidates evaluated for the next split plane
510        int mMaxPolyCandidates;
511        /// number of candidates for split planes evaluated using the rays
512        int mMaxRayCandidates;
513        /// balancing factor for PVS criterium
514        float mCtDivCi;
515
516        //-- axis aligned split criteria
517        float mAxisAlignedCtDivCi;
518        /// spezifies the split border of the axis aligned split
519        float mAxisAlignedSplitBorder;
520
521        /// maximal acceptable cost ratio
522        float mTermMaxCostRatio;
523        /// tolerance value indicating how often the max cost ratio can be failed
524        int mTermMissTolerance;
525
526        //-- factors guiding the split plane heuristics
527        float mLeastRaySplitsFactor;
528        float mBalancedRaysFactor;
529        float mPvsFactor;
530
531        /// if area or accumulated ray lenght should be used for PVS heuristics
532        bool mPvsUseArea;
533        /// tolerance for polygon split
534        float mEpsilon;
535        /// maximal number of test rays used to evaluate candidate split plane
536        int mMaxTests;
537        /// number of different bsp split plane criteria
538        int mNumCriteria;
539
540private:
541       
542        static const float sLeastRaySplitsTable[5];
543        /** Evaluates split plane classification with respect to the plane's
544                contribution for balanced rays.
545        */
546        static const float sBalancedRaysTable[5];
547
548        /// Generates unique ids for PVS criterium
549        static void GenerateUniqueIdsForPvs();
550
551        //-- unique ids for PVS criterium
552        static int sFrontId;
553        static int sBackId;
554        static int sFrontAndBackId;
555};
556
557#endif
Note: See TracBrowser for help on using the repository browser.