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

#ifndef _VspBspTree_H__
#define _VspBspTree_H__

#include "Mesh.h"
#include "Containers.h"
#include "Polygon3.h"
#include <stack>
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "ViewCellBsp.h"



namespace GtpVisibilityPreprocessor {

class ViewCellLeaf;
//class BspViewCell;
class Plane3;
class VspBspTree;  
class BspInterior;
class BspNode;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;
//class Environment;

/**
        This is a view space partitioning specialised BSPtree.  
        There are no polygon splits, but we split the sample rays. 
        The candidates for the next split plane are evaluated only 
        by checking the sampled visibility information. 
        The polygons are employed merely as candidates for the next split planes.
*/
class VspBspTree 
{
        friend class ViewCellsParseHandlers;
        friend class VspBspViewCellsManager;
public:
        
        /** Additional data which is passed down the BSP tree during traversal.
        */
        class VspBspTraversalData
        {  
        public:
                /// the current node
                BspNode *mNode;
                /// polygonal data for splitting
                PolygonContainer *mPolygons;
                /// current depth
                int mDepth;
                /// rays piercing this node
                RayInfoContainer *mRays;
                /// the probability that this node contains view point
                float mProbability;
                /// geometry of node as induced by planes
                BspNodeGeometry *mGeometry;
                /// pvs size
                int mPvs;
                /// how often this branch has missed the max-cost ratio
                int mMaxCostMisses;
                /// if this node is a kd-node (i.e., boundaries are axis aligned
                bool mIsKdNode;
                // current axis
                int mAxis;
                // current priority
                float mPriority;

                
                /** Returns average ray contribution.
                */
                float GetAvgRayContribution() const
                {
                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
                }


                VspBspTraversalData():
                mNode(NULL),
                mPolygons(NULL),
                mDepth(0),
                mRays(NULL),
                mPvs(0),
                mProbability(0.0),
                mGeometry(NULL),
                mMaxCostMisses(0), 
                mIsKdNode(false),
                mPriority(0),
                mAxis(0)
                {}
                
                VspBspTraversalData(BspNode *node, 
                                                        PolygonContainer *polys, 
                                                        const int depth, 
                                                        RayInfoContainer *rays,
                                                        const int pvs,
                                                        const float p,
                                                        BspNodeGeometry *geom): 
                mNode(node), 
                mPolygons(polys), 
                mDepth(depth), 
                mRays(rays),
                mPvs(pvs),
                mProbability(p),
                mGeometry(geom),
                mMaxCostMisses(0),
                mIsKdNode(false),
                mPriority(0),
                mAxis(0)
                {}

                VspBspTraversalData(PolygonContainer *polys, 
                                                        const int depth, 
                                                        RayInfoContainer *rays,
                                                        BspNodeGeometry *geom): 
                mNode(NULL), 
                mPolygons(polys), 
                mDepth(depth), 
                mRays(rays),
                mPvs(0),
                mProbability(0),
                mGeometry(geom),
                mMaxCostMisses(0),
                mIsKdNode(false),
                mAxis(0)
                {}

                /** Returns priority of the traversal data.
                */
                float GetCost() const
                {
                        //cout << mPriority << endl;
                        return mPriority;
                }

                // deletes contents and sets them to NULL
                void Clear()
                {
                        DEL_PTR(mPolygons);
                        DEL_PTR(mRays);
                        DEL_PTR(mGeometry);
                }

                friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
                {
                        return a.GetCost() < b.GetCost();
                }
    };
        

        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
        
        
        struct VspBspSplitCandidate
        {  
                /// the current split plane
                Plane3 mSplitPlane;
                /// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned)
                int mSplitAxis;
                /// the number of misses of max cost ratio until this split
                int mMaxCostMisses;

                // parent data
                VspBspTraversalData mParentData;
                // prioriry of this split
                float mPriority;

                float mRenderCostDecr;

                VspBspSplitCandidate(): mPriority(0), mRenderCostDecr(0) 
                {};

                VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
                mSplitPlane(plane), mParentData(tData), mPriority(0), mRenderCostDecr(0) 
                {}

