Index: trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 294)
+++ trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 297)
@@ -65,5 +65,21 @@
 
 BspTree {
-	splitPlaneStrategy 14
+	# next polygon         = 1
+	# axis aligned         = 2
+	# least splits         = 4
+	# balanced polygons    = 8
+	# balanced view cells  = 16
+	# largest polygon area = 32
+	# vertical axis        = 64
+	
+	# least splits + balanced polygons
+	#splitPlaneStrategy 12
+	# axis aligned + vertical axis
+	#splitPlaneStrategy 66
+	# axis aligned + balanced view cells
+	#splitPlaneStrategy 18
+	# largest polygon area
+	#splitPlaneStrategy 32
+	splitPlaneStrategy 72
 #       constructionMethod rays
 	constructionMethod viewCells
@@ -72,4 +88,5 @@
 	maxViewCells 999999
 	Termination {
+		maxPolysForAxisAligned 50
 		maxPolygons 0
 		maxDepth 100
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 296)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 297)
@@ -162,4 +162,5 @@
 class BspInterior : public BspNode 
 {
+	friend BspTree;
 public:
 	/** Standard contructor taking split plane as argument.
@@ -275,6 +276,7 @@
 
 	/** Default constructor creating an empty tree.
+		@param viewCell view cell corresponding to unbounded space
 	*/ 
-	BspTree();
+	BspTree(ViewCell *viewCell);
 
 	~BspTree();
@@ -427,4 +429,20 @@
 	inline int GetNextCandidateIdx(const int max) const;
 
+	/** Helper function which extracts a view cell on the front and the back
+		of the split plane.
+		@param backViewCell returns view cell on the back of the split plane
+		@param frontViewCell returns a view cell on the front of the split plane
+		@param coincident container of polygons coincident to the split plane
+		@param splitPlane the split plane which decides about back and front
+		@param extractFront if a front view cell is extracted
+		@param extractBack if a back view cell is extracted
+	*/
+	void ExtractViewCells(ViewCell **backViewCell, 
+						  ViewCell **frontViewCell,
+						  const PolygonContainer &coincident,
+						  const Plane3 splitPlane, 
+						  const bool extractFront, 
+						  const bool extractBack) const;
+	
 	/// Pointer to the root of the tree
 	BspNode *mRoot;
@@ -436,9 +454,13 @@
 
 	/// Strategies for choosing next split plane.
-	enum {NEXT_POLYGON = 0, 
-		  LEAST_SPLITS = 2, 
-		  BALANCED_TREE = 4, 
-		  VERTICAL_AXIS = 8, 
-		  AXIS_ALIGNED = 16};
+	enum {NO_STRATEGY = 0,
+		  NEXT_POLYGON = 1, 
+		  AXIS_ALIGNED = 2,
+		  LEAST_SPLITS = 4, 
+		  BALANCED_POLYS = 8,
+		  BALANCED_VIEW_CELLS = 16,
+		  LARGEST_POLY_AREA = 32,
+		  VERTICAL_AXIS = 64
+		};
 
 	/// box around the whole view domain
@@ -448,6 +470,6 @@
 	bool mStorePolys;
 
-	/// vertical axis of scene
-	Vector3 mVerticalAxis;
+	/// view cell corresponding to unbounded space
+	ViewCell *mViewCell;
 
 public:
@@ -465,9 +487,13 @@
 	/// BSP tree construction method
 	static int sConstructionMethod;
-
+	/// maximal number of polygons where we do axis aligned splits
+	static int sTermMaxPolysForAxisAligned;
+
+	// factors to guid the split plane heuristics
 	static float sLeastSplitsFactor;
-	static float sBalancedTreeFactor;
-	static float sVerticalFactor;
-
+	static float sBalancedPolysFactor;
+	static float sBalancedViewCellsFactor;
+	static float sVerticalSplitsFactor;
+	
 private:
 	/** Evaluates split plane classification with respect to the plane's 
@@ -478,5 +504,5 @@
 		contribution for a minimum number splits in the tree.
 	*/
-	static float sBalancedTreeTable[4];
+	static float sBalancedPolysTable[4];
 };
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 268)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 297)
@@ -1161,4 +1161,9 @@
 		 "5");
   
