Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 222)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 224)
@@ -3,4 +3,7 @@
 
 #include "Mesh.h"
+#include "Containers.h"
+
+
 class ViewCell;
 class Plane3;
@@ -8,5 +11,5 @@
 
 //namespace GtpVisibilityPreprocessor {
-  
+class BspTree;  
 class BspInterior;
 
@@ -17,4 +20,6 @@
   class BspNode 
   {
+	  friend BspTree;
+
   public:
 	  /** Determines whether this node is a leaf or not
@@ -28,4 +33,8 @@
 	  virtual bool IsRoot() const;
 
+	  /** Returns parent node.
+	  */
+	  BspInterior *GetParent();
+	  
   protected:
 
@@ -34,14 +43,18 @@
   };
 
-  /** BSP interior node implementation */
+  /** BSP interior node implementation 
+  */
   class BspInterior : public BspNode 
-  {   
+  {
   public:
-	  BspInterior(Plane3 plane): mPlane(plane) {}
-	  /** @return false since it is an interior node */
+	  /** Standard contructor taking split plane as argument.
+	  */
+	  BspInterior(Plane3 plane);
+	  /** @return false since it is an interior node 
+	  */
 	  bool IsLeaf() const;
 
-	  BspNode *GetBack() {return mBack;}
-	  BspNode *GetFront() {return mFront;}
+	  BspNode *GetBack();
+	  BspNode *GetFront();
 
 	  Plane3 *GetPlane();
@@ -78,5 +91,5 @@
   };
   
-  /** Implementation of the ViewCell BSP tree */
+  /** Implementation of the ViewCell BSP tree. */
   class BspTree 
   {
@@ -84,33 +97,73 @@
 	  struct BspTraversalData
 	  {  
+		  /// the current node
 		  BspNode *mNode;
+		  /// parent of current node
 		  BspInterior *mParent;
-
-		  Mesh mViewCell;
+		  /// polygonal data for splitting
+		  Mesh *mPolys;
+		  /// current depth
 		  int mDepth;
 		      
 		  BspTraversalData() {}
-		  BspTraversalData(BspNode *n, BspInterior *p, const Mesh &m, const int d): 
-		  mNode(n), mParent(p), mViewCell(m), mDepth(d) {}
+		  
+		  BspTraversalData(BspNode *node, BspInterior *parent, Mesh *polys, const int depth): 
+		  mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
       };
 	 
-	  /** Constructor takes a pointer to the cell corresponding to the whole
-	  viewspace */
-	  BspTree(ViewCell *cell);
-        
+	  /** 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. */
+	  /** Selects a splitting plane from the given polygons. 
+	  */
 	  Plane3 SelectPlane(Mesh *polys);
 
-	  void Subdivide();
+	  /** 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, 
-							 Mesh *viewCell, const int depth, 
+							 Mesh *polys, const int depth, 
 							 Mesh &frontPolys, Mesh &backPolys);
+
+	  /** Extracts the mesh instances of the objects and copies them into the mesh.
+	  */
+	  static void Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh);
+
 
 	  /// Pointer to the root of the tree
 	  BspNode *mRoot;
 	  /// Pointer to the root cell of the viewspace
-	  ViewCell *mRootCell;
+	  // ViewCell *mRootCell;
+	  /// maximal number of polygons allowed in leaf
+	  int mMaxPolys;
+	  /// maximal depth
+	  int mMaxDepth;
   };
   
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Intersectable.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Intersectable.h	(revision 176)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Intersectable.h	(revision 224)
@@ -13,5 +13,5 @@
   KdPvs mKdPvs;
   
-  enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE };
+  enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEWCELL };
   
   Intersectable():mailbox(0) {}
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h	(revision 221)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h	(revision 224)
@@ -1,4 +1,6 @@
 #ifndef _ViewCell_H__
 #define _ViewCell_H__
+
+#include "Intersectable.h"
 
 class Mesh;
@@ -11,5 +13,5 @@
 	View cell represented as a mesh
 */
-class ViewCell
+class ViewCell: public Intersectable
 {
 public:
@@ -28,4 +30,16 @@
 	BspPvs *GetPVS() {return mPvs;}
 
+	AxisAlignedBox3 GetBox()  {return mMesh->mBox;}
+  
+	int CastRay(Ray &ray) {return 0;}
+  
+	bool IsConvex() {return mMesh->mIsConvex;}
+	bool IsWatertight() {return mMesh->mIsWatertight;}
+	float IntersectionComplexity() {return mMesh->mFaces.size();}
+
+	int Type() const { return VIEWCELL; }
+
+	void GetRandomSurfacePoint(Vector3 &point, Vector3 &normal) {point = Vector3(0,0,0);};
+
 protected:
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 222)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 224)
@@ -6,4 +6,6 @@
 #include <stack>
 
