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

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

debug version for testing subdivision quality

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