Index: trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 275)
+++ trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 286)
@@ -8,11 +8,13 @@
 #	filename glasgow1.x3d
 #	filename vienna.x3d
-	filename ../data/atlanta/atlanta2.x3d
+	filename ../data/vienna/vienna-simple.x3d
+#	filename ../data/vienna/viewcells-25-sel.x3d
+#	filename ../data/atlanta/atlanta2.x3d
 #	filename ../data/soda/soda.dat
 #	filename ../data/soda/soda5.dat
 #	viewcells ../data/atlanta/atlanta_viewcells_large.x3d
 #viewcells ../data/atlanta/atlanta_viewcells_large2.x3d
-#	viewcells ../data/vienna/viewcells-25-sel.x3d
-	viewcells ../data/vienna/viewcells-25.x3d
+	viewcells ../data/vienna/viewcells-25-sel.x3d
+#	viewcells ../data/vienna/viewcells-25.x3d
 #	viewcells ../data/vienna/viewcells-large-sel.x3d
 }
@@ -68,11 +70,11 @@
 	splitPlaneStrategy combined
 #       constructionMethod rays
-	constructionMethod viewCells
-#	constructionMethod sceneGeometry
+#	constructionMethod viewCells
+	constructionMethod sceneGeometry
 	maxCandidates 25
 	maxViewCells 999999
 	Termination {
-		maxPolygons 0
-		maxDepth 3000
+		maxPolygons 3
+		maxDepth 30
 	}
 }
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h	(revision 270)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h	(revision 286)
@@ -13,5 +13,5 @@
 class Plane3;
 class Face;
-
+class Intersectable;
 
 /** Class representing a general planar polygon in 3d.
@@ -22,8 +22,9 @@
 	Polygon3();
 	Polygon3(const VertexContainer &vertices);
+	Polygon3(Intersectable *parent);
 
 	/** Copies all the vertices of the face.
 	*/
-	Polygon3(Face *face, Mesh *parent);
+	Polygon3(Face *face, Mesh *parentMesh);
 	
 	/** Returns supporting plane of this polygon.
@@ -65,7 +66,7 @@
 	/// we can also store materials with polygons
 	Material *mMaterial;
-
-	static int mLeastSplitTable[4];
-	static int mBalancedTreeTable[4];
+	
+	/// pointer to the intersectable this polygon is derived from
+	Intersectable *mParent;
 };
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 271)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 286)
@@ -144,11 +144,10 @@
 	*/
 	PolygonContainer *GetPolygons();
-int mViewCellIdx;
+	/** Stores polygons in node or discards them according to storePolys.
+	*/
+	void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
+
+//int mViewCellIdx;
 protected:
-
-	/** Adds or discards polygons according to storePolys.
-	*/
-	void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
-
 
 	/// parent of this node
@@ -184,8 +183,17 @@
 		@param backPolys returns the polygons in the back of the split plane
 		@param splits number of splits
-		@returns true if one or more polygons are inside of the split plane
-	*/
-	bool SplitPolygons(PolygonContainer *polys, PolygonContainer *frontPolys, 
-					   PolygonContainer *backPolys, int &splits, bool storePolys = false);
+		@returns split polygon if there is a polygon coincident to the split plane, NULL otherwise
+	*/
+	Polygon3 *SplitPolygons(PolygonContainer *polys, 
+							PolygonContainer *frontPolys, 
+						    PolygonContainer *backPolys, 
+							int &splits, 
+							bool storePolys = false);
+
+	/** Stores polygon in node or discards them according to storePolys.
+		@param polys the polygons
+		@param storePolys if the polygons should be stored or discarded
+	*/
+	void ProcessPolygon(Polygon3 *poly, const bool storePolys);
 
 	friend ostream &operator<<(ostream &s, const BspInterior &A)
@@ -194,11 +202,6 @@
 	}
 
-protected:
+protected:	
 	
