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

Revision 648, 27.4 KB checked in by mattausch, 19 years ago (diff)

removed problems with bsp due to polygons equal to scene box faces. removing
this polyogns in a preprocessing step. also using this for vsp bsp tree, because it
is generally a good thing.

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