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

Revision 590, 26.8 KB checked in by mattausch, 19 years ago (diff)

implemented some code for merge history loading

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