-	/** Discards or stores polygon in node.
-		@param polys the polygons
-		@param storePolys if the polygons should be stored or discarded
-	*/
-	void ProcessPolygon(Polygon3 *poly, const bool storePolys);
 
 	/// Splitting plane corresponding to this node
@@ -255,10 +258,12 @@
 		/// current depth
 		int mDepth;
+		/// the polygon that drove the split plane computation
+		Polygon3 *mSplitPoly;
 		/// if the node is an inside or outside node with respect to the parent plane
-		bool mIsInside;
+		//bool mIsInside;
 		BspTraversalData() {}
 		
-		BspTraversalData(BspNode *node, PolygonContainer *polys, const int depth, const bool inside): 
-		mNode(node), mPolygons(polys), mDepth(depth), mIsInside(inside) {}
+		BspTraversalData(BspNode *node, PolygonContainer *polys, const int depth, Polygon3 *splitPoly): 
+		mNode(node), mPolygons(polys), mDepth(depth), mSplitPoly(splitPoly) {}
     };
 
@@ -345,8 +350,8 @@
 	    @param tStack current traversal stack
 		@param tData traversal data also holding node to be subdivided
-		@param viewCell the view cell that will be represented with this part of the Bsp tree.
+		@param viewCellContainer if not null, a new viewcell is created and stored in the container
 		@returns new root of the subtree
 	*/
-	BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);
+	BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCellContainer *viewCells = NULL);
 
 	/** Selects a splitting plane. 
@@ -358,5 +363,5 @@
 		(i.e., possibly more than one leaf).
 	*/
-	void InsertViewCell(ViewCell *viewCell);
+	//void InsertViewCell(ViewCell *viewCell);
 	
 	/** Subdivide leaf.
@@ -365,5 +370,5 @@
 		@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
-		@param if the polygons are outside or inside with respect to the interior node plane
+		@param splitPoly polygon that is coincident to the split plane, NULL if no such polygon
 		@returns the root of the subdivision
 	*/
@@ -371,5 +376,5 @@
 						 	   PolygonContainer *polys, 
 							   PolygonContainer *frontPolys, 
-							   PolygonContainer *backPolys, bool &inside);
+							   PolygonContainer *backPolys, Polygon3 **splitPoly);
 
 	/** Filters polygons down the tree.
@@ -402,7 +407,9 @@
 
 	/** Extract polygons of this mesh and add to polygon container.
+		@param mesh the mesh that drives the polygon construction
+		@param parent the parent intersectable this polygon is constructed from
 		@returns number of polygons
 	*/
-	int AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys);
+	int AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent = NULL);
 
 	/** A ray is cast possible intersecting the tree.
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 276)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 286)
@@ -39,8 +39,8 @@
 /****************************************************************/
 
-BspNode::BspNode(): mParent(NULL), mPolygons(NULL),mViewCellIdx(0)
+BspNode::BspNode(): mParent(NULL), mPolygons(NULL)//,mViewCellIdx(0)
 {}
 
-BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL),mViewCellIdx(0)
+BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL)//,mViewCellIdx(0)
 {}
 
@@ -144,10 +144,10 @@
 }
 
