Index: /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h	(revision 1027)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h	(revision 1084)
@@ -882,5 +882,5 @@
 						int &objectsFront) const;
 	
-	/** Sorts split candidates for surface area heuristics for axis aligned splits.
+	/** Sorts split candidates for cost heuristics using axis aligned splits.
 		@param polys the input for choosing split candidates
 		@param axis the current split axis
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp	(revision 1077)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp	(revision 1084)
@@ -399,5 +399,5 @@
 	Debug << "maxband: " << mMaxBand << endl;
 	Debug << "pvs count method: " << mPvsCountMethod << endl;
-	
+
 
 	mSplitCandidates = new vector<SortableEntry>;
@@ -805,5 +805,5 @@
 	float pos;
 
-	// insert all queries
+	//-- insert all queries
 	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
 	{
@@ -2559,4 +2559,6 @@
 	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
 	
+	mSplitBorder = 0.1f;
+
 
 	//-- debug output
@@ -2740,5 +2742,5 @@
 
 void OspTree::EvalSplitCandidate(OspTraversalData &tData,
-								 OspSplitCandidate &splitData)
+								 OspSplitCandidate &splitCandidate)
 {
 	float frontProb;
@@ -2748,8 +2750,6 @@
 
 	// compute locally best split plane
-	const bool success = false;
-#if TODO
-	SelectPlane(tData, splitData.mSplitPlane,
-				frontData.mProbability, backData.mProbability);
+	const bool success = 
+		SelectSplitPlane(tData, splitCandidate.mSplitPlane,	frontProb, backProb);
 
 	//TODO
@@ -2758,5 +2758,4 @@
 	splitData.mParentData = tData;
 	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
-#endif
 }
 
@@ -2842,42 +2841,27 @@
 
 
-/*
-float OspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
+float OspTree::EvalLocalCostHeuristics(KdLeaf *node,
 									   const AxisAlignedBox3 &box,
-									   int pvsSize,
 									   const int axis,
-									   float &position)
-{
+									   float &position,
+									   int &objectsBack,
+									   int &objectsFront)
+{
+	
+	SortSplitCandidates(node, axis);
+  
+	// 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 pvsSize = PrepareHeuristics(node->mObjects);;
+	int pvsl = 0, pvsr = pvsSize;
+  
 	const float minBox = box.Min(axis);
 	const float maxBox = box.Max(axis);
 
 	const float sizeBox = maxBox - minBox;
-
-	const float minBand = minBox + mMinBand * sizeBox;
-	const float maxBand = minBox + mMaxBand * sizeBox;
-
-	SortSplitCandidates(rays, axis, minBand, maxBand);
-
-	// prepare the sweep 
-	// (note: returns pvs size, so there would be no need 
-	// to give pvs size as argument)
-	pvsSize = PrepareHeuristics(rays);
-
-	Debug << "here45 pvs: " << pvsSize << endl;
-
-	// go through the lists, count the number of objects left and right
-	// and evaluate the following cost funcion:
-	// C = ct_div_ci  + (ql*rl + qr*rr)/queries
-
-	int pvsl = 0;
-	int pvsr = pvsSize;
-
-	int pvsBack = pvsl;
-	int pvsFront = pvsr;
-
-	float sum = (float)pvsSize * sizeBox;
-	float minSum = 1e20f;
-
-	
+	
+			
 	// if no good split can be found, take mid split
 	position = minBox + 0.5f * sizeBox;
@@ -2886,8 +2870,14 @@
 	float ratio = 99999999.0f;
 	bool splitPlaneFound = false;
-
-	Intersectable::NewMail();
-	KdLeaf::NewMail();
-
+  
+	float minBand = minBox + mSplitBorder * (maxBox - minBox);
+	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
+
+    float minSum = 1e20f;
+
+	int pvsBack = pvsl;
+	int pvsFront = pvsr;
+
+	float sum = (float)pvsSize * sizeBox;
 
 	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
@@ -2946,103 +2936,37 @@
 	return ratio;
 }
-*/
-
-float OspTree::EvalLocalCostHeuristics(BspLeaf *node,
-									   const AxisAlignedBox3 &box,
-									   const int axis,
-									   float &position,
-									   int &objectsBack,
-									   int &objectsFront)
-{
-	
-	/*SortSplitCandidates(node, axis);
-  
-	// 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
-
-	float totalIntersections = 0.0f;
-	
-	vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
-
-	for(ci = splitCandidates->begin(); ci != ci_end; ++ ci)
-	{
-		 if ((*ci).type == SortableEntry::BOX_MIN) 
-		 {
-			 totalIntersections += (*ci).intersectable->IntersectionComplexity();
-		 }
-	}
-	
-	float intersectionsLeft = 0;
-	float intersectionsRight = totalIntersections;
-
-	
-	int objectsLeft = 0, objectsRight = (int)node->mObjects.size();
-  
-	float minBox = box.Min(axis);
-	float maxBox = box.Max(axis);
-	
-	float boxArea = box.SurfaceArea();
-  
-	float minBand = minBox + mSplitBorder*(maxBox - minBox);
-	float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
-
-    float minSum = 1e20f;
-  
-	for(ci = splitCandidates->begin(); ci != ci_end; ++ ci)
-	{
-		EvalPvsIncr(ci, pvsl, pvsr);
-
-		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;
-			
-			if (mSahUseFaces)
-				sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
-			else
-				sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
-      
-			//      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
-			//      cout<<"cost= "<<sum<<endl;
-      
-			if (sum < minSum) 
-			{
-				minSum = sum;
-				position = (*ci).value;
-
-				objectsBack = objectsLeft;
-				objectsFront = objectsRight;
-			}
-		}
-	}
-  
-	float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
-	float newCost = mCt_div_ci + minSum/boxArea;
-	float ratio = newCost/oldCost;
-  
-#if 0
-	cout<<"===================="<<endl;
-	cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
-		<<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
-#endif
-	
-	return ratio;
-	*/
-	return 0;
-}
-
-
-void OspTree::SortSplitCandidates(const RayInfoContainer &rays,
-								  const int axis, 
-								  float minBand, 
-								  float maxBand)
-{
-	// TODO
+
+void OspTree::SortSplitCandidates(KdLeaf *node, const int axis)
+{
+	mSplitCandidates->clear();
+
+	int requestedSize = 2*(int)node->mObjects.size();
+	
+	// creates a sorted split candidates array
+	if (mSplitCandidates->capacity() > 500000 &&
+		requestedSize < (int)(mSplitCandidates->capacity()/10)) 
+	{
+		delete mSplitCandidates;
+		mSplitCandidates = new vector<SortableEntry>;
+	}
+
+	mSplitCandidates->reserve(requestedSize);
+	
+	ObjectContainer::const_iterator mi, mi_end = node->mObjects.end();
+
+	// insert all queries 
+	for(mi = node->mObjects.begin(); mi != mi_end; ++ mi) 
+	{
+		AxisAlignedBox3 box = (*mi)->GetBox();
+
+		mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MIN,
+					box.Min(axis), *mi));
+
+
+		mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MAX,
+					box.Max(axis), *mi));
+	}
+
+	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
 }
 