                /** Returns cost of the traversal data.
                */
                float GetPriority() const
                {
#if 1
                        return mPriority;
#else
                        return (float) (-mDepth); // for kd tree
#endif
                }

                friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b)
                {
                        return a.GetPriority() < b.GetPriority();
                }
    };

        typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue;

        /** Default constructor creating an empty tree.
        */ 
        VspBspTree();

        /** Default destructor.
        */
        ~VspBspTree();

        /** Returns BSP Tree statistics.
        */
        const BspTreeStatistics &GetStatistics() const; 
  

        /** Constructs the tree from a given set of rays.
                @param sampleRays the set of sample rays the construction is based on
                @param forcedBoundingBox overwrites the view space box
        */
        void Construct(const VssRayContainer &sampleRays,
                                   AxisAlignedBox3 *forcedBoundingBox);

        /** Returns list of BSP leaves with pvs smaller than
                a certain threshold.
                @param onlyUnmailed if only the unmailed leaves should be considered
                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
        */
        void CollectLeaves(vector<BspLeaf *> &leaves, 
                                           const bool onlyUnmailed = false,
                                           const int maxPvs = -1) const;

        /** Returns box which bounds the whole tree.
        */
        AxisAlignedBox3 GetBoundingBox() const;

        /** Returns root of BSP tree.
        */
        BspNode *GetRoot() const;

        /** Collects the leaf view cells of the tree
                @param viewCells returns the view cells 
        */
        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;

        /** A ray is cast possible intersecting the tree.
                @param the ray that is cast.
                @returns the number of intersections with objects stored in the tree.
        */
        int CastRay(Ray &ray);

        /// bsp tree construction types
        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};

        /** finds neighbouring leaves of this tree node.
        */
        int FindNeighbors(BspNode *n, 
                                          vector<BspLeaf *> &neighbors, 
                                          const bool onlyUnmailed) const;

        /** Constructs geometry associated with the half space intersections 
                leading to this node.
        */
        void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
        
        /** Construct geometry of view cell.
        */
        void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;

        /** Returns random leaf of BSP tree.
                @param halfspace defines the halfspace from which the leaf is taken.
        */
        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);

        /** Returns random leaf of BSP tree.
                @param onlyUnmailed if only unmailed leaves should be returned.
        */
        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);

        /** Returns epsilon of this tree.
        */
        float GetEpsilon() const;

        /** Casts line segment into the tree.
                @param origin the origin of the line segment
                @param termination the end point of the line segment
                @returns view cells intersecting the line segment.
        */
    int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells);

                
        /** Sets pointer to view cells manager.
        */
        void SetViewCellsManager(ViewCellsManager *vcm);

        /** Returns distance from node 1 to node 2.
        */
        int TreeDistance(BspNode *n1, BspNode *n2) const;

        /** Collapses the tree with respect to the view cell partition.
                @returns number of collapsed nodes
        */
        int CollapseTree();

        /** Returns view cell the current point is located in.
                @param point the current view point
                @param active if currently active view cells should be returned or
                elementary view cell
        */
        ViewCell *GetViewCell(const Vector3 &point, const bool active = false);


        /** Returns true if this view point is in a valid view space,
                false otherwise.
        */
        bool ViewPointValid(const Vector3 &viewPoint) const;

        /** Returns view cell corresponding to 
                the invalid view space.
        */
        BspViewCell *GetOutOfBoundsCell();

        /** Writes tree to output stream
        */
#if ZIPPED_VIEWCELLS
        bool Export(ogzstream &stream);
#else
        bool Export(ofstream &stream);
#endif

        /** Casts beam, i.e. a 5D frustum of rays, into tree.
                Tests conservative using the bounding box of the nodes.
                @returns number of view cells it intersected
        */
        int CastBeam(Beam &beam);

        /** Finds approximate neighbours, i.e., finds correct neighbors
                in most cases but sometimes more.
        */
        int FindApproximateNeighbors(BspNode *n, 
                                                             vector<BspLeaf *> &neighbors,
                                                                 const bool onlyUnmailed) const;

        /** Checks if tree validity-flags are right 
                with respect to view cell valitiy.
                If not, marks subtree as invalid.
        */
        void ValidateTree();

        /** Invalid view cells are added to the unbounded space
        */
        void CollapseViewCells();

        /** Collects rays stored in the leaves.
        */
        void CollectRays(VssRayContainer &rays);

        /** Intersects box with the tree and returns the number of intersected boxes.
                @returns number of view cells found
        */
        int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;

        /// pointer to the hierarchy of view cells
        ViewCellsTree *mViewCellsTree;


