source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h @ 264

#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

#include "Mesh.h"
#include "Containers.h"
#include <stack>

class ViewCell;
class Plane3;
//class Mesh;
class BspTree;  
class BspInterior;
class Polygon3;
class AxisAlignedBox3;
class Ray;

//namespace GtpVisibilityPreprocessor {

/** Container storing a soup of polygons used during BSP tree construction
*/
typedef vector<Polygon3 *> PolygonContainer;
typedef vector<Ray *> RayContainer;

struct BspRayTraversalData 
{
    BspNode *mNode;
    Vector3 mExitPoint;
    float mMaxT;
    
    BspRayTraversalData() {}

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

class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics
{
public:
  // total number of nodes
  int nodes;
  // number of splits
  int splits;
  // totals number of rays
  int rays;
  // maximal reached depth
  int maxDepth;
  // total number of query domains
  int queryDomains;
  // total number of ray references
  int rayRefs;
  // refs in non empty leafs
  int rayRefsNonZeroQuery;
  // total number of query references
  int objectRefs;
  // nodes with zero queries
  int zeroQueryNodes;
  // max depth nodes
  int maxDepthNodes;
  // max number of rays per node
  int maxObjectRefs;
  // number of dynamically added ray refs
  int addedRayRefs;
  // number of dynamically removed ray refs
  int removedRayRefs;
  
  // Constructor
  BspTreeStatistics() 
  {
          Reset();
  }

  int Nodes() const {return nodes;}
  int Interior() const { return nodes / 2; }
  int Leaves() const { return (nodes / 2) + 1; }

  void Reset() 
  {
          nodes = 0;
          splits = 0;
          rays = queryDomains = 0;
          rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
          zeroQueryNodes = 0;
      maxDepthNodes = 0;
      //minCostNodes = 0;
          maxObjectRefs = 0;
          addedRayRefs = removedRayRefs = 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 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;

        /** Returns parent node.
        */
        BspInterior *GetParent();
        /** Sets parent node.
        */
        void SetParent(BspInterior *parent);

        /** Returns pointer to polygons.
        */
        PolygonContainer *GetPolygons();

protected:

        /** Adds or discards polygons according to storePolys.
        */
        void ProcessPolygons(PolygonContainer *polys, const bool storePolys);


        /// parent of this node
        BspInterior *mParent;

        /// store polygons created during BSP splits
        PolygonContainer *mPolygons;
};

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

        BspNode *GetBack();
        BspNode *GetFront();

        Plane3 *GetPlane();

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

        /** Splits polygons.
                @param polys the polygons to be split
                @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 splits number of splits
                @returns true if one or more polygons are inside of the split plane
        */
        bool SplitPolygons(PolygonContainer *polys, PolygonContainer *frontPolys, 
                                           PolygonContainer *backPolys, int &splits, bool storePolys = false);

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


protected:
        
        /** Discards or stores polygon in node.
                @param polys the polygons
                @param storePolys if the polygons should be stored or discarded
        */
        void ProcessPolygon(Polygon3 *poly, const bool storePolys);

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

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

        /** @return true since it is an interior node 
        */
        bool IsLeaf() const;
        /** Returns pointer from view cell.
        */
        ViewCell *GetViewCell();
        /** Sets pointer to view cell.
        */
        void SetViewCell(ViewCell *viewCell);

protected:

        /// polygonal representation of this viewcell
        /// if NULL this note does not correspond to feasible viewcell
        ViewCell *mViewCell;
};


/** Implementation of the ViewCell BSP tree. */
class BspTree 
{
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;
                /// if the node is an inside or outside node with respect to the parent plane
                bool mIsInside;
                BspTraversalData() {}
                
                BspTraversalData(BspNode *node, PolygonContainer *polys, const int depth, const bool inside): 
                mNode(node), mPolygons(polys), mDepth(depth), mIsInside(inside) {}
    };

        typedef std::stack<BspTraversalData> BspTraversalStack;

        /// BSP tree construction type
        enum {VIEW_CELLS, SCENE_GEOMETRY, RAYS};

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

        ~BspTree();

        const BspTreeStatistics &GetStatistics() const; 
  