-bool BspInterior::SplitPolygons(PolygonContainer *polys, 
-								PolygonContainer *frontPolys, 
-								PolygonContainer *backPolys, 
-								PolygonContainer *coincident, 
-								int &splits, bool storePolys)
-{
+Polygon3 *BspInterior::SplitPolygons(PolygonContainer *polys, 
+									PolygonContainer *frontPolys, 
+									PolygonContainer *backPolys, 
+									int &splits, bool storePolys)
+{
+	Polygon3 *splitPoly = NULL;
 #ifdef _Debug
 	if (BspTree::displayDebug)Debug << "Splitting polygons of node " << this << " with plane " << mPlane << endl;
@@ -169,23 +169,27 @@
 		{
 			case Polygon3::COINCIDENT:
+				//Debug << "coincident" << endl;	
 				// same surface normal
 				if (DotProd(mPlane.mNormal, poly->GetSupportingPlane().mNormal) > 0)
 				{
-					coincident->push_back(poly);
+					if (!splitPoly) // store the split polygon if there is none
+						splitPoly = poly;
+					else //  discard it otherwise
+						ProcessPolygon(poly, storePolys);
+
 					break;
-				}
-				//if (BspTree::displayDebug)	Debug << "coincident" << endl;				
+				}							
 				
 			case Polygon3::FRONT_SIDE:	
-				//if (BspTree::displayDebug)Debug << "front" << endl;
+				//Debug << "front" << endl;
 				frontPolys->push_back(poly);
 				break;
 			case Polygon3::BACK_SIDE:
-				//if (BspTree::displayDebug)Debug << "back" << endl;
+				//Debug << "back" << endl;
 				backPolys->push_back(poly);
 				break;
 			case Polygon3::SPLIT:
-				front_piece = new Polygon3(poly->GetParent());
-				back_piece = new Polygon3(poly->GetParent());
+				front_piece = new Polygon3(poly->mParent);
+				back_piece = new Polygon3(poly->mParent);
 
 				//-- split polygon
@@ -196,5 +200,5 @@
 
 #ifdef _DEBUG
-				if (BspTree::displayDebug)Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
+				Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
 #endif
 				ProcessPolygon(poly, storePolys);
@@ -207,6 +211,7 @@
 	}
 	//if (BspTree::displayDebug) Debug << "inside: " << inside << endl;
-	// contains nothing
-	delete polys;
+	
+	delete polys; // contains nothing
+	return splitPoly;
 }
 
@@ -252,5 +257,4 @@
 mTermMaxDepth(0), 
 mRoot(NULL), 
-mIsIncremential(false),
 //mStorePolys(true)
 mStorePolys(false)
@@ -354,5 +358,5 @@
 
 
-void BspTree::InsertViewCell(ViewCell *viewCell)
+/*void BspTree::InsertViewCell(ViewCell *viewCell)
 {	
 	std::stack<BspTraversalData> tStack;
@@ -384,5 +388,5 @@
 				PolygonContainer *frontPolys = new PolygonContainer();
 				PolygonContainer *backPolys = new PolygonContainer();
-				PolygonContainer *coincident = new PolygonContainer();
+				Polygon3 *coincident = NULL;
 
 				int splits = 0;
@@ -400,6 +404,6 @@
 
 				// push the children on the stack
-				tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1));
-				tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1));
+				tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
+				tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, coincident));
 			
 			}
@@ -420,5 +424,5 @@
 		}
 	}
-}
+}*/
 
 void BspTree::InitTree(int maxPolygons, int maxDepth)
@@ -433,5 +437,5 @@
 
 
-int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
+int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent)
 {
 	FaceContainer::const_iterator fi;
@@ -442,7 +446,8 @@
 	{
 		Polygon3 *poly = new Polygon3((*fi), mesh);
+		poly->mParent = parent; // set parent intersectable
 		polys.push_back(poly);
 		//if (displayDebug)Debug << *poly << endl;
-		polysNum ++;
+		++ polysNum;
 	}
 	return polysNum;
@@ -458,5 +463,5 @@
 		{
 			mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
-			AddMesh2Polygons(viewCells[i]->GetMesh(), polys);
+			AddMesh2Polygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
 		}
 	}
@@ -507,45 +512,11 @@
 	InitTree(sTermMaxPolygons, sTermMaxDepth);
 
