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

Revision 547, 25.4 KB checked in by mattausch, 19 years ago (diff)
Line 
1#ifndef _ViewCellBsp_H__
2#define _ViewCellBsp_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 "ViewCell.h"
11
12class ViewCell;
13//class BspViewCell;
14class Plane3;
15class BspTree; 
16class BspInterior;
17//class Polygon3;
18class AxisAlignedBox3;
19class Ray;
20class ViewCellsStatistics;
21
22class BspNodeGeometry
23{
24public:
25        BspNodeGeometry()
26        {}; 
27
28        // copy constructor copying the polygon array
29        BspNodeGeometry(const BspNodeGeometry &rhs);
30
31        ~BspNodeGeometry();
32
33        /** Returns accumulated area of all polygons.
34        */
35        float GetArea() const;
36       
37        float GetVolume() const;
38
39        /** Computes new front and back geometry based on the old cell
40                geometry and a new split plane
41        */
42        void SplitGeometry(BspNodeGeometry &front,
43                                           BspNodeGeometry &back,
44                                           const Plane3 &splitPlane,
45                       const AxisAlignedBox3 &box,
46                                           const float epsilon) const;
47
48        /** Computes bounding box of the geometry.
49        */
50        void IncludeInBox(AxisAlignedBox3 &box);
51
52        /** Splits the polygon and returns the part of the polygon inside of the node geometry.
53        */
54        Polygon3 *SplitPolygon(Polygon3 *poly, const float epsilon) const;
55
56        /** Adds node geometry to mesh.
57                @note the mesh vertices will not be connected
58        */
59        void AddToMesh(Mesh &mesh);
60
61        /** Computes mass center of bsp node geometry.
62        */
63        Vector3 CenterOfMass() const;
64
65        /** The polygons the geometry consists of.
66        */
67        PolygonContainer mPolys;
68};
69
70/** Data structure used for optimized ray casting.
71*/
72struct BspRayTraversalData
73{
74    BspNode *mNode;
75    Vector3 mExitPoint;
76    float mMaxT;
77   
78    BspRayTraversalData() {}
79
80    BspRayTraversalData(BspNode *n, const Vector3 &extp, const float maxt):
81    mNode(n), mExitPoint(extp), mMaxT(maxt)
82        {}
83
84        BspRayTraversalData(BspNode *n, const Vector3 &extp):
85        mNode(n), mExitPoint(extp)
86        {}
87};
88
89/** Data used for passing ray data down the tree.
90*/
91struct BoundedRay
92{
93        Ray *mRay;
94        float mMinT;
95        float mMaxT;
96               
97        BoundedRay(): mMinT(0), mMaxT(1e6), mRay(NULL)
98        {}
99        BoundedRay(Ray *r, float minT, float maxT):
100        mRay(r), mMinT(minT), mMaxT(maxT)
101        {}
102};
103
104typedef vector<BoundedRay *> BoundedRayContainer;
105
106class BspTreeStatistics: public StatisticsBase
107{
108public:
109        // total number of nodes
110        int nodes;
111        // number of splits
112        int splits[3];
113       
114        // totals number of rays
115        int rays;
116        // maximal reached depth
117        int maxDepth;
118        // minimal depth
119        int minDepth;
120       
121        // max depth nodes
122        int maxDepthNodes;
123        // minimum depth nodes
124        int minDepthNodes;
125        // max depth nodes
126        int minPvsNodes;
127        // nodes with minimum PVS
128        int minRaysNodes;
129        // max ray contribution nodes
130        int maxRayContribNodes;
131        // minimum area nodes
132        int minProbabilityNodes;
133        /// nodes termination because of max cost ratio;
134        int maxCostNodes;
135        // max number of rays per node
136        int maxObjectRefs;
137        // accumulated depth (used to compute average)
138        int accumDepth;
139        // number of initial polygons
140        int polys;
141        /// samples contributing to pvs
142        int contributingSamples;
143        /// sample contributions to pvs
144        int sampleContributions;
145        /// largest pvs
146        int maxPvs;
147        /// number of invalid leaves
148        int invalidLeaves;
149        /// polygon splits
150        int polySplits;
151        /// accumulated number of rays refs
152        int accumRays;
153
154        // Constructor
155        BspTreeStatistics()
156        {
157                Reset();
158        }
159
160        int Nodes() const {return nodes;}
161        int Interior() const { return nodes / 2; }
162        int Leaves() const { return (nodes / 2) + 1; }
163       
164        // TODO: computation wrong
165        double AvgDepth() const { return accumDepth / (double)Leaves();};
166        double AvgRays() const { return accumRays / (double)Leaves();};
167
168        void Reset()
169        {
170                nodes = 0;
171                for (int i = 0; i < 3; ++ i)
172                        splits[i] = 0;
173               
174                maxDepth = 0;
175                minDepth = 99999;
176                polys = 0;
177                accumDepth = 0;
178       
179                maxDepthNodes = 0;
180                minPvsNodes = 0;
181                minRaysNodes = 0;
182                maxRayContribNodes = 0;
183                minProbabilityNodes = 0;
184                maxCostNodes = 0;
185
186                contributingSamples = 0;
187                sampleContributions = 0;
188
189                maxPvs = 0;
190                invalidLeaves = 0;
191                polySplits = 0;
192                accumRays = 0;
193        }
194
195        void Print(ostream &app) const;
196
197        friend ostream &operator<<(ostream &s, const BspTreeStatistics &stat)
198        {
199                stat.Print(s);
200                return s;
201        }
202};
203
204
205/**
206    BspNode abstract class serving for interior and leaf node implementation
207*/
208class BspNode
209{
210        friend class BspTree;
211
212public:
213        BspNode();
214        virtual ~BspNode(){};
215        BspNode(BspInterior *parent);
216
217        /** Determines whether this node is a leaf or not
218        @return true if leaf
219        */
220        virtual bool IsLeaf() const = 0;
221
222        /** Determines whether this node is a root
223        @return true if root
224        */
225        virtual bool IsRoot() const;
226
227        /** Returns parent node.
228        */
229        BspInterior *GetParent();
230
231        /** Sets parent node.
232        */
233        void SetParent(BspInterior *parent);
234
235        /** Returns true if this node is a sibling of node n.
236        */
237        bool IsSibling(BspNode *n) const;
238
239        /** returns depth of the node.
240        */
241        int GetDepth() const;
242
243        /** returns true if the whole subtree is valid
244        */
245        bool TreeValid() const;
246
247        void SetTreeValid(const bool v);
248
249        //-- mailing options
250
251        void Mail() { mMailbox = sMailId; }
252        static void NewMail() { ++ sMailId; }
253        bool Mailed() const { return mMailbox == sMailId; }
254
255        static int sMailId;
256        int mMailbox;
257
258protected:
259
260        /// if this sub tree is a completely valid view space region
261        bool mTreeValid;
262        /// parent of this node
263        BspInterior *mParent;
264};
265
266/** BSP interior node implementation
267*/
268class BspInterior : public BspNode
269{
270        friend class BspTree;
271public:
272        /** Standard contructor taking split plane as argument.
273        */
274        BspInterior(const Plane3 &plane);
275        ~BspInterior();
276        /** @return false since it is an interior node
277        */
278        bool IsLeaf() const;
279
280        BspNode *GetBack();
281        BspNode *GetFront();
282
283        /** Returns split plane.
284        */
285        Plane3 GetPlane() const;
286
287        /** Replace front or back child with new child.
288        */
289        void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
290        /** Replace front and back child.
291        */
292        void SetupChildLinks(BspNode *b, BspNode *f);
293
294        friend ostream &operator<<(ostream &s, const BspInterior &A)
295        {
296                return s << A.mPlane;
297        }
298
299protected:
300
301        /// Splitting plane corresponding to this node
302        Plane3 mPlane;
303
304        /// back node
305        BspNode *mBack;
306        /// front node
307        BspNode *mFront;
308};
309
310/** BSP leaf node implementation.
311*/
312class BspLeaf: public BspNode
313{
314        friend class BspTree;
315
316public:
317        BspLeaf();
318        BspLeaf(BspViewCell *viewCell);
319        BspLeaf(BspInterior *parent);
320        BspLeaf(BspInterior *parent, BspViewCell *viewCell);
321
322        ~BspLeaf();
323
324        /** @return true since it is an interior node
325        */
326        bool IsLeaf() const;
327       
328        /** Returns pointer of view cell.
329        */
330        BspViewCell *GetViewCell() const;
331
332        /** Sets pointer to view cell.
333        */
334        void SetViewCell(BspViewCell *viewCell);
335
336        /// Rays piercing this leaf.
337        VssRayContainer mVssRays;
338       
339        /// leaf pvs
340        ObjectPvs *mPvs;
341
342        /// Probability that the view point lies in this leaf
343        float mProbability;
344
345protected:
346       
347        /// if NULL this does not correspond to feasible viewcell
348        BspViewCell *mViewCell;
349};
350
351/** Implementation of the view cell BSP tree.
352*/
353class BspTree
354{
355public:
356       
357        /** Additional data which is passed down the BSP tree during traversal.
358        */
359        struct BspTraversalData
360        { 
361                /// the current node
362                BspNode *mNode;
363                /// polygonal data for splitting
364                PolygonContainer *mPolygons;
365                /// current depth
366                int mDepth;
367                /// the view cell associated with this subdivsion
368                ViewCell *mViewCell;
369                /// rays piercing this node
370                BoundedRayContainer *mRays;
371                /// area of current node
372                float mArea;
373                /// geometry of node as induced by planes
374                BspNodeGeometry *mGeometry;
375               
376                /// pvs size
377                int mPvs;
378               
379                /** Returns average ray contribution.
380                */
381                float GetAvgRayContribution() const
382                {
383                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
384                }
385
386
387                BspTraversalData():
388                mNode(NULL),
389                mPolygons(NULL),
390                mDepth(0),
391                mViewCell(NULL),
392                mRays(NULL),
393                mPvs(0),
394                mArea(0.0),
395                mGeometry(NULL)
396                {}
397               
398                BspTraversalData(BspNode *node,
399                                                 PolygonContainer *polys,
400                                                 const int depth,
401                                                 ViewCell *viewCell,
402                                                 BoundedRayContainer *rays,
403                                                 int pvs,
404                                                 float area,
405                                                 BspNodeGeometry *cell):
406                mNode(node),
407                mPolygons(polys),
408                mDepth(depth),
409                mViewCell(viewCell),
410                mRays(rays),
411                mPvs(pvs),
412                mArea(area),
413                mGeometry(cell)
414                {}
415    };
416       
417        typedef std::stack<BspTraversalData> BspTraversalStack;
418       
419        /** Default constructor reading the environment file and
420                creating an empty tree.
421        */
422        BspTree();
423        /** Destroys tree and nodes.
424        */
425        ~BspTree();
426
427        /** Returns detailed statistics of the BSP tree.
428        */
429        const BspTreeStatistics &GetStatistics() const;
430 
431        /** Constructs tree using the given list of view cells.
432            For this type of construction we filter all view cells down the
433                tree. If there is no polygon left, the last split plane
434            decides inside or outside of the viewcell. A pointer to the
435                appropriate view cell is stored within each leaf.
436                Many leafs can point to the same viewcell.
437        */
438        void Construct(const ViewCellContainer &viewCells);
439
440        /** Constructs tree using the given list of objects.
441            @note the objects are not taken as view cells, but the view cells are
442                constructed from the subdivision: Each leaf is taken as one viewcell.
443                @param objects list of objects
444        */
445        void Construct(const ObjectContainer &objects);
446
447        void Construct(const ObjectContainer &objects,
448                                   const RayContainer &sampleRays);
449
450        /** Constructs the tree from a given set of rays.
451                @param sampleRays the set of sample rays the construction is based on
452                @param viewCells if not NULL, new view cells are
453                created in the leafs and stored in the conatainer
454        */
455        void Construct(const RayContainer &sampleRays);
456
457        /** Returns list of BSP leaves.
458        */
459        void CollectLeaves(vector<BspLeaf *> &leaves) const;
460
461        /** Returns box which bounds the whole tree.
462        */
463        AxisAlignedBox3 GetBoundingBox()const;
464
465        /** Returns root of BSP tree.
466        */
467        BspNode *GetRoot() const;
468
469        /** Exports Bsp tree to file.
470        */
471        bool Export(const string filename);
472
473        /** Collects the leaf view cells of the tree
474                @param viewCells returns the view cells
475        */
476        void CollectViewCells(ViewCellContainer &viewCells) const;
477
478        /** A ray is cast possible intersecting the tree.
479                @param the ray that is cast.
480                @returns the number of intersections with objects stored in the tree.
481        */
482        int     _CastRay(Ray &ray);
483
484
485        int     CastLineSegment(const Vector3 &origin,
486                                                const Vector3 &termination,
487                                                ViewCellContainer &viewcells
488                                                );
489
490        ViewCell *GetViewCell(const Vector3 &point);
491 
492        /// bsp tree construction types
493        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
494
495        /** Returns statistics.
496        */
497        BspTreeStatistics &GetStat();
498
499        /** finds neighbouring leaves of this tree node.
500        */
501        int FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
502                                          const bool onlyUnmailed) const;
503
504        /** Constructs geometry of view cell returning a BSP node geometry type.
505        */
506        void ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const;
507       
508        /** Construct geometry of view cell.
509        */
510        void ConstructGeometry(BspViewCell *vc, BspNodeGeometry &geom) const;
511
512        /** Returns random leaf of BSP tree.
513                @param halfspace defines the halfspace from which the leaf is taken.
514        */
515        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
516
517        /** Returns random leaf of BSP tree.
518                @param onlyUnmailed if only unmailed leaves should be returned.
519        */
520        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
521
522        /** Returns view cell corresponding to unbounded space.
523        */
524        BspViewCell *GetRootCell() const;
525
526        /** Returns epsilon of this tree.
527        */
528        float GetEpsilon() const;
529
530protected:
531
532        // --------------------------------------------------------------
533        // For sorting objects
534        // --------------------------------------------------------------
535        struct SortableEntry
536        {
537                enum {POLY_MIN, POLY_MAX};
538   
539                int type;
540                float value;
541                Polygon3 *poly;
542                SortableEntry() {}
543                SortableEntry(const int t, const float v, Polygon3 *poly):
544                type(t), value(v), poly(poly) {}
545               
546                bool operator<(const SortableEntry &b) const
547                {
548                        return value < b.value;
549                } 
550        };
551
552        /** Evaluates tree stats in the BSP tree leafs.
553        */
554        void EvaluateLeafStats(const BspTraversalData &data);
555
556        /** Subdivides node with respect to the traversal data.
557            @param tStack current traversal stack
558                @param tData traversal data also holding node to be subdivided
559                @returns new root of the subtree
560        */
561        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData);
562
563        /** Constructs the tree from the given list of polygons and rays.
564                @param polys stores set of polygons on which subdivision may be based
565                @param rays storesset of rays on which subdivision may be based
566        */
567        void Construct(PolygonContainer *polys, BoundedRayContainer *rays);
568
569        /** Selects the best possible splitting plane.
570                @param leaf the leaf to be split
571                @param polys the polygon list on which the split decition is based
572                @param rays ray container on which selection may be based
573                @note the polygons can be reordered in the process
574                @returns the split plane
575        */
576        Plane3 SelectPlane(BspLeaf *leaf,
577                                           BspTraversalData &data);
578
579        /** Evaluates the contribution of the candidate split plane.
580               
581                @param candidatePlane the candidate split plane
582                @param polys the polygons the split can be based on
583                @param rays the rays the split can be based on
584
585                @returns the cost of the candidate split plane
586        */
587        float SplitPlaneCost(const Plane3 &candidatePlane,
588                                                 BspTraversalData &data) const;
589
590        /** Strategies where the effect of the split plane is tested
591            on all input rays.
592                @returns the cost of the candidate split plane
593        */
594        float SplitPlaneCost(const Plane3 &candidatePlane,
595                                                 const PolygonContainer &polys) const;
596
597        /** Strategies where the effect of the split plane is tested
598            on all input rays.
599
600                @returns the cost of the candidate split plane
601        */
602        float SplitPlaneCost(const Plane3 &candidatePlane,
603                                                 const BoundedRayContainer &rays,
604                                                 const int pvs,
605                                                 const float area,
606                                                 const BspNodeGeometry &cell) const;
607
608        /** Filters next view cell down the tree and inserts it into the appropriate leaves
609                (i.e., possibly more than one leaf).
610        */
611        void InsertViewCell(ViewCell *viewCell);
612        /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,
613                then further subdivided.
614        */
615        void InsertPolygons(PolygonContainer *polys);
616
617        /** Subdivide leaf.
618                @param leaf the leaf to be subdivided
619               
620                @param polys the polygons to be split
621                @param frontPolys returns the polygons in front of the split plane
622                @param backPolys returns the polygons in the back of the split plane
623               
624                @param rays the polygons to be filtered
625                @param frontRays returns the polygons in front of the split plane
626                @param backRays returns the polygons in the back of the split plane
627
628                @returns the root of the subdivision
629        */
630
631        BspInterior *SubdivideNode(BspTraversalData &tData,
632                                                           BspTraversalData &frontData,
633                                                           BspTraversalData &backData,
634                                                           PolygonContainer &coincident);
635
636        /** Filters polygons down the tree.
637                @param node the current BSP node
638                @param polys the polygons to be filtered
639                @param frontPolys returns the polygons in front of the split plane
640                @param backPolys returns the polygons in the back of the split plane
641        */
642        void FilterPolygons(BspInterior *node,
643                                                PolygonContainer *polys,
644                                                PolygonContainer *frontPolys,
645                                                PolygonContainer *backPolys);
646
647        /** Take 3 ray endpoints, where two are minimum and one a maximum
648                point or the other way round.
649        */
650        Plane3 ChooseCandidatePlane(const BoundedRayContainer &rays) const;
651
652        /** Take plane normal as plane normal and the midpoint of the ray.
653                PROBLEM: does not resemble any point where visibility is likely to change
654        */
655        Plane3 ChooseCandidatePlane2(const BoundedRayContainer &rays) const;
656
657        /** Fit the plane between the two lines so that the plane has equal shortest
658                distance to both lines.
659        */
660        Plane3 ChooseCandidatePlane3(const BoundedRayContainer &rays) const;
661
662        /** Selects the split plane in order to construct a tree with
663                certain characteristics (e.g., balanced tree, least splits,
664                2.5d aligned)
665                @param polygons container of polygons
666                @param rays bundle of rays on which the split can be based
667        */
668        Plane3 SelectPlaneHeuristics(BspLeaf *leaf,
669                                                                 BspTraversalData &data);
670
671        /** Extracts the meshes of the objects and adds them to polygons.
672                Adds object aabb to the aabb of the tree.
673                @param maxPolys the maximal number of objects to be stored as polygons
674                @returns the number of polygons
675        */
676        int AddToPolygonSoup(const ObjectContainer &objects,
677                                                 PolygonContainer &polys,
678                                                 int maxObjects = 0);
679
680        /** Extracts the meshes of the view cells and and adds them to polygons.
681                Adds view cell aabb to the aabb of the tree.
682                @param maxPolys the maximal number of objects to be stored as polygons
683                @returns the number of polygons
684        */
685        int AddToPolygonSoup(const ViewCellContainer &viewCells,
686                                                 PolygonContainer &polys,
687                                                 int maxObjects = 0);
688
689        /** Extract polygons of this mesh and add to polygon container.
690                @param mesh the mesh that drives the polygon construction
691                @param parent the parent intersectable this polygon is constructed from
692                @returns number of polygons
693        */
694        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
695
696        /** Helper function which extracts a view cell on the front and the back
697                of the split plane.
698                @param backViewCell returns view cell on the back of the split plane
699                @param frontViewCell returns a view cell on the front of the split plane
700                @param coincident container of polygons coincident to the split plane
701                @param splitPlane the split plane which decides about back and front
702                @param extractBack if a back view cell is extracted
703                @param extractFront if a front view cell is extracted
704        */
705        void ExtractViewCells(BspTraversalData &frontData,
706                                                  BspTraversalData &backData,
707                                                  const PolygonContainer &coincident,
708                                                  const Plane3 &splitPlane) const;
709       
710        /** Computes best cost ratio for the suface area heuristics for axis aligned
711                splits. This heuristics minimizes the cost for ray traversal.
712                @param polys the polygons guiding the ratio computation
713                @param box the bounding box of the leaf
714                @param axis the current split axis
715                @param position returns the split position
716                @param objectsBack the number of objects in the back of the split plane
717                @param objectsFront the number of objects in the front of the split plane
718        */
719        float BestCostRatio(const PolygonContainer &polys,
720                                                const AxisAlignedBox3 &box,
721                                                const int axis,
722                                                float &position,
723                                                int &objectsBack,
724                                                int &objectsFront) const;
725       
726        /** Sorts split candidates for surface area heuristics for axis aligned splits.
727                @param polys the input for choosing split candidates
728                @param axis the current split axis
729                @param splitCandidates returns sorted list of split candidates
730        */
731        void SortSplitCandidates(const PolygonContainer &polys,
732                                                         const int axis,
733                                                         vector<SortableEntry> &splitCandidates) const;
734
735        /** Selects an axis aligned split plane.
736                Returns true if split is valied
737        */
738        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
739
740        /** Subdivides the rays into front and back rays according to the split plane.
741               
742                @param plane the split plane
743                @param rays contains the rays to be split. The rays are
744                           distributed into front and back rays.
745                @param frontRays returns rays on the front side of the plane
746                @param backRays returns rays on the back side of the plane
747               
748                @returns the number of splits
749        */
750        int SplitRays(const Plane3 &plane,
751                                  BoundedRayContainer &rays,
752                              BoundedRayContainer &frontRays,
753                                  BoundedRayContainer &backRays);
754
755
756        /** Extracts the split planes representing the space bounded by node n.
757        */
758        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
759
760        /** Adds the object to the pvs of the front and back leaf with a given classification.
761
762                @param obj the object to be added
763                @param cf the ray classification regarding the split plane
764                @param frontPvs returns the PVS of the front partition
765                @param backPvs returns the PVS of the back partition
766       
767        */
768        void AddObjToPvs(Intersectable *obj, const int cf, int &frontPvs, int &backPvs) const;
769
770        /** Computes PVS size induced by the rays.
771        */
772        int ComputePvsSize(const BoundedRayContainer &rays) const;
773
774        /** Returns true if tree can be terminated.
775        */
776        inline bool TerminationCriteriaMet(const BspTraversalData &data) const;
777
778        /** Computes accumulated ray lenght of this rays.
779        */
780        float AccumulatedRayLength(BoundedRayContainer &rays) const;
781
782        /** Splits polygons with respect to the split plane.
783                @param polys the polygons to be split. the polygons are consumed and
784                           distributed to the containers frontPolys, backPolys, coincident.
785                @param frontPolys returns the polygons in the front of the split plane
786                @param backPolys returns the polygons in the back of the split plane
787                @param coincident returns the polygons coincident to the split plane
788
789                @returns the number of splits   
790        */
791        int SplitPolygons(const Plane3 &plane,
792                                          PolygonContainer &polys,
793                                          PolygonContainer &frontPolys,
794                                          PolygonContainer &backPolys,
795                                          PolygonContainer &coincident) const;
796
797        /** Adds ray sample contributions to the PVS.
798                @param sampleContributions the number contributions of the samples
799                @param contributingSampels the number of contributing rays
800               
801        */
802        void AddToPvs(BspLeaf *leaf,
803                                  const BoundedRayContainer &rays,
804                                  int &sampleContributions,     
805                                  int &contributingSamples);
806
807        /// Pointer to the root of the tree.
808        BspNode *mRoot;
809
810        /// Stores statistics during traversal.
811        BspTreeStatistics mStat;
812
813        /// Strategies for choosing next split plane.
814        enum {NO_STRATEGY = 0,
815                  RANDOM_POLYGON = 1,
816                  AXIS_ALIGNED = 2,
817                  LEAST_SPLITS = 4,
818                  BALANCED_POLYS = 8,
819                  BALANCED_VIEW_CELLS = 16,
820                  LARGEST_POLY_AREA = 32,
821                  VERTICAL_AXIS = 64,
822                  BLOCKED_RAYS = 128,
823                  LEAST_RAY_SPLITS = 256,
824                  BALANCED_RAYS = 512,
825                  PVS = 1024
826                };
827
828        /// box around the whole view domain
829        AxisAlignedBox3 mBox;
830
831        /// view cell corresponding to unbounded space
832        BspViewCell *mRootCell;
833
834        /// if view cells should be generated or the given view cells should be used.
835        bool mGenerateViewCells;
836
837        /// maximal number of polygons before subdivision termination
838        int mTermMinPolys;
839        /// maximal number of rays before subdivision termination
840        int mTermMinRays;
841        /// maximal possible depth
842        int mTermMaxDepth;
843        /// mininum area
844        float mTermMinArea;
845        /// mininum PVS
846        int mTermMinPvs;
847
848        /// minimal number of polygons for axis aligned split
849        int mTermMinPolysForAxisAligned;
850        /// minimal number of rays for axis aligned split
851        int mTermMinRaysForAxisAligned;
852        /// minimal number of objects for axis aligned split
853        int mTermMinObjectsForAxisAligned;
854        /// maximal contribution per ray
855        float mTermMaxRayContribution;
856        /// minimal accumulated ray length
857        float mTermMinAccRayLength;
858
859
860        /// strategy to get the best split plane
861        int mSplitPlaneStrategy;
862        /// number of candidates evaluated for the next split plane
863        int mMaxPolyCandidates;
864        /// number of candidates for split planes evaluated using the rays
865        int mMaxRayCandidates;
866        /// maximum tests for split plane evaluation with a single candidate
867        int mMaxTests;
868
869        float mCtDivCi;
870
871        /// axis aligned split criteria
872        float mAxisAlignedCtDivCi;
873        float mSplitBorder;
874        float mMaxCostRatio;
875
876        // factors guiding the split plane heuristics
877        float mVerticalSplitsFactor;
878        float mLargestPolyAreaFactor;
879        float mBlockedRaysFactor;
880        float mLeastRaySplitsFactor;
881        float mBalancedRaysFactor;
882        float mPvsFactor;
883        float mLeastSplitsFactor;
884        float mBalancedPolysFactor;
885        float mBalancedViewCellsFactor;
886
887        /// if area or accumulated ray lenght should be used for PVS heuristics
888        bool mUseAreaForPvs;
889
890        /// epsilon where two points are still considered equal
891        float mEpsilon;
892
893private:
894       
895        /** Evaluates split plane classification with respect to the plane's
896                contribution for a balanced tree.
897        */
898        static const float sLeastPolySplitsTable[4];
899        /** Evaluates split plane classification with respect to the plane's
900                contribution for a minimum number splits in the tree.
901        */
902        static const float sBalancedPolysTable[4];
903        /** Evaluates split plane classification with respect to the plane's
904                contribution for a minimum number of ray splits.
905        */
906        static const float sLeastRaySplitsTable[5];
907        /** Evaluates split plane classification with respect to the plane's
908                contribution for balanced rays.
909        */
910        static const float sBalancedRaysTable[5];
911
912        /// Generates unique ids for PVS criterium
913        static void GenerateUniqueIdsForPvs();
914
915        //-- unique ids for PVS criterium
916        static int sFrontId;
917        static int sBackId;
918        static int sFrontAndBackId;
919};
920
921struct BspIntersection
922{
923        // the point of intersection
924        float mT;
925 
926        BspLeaf *mLeaf;
927 
928        BspIntersection(const float t, BspLeaf *l):
929        mT(t), mLeaf(l) {}
930 
931        BspIntersection() {}
932 
933        bool operator<(const BspIntersection &b) const
934        {
935                return mT < b.mT;
936        }
937};
938
939struct BspRay
940{
941        VssRay *vssRay;
942
943        std::vector<BspIntersection> intersections;
944
945        BspRay(VssRay *ray): vssRay(ray) {}
946};
947
948#endif
Note: See TracBrowser for help on using the repository browser.