        /** Constructs tree using the given list of view cells.
            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 that 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
                @returns list of view cells.
        */
        void Construct(const ObjectContainer &objects, ViewCellContainer *viewCells);

        /** Constructs tree using the given number of rays
            @param objects list of objects
                @returns list of view cells.
        */
        void Construct(const RayContainer &rays, ViewCellContainer *viewCells);

        int CollectLeafPvs();

        void CollectLeaves(vector<BspLeaf *> &leaves);

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

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

        /** If the view cell polygons are stored in the nodes.
        */
        bool StorePolys() const;

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


protected:
        
        /** Initialises BSP tree.
                @param maxPolygons the maximal polygon count before termination of 
                subdivision
                @param maxDepth the maximal depth before termination of 
                subdivision
        */
        void InitTree(int maxPolygons, int maxDepth);

        /** Constructs the tree from the given list of polygons.
        */
        void Construct(PolygonContainer *polys);

        /** Evaluates the contribution of the candidate split plane.
        */
        int EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const;

        /** 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
                @param viewCell the view cell that will be represented with this part of the Bsp tree.
                @returns new root of the subtree
        */
        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);

        /** Selects a splitting plane. 
                @param polys the polygon list on which the split decition is based
        */
        Plane3 SelectPlane(PolygonContainer *polys) const;

        /** Filters next viewcell down the tree and inserts it into the appropriate leaves
                (i.e., possibly more than one leaf).
        */
        void InsertViewCell(ViewCell *viewCell);
        
        /** Subdivide leaf.
                @param leaf the leaf to be subdivided
                @param polys the input polygons
                @param frontPolys the polygons of the front child node as a result from splitting
                @param backPolys the polygons of the back child node as a result from splitting
                @param if the polygons are outside or inside with respect to the interior node plane
                @returns the root of the subdivision
        */
        BspInterior *SubdivideNode(BspLeaf *leaf, 
                                                           PolygonContainer *polys, 
                                                           PolygonContainer *frontPolys, 
                                                           PolygonContainer *backPolys, bool &inside);

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

        /** Selects the split plane in order to get a balanced tree.
                @param polygons container of polygons
                @param maxTests the maximal number of candidate tests
        */
        Plane3 SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const;

        /** Extracts the meshes of the objects and copies them into the mesh. 
                Adds object aabb to the aabb of the tree.
                @param maxPolys the maximal number of objects to be stored as polygons
        */
        void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects);
        /** Extracts the meshes of the view cells and copies them into the mesh. 
                Adds view cell aabb to the aabb of the tree.
                @param maxPolys the maximal number of objects to be stored as polygons
        */
        void Copy2PolygonSoup(const ViewCellContainer &viewCells, PolygonContainer &polys, int maxObjects);

        /** Add this mesh as polygons to polygon container.
        */
        void AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys);

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



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

        /// Pointer to the root cell of the viewspace
        // ViewCell *mRootCell;
                
        BspTreeStatistics mStat;

        /// local maximal polygons (changes depending on method)
        int mTermMaxPolygons;
        int mTermMaxDepth;

        /// Strategies for choosing next split plane.
        enum {NEXT_POLYGON, LEAST_SPLITS, BALANCED_TREE, COMBINED};

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

                /// if view cell calculation is incremential
        bool mIsIncremential;

        /// if polygons should be stored in the tree
        bool mStorePolys;

public:
        /// Parses the environment and stores the global BSP tree parameters
        static void ParseEnvironment();

        /// maximal number of polygons where tree construction is terminated
        static int sTermMaxPolygons;
        /// maximal possible depth
        static int sTermMaxDepth;
        /// strategy to get the best split plane
        static int sSplitPlaneStrategy;
        /// number of candidates evaluated for the next split plane
        static int sMaxCandidates;
        /// BSP tree construction method
        static int sConstructionMethod;

private:
        /** Evaluates split plane classification with respect to the plane's 
                contribution for a balanced tree.
        */
        static int sLeastSplitsTable[4];
        /** Evaluates split plane classification with respect to the plane's 
                contribution for a minimum number splits in the tree.
        */
        static int sBalancedTreeTable[4];
};

//}; // GtpVisibilityPreprocessor

#endif