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

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