@@ -3075,30 +2999,19 @@
 
 
-int OspTree::PrepareHeuristics(const RayInfoContainer &rays)
+int OspTree::PrepareHeuristics(const ObjectContainer &objects)
 {	
 	Intersectable::NewMail();
-	KdNode::NewMail();
+	ViewCell::NewMail();
 
 	int pvsSize = 0;
 
-	RayInfoContainer::const_iterator ri, ri_end = rays.end();
-
-	//-- set all kd nodes as belonging to the front pvs
-
-	for (ri = rays.begin(); ri != ri_end; ++ ri)
-	{
-		Intersectable *oObject = (*ri).mRay->mOriginObject;
-
-		if (oObject)
-		{
-			pvsSize += PrepareHeuristics(oObject);		
-		}
-
-		Intersectable *tObject = (*ri).mRay->mTerminationObject;
-
-		if (tObject)
-		{
-			pvsSize += PrepareHeuristics(tObject);	
-		}
+	ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+	//-- set all pvs as belonging to the front pvs
+	for (oit = objects.begin(); oit != oit_end; ++ oit)
+	{
+		Intersectable *obj = *oit;
+
+		pvsSize += PrepareHeuristics(obj);		
 	}
 
@@ -3156,4 +3069,79 @@
 		}
 	}
