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

Revision 1008, 28.8 KB checked in by mattausch, 18 years ago (diff)

worked on vsp osp tree. warning: does not compile

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