Index: trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 301)
+++ trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 302)
@@ -76,7 +76,7 @@
 	#splitPlaneStrategy 12
 	#axis aligned + vertical axis
-	#splitPlaneStrategy 66
+	splitPlaneStrategy 66
 	# axis aligned + balanced view cells
-	splitPlaneStrategy 18
+	# splitPlaneStrategy 18
 	# largest polygon area
 	#splitPlaneStrategy 32
@@ -89,5 +89,5 @@
 	maxViewCells 999999
 	Termination {
-		maxPolysForAxisAligned 20
+		maxPolysForAxisAligned 200
 		maxPolygons 0
 		maxDepth 100
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 297)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 302)
@@ -244,5 +244,4 @@
 };
 
-
 /** Implementation of the ViewCell BSP tree. */
 class BspTree 
@@ -331,4 +330,24 @@
 protected:
 	
+	// --------------------------------------------------------------
+	// For sorting objects
+	// --------------------------------------------------------------
+	struct SortableEntry
+	{
+		enum {POLY_MIN, POLY_MAX};
+    
+		int type;
+		float value;
+		Polygon3 *poly;
+		SortableEntry() {}
+		SortableEntry(const int t, const float v, Polygon3 *poly): 
+		type(t), value(v), poly(poly) {}
+		
+		bool operator<(const SortableEntry &b) const 
+		{
+			return value < b.value;
+		}  
+	};
+
 	/** Constructs the tree from the given list of polygons.
 		@param viewCells if not NULL, new view cells are 
@@ -355,7 +374,8 @@
 
 	/** Selects a splitting plane. 
+		@param leaf the leaf to be split
 		@param polys the polygon list on which the split decition is based
 	*/
-	Plane3 SelectPlane(const PolygonContainer &polys) const;
+	Plane3 SelectPlane(BspLeaf *leaf, const PolygonContainer &polys) const;
 
 	/** Filters next view cell down the tree and inserts it into the appropriate leaves
@@ -445,4 +465,29 @@
 						  const bool extractBack) const;
 	
+	/** Computes best cost ratio for the suface area heuristics for axis aligned
+		splits. This heuristics minimizes the cost for ray traversal.
+		@param polys the polygons guiding the ratio computation
+		@param box the bounding box of the leaf
+		@param axis the current split axis
+		@param position returns the split position
+		@param objectsBack the number of objects in the back of the split plane
+		@param objectsFront the number of objects in the front of the split plane
+	*/
+	float BestCostRatio(const PolygonContainer &polys,
+						const AxisAlignedBox3 &box,
+						const int axis,
+						float &position,
+						int &objectsBack,
+						int &objectsFront) const;
+	
+	/** Sorts split candidates for surface area heuristics for axis aligned splits.
+		@param polys the input for choosing split candidates
+		@param axis the current split axis
+		@param splitCandidates returns sorted list of split candidates
+	*/
+	void SortSplitCandidates(const PolygonContainer &polys, 
+							 const int axis, 
+							 vector<SortableEntry> &splitCandidates) const;
+
 	/// Pointer to the root of the tree
 	BspNode *mRoot;
@@ -490,4 +535,8 @@
 	static int sTermMaxPolysForAxisAligned;
 
+	static float sCt_div_ci;
+	static float sSplitBorder;
+	static float sMaxCostRatio;
+
 	// factors to guid the split plane heuristics
 	static float sLeastSplitsFactor;
Index: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h	(revision 295)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h	(revision 302)
@@ -198,5 +198,5 @@
   virtual float SurfaceArea() const;
   virtual float GetVolume() const {
-    return (mMax.x -mMin.x) * (mMax.y -mMin.y) * (mMax.z - mMin.z);
+    return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z);
   }
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 301)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 302)
@@ -19,4 +19,8 @@
 int BspTree::sConstructionMethod = VIEW_CELLS;
 int BspTree::sTermMaxPolysForAxisAligned = 50;
+
+float BspTree::sCt_div_ci = 1.0f;
+float BspTree::sSplitBorder = 1.0f;
+float BspTree::sMaxCostRatio = 0.9;
 
 //-- factors for bsp tree split plane heuristics
@@ -581,7 +585,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);
@@ -691,5 +695,5 @@
 
 	// add the new nodes to the tree + select subdivision plane
-	BspInterior *interior = new BspInterior(SelectPlane(*polys)); 
+	BspInterior *interior = new BspInterior(SelectPlane(leaf, *polys)); 
 
 #ifdef _DEBUG
@@ -719,5 +723,108 @@
 }
 
