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

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