-    bool savedStorePolys = mStorePolys;
-
-	// tree is completely constructed once before 
-	// view cells are inserted one after another => 
-	// global tree optimization possible
-	if (!mIsIncremential) // todo: not incremential does not work
-	{
-		// copy view cell meshes into one big polygon soup
-		PolygonContainer *polys = new PolygonContainer();
-		Copy2PolygonSoup(viewCells, *polys);
-
-		// polygons are stored only during view cell insertion
-		mStorePolys = false;
-
-		// construct tree from viewcell polygons
-		Construct(polys);
-		//Export("bsp.x3d");
-	}
-	
-	//-- insert all viewcells one after another
-	ViewCellContainer::const_iterator it;
-
-	mStorePolys = savedStorePolys;
-	mStat.polys = 0;
-	mStat.splits = 0;
-	mStat.accumDepth = 0;
-
-	long startTime = GetTime();
-//displayDebug = true;
-	counter = 0;
-	Debug << "**** Starting view cell insertion ****" << endl;
-	for (it = viewCells.begin(); it != viewCells.end(); ++ it)
-	{
-		//if ((counter == 12) || (counter == 14)){
-		//Debug << "** inserting view cell " << counter << " **" << endl;
-		InsertViewCell(*it);
-	//}	counter ++;
-	}
-
-	Debug << "**** Finished view cell insertion ****" << endl;
-	Debug << "insertion time: "<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+ 	// copy view cell meshes into one big polygon soup
+	PolygonContainer *polys = new PolygonContainer();
+	Copy2PolygonSoup(viewCells, *polys);
+
+	// construct tree from viewcell polygons
+	Construct(polys);
+	//Export("bsp.x3d");
 }
 
@@ -574,5 +545,5 @@
 	std::stack<BspTraversalData> tStack;
 	
-	BspTraversalData tData(new BspLeaf(), polys, 0, true, viewCells);
+	BspTraversalData tData(new BspLeaf(), polys, 0, NULL);
 
 	tStack.push(tData);
@@ -585,15 +556,6 @@
 	    tStack.pop();
 
-		//TODO
-		ViewCell *viewCell = NULL;
-
-        /*if (viewCells) // generate new view cell in leaf
-		{
-			viewCell = new ViewCell();
-			viewCells->push_back(viewCell);
-		}*/
-
 		// subdivide leaf node
-		BspNode *root = Subdivide(tStack, tData, viewCell);
+		BspNode *root = Subdivide(tStack, tData, viewCells);
 
 		// empty tree => new root corresponding to unbounded space
@@ -608,44 +570,53 @@
 
 BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, 
-							ViewCell *viewCell)
+							ViewCellContainer *viewCells)
 {
 	//-- terminate traversal  
 	if ((tData.mPolygons->size() <= mTermMaxPolygons) || (tData.mDepth >= mTermMaxDepth))
-		// if there is another view cell associated with this leaf => subdivide further
-		//&& !(viewCell && tData.mIsInside && dynamic_cast<BspLeaf *>(tData.mNode)->GetViewCell()))  
 	{
 #ifdef _DEBUG
-		if (displayDebug)Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
+		Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
 #endif
 
 		EvaluateLeafStats(tData);
 
-	    // add view cell if inside object) 
-		if (viewCell && tData.mCoincident && (tData.mCoincident->size() > 0))) // || (tData.mGeometry->size() > 0) // or if there is still geometry left 
-		{
-			BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
-
+		BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+		//-- new viewcells are generated and added to each leaf
+		if (viewCells)
+		{
+			ViewCell *viewCell = new ViewCell();
+			leaf->SetViewCell(viewCell);
+			viewCells->push_back(viewCell);
+			Debug << "creating new viewcell" << endl;
+		}
+		//-- add viewcell stored in split polygon
+		else if (tData.mSplitPoly && tData.mSplitPoly->mParent)
+		{
 			if (leaf->GetViewCell())
 				Debug << "ERROR: leaf already has view cell " << endl;//leaf->mViewCellIdx << endl;
 
-			//leaf->mViewCellIdx = counter;
-			//Debug << "insert view cell" << endl;
-
-			leaf->SetViewCell(coincident[0]->GetParent());
-		}
-
+			//leaf->mViewCellIdx = counter;Debug << "insert view cell" << endl;
+
+			leaf->SetViewCell(dynamic_cast<ViewCell *>(tData.mSplitPoly->mParent));
+
+			// discard split polygon
+			tData.mNode->GetParent()->ProcessPolygon(tData.mSplitPoly, mStorePolys);
+		}
+	
 		// add or delete remaining polygons
 		tData.mNode->ProcessPolygons(tData.mPolygons, mStorePolys);
-		tData.mNode->ProcessPolygons(tData.coincident, mStorePolys);
-
+				
 		return tData.mNode;
 	}
 
