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

#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

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

namespace GtpVisibilityPreprocessor {

class ViewCellLeaf;
class Plane3;
class BspTree;  
class BspInterior;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class ViewCellsTree;
class ViewCell;
class ViewCellLeaf;

class BspNodeGeometry
{
public:
        /** Default constructor.
        */
        BspNodeGeometry()
        {};  

        /** copy constructor copying the polygon array.
                The polygons are deeply copied.
        */
        BspNodeGeometry(const BspNodeGeometry &rhs);
        /** This operator uses a deep copy to copy the polygons.
        */
        BspNodeGeometry& operator=(const BspNodeGeometry& p);

        /** Builds node geometry using this polygons. 
                @NOTE The polygons are NOT duplicated, only
                a shallow copy is used.
        */      
    BspNodeGeometry(const PolygonContainer &polys);

        ~BspNodeGeometry();

        /** Returns accumulated area of all polygons.
        */
        float GetArea() const;

        /** Returns volume of this node geometry.
        */
        float GetVolume() const;

        /** Computes new front and back geometry based on the old cell 
                geometry and a new split plane
                @returns true if the geometry is actually split by this plane
        */
        bool SplitGeometry(BspNodeGeometry &front,
                                           BspNodeGeometry &back,
                                           const Plane3 &splitPlane,
                       const AxisAlignedBox3 &box,
                                           const float epsilon) const;

        /** Computes the intersection of the box with the node geometry.
        */
        int ComputeIntersection(const AxisAlignedBox3 &box) const;

        /** Computes bounding box of the geometry.
        */
        void GetBoundingBox(AxisAlignedBox3 &box) const;

        /** Returns 
                1 of geometry in front of plane
                0 if plane intersects geometry,
                -1 if geometry in back of plane
        */
        int Side(const Plane3 &plane, const float eps = 0.0f) const;

        /** Splits the polygon and returns the part of the polygon inside of the node geometry.
        */
        Polygon3 *SplitPolygon(Polygon3 *poly, const float epsilon) const;

        /** Computes mass center of bsp node geometry.
        */
        Vector3 CenterOfMass() const;

        /** Returns true if this geometry is well shaped.
        */
        bool Valid() const;
        
        friend ostream &operator<<(ostream &s, const BspNodeGeometry &a)
        {
                PolygonContainer::const_iterator it, it_end = a.mPolys.end();

                for (it = a.mPolys.begin(); it != it_end; ++ it)
                        s << *(*it) << endl;
                return s << endl;
        }

        /** Number of polygons.
        */
        int Size() const;
        /** Returns the polygons in a container.
        */
        const PolygonContainer &GetPolys();

    /** Adds polygon and plane equation to this geometry.
        */
        void Add(Polygon3 *p, const Plane3 &plane);

        /** Adds node geometry to mesh.
                @note the mesh vertices will not be connected
        */
        friend void IncludeNodeGeomInMesh(const BspNodeGeometry &geom, Mesh &mesh);

protected:
        /** The polygons the geometry consists of.
        */
        PolygonContainer mPolys;

        /** The corresponding set of planes for the polygons.
                Need this because of precision issues.
        */
        vector<Plane3> mPlanes;
};


/** Data structure used for optimized ray casting.
*/
struct BspRayTraversalData 
{
    BspNode *mNode;
    Vector3 mExitPoint;
    float mMaxT;
    
    BspRayTraversalData() {}

    BspRayTraversalData(BspNode *n, const Vector3 &extp, const float maxt):
    mNode(n), mExitPoint(extp), mMaxT(maxt) 
        {}

        BspRayTraversalData(BspNode *n, const Vector3 &extp):
        mNode(n), mExitPoint(extp)
        {}
};

/** Data used for passing ray data down the tree.
*/
struct BoundedRay
{
        Ray *mRay;
        float mMinT;
        float mMaxT;
                
        BoundedRay(): mMinT(0), mMaxT(1e6), mRay(NULL)
        {}
        BoundedRay(Ray *r, float minT, float maxT):
        mRay(r), mMinT(minT), mMaxT(maxT)
        {}
};

typedef vector<BoundedRay *> BoundedRayContainer;

class BspTreeStatistics: public StatisticsBase
{
public:
        // total number of nodes
        int nodes;
        // number of splits
        int splits[3];
        
        // totals number of rays
        int rays;
        // maximal reached depth
        int maxDepth;
        // minimal depth
        int minDepth;
        
