Index: trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 469)
+++ trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 472)
@@ -289,5 +289,6 @@
 		minRays			500
 		minSize			0.1
-		maxCostRatio		999.0
+		maxCostRatio		0.9
+		missTolerance		4
 		maxRayContribution 	0.2
 	}
@@ -345,11 +346,13 @@
 	Termination {
 		# parameters used for autopartition
-		minRays 100
-		minPolygons -1
-		maxDepth 30
-		minPvs 100
-		minArea 0.01
-		maxRayContribution 0.005
-		#maxAccRayLength 100
+		minRays 		100
+		minPolygons 		-1
+		maxDepth		30
+		minPvs 			100
+		minArea 		0.01
+		maxRayContribution	0.005
+		maxCostRatio		0.9
+		missTolerance		4
+		#maxAccRayLength	100
 		
 		# used for pvs criterium
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h	(revision 469)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h	(revision 472)
@@ -10,5 +10,4 @@
 #include "RayInfo.h"
 #include "ViewCellBsp.h"
-#include "ViewCell.h"
 
 class ViewCell;
@@ -51,5 +50,4 @@
 		/// current depth
 		int mDepth;
-		
 		/// rays piercing this node
 		RayInfoContainer *mRays;
@@ -58,8 +56,8 @@
 		/// geometry of node as induced by planes
 		BspNodeGeometry *mGeometry;
-		
 		/// pvs size
 		int mPvs;
-		
+		/// how often this branch has missed the max-cost ratio
+		int mMaxCostMisses;
 		/** Returns average ray contribution.
 		*/
@@ -77,5 +75,6 @@
 		mPvs(0),
 		mArea(0.0),
-		mGeometry(NULL)
+		mGeometry(NULL),
+		mMaxCostMisses(0)
 		{}
 		
@@ -93,5 +92,6 @@
 		mPvs(pvs),
 		mArea(area),
-		mGeometry(geom)
+		mGeometry(geom),
+		mMaxCostMisses(0)
 		{}
 
@@ -106,9 +106,33 @@
 		mPvs(0),
 		mArea(0),
-		mGeometry(geom)
+		mGeometry(geom),
+		mMaxCostMisses(0)
 		{}
+
+		friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
+		{
+#if 0
+			return a.mPvs * a.mArea < b.mPvs * b.mArea;
+#endif
+#if 1
+			return a.mPvs * (int)a.mRays->size() < b.mPvs * (int)b.mRays->size();
+#endif
+#if 0
+			return a.mPvs < b.mPvs;
+#endif
+#if 0
+			return 
+				a.mPvs / (float)(a.mRays->size() + Limits::Small())
+				>
+				b.mPvs / (float)(b.mRays->size() + Limits::Small());
+#endif
+#if 0
+			return a.mPvs * (int)a.mRays->size() <	b.mPvs * (int)b.mRays->size();
+#endif
+		}
     };
 	
-	typedef std::stack<VspBspTraversalData> VspBspTraversalStack;
+	typedef std::priority_queue<VspBspTraversalData> VspBspTraversalStack;
+	//typedef std::stack<VspBspTraversalData> VspBspTraversalStack;
 
 	/** Default constructor creating an empty tree.
@@ -257,13 +281,15 @@
 
 	/** Selects the best possible splitting plane. 
+		@param plane returns the split plane
 		@param leaf the leaf to be split
 		@param polys the polygon list on which the split decition is based
 		@param rays ray container on which selection may be based
 		@note the polygons can be reordered in the process
-		@returns the split plane
-	*/
-	Plane3 SelectPlane(BspLeaf *leaf, 
-					   VspBspTraversalData &data);
-
+		@returns true if the cost of the split is under maxCostRatio
+
+	*/
+	bool SelectPlane(Plane3 &plane, 
+					 BspLeaf *leaf, 
+					 VspBspTraversalData &data);
 	
 	/** Strategies where the effect of the split plane is tested
@@ -274,5 +300,4 @@
 	float SplitPlaneCost(const Plane3 &candidatePlane, 
 						 const VspBspTraversalData &data);
-
 
 
@@ -291,17 +316,21 @@
 	*/
 