-	tData.mNode->ProcessPolygons(tData.coincident, mStorePolys);
+	// discard the split polygon (not needed if traversal continues)
+	if (tData.mSplitPoly)
+		tData.mNode->GetParent()->ProcessPolygon(tData.mSplitPoly, mStorePolys);
 
 	//-- create new subdivided node
 	PolygonContainer *backPolys = new PolygonContainer();
 	PolygonContainer *frontPolys = new PolygonContainer();
-	PolygonContainer *coincident = new PolygonContainer();
+	Polygon3 *splitPoly = NULL;
 	
 	BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
@@ -653,10 +624,10 @@
 										  frontPolys,
 										  backPolys, 
-										  coincident);
+										  &splitPoly);
 
 	// push the children on the stack
 	// inside information is only propagated with the back leaf
-	tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, coincident));
-	tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1));
+	tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
+	tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, splitPoly));
 
 	return interior;
@@ -667,6 +638,5 @@
 									PolygonContainer *polys, 
 									PolygonContainer *frontPolys,
-									PolygonContainer *coincident, 
-									PolygonContainer *backPolys, bool &inside)
+									PolygonContainer *backPolys, Polygon3 **splitPoly)
 {
 	mStat.nodes += 2;
@@ -682,5 +652,5 @@
 	int splits = 0;
 		
-	inside = interior->SplitPolygons(polys, frontPolys, backPolys, coincident, splits, mStorePolys);
+	*splitPoly = interior->SplitPolygons(polys, frontPolys, backPolys, splits, mStorePolys);
 	
  	mStat.splits += splits;
Index: trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp	(revision 275)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp	(revision 286)
@@ -53,10 +53,9 @@
 	  else
 		  p->GenerateViewCells();
-
-	  Debug << "Number of view cells: " << p->mViewCells.size() << endl;
   }
 
   p->BuildBspTree();
   p->BspTreeStatistics(Debug);
+  Debug << "Number of view cells: " << p->mViewCells.size() << endl;
   p->Export(filename + "-bsptree.x3d", false, false, true);
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp	(revision 268)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp	(revision 286)
@@ -2,22 +2,27 @@
 #include "Mesh.h"
 #include "ViewCellBsp.h" // TODO: erase this
+#include "Intersectable.h"
+
 // tolerance value for side relation
 #define SIDE_TOLERANCE 0.002f // TODO: Test different values
 
-Polygon3::Polygon3(): mMaterial(NULL)
+Polygon3::Polygon3(): mMaterial(NULL), mParent(NULL)
 {}
 
-Polygon3::Polygon3(const VertexContainer &vertices): mVertices(vertices), mMaterial(NULL)
+Polygon3::Polygon3(const VertexContainer &vertices): mVertices(vertices), mMaterial(NULL), mParent(NULL)
 {}
 
-Polygon3::Polygon3(Face *face, Mesh *parent)
+Polygon3::Polygon3(Intersectable *parent): mMaterial(NULL), mParent(parent)
+{
+}
+Polygon3::Polygon3(Face *face, Mesh *parentMesh)
 {	
 	VertexIndexContainer::iterator it = face->mVertexIndices.begin();
 	for (; it != face->mVertexIndices.end();  ++it)
 	{
-		mVertices.push_back(parent->mVertices[*it]);
-		mMaterial = parent->mMaterial;
+		mVertices.push_back(parentMesh->mVertices[*it]);
+		mMaterial = parentMesh->mMaterial;
 		
-		//Debug << parent->mVertices[*it] << endl;
+		//Debug << parentMesh->mVertices[*it] << endl;
 	}
 }