-Plane3 BspTree::SelectPlane(const PolygonContainer &polys)  const
+void BspTree::SortSplitCandidates(const PolygonContainer &polys, 
+								  const int axis, 
+								  vector<SortableEntry> &splitCandidates) const
+{
+  splitCandidates.clear();
+  
+  int requestedSize = 2 * (int)polys.size();
+  // creates a sorted split candidates array  
+  splitCandidates.reserve(requestedSize);
+  
+  PolygonContainer::const_iterator it, it_end = polys.end();
+
+  AxisAlignedBox3 box;
+
+  // insert all queries 
+  for(it = polys.begin(); it != it_end; ++ it)
+  {
+	  box.Initialize();
+	  box.Include(*(*it));
+	  
+	  splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
+      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
+  }
+  
+  stable_sort(splitCandidates.begin(), splitCandidates.end());
+}
+
+
+float BspTree::BestCostRatio(const PolygonContainer &polys,
+							 const AxisAlignedBox3 &box,
+							 const int axis,
+							 float &position,
+							 int &objectsBack,
+							 int &objectsFront) const
+{
+	vector<SortableEntry> splitCandidates;
+
+	SortSplitCandidates(polys, axis, splitCandidates);
+	
+	// go through the lists, count the number of objects left and right
+	// and evaluate the following cost funcion:
+	// C = ct_div_ci  + (ol + or)/queries
+	
+	int objectsLeft = 0, objectsRight = (int)polys.size();
+	
+	float minBox = box.Min(axis);
+	float maxBox = box.Max(axis);
+	float boxArea = box.SurfaceArea();
+  
+	float minBand = minBox + sSplitBorder * (maxBox - minBox);
+	float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
+	
+	float minSum = 1e20f;
+	vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
+
+	for(ci = splitCandidates.begin(); ci != ci_end; ++ ci) 
+	{
+		switch ((*ci).type) 
+		{
+			case SortableEntry::POLY_MIN:
+				++ objectsLeft;
+				break;
+			case SortableEntry::POLY_MAX:
+			    -- objectsRight;
+				break;
+			default:
+				break;
+		}
+		
+		if ((*ci).value > minBand && (*ci).value < maxBand) 
+		{
+			AxisAlignedBox3 lbox = box;
+			AxisAlignedBox3 rbox = box;
+			lbox.SetMax(axis, (*ci).value);
+			rbox.SetMin(axis, (*ci).value);
+
+			float sum = objectsLeft * lbox.SurfaceArea() + 
+						objectsRight * rbox.SurfaceArea();
+      
+			if (sum < minSum) 
+			{
+				minSum = sum;
+				position = (*ci).value;
+
+				objectsBack = objectsLeft;
+				objectsFront = objectsRight;
+			}
+		}
+	}
+  
+	float oldCost = (float)polys.size();
+	float newCost = sCt_div_ci + minSum / boxArea;
+	float ratio = newCost / oldCost;
+
+
+#if 0
+  Debug << "====================" << endl;
+  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
+      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
+#endif
+  return ratio;
+}
+
+Plane3 BspTree::SelectPlane(BspLeaf *leaf, const PolygonContainer &polys)  const
 {
 	if (polys.size() == 0)
@@ -741,13 +848,9 @@
 		Vector3 position;
 
-		for (int i=0; i < 3; i++) 
+		for (int i = 0; i < 3; ++ i) 
 		{
 			float p = 0;
-			float r = 0;/*BestCostRatio(leaf,
-									box,
-									i,
-									p,
-									objectsBack,
-									objectsFront);*/
+			float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
+			
 			if (r < costRatio)
 			{
@@ -758,12 +861,13 @@
 		}
 		
-		//if (costRatio > mMaxCostRatio) axis = -1;
-		Vector3 norm(0,0,0); norm[axis] = 1.0f;
-		return Plane3(norm, position);
-
+		if (costRatio < sMaxCostRatio)
+		{
+			Vector3 norm(0,0,0); norm[axis] = 1.0f;
+			return Plane3(norm, position);
+		}
 		/*int axis = box.Size().DrivingAxis();
 		Vector3 norm(0,0,0); norm[axis] = 1;
 		Vector3 pt = (box.Min()[axis] + box.Max()[axis]) * 0.5f;*/
-		//Debug << "splitting axis aligned" << endl;
+		
 		//return Plane3(norm, pt);
 	}
@@ -775,16 +879,4 @@
 	}
 
-	/*if (sSplitPlaneStrategy & VERTICAL_AXIS)
-	{
-		const float dot_thres = 0.999;
-		PolygonContainer::const_iterator it, it_end = polys->end();
-		
-		for (it = polys->begin(); it != it_end; ++ it)
-		{
-			if (DotProd((*it)->GetSupportingPlane().mNormal, mVerticalAxis) > dot_thres)
-				return (*it)->GetSupportingPlane();
-		}
-	}*/
-	
 	// use heuristics to find appropriate plane
 	return SelectPlaneHeuristics(polys, sMaxCandidates);
@@ -932,4 +1024,9 @@
 	environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
 	environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
+
+	// need kdtree criteria for axis aligned split
+	environment->GetFloatValue("MeshKdTree.Termination.ct_div_ci", sCt_div_ci);
+	environment->GetFloatValue("MeshKdTree.splitBorder", sSplitBorder);
+	environment->GetFloatValue("MeshKdTree.Termination.maxCostRatio", sMaxCostRatio);
 
     Debug << "BSP max depth: " << sTermMaxDepth << endl;
Index: trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp	(revision 297)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp	(revision 302)
@@ -54,5 +54,6 @@
   p->Export("vc_bsptree.x3d", false, false, true);
 
-  //-- export the complementary view cells, i.e., the view cells not associated with leafs in the tree.
+  //-- export the complementary view cells
+  // i.e., the view cells not associated with leafs in the tree.
   Exporter *exporter = Exporter::GetExporter("viewcells_compl.x3d");
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp	(revision 295)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp	(revision 302)
@@ -657,4 +657,5 @@
 {
   Vector3 ext = mMax - mMin;
+ 
   return 2.0 * (ext.x * ext.y +
 	        ext.x * ext.z +