-	BspInterior *SubdivideNode(VspBspTraversalData &tData,
-							   VspBspTraversalData &frontData,
-							   VspBspTraversalData &backData,
-							   PolygonContainer &coincident);
+	BspNode *SubdivideNode(VspBspTraversalData &tData,
+						   VspBspTraversalData &frontData,
+						   VspBspTraversalData &backData,
+						   PolygonContainer &coincident);
 
 	/** Selects the split plane in order to construct a tree with
 		certain characteristics (e.g., balanced tree, least splits, 
 		2.5d aligned)
+		@param bestPlane returns the split plane
 		@param polygons container of polygons
 		@param rays bundle of rays on which the split can be based
-	*/
-	Plane3 SelectPlaneHeuristics(BspLeaf *leaf,
-								 VspBspTraversalData &data);
+
+		@returns true if the overall cost is under maxCostRatio
+	*/
+	bool SelectPlaneHeuristics(Plane3 &bestPlane, 
+							   BspLeaf *leaf, 
+							   VspBspTraversalData &data);
 
 	/** Extracts the meshes of the objects and adds them to polygons. 
@@ -476,5 +505,4 @@
 	float mTermMinAccRayLength;
 
-
 	/// strategy to get the best split plane
 	int mSplitPlaneStrategy;
@@ -487,7 +515,12 @@
 
 	//-- axis aligned split criteria
-	float mAaCtDivCi;
-	float mSplitBorder;
-	float mMaxCostRatio;
+	float mAxisAlignedCtDivCi;
+	/// spezifies the split border of the axis aligned split
+	float mAxisAlignedSplitBorder;
+
+	/// maximal acceptable cost ratio
+	float mTermMaxCostRatio;
+	/// tolerance value indicating how often the max cost ratio can be failed
+	int mTermMissTolerance;
 
 	//-- factors guiding the split plane heuristics
@@ -498,8 +531,10 @@
 	/// if area or accumulated ray lenght should be used for PVS heuristics
 	bool mPvsUseArea;
-
+	/// tolerance for polygon split
 	float mEpsilon;
-
+	/// maximal number of test rays used to evaluate candidate split plane
 	int mMaxTests;
+	/// number of different bsp split plane criteria
+	int mNumCriteria;
 
 private:
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 471)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 472)
@@ -31,6 +31,5 @@
 int VspKdLeaf::sMailId = 0;
 int MergeCandidate::sMaxPvsSize = 150;
-
-
+float MergeCandidate::sOverallCost = Limits::Small;
 #define USE_FIXEDPOINT_T 0
 
@@ -184,6 +183,9 @@
 
 
-VspKdLeaf::VspKdLeaf(VspKdInterior *p,	const int nRays):
-VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
+VspKdLeaf::VspKdLeaf(VspKdInterior *p, 
+					 const int nRays, 
+					 const int maxCostMisses):
+VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL),
+mMaxCostMisses(maxCostMisses)
 {
 	mRays.reserve(nRays);
@@ -193,4 +195,11 @@
 {
 }
+
+
+int VspKdLeaf::GetMaxCostMisses()
+{
+	return mMaxCostMisses;
+}
+
 
 int VspKdLeaf::Type() const
@@ -343,4 +352,6 @@
 	environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
 
+	environment->GetIntValue("VspKdTree.Termination.missTolerance", mTermMissTolerance);
+
 	mTermMinSize = sqr(mTermMinSize);
 
@@ -356,6 +367,6 @@
 	//environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
 
-	environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMinViewCells);
-	environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMaxCostRatio);
+	environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMergeMinViewCells);
+	environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
 	environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
 							 MergeCandidate::sMaxPvsSize);
@@ -615,6 +626,6 @@
 		tStack.pop();
 
-		VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode,
-											data.mBox, backBox,	frontBox);
+		VspKdNode *node = SubdivideNode(dynamic_cast<VspKdLeaf *>(data.mNode),
+										data.mBox, backBox,	frontBox);
 		if (result == NULL)
 			result = node;
@@ -663,11 +674,11 @@
 	else if (splitType == ESplitHeuristic)
 	{
-			costRatio = BestCostRatioHeuristic(leaf,
-											   axis,
-											   position,
-											   raysBack,
-											   raysFront,
-											   pvsBack,
-											   pvsFront);
+		costRatio = BestCostRatioHeuristic(leaf,
+										   axis,
+										   position,
+										   raysBack,
+										   raysFront,
+										   pvsBack,
+										   pvsFront);
 	}
 	else
@@ -1022,7 +1033,7 @@
 
 VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf,
-										const AxisAlignedBox3 &box,
-										AxisAlignedBox3 &backBBox,
-										AxisAlignedBox3 &frontBBox)
+									const AxisAlignedBox3 &box,
+									AxisAlignedBox3 &backBBox,
+									AxisAlignedBox3 &frontBBox)
 {
 	if (TerminationCriteriaMet(leaf, box))
@@ -1050,7 +1061,12 @@
 	//Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" <<	pvsFront << endl;
 
+	int maxCostMisses = leaf->GetMaxCostMisses();
+
 	if (axis == -1)
 	{
-		return leaf;
+		++ maxCostMisses;
+
+		if (maxCostMisses >= mTermMissTolerance)
+			return leaf;
 	}
 
@@ -1068,7 +1084,7 @@
 	frontBBox = box;
 
-	VspKdLeaf *back = new VspKdLeaf(node, raysBack);
+	VspKdLeaf *back = new VspKdLeaf(node, raysBack, maxCostMisses);
 	back->SetPvsSize(pvsBack);
-	VspKdLeaf *front = new VspKdLeaf(node, raysFront);
+	VspKdLeaf *front = new VspKdLeaf(node, raysFront, maxCostMisses);
 	front->SetPvsSize(pvsFront);
 
@@ -1488,6 +1504,6 @@
 		else
 		{
-			tstack.push(((VspKdInterior *)node)->GetFront());
-			tstack.push(((VspKdInterior *)node)->GetBack());
+			tstack.push(dynamic_cast<VspKdInterior *>(node)->GetFront());
+			tstack.push(dynamic_cast<VspKdInterior *>(node)->GetBack());
 		}
 	}
@@ -1499,6 +1515,7 @@
 
 	if (newLeaf->mParent)
+	{
 		newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
-
+	}
 	tstack.push(sroot);
 
@@ -2078,5 +2095,6 @@
 bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2)
 {
-	//-- change pointer to view cells of all leaves associated with the previous view cells
+	//-- change pointer to view cells of all leaves associated 
+	//-- with the previous view cells
 	VspKdViewCell *fVc = l1->GetViewCell();
 	VspKdViewCell *bVc = l2->GetViewCell();
@@ -2156,5 +2174,11 @@
 
 			for (nit = neighbors.begin(); nit != nit_end; ++ nit)
-				mergeQueue.push(MergeCandidate(leaf, *nit));
+			{
+				MergeCandidate mc = MergeCandidate(leaf, *nit);
+				mergeQueue.push(mc);
+
+				MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
+				MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
+			}
 		}
 	}
@@ -2166,6 +2190,7 @@
 	// use priority queue to merge leaves
 	while (!mergeQueue.empty() &&
-		   (vcSize > mMinViewCells))// &&
-		   //(mergeQueue.top().GetMergeCost() < mMaxCostRatio))
+		   (vcSize > mMergeMinViewCells) &&
+		   (mergeQueue.top().GetMergeCost() < 
+		    mMergeMaxCostRatio / MergeCandidate::sOverallCost))
 	{
 		//Debug << mergeQueue.top().GetMergeCost() << " " << mMaxCostRatio << endl;
@@ -2184,4 +2209,6 @@
 			++ merged;
 			-- vcSize;
+			// increase absolute merge cost
+			MergeCandidate::sOverallCost += mc.GetMergeCost();
 		}
 		// merge candidate not valid, because one of the leaves was already
@@ -2230,5 +2257,4 @@
 			if (!viewCell->Mailed())
 			{
-				Debug << "jhere2" << endl;
 				viewCell->mLeaves.clear();
 				viewCell->Mail();
@@ -2252,5 +2278,4 @@
 		return node;
 
-	Debug << "here554444" << endl;
 	VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
@@ -2300,4 +2325,15 @@
 }
 
+float MergeCandidate::GetLeaf1Cost() const
+{
+	VspKdViewCell *vc = mLeaf1->GetViewCell();
+	return vc->GetPvs().GetSize() * vc->GetVolume();
+}
+
+float MergeCandidate::GetLeaf2Cost() const
+{
+	VspKdViewCell *vc = mLeaf2->GetViewCell();
+	return vc->GetPvs().GetSize() * vc->GetVolume();
+}
 
 void MergeCandidate::EvalMergeCost()
@@ -2313,8 +2349,6 @@
 	//-- (added size of left and right view cell times pvs size)
 	//-- to new rendering cost (size of merged view cell times pvs size)
-	const float oldCost =
-		(float)vc1->GetPvs().GetSize() * vc1->GetVolume() +
-		(float)vc2->GetPvs().GetSize() * vc2->GetVolume();
-
+	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
+	
 	const float newCost =
 		(float)vcPvs * (vc1->GetVolume() + vc2->GetVolume());
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 469)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h	(revision 472)
@@ -346,4 +346,5 @@
 	
 	typedef std::stack<BspTraversalData> BspTraversalStack;
+	//typedef std::priority_queue<BspTraversalData> BspTraversalStack;
 
 	/** Default constructor creating an empty tree.
@@ -353,5 +354,6 @@
 	~BspTree();
 
-	
+	/** Returns detailed statistics of the BSP tree.
+	*/
 	const BspTreeStatistics &GetStatistics() const; 
   