+  RegisterOption("BspTree.Termination.maxPolysForAxisAligned",
+		 optInt,
+		 "-bsp_term_max_polygons=",
+		 "50");
+
   RegisterOption("BspTree.Termination.maxDepth",
 		 optInt,
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 296)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 297)
@@ -18,7 +18,11 @@
 int BspTree::sSplitPlaneStrategy = NEXT_POLYGON; 
 int BspTree::sConstructionMethod = VIEW_CELLS;
-float BspTree::sLeastSplitsFactor = 1.0f
-float BspTree::sBalancedTreeFactor = 2.0f;
-float BspTree::sVerticalFactor = 50.0f // very important criterium for 2.5d scenes
+int BspTree::sTermMaxPolysForAxisAligned = 50;
+
+//-- factors for bsp tree split plane heuristics
+float BspTree::sLeastSplitsFactor = 1.0f;
+float BspTree::sBalancedPolysFactor = 2.0f;
+float BspTree::sBalancedViewCellsFactor = 2.0f;
+float BspTree::sVerticalSplitsFactor = 1.0f; // very important criterium for 2.5d scenes
 
 
@@ -30,5 +34,5 @@
 	contribution for a minimum number splits in the tree.
 */
-float BspTree::sBalancedTreeTable[] = {-1, 1, 0, 0};
+float BspTree::sBalancedPolysTable[] = {-1, 1, 0, 0};
 
 //int counter = 0;
@@ -187,10 +191,11 @@
 
 				++ splits; // increase number of splits
-				// check if polygon still valid 
+
+				// check if polygons still valid 
 				if (front_piece->mVertices.size() >= 3)
 					frontPolys->push_back(front_piece);
 				else
 					DEL_PTR(front_piece);
-				// check if polygon still valid
+				
 				if (back_piece->mVertices.size() >= 3)
 					backPolys->push_back(back_piece);
@@ -248,7 +253,7 @@
 /****************************************************************/
 
-BspTree::BspTree(): 
+BspTree::BspTree(ViewCell *viewCell): 
 mRoot(NULL), 
-mVerticalAxis(Vector3(0, 0, 1)),
+mViewCell(viewCell),
 //mStorePolys(true)
 mStorePolys(false)
@@ -369,5 +374,5 @@
 	BspNode *firstNode = mRoot ? mRoot : new BspLeaf();
 
-	tStack.push(BspTraversalData(firstNode, polys, 0, NULL));
+	tStack.push(BspTraversalData(firstNode, polys, 0, mViewCell));
 
 	while (!tStack.empty())
@@ -398,7 +403,19 @@
 										mStorePolys);
 				
-				// get view cell associated with the split polygon
-				ViewCell *viewCell = (coincident.size() > 0) ? 
-					dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL;
+				// extract view cells associated with the split polygons
+				ViewCell *frontViewCell = mViewCell;
+				ViewCell *backViewCell = mViewCell;
+	
+				if (!viewCells)
+				{
+					ExtractViewCells(&backViewCell,
+									 &frontViewCell,
+									 coincident, 
+									 interior->mPlane, 
+									 frontPolys->empty(), 
+									 backPolys->empty());
+				}
+
+				// don't need coincident polygons anymore
 				interior->ProcessPolygons(&coincident, mStorePolys);
 
@@ -407,6 +424,6 @@
 
 				// push the children on the stack
-				tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
-				tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, viewCell));
+				tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, frontViewCell));
+				tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, backViewCell));
 			}
 
@@ -533,5 +550,5 @@
 	std::stack<BspTraversalData> tStack;
 	
-	BspTraversalData tData(new BspLeaf(), polys, 0, NULL);
+	BspTraversalData tData(new BspLeaf(), polys, 0, mViewCell);
 
 	tStack.push(tData);
