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
 
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 225)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 233)
@@ -67,354 +67,13 @@
 }
 
-/****************************************************************/
-/*                  class BspLeaf implementation                */
-/****************************************************************/
-
-BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
-{
-}
-
-ViewCell *BspLeaf::GetViewCell()
-{
-	return mViewCell;
-}
-
-bool BspLeaf::IsLeaf() const 
-{ 
-	return true; 
-}
-
-/****************************************************************/
-/*                  class Polygon implementation                */
-/****************************************************************/
-
-Polygon::Polygon()
-{}
-
-Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices) 
-{}
-
-Polygon::Polygon(Face *face, Mesh *parent)
-{
-	VertexIndexContainer::const_iterator it;
-
-	for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
-	{
-		mVertices.push_back(parent->mVertices[*it]);
-	}
-}
-
-Plane3 Polygon::GetSupportingPlane()
-{
-	return Plane3(mVertices[0], mVertices[1], mVertices[2]);
-}
-
-void Polygon::DeletePolygons(PolygonQueue *polys)
-{
-	// don't need to store polygon information = delete polygons
-	while(!polys->empty())
+void BspInterior::SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys)
+{
+ 	while (!polys->empty())
 	{
 		Polygon *poly = polys->front();
+
 		polys->pop();
-		DEL_PTR(poly);
-	}
-
-}
-
-void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back)
-{
-	Vector3 ptA = mVertices[mVertices.size() - 1];;
-	
-	int sideA = partition->Side(ptA);
-	
-	VertexContainer::const_iterator it;
-
-	// find line - plane intersections
-	for (it = mVertices.begin(); it != mVertices.end(); ++ it)
-	{
-		Vector3 ptB = (*it);
-		int sideB = partition->Side(ptB);
-
-		// vertices on different sides => split
-		if ((sideA != 0) && (sideB != 0) && (sideA != sideB)) 
-		{
-			Vector3 v = ptB - ptA; // line from A to B
-			float dv = DotProd(partition->mNormal, v);
-			float t = 0;
-			
-			if (dv)
-			{
-				t = - partition->Distance(ptA) / dv;
-			}
-		}
-		if (sideB >= 0)
-		{
-			back->mVertices.push_back(ptB);
-		}
-		else if (sideB <= 0)
-		{
-			front->mVertices.push_back(ptB);
-		}
-
-		ptA = ptB;
-		sideA = sideB;
-	}
-}
-
-int Polygon::Side(Plane3 *plane)
-{
-	VertexContainer::const_iterator it;
-
-	bool onFrontSide = false;
-	bool onBackSide = false;
-
-	// find line - plane intersections
-	for (it = mVertices.begin(); it != mVertices.end(); ++ it)
-	{
-		int side = plane->Side(*it);
-		
-		if (side > 0)
-		{
-			onFrontSide = true;
-		}
-		else if (side < 0)
-		{
-			onBackSide = true;
-		}
-
-		if (onFrontSide && onBackSide) // splits
-			return SPLIT;
-	}
-
-	if (onBackSide)
-	{
-		return BACK_SIDE;
-	}
-	else if (onFrontSide)
-	{
-		return FRONT_SIDE;
-	}
-
-	return COINCIDENT;
-}
-
-/****************************************************************/
-/*                  class BspTree implementation                */
-/****************************************************************/
-
-BspTree::BspTree(const ViewCellContainer &viewCells): 
-mMaxPolys(0), mMaxDepth(0), mRoot(NULL)
-{
-	//mRootCell = cell;
-	Subdivide(viewCells);
-}
-
-BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth):
-mMaxPolys(maxPolys), mMaxDepth(maxDepth)
-{
-	mRoot = new BspLeaf();
-
-	Subdivide(objects);
-}
- 
-BspTree::~BspTree()
-{
-	std::stack<BspNode *> tStack;
-
-	tStack.push(mRoot);
-
-	while (!tStack.empty())
-	{
-		BspNode *node = tStack.top();
-
-	    tStack.pop();
-	
-		if (!node->IsLeaf())
-		{
-			BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-			// push the children on the stack (there are always two children)
-			interior->GetBack()->mParent = NULL;
-			interior->GetFront()->mParent = NULL;
-
-			tStack.push(interior->GetBack());
-			tStack.push(interior->GetFront());
-		}
-
-		DEL_PTR(node);
-	}
-}
-
-
-void BspTree::InsertViewCell(ViewCell *viewCell)
-{
-	std::stack<BspTraversalData> tStack;
-	
-	PolygonQueue polys;
-	// copy polygon information to guide the split process
-	CopyMesh2Polygon(viewCell->GetMesh(), polys);
-
-	tStack.push(BspTraversalData(mRoot, NULL, &polys, 0));
-
-	while (!tStack.empty())
-	{
-		/*BspNode *node = tStack.top();
-
-	    tStack.pop();
-	
-		if (!node->IsLeaf())
-		{
-			BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-			// push the children on the stack (there are always two children)
-			interior->GetBack()->mParent = NULL;
-			interior->GetFront()->mParent = NULL;
-
-			tStack.push(interior->GetBack());
-			tStack.push(interior->GetFront());
-		}
-
-		DEL_PTR(node);*/
-	}
-/*	BspNode *currentNode = mRoot;
-  
-	std::stack<BspTraversalData> tStack;
-	//  stack<STraversalData> tStack;
-
-	//tStack.push(tdata);
-
-	while (!tStack.empty()) 
-	{
-	    BspTraversalData data = tStack.top();
-
-	    tStack.pop();
-    
-		Mesh backPolys;
-		Mesh frontPolys;
-
-		if (data.mNode->IsLeaf()) // if we have a leaf => subdivide
-		{
-			BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
-										  data.mParent,
-										  data.mPolys,
-									      data.mDepth,
-										  backPolys,
-										  frontPolys);
-	
-			if (!node->IsLeaf()) // node was subdivided
-			{
-				BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-				// push the children on the stack (there are always two children)
-				//tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
-				//tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
-			}
-		}
-	}*/
-}
-
-void BspTree::Subdivide(const ViewCellContainer &viewCells)
-{
-}
-
-void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys)
-{
-	FaceContainer::const_iterator fi;
-	// copy the face data to polygons
-	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
-	{
-		Polygon *poly = new Polygon((*fi), mesh);
-		polys.push(poly);
-	}
-}
-
-void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys)
-{
-	ObjectContainer::const_iterator it, it_end = objects.end();
-
-	for (it = objects.begin(); it != it_end; ++ it)
-	{
-		Intersectable *object = *it;
-
-		// extract the mesh instances
-		if (object->Type() == Intersectable::MESH_INSTANCE)
-		{
-			MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
-
-			Mesh *mesh = inst->GetMesh();
-
-			// copy the mesh data to polygons
-			CopyMesh2Polygon(mesh, polys);
-		}
-	}
-}
-
-void BspTree::Subdivide(const ObjectContainer &objects)
-{
-	std::stack<BspTraversalData> tStack;
-	PolygonQueue polys;
-	
-	// copy mesh instance polygons into one big polygon soup
-	Copy2PolygonSoup(objects, polys);
-
-	BspTraversalData tdata(mRoot, mRoot->GetParent(), &polys, 0);
-	tStack.push(tdata);
-
-	while (!tStack.empty()) 
-	{
-	    BspTraversalData data = tStack.top();
-
-	    tStack.pop();
-    
-		PolygonQueue *backPolys = new PolygonQueue();
-		PolygonQueue *frontPolys = new PolygonQueue();
-
-		BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
-									  data.mParent,
-									  data.mPolys,
-								      data.mDepth,
-									  backPolys,
-									  frontPolys);
-	
-		if (!node->IsLeaf()) // node was subdivided
-		{
-			BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-			// push the children on the stack (there are always two children)
-			tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
-			tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
-		}
-	}
-}
-
-Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue) 
-{
-	// TODO: more sophisticated criteria
-	return polyQueue->front()->GetSupportingPlane();
-}
-
-BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-								PolygonQueue *polys, const int depth, 
-								PolygonQueue *frontPolys, PolygonQueue *backPolys)
-{
-	// terminate traversal if no more faces in mesh
-	if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
-	{
-		// don't need to store polygon information = delete polygons
-		Polygon::DeletePolygons(polys);
-		
-		return leaf;
-	}
-
-	// add the new nodes to the tree + select subdivision plane
-	BspInterior *node = new BspInterior(SelectPlane(polys)); 
-
- 	while (!polys->empty())
-	{
-		Polygon *poly = polys->front();
-
-		polys->pop();
-
-		int  result = 0;// = node->GetPlane()->Side(node->GetPlane());
+
+		int result = poly->Side(&mPlane);
 
 		Polygon *front_piece = NULL;
@@ -424,4 +83,5 @@
 		{
 			case Polygon::COINCIDENT:
+				break;
 			case Polygon::FRONT_SIDE:
 				frontPolys->push(poly);
@@ -435,6 +95,5 @@
 
 				//-- split polygon
-                poly->Split(node->GetPlane(), front_piece, back_piece);
-
+                poly->Split(&mPlane, front_piece, back_piece);
 
 				backPolys->push(back_piece);
@@ -445,12 +104,383 @@
 				break;
 			default:
-				frontPolys->push(poly);
 				break;
 		}
 	}
-
-	// backside of convex view cell polygon => outside
+	// delete old polygons
+	Polygon::DeletePolygons(polys);
+}
+
+/****************************************************************/
+/*                  class BspLeaf implementation                */
+/****************************************************************/
+
+BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
+{
+}
+
+ViewCell *BspLeaf::GetViewCell()
+{
+	return mViewCell;
+}
+
+bool BspLeaf::IsLeaf() const 
+{ 
+	return true; 
+}
+
+/****************************************************************/
+/*                  class Polygon implementation                */
+/****************************************************************/
+
+Polygon::Polygon()
+{}
+
+Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices) 
+{}
+
+Polygon::Polygon(Face *face, Mesh *parent)
+{
+	VertexIndexContainer::const_iterator it;
+
+	for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
+	{
+		mVertices.push_back(parent->mVertices[*it]);
+	}
+}
+
+Plane3 Polygon::GetSupportingPlane()
+{
+	return Plane3(mVertices[0], mVertices[1], mVertices[2]);
+}
+
+void Polygon::DeletePolygons(PolygonQueue *polys)
+{
+	// don't need to store polygon information = delete polygons
+	while(!polys->empty())
+	{
+		Polygon *poly = polys->front();
+		polys->pop();
+		DEL_PTR(poly);
+	}
+}
+
+void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back)
+{
+	Vector3 ptA = mVertices[mVertices.size() - 1];;
+	
+	int sideA = partition->Side(ptA);
+	
+	VertexContainer::const_iterator it;
+
+	// find line - plane intersections
+	for (it = mVertices.begin(); it != mVertices.end(); ++ it)
+	{
+		Vector3 ptB = (*it);
+		int sideB = partition->Side(ptB);
+
+		// vertices on different sides => split
+		if ((sideA != 0) && (sideB != 0) && (sideA != sideB)) 
+		{
+			Vector3 v = ptB - ptA; // line from A to B
+			float dv = DotProd(partition->mNormal, v);
+			float t = 0;
+			
+			if (dv)
+			{
+				t = - partition->Distance(ptA) / dv;
+			}
+		}
+		if (sideB >= 0)
+		{
+			back->mVertices.push_back(ptB);
+		}
+		else if (sideB <= 0)
+		{
+			front->mVertices.push_back(ptB);
+		}
+
+		ptA = ptB;
+		sideA = sideB;
+	}
+}
+
+int Polygon::Side(Plane3 *plane)
+{
+	VertexContainer::const_iterator it;
+
+	bool onFrontSide = false;
+	bool onBackSide = false;
+
+	// find line - plane intersections
+	for (it = mVertices.begin(); it != mVertices.end(); ++ it)
+	{
+		int side = plane->Side(*it);
+		
+		if (side > 0)
+		{
+			onFrontSide = true;
+		}
+		else if (side < 0)
+		{
+			onBackSide = true;
+		}
+
+		if (onFrontSide && onBackSide) // splits
+			return SPLIT;
+	}
+
+	if (onBackSide)
+	{
+		return BACK_SIDE;
+	}
+	else if (onFrontSide)
+	{
+		return FRONT_SIDE;
+	}
+
+	return COINCIDENT;
+}
+
+/****************************************************************/
+/*                  class BspTree implementation                */
+/****************************************************************/
+
+BspTree::BspTree(const ViewCellContainer &viewCells): 
+mMaxPolys(0), mMaxDepth(0), mRoot(NULL)
+{
+	//mRootCell = cell;
+	Subdivide(viewCells);
+}
+
+BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth):
+mMaxPolys(maxPolys), mMaxDepth(maxDepth)
+{
+	mRoot = new BspLeaf();
+
+	Subdivide(objects);
+}
+ 
+BspTree::~BspTree()
+{
+	std::stack<BspNode *> tStack;
+
+	tStack.push(mRoot);
+
+	while (!tStack.empty())
+	{
+		BspNode *node = tStack.top();
+
+	    tStack.pop();
+	
+		if (!node->IsLeaf())
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+			// push the children on the stack (there are always two children)
+			interior->GetBack()->mParent = NULL;
+			interior->GetFront()->mParent = NULL;
+
+			tStack.push(interior->GetBack());
+			tStack.push(interior->GetFront());
+		}
+
+		DEL_PTR(node);
+	}
+}
+
+
+void BspTree::InsertViewCell(ViewCell *viewCell)
+{
+	std::stack<BspTraversalData> tStack;
+	
+	PolygonQueue polys;
+	// copy polygon information to guide the split process
+	CopyMesh2Polygon(viewCell->GetMesh(), polys);
+
+	tStack.push(BspTraversalData(mRoot, NULL, &polys, 0, viewCell));
+
+	while (!tStack.empty())
+	{
+		// filter polygons donw the tree
+		BspTraversalData tData = tStack.top();
+
+	    tStack.pop();
+	
+        if (!tData.mNode->IsLeaf())
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
+
+			// filter polygons down the tree.
+			PolygonQueue *frontPolys = new PolygonQueue();
+			PolygonQueue *backPolys = new PolygonQueue();
+
+			interior->SplitPolygons(tData.mPolys, frontPolys, backPolys);
+
+			// push the children on the stack
+			if (frontPolys->size() > 0)
+				tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), frontPolys, tData.mDepth + 1));
+			else
+				delete frontPolys;
+
+			if (backPolys > 0)
+				tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1)); // TODO: really need to keep viewcell??
+			else
+				delete backPolys;
+		}
+		else // reached leaf and must split
+		{
+			BuildTree(tStack, tData);
+		}
+	}
+/*	BspNode *currentNode = mRoot;
+  
+	std::stack<BspTraversalData> tStack;
+	//  stack<STraversalData> tStack;
+
+	//tStack.push(tdata);
+
+	while (!tStack.empty()) 
+	{
+	    BspTraversalData data = tStack.top();
+
+	    tStack.pop();
+    
+		Mesh backPolys;
+		Mesh frontPolys;
+
+		if (data.mNode->IsLeaf()) // if we have a leaf => subdivide
+		{
+			BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
+										  data.mParent,
+										  data.mPolys,
+									      data.mDepth,
+										  data.viewCell,
+										  backPolys,
+										  frontPolys);
+	
+			if (!node->IsLeaf()) // node was subdivided
+			{
+				BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+				// push the children on the stack (there are always two children)
+				//tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
+				//tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
+			}
+		}
+	}*/
+}
+
+void BspTree::Subdivide(const ViewCellContainer &viewCells)
+{
+}
+
+void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys)
+{
+	FaceContainer::const_iterator fi;
+	// copy the face data to polygons
+	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
+	{
+		Polygon *poly = new Polygon((*fi), mesh);
+		polys.push(poly);
+	}
+}
+
+void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys)
+{
+	ObjectContainer::const_iterator it, it_end = objects.end();
+
+	for (it = objects.begin(); it != it_end; ++ it)
+	{
+		Intersectable *object = *it;
+
+		// extract the mesh instances
+		if (object->Type() == Intersectable::MESH_INSTANCE)
+		{
+			MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
+
+			Mesh *mesh = inst->GetMesh();
+
+			// copy the mesh data to polygons
+			CopyMesh2Polygon(mesh, polys);
+		}
+	}
+}
+
+void BspTree::Subdivide(const ObjectContainer &objects)
+{
+	std::stack<BspTraversalData> tStack;
+	PolygonQueue *polys = new PolygonQueue();
+	
+	// copy mesh instance polygons into one big polygon soup
+	Copy2PolygonSoup(objects, *polys);
+
+	BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0, NULL);
+	tStack.push(tData);
+
+	while (!tStack.empty()) 
+	{
+	    tData = tStack.top();
+
+	    tStack.pop();
+    
+		BuildTree(tStack, tData);
+	}
+}
+
+void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData)
+{
+	PolygonQueue *backPolys = new PolygonQueue();
+	PolygonQueue *frontPolys = new PolygonQueue();
+
+	BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(currentData.mNode),
+								  currentData.mParent,
+								  currentData.mPolys,
+								  currentData.mDepth,
+								  currentData.mViewCell,
+								  backPolys,
+								  frontPolys);
+	
+	if (!node->IsLeaf()) // node was subdivided
+	{
+		BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+		// push the children on the stack (there are always two children)
+		tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1, NULL));
+		tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1, currentData.mViewCell));
+	}
+}
+
+Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue) 
+{
+	// TODO: more sophisticated criteria
+	return polyQueue->front()->GetSupportingPlane();
+}
+
+BspNode *BspTree::SubdivideNode(BspLeaf *leaf, 
+								BspInterior *parent, 
+								PolygonQueue *polys, 
+								const int depth, 
+								ViewCell *viewCell,
+								PolygonQueue *frontPolys, 
+								PolygonQueue *backPolys)
+{
+	// terminate traversal if no more faces in mesh
+	if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
+	{
+		// don't need to store polygon information = delete polygons
+		Polygon::DeletePolygons(polys);
+		
+		return leaf;
+	}
+
+	// add the new nodes to the tree + select subdivision plane
+	BspInterior *node = new BspInterior(SelectPlane(polys)); 
+
+	// split polygon according to current plane
+	node->SplitPolygons(polys, frontPolys, backPolys);
+ 	
+	// two new leaves
 	BspLeaf *back = new BspLeaf();
-	BspLeaf *front = new BspLeaf();
+	BspLeaf *front = new BspLeaf(viewCell);
 
 	// replace a link from node's parent
@@ -467,4 +497,3 @@
 	return node;
 }
-
 //} // GtpVisibilityPreprocessor