@@ -797,5 +799,5 @@
 
 	/// axis aligned split criteria
-	float mAaCtDivCi;
+	float mAxisAlignedCtDivCi;
 	float mSplitBorder;
 	float mMaxCostRatio;
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 469)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 472)
@@ -37,5 +37,6 @@
 VspBspTree::VspBspTree(): 
 mRoot(NULL),
-mPvsUseArea(true)
+mPvsUseArea(true),
+mNumCriteria(0)
 {
 	mRootCell = new BspViewCell();
@@ -50,4 +51,6 @@
 	environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
 	environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
+	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
+	environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
 
 	//-- factors for bsp tree split plane heuristics
@@ -57,6 +60,6 @@
 
 	//-- termination criteria for axis aligned split
-	environment->GetFloatValue("VspBspTree.Termination.AxisAligned.ct_div_ci", mAaCtDivCi);
-	environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxCostRatio", mMaxCostRatio);
+	environment->GetFloatValue("VspBspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
+	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
 	
 	environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays", 
@@ -67,5 +70,5 @@
 	environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
 	environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
-	environment->GetFloatValue("VspBspTree.AxisAligned.splitBorder", mSplitBorder);
+	environment->GetFloatValue("VspBspTree.AxisAligned.splitBorder", mAxisAlignedSplitBorder);
 
 	environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
@@ -82,12 +85,25 @@
 	if (mSplitPlaneStrategy & RANDOM_POLYGON)
 		Debug << "random polygon ";
+
 	if (mSplitPlaneStrategy & AXIS_ALIGNED)
+	{
+		++ mNumCriteria;
 		Debug << "axis aligned ";
+	}
 	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+	{
+		++ mNumCriteria;
 		Debug << "least ray splits ";
+	}
 	if (mSplitPlaneStrategy & BALANCED_RAYS)
+	{
+		++ mNumCriteria;
 		Debug << "balanced rays ";
+	}
 	if (mSplitPlaneStrategy & PVS)
+	{
+		++ mNumCriteria;
 		Debug << "pvs";
+	}
 
 	Debug << endl;
@@ -261,5 +277,5 @@
 void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
 {
-	std::stack<VspBspTraversalData> tStack;
+	VspBspTraversalStack tStack;
 
 	mRoot = new BspLeaf();
@@ -338,6 +354,5 @@
 		EvaluateLeafStats(tData);
 	
-		//-- clean up
-		
+		//-- clean up	
 		DEL_PTR(tData.mPolygons);
 		DEL_PTR(tData.mRays);
@@ -361,7 +376,11 @@
 
 	// create new interior node and two leaf nodes
-	BspInterior *interior = 
-		SubdivideNode(tData, tFrontData, tBackData, coincident);
-
+	BspNode *newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
+
+	// subdivide further
+	if (!newNode->IsLeaf())
+	{
+		BspInterior *interior = dynamic_cast<BspInterior *>(newNode);
+		
 #ifdef _DEBUG	
 //  	if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
@@ -371,22 +390,24 @@
 #endif
 
-	// push the children on the stack
-	tStack.push(tFrontData);
-	tStack.push(tBackData);
+		// push the children on the stack
+		tStack.push(tFrontData);
+		tStack.push(tBackData);
+
+		// delete old leaf node
+		DEL_PTR(tData.mNode);	
+	}
 
 	// cleanup
-	DEL_PTR(tData.mNode);	
-
 	DEL_PTR(tData.mPolygons);
 	DEL_PTR(tData.mRays);
 	DEL_PTR(tData.mGeometry);
 
-	return interior;
-}
-
-BspInterior *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
-									   VspBspTraversalData &frontData,
-									   VspBspTraversalData &backData,
-									   PolygonContainer &coincident)
+	return newNode;
+}
+
+BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
+								   VspBspTraversalData &frontData,
+								   VspBspTraversalData &backData,
+								   PolygonContainer &coincident)
 {
 	mStat.nodes += 2;
@@ -394,6 +415,18 @@
 	BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
 	
+	int maxCostMisses = tData.mMaxCostMisses;
+
 	// select subdivision plane
-	BspInterior *interior = new BspInterior(SelectPlane(leaf, tData)); 
+	Plane3 splitPlane;
+	if (!SelectPlane(splitPlane, leaf, tData))
+	{
+		++ maxCostMisses;
+
+		if (maxCostMisses >= mTermMissTolerance)
+            return leaf;
+	}
+
+	// subdivide further
+	BspInterior *interior = new BspInterior(splitPlane); 
 
 #ifdef _DEBUG
@@ -414,5 +447,10 @@
 								  coincident);
 
