Index: /trunk/VUT/GtpVisibilityPreprocessor/include/ViewCellBsp.h
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/include/ViewCellBsp.h	(revision 221)
+++ /trunk/VUT/GtpVisibilityPreprocessor/include/ViewCellBsp.h	(revision 225)
@@ -29,6 +29,4 @@
   protected:
 
-	  void SplitPoly(Plane3 *plane, Mesh *viewcell);
-
 	  /// parent of this node
 	  BspInterior *mParent;
@@ -38,18 +36,19 @@
   class BspInterior : public BspNode 
   {    
-	/** @return false since it is an interior node */
-	bool IsLeaf() const;
-
-	protected:
-	/// Splitting plane corresponding to this node
-	Plane3 mPlane;
-	/// back node
-	BspNode *mBack;
-	/// front node
-	BspNode *mFront;
+	  /** @return false since it is an interior node */
+	  bool IsLeaf() const;
+  
+  protected:
+	  /// Splitting plane corresponding to this node
+	  Plane3 mPlane;
+	  /// back node
+	  BspNode *mBack;
+	  /// front node
+	  BspNode *mFront;
   };
   
   
-  /** BSP leaf node implementation */
+  /** BSP leaf node implementation.
+  */
   class BspLeaf : public BspNode 
   {
@@ -65,5 +64,6 @@
   };
   
-  /** Implementation of the ViewCell BSP tree */
+  /** Implementation of the ViewCell BSP tree.
+  */
   class BspTree 
   {
Index: /trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj	(revision 221)
+++ /trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj	(revision 225)
@@ -217,4 +217,7 @@
 			</File>
 			<File
+				RelativePath="..\src\Rectangle3.cpp">
+			</File>
+			<File
 				RelativePath="..\src\Rectangle3.h">
 			</File>
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 224)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 225)
@@ -4,5 +4,5 @@
 #include "Mesh.h"
 #include "Containers.h"
-
+#include <queue>
 
 class ViewCell;
@@ -13,5 +13,5 @@
 class BspTree;  
 class BspInterior;
-
+class Polygon;
 
   /**
@@ -91,8 +91,49 @@
   };
   
+  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
 	  {  
@@ -102,5 +143,5 @@
 		  BspInterior *mParent;
 		  /// polygonal data for splitting
-		  Mesh *mPolys;
+		  PolygonQueue *mPolys;
 		  /// current depth
 		  int mDepth;
@@ -108,8 +149,9 @@
 		  BspTraversalData() {}
 		  
-		  BspTraversalData(BspNode *node, BspInterior *parent, Mesh *polys, const int depth): 
+		  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.
 	  */ 
@@ -127,5 +169,5 @@
 	  /** Selects a splitting plane from the given polygons. 
 	  */
-	  Plane3 SelectPlane(Mesh *polys);
+	  Plane3 SelectPlane(PolygonQueue *polyQueue);
 
 	  /** Filters next viewcell down the tree and inserts it into the appropriate leaves
@@ -150,11 +192,12 @@
 	  */
 	  BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-							 Mesh *polys, const int depth, 
-							 Mesh &frontPolys, Mesh &backPolys);
+							 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, Mesh &mesh);
-
+	  static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);
+
+	  static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);
 
 	  /// Pointer to the root of the tree
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 224)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 225)
@@ -86,4 +86,118 @@
 
 /****************************************************************/
+/*                  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                */
 /****************************************************************/
@@ -128,6 +242,5 @@
 		}
 
-		delete node;
-		node = NULL;
+		DEL_PTR(node);
 	}
 }
@@ -136,5 +249,33 @@
 void BspTree::InsertViewCell(ViewCell *viewCell)
 {
-	BspNode *currentNode = mRoot;
+	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;
@@ -170,5 +311,5 @@
 			}
 		}
-	}
+	}*/
 }
 
@@ -177,5 +318,16 @@
 }
 
