Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 225)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 233)
@@ -5,4 +5,5 @@
 #include "Containers.h"
 #include <queue>
+#include <stack>
 
 class ViewCell;
@@ -15,200 +16,222 @@
 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:
+typedef std::queue<Polygon *> PolygonQueue;
+
+/**
+    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;
 		
-	  /// 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;
-  };
-  
+		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);
+
+	/** 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;
+};
+
 //}; // GtpVisibilityPreprocessor
 