@@ -563,7 +580,7 @@
 	if ((tData.mPolygons->size() <= sTermMaxPolygons) || (tData.mDepth >= sTermMaxDepth))
 	{
-#ifdef _DEBUG
+//#ifdef _DEBUG
 		Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
-#endif
+//#endif
 
 		EvaluateLeafStats(tData);
@@ -580,5 +597,5 @@
 		}
 		//-- add viewcell stored in split polygon
-		else if (tData.mViewCell)
+		else
 		{
 			if (leaf->GetViewCell())
@@ -586,5 +603,5 @@
 
 			//leaf->mViewCellIdx = counter; Debug << "insert view cell " << tData.mViewCell << endl;
-			leaf->SetViewCell(dynamic_cast<ViewCell *>(tData.mViewCell));
+			leaf->SetViewCell(tData.mViewCell);
 		}
 	
@@ -608,13 +625,25 @@
 										  &coincident);
 
-	// view cell associated with the first split polygon
-	ViewCell *viewCell = (coincident.size() > 0) ? 
-					dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL;
+	//-- extract view cells from coincident polygons according to plane normal
+	ViewCell *frontViewCell = mViewCell;
+	ViewCell *backViewCell = mViewCell;
+	
+    if (!viewCells)
+	{
+		ExtractViewCells(&backViewCell,
+						 &frontViewCell,
+						 coincident, 
+						 interior->mPlane, 
+						 frontPolys->empty(), 
+						 backPolys->empty());
+	}
+    
+	// don't need coincident polygons anymore
 	interior->ProcessPolygons(&coincident, mStorePolys);
 
 	// push the children on the stack
 	// split polygon is only needed in the back leaf
-	tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
-	tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, viewCell));
+	tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, frontViewCell));
+	tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, backViewCell));
 
 	// cleanup
@@ -625,4 +654,30 @@
 }
 
+void BspTree::ExtractViewCells(ViewCell **backViewCell, 
+							   ViewCell **frontViewCell,
+							   const PolygonContainer &coincident,
+							   const Plane3 splitPlane, 
+							   const bool extractFront, 
+							   const bool extractBack) const
+{
+	bool foundFront = !extractFront, foundBack = !extractBack;
+
+	PolygonContainer::const_iterator it, it_end = coincident.end();
+
+	for (it = coincident.begin(); !(foundFront && foundBack) && 
+		(it < coincident.end()); ++it)
+	{
+		if (DotProd((*it)->GetSupportingPlane().mNormal, splitPlane.mNormal > 0))
+		{
+			*backViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
+			foundBack = true;
+		}
+		else
+		{
+			*frontViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
+			foundFront = true;
+		}
+	}
+}
 
 BspInterior *BspTree::SubdivideNode(BspLeaf *leaf, 
@@ -671,15 +726,11 @@
 	}
 
-	// simple strategy: just take next polygon
-	if (sSplitPlaneStrategy & NEXT_POLYGON)
-	{
-		return polys.front()->GetSupportingPlane();
-	}
-	
-	if (sSplitPlaneStrategy & AXIS_ALIGNED)
+	if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
+		((int)polys.size() > sTermMaxPolysForAxisAligned))
 	{
 		AxisAlignedBox3 box;
 		box.Initialize();
 	
+		// todo: area subdivision
 		Polygon3::IncludeInBox(polys, box);
         
@@ -690,4 +741,10 @@
 
 		return Plane3(norm, pt);
+	}
+
+	// simplest strategy: just take next polygon
+	if (sSplitPlaneStrategy & NEXT_POLYGON)
+	{
+		return polys.front()->GetSupportingPlane();
 	}
 
@@ -729,5 +786,5 @@
 		}
 	}
-	//Debug << "Plane lowest cost: " << lowestCost << endl;
+	Debug << "Plane lowest cost: " << lowestCost << endl;
 	
 	return polys[bestPlaneIdx]->GetSupportingPlane();
