source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h @ 1121

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