source: obsolete/trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h @ 611

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