        // max depth nodes
        int maxDepthNodes;
        // minimum depth nodes
        int minDepthNodes;
        // max depth nodes
        int minPvsNodes;
        // nodes with minimum PVS
        int minRaysNodes;
        // max ray contribution nodes
        int maxRayContribNodes;
        // minimum area nodes
        int minProbabilityNodes;
        /// nodes termination because of max cost ratio;
        int maxCostNodes;
        // max number of rays per node
        int maxObjectRefs;
        // accumulated depth (used to compute average)
        int accumDepth;
        // number of initial polygons
        int polys;
        /// samples contributing to pvs
        int contributingSamples;
        /// sample contributions to pvs
        int sampleContributions;
        /// largest pvs
        int maxPvs;
        /// number of invalid leaves
        int invalidLeaves;
        /// polygon splits 
        int polySplits;
        /// accumulated number of rays refs
        int accumRays;
        int pvs;
        // global cost ratio violations
        int mGlobalCostMisses;

        // Constructor
        BspTreeStatistics() 
        {
                Reset();
        }

        int Nodes() const { return nodes; }
        int Interior() const { return nodes / 2; }
        int Leaves() const { return (nodes / 2) + 1; }
        
        // TODO: computation wrong
        double AvgDepth() const { return accumDepth / (double)Leaves(); }
        double AvgRays() const { return accumRays / (double)Leaves(); }

        void Reset() 
        {
                nodes = 0;
                for (int i = 0; i < 3; ++ i)
                        splits[i] = 0;
        
                mGlobalCostMisses = 0;
                maxDepth = 0;
                minDepth = 99999;
                polys = 0;
                accumDepth = 0;
        pvs = 0;
                maxDepthNodes = 0;
                minPvsNodes = 0;
                minRaysNodes = 0;
                maxRayContribNodes = 0;
                minProbabilityNodes = 0;
                maxCostNodes = 0;

                contributingSamples = 0;
                sampleContributions = 0;

                maxPvs = 0;
                invalidLeaves = 0;
                polySplits = 0;
                accumRays = 0;
        }

        void Print(ostream &app) const;

        friend ostream &operator<<(ostream &s, const BspTreeStatistics &stat) 
        {
                stat.Print(s);
                return s;
        } 
};


/**
    BspNode abstract class serving for interior and leaf node implementation
*/
class BspNode 
{
        friend class BspTree;

public:
        BspNode();
        virtual ~BspNode(){};
        BspNode(BspInterior *parent);

        /** Determines whether this node is a leaf or not
        @return true if leaf
        */
        virtual bool IsLeaf() const = 0;

        /** Determines whether this node is a root
                @return true if root
        */
        virtual bool IsRoot() const
        {
                return mParent == NULL;
        }

        /** Returns parent node.
        */
        inline BspInterior *GetParent()
        { 
                return mParent; 
        }

        /** Sets parent node.
        */
        inline void BspNode::SetParent(BspInterior *parent)
        {
                mParent = parent;
        }


        /** Returns true if this node is a sibling of node n.
        */
        bool IsSibling(BspNode *n) const;

        /** Returns depth of the node.
        */
        int GetDepth() const;

        /** Returns true if the whole subtree is valid
        */
        bool TreeValid() const;

        /** Sets the valid flag for the subtree with this node as root.
        */
        void SetTreeValid(const bool v);

        //-- mailing options

        void Mail() { mMailbox = sMailId; }
        static void NewMail() { ++ sMailId; }
        bool Mailed() const { return mMailbox == sMailId; }

        static int sMailId;
        int mMailbox;

        int mTimeStamp;

protected:

        /// if this sub tree is a completely valid view space region
        bool mTreeValid;
        /// parent of this node
        BspInterior *mParent;
};


/** BSP interior node implementation 
*/
class BspInterior: public BspNode 
{
        friend class BspTree;

public:
        /** Standard contructor taking split plane as argument.
        */
        BspInterior(const Plane3 &plane);
        ~BspInterior();

        /** @return false since it is an interior node 
        */
        bool IsLeaf() const
        { 
                return false; 
        }
        BspNode *GetBack() 
        {
                return mBack;
        }

        BspNode *GetFront() 
        {
                return mFront;
        }
        
        /** Returns split plane.
        */
        Plane3 BspInterior::GetPlane() const
        {
                return mPlane;
        }

        /** Replace front or back child with new child.
        */
        inline void ReplaceChildLink(BspNode *oldChild, BspNode *newChild)
        {
                if (mBack == oldChild)
                        mBack = newChild;
                else
                        mFront = newChild;
        }