protected:

        // --------------------------------------------------------------
        // For sorting objects
        // --------------------------------------------------------------
        struct SortableEntry
        {
                enum EType 
                {
                        ERayMin,
                        ERayMax
                };

                int type;
                float value;
                VssRay *ray;
  
                SortableEntry() {}
                SortableEntry(const int t, const float v, VssRay *r):type(t),
                                          value(v), ray(r) 
                {
                }
                
                friend bool operator<(const SortableEntry &a, const SortableEntry &b) 
                {
                        return a.value < b.value;
                }
        };

        void ComputeBoundingBox(const VssRayContainer &sampleRays, 
                                                        AxisAlignedBox3 *forcedBoundingBox);

        /** faster evaluation of split plane cost for kd axis aligned cells.
        */
        float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
                                                                   const AxisAlignedBox3 &box,
                                                                   const int axis,
                                                                   const float &position,
                                                                   float &pFront,
                                                                   float &pBack) const;

        /** Evaluates candidate for splitting.
        */
        void EvalSplitCandidate(VspBspSplitCandidate &splitData);

        /** Computes priority of the traversal data and stores it in tData.
        */
        void EvalPriority(VspBspTraversalData &tData) const;

        /** Evaluates render cost decrease of next split.
        */
        float EvalRenderCostDecrease(const Plane3 &candidatePlane,
                                                                 const VspBspTraversalData &data,
                                                                 float &normalizedOldRenderCost) const;

        /** Constructs tree using the split priority queue.
        */
        void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays);

        /** Collects view cells in the subtree under root.
        */
        void CollectViewCells(BspNode *root, 
                                                  bool onlyValid, 
                                                  ViewCellContainer &viewCells,
                                                  bool onlyUnmailed = false) const;

        /** Returns view cell corresponding to 
                the invalid view space. If it does not exist, it is created.
        */
        BspViewCell *GetOrCreateOutOfBoundsCell();

        /** Collapses the tree with respect to the view cell partition,
                i.e. leaves having the same view cell are collapsed.
                @param node the root of the subtree to be collapsed
                @param collapsed returns the number of collapsed nodes
                @returns node of type leaf if the node could be collapsed, 
                this node otherwise
        */
        BspNode *CollapseTree(BspNode *node, int &collapsed);

        /** Helper function revalidating the view cell leaf list after merge.
        */
        void RepairViewCellsLeafLists();

        /** Evaluates tree stats in the BSP tree leafs.
        */
        void EvaluateLeafStats(const VspBspTraversalData &data);

        /** Subdivides node with respect to the traversal data.
            @param tStack current traversal stack
                @param tData traversal data also holding node to be subdivided
                @returns new root of the subtree
        */
        BspNode *Subdivide(VspBspTraversalQueue &tStack, 
                                           VspBspTraversalData &tData);

        /** Subdivides node using a best split priority queue.
            @param tQueue the best split priority queue
                @param splitCandidate the candidate for the next split
                @returns new root of the subtree
        */
        BspNode *Subdivide(VspBspSplitQueue &tQueue,
                                           VspBspSplitCandidate &splitCandidate);

        /** Constructs the tree from the given traversal data.
                @param polys stores set of polygons on which subdivision may be based
                @param rays stores set of rays on which subdivision may be based
        */
        void Construct(const PolygonContainer &polys, RayInfoContainer *rays);

        /** Selects the best possible splitting plane. 
                @param plane returns the split plane
                @param leaf the leaf to be split
                @param data the traversal data holding the polygons and rays which the split decision is based
                @param frontData the front node traversal data (which may be updated to avoid repcomputations
                @param backData the front node traversal data (which may be updated to avoid repcomputations
                @param splitAxis 0 - 2 if axis aligned split, 3 if polygon-aligned split

                @note the polygons can be reordered in the process
                
                @returns true if the cost of the split is under maxCostRatio

        */
        bool SelectPlane(Plane3 &plane, 
                                         BspLeaf *leaf, 
                                         VspBspTraversalData &data,
                                         VspBspTraversalData &frontData,
                                         VspBspTraversalData &backData,
                                         int &splitAxis);
        
        /** Strategies where the effect of the split plane is tested
            on all input rays.

                @returns the cost of the candidate split plane
        */
        float EvalSplitPlaneCost(const Plane3 &candidatePlane, 
                                                         const VspBspTraversalData &data,
                                                         BspNodeGeometry &geomFront,
                                                         BspNodeGeometry &geomBack,
                                                         float &pFront,
                                                         float &pBack) const;

        /** Subdivides leaf.
                        
                @param tData data object holding, e.g., a pointer to the leaf
                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
                @param backData returns the data (e.g.,  pointer to the leaf) in the back of the split plane
                
                @param rays the polygons to be filtered
                @param frontRays returns the polygons in front of the split plane
                @param coincident returns the polygons which are coincident to the plane and thus discarded 
                for traversal

                @returns the root of the subdivision
        */

        BspInterior *SubdivideNode(const Plane3 &splitPlane,
                                                           VspBspTraversalData &tData,
                                                           VspBspTraversalData &frontData,
                               VspBspTraversalData &backData,
                                                           PolygonContainer &coincident);

        /** Extracts the meshes of the objects and adds them to polygons. 
                Adds object aabb to the aabb of the tree.
                @param maxPolys the maximal number of objects to be stored as polygons
                @returns the number of polygons
        */
        int AddToPolygonSoup(const ObjectContainer &objects, 
                                                 PolygonContainer &polys, 
                                                 int maxObjects = 0);

        /** Extracts the meshes of the view cells and and adds them to polygons.
                Adds view cell aabb to the aabb of the tree.
                @param maxPolys the maximal number of objects to be stored as polygons
                @returns the number of polygons
        */
        int AddToPolygonSoup(const ViewCellContainer &viewCells, 
                                                 PolygonContainer &polys, 
                                                 int maxObjects = 0);

        /** Extract polygons of this mesh and add to polygon container.
                @param mesh the mesh that drives the polygon construction
                @param parent the parent intersectable this polygon is constructed from
                @returns number of polygons
        */
        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);

        /** Selects an axis aligned for the next split.
                @returns cost for this split
        */
        float SelectAxisAlignedPlane(Plane3 &plane, 
                                                                 const VspBspTraversalData &tData,
                                                                 int &axis,
                                                                 BspNodeGeometry **frontGeom,
                                                                 BspNodeGeometry **backGeom,
                                                                 float &pFront,
                                                                 float &pBack,
                                                                 const bool useKdSplit);

        /** Sorts split candidates for cost heuristics using axis aligned splits.
                @param polys the input for choosing split candidates
                @param axis the current split axis
                @param splitCandidates returns sorted list of split candidates
        */
        void SortSplitCandidates(const RayInfoContainer &rays, 
                                                         const int axis, 
                                                         float minBand, 
                                                         float maxBand);

        /** Computes best cost for axis aligned planes.
        */
        float BestCostRatioHeuristics(const RayInfoContainer &rays,
                                                                  const AxisAlignedBox3 &box,
                                                                  const int pvsSize,
                                                                  const int axis,
                                                                  float &position);

        /** Subdivides the rays into front and back rays according to the split plane.
                
                @param plane the split plane
                @param rays contains the rays to be split. The rays are 
                           distributed into front and back rays.
                @param frontRays returns rays on the front side of the plane
                @param backRays returns rays on the back side of the plane
                
                @returns the number of splits
        */
        int SplitRays(const Plane3 &plane,
                                  RayInfoContainer &rays, 
                              RayInfoContainer &frontRays, 
                                  RayInfoContainer &backRays) const;


        /** Extracts the split planes representing the space bounded by node n.
        */
        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;

        /** Adds the object to the pvs of the front and back leaf with a given classification.

                @param obj the object to be added
                @param cf the ray classification regarding the split plane
                @param frontPvs returns the PVS of the front partition
                @param backPvs returns the PVS of the back partition
        
        */
        void AddObjToPvs(Intersectable *obj, 
                                         const int cf, 
                                         float &frontPvs, 
                                         float &backPvs, 
                                         float &totalPvs) const;
        
        /** Computes PVS size induced by the rays.
        */
        int ComputePvsSize(const RayInfoContainer &rays) const;

        /** Returns true if tree can be terminated.
        */
        inline bool LocalTerminationCriteriaMet(const VspBspTraversalData &data) const;

        /** Returns true if global tree can be terminated.
        */
        inline bool GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const;

        /** Computes accumulated ray lenght of this rays.
        */
        float AccumulatedRayLength(const RayInfoContainer &rays) const;

        /** Splits polygons with respect to the split plane.

                @param plane the split plane
                @param polys the polygons to be split. the polygons are consumed and
                           distributed to the containers frontPolys, backPolys, coincident.
                @param frontPolys returns the polygons in the front of the split plane
                @param backPolys returns the polygons in the back of the split plane
                @param coincident returns the polygons coincident to the split plane

                @returns the number of splits   
        */
        int SplitPolygons(const Plane3 &plane,
                                          PolygonContainer &polys, 
                                          PolygonContainer &frontPolys, 
                                          PolygonContainer &backPolys, 
                                          PolygonContainer &coincident) const;

        /** Adds ray sample contributions to the PVS.
                @param sampleContributions the number contributions of the samples
                @param contributingSampels the number of contributing rays
                
        */
        void AddToPvs(BspLeaf *leaf,
                                  const RayInfoContainer &rays, 
                                  float &sampleContributions,
                                  int &contributingSamples);

        
        /** Take 3 ray endpoints, where two are minimum and one a maximum
                point or the other way round.
        */
        Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;

        /** Take plane normal as plane normal and the midpoint of the ray.
                PROBLEM: does not resemble any point where visibility is 
                likely to change
        */
        Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;

        /** Fit the plane between the two lines so that the plane 
                has equal shortest distance to both lines.
        */
        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
  
        /** Collects candidates for merging.
                @param leaves the leaves to be merged
                @returns number of leaves in queue
        */
        int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);

        /** Collects candidates for the merge in the merge queue.
                @returns number of leaves in queue
        */
        int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
        
        /** Preprocesses polygons and throws out all polygons which are coincident to
                the view space box faces (they can be problematic).
        */
        void PreprocessPolygons(PolygonContainer &polys);
        
        /** Propagates valid flag up the tree.
        */
        void PropagateUpValidity(BspNode *node);

        /** Writes the node to disk
                @note: should be implemented as visitor.
        */