-    // compute pvs
+    
+	//-- set left and right traversal data
+	frontData.mMaxCostMisses = maxCostMisses;
+	backData.mMaxCostMisses = maxCostMisses;
+
+	// compute pvs
 	frontData.mPvs = ComputePvsSize(*frontData.mRays);
 	backData.mPvs = ComputePvsSize(*backData.mRays);
@@ -426,8 +464,8 @@
 									   mBox,
 									   mEpsilon);
-	
-		
-		frontData.mArea = frontData.mGeometry->GetArea();
-		backData.mArea = backData.mGeometry->GetArea();
+			
+		// area is normalized with view space area
+		frontData.mArea = frontData.mGeometry->GetArea() / mBox.SurfaceArea();
+		backData.mArea = backData.mGeometry->GetArea() / mBox.SurfaceArea();
 	}
 
@@ -543,6 +581,6 @@
 	float boxArea = box.SurfaceArea();
   
-	float minBand = minBox + mSplitBorder * (maxBox - minBox);
-	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
+	float minBand = minBox + mAxisAlignedSplitBorder * (maxBox - minBox);
+	float maxBand = minBox + (1.0f - mAxisAlignedSplitBorder) * (maxBox - minBox);
 	
 	float minSum = 1e20f;
@@ -584,7 +622,7 @@
 	}
   