        /** Replace front and back child.
        */
        void SetupChildLinks(BspNode *b, BspNode *f);

        friend ostream &operator<<(ostream &s, const BspInterior &A)
        {
                return s << A.mPlane;
        }

protected:

        /// Splitting plane corresponding to this node
        Plane3 mPlane;

        /// back node
        BspNode *mBack;
        /// front node
        BspNode *mFront;
};


/** BSP leaf node implementation.
*/
class BspLeaf: public BspNode 
{
        friend class BspTree;

public:
        BspLeaf();
        BspLeaf(ViewCellLeaf *viewCell);
        BspLeaf(BspInterior *parent);
        BspLeaf(BspInterior *parent, ViewCellLeaf *viewCell);

        ~BspLeaf();

        /** Returns pointer of view cell.
        */
        inline ViewCellLeaf *GetViewCell() const
        {
                return mViewCell;
        }

        /** Sets pointer to view cell.
        */
        inline void SetViewCell(ViewCellLeaf *viewCell)
        {
                mViewCell = viewCell;
        }

        /** @return true since it is an interior node 
        */
        bool BspLeaf::IsLeaf() const 
        { 
                return true; 
        }
        
        /// Rays piercing this leaf.
        VssRayContainer mVssRays;
        
        /// leaf pvs
        ObjectPvs *mPvs;
        
        /// Probability that the view point lies in this leaf
        float mProbability;


protected:
        
        /// if NULL this does not correspond to feasible viewcell
        ViewCellLeaf *mViewCell;
};


/** Implementation of the view cell BSP tree. 
*/
class BspTree 
{
        friend class ViewCellsParseHandlers;

public:
        
        /** Additional data which is passed down the BSP tree during traversal.
        */
        struct BspTraversalData
        {  
                /// the current node
                BspNode *mNode;
                /// polygonal data for splitting
                PolygonContainer *mPolygons;
                /// current depth
                int mDepth;
                /// the view cell associated with this subdivsion
                ViewCellLeaf *mViewCell;
                /// rays piercing this node
                BoundedRayContainer *mRays;
                /// probability of current node
                float mProbability;
                /// geometry of node as induced by planes
                BspNodeGeometry *mGeometry;
                
                /// pvs size
                int mPvs;
                
                /** Returns average ray contribution.
                */
                float GetAvgRayContribution() const
                {
                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
                }


                BspTraversalData():
                mNode(NULL),
                mPolygons(NULL),
                mDepth(0),
                mViewCell(NULL),
                mRays(NULL),
                mPvs(0),
                mProbability(0.0),
                mGeometry(NULL)
                {}
                
                BspTraversalData(BspNode *node, 
                                                 PolygonContainer *polys, 
                                                 const int depth, 
                                                 ViewCellLeaf *viewCell,
                                                 BoundedRayContainer *rays,
                                                 int pvs,
                                                 float p,
                                                 BspNodeGeometry *cell): 
                mNode(node), 
                mPolygons(polys), 
                mDepth(depth), 
                mViewCell(viewCell),
                mRays(rays),
                mPvs(pvs),
                mProbability(p),
                mGeometry(cell)
                {}


                float GetCost() const
                {
#if 0
                        return mPvs * mProbability;
#endif
#if 0
                        return (float) (-mDepth); // for regular grid
#endif
#if 1
                        return (float) mDepth; // depth first
#endif
#if 0
                        return mProbability;
#endif
#if 0
                        return (float)mPvs;
#endif
#if 0
                        return (float)mRays->size();
#endif
                }
                
                friend bool operator<(const BspTraversalData &a, const BspTraversalData &b)
                {
                        return a.GetCost() < b.GetCost();
                }
    };
        
        //typedef std::stack<BspTraversalData> BspTraversalStack;
        typedef std::priority_queue<BspTraversalData> BspTraversalStack;

        /** Default constructor reading the environment file and 
                creating an empty tree.
        */ 
        BspTree();
        /** Destroys tree and nodes.
        */
        ~BspTree();

        /** Returns detailed statistics of the BSP tree.
        */
        const BspTreeStatistics &GetStatistics() const; 
  
        /** Constructs tree using the given list of view cells.
            For this type of construction we filter all view cells down the 
                tree. If there is no polygon left, the last split plane
            decides inside or outside of the viewcell. A pointer to the 
                appropriate view cell is stored within each leaf. 
                Many leafs can point to the same viewcell.
        */
        void Construct(const ViewCellContainer &viewCells);