#if ZIPPED_VIEWCELLS
        void ExportNode(BspNode *node, ogzstream &stream);
#else
        void ExportNode(BspNode *node, ofstream &stream);
#endif

        /** Returns estimated memory usage of tree.
        */
        float GetMemUsage() const;
        //float GetMemUsage(const VspBspTraversalQueue &tstack) const;


        void EvalSubdivisionStats(const VspBspTraversalData &tData,
                                                      const VspBspTraversalData &tFrontData,
                                                          const VspBspTraversalData &tBackData
                                                          );

        /** Adds stats to subdivision log file.
        */
        void AddSubdivisionStats(const int viewCells,
                                                         const float renderCostDecr,
                                                         const float splitCandidateCost,
                                                         const float totalRenderCost,
                                                         const float avgRenderCost);

        ///////////////////////////////////////////////////////////


protected:
        
        /// Pointer to the root of the tree
        BspNode *mRoot;
        
        /// the pointer to the view cells manager
        ViewCellsManager *mViewCellsManager;
        
        /// View cell corresponding to the space outside the valid view space
        BspViewCell *mOutOfBoundsCell;

        /// the bsp tree statistics
        BspTreeStatistics mBspStats;

        /// sorted split candidates used for sweep-heuristics
        vector<SortableEntry> *mLocalSplitCandidates;

        /// box around the whole view domain
        AxisAlignedBox3 mBox;

        
        //-- termination critera

        /// minimal number of rays before subdivision termination
        int mTermMinRays;
        /// maximal possible depth
        int mTermMaxDepth;
        /// mininum probability
        float mTermMinProbability;
        /// mininum PVS
        int mTermMinPvs;
        /// maximal contribution per ray
        float mTermMaxRayContribution;
        /// minimal accumulated ray length
        float mTermMinAccRayLength;
        /// maximal acceptable cost ratio
        float mTermMaxCostRatio;
        /// tolerance value indicating how often the max cost ratio can be failed
        int mTermMissTolerance;


        //-- termination criteria for
        //-- hybrid stategy where only axis aligned split are used until 
        //-- a certain point and then also polygon aligned split are taken
         
        /// minimal number of rays where axis aligned split is taken
        int mTermMinRaysForAxisAligned;
        /// max ray contribution
        float mTermMaxRayContriForAxisAligned;
        /// weight for heuristics evaluation
        float mAxisAlignedCtDivCi;
        /// spezifies the split border of the axis aligned split
        float mAxisAlignedSplitBorder;


        //-- global terminatino criteria

        float mTermMinGlobalCostRatio;
        int mTermGlobalCostMissTolerance;
        int mGlobalCostMisses;

        /// maximal number of view cells
        int mMaxViewCells;
        /// maximal tree memory
        float mMaxMemory;
        /// the tree is out of memory
        bool mOutOfMemory;


        /// number of candidates evaluated for the next split plane
        int mMaxPolyCandidates;
        /// number of candidates for split planes evaluated using the rays
        int mMaxRayCandidates;
        


        //-- axis aligned split criteria

        /// if only driving axis should be used for choosing the axis-aligned split
        bool mOnlyDrivingAxis;
        /// if heuristics should be used to place the split plane of an axis-aligned split
        bool mUseCostHeuristics;
        /// if driving axis should taken if max cost is exceeded for
        /// all evaluated axis aligned split plane candidates
        bool mUseDrivingAxisIfMaxCostViolated;
        /// minimal relative position where the split axis can be placed
        float mMinBand;
        /// maximal relative position where the split axis can be placed
        float mMaxBand;
        /// balancing factor for PVS criterium
        float mCtDivCi;
        /// if random split axis should be used
        bool mUseRandomAxis;
        /// if vsp bsp tree should simulate octree
        bool mCirculatingAxis;


        
        /// priority queue strategy
        enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED};
        /// if we should use breath first priority for the splits
        int mNodePriorityQueueType;
        /// if split cost queue should be used to compute next best split
        bool mUseSplitCostQueue;
        

        
        /// Strategies for choosing next split plane.
        enum {NO_STRATEGY = 0,
                  RANDOM_POLYGON = 1, 
                  AXIS_ALIGNED = 2,
                  LEAST_RAY_SPLITS = 256,
                  BALANCED_RAYS = 512,
                  PVS = 1024
                };

        /// strategy to get the best split plane
        int mSplitPlaneStrategy;

        //-- factors guiding the split plane heuristics

        float mLeastRaySplitsFactor;
        float mBalancedRaysFactor;
        float mPvsFactor;


        /// if area or volume should be used for PVS heuristics
        bool mUseAreaForPvs;
        /// tolerance for polygon split
        float mEpsilon;
        /// maximal number of test rays used to evaluate candidate split plane
        int mMaxTests;
        /// normalizes different bsp split plane criteria
        float mCostNormalizer;
        // if rays should be stored in leaves
        bool mStoreRays;
        /// weight between  render cost (expected value) and variance
        float mRenderCostWeight;
        /// weight between  render cost decrease and node render cost
        float mRenderCostDecreaseWeight;

        //-- subdivision statistics

        /// subdivision stats output file
        ofstream mSubdivisionStats;
        float mTotalCost;
        int mTotalPvsSize;


        /// use polygon split whenever there are polys left
        bool mUsePolygonSplitIfAvailable;
        /// current time stamp (used for keeping split history)
        int mTimeStamp;
        /// number of currenly generated view cells
        int mCreatedViewCells;


private:

        /// Generates unique ids for PVS criterium
        static void GenerateUniqueIdsForPvs();

        //-- unique ids for PVS criterium
        static int sFrontId; 
        static int sBackId;
        static int sFrontAndBackId;
};

}


#endif