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

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