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

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