Index: /GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj	(revision 1135)
+++ /GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj	(revision 1137)
@@ -206,10 +206,4 @@
 			</File>
 			<File
-				RelativePath="..\src\KdIntersectable.cpp">
-			</File>
-			<File
-				RelativePath="..\src\KdIntersectable.h">
-			</File>
-			<File
 				RelativePath="..\src\KdTree.cpp">
 			</File>
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 1106)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 1137)
@@ -1264,9 +1264,6 @@
 	mLocalSplitCandidates->reserve(requestedSize);
 
-	float pos;
-
-	// float values => don't compare with exact values
 	if (0)
-	{
+	{	// float values => don't compare with exact values
 		minBand += Limits::Small;
 		maxBand -= Limits::Small;
@@ -1277,6 +1274,6 @@
 	{
 		const bool positive = (*ri).mRay->HasPosDir(axis);
-				
-		pos = (*ri).ExtrapOrigin(axis);
+		float pos = (*ri).ExtrapOrigin(axis);
+
 		// clamp to min / max band
 		if (0) ClipValue(pos, minBand, maxBand);
@@ -1286,4 +1283,5 @@
 
 		pos = (*ri).ExtrapTermination(axis);
+
 		// clamp to min / max band
 		if (0) ClipValue(pos, minBand, maxBand);
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp	(revision 1135)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp	(revision 1137)
@@ -934,18 +934,20 @@
 	float pos;
 
+	RayInfoContainer::const_iterator rit, rit_end = rays.end();
+
 	//-- insert all queries
-	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
-	{
-		const bool positive = (*ri).mRay->HasPosDir(axis);
+	for (rit = rays.begin(); rit != rit_end; ++ rit)
+	{
+		const bool positive = (*rit).mRay->HasPosDir(axis);
 				
-		pos = (*ri).ExtrapOrigin(axis);
+		pos = (*rit).ExtrapOrigin(axis);
 		
 		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
-									pos, (*ri).mRay));
-
-		pos = (*ri).ExtrapTermination(axis);
+									pos, (*rit).mRay));
+
+		pos = (*rit).ExtrapTermination(axis);
 
 		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
-									pos, (*ri).mRay));
+									pos, (*rit).mRay));
 	}
 
@@ -1005,4 +1007,5 @@
 
 		//-- the objects belonging to several leaves must be handled seperately
+
 		ObjectContainer::const_iterator oit, oit_end = node->mMultipleObjects.end();
 
@@ -2625,7 +2628,14 @@
 
 
-/*****************************************************************/
-/*                class OspTree implementation                   */
-/*****************************************************************/
+void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
+{
+	// if no precomputation of view cells
+	CastLineSegment(ray.mOrigin, ray.mTermination, viewCells);
+}
+
+
+/*******************************************************************/
+/*                  class OspTree implementation                   */
+/*******************************************************************/
 
 
@@ -3009,8 +3019,10 @@
   
 	const int totalPvs = tData.mNode->mObjects.size();
-
-				
+	
+	int pvsl = 0;
+	int pvsr = totalPvs;
+
 	// if no good split can be found, take mid split
-	int pvsBack = totalPvs / 2;
+	position = minBox + 0.5f * sizeBox;
 	
 	// the relative cost ratio
@@ -3023,26 +3035,22 @@
 	float volFront = volr;
 
+	int pvsBack = 0;
+	int pvsFront = 0;
+	
+
 	float sum = (float)totalVol * sizeBox;
 
-	int currentPvs = 0;
-
 	Intersectable::NewMail();
-
-	//-- traverse through visibility events
+	ViewCell::NewMail();
+
+	//-- traverse through events and find best split plane
 
 	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
 