-	float oldCost = (float)polys.size();
-	float newCost = mAaCtDivCi + minSum / boxArea;
-	float ratio = newCost / oldCost;
+	const float oldCost = (float)polys.size();
+	const float newCost = mAxisAlignedCtDivCi + minSum / boxArea;
+	const float ratio = newCost / oldCost;
 
 
@@ -615,5 +653,5 @@
 	{
 		float p = 0;
-		float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
+		const float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
 		
 		if (r < costRatio)
@@ -625,5 +663,5 @@
 	}
 	
-	if (costRatio >= mMaxCostRatio)
+	if (costRatio >= mTermMaxCostRatio)
 		return false;
 
@@ -634,12 +672,12 @@
 }
 
-Plane3 VspBspTree::SelectPlane(BspLeaf *leaf, VspBspTraversalData &data)
+bool VspBspTree::SelectPlane(Plane3 &plane, 
+							 BspLeaf *leaf, 
+							 VspBspTraversalData &data)
 {
 	if ((mSplitPlaneStrategy & AXIS_ALIGNED) &&
 		((int)data.mRays->size() > mTermMinRaysForAxisAligned))
-	{
-		Plane3 plane;
-		if (SelectAxisAlignedPlane(plane, *data.mPolygons)) // TODO: should be rays
-			return plane;
+	{	// TODO: candidates should be rays
+		return SelectAxisAlignedPlane(plane, *data.mPolygons); 
 	}
 
@@ -651,5 +689,7 @@
 			const int randIdx = Random((int)data.mPolygons->size());
 			Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
-			return nextPoly->GetSupportingPlane();
+
+			plane = nextPoly->GetSupportingPlane();
+			return true;
 		}
 		else
@@ -665,22 +705,24 @@
 			const Vector3 normal = (*data.mRays)[candidateIdx].mRay->GetDir();
 			
-			return Plane3(normal, pt);
-		}
-
-		return Plane3();
+			plane = Plane3(normal, pt);
+			return true;
+		}
+
+		return false;
 	}
 
 	// use heuristics to find appropriate plane