@@ -741,15 +798,20 @@
 float BspTree::EvalSplitPlane(const PolygonContainer &polys, const Plane3 &candidatePlane) const
 {
-	float sumBalanced = 0, sumLeastSplits = 0, verticalAxis = 0;
+	float sumBalancedPolys = 0;
+	float sumBalancedViewCells = 0;
+	float sumLeastSplits = 0;
+	float verticalAxis = 0;
 	
 	if (sSplitPlaneStrategy & VERTICAL_AXIS)
 	{
-		Vector3 thinAxis(0,0,0); thinAxis[mBox.size().ThinAxis()] = 1.0f;
-		// want to minimize this dot product
-		verticalAxis = DotProd(candidatePlane.mNormal, thinAxis);
-		
-        //drivingAxis = (candidatePlane.mNormal.DrivingAxis() == mBox.Size().DrivingAxis()) ? 99.0f : 0.0f;
-	}
-	if ((sSplitPlaneStrategy & BALANCED_TREE) || (sSplitPlaneStrategy & LEAST_SPLITS))
+		Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
+		// want to put a penalty on the dot product between the "tiny" vertical axis
+		// and the split plane axis
+		verticalAxis = fabs(DotProd(candidatePlane.mNormal, tinyAxis)) * (float)polys.size();
+	}
+	//-- strategies where the effect of the split plane on the polygons is tested
+	if ((sSplitPlaneStrategy & BALANCED_POLYS)      || 
+		(sSplitPlaneStrategy & LEAST_SPLITS)        ||
+		(sSplitPlaneStrategy & LARGEST_POLY_AREA))
 	{
 		PolygonContainer::const_iterator it, it_end = polys.end();
@@ -759,14 +821,66 @@
 			int classification = (*it)->ClassifyPlane(candidatePlane);
 
-			if (sSplitPlaneStrategy & BALANCED_TREE)
-				sumBalanced += sBalancedTreeTable[classification];
-	
+			if (sSplitPlaneStrategy & BALANCED_POLYS)
+				sumBalancedPolys += sBalancedPolysTable[classification];
+				
 			if (sSplitPlaneStrategy & LEAST_SPLITS)
 				sumLeastSplits += sLeastSplitsTable[classification];
 		}
 	}
+	
+	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
+	{
+		// store view cells
+		ObjectContainer frontViewCells;
+		ObjectContainer backViewCells;
+
+		PolygonContainer::const_iterator it, it_end = polys.end();
+		
+		for (it = polys.begin(); it != it_end; ++ it)
+		{
+			int classification = (*it)->ClassifyPlane(candidatePlane);
+			Intersectable *viewCell = (*it)->mParent;
+			
+			if (viewCell && (classification == Polygon3::FRONT_SIDE))
+				frontViewCells.push_back(viewCell);
+			else if (viewCell && (classification == Polygon3::BACK_SIDE))
+				backViewCells.push_back(viewCell);
+		}
+
+		// count number of unique view cells
+		sort(frontViewCells.begin(), frontViewCells.end());
+		sort(backViewCells.begin(), backViewCells.end());
+
+		ObjectContainer::const_iterator frontIt, frontIt_end = frontViewCells.end();
+		
+		Intersectable *intersect = NULL;
+		// increase counter for view cells in front of plane
+        for (frontIt = frontViewCells.begin(); frontIt != frontIt_end; ++frontIt)
+		{
+			if (*frontIt != intersect)
+			{
+				intersect = *frontIt;
+				sumBalancedViewCells += 1;
+			}
+		}
+
+		ObjectContainer::const_iterator backIt, backIt_end = backViewCells.end();
+		intersect = NULL;
+		// decrease counter for view cells on back side of plane
+        for (backIt = backViewCells.begin(); backIt != backIt_end; ++backIt)
+		{
+			if (*backIt != intersect)
+			{
+				intersect = *backIt;
+				sumBalancedViewCells -= 1;
+			}
+		}
+	}
 
 	// return linear combination of the sums
