source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h @ 663

Revision 663, 22.5 KB checked in by mattausch, 19 years ago (diff)
Line 
1#ifndef _VspBspTree_H__
2#define _VspBspTree_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 "RayInfo.h"
11#include "ViewCellBsp.h"
12
13class ViewCell;
14//class BspViewCell;
15class Plane3;
16class VspBspTree; 
17class BspInterior;
18class BspNode;
19class AxisAlignedBox3;
20class Ray;
21class ViewCellsStatistics;
22class ViewCellsManager;
23class MergeCandidate;
24class Beam;
25class ViewCellsTree;
26
27
28struct BspRay;
29
30//#define OCTREE_HACK 0
31/**
32        This is a view space partitioning specialised BSPtree. 
33        There are no polygon splits, but we split the sample rays.
34        The candidates for the next split plane are evaluated only
35        by checking the sampled visibility information.
36        The polygons are employed merely as candidates for the next split planes.
37*/
38class VspBspTree
39{
40        friend class ViewCellsParseHandlers;
41        friend class VspBspViewCellsManager;
42public:
43       
44        /** Additional data which is passed down the BSP tree during traversal.
45        */
46        class VspBspTraversalData
47        { 
48        public:
49                /// the current node
50                BspNode *mNode;
51                /// polygonal data for splitting
52                PolygonContainer *mPolygons;
53                /// current depth
54                int mDepth;
55                /// rays piercing this node
56                RayInfoContainer *mRays;
57                /// the probability that this node contains view point
58                float mProbability;
59                /// geometry of node as induced by planes
60                BspNodeGeometry *mGeometry;
61                /// pvs size
62                int mPvs;
63                /// how often this branch has missed the max-cost ratio
64                int mMaxCostMisses;
65                /// if this node is a kd-node (i.e., boundaries are axis aligned
66                bool mIsKdNode;
67                // hack for octree
68                int mAxis;
69                float mPriority;
70
71                static bool sBreathFirstSplits;
72
73                /** Returns average ray contribution.
74                */
75                float GetAvgRayContribution() const
76                {
77                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
78                }
79
80
81                VspBspTraversalData():
82                mNode(NULL),
83                mPolygons(NULL),
84                mDepth(0),
85                mRays(NULL),
86                mPvs(0),
87                mProbability(0.0),
88                mGeometry(NULL),
89                mMaxCostMisses(0),
90                mIsKdNode(false)
91                {}
92               
93                VspBspTraversalData(BspNode *node,
94                                                        PolygonContainer *polys,
95                                                        const int depth,
96                                                        RayInfoContainer *rays,
97                                                        const int pvs,
98                                                        const float p,
99                                                        BspNodeGeometry *geom):
100                mNode(node),
101                mPolygons(polys),
102                mDepth(depth),
103                mRays(rays),
104                mPvs(pvs),
105                mProbability(p),
106                mGeometry(geom),
107                mMaxCostMisses(0),
108                mIsKdNode(false)
109                {}
110
111                VspBspTraversalData(PolygonContainer *polys,
112                                                        const int depth,
113                                                        RayInfoContainer *rays,
114                                                        BspNodeGeometry *geom):
115                mNode(NULL),
116                mPolygons(polys),
117                mDepth(depth),
118                mRays(rays),
119                mPvs(0),
120                mProbability(0),
121                mGeometry(geom),
122                mMaxCostMisses(0),
123                mIsKdNode(false)
124                {}
125
126                /** Returns cost of the traversal data.
127                */
128                float GetCost() const
129                {
130                        if (sBreathFirstSplits)
131                                return mPvs * mProbability;
132                        else
133                                return (float) (-mDepth); // for kd tree
134                }
135
136                // deletes contents and sets them to NULL
137                void Clear()
138                {
139                        DEL_PTR(mPolygons);
140                        DEL_PTR(mRays);
141                        DEL_PTR(mGeometry);
142                }
143
144                friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
145                {
146                        return a.GetCost() < b.GetCost();
147                }
148    };
149       
150
151        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
152       
153       
154        struct VspBspSplitCandidate
155        { 
156                /// the current node
157                Plane3 mSplitPlane;
158                /// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned)
159                int mSplitAxis;
160                /// the number of misses of max cost ratio until this split
161                int mMaxCostMisses;
162
163                // parent data
164                VspBspTraversalData mParentData;
165                // cost of applying this split
166                float mRenderCost;
167
168                VspBspSplitCandidate(): mRenderCost(0)
169                {};
170
171                VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData):
172                mSplitPlane(plane), mParentData(tData), mRenderCost(0)
173                {}
174
175                /** Returns cost of the traversal data.
176                */
177                float GetCost() const
178                {
179#if 1
180                        return mRenderCost;
181#endif
182#if 0
183                        return (float) (-mDepth); // for kd tree
184#endif
185                }
186
187                friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b)
188                {
189                        return a.GetCost() < b.GetCost();
190                }
191    };
192
193        typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue;
194
195        /** Default constructor creating an empty tree.
196        */
197        VspBspTree();
198
199        /** Default destructor.
200        */
201        ~VspBspTree();
202
203        /** Returns BSP Tree statistics.
204        */
205        const BspTreeStatistics &GetStatistics() const;
206 
207
208        /** Constructs the tree from a given set of rays.
209                @param sampleRays the set of sample rays the construction is based on
210                @param viewCells if not NULL, new view cells are
211                created in the leafs and stored in the container
212        */
213        void Construct(const VssRayContainer &sampleRays,
214                                   AxisAlignedBox3 *forcedBoundingBox);
215
216        /** Returns list of BSP leaves with pvs smaller than
217                a certain threshold.
218                @param onlyUnmailed if only the unmailed leaves should be considered
219                @param maxPvs the maximal pvs (-1 means unlimited)
220        */
221        void CollectLeaves(vector<BspLeaf *> &leaves,
222                                           const bool onlyUnmailed = false,
223                                           const int maxPvs = -1) const;
224
225        /** Returns box which bounds the whole tree.
226        */
227        AxisAlignedBox3 GetBoundingBox()const;
228
229        /** Returns root of BSP tree.
230        */
231        BspNode *GetRoot() const;
232
233        /** Collects the leaf view cells of the tree
234                @param viewCells returns the view cells
235        */
236        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
237
238        /** A ray is cast possible intersecting the tree.
239                @param the ray that is cast.
240                @returns the number of intersections with objects stored in the tree.
241        */
242        int CastRay(Ray &ray);
243
244        /// bsp tree construction types
245        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
246
247        /** finds neighbouring leaves of this tree node.
248        */
249        int FindNeighbors(BspNode *n,
250                                          vector<BspLeaf *> &neighbors,
251                                          const bool onlyUnmailed) const;
252
253        /** Constructs geometry associated with the half space intersections
254                leading to this node.
255        */
256        void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
257       
258        /** Construct geometry of view cell.
259        */
260        void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;
261
262        /** Returns random leaf of BSP tree.
263                @param halfspace defines the halfspace from which the leaf is taken.
264        */
265        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
266
267        /** Returns random leaf of BSP tree.
268                @param onlyUnmailed if only unmailed leaves should be returned.
269        */
270        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
271
272        /** Returns epsilon of this tree.
273        */
274        float GetEpsilon() const;
275
276        /** Casts line segment into the tree.
277                @param origin the origin of the line segment
278                @param termination the end point of the line segment
279                @returns view cells intersecting the line segment.
280        */
281    int CastLineSegment(const Vector3 &origin,
282                                                const Vector3 &termination,
283                                                ViewCellContainer &viewcells);
284
285               
286        /** Sets pointer to view cells manager.
287        */
288        void SetViewCellsManager(ViewCellsManager *vcm);
289
290        /** Returns distance from node 1 to node 2.
291        */
292        int TreeDistance(BspNode *n1, BspNode *n2) const;
293
294        /** Collapses the tree with respect to the view cell partition.
295                @returns number of collapsed nodes
296        */
297        int CollapseTree();
298
299        /** Returns view cell the current point is located in.
300        */
301        ViewCell *GetViewCell(const Vector3 &point);
302
303
304        /** Returns true if this view point is in a valid view space,
305                false otherwise.
306        */
307        bool ViewPointValid(const Vector3 &viewPoint) const;
308
309        /** Returns view cell corresponding to
310                the invalid view space.
311        */
312        BspViewCell *GetOutOfBoundsCell();
313
314        /** Writes tree to output stream
315        */
316        bool Export(ofstream &stream);
317
318        /** Casts beam, i.e. a 5D frustum of rays, into tree.
319                Tests conservative using the bounding box of the nodes.
320                @returns number of view cells it intersected
321        */
322        int CastBeam(Beam &beam);
323
324        void CollectViewCells(BspNode *root,
325                                                  bool onlyValid,
326                                                  ViewCellContainer &viewCells,
327                                                  bool onlyUnmailed = false) const;
328
329       
330        int FindApproximateNeighbors(BspNode *n,
331                                                             vector<BspLeaf *> &neighbors,
332                                                                 const bool onlyUnmailed) const;
333
334        /** Checks if tree validity-flags are right
335                with respect to view cell valitiy.
336                If not, marks subtree as invalid.
337        */
338        void ValidateTree();
339
340        /** Invalid view cells are added to the unbounded space
341        */
342        void CollapseViewCells();
343
344        /** Collects rays stored in the leaves.
345        */
346        void CollectRays(VssRayContainer &rays);
347
348
349        ViewCellsTree *mViewCellsTree;
350
351
352protected:
353
354        // --------------------------------------------------------------
355        // For sorting objects
356        // --------------------------------------------------------------
357        struct SortableEntry
358        {
359                enum EType
360                {
361                        ERayMin,
362                        ERayMax
363                };
364
365                int type;
366                float value;
367                VssRay *ray;
368 
369                SortableEntry() {}
370                SortableEntry(const int t, const float v, VssRay *r):type(t),
371                                          value(v), ray(r)
372                {
373                }
374               
375                friend bool operator<(const SortableEntry &a, const SortableEntry &b)
376                {
377                        return a.value < b.value;
378                }
379        };
380
381        /** faster evaluation of split plane cost for kd axis aligned cells.
382        */
383        float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
384                                                                   const AxisAlignedBox3 &box,
385                                                                   const int axis,
386                                                                   const float &position,
387                                                                   float &pFront,
388                                                                   float &pBack) const;
389
390        void EvalSplitCandidate(VspBspTraversalData &tData, VspBspSplitCandidate &splitData);
391
392        float EvalRenderCostDecrease(const Plane3 &candidatePlane,
393                                                                 const VspBspTraversalData &data) const;
394
395        void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays);
396
397
398        /** Returns view cell corresponding to
399                the invalid view space. If it does not exist, it is created.
400        */
401        BspViewCell *GetOrCreateOutOfBoundsCell();
402
403        /** Collapses the tree with respect to the view cell partition,
404                i.e. leaves having the same view cell are collapsed.
405                @param node the root of the subtree to be collapsed
406                @param collapsed returns the number of collapsed nodes
407                @returns node of type leaf if the node could be collapsed,
408                this node otherwise
409        */
410        BspNode *CollapseTree(BspNode *node, int &collapsed);
411
412        /** Helper function revalidating the view cell leaf list after merge.
413        */
414        void RepairViewCellsLeafLists();
415
416        /** Evaluates tree stats in the BSP tree leafs.
417        */
418        void EvaluateLeafStats(const VspBspTraversalData &data);
419
420        /** Subdivides node with respect to the traversal data.
421            @param tStack current traversal stack
422                @param tData traversal data also holding node to be subdivided
423                @returns new root of the subtree
424        */
425        BspNode *Subdivide(VspBspTraversalQueue &tStack,
426                                           VspBspTraversalData &tData);
427
428        BspNode *Subdivide(VspBspSplitQueue &tQueue,
429                                           VspBspSplitCandidate &splitCandidate);
430
431        /** Constructs the tree from the given traversal data.
432                @param polys stores set of polygons on which subdivision may be based
433                @param rays storesset of rays on which subdivision may be based
434        */
435        void Construct(const PolygonContainer &polys, RayInfoContainer *rays);
436
437        /** Selects the best possible splitting plane.
438                @param plane returns the split plane
439                @param leaf the leaf to be split
440                @param polys the polygon list on which the split decition is based
441                @param rays ray container on which selection may be based
442                @note the polygons can be reordered in the process
443                @returns true if the cost of the split is under maxCostRatio
444
445        */
446        bool SelectPlane(Plane3 &plane,
447                                         BspLeaf *leaf,
448                                         VspBspTraversalData &data,
449                                         VspBspTraversalData &frontData,
450                                         VspBspTraversalData &backData,
451                                         int &splitAxis);
452       
453        /** Strategies where the effect of the split plane is tested
454            on all input rays.
455
456                @returns the cost of the candidate split plane
457        */
458        float EvalSplitPlaneCost(const Plane3 &candidatePlane,
459                                                         const VspBspTraversalData &data,
460                                                         BspNodeGeometry &geomFront,
461                                                         BspNodeGeometry &geomBack,
462                                                         float &pFront,
463                                                         float &pBack) const;
464
465        /** Subdivides leaf.
466                @param leaf the leaf to be subdivided
467               
468                @param polys the polygons to be split
469                @param frontPolys returns the polygons in front of the split plane
470                @param backPolys returns the polygons in the back of the split plane
471               
472                @param rays the polygons to be filtered
473                @param frontRays returns the polygons in front of the split plane
474                @param backRays returns the polygons in the back of the split plane
475
476                @returns the root of the subdivision
477        */
478
479        BspInterior *SubdivideNode(const Plane3 &splitPlane,
480                                                           VspBspTraversalData &tData,
481                                                           VspBspTraversalData &frontData,
482                               VspBspTraversalData &backData,
483                                                           PolygonContainer &coincident);
484
485        /** Extracts the meshes of the objects and adds them to polygons.
486                Adds object aabb to the aabb of the tree.
487                @param maxPolys the maximal number of objects to be stored as polygons
488                @returns the number of polygons
489        */
490        int AddToPolygonSoup(const ObjectContainer &objects,
491                                                 PolygonContainer &polys,
492                                                 int maxObjects = 0);
493
494        /** Extracts the meshes of the view cells and and adds them to polygons.
495                Adds view cell aabb to the aabb of the tree.
496                @param maxPolys the maximal number of objects to be stored as polygons
497                @returns the number of polygons
498        */
499        int AddToPolygonSoup(const ViewCellContainer &viewCells,
500                                                 PolygonContainer &polys,
501                                                 int maxObjects = 0);
502
503        /** Extract polygons of this mesh and add to polygon container.
504                @param mesh the mesh that drives the polygon construction
505                @param parent the parent intersectable this polygon is constructed from
506                @returns number of polygons
507        */
508        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
509
510        /** Selects an axis aligned for the next split.
511                @returns cost for this split
512        */
513        float SelectAxisAlignedPlane(Plane3 &plane,
514                                                                 const VspBspTraversalData &tData,
515                                                                 int &axis,
516                                                                 BspNodeGeometry **frontGeom,
517                                                                 BspNodeGeometry **backGeom,
518                                                                 float &pFront,
519                                                                 float &pBack,
520                                                                 const bool useKdSplit);
521
522        /** Sorts split candidates for surface area heuristics for axis aligned splits.
523                @param polys the input for choosing split candidates
524                @param axis the current split axis
525                @param splitCandidates returns sorted list of split candidates
526        */
527        void SortSplitCandidates(const RayInfoContainer &rays, const int axis);
528
529        /** Computes best cost for axis aligned planes.
530        */
531        float BestCostRatioHeuristics(const RayInfoContainer &rays,
532                                                                  const AxisAlignedBox3 &box,
533                                                                  const int pvsSize,
534                                                                  const int &axis,
535                                                                  float &position);
536
537        /** Selects an axis aligned split plane.
538                @Returns true if split is valied
539        */
540        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
541
542        /** Subdivides the rays into front and back rays according to the split plane.
543               
544                @param plane the split plane
545                @param rays contains the rays to be split. The rays are
546                           distributed into front and back rays.
547                @param frontRays returns rays on the front side of the plane
548                @param backRays returns rays on the back side of the plane
549               
550                @returns the number of splits
551        */
552        int SplitRays(const Plane3 &plane,
553                                  RayInfoContainer &rays,
554                              RayInfoContainer &frontRays,
555                                  RayInfoContainer &backRays) const;
556
557
558        /** Extracts the split planes representing the space bounded by node n.
559        */
560        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
561
562        /** Adds the object to the pvs of the front and back leaf with a given classification.
563
564                @param obj the object to be added
565                @param cf the ray classification regarding the split plane
566                @param frontPvs returns the PVS of the front partition
567                @param backPvs returns the PVS of the back partition
568       
569        */
570        void AddObjToPvs(Intersectable *obj,
571                                         const int cf,
572                                         int &frontPvs,
573                                         int &backPvs,
574                                         int &totalPvs) const;
575       
576        /** Computes PVS size induced by the rays.
577        */
578        int ComputePvsSize(const RayInfoContainer &rays) const;
579
580        /** Returns true if tree can be terminated.
581        */
582        inline bool LocalTerminationCriteriaMet(const VspBspTraversalData &data) const;
583
584        inline bool GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const;
585
586        /** Computes accumulated ray lenght of this rays.
587        */
588        float AccumulatedRayLength(const RayInfoContainer &rays) const;
589
590        /** Splits polygons with respect to the split plane.
591
592                @param plane the split plane
593                @param polys the polygons to be split. the polygons are consumed and
594                           distributed to the containers frontPolys, backPolys, coincident.
595                @param frontPolys returns the polygons in the front of the split plane
596                @param backPolys returns the polygons in the back of the split plane
597                @param coincident returns the polygons coincident to the split plane
598
599                @returns the number of splits   
600        */
601        int SplitPolygons(const Plane3 &plane,
602                                          PolygonContainer &polys,
603                                          PolygonContainer &frontPolys,
604                                          PolygonContainer &backPolys,
605                                          PolygonContainer &coincident) const;
606
607        /** Adds ray sample contributions to the PVS.
608                @param sampleContributions the number contributions of the samples
609                @param contributingSampels the number of contributing rays
610               
611        */
612        void AddToPvs(BspLeaf *leaf,
613                                  const RayInfoContainer &rays,
614                                  float &sampleContributions,
615                                  int &contributingSamples);
616
617
618
619
620
621       
622        /** Take 3 ray endpoints, where two are minimum and one a maximum
623                point or the other way round.
624        */
625        Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;
626
627        /** Take plane normal as plane normal and the midpoint of the ray.
628                PROBLEM: does not resemble any point where visibility is
629                likely to change
630        */
631        Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
632
633        /** Fit the plane between the two lines so that the plane
634                has equal shortest distance to both lines.
635        */
636        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
637 
638        /** Collects candidates for merging.
639                @param leaves the leaves to be merged
640                @returns number of leaves in queue
641        */
642        int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
643
644        /** Collects candidates for the merge in the merge queue.
645                @returns number of leaves in queue
646        */
647        int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
648       
649        /** Preprocesses polygons and throws out all polygons which are coincident to
650                the view space box faces (they can be problematic).
651        */
652        void PreprocessPolygons(PolygonContainer &polys);
653       
654        /** Propagates valid flag up the tree.
655        */
656        void PropagateUpValidity(BspNode *node);
657
658        /** Writes the node to disk
659                @note: should be implemented as visitor
660        */
661        void ExportNode(BspNode *node, ofstream &stream);
662
663        /** Returns estimated memory usage of tree.
664        */
665        //float GetMemUsage(const VspBspTraversalQueue &tstack) const;
666        float GetMemUsage() const;
667
668
669
670        /// Pointer to the root of the tree
671        BspNode *mRoot;
672               
673        BspTreeStatistics mBspStats;
674
675        /// Strategies for choosing next split plane.
676        enum {NO_STRATEGY = 0,
677                  RANDOM_POLYGON = 1,
678                  AXIS_ALIGNED = 2,
679                  LEAST_RAY_SPLITS = 256,
680                  BALANCED_RAYS = 512,
681                  PVS = 1024
682                };
683
684        /// box around the whole view domain
685        AxisAlignedBox3 mBox;
686
687        bool mUseCostHeuristics;
688
689        /// minimal number of rays before subdivision termination
690        int mTermMinRays;
691        /// maximal possible depth
692        int mTermMaxDepth;
693        /// mininum probability
694        float mTermMinProbability;
695        /// mininum PVS
696        int mTermMinPvs;
697        /// maximal contribution per ray
698        float mTermMaxRayContribution;
699        /// minimal accumulated ray length
700        float mTermMinAccRayLength;
701
702        //HACK
703        int mTermMinPolygons;
704
705        float mTermMinGlobalCostRatio;
706        int mTermGlobalCostMissTolerance;
707
708        int mGlobalCostMisses;
709
710        bool mUseSplitCostQueue;
711        //-- termination criteria for axis aligned split
712
713        /// minimal number of rays for axis aligned split
714        int mTermMinRaysForAxisAligned;
715        // max ray contribution
716        float mTermMaxRayContriForAxisAligned;
717
718        /// strategy to get the best split plane
719        int mSplitPlaneStrategy;
720        /// number of candidates evaluated for the next split plane
721        int mMaxPolyCandidates;
722        /// number of candidates for split planes evaluated using the rays
723        int mMaxRayCandidates;
724        /// balancing factor for PVS criterium
725        float mCtDivCi;
726
727        //-- axis aligned split criteria
728        float mAxisAlignedCtDivCi;
729        /// spezifies the split border of the axis aligned split
730        float mAxisAlignedSplitBorder;
731
732        /// maximal acceptable cost ratio
733        float mTermMaxCostRatio;
734        /// tolerance value indicating how often the max cost ratio can be failed
735        int mTermMissTolerance;
736
737        //-- factors guiding the split plane heuristics
738        float mLeastRaySplitsFactor;
739        float mBalancedRaysFactor;
740        float mPvsFactor;
741
742        /// if area or volume should be used for PVS heuristics
743        bool mUseAreaForPvs;
744        /// tolerance for polygon split
745        float mEpsilon;
746        /// maximal number of test rays used to evaluate candidate split plane
747        int mMaxTests;
748        /// normalizes different bsp split plane criteria
749        float mCostNormalizer;
750        /// maximal number of view cells
751        int mMaxViewCells;
752       
753        ofstream  mSubdivisionStats;
754
755        // if rays should be stored in leaves
756        bool mStoreRays;
757       
758        /// if only driving axis should be used for split
759        bool mOnlyDrivingAxis;
760
761        ViewCellsManager *mViewCellsManager;
762
763        vector<SortableEntry> *mSplitCandidates;
764
765       
766        float mRenderCostWeight;
767        /// View cell corresponding to the space outside the valid view space
768        BspViewCell *mOutOfBoundsCell;
769
770        /// maximal tree memory
771        float mMaxMemory;
772        /// the tree is out of memory
773        bool mOutOfMemory;
774       
775        float mTotalCost;
776        int mTotalPvsSize;
777
778        //int mSplits;
779        /// subdivision stats output file
780        ofstream mSubdivsionStats;
781        /// if random split axis should be used
782        bool mUseRandomAxis;
783        /// use polygon split whenever there are polys left
784        bool mUsePolygonSplitIfAvailable;
785        /// current time stamp (used for keeping split history)
786        int mTimeStamp;
787        /// number of currenly generated view cells
788        int mCreatedViewCells;
789        /// if vsp bsp tree should simulate octree
790        bool mSimulateOctree;
791
792        int mBreathFirstSplits;
793
794private:
795
796
797        static const float sLeastRaySplitsTable[5];
798        /** Evaluates split plane classification with respect to the plane's
799                contribution for balanced rays.
800        */
801        static const float sBalancedRaysTable[5];
802
803        /// Generates unique ids for PVS criterium
804        static void GenerateUniqueIdsForPvs();
805
806        //-- unique ids for PVS criterium
807        static int sFrontId;
808        static int sBackId;
809        static int sFrontAndBackId;
810};
811
812
813
814
815#endif
Note: See TracBrowser for help on using the repository browser.