-	return SelectPlaneHeuristics(leaf, data); 
-}
-
-Plane3 VspBspTree::SelectPlaneHeuristics(BspLeaf *leaf, VspBspTraversalData &data)
+	return SelectPlaneHeuristics(plane, leaf, data); 
+}
+
+bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane, 
+									   BspLeaf *leaf, 
+									   VspBspTraversalData &data)
 {
 	float lowestCost = MAX_FLOAT;
-	Plane3 bestPlane;
+	// intermediate plane
 	Plane3 plane;
 
-	int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-	
+	const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
 	int candidateIdx = limit;
 	
@@ -774,8 +816,13 @@
 	}	
 
+	// cost ratio miss
+	if (lowestCost > mTermMaxCostRatio)
+		return false;
+
 #ifdef _DEBUG
 	Debug << "plane lowest cost: " << lowestCost << endl;
 #endif
-	return bestPlane;
+
+	return true;
 }
 
@@ -802,5 +849,5 @@
 								 const VspBspTraversalData &data)
 {
-	float val = 0;
+	float cost = 0;
 
 	float sumBalancedRays = 0;
@@ -933,16 +980,17 @@
 
 	const float raysSize = (float)data.mRays->size() + Limits::Small;
-
+	
 	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-		val += mLeastRaySplitsFactor * sumRaySplits / raysSize;
+		cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
 
 	if (mSplitPlaneStrategy & BALANCED_RAYS)
-		val += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
-
-	const float denom = pOverall * (float)data.mPvs * 2.0f + Limits::Small;
-
+		cost += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
+	
+	// pvs criterium
 	if (mSplitPlaneStrategy & PVS)
 	{
-		val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom;
+		const float oldCost = pOverall * (float)data.mPvs + Limits::Small;
+
+		cost += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / oldCost;
 
 		// give penalty to unbalanced split
@@ -950,5 +998,5 @@
 		if (((pFront * 0.2 + Limits::Small) > pBack) || 
 			(pFront < (pBack * 0.2 + Limits::Small)))
-			val += 0.5;
+			cost += 0.5;
 	}
 
@@ -958,5 +1006,7 @@
 //  		  << " backpvs: " << backPvs << " pBack: " << pBack << endl << endl;
 #endif
-	return val;
+
+	// normalize by number of criteria
+	return cost / (float)(mNumCriteria + Limits::Small);
 }
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 469)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 472)
@@ -139,5 +139,5 @@
     return;
 