+#define DEL_PTR(ptr) while (0) {if (ptr) {delete (ptr); (ptr) = NULL;}}
+
 //namespace GtpVisibilityPreprocessor {
 /****************************************************************/
@@ -15,4 +17,8 @@
 }
 
+BspInterior *BspNode::GetParent() 
+{ 
+	return mParent; 
+}
 /****************************************************************/
 /*              class BspInterior implementation                */
@@ -61,5 +67,4 @@
 }
 
-
 /****************************************************************/
 /*                  class BspLeaf implementation                */
@@ -84,12 +89,50 @@
 /****************************************************************/
 
-BspTree::BspTree(ViewCell *cell) 
-{
-	mRootCell = cell;
-	mRoot = new BspLeaf(mRootCell);
-}
-
-  
-void BspTree::Subdivide()
+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());
+		}
+
+		delete node;
+		node = NULL;
+	}
+}
+
+
+void BspTree::InsertViewCell(ViewCell *viewCell)
 {
 	BspNode *currentNode = mRoot;
@@ -103,4 +146,5 @@
 	{
 	    BspTraversalData data = tStack.top();
+
 	    tStack.pop();
     
@@ -112,5 +156,5 @@
 			BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
 										  data.mParent,
-										  &data.mViewCell,
+										  data.mPolys,
 									      data.mDepth,
 										  backPolys,
@@ -122,6 +166,6 @@
 
 				// 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));
+				//tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
+				//tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
 			}
 		}
@@ -129,5 +173,73 @@
 }
 
-Plane3 BspTree::SelectPlane(Mesh *polys)
+void BspTree::Subdivide(const ViewCellContainer &viewCells)
+{
+}
+
+void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh)
+{
+	ObjectContainer::const_iterator it, it_end = objects.end();
+
+	for (it = objects.begin(); it != it_end; ++ it)
+	{
+		FaceContainer::const_iterator fi;
+		Intersectable *object = *it;
+
+		// extract the mesh instances
+		if (object->Type() == Intersectable::MESH_INSTANCE)
+		{
+			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);
+			}
+		}
+	}
+}
+
+void BspTree::Subdivide(const ObjectContainer &objects)
+{
+	std::stack<BspTraversalData> tStack;
+	Mesh 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();
+    
+		Mesh backPolys;
+		Mesh frontPolys;
+
+		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(Mesh *polys) 
 {
 	// TODO: more sophisticated criteria
@@ -136,44 +248,55 @@
 
 BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-								Mesh *viewCell, const int depth, 
+								Mesh *polys, const int depth, 
 								Mesh &frontPolys, Mesh &backPolys)
 {
-	ViewCell *viewCell = leaf->GetViewCell();
-
-	// terminate traversal if no more faces in mesh or outside
-	if (!viewCell || (viewCell->mFaces.size() == 0))
-	{
+	// 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
+
 		return leaf;
 	}
+
 	// add the new nodes to the tree + select subdivision plane
-	BspInterior *node = new BspInterior(SelectPlane(viewCell)); 
+	BspInterior *node = new BspInterior(SelectPlane(polys)); 
 
  	FaceContainer::const_iterator fi;
 
-	for (fi = viewCell->mFaces.begin(); fi != viewCell->mFaces.end(); ++ fi)
-	{
-		int  result = node->GetPlane()->Side();
-		Mesh *front_piece, *back_piece;
+	for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
+	{
+		Face *face = (*fi);
+
+		int  result = 0;// = node->GetPlane()->Side(node->GetPlane());
+
+		Face *front_piece, *back_piece;
 
 		switch (result)
 		{
 			case 1:
-				frontPolys.AddFace(poly);
+				frontPolys.AddFace(face);
 				break;
 			case -1:
-				backPolys.AddFace(poly);
+				backPolys.AddFace(face);
 				break;
 			case 0:
-				//Split_Polygon (poly, tree->partition, front_piece, back_piece);
+				//Split_Polygon (face, tree->partition, front_piece, back_piece);
 				backPolys.AddFace(back_piece);
 				frontPolys.AddFace(front_piece);
+
+				// face not needed anymore
+				DEL_PTR(face);
+
 				break;
-			default;
-				brak;
-		}
-	}
+			default:
+				break;
+		}
+	}
+
 	// backside of convex view cell polygon => outside
-	BspLeaf *back = new BspLeaf(NULL);
-	BspLeaf *front = new BspLeaf(viewCell);
+	BspLeaf *back = new BspLeaf();
+	BspLeaf *front = new BspLeaf();
 
 	// replace a link from node's parent
@@ -185,6 +308,11 @@
 	// and setup child links
 	node->SetupChildLinks(back, front);
-  
-	delete leaf;
+
+  	// 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);
+
 	return node;
 }