-	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci, ++ currentPvs)
+	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
 	{
 		Intersectable *object = (*ci).mObject;
 
-		// new object in this node -> add to the pvs
-		if (!object->Mailed())
-		{
-			object->Mail();
-			++ currentPvs;
-		}
-
-		EvalViewCellVolumeIncr(*ci, voll, volr);
+		EvalHeuristicsContribution(*ci, voll, volr, pvsl, pvsr);
 
 		cout << "incr: " << ci->mObject->mViewCellPvs.GetSize() << " obj id " 
@@ -3053,8 +3061,10 @@
 		{
 			//sum = costl * ((*ci).value - minBox) + costr * (maxBox - (*ci).value);
-			sum = voll * currentPvs + volr * (totalPvs - currentPvs);
-
-			cout << "pos=" << currentPvs << "\t volt=(" <<  voll << "," 
-				 << volr << ")" << "\t volt= " << sum << endl;
+			sum = voll * pvsBack + volr * pvsFront;
+
+			cout << "pos: " << (*ci).mPos 
+				 << "\t (pvsl: " << pvsBack << ", pvsr: " << pvsFront << ")"
+				 << "\t (voll: " << voll << ", volr: " << volr << ")"
+				 << "\t sum: " << sum << endl;
 
 			if (sum < minSum)
@@ -3063,12 +3073,17 @@
 
 				minSum = sum;
-				pvsBack = currentPvs;
+
+				pvsBack = pvsl;
+				pvsFront = pvsr;
 				
 				volBack = voll;
 				volFront = volr;
-			}
-		}
-	}
-	
+
+				position = (*ci).mPos;
+			}
+		}
+	}
+	
+
 	//-- compute cost
 
@@ -3081,5 +3096,5 @@
 
 	const float penaltyOld = (float)totalPvs;//EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = (float)totalPvs - pvsBack;//EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = (float)pvsFront;//EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
 	const float penaltyBack = (float)pvsBack;//EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
 	
@@ -3113,5 +3128,5 @@
 	KdLeaf *leaf = tData.mNode;
 
-	int requestedSize = 2 * (int)rays->size();
+	int requestedSize = 2 * (int)rays->size() + 2 * (int)leaf->mObjects.size();
 
 	// creates a sorted split candidates array
@@ -3127,21 +3142,71 @@
 	float pos;
 
-	//-- insert all queries
-	for (RayInfoContainer::const_iterator ri = rays->begin(); ri < rays->end(); ++ ri)
-	{
-		const bool positive = (*ri).mRay->HasPosDir(axis);
-				
-		pos = (*ri).ExtrapOrigin(axis);
-	
-
-		//if (mOspTree->GetLeaf() == leaf)
-
-	/*	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
-									pos, (*ri).mRay));
-
-		pos = (*ri).ExtrapTermination(axis);
-
-		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
-									pos, (*ri).mRay));*/
+	//-- insert ray queries
+	//-- we are intersested only in rays which intersect an object that
+	//-- is part of the kd node because they can induce a change in view cell
+	//-- volume on the left and the right part. 
+	//-- Note that they cannot induce a change in pvs size!!
+
+	RayInfoContainer::const_iterator rit, rit_end = rays->end();
+
+	for (rit = rays->begin(); rit < rit_end; ++ rit)
+	{
+		VssRay *ray = (*rit).mRay;
+
+		const bool positive = ray->HasPosDir(axis);
+		
+		// if hitpoint with object is inside this node
+		if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)
+		{
+			pos = ray->mOrigin[axis];
+	
+			mSplitCandidates->push_back(
+				SortableEntry(SortableEntry::BOX_INTERSECT, 
+							  pos, 
+							  ray->mOriginObject, 
+							  ray)
+							  );
+		}
+
+		if (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf)
+		{
+			pos = ray->mTermination[axis];
+
+			mSplitCandidates->push_back(
+				SortableEntry(SortableEntry::BOX_INTERSECT, 
+							  pos, 
+							  ray->mOriginObject, 
+							  ray)
+							  );
+		}
+	}
+
+
+	//-- insert object queries
+	//-- These queries can induce a change in pvs size.
+	//-- Note that they cannot induce a change in view cell volume, as
+	//-- there is no ray associated with these events!!
+
+	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
+    for (oit = leaf->mObjects.begin(); oit != leaf->mObjects.end(); ++ oit ) 
+	{
+		Intersectable *object = *oit;
+		const AxisAlignedBox3 box = object->GetBox();
+
+		mSplitCandidates->push_back(
+			SortableEntry(SortableEntry::BOX_MIN,
+						  box.Min(axis),
+						  object,
+						  NULL)
+						  );
+   
+    
+		mSplitCandidates->push_back(
+			SortableEntry(SortableEntry::BOX_MAX,
+						  box.Max(axis),
+						  object,
+						  NULL)
+						  );
 	}
 