        /** Constructs tree using the given list of objects. 
            @note the objects are not taken as view cells, but the view cells are
                constructed from the subdivision: Each leaf is taken as one viewcell.
                @param objects list of objects
        */
        void Construct(const ObjectContainer &objects);

        void Construct(const ObjectContainer &objects,
                                   const RayContainer &sampleRays,
                                   AxisAlignedBox3 *forcedBoundingBox);

        /** Constructs the tree from a given set of rays.
                @param sampleRays the set of sample rays the construction is based on
                @param viewCells if not NULL, new view cells are 
                created in the leafs and stored in the conatainer
        */
        void Construct(const RayContainer &sampleRays,
                                   AxisAlignedBox3 *forcedBoundingBox);

        /** Returns list of BSP leaves.
        */
        void CollectLeaves(vector<BspLeaf *> &leaves) 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) 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);

        /** Casts line segment between origin and termination and returns
                view cells which are touched by the line.
        */
        int     CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells
                                                );

        /** Returns view cell this point is located in.
        */
        ViewCell *GetViewCell(const Vector3 &point);
  
        /// bsp tree construction types
        //enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};

        /** Returns statistics.
        */
        BspTreeStatistics &GetStat();

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

        /** Constructs geometry of view cell returning a BSP node geometry type.
        */
        void ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const;
        
        /** Construct geometry of view cell.
        */
        void ConstructGeometry(ViewCell* vc, BspNodeGeometry &geom) const;
                        
        /** Sets pointer to view cells manager.
        */
        void SetViewCellsManager(ViewCellsManager *vcm);

        /** 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;

        int CollectMergeCandidates(const vector<BspLeaf *> leaves,
                                                           vector<MergeCandidate> &candidates);

        int CollectMergeCandidates(const VssRayContainer &rays,
                                                   vector<MergeCandidate> &candidates);

        /** Exports Bsp tree to file.
        */
        bool Export(OUT_STREAM &stream);

        /** Pointer to the view cells tree.
        */
        void SetViewCellsTree(ViewCellsTree *vct);
        
        /** Returns true if this view cell prepresents
                invalid view space.
        */
        bool IsOutOfBounds(ViewCell *vc) const;

