source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h @ 445

#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"

class ViewCell;
class BspViewCell;
class Plane3;
class VspBspTree;  
class VspBspInterior;
class VspBspNode;
class AxisAlignedBox3;
class Ray;

class VspBspNodeGeometry
{
public:
        VspBspNodeGeometry()
        {};  

        ~VspBspNodeGeometry();

        float GetArea() const;
        
        /** Computes new cell based on the old cell definition and a new split plane
                @param side indicates which side of the halfspace 
        */
        void SplitGeometry(VspBspNodeGeometry &front, 
                                           VspBspNodeGeometry &back,
                                           const VspBspTree &tree,
                                           const Plane3 &splitPlane) const;

        Polygon3 *SplitPolygon(Polygon3 *poly, const VspBspTree &tree) const;

        PolygonContainer mPolys;
};

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

    VspBspRayTraversalData(VspBspNode *n, const Vector3 &extp, const float maxt):
    mNode(n), mExitPoint(extp), mMaxT(maxt) 
        {}
};

class VspBspTreeStatistics: public StatisticsBase
{
public:
        // total number of nodes
        int nodes;
        // number of splits
        int splits;
        // 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 minAreaNodes;

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

        // Constructor
        VspBspTreeStatistics() 
        {
                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();}; 
  
        void Reset() 
        {
                nodes = 0;
                splits = 0;
                
                maxDepth = 0;
                minDepth = 99999;
                polys = 0;
                accumDepth = 0;
        
                maxDepthNodes = 0;
                minPvsNodes = 0;
                minRaysNodes = 0;
                maxRayContribNodes = 0;
                minAreaNodes = 0;

                contributingSamples = 0;
                sampleContributions = 0;
        }

        void Print(ostream &app) const;

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

class VspBspViewCellsStatistics: public StatisticsBase
{
public:

        /// number of view cells
        int viewCells;

        /// size of the PVS
        int pvs;
  
        /// largest PVS of all view cells
        int maxPvs;

        /// smallest PVS of all view cells
        int minPvs;

        /// view cells with empty PVS
        int emptyPvs;

        /// number of bsp leaves covering the view space
        int bspLeaves;

        /// largest number of leaves covered by one view cell  
        int maxVspBspLeaves;

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

        double AvgVspBspLeaves() const {return (double)bspLeaves / (double)viewCells;};
        double AvgPvs() const {return (double)pvs / (double)viewCells;};
  
        void Reset() 
        {
                viewCells = 0;  
                pvs = 0;  
                maxPvs = 0;

                minPvs = 999999;
                emptyPvs = 0;
                bspLeaves = 0;
                maxVspBspLeaves = 0;
        }

        void Print(ostream &app) const;

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

/**
    VspBspNode abstract class serving for interior and leaf node implementation
*/
class VspBspNode 
{
        friend class VspBspTree;

public:
        VspBspNode();
        virtual ~VspBspNode(){};
        VspBspNode(VspBspInterior *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;

        /** Returns parent node.
        */
        VspBspInterior *GetParent();

        /** Sets parent node.
        */
        void SetParent(VspBspInterior *parent);

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

protected:

        /// parent of this node
        VspBspInterior *mParent;
};

/** BSP interior node implementation 
*/
class VspBspInterior : public VspBspNode 
{
        friend class VspBspTree;
public:
        /** Standard contructor taking split plane as argument.
        */
        VspBspInterior(const Plane3 &plane);
        ~VspBspInterior();
        /** @return false since it is an interior node 
        */
        bool IsLeaf() const;

        VspBspNode *GetBack();
        VspBspNode *GetFront();

        Plane3 *GetPlane();

        void ReplaceChildLink(VspBspNode *oldChild, VspBspNode *newChild);
        void SetupChildLinks(VspBspNode *b, VspBspNode *f);

        /** 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(PolygonContainer &polys, 
                                          PolygonContainer &frontPolys, 
                                          PolygonContainer &backPolys, 
                                          PolygonContainer &coincident);

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

protected:

        /// Splitting plane corresponding to this node
        Plane3 mPlane;
        /// back node
        VspBspNode *mBack;
        /// front node
        VspBspNode *mFront;
};

/** BSP leaf node implementation.
*/
class VspBspLeaf : public VspBspNode 
{
        friend class VspBspTree;

public:
        VspBspLeaf();
        VspBspLeaf(BspViewCell *viewCell);
        VspBspLeaf(VspBspInterior *parent);
        VspBspLeaf(VspBspInterior *parent, BspViewCell *viewCell);

        /** @return true since it is an interior node 
        */
        bool IsLeaf() const;
        
        /** Returns pointer of view cell.
        */
        BspViewCell *GetViewCell() const;

        /** Sets pointer to view cell.
        */
        void SetViewCell(BspViewCell *viewCell);

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

protected:

        /// if NULL this does not correspond to feasible viewcell
        BspViewCell *mViewCell;
};

/**
        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 
{
public:
        
        /** Additional data which is passed down the BSP tree during traversal.
        */
        struct VspBspTraversalData
        {  
                /// the current node
                VspBspNode *mNode;
                /// polygonal data for splitting
                PolygonContainer *mPolygons;
                /// current depth
                int mDepth;
                /// the view cell associated with this subdivsion
                ViewCell *mViewCell;
                /// rays piercing this node
                RayInfoContainer *mRays;
                /// area of current node
                float mArea;
                /// geometry of current node induced by split planes
                VspBspNodeGeometry *mGeometry;

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


                VspBspTraversalData():
                mNode(NULL),
                mPolygons(NULL),
                mDepth(0),
                mViewCell(NULL),
                mRays(NULL),
                mPvs(0),
                mArea(0.0),
                mGeometry(NULL)
                {}
                
                VspBspTraversalData(VspBspNode *node, 
                                                 PolygonContainer *polys, 
                                                 const int depth, 
                                                 ViewCell *viewCell,
                                                 RayInfoContainer *rays,
                                                 int pvs,
                                                 float area,
                                                 VspBspNodeGeometry *cell): 
                mNode(node), 
                mPolygons(polys), 
                mDepth(depth), 
                mViewCell(viewCell),
                mRays(rays),
                mPvs(pvs),
                mArea(area),
                mGeometry(cell)
                {}
    };
        
        typedef std::stack<VspBspTraversalData> VspBspTraversalStack;

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

        ~VspBspTree();

        const VspBspTreeStatistics &GetStatistics() const; 
  

        /** 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 container
        */
        void Construct(const VssRayContainer &sampleRays);

        /** Returns list of BSP leaves.
        */
        void CollectLeaves(vector<VspBspLeaf *> &leaves) const;

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

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

        /** Exports VspBsp tree to file.
        */
        bool Export(const string filename);

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

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

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

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

        /** Constructs geometry associated with the half space intersections 
                leading to this node.
        */
        void ConstructGeometry(VspBspNode *n, PolygonContainer &cell) const;

        /** Constructs geometry associated with the half space intersections 
                leading to this node.
        */
        void ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const;

        /** Construct geometry and stores it in a geometry node container.
        */
        void ConstructGeometry(VspBspNode *n, VspBspNodeGeometry &cell) const;

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

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

        /** Traverses tree and counts all view cells as well as their PVS size.
        */
        void EvaluateViewCellsStats(VspBspViewCellsStatistics &stat) const;


        /** Returns view cell corresponding to unbounded space.
        */
        BspViewCell *GetRootCell() const;

protected:

        // --------------------------------------------------------------
        // For sorting objects
        // --------------------------------------------------------------
        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;
                }  
        };

        /** 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
        */
        VspBspNode *Subdivide(VspBspTraversalStack &tStack, VspBspTraversalData &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, RayInfoContainer *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(VspBspLeaf *leaf, 
                                           VspBspTraversalData &data);

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



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

        VspBspInterior *SubdivideNode(VspBspTraversalData &tData,
                                                           VspBspTraversalData &frontData,
                                                           VspBspTraversalData &backData,
                                                           PolygonContainer &coincident);

        /** 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(VspBspLeaf *leaf,
                                                                 VspBspTraversalData &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);

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

        /** returns next candidate index and reorders polygons so no candidate is chosen two times
                @param the current candidate index
                @param max the range of candidates
        */
        int GetNextCandidateIdx(int currentIdx, PolygonContainer &polys);
        
        /** 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 surface area heuristics for 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 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;

        /** Bounds ray and returns minT and maxT.
                @returns true if ray hits BSP tree bounding box
        */
        bool BoundRay(const Ray &ray, float &minT, float &maxT) 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,
                                  RayInfoContainer &rays, 
                              RayInfoContainer &frontRays, 
                                  RayInfoContainer &backRays);


        /** Extracts the split planes representing the space bounded by node n.
        */
        void ExtractHalfSpaces(VspBspNode *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 RayInfoContainer &rays) const;

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

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



        /// Pointer to the root of the tree
        VspBspNode *mRoot;
                
        VspBspTreeStatistics mStat;

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

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

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

        /// minimal number of rays before subdivision termination
        int mTermMinRays;
        /// maximal possible depth
        int mTermMaxDepth;
        /// mininum area
        float mTermMinArea;
        /// mininum PVS
        int mTermMinPvs;

        /// 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;
        /// balancing factor for PVS criterium
        float mCtDivCi;

        //-- axis aligned split criteria
        float mAaCtDivCi;
        float mSplitBorder;
        float mMaxCostRatio;

        //-- factors guiding the split plane heuristics
        float mLeastRaySplitsFactor;
        float mBalancedRaysFactor;
        float mPvsFactor;

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

private:
        
        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;
};

#endif