source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h @ 367

Revision 367, 21.5 KB checked in by mattausch, 19 years ago (diff)

started pvs surface area heuristics

Line 
1#ifndef _ViewCellBsp_H__
2#define _ViewCellBsp_H__
3
4#include "Mesh.h"
5#include "Containers.h"
6#include <stack>
7
8class ViewCell;
9class BspViewCell;
10class Plane3;
11class BspTree; 
12class BspInterior;
13class Polygon3;
14class AxisAlignedBox3;
15class Ray;
16
17/** Data structure used for optimized ray casting.
18*/
19struct BspRayTraversalData
20{
21    BspNode *mNode;
22    Vector3 mExitPoint;
23    float mMaxT;
24   
25    BspRayTraversalData() {}
26
27    BspRayTraversalData(BspNode *n, const Vector3 &extp, const float maxt):
28    mNode(n), mExitPoint(extp), mMaxT(maxt)
29        {}
30};
31
32/** Data used for passing ray data down the tree.
33*/
34struct BoundedRay
35{
36        Ray *mRay;
37        float mMinT;
38        float mMaxT;
39               
40        BoundedRay(): mMinT(0), mMaxT(1e6), mRay(NULL)
41        {}
42        BoundedRay(Ray *r, float minT, float maxT):
43        mRay(r), mMinT(minT), mMaxT(maxT)
44        {}
45};
46
47typedef vector<BoundedRay *> BoundedRayContainer;
48
49class BspTreeStatistics
50{
51public:
52  // total number of nodes
53  int nodes;
54  // number of splits
55  int splits;
56  // totals number of rays
57  int rays;
58  // maximal reached depth
59  int maxDepth;
60  // minimal depth
61  int minDepth;
62  // max depth nodes
63  int maxDepthNodes;
64  // max number of rays per node
65  int maxObjectRefs;
66   // accumulated depth (used to compute average)
67  int accumDepth;
68  // number of initial polygons
69  int polys;
70  /// number of view cells different to the view cell representing unbounded space.
71  int viewCells;
72  /// size of the VPS
73  int pvs;
74  /// samples contributing to pvs
75  int contributingSamples;
76   /// sample contributions to pvs
77  int sampleContributions;
78
79  // Constructor
80  BspTreeStatistics()
81  {
82          Reset();
83  }
84
85  int Nodes() const {return nodes;}
86  int Interior() const { return nodes / 2; }
87  int Leaves() const { return (nodes / 2) + 1; }
88  double AvgDepth() const { return accumDepth / (double)Leaves();}; // TODO: computation wrong
89 
90  void Reset()
91  {
92          nodes = 0;
93          splits = 0;
94      maxDepthNodes = 0;
95          maxDepth = 0;
96          minDepth = 99999;
97          polys = 0;
98          accumDepth = 0;
99          viewCells = 0;
100          pvs = 0;
101          contributingSamples = 0;
102          sampleContributions = 0;
103  }
104
105  void
106  Print(ostream &app) const;
107
108  friend ostream &operator<<(ostream &s, const BspTreeStatistics &stat) {
109    stat.Print(s);
110    return s;
111  }
112 
113};
114
115/**
116    BspNode abstract class serving for interior and leaf node implementation
117*/
118class BspNode
119{
120        friend class BspTree;
121
122public:
123        BspNode();
124        virtual ~BspNode();
125        BspNode(BspInterior *parent);
126
127        /** Determines whether this node is a leaf or not
128        @return true if leaf
129        */
130        virtual bool IsLeaf() const = 0;
131
132        /** Determines whether this node is a root
133        @return true if root
134        */
135        virtual bool IsRoot() const;
136
137        /** Returns parent node.
138        */
139        BspInterior *GetParent();
140        /** Sets parent node.
141        */
142        void SetParent(BspInterior *parent);
143
144        /** Returns pointer to polygons.
145        */
146        PolygonContainer *GetPolygons();
147        /** Stores polygons in node or discards them according to storePolys.
148        */
149        void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
150
151        static int mailID;
152        int mailbox;
153 
154        void Mail() { mailbox = mailID; }
155        static void NewMail() { mailID++; }
156        bool Mailed() const { return mailbox == mailID; }
157
158//int mViewCellIdx;
159protected:
160
161        /// parent of this node
162        BspInterior *mParent;
163
164        /// store polygons created during BSP splits
165        PolygonContainer *mPolygons;
166};
167
168/** BSP interior node implementation
169*/
170class BspInterior : public BspNode
171{
172        friend class BspTree;
173public:
174        /** Standard contructor taking split plane as argument.
175        */
176        BspInterior(const Plane3 &plane);
177        /** @return false since it is an interior node
178        */
179        bool IsLeaf() const;
180
181        BspNode *GetBack();
182        BspNode *GetFront();
183
184        Plane3 *GetPlane();
185
186        void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
187        void SetupChildLinks(BspNode *b, BspNode *f);
188
189        /** Splits polygons with respect to the split plane.
190                @param polys the polygons to be split. the polygons are consumed and
191                           distributed to the containers frontPolys, backPolys, coincident.
192                @param frontPolys returns the polygons in the front of the split plane
193                @param backPolys returns the polygons in the back of the split plane
194                @param coincident returns the polygons coincident to the split plane
195                @param storePolys if the polygons should be stored in the node
196               
197                @returns the number of splits   
198        */
199        int SplitPolygons(PolygonContainer &polys,
200                                          PolygonContainer &frontPolys,
201                                          PolygonContainer &backPolys,
202                                          PolygonContainer &coincident,
203                                          const bool storePolys = false);
204
205        /** Stores polygon in node or discards them according to storePolys.
206                @param polys the polygons
207                @param storePolys if the polygons should be stored or discarded
208        */
209        void ProcessPolygon(Polygon3 **poly, const bool storePolys);
210
211        friend ostream &operator<<(ostream &s, const BspInterior &A)
212        {
213                return s << A.mPlane;
214        }
215
216protected:
217
218        /// Splitting plane corresponding to this node
219        Plane3 mPlane;
220        /// back node
221        BspNode *mBack;
222        /// front node
223        BspNode *mFront;
224};
225
226/** BSP leaf node implementation.
227*/
228class BspLeaf : public BspNode
229{
230        friend class BspTree;
231
232public:
233        BspLeaf();
234        BspLeaf(BspViewCell *viewCell);
235        BspLeaf(BspInterior *parent);
236        BspLeaf(BspInterior *parent, BspViewCell *viewCell);
237
238        /** @return true since it is an interior node
239        */
240        bool IsLeaf() const;
241       
242        /** Returns pointer of view cell.
243        */
244        BspViewCell *GetViewCell() const;
245
246        /** Sets pointer to view cell.
247        */
248        void SetViewCell(BspViewCell *viewCell);
249
250        /** Generates new view cell and adds rays to the PVS.
251                @param sampleContributions the number contributions of the sampels
252                @param contributingSampels the number of contributing rays
253               
254        */
255        void GenerateViewCell(const BoundedRayContainer &rays,
256                                              int &sampleContributions,
257                                                  int &contributingSamples);
258
259protected:
260
261        /// if NULL this does not correspond to feasible viewcell
262        BspViewCell *mViewCell;
263};
264
265/** Implementation of the view cell BSP tree.
266*/
267class BspTree
268{
269public:
270       
271        /** Additional data which is passed down the BSP tree during traversal.
272        */
273        struct BspTraversalData
274        { 
275                /// the current node
276                BspNode *mNode;
277                /// polygonal data for splitting
278                PolygonContainer *mPolygons;
279                /// current depth
280                int mDepth;
281                /// the view cell associated with this subdivsion
282                ViewCell *mViewCell;
283                /// rays piercing this node
284                BoundedRayContainer *mRays;
285
286                BspTraversalData():
287                mNode(NULL),
288                mPolygons(NULL),
289                mDepth(0),
290                mViewCell(NULL),
291                mRays(NULL)
292                {}
293               
294                BspTraversalData(BspNode *node,
295                                                 PolygonContainer *polys,
296                                                 const int depth,
297                                                 ViewCell *viewCell,
298                                                 BoundedRayContainer *rays):
299                mNode(node),
300                mPolygons(polys),
301                mDepth(depth),
302                mViewCell(viewCell),
303                mRays(rays)
304                {}
305    };
306       
307        typedef std::stack<BspTraversalData> BspTraversalStack;
308
309        /** Default constructor creating an empty tree.
310                @param viewCell view cell corresponding to unbounded space
311        */
312        BspTree(ViewCell *viewCell);
313
314        ~BspTree();
315
316        const BspTreeStatistics &GetStatistics() const;
317 
318        /** Constructs tree using the given list of view cells.
319            For this type of construction we filter all view cells down the
320                tree. If there is no polygon left, the last split plane
321            decides inside or outside of the viewcell. A pointer to the
322                appropriate view cell is stored within each leaf.
323                Many leafs can point to the same viewcell.
324        */
325        void Construct(const ViewCellContainer &viewCells);
326
327        /** Constructs tree using the given list of objects.
328            @note the objects are not taken as view cells, but the view cells are
329                constructed from the subdivision: Each leaf is taken as one viewcell.
330                @param objects list of objects
331        */
332        void Construct(const ObjectContainer &objects);
333
334        /** Constructs the tree from a given set of rays.
335                @param sampleRays the set of sample rays the construction is based on
336                @param viewCells if not NULL, new view cells are
337                created in the leafs and stored in the conatainer
338        */
339        void Construct(const RayContainer &sampleRays);
340
341        /** Returns list of BSP leaves.
342        */
343        void CollectLeaves(vector<BspLeaf *> &leaves);
344
345        /** Returns box which bounds the whole tree.
346        */
347        AxisAlignedBox3 GetBoundingBox()const;
348
349        /** Returns root of BSP tree.
350        */
351        BspNode *GetRoot() const;
352
353        /** Exports Bsp tree to file.
354        */
355        bool Export(const string filename);
356
357        /** Collects the leaf view cells of the tree
358                @param viewCells returns the view cells
359        */
360        void CollectViewCells(ViewCellContainer &viewCells) const;
361
362        /** A ray is cast possible intersecting the tree.
363                @param the ray that is cast.
364                @returns the number of intersections with objects stored in the tree.
365        */
366        int CastRay(Ray &ray);
367
368        /** Set to true if new view cells shall be generated in each leaf.
369        */
370        void SetGenerateViewCells(int generateViewCells);
371
372        /// bsp tree construction types
373        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_RAYS};
374
375        /** Returns statistics.
376        */
377        BspTreeStatistics &GetStat();
378
379        /** finds neighbouring leaves of this tree node.
380        */
381        int FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
382                                          const bool onlyUnmailed) const;
383
384        /** Constructs geometry associated with the half space intersections
385                leading to this node.
386        */
387        void ConstructGeometry(BspNode *n, PolygonContainer &cell) const;
388       
389        /** Construct geometry of view cell.
390        */
391        void ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const;
392
393        /** Returns random leaf of BSP tree.
394                @param halfspace defines the halfspace from which the leaf is taken.
395        */
396        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
397
398        /** Returns random leaf of BSP tree.
399                @param onlyUnmailed if only unmailed leaves should be returned.
400        */
401        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
402
403        /** Adds halfspace to cell definition.
404                @param side indicates which side of halfspace is added
405        */
406        void AddHalfspace(PolygonContainer &cell,
407                                          vector<Plane3> &planes,
408                                          vector<bool> &sides,
409                                          const Plane3 &halfspace,
410                                          const bool side) const;
411
412        /** Returns true if merge criteria are reached.
413        */
414    bool ShouldMerge(BspLeaf *front, BspLeaf *back) const;
415
416        /** Merges view cells based on some criteria
417            E.g., empty view cells can pe purged, view cells which have
418                a very similar PVS can be merged to one larger view cell.
419
420                @returns true if merge was successful.
421        */
422        bool MergeViewCells(BspLeaf *front, BspLeaf *back) const;
423
424        /** Traverses tree and counts PVS size of all view cells
425        */
426        int CountViewCellPvs() const;
427
428protected:
429
430        // --------------------------------------------------------------
431        // For sorting objects
432        // --------------------------------------------------------------
433        struct SortableEntry
434        {
435                enum {POLY_MIN, POLY_MAX};
436   
437                int type;
438                float value;
439                Polygon3 *poly;
440                SortableEntry() {}
441                SortableEntry(const int t, const float v, Polygon3 *poly):
442                type(t), value(v), poly(poly) {}
443               
444                bool operator<(const SortableEntry &b) const
445                {
446                        return value < b.value;
447                } 
448        };
449
450        /** Evaluates tree stats in the BSP tree leafs.
451        */
452        void EvaluateLeafStats(const BspTraversalData &data);
453
454        /** Subdivides node with respect to the traversal data.
455            @param tStack current traversal stack
456                @param tData traversal data also holding node to be subdivided
457                @returns new root of the subtree
458        */
459        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData);
460
461        /** Constructs the tree from the given list of polygons and rays.
462                @param polys stores set of polygons on which subdivision may be based
463                @param rays storesset of rays on which subdivision may be based
464        */
465        void Construct(PolygonContainer *polys, BoundedRayContainer *rays);
466
467        /** Selects the best possible splitting plane.
468                @param leaf the leaf to be split
469                @param polys the polygon list on which the split decition is based
470                @param rays ray container on which selection may be based
471                @note the polygons can be reordered in the process
472                @returns the split plane
473        */
474        Plane3 SelectPlane(BspLeaf *leaf,
475                                           PolygonContainer &polys,
476                                           const BoundedRayContainer &ray);
477
478        /** Evaluates the contribution of the candidate split plane.
479               
480                @param canditatePlane the candidate split plane
481                @param polys the polygons the split can be based on
482                @param rays the rays the split can be based on
483                @returns the cost of the candidate split plane
484        */
485        float SplitPlaneCost(const Plane3 &candidatePlane,
486                                                 const PolygonContainer &polys,                                                 
487                                                 const BoundedRayContainer &rays) const;
488
489        /** Strategies where the effect of the split plane is tested
490            on all input rays.
491                @returns the cost of the candidate split plane
492        */
493        float SplitPlaneCost(const Plane3 &candidatePlane,
494                                                 const PolygonContainer &polys) const;
495
496        /** Strategies where the effect of the split plane is tested
497            on all input polygons.
498                @returns the cost of the candidate split plane
499        */
500        float SplitPlaneCost(const Plane3 &candidatePlane,
501                                                 const BoundedRayContainer &polys) const;
502
503        /** Filters next view cell down the tree and inserts it into the appropriate leaves
504                (i.e., possibly more than one leaf).
505        */
506        void InsertViewCell(ViewCell *viewCell);
507        /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,
508                then further subdivided.
509        */
510        void InsertPolygons(PolygonContainer *polys);
511
512        /** Subdivide leaf.
513                @param leaf the leaf to be subdivided
514               
515                @param polys the polygons to be split
516                @param frontPolys returns the polygons in front of the split plane
517                @param backPolys returns the polygons in the back of the split plane
518               
519                @param rays the polygons to be filtered
520                @param frontRays returns the polygons in front of the split plane
521                @param backRays returns the polygons in the back of the split plane
522
523                @returns the root of the subdivision
524        */
525        BspInterior *SubdivideNode(BspLeaf *leaf,
526                                                           PolygonContainer &polys,
527                                                           PolygonContainer &frontPolys,
528                                                           PolygonContainer &backPolys,
529                                                           PolygonContainer &coincident,
530                                                           BoundedRayContainer &rays,
531                                                           BoundedRayContainer &frontRays,
532                                                           BoundedRayContainer &backRays);
533
534        /** Filters polygons down the tree.
535                @param node the current BSP node
536                @param polys the polygons to be filtered
537                @param frontPolys returns the polygons in front of the split plane
538                @param backPolys returns the polygons in the back of the split plane
539        */
540        void FilterPolygons(BspInterior *node,
541                                                PolygonContainer *polys,
542                                                PolygonContainer *frontPolys,
543                                                PolygonContainer *backPolys);
544
545        /** Selects the split plane in order to construct a tree with
546                certain characteristics (e.g., balanced tree, least splits,
547                2.5d aligned)
548                @param polygons container of polygons
549                @param rays bundle of rays on which the split can be based
550                @param maxTests the maximal number of candidate tests
551        */
552        Plane3 SelectPlaneHeuristics(PolygonContainer &polys,
553                                                                 const BoundedRayContainer &rays,
554                                                                 const int maxTests);
555
556        /** Extracts the meshes of the objects and adds them to polygons.
557                Adds object aabb to the aabb of the tree.
558                @param maxPolys the maximal number of objects to be stored as polygons
559                @returns the number of polygons
560        */
561        int AddToPolygonSoup(const ObjectContainer &objects,
562                                                 PolygonContainer &polys,
563                                                 int maxObjects = 0);
564
565        /** Extracts the meshes of the view cells and and adds them to polygons.
566                Adds view cell aabb to the aabb of the tree.
567                @param maxPolys the maximal number of objects to be stored as polygons
568                @returns the number of polygons
569        */
570        int AddToPolygonSoup(const ViewCellContainer &viewCells,
571                                                 PolygonContainer &polys,
572                                                 int maxObjects = 0);
573
574        /** Extract polygons of this mesh and add to polygon container.
575                @param mesh the mesh that drives the polygon construction
576                @param parent the parent intersectable this polygon is constructed from
577                @returns number of polygons
578        */
579        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
580
581        /** returns next candidate index and reorders polygons so no candidate is chosen two times
582                @param the current candidate index
583                @param max the range of candidates
584        */
585        int GetNextCandidateIdx(int currentIdx, PolygonContainer &polys);
586
587        /** Helper function which extracts a view cell on the front and the back
588                of the split plane.
589                @param backViewCell returns view cell on the back of the split plane
590                @param frontViewCell returns a view cell on the front of the split plane
591                @param coincident container of polygons coincident to the split plane
592                @param splitPlane the split plane which decides about back and front
593                @param extractBack if a back view cell is extracted
594                @param extractFront if a front view cell is extracted
595        */
596        void ExtractViewCells(ViewCell **backViewCell,
597                                                  ViewCell **frontViewCell,
598                                                  const PolygonContainer &coincident,
599                                                  const Plane3 splitPlane,
600                                                  const bool extractBack,
601                                                  const bool extractFront) const;
602       
603        /** Computes best cost ratio for the suface area heuristics for axis aligned
604                splits. This heuristics minimizes the cost for ray traversal.
605                @param polys the polygons guiding the ratio computation
606                @param box the bounding box of the leaf
607                @param axis the current split axis
608                @param position returns the split position
609                @param objectsBack the number of objects in the back of the split plane
610                @param objectsFront the number of objects in the front of the split plane
611        */
612        float BestCostRatio(const PolygonContainer &polys,
613                                                const AxisAlignedBox3 &box,
614                                                const int axis,
615                                                float &position,
616                                                int &objectsBack,
617                                                int &objectsFront) const;
618       
619        /** Sorts split candidates for surface area heuristics for axis aligned splits.
620                @param polys the input for choosing split candidates
621                @param axis the current split axis
622                @param splitCandidates returns sorted list of split candidates
623        */
624        void SortSplitCandidates(const PolygonContainer &polys,
625                                                         const int axis,
626                                                         vector<SortableEntry> &splitCandidates) const;
627
628        /** Selects an axis aligned split plane.
629                Returns true if split is valied
630        */
631        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
632
633        /** Bounds ray and returns minT and maxT.
634                @returns true if ray hits BSP tree bounding box
635        */
636        bool BoundRay(const Ray &ray, float &minT, float &maxT) const;
637
638        /** Subdivides the rays into front and back rays according to the split plane.
639               
640                @param plane the split plane
641                @param rays contains the rays to be split. The rays are
642                           distributed into front and back rays.
643                @param frontRays returns rays on the front side of the plane
644                @param backRays returns rays on the back side of the plane
645               
646                @returns the number of splits
647        */
648        int SplitRays(const Plane3 &plane,
649                                  BoundedRayContainer &rays,
650                              BoundedRayContainer &frontRays,
651                                  BoundedRayContainer &backRays);
652
653
654        /** Extracts the split planes representing the space bounded by node n.
655        */
656        void ExtractSplitPlanes(BspNode *n, vector<Plane3 *> &planes, vector<bool> &sides) const;
657
658        int CountPvs(const BoundedRayContainer &rays) const;
659       
660        float PvsValue(Intersectable &obj,
661                                   const int cf,
662                                   const int frontId,
663                                   const int backId,
664                                   const int frontAndBackId) const;
665       
666        /// Pointer to the root of the tree
667        BspNode *mRoot;
668
669        /// Pointer to the root cell of the viewspace
670        // ViewCell *mRootCell;
671               
672        BspTreeStatistics mStat;
673
674        /// Strategies for choosing next split plane.
675        enum {NO_STRATEGY = 0,
676                  RANDOM_POLYGON = 1,
677                  AXIS_ALIGNED = 2,
678                  LEAST_SPLITS = 4,
679                  BALANCED_POLYS = 8,
680                  BALANCED_VIEW_CELLS = 16,
681                  LARGEST_POLY_AREA = 32,
682                  VERTICAL_AXIS = 64,
683                  BLOCKED_RAYS = 128,
684                  LEAST_RAY_SPLITS = 256,
685                  BALANCED_RAYS = 512,
686                  PVS = 1024
687                };
688
689        /// box around the whole view domain
690        AxisAlignedBox3 mBox;
691
692        /// view cell corresponding to unbounded space
693        ViewCell *mRootCell;
694
695        /// should view cells be stored or generated in the leaves?
696        bool mGenerateViewCells;
697
698        /// if rays should be stored that are piercing this view cell
699        bool mStorePiercingRays;
700
701public:
702        /// Parses the environment and stores the global BSP tree parameters
703        static void ParseEnvironment();
704
705        /// maximal number of polygons before subdivision termination
706        static int sTermMaxPolygons;
707        /// maximal number of rays before subdivision termination
708        static int sTermMaxRays;
709        /// maximal possible depth
710        static int sTermMaxDepth;
711        /// strategy to get the best split plane
712        static int sSplitPlaneStrategy;
713        /// number of candidates evaluated for the next split plane
714        static int sMaxCandidates;
715        /// BSP tree construction method
716        static int sConstructionMethod;
717        /// maximal number of polygons for axis aligned split
718        static int sTermMaxPolysForAxisAligned;
719        /// maximal number of rays for axis aligned split
720        static int sTermMaxRaysForAxisAligned;
721        /// maximal number of objects for axis aligned split
722        static int sTermMaxObjectsForAxisAligned;
723
724        /// axis aligned split criteria
725        static float sCt_div_ci;
726        static float sSplitBorder;
727        static float sMaxCostRatio;
728
729        // factors guiding the split plane heuristics
730        static float sLeastSplitsFactor;
731        static float sBalancedPolysFactor;
732        static float sBalancedViewCellsFactor;
733        static float sVerticalSplitsFactor;
734        static float sLargestPolyAreaFactor;
735        static float sBlockedRaysFactor;
736        static float sLeastRaySplitsFactor;
737        static float sBalancedRaysFactor;
738        static float sPvsFactor;
739
740        /// if polygons should be stored in the tree
741        static bool sStoreSplitPolys;
742
743        /// threshold where view cells are merged
744        static int sMinPvsDif;
745
746private:
747        /** Evaluates split plane classification with respect to the plane's
748                contribution for a balanced tree.
749        */
750        static float sLeastPolySplitsTable[4];
751        /** Evaluates split plane classification with respect to the plane's
752                contribution for a minimum number splits in the tree.
753        */
754        static float sBalancedPolysTable[4];
755        /** Evaluates split plane classification with respect to the plane's
756                contribution for a minimum number of ray splits.
757        */
758        static float sLeastRaySplitsTable[5];
759        /** Evaluates split plane classification with respect to the plane's
760                contribution for balanced rays.
761        */
762        static float sBalancedRaysTable[5];
763
764};
765
766#endif
Note: See TracBrowser for help on using the repository browser.