-  numParams = strlen(optParams) + 1;
+  numParams = (int)strlen(optParams) + 1;
   optionalParams = new char[numParams];
   strcpy(optionalParams, optParams);
@@ -390,8 +390,8 @@
   if (options[i].value != NULL) {
     // option was explicitly specified
-    value = strtod(options[i].value, NULL);
+    value = (Real)strtod(options[i].value, NULL);
   } else {
     // option was not read, so use the default
-    value = strtod(options[i].defaultValue, NULL);
+    value = (Real)strtod(options[i].defaultValue, NULL);
   }
   return true;
@@ -1315,5 +1315,5 @@
 		 "100");
 
-  RegisterOption("BspTree.Termination.AxisAligned.maxCostRatio",
+  RegisterOption("BspTree.Termination.maxCostRatio",
 		 optFloat,
 		 "-bsp_term_axis_aligned_max_cost_ratio=",
@@ -1512,4 +1512,13 @@
 		"false");
 
+	RegisterOption("VspKdTree.Termination.maxCostRatio",
+		optFloat,
+		"-vsp_kd_term_max_cost_ratio=",
+		"1.5");
+
+	RegisterOption("VspKdTree.Termination.missTolerance",
+		 optInt,
+		 "-vsp_kd_term_miss_tolerance=",
+		 "4");
 
 	/************************************************************************************/
@@ -1663,4 +1672,13 @@
 			"1.5");
 
+	RegisterOption("VspBspTree.Termination.maxCostRatio",
+		optFloat,
+		"-vsp_bsp_term_max_cost_ratio=",
+		"1.5");
+
+	RegisterOption("VspBspTree.Termination.missTolerance",
+		 optInt,
+		 "-vsp_bsp_term_miss_tolerance=",
+		 "4");
 
 	RegisterOption("VspBspTree.Termination.AxisAligned.ct_div_ci",
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 469)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 472)
@@ -195,6 +195,6 @@
 
 	//-- termination criteria for axis aligned split
-	environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAaCtDivCi);
-	environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", mMaxCostRatio);
+	environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
+	environment->GetFloatValue("BspTree.Termination.maxCostRatio", mMaxCostRatio);
 	environment->GetIntValue("BspTree.Termination.AxisAligned.minPolys", 
 							 mTermMinPolysForAxisAligned);
@@ -406,5 +406,5 @@
 void BspTree::InsertPolygons(PolygonContainer *polys)
 {	
-	std::stack<BspTraversalData> tStack;
+	BspTraversalStack tStack;
 
 	// traverse existing tree or create new tree
@@ -710,5 +710,5 @@
 void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays)
 {
-	std::stack<BspTraversalData> tStack;
+	BspTraversalStack tStack;
 
 	mRoot = new BspLeaf();
@@ -1042,6 +1042,6 @@
 			rbox.SetMin(axis, (*ci).value);
 
-			float sum = objectsLeft * lbox.SurfaceArea() + 
-						objectsRight * rbox.SurfaceArea();
+			const float sum = objectsLeft * lbox.SurfaceArea() + 
+					 		  objectsRight * rbox.SurfaceArea();
       
 			if (sum < minSum) 
@@ -1056,7 +1056,7 @@
 	}
   
