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

#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

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

class ViewCell;
class Plane3;
//class Mesh;

//namespace GtpVisibilityPreprocessor {
class BspTree;  
class BspInterior;
class Polygon3;

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

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

protected:

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

/** BSP interior node implementation 
*/
class BspInterior : public BspNode 
{
public:
        /** Standard contructor taking split plane as argument.
        */
        BspInterior(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
        */
        void SplitPolygons(PolygonContainer *polys, PolygonContainer *frontPolys, 
                                           PolygonContainer *backPolys, int &splits);

        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 
{
public:
        BspLeaf(ViewCell *viewCell = NULL);

        /** @return true since it is an interior node */
        bool IsLeaf() const;
        ViewCell *GetViewCell();

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;
                /// parent of current node
                BspInterior *mParent;
                /// polygonal data for splitting
                PolygonContainer *mPolygons;
                /// current depth
                int mDepth;
                
                BspTraversalData() {}
                
                BspTraversalData(BspNode *node, BspInterior *parent, PolygonContainer *polys, const int depth): 
                mNode(node), mParent(parent), mPolygons(polys), mDepth(depth) {}
    };

        typedef std::stack<BspTraversalData> BspTraversalStack;

        /// BSP tree construction type
        enum {VIEWCELLS, SCENE_GEOMETRY};

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

        ~BspTree();

        const BspTreeStatistics &GetStatistics() const; 
  
        /** Constructs tree using the given list of viewcells.
            A pointer to the appropriate viewcell 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. Each leaf is taken as viewcell.
            No objects are treated as viewcells explicitly.

                @param objects list of objects
        */
        void Construct(const ObjectContainer &objects);


protected:
        
        /** Evaluates plane classification with respect to the plane's 
                contribution for a balanced tree.
        */
        static inline int EvalForBalancedTree(const int classficiation);
        /** Evaluates plane classification with respect to the plane's 
                contribution for a minimum number splits in the tree.
        */
        static inline int EvalForLeastSplits(const int classification);

        /** 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 polygons the polygon data on which the split decition is based
        */
        Plane3 SelectPlane(PolygonContainer *polygons) 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 parent the parent node of this leaf
                @param polys the input polygons
                @param depth the current tree depth
                @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
        */
        BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
                                                        PolygonContainer *polys, const int depth, 
                                                        ViewCell *viewCell,
                                                        PolygonContainer *frontPolys, PolygonContainer *backPolys);

        /** 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.
        */
        static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxPolys);

        /** copy this mesh into polygons.
        */
        static void CopyMesh2Polygons(Mesh *mesh, PolygonContainer &polys);

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

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

//}; // GtpVisibilityPreprocessor

#endif