@@ -3150,22 +3215,4 @@
 
 
-float OspTree::PrepareHeuristics(Intersectable *object)
-{
-	if (mUseEqualWeightForHeuristics)
-	{	
-		// like sah: each object has weight one for heuristics
-		return 1;
-	}
-	else
-	{
-		// the priotity of the object is the sum of view cells 
-		// weighted per their volume
-		float vol = 0;
-		return vol;
-		//return object->mViewCellPvs.GetSize();
-	}
-}
-
-
 const OspTreeStatistics &OspTree::GetStatistics() const
 {
@@ -3174,5 +3221,31 @@
 
 
-float OspTree::PrepareHeuristics(const ObjectContainer &objects)
+float OspTree::PrepareHeuristics(const VssRay &ray)
+{
+	float vol = 0;
+
+	ViewCellContainer viewCells;
+
+	mVspTree->GetViewCells(ray);
+    
+	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+	{
+		ViewCell *vc = (*vit);
+
+		if (!vc->Mailed())
+		{
+			vc->Mail();
+			vc->mCounter = 0;
+			vol += vc->GetVolume();
+		}
+	}
+
+	return vol;
+}
+
+
+float OspTree::PrepareHeuristics(const OspTraversalData &tData)
 {	
 	Intersectable::NewMail();
@@ -3181,11 +3254,19 @@
 	float vol = 0;
 
-	ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-	//-- set all view cell volume as belonging to front volume
-	for (oit = objects.begin(); oit != oit_end; ++ oit)
-	{
-		Intersectable *obj = *oit;
- 		vol += PrepareHeuristics(obj);		
+	KdLeaf *leaf = tData.mNode;
+
+	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
+
+	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
+	{
+		VssRay *ray = (*rit).mRay;
+
+		// if hitpoint with one of the objects is inside this node, we
+		// evaluate the volume of the view cells seen by this ray
+		if ((GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf) ||
+			(GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
+		{
+            vol += PrepareHeuristics(ray);
+		}
 	}
 
@@ -3194,19 +3275,31 @@
 
 
-void OspTree::EvalViewCellVolumeIncr(const SortableEntry &ci,
-									 float &volLeft,
-									 float &volRight) const
+void OspTree::EvalHeuristicsContribution(const SortableEntry &ci,
+										 float &volLeft,
+										 float &volRight,
+										 int &pvsLeft,
+										 int &pvsRight)
 {
 	Intersectable *obj = ci.mObject;
+	VssRay *ray = ci.mRay;
 
 	switch (ci.mType) 
 	{
+		// add reverse pvs to left side of split plane
 		case SortableEntry::BOX_MIN:
-			AddContriToPvs(obj, volLeft);
+			++ pvsLeft;
 			break;
 			
 		case SortableEntry::BOX_MAX:
-			RemoveContriFromPvs(obj, volRight);
+			-- pvsRight;
 			break;
+
+		// compute volume contribution from view cells
+		case SortableEntry::BOX_INTERSECT:
+			EvalVolumeContribution(*ray, volRight, volLeft);
+			break;
+		default:
+			cout << "should not come here" << endl;
+			break;
 	}
 
@@ -3215,4 +3308,33 @@
 
 
+void OspTree::EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight)
+{
+	ViewCellContainer viewCells;
+
+	mVspTree->GetViewCells(ray, viewCells);
+
+	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+	{
+		// view cells comes to left child node
+		ViewCell *viewCell = *vit;
+
+		if (!viewCell->Mailed())
+		{
+			viewCell->Mail();
+			volLeft += viewCell->GetVolume();
+		}
+
+		// remove from right child node
+
+		if (-- viewCell->mCounter == 0)
+		{
+			volRight -= viewCell->GetVolume();
+		}
+	}
+}
+
+
 void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
 {
@@ -3224,24 +3346,4 @@
 {
 	return mBoundingBox;
-}
-
-
-void OspTree::RemoveContriFromPvs(Intersectable *object, float &pvs) const
-{
-	if (mUseEqualWeightForHeuristics)
-		-- pvs;
-	else
-		// the cost of an object is the number of view cells it is part of
-		pvs -= object->mViewCellPvs.GetSize();
-}
-
-
-void OspTree::AddContriToPvs(Intersectable *object, float &pvs) const
-{
-	if (mUseEqualWeightForHeuristics)
-		++ pvs;
-	else
-		// the cost of an object is the number of view cells it is part of
-		pvs += object->mViewCellPvs.GetSize();
 }
 
@@ -3279,5 +3381,5 @@
 
 				nCostRatio[axis] =
-					EvalLocalCostHeuristics(tData.mNode,
+					EvalLocalCostHeuristics(tData,
 									   tData.mBoundingBox,
 									   axis,
@@ -3325,13 +3427,4 @@
 
 
-float OspTree::EvalViewCellPvsIncr(Intersectable *object) const
-{
-	if (mUseEqualWeightForHeuristics)
-		return 1;
-	else
-		return (float)object->mViewCellPvs.GetSize();
-}
-
-
 float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
 									  const OspTraversalData &data) const
@@ -3357,4 +3450,5 @@
 	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
 
+	//TODO §§matt: have to evaluate view cell volume on left and right cell
 	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
 	{
@@ -3362,17 +3456,73 @@
 		const AxisAlignedBox3 box = obj->GetBox();
 		
-		const float pvsIncr = EvalViewCellPvsIncr(obj);
-		totalPvs += pvsIncr;
-		cout << "totalpvs " << totalPvs << " incr " << pvsIncr << endl;
+		++ totalPvs;
+
+		cout << "totalpvs " << totalPvs << endl;
 
 		if (box.Max(candidatePlane.mAxis) > candidatePlane.mPosition)
 		{
-			pvsFront += pvsIncr;
-		}
-		if (box.Min(candidatePlane.mAxis) > candidatePlane.mPosition)
-		{
-			pvsBack += pvsIncr;
-		}
-	}
+			++ pvsFront;
+		}
+		if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition)
+		{
+			++ pvsBack;
+		}
+	}
+
+
+	ViewCell::NewMail();
+	
+	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
+
+	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
+	{
+		VssRay *ray = (*rit).mRay;
+
+		// if hitpoint with one of the objects is inside this node
+		if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)
+		{
+			if (ray->mOrigin[candidatePlane.mAxis] > candidatePlane.mPosition)
+			{
+				// add view cells volume to front	
+				mVspTree->GetViewCells(ray, viewCells);
+
+				ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+				for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+				{
+					ViewCell *vc = *vit;
+
+					if (!vit->Mailed())
+					{
+						vit->Mail();
+						volBack += vc->GetVolume();
+					}
+				}
+			}
+			else
+			{// TODO matt§§
+				// add view cells volume to back
+				if (ray->mOrigin[candidatePlane.mAxis] < candidatePlane.mPosition)
+				{
+					// add view cells volume to front	
+					mVspTree->GetViewCells(ray, viewCells);
+
+					ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+					for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+					{
+						ViewCell *vc = *vit;
+	
+						if (!vit->Mailed())
+						{
+							vit->Mail();
+							volBack += vc->GetVolume();
+						}
+					}
+				}
+			}
+		}
+	}
+
 
 
@@ -3776,5 +3926,7 @@
 mVspTree(vspTree), mOspTree(ospTree)
 {
+	// cross references
 	mVspTree.mOspTree = &ospTree;
+	mOspTree.mVspTree = &vspTree;
 }
 
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1135)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1137)
@@ -749,4 +749,9 @@
 	void AddViewCellReferences(ViewCell *vc) const;
 
+	/** Returns view cells of this ray, either taking precomputed cells
+		or by recomputation.
+	*/
+	void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
+
 
 	/// pointer to the hierarchy of view cells
@@ -900,5 +905,5 @@
 	/** Computes best cost for axis aligned planes.
 	*/
-	float EvalLocalCostHeuristics(const VspTraversalData &data,
+	float EvalLocalCostHeuristics(const VspTraversalData &tData,
 								  const AxisAlignedBox3 &box,
 								  const int axis,
@@ -1365,8 +1370,13 @@
 	struct SortableEntry
 	{
+		/** There is a 3th "event" for rays which intersect a
+			box in the middle. These "events" don't induce a change in
+			pvs size, but may induce a change in view cell volume.
+		*/
 		enum EType 
 		{
-			ERayMin,
-			ERayMax
+			BOX_MIN,
+			BOX_MAX,
+			BOX_INTERSECT
 		};
 
@@ -1374,17 +1384,20 @@
 		//int mPvs;
 		float mPos;
-
+		VssRay *mRay;
+		
 		Intersectable *mObject;
 
 		SortableEntry() {}
 
-		SortableEntry(const int type, 
+		SortableEntry(const int type,
 			//const float pvs, 
 			const float pos,
-			Intersectable *obj):
+			Intersectable *obj,
+			VssRay *ray):
 		mType(type), 
 		//mPvs(pvs), 
 		mPos(pos), 
-		mObject(obj) 
+		mObject(obj),
+		mRay(ray)
 		{}
 
@@ -1417,6 +1430,4 @@
 	float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
 								 const OspTraversalData &data) const;
-
-	float EvalViewCellPvsIncr(Intersectable *object) const;
 
 
@@ -1490,5 +1501,5 @@
 	/** Computes best cost for axis aligned planes.
 	*/
-	float EvalLocalCostHeuristics(const OspTraversalData &data,
+	float EvalLocalCostHeuristics(const OspTraversalData &tData,
 		const AxisAlignedBox3 &box,
 		const int axis,
@@ -1565,25 +1576,27 @@
 	float GetMemUsage() const;
 
-	/** Evaluates the influence on the pvs of the visibility event ve.
+	/** Evaluates the influence on the pvs of the event.
 		@param ve the visibility event
 		@param pvsLeft updates the left pvs
 		@param rightPvs updates the right pvs
 	*/
-	void EvalViewCellVolumeIncr(const SortableEntry &ve,
+	void EvalHeuristicsContribution(const SortableEntry &ci,
 		float &volLeft,
-		float &volRight) const;
-
-	void RemoveContriFromPvs(Intersectable *object, float &pvs) const;
-	void AddContriToPvs(Intersectable *object, float &pvs) const;
+		float &volRight,
+		int &pvsLeft,
+		int &pvsRight);
+
+	/** Evaluate the contributions of view cell volume of the left and the right view cell.
+	*/
+	void EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight);
 
 	/** Prepares objects for the cost heuristics.
 		@returns pvs size of the node
 	*/
-	float PrepareHeuristics(const ObjectContainer &objects);
-
-	/** Evaluates contribution for one object 
-		to heuristics preparation.
-	*/
-	float PrepareHeuristics(Intersectable *object);
+	float PrepareHeuristics(const OspTraversalData &tData);
+
+	/** Prepares heuristics for a particular ray.
+	*/
+	float PrepareHeuristics(const VssRay &ray);
 
 	/** Prepares construction for vsp and osp trees.
@@ -1605,4 +1618,6 @@
 
 protected:
+
+	VspTree *mVspTree;
 
 	/// The view cells manager
