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

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