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

Revision 485, 24.5 KB checked in by mattausch, 19 years ago (diff)

changed castlinesegment of vspbpstree
changed rayinfo ray classification for bsp tree
implemented shuffling

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