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

#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

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

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

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

    BspRayTraversalData(BspNode *n, const Vector3 &extp, const float maxt):
    mNode(n), mExitPoint(extp), 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;
  // minimal depth
  int minDepth;
  // 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;
  // accumulated depth (used to compute average)
  int accumDepth;
  // number of initial polygons
  int polys;
  /// number of view cells in leaf
  int viewCellLeaves;

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

  int Nodes() const {return nodes;}
  int Interior() const { return nodes / 2; }
  int Leaves() const { return (nodes / 2) + 1; }
  double AvgDepth() const { return accumDepth / (double)Leaves();}; // TODO: computation wrong
  
  void Reset() 
  {
          nodes = 0;
          splits = 0;
          rays = queryDomains = 0;
          rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
          zeroQueryNodes = 0;
      maxDepthNodes = 0;

          maxObjectRefs = 0;
          addedRayRefs = removedRayRefs = 0;
          maxDepth = 0;
          minDepth = 99999;
          polys = 0;
          accumDepth = 0;
          viewCellLeaves = 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();
        /** Stores polygons in node or discards them according to storePolys.
        */
        void ProcessPolygons(PolygonContainer *polys, const bool storePolys);

//int mViewCellIdx;
protected:

        /// parent of this node
        BspInterior *mParent;

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

/** BSP interior node implementation 
*/
class BspInterior : public BspNode 
{
        friend BspTree;
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 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
                @param splits returns the splits number of splits       
                @param storePolys if the polygons should be stored in the node
        */
        void SplitPolygons(PolygonContainer &polys, 
                                           PolygonContainer &frontPolys, 
                                           PolygonContainer &backPolys, 
                                           PolygonContainer &coincident,
                                           int &splits,
                                           bool storePolys = false);

        /** Stores polygon in node or discards them according to storePolys.
                @param polys the polygons
                @param storePolys if the polygons should be stored or discarded
        */
        void ProcessPolygon(Polygon3 **poly, const bool storePolys);

        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 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:

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

/** Implementation of the view cell 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;
                /// the view cell associated with this subdivsion
                ViewCell *mViewCell;
                /// rays piercing this node
                RayContainer *mRays;

                BspTraversalData():
                mNode(NULL),
                mPolygons(NULL),
                mDepth(0),
                mViewCell(NULL),
                mRays(NULL)
                {}
                
                BspTraversalData(BspNode *node, 
                                                 PolygonContainer *polys, 
                                                 const int depth, 
                                                 ViewCell *viewCell,
                                                 RayContainer *rays = NULL): 
                mNode(node), 
                mPolygons(polys), 
                mDepth(depth), 
                mViewCell(viewCell),
                mRays(rays)
                {}
    };

        typedef std::stack<BspTraversalData> BspTraversalStack;

        /** Default constructor creating an empty tree.
                @param viewCell view cell corresponding to unbounded space
        */ 
        BspTree(ViewCell *viewCell);

        ~BspTree();

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

        void CollectViewCells(BspNode *n, ViewCellContainer &viewCells);

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

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

        /** Constructs the tree from the given list of polygons.
                @param viewCells if not NULL, new view cells are 
                created in the leafs and stored in the conatainer
        */
        void Construct(PolygonContainer *polys, ViewCellContainer *viewCells = NULL);

        /** Evaluates the contribution of the candidate split plane.
                @note the polygons can be reordered in the process.
                @returns the cost of the candidate split plane
        */
        float EvalSplitPlane(PolygonContainer &polys, 
                                                 const Plane3 &candidatePlane,
                                                 const RayContainer &rays);

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

        /** Selects a 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
                Returns the split plane
        */
        Plane3 SelectPlane(BspLeaf *leaf, 
                                           PolygonContainer &polys,
                                           const RayContainer &ray);

        /** Filters next view cell down the tree and inserts it into the appropriate leaves
                (i.e., possibly more than one leaf).
        */
        void InsertViewCell(ViewCell *viewCell);
        /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,
                then further subdivided.
                @param viewCellContainer if not null, a new viewcell is created and stored in the container
        */
        void InsertPolygons(PolygonContainer *polys, ViewCellContainer *viewCells = NULL);

        /** Subdivide leaf.
                @param leaf the leaf to be subdivided
                @param polys the input polygons
                @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
                @param rays ray container used to guide the split process
                @returns the root of the subdivision
        */
        BspInterior *SubdivideNode(BspLeaf *leaf, 
                                                           PolygonContainer &polys, 
                                                           PolygonContainer &frontPolys,
                                                           PolygonContainer &backPolys, 
                                                           PolygonContainer &coincident,
                                                           const RayContainer &rays);

        /** 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 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
                @param maxTests the maximal number of candidate tests
        */
        Plane3 SelectPlaneHeuristics(PolygonContainer &polys, 
                                                                 const RayContainer &rays,
                                                                 const int maxTests);

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

        /** 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(ViewCell **backViewCell, 
                                                  ViewCell **frontViewCell,
                                                  const PolygonContainer &coincident,
                                                  const Plane3 splitPlane, 
                                                  const bool extractBack,
                                                  const bool extractFront) 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 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;

        /** Splits the rays into front and back rays according to split plane
                @param rays contains the rays to be split. The rays are 
                           distributed to 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
        */
        void BspTree::SplitRays(const Plane3 plane,
                                                        RayContainer &rays, 
                                                        RayContainer &frontRays, 
                                                        RayContainer &backRays);

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

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

        /// Strategies for choosing next split plane.
        enum {NO_STRATEGY = 0,
                  NEXT_POLYGON = 1, 
                  AXIS_ALIGNED = 2,
                  LEAST_SPLITS = 4, 
                  BALANCED_POLYS = 8,
                  BALANCED_VIEW_CELLS = 16,
                  LARGEST_POLY_AREA = 32,
                  VERTICAL_AXIS = 64
                };

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

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

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

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;
        /// maximal number of polygons where we do axis aligned splits
        static int sTermMaxPolysForAxisAligned;

        static float sCt_div_ci;
        static float sSplitBorder;
        static float sMaxCostRatio;

        // factors to guid the split plane heuristics
        static float sLeastSplitsFactor;
        static float sBalancedPolysFactor;
        static float sBalancedViewCellsFactor;
        static float sVerticalSplitsFactor;
        static float sLargestPolyAreaFactor;
        
private:
        /** Evaluates split plane classification with respect to the plane's 
                contribution for a balanced tree.
        */
        static float sLeastSplitsTable[4];
        /** Evaluates split plane classification with respect to the plane's 
                contribution for a minimum number splits in the tree.
        */
        static float sBalancedPolysTable[4];
};

//}; // GtpVisibilityPreprocessor

#endif