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

Revision 727, 28.5 KB checked in by mattausch, 19 years ago (diff)

added view cell description bsp tree

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