-	return sBalancedFactor * fabs(sumBalanced) + sLeastSplitsFactor * sumLeastSplits + sVerticalFactor * dotProd;
+	return sBalancedPolysFactor * fabs(sumBalancedPolys) + 
+		   sBalancedViewCellsFactor * fabs(sumBalancedViewCells) +
+		   sLeastSplitsFactor * sumLeastSplits + 
+		   sVerticalSplitsFactor * verticalAxis;
 }
 
@@ -775,10 +889,30 @@
 	environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
 	environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
+	environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned", 
+							 sTermMaxPolysForAxisAligned);
 	environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
 	environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
 
-	Debug << "BSP max depth: " << sTermMaxDepth << endl;
+    Debug << "BSP max depth: " << sTermMaxDepth << endl;
 	Debug << "BSP max polys: " << sTermMaxPolygons << endl;
 	Debug << "BSP max candidates: " << sMaxCandidates << endl;
+	
+	Debug << "Split plane strategy: ";
+	if (sSplitPlaneStrategy & NEXT_POLYGON)
+		Debug << "next polygon ";
+	if (sSplitPlaneStrategy & AXIS_ALIGNED)
+		Debug << "axis aligned ";
+	if (sSplitPlaneStrategy & LEAST_SPLITS)     
+		Debug << "least splits ";
+	if (sSplitPlaneStrategy & BALANCED_POLYS)
+		Debug << "balanced polygons ";
+	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
+		Debug << "balanced view cells ";
+	if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
+		Debug << "largest polygon area ";
+	if (sSplitPlaneStrategy & VERTICAL_AXIS)
+		Debug << "vertical axis ";
+
+	Debug << endl;
 
 	//-- parse BSP tree construction method
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp	(revision 265)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp	(revision 297)
@@ -9,5 +9,6 @@
 Preprocessor::Preprocessor():
 mKdTree(NULL),
-mBspTree(NULL)
+mBspTree(NULL),
+mRootViewCell(NULL)
 {
 }
@@ -18,4 +19,5 @@
   DEL_PTR(mBspTree);
   DEL_PTR(mKdTree);
+  DEL_PTR(mRootViewCell);
 }
 
@@ -87,5 +89,7 @@
 {
 	DEL_PTR(mBspTree);
-	mBspTree = new BspTree();
+	DEL_PTR(mRootViewCell);
+	mRootViewCell = new ViewCell();
+	mBspTree = new BspTree(mRootViewCell);
 
 	ObjectContainer objects;
Index: trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp	(revision 294)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp	(revision 297)
@@ -47,5 +47,5 @@
 		  p->GenerateViewCells();
 
-	 Debug << "Viewcells loaded / generated. Number of view cells: " << p->mViewCells.size() << endl;
+	 Debug << "Viewcells loaded / generated. Number of view cells: " << (int)p->mViewCells.size() << endl;
   }
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h	(revision 263)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h	(revision 297)
@@ -105,4 +105,7 @@
   /// BSP tree representing the viewcells
   BspTree *mBspTree;
+
+  /// the root view cell of the bsp tree
+  ViewCell *mRootViewCell;
 };
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp	(revision 295)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp	(revision 297)
@@ -124,7 +124,5 @@
 	bool onFrontSide = false;
 	bool onBackSide = false;
-	// threshold for coincident classification
-	const float dot_thres = 0.99f;
-
+	
 	int count = 0;
 	// find possible line-plane intersections
@@ -145,11 +143,5 @@
 		// 3 vertices enough to decide coincident
 		else if (((++ count) >= 3) && !onFrontSide && !onBackSide) 
-		{
-			// Decide if plane and surface normal are same
-			if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres)
-				return COINCIDENT; // plane and polygon are coincident
-			else 
-				return FRONT_SIDE;
-		}
+			return COINCIDENT; 
 	}
 
@@ -163,9 +155,5 @@
 	}
 
-	// Decide if plane and surface normal are same
-	if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres)
-		return COINCIDENT; // plane and polygon are coincident
-	else 
-		return FRONT_SIDE;
+	return COINCIDENT; // plane and polygon are coincident
 }
 