protected:

        /// Strategies for choosing next split plane.
        enum {NO_STRATEGY = 0,
                  RANDOM_POLYGON = 1, 
                  AXIS_ALIGNED = 2,
                  LEAST_SPLITS = 4, 
                  BALANCED_POLYS = 8,
                  BALANCED_VIEW_CELLS = 16,
                  LARGEST_POLY_AREA = 32,
                  VERTICAL_AXIS = 64,
                  BLOCKED_RAYS = 128,
                  LEAST_RAY_SPLITS = 256,
                  BALANCED_RAYS = 512,
                  PVS = 1024
                };

        /** 
                For sorting polygons
        */
        struct SortableEntry
        {
                enum {POLY_MIN, POLY_MAX};
    
                int type;
                float value;
                Polygon3 *poly;
                SortableEntry() {}
                SortableEntry(const int t, const float v, Polygon3 *poly): 
                type(t), value(v), poly(poly) {}
                
                bool operator<(const SortableEntry &b) const 
                {
                        return value < b.value;
                }  
        };

        /** Returns view cell representing the empty view space.
        */
        BspViewCell *GetOrCreateOutOfBoundsCell();

        void ExportNode(BspNode *node, OUT_STREAM &stream);

        /** Evaluates tree stats in the BSP tree leafs.
        */
        void EvaluateLeafStats(const BspTraversalData &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(BspTraversalStack &tStack, BspTraversalData &tData);

        /** Constructs the tree from the given list of polygons and rays.
                @param polys stores set of polygons on which subdivision may be based
                @param rays storesset of rays on which subdivision may be based
        */
        void Construct(PolygonContainer *polys, BoundedRayContainer *rays);

        /** Selects the best possible splitting plane. 
                @param leaf the leaf to be split
                @param polys the polygon list on which the split decition is based
                @param rays ray container on which selection may be based
                @note the polygons can be reordered in the process
                @returns the split plane
        */
        Plane3 SelectPlane(BspLeaf *leaf, 
                                           BspTraversalData &data);

        /** Evaluates the contribution of the candidate split plane.
                
                @param candidatePlane the candidate split plane
                @param polys the polygons the split can be based on
                @param rays the rays the split can be based on

                @returns the cost of the candidate split plane
        */
        float SplitPlaneCost(const Plane3 &candidatePlane,
                                                 BspTraversalData &data) const;

        /** Strategies where the effect of the split plane is tested
            on all input rays.
                @returns the cost of the candidate split plane
        */
        float SplitPlaneCost(const Plane3 &candidatePlane,
                                                 const PolygonContainer &polys) const;

        /** Strategies where the effect of the split plane is tested
            on all input rays.

                @returns the cost of the candidate split plane
        */
        float SplitPlaneCost(const Plane3 &candidatePlane, 
                                                 const BoundedRayContainer &rays,
                                                 const int pvs,
                                                 const float probability,
                                                 const BspNodeGeometry &cell) const;

        /** Filters next view cell down the tree and inserts it into the appropriate leaves
                (i.e., possibly more than one leaf).
        */
        void InsertViewCell(ViewCellLeaf *viewCell);
        /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,
                then further subdivided.
        */
        void InsertPolygons(PolygonContainer *polys);

        /** Subdivide leaf.
                @param leaf the leaf to be subdivided
                
                @param polys the polygons to be split
                @param frontPolys returns the polygons in front of the split plane
                @param backPolys returns the polygons 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 backRays returns the polygons in the back of the split plane

                @returns the root of the subdivision
        */

        BspInterior *SubdivideNode(BspTraversalData &tData,
                                                           BspTraversalData &frontData,
                                                           BspTraversalData &backData,
                                                           PolygonContainer &coincident);

        /** Filters polygons down the tree.
                @param node the current BSP node
                @param polys the polygons to be filtered
                @param frontPolys returns the polygons in front of the split plane
                @param backPolys returns the polygons in the back of the split plane
        */
        void FilterPolygons(BspInterior *node, 
                                                PolygonContainer *polys, 
                                                PolygonContainer *frontPolys, 
                                                PolygonContainer *backPolys);

        /** Take 3 ray endpoints, where two are minimum and one a maximum
                point or the other way round.
        */
        Plane3 ChooseCandidatePlane(const BoundedRayContainer &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 BoundedRayContainer &rays) const;

        /** Fit the plane between the two lines so that the plane has equal shortest 
                distance to both lines.
        */
        Plane3 ChooseCandidatePlane3(const BoundedRayContainer &rays) const;

        /** Selects the split plane in order to construct a tree with
                certain characteristics (e.g., balanced tree, least splits, 
                2.5d aligned)
                @param polygons container of polygons
                @param rays bundle of rays on which the split can be based
        */
        Plane3 SelectPlaneHeuristics(BspLeaf *leaf,
                                                                 BspTraversalData &data);

        /** 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,
                                                 bool addToBbox = true);

        /** 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);

        /** Helper function which extracts a view cell on the front and the back
                of the split plane.
                @param backViewCell returns view cell on the back of the split plane
                @param frontViewCell returns a view cell on the front of the split plane
                @param coincident container of polygons coincident to the split plane
                @param splitPlane the split plane which decides about back and front
                @param extractBack if a back view cell is extracted
                @param extractFront if a front view cell is extracted
        */
        void ExtractViewCells(BspTraversalData &frontData,
                                                  BspTraversalData &backData, 
                                                  const PolygonContainer &coincident,
                                                  const Plane3 &splitPlane) const;
        
        /** Computes best cost ratio for the suface area heuristics for axis aligned
                splits. This heuristics minimizes the cost for ray traversal.
                @param polys the polygons guiding the ratio computation
                @param box the bounding box of the leaf
                @param axis the current split axis
                @param position returns the split position
                @param objectsBack the number of objects in the back of the split plane
                @param objectsFront the number of objects in the front of the split plane
        */
        float BestCostRatio(const PolygonContainer &polys,
                                                const AxisAlignedBox3 &box,
                                                const int axis,
                                                float &position,
                                                int &objectsBack,
                                                int &objectsFront) const;
        
        /** 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 SortSubdivisionCandidates(const PolygonContainer &polys, 
                                                         const int axis, 
                                                         vector<SortableEntry> &splitCandidates) const;

        /** Selects an axis aligned split plane.
                Returns true if split is valied
        */
        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;

        /** 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,
                                  BoundedRayContainer &rays, 
                              BoundedRayContainer &frontRays, 
                                  BoundedRayContainer &backRays);


        /** 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, int &frontPvs, int &backPvs) const;

        /** Computes PVS size induced by the rays.
        */
        int ComputePvsSize(const BoundedRayContainer &rays) const;

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

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

        /** Splits polygons with respect to 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 BoundedRayContainer &rays, 
                                  int &sampleContributions,     
                                  int &contributingSamples);

        /** Preprocesses polygons and throws out all polygons which 
                are coincident to the view space box faces:
                These polygons can can be problematic for bsp because they create
                bad view cells.
        */
        void PreprocessPolygons(PolygonContainer &polys);


        ///////////////////////////////////
                
        /// Pointer to the root of the tree.
        BspNode *mRoot;

        /// Stores statistics during traversal.
        BspTreeStatistics mStat;

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

        /// view cell corresponding to unbounded space
        BspViewCell *mOutOfBoundsCell;

        /// if view cells should be generated or the given view cells should be used.
        bool mUsePredefinedViewCells;

        /// maximal number of polygons before subdivision termination
        int mTermMinPolys;
        /// maximal number of rays before subdivision termination
        int mTermMinRays;
        /// maximal possible depth
        int mTermMaxDepth;
        /// mininum area
        float mTermMinProbability;
        /// mininum PVS
        int mTermMinPvs;

        /// minimal number of polygons for axis aligned split
        int mTermMinPolysForAxisAligned;
        /// minimal number of rays for axis aligned split
        int mTermMinRaysForAxisAligned;
        /// minimal number of objects for axis aligned split
        int mTermMinObjectsForAxisAligned;
        /// maximal contribution per ray
        float mTermMaxRayContribution;
        /// minimal accumulated ray length
        float mTermMinAccRayLength;


        /// strategy to get the best split plane
        int mSplitPlaneStrategy;
        /// number of candidates evaluated for the next split plane
        int mMaxPolyCandidates;
        /// number of candidates for split planes evaluated using the rays
        int mMaxRayCandidates;
        /// maximum tests for split plane evaluation with a single candidate
        int mMaxTests;

        float mCtDivCi;

        /// axis aligned split criteria
        float mAxisAlignedCtDivCi;
        float mSplitBorder;
        float mMaxCostRatio;

        // factors guiding the split plane heuristics
        float mVerticalSplitsFactor;
        float mLargestPolyAreaFactor;
        float mBlockedRaysFactor;
        float mLeastRaySplitsFactor;
        float mBalancedRaysFactor;
        float mPvsFactor;
        float mLeastSplitsFactor;
        float mBalancedPolysFactor;
        float mBalancedViewCellsFactor;

        /// if area or accumulated ray lenght should be used for PVS heuristics
        bool mUseAreaForPvs;

        int mMaxViewCells;

        /// epsilon where two points are still considered equal
        float mEpsilon;

        ViewCellsManager *mViewCellsManager;

        int mTimeStamp;

        float mTotalCost;
        int mTotalPvsSize;

        //int mSplits;
        ofstream  mSubdivisionStats;

        ViewCellsTree *mViewCellsTree;
        /// if out of bounds cell is part of the bsp tree
        bool mOutOfBoundsCellPartOfTree;


private:
        
        /** Evaluates split plane classification with respect to the plane's 
                contribution for a balanced tree.
        */
        static const float sLeastPolySplitsTable[4];
        /** Evaluates split plane classification with respect to the plane's 
                contribution for a minimum number splits in the tree.
        */
        static const float sBalancedPolysTable[4];
        /** Evaluates split plane classification with respect to the plane's 
                contribution for a minimum number of ray splits.
        */
        static const float sLeastRaySplitsTable[5];
        /** Evaluates split plane classification with respect to the plane's 
                contribution for balanced rays.
        */
        static const float sBalancedRaysTable[5];

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

        ///////////
        //-- unique ids for PVS criterium

        static int sFrontId; 
        static int sBackId;
        static int sFrontAndBackId;
};


struct BspIntersection 
{
        // the point of intersection
        float mT;
  
        BspLeaf *mLeaf;
  
        BspIntersection(const float t, BspLeaf *l):
        mT(t), mLeaf(l) {}
  
        BspIntersection() {}
  
        bool operator<(const BspIntersection &b) const 
        {
                return mT < b.mT; 
        }
};

/** struct storing the view cell intersections.
*/
struct BspRay 
{
        VssRay *vssRay;
        std::vector<BspIntersection> intersections;
        BspRay(VssRay *ray): vssRay(ray) {}
};

}

#endif