+}
+
+
+float OspTree::SelectSplitPlane(const VspTraversalData &tData,
+								AxisAlignedPlane &plane,
+								float &pFront,
+								float &pBack)
+{
+	float nPosition[3];
+	float nCostRatio[3];
+	float nProbFront[3];
+	float nProbBack[3];
+
+	// create bounding box of node geometry
+	AxisAlignedBox3 box = tData.mBoundingBox;
+		
+	int sAxis = 0;
+	int bestAxis = -1;
+
+	if (mOnlyDrivingAxis)
+	{
+		sAxis = box.Size().DrivingAxis();
+	}
+
+	//sAxis = 2;
+	for (int axis = 0; axis < 3; ++ axis)
+	{
+		if (!mOnlyDrivingAxis || (axis == sAxis))
+		{
+			//-- place split plane using heuristics
+
+			if (mUseCostHeuristics)
+			{
+				nCostRatio[axis] =
+					EvalLocalCostHeuristics(*tData.mRays,
+											box,
+											tData.mPvs,
+											axis,
+											nPosition[axis]);			
+			}
+			else //-- split plane position is spatial median
+			{
+				nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
+
+				nCostRatio[axis] = EvalLocalSplitCost(tData,
+													  box,
+													  axis,
+													  nPosition[axis],
+													  nProbFront[axis], 
+													  nProbBack[axis]);
+			}
+						
+			if (bestAxis == -1)
+			{
+				bestAxis = axis;
+			}
+			else if (nCostRatio[axis] < nCostRatio[bestAxis])
+			{
+				bestAxis = axis;
+			} 
+		}
+	}
+
+
+	//-- assign values
+	
+	plane.mAxis = bestAxis;
+	// split plane position
+    plane.mPosition = nPosition[bestAxis];
+
+	pFront = nProbFront[bestAxis];
+	pBack = nProbBack[bestAxis];
+
+	//Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
+	return nCostRatio[bestAxis];
 }
 
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h	(revision 1027)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h	(revision 1084)
@@ -559,5 +559,5 @@
 								 const bool useKdSplit);
 
-	/** Sorts split candidates for surface area heuristics for axis aligned splits.
+	/** Sorts split candidates for cost heuristics using axis aligned splits.
 		@param polys the input for choosing split candidates
 		@param axis the current split axis
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1077)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1084)
@@ -871,5 +871,5 @@
 		The split candidates are generated on possible visibility
 		events (i.e., where ray segments intersect the ray boundaries).
-		The sorted candidates are needed to compute the SAH.
+		The sorted candidates are needed to compute the heuristics.
 
 		@param polys the input for choosing split candidates
@@ -882,5 +882,5 @@
 							 float maxBand);
 
-	/** Computes pvs increase with respect to the previous pvs for SAH.
+	/** Computes pvs increase with respect to the previous pvs for heuristics.
 	*/
 	int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes);
@@ -910,5 +910,5 @@
 	void AddContriToPvs(KdLeaf *leaf, int &pvs) const;
 
-	/** Prepares objects for SAH.
+	/** Prepares objects for the heuristics.
 		@returns pvs size of the ray container
 	*/
@@ -1438,23 +1438,13 @@
 					  float &pBack);
 
-	/** Sorts split candidates for surface area heuristics for axis aligned splits.
-		@param polys the input for choosing split candidates
+	/** Sorts split candidates for cost heuristics using axis aligned splits.
+		@param node the current node
 		@param axis the current split axis
-		@param splitCandidates returns sorted list of split candidates
-	*/
-	void SortSplitCandidates(const RayInfoContainer &rays, 
-							 const int axis, 
-							 float minBand, 
-							 float maxBand);
+	*/
+	void SortSplitCandidates(KdLeaf *node, const int axis);
 
 	/** Computes best cost for axis aligned planes.
 	*/
-/*	float EvalLocalCostHeuristics(const RayInfoContainer &rays,
-								  const AxisAlignedBox3 &box,
-								  const int pvsSize,
-								  const int axis,
-								  float &position);
-*/
-	float EvalLocalCostHeuristics(BspLeaf *node,
+	float EvalLocalCostHeuristics(KdLeaf *node,
 		const AxisAlignedBox3 &box,
 		const int axis,
@@ -1504,4 +1494,8 @@
 	inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const;
 
+	float SelectSplitPlane(const VspTraversalData &tData,
+								AxisAlignedPlane &plane,
+								float &pFront,
+								float &pBack);
 	/** Adds ray sample contributions to the PVS.
 		@param sampleContributions the number contributions of the samples
@@ -1543,8 +1537,8 @@
 	void AddContriToPvs(Intersectable *object, int &pvs) const;
 
-	/** Prepares objects for SAH.
-		@returns pvs size of the ray container
-	*/
-	int PrepareHeuristics(const RayInfoContainer &rays);
+	/** Prepares objects for the cost heuristics.
+		@returns pvs size of the node
+	*/
+	int PrepareHeuristics(const ObjectContainer &objects);
 
 	int PrepareHeuristics(Intersectable *object);
@@ -1631,4 +1625,7 @@
 	int mCreatedViewCells;
 
+	float mSplitBorder;
+
+
 private:
 