-	float oldCost = (float)polys.size();
-	float newCost = mAaCtDivCi + minSum / boxArea;
-	float ratio = newCost / oldCost;
+	const float oldCost = (float)polys.size();
+	const float newCost = mAxisAlignedCtDivCi + minSum / boxArea;
+	const float ratio = newCost / oldCost;
 
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h	(revision 469)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h	(revision 472)
@@ -76,6 +76,15 @@
 	float GetMergeCost() const;
 
+	/** Returns cost of leaf 1.
+	*/
+	float GetLeaf1Cost() const;
+	/** Returns cost of leaf 2.
+	*/
+	float GetLeaf2Cost() const;
+
 	/// maximal pvs size
 	static int sMaxPvsSize;
+	/// overall cost used to normalize cost ratio
+	static float sOverallCost;
 
 protected:
@@ -305,6 +314,7 @@
 		@param p the parent node
 		@param nRays preallocates memory to store this number of rays
-	*/
-	VspKdLeaf(VspKdInterior *p,	const int nRays);
+		@parma maxMisses how many times the max cost ratio was missed on the path to the leaf
+	*/
+	VspKdLeaf(VspKdInterior *p,	const int nRays, const int maxCostMisses = 0);
 	
 	virtual ~VspKdLeaf();
@@ -365,4 +375,10 @@
 	VspKdViewCell *GetViewCell();
 
+	/** Returns number of times the max cost ratio was missed until
+		this leaf.
+	*/
+	int GetMaxCostMisses();
+
+
 	////////////////////////////////////////////
 	
@@ -371,5 +387,5 @@
 	static int sMailId;
 
-
+	
 protected:
 
@@ -381,11 +397,12 @@
 	int mMailbox;
   
+	/// rays intersecting this leaf.
 	RayInfoContainer mRays;
-	
 	/// true if mPvsSize is valid => PVS does not have to be updated
 	bool mValidPvs;
-
 	/// the view cell associated with this leaf
 	VspKdViewCell *mViewCell;
+	/// number of times the max cost ratio was missed on the way to the leaf.
+	int mMaxCostMisses;
 
 private:
@@ -453,5 +470,5 @@
 		//    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
     
-		friend bool operator<(const TraversalData &a, const TraversalData &b) 
+        friend bool operator<(const TraversalData &a, const TraversalData &b) 
 		{
 			// return a.node->queries.size() < b.node->queries.size();
@@ -743,7 +760,4 @@
 	ViewCellsManager *mViewCellsManager;
 
-	/// maximal cost ratio of a merge
-	float mMaxCostRatio;
-
 	/////////////////////////////
 	// Construction parameters
@@ -751,19 +765,25 @@
 	/// max depth of the tree
 	int mTermMaxDepth;
-
 	/// minimal ratio of the volume of the cell and the query volume
 	float mTermMinSize;
-
 	/// minimal pvs per node to still get subdivided
 	int mTermMinPvs;
-
 	/// minimal ray number per node to still get subdivided
 	int mTermMinRays;
-	
-	/// maximal cost ration to subdivide a node
+	/// maximal acceptable cost ratio to continue subdivision
 	float mTermMaxCostRatio;
-	
 	/// maximal contribution per ray to subdivide the node
 	float mTermMaxRayContribution;
+	/// tolerance value indicating how often the max cost ratio can be failed
+	int mTermMissTolerance;
+
+	/// maximal numbers of view cells
+	int mMaxViewCells;
+
+	/// maximal cost ratio of a merge
+	float mMergeMaxCostRatio;
+	
+	/// minimal number of view cells
+	int mMergeMinViewCells;
 
 	/// if only the "driving axis", i.e., the axis with the biggest extent
@@ -771,10 +791,4 @@
 	bool mOnlyDrivingAxis;
 
-	/// maximal numbers of view cells
-	int mMaxViewCells;
-
-	/// minimal number of view cells
-	int mMinViewCells;
-
 	/////////////////////////////
 	VspKdStatistics mStat;	