-void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh)
+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();
@@ -183,5 +335,4 @@
 	for (it = objects.begin(); it != it_end; ++ it)
 	{
-		FaceContainer::const_iterator fi;
 		Intersectable *object = *it;
 
@@ -191,12 +342,8 @@
 			MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
 
-			Mesh *polys = inst->GetMesh();
-
-			// copy the face data
-			for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
-			{
-				Face *face = new Face((*fi)->mVertexIndices);
-				mesh.AddFace(face);
-			}
+			Mesh *mesh = inst->GetMesh();
+
+			// copy the mesh data to polygons
+			CopyMesh2Polygon(mesh, polys);
 		}
 	}
@@ -206,5 +353,5 @@
 {
 	std::stack<BspTraversalData> tStack;
-	Mesh polys;
+	PolygonQueue polys;
 	
 	// copy mesh instance polygons into one big polygon soup
@@ -220,6 +367,6 @@
 	    tStack.pop();
     
-		Mesh backPolys;
-		Mesh frontPolys;
+		PolygonQueue *backPolys = new PolygonQueue();
+		PolygonQueue *frontPolys = new PolygonQueue();
 
 		BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
@@ -235,27 +382,26 @@
 
 			// 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(Mesh *polys) 
+			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 polys->GetFacePlane(0);
+	return polyQueue->front()->GetSupportingPlane();
 }
 
 BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-								Mesh *polys, const int depth, 
-								Mesh &frontPolys, Mesh &backPolys)
+								PolygonQueue *polys, const int depth, 
+								PolygonQueue *frontPolys, PolygonQueue *backPolys)
 {
 	// terminate traversal if no more faces in mesh
-	if ((polys->mFaces.size() <= mMaxPolys) || (depth >= mMaxDepth))
-	{
-		// don't need to store polygon information
-		polys->mFaces->clear(); // HACK: faces were deleted before
-		DEL_PTR(polys); // we can savely delete mesh
-
+	if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
+	{
+		// don't need to store polygon information = delete polygons
+		Polygon::DeletePolygons(polys);
+		
 		return leaf;
 	}
@@ -264,32 +410,40 @@
 	BspInterior *node = new BspInterior(SelectPlane(polys)); 
 
- 	FaceContainer::const_iterator fi;
-
-	for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
-	{
-		Face *face = (*fi);
+ 	while (!polys->empty())
+	{
+		Polygon *poly = polys->front();
+
+		polys->pop();
 
 		int  result = 0;// = node->GetPlane()->Side(node->GetPlane());
 
-		Face *front_piece, *back_piece;
+		Polygon *front_piece = NULL;
+		Polygon *back_piece = NULL;
 
 		switch (result)
 		{
-			case 1:
-				frontPolys.AddFace(face);
+			case Polygon::COINCIDENT:
+			case Polygon::FRONT_SIDE:
+				frontPolys->push(poly);
 				break;
-			case -1:
-				backPolys.AddFace(face);
+			case Polygon::BACK_SIDE:
+				backPolys->push(poly);
 				break;
-			case 0:
-				//Split_Polygon (face, tree->partition, front_piece, back_piece);
-				backPolys.AddFace(back_piece);
-				frontPolys.AddFace(front_piece);
-
-				// face not needed anymore
-				DEL_PTR(face);
-
+			case Polygon::SPLIT:
+				front_piece = new Polygon();
+				back_piece = new Polygon();
+
+				//-- split polygon
+                poly->Split(node->GetPlane(), front_piece, back_piece);
+
+
+				backPolys->push(back_piece);
+				frontPolys->push(front_piece);
+
+				// don't need polygon anymore
+				DEL_PTR(poly);
 				break;
 			default:
+				frontPolys->push(poly);
 				break;
 		}
@@ -309,8 +463,4 @@
 	node->SetupChildLinks(back, front);
 
-  	// don't need to store polygon information
-	polys->mFaces->clear(); // HACK: faces were deleted before
-	DEL_PTR(polys); // we can savely delete mesh
-
 	DEL_PTR(leaf);
 
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h	(revision 209)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h	(revision 225)
@@ -41,5 +41,5 @@
 			   float *t = NULL,
 			   bool *coplanar = NULL
-			   ) const;
+			   ) const {return Vector3(0,0,0);} // TODO
 
   friend bool
