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

#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 Polygon;

typedef std::queue<Polygon *> PolygonQueue;

class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics
{
public:
  // total number of nodes
  int nodes;
  // totals number of rays
  int rays;
  // 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;

          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:
        /** 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();
        
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
        */
        void SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys);

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


/** Class representing a polygon.
*/
class Polygon
{
public:
        Polygon();
        Polygon(const VertexContainer &vertices);

        /** Copies all the vertices of the face.
        */
        Polygon(Face *face, Mesh *parent);
        
        /** Returns supporting plane of this polygon.
        */
        Plane3 GetSupportingPlane();

        /** Splits polygon.
                @param partition the split plane
                @param front the front polygon
                @param back the back polygon
        */
        void Split(Plane3 *partition, Polygon *front, Polygon *back);

        enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};

        /** Side of the plane where the polygon is located.
            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
        */
        int Side(Plane3 *plane);

        static void DeletePolygons(PolygonQueue *polys);

        /// vertices are connected in counterclockwise order.
        VertexContainer mVertices;
};

/** 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
                PolygonQueue *mPolys;
                /// current depth
                int mDepth;
                
                BspTraversalData() {}
                
                BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth): 
                mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
    };

        typedef std::stack<BspTraversalData> BspTraversalStack;

        /** Constructs BSP tree from list of view cells.
        */ 
        BspTree(const ViewCellContainer &viewCells);
        /** Constructs BSP tree from list of objects.
                @param object list of intersectables
                @param maxPolys maximal allowed number of polygons
                @param maxDepth maximal allowed BSP tree depth
        */
        BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth);

        ~BspTree();

protected:
        /** Builds a new extension of the tree.
        */
        void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData, ViewCell *viewCell = NULL);

        /** Selects a splitting plane from the given polygons. 
        */
        Plane3 SelectPlane(PolygonQueue *polyQueue);

        /** Filters next viewcell down the tree and inserts it into the appropriate leaves
                (i.e., possibly more than one leaf).
        */
        void InsertViewCell(ViewCell *viewCell);

        /** Subdivides tree according to the given list of viewcells.
        */
        void Subdivide(const ViewCellContainer &viewCells);
        /** Subdivides tree according to the given list of objects.
        */
        void Subdivide(const ObjectContainer &objects);
        
        /** Subdivides 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, 
                                                        PolygonQueue *polys, const int depth, 
                                                        ViewCell *viewCell,
                                                        PolygonQueue *frontPolys, PolygonQueue *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, PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys);

        /** Extracts the mesh instances of the objects and copies them into the mesh.
        */
        static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);

        static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);

        /// Pointer to the root of the tree
        BspNode *mRoot;
        /// Pointer to the root cell of the viewspace
        // ViewCell *mRootCell;
        /// maximal number of polygons allowed in leaf
        int mMaxPolys;
        /// maximal depth
        int mMaxDepth;

        BspTreeStatistics mStat;
};

//}; // GtpVisibilityPreprocessor

#endif