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

#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

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

class ViewCell;
class Plane3;
//class Mesh;

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

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

  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;
  };
  
  typedef std::queue<Polygon *> PolygonQueue;

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


          /** 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:
          /** 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, 
                                                         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;
  };
  
//}; // GtpVisibilityPreprocessor

#endif