Index: /GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj	(revision 752)
+++ /GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj	(revision 810)
@@ -163,4 +163,10 @@
 			</File>
 			<File
+				RelativePath="..\src\FromPointVisibilityTree.cpp">
+			</File>
+			<File
+				RelativePath="..\src\FromPointVisibilityTree.h">
+			</File>
+			<File
 				RelativePath="..\src\GlRenderer.cpp">
 			</File>
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h	(revision 801)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h	(revision 810)
@@ -28,5 +28,5 @@
 struct BspRay;
 
-//#define OCTREE_HACK 0
+
 /**
 	This is a view space partitioning specialised BSPtree.  
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h	(revision 752)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h	(revision 810)
@@ -316,6 +316,5 @@
 	/** sets validy of all viewcells 
 	*/
-  	virtual void SetValidity(
-							 int minPvsSize, 
+  	virtual void SetValidity(int minPvsSize, 
 							 int maxPvsSize) const;
 
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 801)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 810)
@@ -1197,5 +1197,5 @@
 		
 		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
-			pos, (*ri).mRay));
+									pos, (*ri).mRay));
 
 		pos = (*ri).ExtrapTermination(axis);
@@ -1204,5 +1204,5 @@
 
 		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
-			pos, (*ri).mRay));
+									pos, (*ri).mRay));
 	}
 
@@ -1230,5 +1230,6 @@
 	// C = ct_div_ci  + (ql*rl + qr*rr)/queries
 
-	int pvsl = 0, pvsr = pvsSize;
+	int pvsl = 0;
+	int pvsr = pvsSize;
 
 	int pvsBack = pvsl;
@@ -1329,6 +1330,6 @@
 			sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
 
-			//  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
-			// cout<<"cost= "<<sum<<endl;
+			//cout << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
+			//cout<<"cost= "<<sum<<endl;
 
 			if (sum < minSum)
@@ -1343,5 +1344,5 @@
 	}
 	
-	//Debug << "pos: " << position << " sizebox: " << sizeBox << " pvs: " << pvsSize << endl;
+	Debug << "pos: " << position << " sizebox: " << sizeBox << " pvs: " << pvsSize << endl;
 
 	// -- compute cost
@@ -1413,7 +1414,8 @@
 
 	int sAxis = 0;
-	bool maxDepthForDrivingAxis = 0;
-
-	const bool useSpecialAxis = mOnlyDrivingAxis || mUseRandomAxis || 
+	// hack : subdivide along driving axis up to certain depth
+	int maxDepthForDrivingAxis = 0;
+
+    const bool useSpecialAxis = mOnlyDrivingAxis || mUseRandomAxis || 
 		mCirculatingAxis || (tData.mDepth < maxDepthForDrivingAxis);
 
@@ -1529,5 +1531,5 @@
 							 int &splitAxis)
 {
-	// hack
+	// HACK matt: subdivide regularily to certain depth
 	if (data.mDepth < 0)  	
 	{
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.h	(revision 810)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.h	(revision 810)
@@ -0,0 +1,850 @@
+#ifndef _FromPointVisibilityTree_H__
+#define _FromPointVisibilityTree_H__
+
+#include "Mesh.h"
+#include "Containers.h"
+#include "Polygon3.h"
+#include <stack>
+#include "Statistics.h"
+#include "VssRay.h"
+#include "RayInfo.h"
+#include "ViewCellBsp.h"
+
+class ViewCell;
+//class BspViewCell;
+class Plane3;
+class FromPointVisibilityTree;  
+class BspInterior;
+class BspNode;
+class AxisAlignedBox3;
+class Ray;
+class ViewCellsStatistics;
+class ViewCellsManager;
+class MergeCandidate;
+class Beam;
+class ViewCellsTree;
+
+
+struct BspRay;
+
+
+/** A location in space representing from point-visibility.
+*/
+struct VisibilityPoint
+{
+	Vector3 mPosition;
+	/// from point visibility => visible objects, not potentially
+	ObjectPvs mVisibleObjects;
+};
+
+
+/**
+	This is a view space partitioning specialised BSPtree.  
+	There are no polygon splits, but we split the sample rays. 
+	The candidates for the next split plane are evaluated only 
+	by checking the sampled	visibility information. 
+	The polygons are employed merely as candidates for the next split planes.
+*/
+class FromPointVisibilityTree 
+{
+	friend class ViewCellsParseHandlers;
+	friend class VspBspViewCellsManager;
+public:
+	
+	/** Additional data which is passed down the BSP tree during traversal.
+	*/
+	class VspBspTraversalData
+	{  
+	public:
+		/// the current node
+		BspNode *mNode;
+		/// polygonal data for splitting
+		PolygonContainer *mPolygons;
+		/// current depth
+		int mDepth;
+		/// rays piercing this node
+		RayInfoContainer *mRays;
+		/// the probability that this node contains view point
+		float mProbability;
+		/// 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;
+		/// if this node is a kd-node (i.e., boundaries are axis aligned
+		bool mIsKdNode;
+		// current axis
+		int mAxis;
+		// current priority
+		float mPriority;
+
+		
+		/** Returns average ray contribution.
+		*/
+		float GetAvgRayContribution() const
+		{
+			return (float)mPvs / ((float)mRays->size() + Limits::Small);
+		}
+
+
+		VspBspTraversalData():
+		mNode(NULL),
+		mPolygons(NULL),
+		mDepth(0),
+		mRays(NULL),
+		mPvs(0),
+		mProbability(0.0),
+		mGeometry(NULL),
+		mMaxCostMisses(0), 
+		mIsKdNode(false),
+		mPriority(0),
+		mAxis(0)
+		{}
+		
+		VspBspTraversalData(BspNode *node, 
+							PolygonContainer *polys, 
+							const int depth, 
+							RayInfoContainer *rays,
+							const int pvs,
+							const float p,
+							BspNodeGeometry *geom): 
+		mNode(node), 
+		mPolygons(polys), 
+		mDepth(depth), 
+		mRays(rays),
+		mPvs(pvs),
+		mProbability(p),
+		mGeometry(geom),
+		mMaxCostMisses(0),
+		mIsKdNode(false),
+		mPriority(0),
+		mAxis(0)
+		{}
+
+		VspBspTraversalData(PolygonContainer *polys, 
+							const int depth, 
+							RayInfoContainer *rays,
+							BspNodeGeometry *geom): 
+		mNode(NULL), 
+		mPolygons(polys), 
+		mDepth(depth), 
+		mRays(rays),
+		mPvs(0),
+		mProbability(0),
+		mGeometry(geom),
+		mMaxCostMisses(0),
+		mIsKdNode(false),
+		mAxis(0)
+		{}
+
+		/** Returns cost of the traversal data.
+		*/
+		float GetCost() const
+		{
+			//cout << mPriority << endl;
+			return mPriority;
+		}
+
+		// deletes contents and sets them to NULL
+		void Clear()
+		{
+			DEL_PTR(mPolygons);
+			DEL_PTR(mRays);
+			DEL_PTR(mGeometry);
+		}
+
+		friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
+		{
+			return a.GetCost() < b.GetCost();
+		}
+    };
+	
+
+	typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
+	
+	
+	struct VspBspSplitCandidate
+	{  
+		/// the current node
+		Plane3 mSplitPlane;
+		/// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned)
+		int mSplitAxis;
+		/// the number of misses of max cost ratio until this split
+		int mMaxCostMisses;
+
+		// parent data
+		VspBspTraversalData mParentData;
+		// cost of applying this split
+		float mRenderCost;
+
+		VspBspSplitCandidate(): mRenderCost(0) 
+		{};
+
+		VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
+		mSplitPlane(plane), mParentData(tData), mRenderCost(0)
+		{}
+
+		/** Returns cost of the traversal data.
+		*/
+		float GetCost() const
+		{
+#if 1
+			return mRenderCost;
+#endif
+#if 0
+			return (float) (-mDepth); // for kd tree
+#endif
+		}
+
+		friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b)
+		{
+			return a.GetCost() < b.GetCost();
+		}
+    };
+
+	typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue;
+
+	/** Default constructor creating an empty tree.
+	*/ 
+	FromPointVisibilityTree();
+
+	/** Default destructor.
+	*/
+	~FromPointVisibilityTree();
+
+	/** Returns BSP Tree statistics.
+	*/
+	const BspTreeStatistics &GetStatistics() const; 
+  
+
+	/** Constructs the tree from a given set of rays.
+		@param sampleRays the set of sample rays the construction is based on
+	*/
+	void Construct(const VssRayContainer &sampleRays,
+				   AxisAlignedBox3 *forcedBoundingBox);
+
+	
+	/** Constructs the tree from a given set of visibility points
+		@param visibiltiyPointe visibility points the construction is based on
+	*/
+	void Construct(const VisibilityPointsContainer &visibilityPoints, 
+				   AxisAlignedBox3 *forcedBoundingBox);
+
+	/** Returns list of BSP leaves with pvs smaller than
+		a certain threshold.
+		@param onlyUnmailed if only the unmailed leaves should be considered
+		@param maxPvs the maximal pvs (-1 means unlimited)
+	*/
+	void CollectLeaves(vector<BspLeaf *> &leaves, 
+					   const bool onlyUnmailed = false,
+					   const int maxPvs = -1) const;
+
+	/** Returns box which bounds the whole tree.
+	*/
+	AxisAlignedBox3 GetBoundingBox()const;
+
+	/** Returns root of BSP tree.
+	*/
+	BspNode *GetRoot() const;
+
+	/** Collects the leaf view cells of the tree
+		@param viewCells returns the view cells 
+	*/
+	void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
+
+	/** A ray is cast possible intersecting the tree.
+		@param the ray that is cast.
+		@returns the number of intersections with objects stored in the tree.
+	*/
+	int CastRay(Ray &ray);
+
+	/// bsp tree construction types
+	enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
+
+	/** finds neighbouring leaves of this tree node.
+	*/
+	int FindNeighbors(BspNode *n, 
+					  vector<BspLeaf *> &neighbors, 
+					  const bool onlyUnmailed) const;
+
+	/** Constructs geometry associated with the half space intersections 
+		leading to this node.
+	*/
+	void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
+	
+	/** Construct geometry of view cell.
+	*/
+	void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;
+
+	/** Returns random leaf of BSP tree.
+		@param halfspace defines the halfspace from which the leaf is taken.
+	*/
+	BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
+
+	/** Returns random leaf of BSP tree.
+		@param onlyUnmailed if only unmailed leaves should be returned.
+	*/
+	BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
+
+	/** Returns epsilon of this tree.
+	*/
+	float GetEpsilon() const;
+
+	/** Casts line segment into the tree.
+		@param origin the origin of the line segment
+		@param termination the end point of the line segment
+		@returns view cells intersecting the line segment.
+	*/
+    int CastLineSegment(const Vector3 &origin,
+						const Vector3 &termination,
+						ViewCellContainer &viewcells);
+
+		
+	/** Sets pointer to view cells manager.
+	*/
+	void SetViewCellsManager(ViewCellsManager *vcm);
+
+	/** Returns distance from node 1 to node 2.
+	*/
+	int TreeDistance(BspNode *n1, BspNode *n2) const;
+
+	/** Collapses the tree with respect to the view cell partition.
+		@returns number of collapsed nodes
+	*/
+	int CollapseTree();
+
+	/** Returns view cell the current point is located in.
+	*/
+	ViewCell *GetViewCell(const Vector3 &point);
+
+
+	/** Returns true if this view point is in a valid view space,
+		false otherwise.
+	*/
+	bool ViewPointValid(const Vector3 &viewPoint) const;
+
+	/** Returns view cell corresponding to 
+		the invalid view space.
+	*/
+	BspViewCell *GetOutOfBoundsCell();
+
+	/** Writes tree to output stream
+	*/
+	bool Export(ofstream &stream);
+
+	/** Casts beam, i.e. a 5D frustum of rays, into tree.
+		Tests conservative using the bounding box of the nodes.
+		@returns number of view cells it intersected
+	*/
+	int CastBeam(Beam &beam);
+
+	void CollectViewCells(BspNode *root, 
+						  bool onlyValid, 
+						  ViewCellContainer &viewCells,
+						  bool onlyUnmailed = false) const;
+
+	
+	int FindApproximateNeighbors(BspNode *n, 
+							     vector<BspLeaf *> &neighbors,
+								 const bool onlyUnmailed) const;
+
+	/** Checks if tree validity-flags are right 
+		with respect to view cell valitiy.
+		If not, marks subtree as invalid.
+	*/
+	void ValidateTree();
+
+	/** Invalid view cells are added to the unbounded space
+	*/
+	void CollapseViewCells();
+
+	/** Collects rays stored in the leaves.
+	*/
+	void CollectRays(VssRayContainer &rays);
+
+	/** Intersects box with the tree and returns the number of intersected boxes.
+		@returns number of view cells found
+	*/
+	int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;
+
+	// pointer to the hierarchy of view cells
+	ViewCellsTree *mViewCellsTree;
+
+
+protected:
+
+	// --------------------------------------------------------------
+	// For sorting objects
+	// --------------------------------------------------------------
+	struct SortableEntry
+	{
+		enum EType 
+		{
+			ERayMin,
+			ERayMax
+		};
+
+		int type;
+		float value;
+		VssRay *ray;
+  
+		SortableEntry() {}
+		SortableEntry(const int t, const float v, VssRay *r):type(t),
+					  value(v), ray(r) 
+		{
+		}
+		
+		friend bool operator<(const SortableEntry &a, const SortableEntry &b) 
+		{
+			return a.value < b.value;
+		}
+	};
+
+	/** faster evaluation of split plane cost for kd axis aligned cells.
+	*/
+	float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
+								   const AxisAlignedBox3 &box,
+								   const int axis,
+								   const float &position,
+								   float &pFront,
+								   float &pBack) const;
+
+	/** Evaluates candidate for splitting.
+	*/
+	void EvalSplitCandidate(VspBspTraversalData &tData, VspBspSplitCandidate &splitData);
+
+	/** Computes priority of the traversal data and stores it in tData.
+	*/
+	void EvalPriority(VspBspTraversalData &tData) const;
+
+	float EvalRenderCostDecrease(const Plane3 &candidatePlane,
+								 const VspBspTraversalData &data) const;
+
+	void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays);
+
+
+	/** Returns view cell corresponding to 
+		the invalid view space. If it does not exist, it is created.
+	*/
+	BspViewCell *GetOrCreateOutOfBoundsCell();
+
+	/** Collapses the tree with respect to the view cell partition,
+		i.e. leaves having the same view cell are collapsed.
+		@param node the root of the subtree to be collapsed
+		@param collapsed returns the number of collapsed nodes
+		@returns node of type leaf if the node could be collapsed, 
+		this node otherwise
+	*/
+	BspNode *CollapseTree(BspNode *node, int &collapsed);
+
+	/** Helper function revalidating the view cell leaf list after merge.
+	*/
+	void RepairViewCellsLeafLists();
+
+	/** Evaluates tree stats in the BSP tree leafs.
+	*/
+	void EvaluateLeafStats(const VspBspTraversalData &data);
+
+	/** Subdivides node with respect to the traversal data.
+	    @param tStack current traversal stack
+		@param tData traversal data also holding node to be subdivided
+		@returns new root of the subtree
+	*/
+	BspNode *Subdivide(VspBspTraversalQueue &tStack, 
+					   VspBspTraversalData &tData);
+
+	BspNode *Subdivide(VspBspSplitQueue &tQueue,
+					   VspBspSplitCandidate &splitCandidate);
+
+	/** Constructs the tree from the given traversal data.
+		@param polys stores set of polygons on which subdivision may be based
+		@param rays storesset of rays on which subdivision may be based
+	*/
+	void Construct(const PolygonContainer &polys, RayInfoContainer *rays);
+
+	/** 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 true if the cost of the split is under maxCostRatio
+
+	*/
+	bool SelectPlane(Plane3 &plane, 
+					 BspLeaf *leaf, 
+					 VspBspTraversalData &data,
+					 VspBspTraversalData &frontData,
+					 VspBspTraversalData &backData,
+					 int &splitAxis);
+	
+	/** Strategies where the effect of the split plane is tested
+	    on all input rays.
+
+		@returns the cost of the candidate split plane
+	*/
+	float EvalSplitPlaneCost(const Plane3 &candidatePlane, 
+							 const VspBspTraversalData &data,
+							 BspNodeGeometry &geomFront,
+							 BspNodeGeometry &geomBack,
+							 float &pFront,
+							 float &pBack) const;
+
+	/** Subdivides leaf.
+		@param leaf the leaf to be subdivided
+		
+		@param polys the polygons to be split
+		@param frontPolys returns the polygons in front of the split plane
+		@param backPolys returns the polygons in the back of the split plane
+		
+		@param rays the polygons to be filtered
+		@param frontRays returns the polygons in front of the split plane
+		@param backRays returns the polygons in the back of the split plane
+
+		@returns the root of the subdivision
+	*/
+
+	BspInterior *SubdivideNode(const Plane3 &splitPlane,
+							   VspBspTraversalData &tData,
+							   VspBspTraversalData &frontData,
+                               VspBspTraversalData &backData,
+							   PolygonContainer &coincident);
+
+	/** Extracts the meshes of the objects and adds them to polygons. 
+		Adds object aabb to the aabb of the tree.
+		@param maxPolys the maximal number of objects to be stored as polygons
+		@returns the number of polygons
+	*/
+	int AddToPolygonSoup(const ObjectContainer &objects, 
+						 PolygonContainer &polys, 
+						 int maxObjects = 0);
+
+	/** Extracts the meshes of the view cells and and adds them to polygons.
+		Adds view cell aabb to the aabb of the tree.
+		@param maxPolys the maximal number of objects to be stored as polygons
+		@returns the number of polygons
+	*/
+	int AddToPolygonSoup(const ViewCellContainer &viewCells, 
+						 PolygonContainer &polys, 
+						 int maxObjects = 0);
+
+	/** Extract polygons of this mesh and add to polygon container.
+		@param mesh the mesh that drives the polygon construction
+		@param parent the parent intersectable this polygon is constructed from
+		@returns number of polygons
+	*/
+	int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
+
+	/** Selects an axis aligned for the next split.
+		@returns cost for this split
+	*/
+	float SelectAxisAlignedPlane(Plane3 &plane, 
+								 const VspBspTraversalData &tData,
+								 int &axis,
+								 BspNodeGeometry **frontGeom,
+								 BspNodeGeometry **backGeom,
+								 float &pFront,
+								 float &pBack,
+								 const bool useKdSplit);
+
+	/** 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 RayInfoContainer &rays, 
+							 const int axis, 
+							 float minBand, 
+							 float maxBand);
+
+	/** Computes best cost for axis aligned planes.
+	*/
+	float BestCostRatioHeuristics(const RayInfoContainer &rays,
+								  const AxisAlignedBox3 &box,
+								  const int pvsSize,
+								  const int axis,
+								  float &position);
+
+	/** Selects an axis aligned split plane.
+		@Returns true if split is valied
+	*/
+	bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
+
+	/** Subdivides the rays into front and back rays according to the split plane.
+		
+		@param plane the split plane
+		@param rays contains the rays to be split. The rays are 
+			   distributed into front and back rays.
+		@param frontRays returns rays on the front side of the plane
+		@param backRays returns rays on the back side of the plane
+		
+		@returns the number of splits
+	*/
+	int SplitRays(const Plane3 &plane,
+				  RayInfoContainer &rays, 
+			      RayInfoContainer &frontRays, 
+				  RayInfoContainer &backRays) const;
+
+
+	/** Extracts the split planes representing the space bounded by node n.
+	*/
+	void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
+
+	/** Adds the object to the pvs of the front and back leaf with a given classification.
+
+		@param obj the object to be added
+		@param cf the ray classification regarding the split plane
+		@param frontPvs returns the PVS of the front partition
+		@param backPvs returns the PVS of the back partition
+	
+	*/
+	void AddObjToPvs(Intersectable *obj, 
+					 const int cf, 
+					 float &frontPvs, 
+					 float &backPvs, 
+					 float &totalPvs) const;
+	
+	/** Computes PVS size induced by the rays.
+	*/
+	int ComputePvsSize(const RayInfoContainer &rays) const;
+
+	/** Returns true if tree can be terminated.
+	*/
+	inline bool LocalTerminationCriteriaMet(const VspBspTraversalData &data) const;
+
+	/** Returns true if global tree can be terminated.
+	*/
+	inline bool GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const;
+
+	/** Computes accumulated ray lenght of this rays.
+	*/
+	float AccumulatedRayLength(const RayInfoContainer &rays) const;
+
+	/** Splits polygons with respect to the split plane.
+
+		@param plane the split plane
+		@param polys the polygons to be split. the polygons are consumed and
+			   distributed to the containers frontPolys, backPolys, coincident.
+		@param frontPolys returns the polygons in the front of the split plane
+		@param backPolys returns the polygons in the back of the split plane
+		@param coincident returns the polygons coincident to the split plane
+
+		@returns the number of splits	
+	*/
+	int SplitPolygons(const Plane3 &plane,
+					  PolygonContainer &polys, 
+					  PolygonContainer &frontPolys, 
+					  PolygonContainer &backPolys, 
+					  PolygonContainer &coincident) const;
+
+	/** Adds ray sample contributions to the PVS.
+		@param sampleContributions the number contributions of the samples
+		@param contributingSampels the number of contributing rays
+		
+	*/
+	void AddToPvs(BspLeaf *leaf,
+				  const RayInfoContainer &rays, 
+				  float &sampleContributions,
+				  int &contributingSamples);
+
+
+
+
+
+	
+	/** Take 3 ray endpoints, where two are minimum and one a maximum
+		point or the other way round.
+	*/
+	Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;
+
+	/** Take plane normal as plane normal and the midpoint of the ray.
+		PROBLEM: does not resemble any point where visibility is 
+		likely to change
+	*/
+	Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
+
+	/** Fit the plane between the two lines so that the plane 
+		has equal shortest distance to both lines.
+	*/
+	Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
+  
+	/** Collects candidates for merging.
+		@param leaves the leaves to be merged
+		@returns number of leaves in queue
+	*/
+	int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
+
+	/** Collects candidates for the merge in the merge queue.
+		@returns number of leaves in queue
+	*/
+	int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
+	
+	/** Preprocesses polygons and throws out all polygons which are coincident to
+		the view space box faces (they can be problematic).
+	*/
+	void PreprocessPolygons(PolygonContainer &polys);
+	
+	/** Propagates valid flag up the tree.
+	*/
+	void PropagateUpValidity(BspNode *node);
+
+	/** Writes the node to disk
+		@note: should be implemented as visitor
+	*/
+	void ExportNode(BspNode *node, ofstream &stream);
+
+	/** Returns estimated memory usage of tree.
+	*/
+	//float GetMemUsage(const VspBspTraversalQueue &tstack) const;
+	float GetMemUsage() const;
+
+
+
+	/// Pointer to the root of the tree
+	BspNode *mRoot;
+		
+	BspTreeStatistics mBspStats;
+
+	/// Strategies for choosing next split plane.
+	enum {NO_STRATEGY = 0,
+		  RANDOM_POLYGON = 1, 
+		  AXIS_ALIGNED = 2,
+		  LEAST_RAY_SPLITS = 256,
+		  BALANCED_RAYS = 512,
+		  PVS = 1024
+		};
+
+	/// box around the whole view domain
+	AxisAlignedBox3 mBox;
+
+	bool mUseCostHeuristics;
+
+	/// minimal number of rays before subdivision termination
+	int mTermMinRays;
+	/// maximal possible depth
+	int mTermMaxDepth;
+	/// mininum probability
+	float mTermMinProbability;
+	/// mininum PVS
+	int mTermMinPvs;
+	/// maximal contribution per ray
+	float mTermMaxRayContribution;
+	/// minimal accumulated ray length
+	float mTermMinAccRayLength;
+
+	//HACK
+	int mTermMinPolygons;
+
+	float mTermMinGlobalCostRatio;
+	int mTermGlobalCostMissTolerance;
+
+	int mGlobalCostMisses;
+
+	bool mUseSplitCostQueue;
+	//-- termination criteria for axis aligned split
+
+	/// minimal number of rays for axis aligned split
+	int mTermMinRaysForAxisAligned;
+	// max ray contribution
+	float mTermMaxRayContriForAxisAligned;
+
+	/// strategy to get the best split plane
+	int mSplitPlaneStrategy;
+	/// number of candidates evaluated for the next split plane
+	int mMaxPolyCandidates;
+	/// number of candidates for split planes evaluated using the rays
+	int mMaxRayCandidates;
+	/// balancing factor for PVS criterium
+	float mCtDivCi;
+
+	//-- axis aligned split criteria
+	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
+	float mLeastRaySplitsFactor;
+	float mBalancedRaysFactor;
+	float mPvsFactor;
+
+	/// if area or volume should be used for PVS heuristics
+	bool mUseAreaForPvs;
+	/// tolerance for polygon split
+	float mEpsilon;
+	/// maximal number of test rays used to evaluate candidate split plane
+	int mMaxTests;
+	/// normalizes different bsp split plane criteria
+	float mCostNormalizer;
+	/// maximal number of view cells
+	int mMaxViewCells;
+	
+	ofstream  mSubdivisionStats;
+
+	// if rays should be stored in leaves
+	bool mStoreRays;
+	
+	/// if only driving axis should be used for split
+	bool mOnlyDrivingAxis;
+
+	ViewCellsManager *mViewCellsManager;
+
+	vector<SortableEntry> *mSplitCandidates;
+
+	
+	float mRenderCostWeight;
+	/// View cell corresponding to the space outside the valid view space
+	BspViewCell *mOutOfBoundsCell;
+
+	/// maximal tree memory
+	float mMaxMemory;
+	/// the tree is out of memory
+	bool mOutOfMemory;
+	
+	float mTotalCost;
+	int mTotalPvsSize;
+
+	float mMinBand;
+	float mMaxBand;
+
+	//int mSplits;
+	/// subdivision stats output file
+	ofstream mSubdivsionStats;
+	/// if random split axis should be used
+	bool mUseRandomAxis;
+	/// use polygon split whenever there are polys left
+	bool mUsePolygonSplitIfAvailable;
+	/// current time stamp (used for keeping split history)
+	int mTimeStamp;
+	/// number of currenly generated view cells
+	int mCreatedViewCells;
+	/// if vsp bsp tree should simulate octree
+	bool mCirculatingAxis;
+
+	/// if we should use breath first priority for the splits
+	int mNodePriorityQueueType;
+
+	bool mEmptyViewCellsMergeAllowed;
+
+	// priority queue strategy
+	enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED};
+private:
+
+	/// Generates unique ids for PVS criterium
+	static void GenerateUniqueIdsForPvs();
+
+	//-- unique ids for PVS criterium
+	static int sFrontId; 
+	static int sBackId;
+	static int sFrontAndBackId;
+};
+
+
+
+
+#endif
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.h	(revision 801)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.h	(revision 810)
@@ -95,4 +95,5 @@
 	friend class BspViewCellsManager;
 	friend class VspBspTree;
+	friend class FromPointVisibilityTree;
 	friend class BspTree;
 
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.cpp	(revision 810)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.cpp	(revision 810)
@@ -0,0 +1,3929 @@
+#include <stack>
+#include <time.h>
+#include <iomanip>
+
+#include "Plane3.h"
+#include "FromPointVisibilityTree.h"
+#include "Mesh.h"
+#include "common.h"
+#include "ViewCell.h"
+#include "Environment.h"
+#include "Polygon3.h"
+#include "Ray.h"
+#include "AxisAlignedBox3.h"
+#include "Exporter.h"
+#include "Plane3.h"
+#include "ViewCellBsp.h"
+#include "ViewCellsManager.h"
+#include "Beam.h"
+
+#define USE_FIXEDPOINT_T 0
+
+
+//-- static members
+
+
+int FromPointVisibilityTree::sFrontId = 0;
+int FromPointVisibilityTree::sBackId = 0;
+int FromPointVisibilityTree::sFrontAndBackId = 0;
+
+typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
+
+
+// pvs penalty can be different from pvs size
+inline float EvalPvsPenalty(const int pvs, 
+							const int lower,
+							const int upper)
+{
+	// clamp to minmax values
+	if (pvs < lower)
+		return (float)lower;
+	if (pvs > upper)
+		return (float)upper;
+
+	return (float)pvs;
+}
+
+
+
+
+/******************************************************************************/
+/*                       class FromPointVisibilityTree implementation                      */
+/******************************************************************************/
+
+
+FromPointVisibilityTree::FromPointVisibilityTree():
+mRoot(NULL),
+mUseAreaForPvs(false),
+mCostNormalizer(Limits::Small),
+mViewCellsManager(NULL),
+mOutOfBoundsCell(NULL),
+mStoreRays(false),
+mRenderCostWeight(0.5),
+mUseRandomAxis(false),
+mTimeStamp(1)
+{
+	bool randomize = false;
+	environment->GetBoolValue("FromPointVisibilityTree.Construction.randomize", randomize);
+	if (randomize)
+		Randomize(); // initialise random generator for heuristics
+
+	//-- termination criteria for autopartition
+	environment->GetIntValue("FromPointVisibilityTree.Termination.maxDepth", mTermMaxDepth);
+	environment->GetIntValue("FromPointVisibilityTree.Termination.minPvs", mTermMinPvs);
+	environment->GetIntValue("FromPointVisibilityTree.Termination.minRays", mTermMinRays);
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.minProbability", mTermMinProbability);
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.maxRayContribution", mTermMaxRayContribution);
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.minAccRayLenght", mTermMinAccRayLength);
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.maxCostRatio", mTermMaxCostRatio);
+	environment->GetIntValue("FromPointVisibilityTree.Termination.missTolerance", mTermMissTolerance);
+	environment->GetIntValue("FromPointVisibilityTree.Termination.maxViewCells", mMaxViewCells);
+
+	//-- max cost ratio for early tree termination
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.maxCostRatio", mTermMaxCostRatio);
+
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
+	environment->GetIntValue("FromPointVisibilityTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
+
+	// HACK//mTermMinPolygons = 25;
+
+	//-- factors for bsp tree split plane heuristics
+	environment->GetFloatValue("FromPointVisibilityTree.Factor.pvs", mPvsFactor);
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.ct_div_ci", mCtDivCi);
+
+
+	//-- partition criteria
+	environment->GetIntValue("FromPointVisibilityTree.maxPolyCandidates", mMaxPolyCandidates);
+	environment->GetIntValue("FromPointVisibilityTree.maxRayCandidates", mMaxRayCandidates);
+	environment->GetIntValue("FromPointVisibilityTree.splitPlaneStrategy", mSplitPlaneStrategy);
+
+	environment->GetFloatValue("FromPointVisibilityTree.Construction.epsilon", mEpsilon);
+	environment->GetIntValue("FromPointVisibilityTree.maxTests", mMaxTests);
+
+	// if only the driving axis is used for axis aligned split
+	environment->GetBoolValue("FromPointVisibilityTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+	
+	//-- termination criteria for axis aligned split
+	environment->GetFloatValue("FromPointVisibilityTree.Termination.AxisAligned.maxRayContribution", 
+								mTermMaxRayContriForAxisAligned);
+	environment->GetIntValue("FromPointVisibilityTree.Termination.AxisAligned.minRays",
+							 mTermMinRaysForAxisAligned);
+
+	//environment->GetFloatValue("FromPointVisibilityTree.maxTotalMemory", mMaxTotalMemory);
+	environment->GetFloatValue("FromPointVisibilityTree.maxStaticMemory", mMaxMemory);
+
+	environment->GetFloatValue("FromPointVisibilityTree.Construction.renderCostWeight", mRenderCostWeight);
+	environment->GetBoolValue("FromPointVisibilityTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable);
+
+	environment->GetBoolValue("FromPointVisibilityTree.useCostHeuristics", mUseCostHeuristics);
+	environment->GetBoolValue("FromPointVisibilityTree.useSplitCostQueue", mUseSplitCostQueue);
+	environment->GetBoolValue("FromPointVisibilityTree.simulateOctree", mCirculatingAxis);
+	environment->GetBoolValue("FromPointVisibilityTree.useRandomAxis", mUseRandomAxis);
+	environment->GetIntValue("FromPointVisibilityTree.nodePriorityQueueType", mNodePriorityQueueType);
+
+	environment->GetBoolValue("ViewCells.PostProcess.emptyViewCellsMerge", mEmptyViewCellsMergeAllowed);
+	
+	char subdivisionStatsLog[100];
+	environment->GetStringValue("FromPointVisibilityTree.subdivisionStats", subdivisionStatsLog);
+	mSubdivisionStats.open(subdivisionStatsLog);
+
+	environment->GetFloatValue("FromPointVisibilityTree.Construction.minBand", mMinBand);
+	environment->GetFloatValue("FromPointVisibilityTree.Construction.maxBand", mMaxBand);
+
+	//-- debug output
+
+	Debug << "******* VSP BSP options ******** " << endl;
+    Debug << "max depth: " << mTermMaxDepth << endl;
+	Debug << "min PVS: " << mTermMinPvs << endl;
+	Debug << "min probabiliy: " << mTermMinProbability << endl;
+	Debug << "min rays: " << mTermMinRays << endl;
+	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
+	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
+	Debug << "miss tolerance: " << mTermMissTolerance << endl;
+	Debug << "max view cells: " << mMaxViewCells << endl;
+	Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
+	//Debug << "max plane candidates: " << mMaxRayCandidates << endl;
+	Debug << "randomize: " << randomize << endl;
+
+	Debug << "using area for pvs: " << mUseAreaForPvs << endl;
+	Debug << "render cost weight: " << mRenderCostWeight << endl;
+	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
+	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
+	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
+	Debug << "max memory: " << mMaxMemory << endl;
+	Debug << "use poly split if available: " << mUsePolygonSplitIfAvailable << endl;
+	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
+	Debug << "use split cost queue: " << mUseSplitCostQueue << endl;
+	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
+	Debug << "use random axis: " << mUseRandomAxis << endl;
+	Debug << "priority queue type: " << mNodePriorityQueueType << endl;
+	Debug << "empty view cells merge: " << mEmptyViewCellsMergeAllowed << endl;
+	Debug << "octree: " << mCirculatingAxis << endl;
+	Debug << "minband: " << mMinBand << endl;
+	Debug << "maxband: " << mMaxBand << endl;
+	
+
+	Debug << "Split plane strategy: ";
+
+	if (mSplitPlaneStrategy & RANDOM_POLYGON)
+	{
+		Debug << "random polygon ";
+	}
+	if (mSplitPlaneStrategy & AXIS_ALIGNED)
+	{
+		Debug << "axis aligned ";
+	}
+	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+	{
+		mCostNormalizer += mLeastRaySplitsFactor;
+		Debug << "least ray splits ";
+	}
+	if (mSplitPlaneStrategy & BALANCED_RAYS)
+	{
+		mCostNormalizer += mBalancedRaysFactor;
+		Debug << "balanced rays ";
+	}
+	if (mSplitPlaneStrategy & PVS)
+	{
+		mCostNormalizer += mPvsFactor;
+		Debug << "pvs";
+	}
+
+
+	mSplitCandidates = new vector<SortableEntry>;
+
+	Debug << endl;
+}
+
+
+BspViewCell *FromPointVisibilityTree::GetOutOfBoundsCell()
+{
+	return mOutOfBoundsCell;
+}
+
+
+BspViewCell *FromPointVisibilityTree::GetOrCreateOutOfBoundsCell()
+{
+	if (!mOutOfBoundsCell)
+	{
+		mOutOfBoundsCell = new BspViewCell();
+		mOutOfBoundsCell->SetId(-1);
+		mOutOfBoundsCell->SetValid(false);
+	}
+
+	return mOutOfBoundsCell;
+}
+
+
+const BspTreeStatistics &FromPointVisibilityTree::GetStatistics() const
+{
+	return mBspStats;
+}
+
+
+FromPointVisibilityTree::~FromPointVisibilityTree()
+{
+	DEL_PTR(mRoot);
+	DEL_PTR(mSplitCandidates);
+}
+
+
+int FromPointVisibilityTree::AddMeshToPolygons(Mesh *mesh,
+								  PolygonContainer &polys,
+								  MeshInstance *parent)
+{
+	FaceContainer::const_iterator fi;
+
+	// copy the face data to polygons
+	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
+	{
+		Polygon3 *poly = new Polygon3((*fi), mesh);
+
+		if (poly->Valid(mEpsilon))
+		{
+			poly->mParent = parent; // set parent intersectable
+			polys.push_back(poly);
+		}
+		else
+			DEL_PTR(poly);
+	}
+	return (int)mesh->mFaces.size();
+}
+
+
+int FromPointVisibilityTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
+							  PolygonContainer &polys,
+							  int maxObjects)
+{
+	int limit = (maxObjects > 0) ?
+		Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
+
+	int polysSize = 0;
+
+	for (int i = 0; i < limit; ++ i)
+	{
+		if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
+		{
+			mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
+			polysSize +=
+				AddMeshToPolygons(viewCells[i]->GetMesh(),
+								  polys,
+								  viewCells[i]);
+		}
+	}
+
+	return polysSize;
+}
+
+
+int FromPointVisibilityTree::AddToPolygonSoup(const ObjectContainer &objects,
+								 PolygonContainer &polys,
+								 int maxObjects)
+{
+	int limit = (maxObjects > 0) ?
+		Min((int)objects.size(), maxObjects) : (int)objects.size();
+
+	for (int i = 0; i < limit; ++i)
+	{
+		Intersectable *object = objects[i];//*it;
+		Mesh *mesh = NULL;
+
+		switch (object->Type()) // extract the meshes
+		{
+		case Intersectable::MESH_INSTANCE:
+			mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
+			break;
+		case Intersectable::VIEW_CELL:
+			mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
+			break;
+			// TODO: handle transformed mesh instances
+		default:
+			Debug << "intersectable type not supported" << endl;
+			break;
+		}
+
+        if (mesh) // copy the mesh data to polygons
+		{
+			mBox.Include(object->GetBox()); // add to BSP tree aabb
+			AddMeshToPolygons(mesh, polys, NULL);
+		}
+	}
+
+	return (int)polys.size();
+}
+
+
+void FromPointVisibilityTree::Construct(const VssRayContainer &sampleRays,
+						   AxisAlignedBox3 *forcedBoundingBox)
+{
+	mBspStats.nodes = 1;
+	mBox.Initialize(); 	// initialise BSP tree bounding box
+
+	if (forcedBoundingBox)
+		mBox = *forcedBoundingBox;
+	
+	PolygonContainer polys;
+	RayInfoContainer *rays = new RayInfoContainer();
+
+	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+	long startTime = GetTime();
+
+	cout << "Extracting polygons from rays ... ";
+
+	Intersectable::NewMail();
+
+	int numObj = 0;
+
+	//-- extract polygons intersected by the rays
+	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+	{
+		VssRay *ray = *rit;
+
+		if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
+			ray->mTerminationObject && 
+			!ray->mTerminationObject->Mailed())
+		{
+			ray->mTerminationObject->Mail();
+			MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
+			AddMeshToPolygons(obj->GetMesh(), polys, obj);
+			++ numObj;
+
+			//-- compute bounding box
+			if (!forcedBoundingBox)
+				mBox.Include(ray->mTermination);
+		}
+
+		if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
+			ray->mOriginObject && 
+			!ray->mOriginObject->Mailed())
+		{
+			ray->mOriginObject->Mail();
+			MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
+			AddMeshToPolygons(obj->GetMesh(), polys, obj);
+			++ numObj;
+
+			//-- compute bounding box
+			if (!forcedBoundingBox)
+				mBox.Include(ray->mOrigin);
+		}
+	}
+	
+	Debug << "maximal pvs (i.e., pvs still considered as valid) : " 
+		  << mViewCellsManager->GetMaxPvsSize() << endl;
+
+	//-- store rays
+	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+	{
+		VssRay *ray = *rit;
+
+		float minT, maxT;
+
+		static Ray hray;
+		hray.Init(*ray);
+
+		// TODO: not very efficient to implictly cast between rays types
+		if (mBox.GetRaySegment(hray, minT, maxT))
+		{
+			float len = ray->Length();
+
+			if (!len)
+				len = Limits::Small;
+
+			rays->push_back(RayInfo(ray, minT / len, maxT / len));
+		}
+	}
+
+	// normalize
+	if (mUseAreaForPvs)
+		mTermMinProbability *= mBox.SurfaceArea(); 
+	else 
+		mTermMinProbability *= mBox.GetVolume();
+
+	// throw out unnecessary polygons
+	PreprocessPolygons(polys);
+
+	mBspStats.polys = (int)polys.size();
+	mGlobalCostMisses = 0;
+
+	cout << "finished" << endl;
+
+	Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
+		  << (int)sampleRays.size() << " rays in "
+		  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
+
+	// use split cost priority queue
+	if (mUseSplitCostQueue)
+	{
+		ConstructWithSplitQueue(polys, rays);
+	}
+	else
+	{
+		Construct(polys, rays);
+	}
+
+	// clean up polygons
+	CLEAR_CONTAINER(polys);
+}
+
+
+// TODO: return memory usage in MB
+float FromPointVisibilityTree::GetMemUsage() const
+{
+	return (float)
+		 (sizeof(FromPointVisibilityTree) + 
+		  mBspStats.Leaves() * sizeof(BspLeaf) + 
+		  mCreatedViewCells * sizeof(BspViewCell) +
+		  mBspStats.pvs * sizeof(ObjectPvsData) +
+		  mBspStats.Interior() * sizeof(BspInterior) +
+		  mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
+}
+
+
+
+void FromPointVisibilityTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
+{
+	VspBspTraversalQueue tQueue;
+
+	mRoot = new BspLeaf();
+
+	// constrruct root node geometry
+	BspNodeGeometry *geom = new BspNodeGeometry();
+	ConstructGeometry(mRoot, *geom);
+
+	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
+
+	VspBspTraversalData tData(mRoot,
+							  new PolygonContainer(polys),
+							  0,
+							  rays,
+                              ComputePvsSize(*rays),
+							  prop,
+							  geom);
+
+	EvalPriority(tData);
+
+
+	// first node is kd node, i.e. an axis aligned box
+	if (1)
+        tData.mIsKdNode = true;
+	else
+		tData.mIsKdNode = false;
+
+	tQueue.push(tData);
+
+
+	mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
+	mTotalPvsSize = tData.mPvs;
+	
+	mSubdivisionStats 
+			<< "#ViewCells\n1" <<  endl
+			<< "#RenderCostDecrease\n0" << endl 
+			<< "#TotalRenderCost\n" << mTotalCost << endl
+			<< "#AvgRenderCost\n" << mTotalPvsSize << endl;
+
+	Debug << "total cost: " << mTotalCost << endl;
+	
+	
+	mBspStats.Start();
+	cout << "Constructing vsp bsp tree ... \n";
+
+	long startTime = GetTime();	
+	int nLeaves = 500;
+	int nViewCells = 500;
+
+	// used for intermediate time measurements and progress
+	long interTime = GetTime();	
+
+	mOutOfMemory = false;
+
+	mCreatedViewCells = 0;
+	
+	while (!tQueue.empty())
+	{
+		tData = tQueue.top();
+	    tQueue.pop();		
+
+		if (0 && !mOutOfMemory)
+		{
+			float mem = GetMemUsage();
+
+			if (mem > mMaxMemory)
+			{
+				mOutOfMemory = true;
+				Debug << "memory limit reached: " << mem << endl;
+			}
+		}
+
+		// subdivide leaf node
+		BspNode *r = Subdivide(tQueue, tData);
+
+		if (r == mRoot)
+			Debug << "VSP BSP tree construction time spent at root: "
+				  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
+		if (mBspStats.Leaves() >= nLeaves)
+		{
+			nLeaves += 500;
+
+			cout << "leaves=" << mBspStats.Leaves() << endl;
+			Debug << "needed "
+				  << TimeDiff(interTime, GetTime())*1e-3 
+				  << " secs to create 500 view cells" << endl;
+			interTime = GetTime();
+		}
+
+		if (mCreatedViewCells >= nViewCells)
+		{
+			nViewCells += 500;
+
+			cout << "generated " << mCreatedViewCells << " viewcells" << endl;
+		}
+	}
+
+	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
+	cout << "finished\n";
+
+	mBspStats.Stop();
+}
+
+
+
+void FromPointVisibilityTree::ConstructWithSplitQueue(const PolygonContainer &polys, 
+											  RayInfoContainer *rays)
+{
+	VspBspSplitQueue tQueue;
+
+	mRoot = new BspLeaf();
+
+	// constrruct root node geometry
+	BspNodeGeometry *geom = new BspNodeGeometry();
+	ConstructGeometry(mRoot, *geom);
+
+	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
+
+	VspBspTraversalData tData(mRoot,
+							  new PolygonContainer(polys),
+							  0,
+							  rays,
+                              ComputePvsSize(*rays),
+							  prop,
+							  geom);
+
+
+	// compute first split candidate
+	VspBspSplitCandidate splitCandidate;
+	EvalSplitCandidate(tData, splitCandidate);
+
+	tQueue.push(splitCandidate);
+
+	mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
+	mTotalPvsSize = tData.mPvs;
+	
+	mSubdivisionStats 
+			<< "#ViewCells\n1\n" <<  endl
+			<< "#RenderCostDecrease\n0\n" << endl 
+			<< "#SplitCandidateCost\n0\n" << endl
+			<< "#TotalRenderCost\n" << mTotalCost << endl
+			<< "#AvgRenderCost\n" << mTotalPvsSize << endl;
+
+	Debug << "total cost: " << mTotalCost << endl;
+	
+	
+	mBspStats.Start();
+	cout << "Constructing vsp bsp tree ... \n";
+
+	long startTime = GetTime();	
+	int nLeaves = 500;
+	int nViewCells = 500;
+
+	// used for intermediate time measurements and progress
+	long interTime = GetTime();	
+
+	mOutOfMemory = false;
+
+	mCreatedViewCells = 0;
+	
+	while (!tQueue.empty())
+	{
+		splitCandidate = tQueue.top();
+	    tQueue.pop();		
+
+		// cost ratio of cost decrease / totalCost
+		float costRatio = splitCandidate.GetCost() / mTotalCost;
+
+		//Debug << "cost ratio: " << costRatio << endl;
+
+		if (costRatio < mTermMinGlobalCostRatio)
+			++ mGlobalCostMisses;
+		
+		if (0 && !mOutOfMemory)
+		{
+			float mem = GetMemUsage();
+
+			if (mem > mMaxMemory)
+			{
+				mOutOfMemory = true;
+				Debug << "memory limit reached: " << mem << endl;
+			}
+		}
+
+		// subdivide leaf node
+		BspNode *r = Subdivide(tQueue, splitCandidate);
+
+		if (r == mRoot)
+			Debug << "VSP BSP tree construction time spent at root: "
+				  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
+		if (mBspStats.Leaves() >= nLeaves)
+		{
+			nLeaves += 500;
+
+			cout << "leaves=" << mBspStats.Leaves() << endl;
+			Debug << "needed "
+				  << TimeDiff(interTime, GetTime())*1e-3 
+				  << " secs to create 500 view cells" << endl;
+			interTime = GetTime();
+		}
+
+		if (mCreatedViewCells == nViewCells)
+		{
+			nViewCells += 500;
+
+			cout << "generated " << mCreatedViewCells << " viewcells" << endl;
+		}
+	}
+
+	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
+	cout << "finished\n";
+
+	mBspStats.Stop();
+}
+
+
+bool FromPointVisibilityTree::LocalTerminationCriteriaMet(const VspBspTraversalData &data) const
+{
+	return
+		(((int)data.mRays->size() <= mTermMinRays) ||
+		 (data.mPvs <= mTermMinPvs)   ||
+		 (data.mProbability <= mTermMinProbability) ||
+		 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
+		 (data.mDepth >= mTermMaxDepth));
+}
+
+
+bool FromPointVisibilityTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
+{
+	return
+		(mOutOfMemory 
+		|| (mBspStats.Leaves() >= mMaxViewCells) 
+		|| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
+		 );
+}
+
+
+
+BspNode *FromPointVisibilityTree::Subdivide(VspBspTraversalQueue &tQueue,
+							   VspBspTraversalData &tData)
+{
+	BspNode *newNode = tData.mNode;
+
+	if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
+	{
+		PolygonContainer coincident;
+
+		VspBspTraversalData tFrontData;
+		VspBspTraversalData tBackData;
+
+		// create new interior node and two leaf nodes
+		// or return leaf as it is (if maxCostRatio missed)
+		int splitAxis;
+		bool splitFurther = true;
+		int maxCostMisses = tData.mMaxCostMisses;
+		
+		Plane3 splitPlane;
+		BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+		
+		// choose next split plane
+		if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis))
+		{
+			++ maxCostMisses;
+
+			if (maxCostMisses > mTermMissTolerance)
+			{
+				// terminate branch because of max cost
+				++ mBspStats.maxCostNodes;
+				splitFurther = false;
+			}
+		}
+	
+		// if this a valid split => subdivide this node further
+		if (splitFurther) //-- continue subdivision
+		{
+			newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
+
+			if (splitAxis < 3)
+				++ mBspStats.splits[splitAxis];
+			else
+				++ mBspStats.polySplits;
+
+			tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
+			tFrontData.mAxis = tBackData.mAxis = splitAxis;
+
+			// how often was max cost ratio missed in this branch?
+			tFrontData.mMaxCostMisses = maxCostMisses;
+			tBackData.mMaxCostMisses = maxCostMisses;
+
+			EvalPriority(tFrontData);
+			EvalPriority(tBackData);
+
+			// evaluate subdivision stats
+			if (1)
+			{
+				float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+				float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+				float cData = (float)tData.mPvs * tData.mProbability;;
+
+                float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
+
+				mTotalCost += costDecr;
+				mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
+
+				mSubdivisionStats 
+						<< "#ViewCells\n" << mBspStats.Leaves() << endl
+						<< "#RenderCostDecrease\n" << -costDecr << endl 
+						<< "#TotalRenderCost\n" << mTotalCost << endl
+						<< "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+			}
+
+			// push the children on the stack
+			tQueue.push(tFrontData);
+			tQueue.push(tBackData);
+
+			// delete old leaf node
+			DEL_PTR(tData.mNode);
+		}
+	}
+
+	//-- terminate traversal and create new view cell
+	if (newNode->IsLeaf())
+	{
+		BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+		BspViewCell *viewCell = new BspViewCell();
+		
+		leaf->SetViewCell(viewCell);
+	
+		//-- update pvs
+		int conSamp = 0;
+		float sampCon = 0.0f;
+		AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
+
+		// update single pvs parameter
+		viewCell->mPvsSize = viewCell->GetPvs().GetSize(); 
+		viewCell->mPvsSizeValid = true;
+
+
+		mBspStats.contributingSamples += conSamp;
+		mBspStats.sampleContributions +=(int) sampCon;
+
+		//-- store additional info
+		if (mStoreRays)
+		{
+			RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
+			for (it = tData.mRays->begin(); it != it_end; ++ it)
+			{
+				(*it).mRay->Ref();			
+				leaf->mVssRays.push_back((*it).mRay);
+			}
+		}
+
+		// should I check here?
+		if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
+		{
+			viewCell->SetValid(false);
+			leaf->SetTreeValid(false);
+			PropagateUpValidity(leaf);
+
+			++ mBspStats.invalidLeaves;
+		}
+		
+        viewCell->mLeaf = leaf;
+
+		if (mUseAreaForPvs)
+			viewCell->SetArea(tData.mProbability);
+		else
+			viewCell->SetVolume(tData.mProbability);
+
+		leaf->mProbability = tData.mProbability;
+
+		EvaluateLeafStats(tData);		
+	}
+
+	//-- cleanup
+	tData.Clear();
+
+	return newNode;
+}
+
+// subdivide using a split plane queue
+BspNode *FromPointVisibilityTree::Subdivide(VspBspSplitQueue &tQueue,
+							   VspBspSplitCandidate &splitCandidate)
+{
+	VspBspTraversalData &tData = splitCandidate.mParentData;
+
+	BspNode *newNode = tData.mNode;
+
+	if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
+	{	
+		PolygonContainer coincident;
+
+		VspBspTraversalData tFrontData;
+		VspBspTraversalData tBackData;
+
+		//-- continue subdivision
+		
+		// create new interior node and two leaf node
+		const Plane3 splitPlane = splitCandidate.mSplitPlane;
+				
+		newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
+	
+		const int splitAxis = splitCandidate.mSplitAxis;
+		const int maxCostMisses = splitCandidate.mMaxCostMisses;
+
+		if (splitAxis < 3)
+			++ mBspStats.splits[splitAxis];
+		else
+			++ mBspStats.polySplits;
+
+		tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
+		tFrontData.mAxis = tBackData.mAxis = splitAxis;
+
+		// how often was max cost ratio missed in this branch?
+		tFrontData.mMaxCostMisses = maxCostMisses;
+		tBackData.mMaxCostMisses = maxCostMisses;
+			
+		
+		if (1)
+		{
+			float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+			float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+			float cData = (float)tData.mPvs * tData.mProbability;
+
+			
+			float costDecr = 
+				(cFront + cBack - cData) / mBox.GetVolume();
+
+			mTotalCost += costDecr;
+			mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
+
+			mSubdivisionStats 
+					<< "#ViewCells\n" << mBspStats.Leaves() << endl
+					<< "#RenderCostDecrease\n" << -costDecr << endl
+					<< "#SplitCandidateCost\n" << splitCandidate.GetCost() << endl
+					<< "#TotalRenderCost\n" << mTotalCost << endl
+					<< "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+		}
+
+	
+		//-- push the new split candidates on the stack
+		VspBspSplitCandidate frontCandidate;
+		VspBspSplitCandidate backCandidate;
+
+		EvalSplitCandidate(tFrontData, frontCandidate);
+		EvalSplitCandidate(tBackData, backCandidate);
+	
+		tQueue.push(frontCandidate);
+		tQueue.push(backCandidate);
+	
+		// delete old leaf node
+		DEL_PTR(tData.mNode);
+	}
+
+
+	//-- terminate traversal and create new view cell
+	if (newNode->IsLeaf())
+	{
+		BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+		BspViewCell *viewCell = new BspViewCell();
+
+        leaf->SetViewCell(viewCell);
+		
+		//-- update pvs
+		int conSamp = 0;
+		float sampCon = 0.0f;
+		AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
+
+		viewCell->mPvsSize = viewCell->GetPvs().GetSize();
+		viewCell->mPvsSizeValid = true;
+
+		mBspStats.contributingSamples += conSamp;
+		mBspStats.sampleContributions +=(int) sampCon;
+
+		//-- store additional info
+		if (mStoreRays)
+		{
+			RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
+			for (it = tData.mRays->begin(); it != it_end; ++ it)
+			{
+				(*it).mRay->Ref();			
+				leaf->mVssRays.push_back((*it).mRay);
+			}
+		}
+
+		// should I check here?
+		viewCell->mLeaf = leaf;
+
+		if (mUseAreaForPvs)
+			viewCell->SetArea(tData.mProbability);
+		else
+			viewCell->SetVolume(tData.mProbability);
+
+        leaf->mProbability = tData.mProbability;
+
+		EvaluateLeafStats(tData);		
+	}
+
+	//-- cleanup
+	tData.Clear();
+
+	return newNode;
+}
+
+
+void FromPointVisibilityTree::EvalPriority(VspBspTraversalData &tData) const
+{
+    switch (mNodePriorityQueueType) 
+	{
+	case BREATH_FIRST:
+		tData.mPriority = (float)-tData.mDepth;
+		break;
+	case DEPTH_FIRST:
+		tData.mPriority = (float)tData.mDepth;
+		break;
+	default:
+		tData.mPriority = tData.mPvs * tData.mProbability;
+		//Debug << "priority: " << tData.mPriority << endl;
+		break;
+	}
+}
+
+
+void FromPointVisibilityTree::EvalSplitCandidate(VspBspTraversalData &tData,
+									VspBspSplitCandidate &splitData)
+{
+	VspBspTraversalData frontData;
+	VspBspTraversalData backData;
+
+	BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+	// compute locally best split plane
+    bool success = SelectPlane(splitData.mSplitPlane, leaf, tData, 
+							   frontData, backData, splitData.mSplitAxis);
+
+	// TODO: reuse
+	DEL_PTR(frontData.mGeometry);
+	DEL_PTR(backData.mGeometry);
+	
+	// compute global decrease in render cost
+	splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
+	splitData.mParentData = tData;
+	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
+}
+
+
+BspInterior *FromPointVisibilityTree::SubdivideNode(const Plane3 &splitPlane,
+									   VspBspTraversalData &tData,
+									   VspBspTraversalData &frontData,
+									   VspBspTraversalData &backData,
+									   PolygonContainer &coincident)
+{
+	BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+	
+	//-- the front and back traversal data is filled with the new values
+	frontData.mDepth = tData.mDepth + 1;
+	frontData.mPolygons = new PolygonContainer();
+	frontData.mRays = new RayInfoContainer();
+	
+	backData.mDepth = tData.mDepth + 1;
+	backData.mPolygons = new PolygonContainer();
+	backData.mRays = new RayInfoContainer();
+	
+
+	//-- subdivide rays
+	SplitRays(splitPlane,
+			  *tData.mRays,
+			  *frontData.mRays,
+			  *backData.mRays);
+
+
+	// compute pvs
+	frontData.mPvs = ComputePvsSize(*frontData.mRays);
+	backData.mPvs = ComputePvsSize(*backData.mRays);
+
+	// split front and back node geometry and compute area
+	
+	// if geometry was not already computed
+	if (!frontData.mGeometry && !backData.mGeometry)
+	{
+		frontData.mGeometry = new BspNodeGeometry();
+		backData.mGeometry = new BspNodeGeometry();
+
+		tData.mGeometry->SplitGeometry(*frontData.mGeometry,
+									   *backData.mGeometry,
+									   splitPlane,
+									   mBox,
+									   //0.0f);
+									   mEpsilon);
+		
+		if (mUseAreaForPvs)
+		{
+			frontData.mProbability = frontData.mGeometry->GetArea();
+			backData.mProbability = backData.mGeometry->GetArea();
+		}
+		else
+		{
+			frontData.mProbability = frontData.mGeometry->GetVolume();
+			backData.mProbability = tData.mProbability - frontData.mProbability;
+
+			// should never come here: wrong volume !!!
+			if (0)
+			{
+				if (frontData.mProbability < -0.00001)
+					Debug << "fatal error f: " << frontData.mProbability << endl;
+				if (backData.mProbability < -0.00001)
+					Debug << "fatal error b: " << backData.mProbability << endl;
+
+				// clamp because of precision issues
+				if (frontData.mProbability < 0)	frontData.mProbability = 0;
+				if (backData.mProbability < 0) backData.mProbability = 0;
+			}
+		}
+	}
+
+	
+    // subdivide polygons
+	SplitPolygons(splitPlane,
+				  *tData.mPolygons,
+	              *frontData.mPolygons,
+				  *backData.mPolygons,
+				  coincident);
+
+
+
+	///////////////////////////////////////
+	// subdivide further
+
+	// store maximal and minimal depth
+	if (tData.mDepth > mBspStats.maxDepth)
+	{
+		Debug << "max depth increases to " << tData.mDepth << " at " << mBspStats.Leaves() << " leaves" << endl;
+		mBspStats.maxDepth = tData.mDepth;
+	}
+
+	mBspStats.nodes += 2;
+
+    
+	BspInterior *interior = new BspInterior(splitPlane);
+
+#ifdef _DEBUG
+	Debug << interior << endl;
+#endif
+
+
+	//-- create front and back leaf
+
+	BspInterior *parent = leaf->GetParent();
+
+	// replace a link from node's parent
+	if (parent)
+	{
+		parent->ReplaceChildLink(leaf, interior);
+		interior->SetParent(parent);
+	}
+	else // new root
+	{
+		mRoot = interior;
+	}
+
+	// and setup child links
+	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
+
+	frontData.mNode = interior->GetFront();
+	backData.mNode = interior->GetBack();
+
+	interior->mTimeStamp = mTimeStamp ++;
+	
+
+	//DEL_PTR(leaf);
+	return interior;
+}
+
+
+void FromPointVisibilityTree::Construct(const VisibilityPointsContainer &visibilityPoints,
+										AxisAlignedBox3 *forcedBoundingBox)
+{
+	/*mBspStats.nodes = 1;
+	mBox.Initialize(); 	// initialise BSP tree bounding box
+
+	if (forcedBoundingBox)
+		mBox = *forcedBoundingBox;
+	
+	PolygonContainer polys;
+	RayInfoContainer *rays = new RayInfoContainer();
+
+	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+	long startTime = GetTime();
+
+	cout << "Extracting polygons from rays ... ";
+
+	Intersectable::NewMail();
+
+	int numObj = 0;
+
+	//-- extract polygons intersected by the rays
+	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+	{
+		VssRay *ray = *rit;
+
+		if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
+			ray->mTerminationObject && 
+			!ray->mTerminationObject->Mailed())
+		{
+			ray->mTerminationObject->Mail();
+			MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
+			AddMeshToPolygons(obj->GetMesh(), polys, obj);
+			++ numObj;
+
+			//-- compute bounding box
+			if (!forcedBoundingBox)
+				mBox.Include(ray->mTermination);
+		}
+
+		if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
+			ray->mOriginObject && 
+			!ray->mOriginObject->Mailed())
+		{
+			ray->mOriginObject->Mail();
+			MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
+			AddMeshToPolygons(obj->GetMesh(), polys, obj);
+			++ numObj;
+
+			//-- compute bounding box
+			if (!forcedBoundingBox)
+				mBox.Include(ray->mOrigin);
+		}
+	}
+	
+	Debug << "maximal pvs (i.e., pvs still considered as valid) : " 
+		  << mViewCellsManager->GetMaxPvsSize() << endl;
+
+	//-- store rays
+	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+	{
+		VssRay *ray = *rit;
+
+		float minT, maxT;
+
+		static Ray hray;
+		hray.Init(*ray);
+
+		// TODO: not very efficient to implictly cast between rays types
+		if (mBox.GetRaySegment(hray, minT, maxT))
+		{
+			float len = ray->Length();
+
+			if (!len)
+				len = Limits::Small;
+
+			rays->push_back(RayInfo(ray, minT / len, maxT / len));
+		}
+	}
+
+	// normalize
+	if (mUseAreaForPvs)
+		mTermMinProbability *= mBox.SurfaceArea(); 
+	else 
+		mTermMinProbability *= mBox.GetVolume();
+
+	// throw out unnecessary polygons
+	PreprocessPolygons(polys);
+
+	mBspStats.polys = (int)polys.size();
+	mGlobalCostMisses = 0;
+
+	cout << "finished" << endl;
+
+	Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
+		  << (int)sampleRays.size() << " rays in "
+		  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
+
+	// use split cost priority queue
+	if (mUseSplitCostQueue)
+	{
+		ConstructWithSplitQueue(polys, rays);
+	}
+	else
+	{
+		Construct(polys, rays);
+	}
+
+	// clean up polygons
+	CLEAR_CONTAINER(polys);
+	*/
+}
+
+
+
+void FromPointVisibilityTree::AddToPvs(BspLeaf *leaf,
+						  const RayInfoContainer &rays,
+						  float &sampleContributions,
+						  int &contributingSamples)
+{
+	sampleContributions = 0;
+	contributingSamples = 0;
+
+
+	RayInfoContainer::const_iterator it, it_end = rays.end();
+    ViewCell *vc = leaf->GetViewCell();
+
+    // add contributions from samples to the PVS
+	for (it = rays.begin(); it != it_end; ++ it)
+	{
+		float sc = 0.0f;
+		
+		VssRay *ray = (*it).mRay;
+		
+		bool madeContrib = false;
+		float contribution;
+		
+		if (ray->mTerminationObject) 
+		{
+			if (vc->GetPvs().AddSample(ray->mTerminationObject, ray->mPdf, contribution))
+				madeContrib = true;
+			sc += contribution;
+		}
+	  
+	  if (ray->mOriginObject) 
+	  {
+		  if (vc->GetPvs().AddSample(ray->mOriginObject, ray->mPdf, contribution))
+			  madeContrib = true;
+		  sc += contribution;
+	  }
+	  
+	  sampleContributions += sc;
+	  if (madeContrib)
+		  ++ contributingSamples;
+		
+	  //leaf->mVssRays.push_back(ray);
+	}
+}
+
+
+void FromPointVisibilityTree::SortSplitCandidates(const RayInfoContainer &rays, 
+									 const int axis, 
+									 float minBand, 
+									 float maxBand)
+{
+	mSplitCandidates->clear();
+
+	int requestedSize = 2 * (int)(rays.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);
+
+	float pos;
+
+	// float values => don't compare with exact values
+	if (0)
+	{
+		minBand += Limits::Small;
+		maxBand -= Limits::Small;
+	}
+
+	// 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);
+		// clamp to min / max band
+		if (0) ClipValue(pos, minBand, maxBand);
+		
+		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
+									pos, (*ri).mRay));
+
+		pos = (*ri).ExtrapTermination(axis);
+		// clamp to min / max band
+		if (0) ClipValue(pos, minBand, maxBand);
+
+		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
+									pos, (*ri).mRay));
+	}
+
+	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
+}
+
+
+float FromPointVisibilityTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
+										  const AxisAlignedBox3 &box,
+										  const int pvsSize,
+										  const int axis,
+                                          float &position)
+{
+	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);
+
+	// 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 border can be found, take mid split
+	position = minBox + 0.5f * sizeBox;
+
+	Intersectable::NewMail();
+
+   	RayInfoContainer::const_iterator ri, ri_end = rays.end();
+
+	// set all object as belonging to the front pvs
+	for(ri = rays.begin(); ri != ri_end; ++ ri)
+	{
+		Intersectable *oObject = (*ri).mRay->mOriginObject;
+		Intersectable *tObject = (*ri).mRay->mTerminationObject;
+
+		if (oObject)
+		{
+			if (!oObject->Mailed())
+			{
+				oObject->Mail();
+				oObject->mCounter = 1;
+			}
+			else
+			{
+				++ oObject->mCounter;
+			}
+		}
+		if (tObject)
+		{
+			if (!tObject->Mailed())
+			{
+				tObject->Mail();
+				tObject->mCounter = 1;
+			}
+			else
+			{
+				++ tObject->mCounter;
+			}
+		}
+	}
+
+	Intersectable::NewMail();
+
+	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
+
+	for (ci = mSplitCandidates->begin(); ci < ci_end; ++ ci)
+	{
+		VssRay *ray;
+		ray = (*ci).ray;
+		
+		Intersectable *oObject = ray->mOriginObject;
+		Intersectable *tObject = ray->mTerminationObject;
+		
+
+		switch ((*ci).type)
+		{
+			case SortableEntry::ERayMin:
+				{
+					if (oObject && !oObject->Mailed())
+					{
+						oObject->Mail();
+						++ pvsl;
+					}
+					if (tObject && !tObject->Mailed())
+					{
+						tObject->Mail();
+						++ pvsl;
+					}
+					break;
+				}
+			case SortableEntry::ERayMax:
+				{
+					if (oObject)
+					{
+						if (-- oObject->mCounter == 0)
+							-- pvsr;
+					}
+
+					if (tObject)
+					{
+						if (-- tObject->mCounter == 0)
+							-- pvsr;
+					}
+
+					break;
+				}
+		}
+
+		// Note: sufficient to compare size of bounding boxes of front and back side?
+		if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
+		{
+			sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
+
+			//cout << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
+			//cout<<"cost= "<<sum<<endl;
+
+			if (sum < minSum)
+			{
+				minSum = sum;
+				position = (*ci).value;
+				
+				pvsBack = pvsl;
+				pvsFront = pvsr;
+			}
+		}
+	}
+	
+	Debug << "pos: " << position << " sizebox: " << sizeBox << " pvs: " << pvsSize << endl;
+
+	// -- compute cost
+	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+	const float pOverall = sizeBox;
+
+	const float pBack = position - minBox;
+	const float pFront = maxBox - position;
+	
+	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+	
+	const float oldRenderCost = penaltyOld * pOverall;
+	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+	float ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
+
+	//Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+	//     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
+
+	return ratio;
+}
+
+
+float FromPointVisibilityTree::SelectAxisAlignedPlane(Plane3 &plane,
+										 const VspBspTraversalData &tData,
+										 int &axis,
+										 BspNodeGeometry **frontGeom,
+										 BspNodeGeometry **backGeom,
+										 float &pFront,
+										 float &pBack,
+										 const bool isKdNode)
+{
+	float nPosition[3];
+	float nCostRatio[3];
+	float nProbFront[3];
+	float nProbBack[3];
+
+	BspNodeGeometry *nFrontGeom[3];
+	BspNodeGeometry *nBackGeom[3];
+
+	for (int i = 0; i < 3; ++ i)
+	{
+		nFrontGeom[i] = NULL;
+		nBackGeom[i] = NULL;
+	}
+
+	int bestAxis = -1;
+
+	// create bounding box of node geometry
+	AxisAlignedBox3 box;
+		
+	//TODO: for kd split geometry already is box => only take minmax vertices
+	if (1)
+	{
+		tData.mGeometry->GetBoundingBox(box);
+	}
+	else
+	{
+		box.Initialize();
+		RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
+
+		for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
+			box.Include((*ri).ExtrapTermination());
+	}
+
+	int sAxis = 0;
+	// hack : subdivide along driving axis up to certain depth
+	int maxDepthForDrivingAxis = 0;
+
+    const bool useSpecialAxis = mOnlyDrivingAxis || mUseRandomAxis || 
+		mCirculatingAxis || (tData.mDepth < maxDepthForDrivingAxis);
+
+
+	// use some kind of specialised fixed axis
+	if (mUseRandomAxis)
+		sAxis = Random(3);
+	else if (mCirculatingAxis)
+		sAxis = (tData.mAxis + 1) % 3;
+	else if (mOnlyDrivingAxis || (tData.mDepth < maxDepthForDrivingAxis))
+		sAxis = box.Size().DrivingAxis();
+
+		
+	//Debug << "use special axis: " << useSpecialAxis << endl;
+	//Debug << "axis: " << sAxis << " drivingaxis: " << box.Size().DrivingAxis();
+
+	for (axis = 0; axis < 3; ++ axis)
+	{
+		if (!useSpecialAxis || (axis == sAxis))
+		{
+			if (!mUseCostHeuristics)
+			{
+				nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
+				Vector3 normal(0,0,0); normal[axis] = 1.0f;
+
+				// allows faster split because we have axis aligned kd tree boxes
+				if (0 && isKdNode)
+				{
+					nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
+																box,
+																axis,
+																nPosition[axis],
+																nProbFront[axis], 
+																nProbBack[axis]);
+					
+					Vector3 pos;
+					
+					// create back geometry from box
+					pos = box.Max(); pos[axis] = nPosition[axis];
+					AxisAlignedBox3 bBox(box.Min(), pos);
+					PolygonContainer fPolys;
+					bBox.ExtractPolys(fPolys);
+
+					nBackGeom[axis] = new BspNodeGeometry(fPolys);
+	
+					// create front geometry from box
+					pos = box.Min(); pos[axis] = nPosition[axis];
+					AxisAlignedBox3 fBox(pos, box.Max());
+
+					PolygonContainer bPolys;
+					fBox.ExtractPolys(bPolys);
+					nFrontGeom[axis] = new BspNodeGeometry(bPolys);
+				}
+				else
+				{
+					nFrontGeom[axis] = new BspNodeGeometry();
+					nBackGeom[axis] = new BspNodeGeometry();
+
+					nCostRatio[axis] = 
+						EvalSplitPlaneCost(Plane3(normal, nPosition[axis]), 
+										   tData, *nFrontGeom[axis], *nBackGeom[axis],
+										   nProbFront[axis], nProbBack[axis]);
+				}
+			}
+			else
+			{
+				nCostRatio[axis] =
+					BestCostRatioHeuristics(*tData.mRays,
+										    box,
+											tData.mPvs,
+											axis,
+											nPosition[axis]);
+			}
+
+			if (bestAxis == -1)
+			{
+				bestAxis = axis;
+			}
+			else if (nCostRatio[axis] < nCostRatio[bestAxis])
+			{
+				bestAxis = axis;
+			}
+
+		}
+	}
+
+	//-- assign values
+	axis = bestAxis;
+	pFront = nProbFront[bestAxis];
+	pBack = nProbBack[bestAxis];
+
+	// assign best split nodes geometry 
+	*frontGeom = nFrontGeom[bestAxis];
+	*backGeom = nBackGeom[bestAxis];
+
+	// and delete other geometry
+	DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]);
+	DEL_PTR(nBackGeom[(bestAxis + 2) % 3]);
+
+	//-- split plane
+    Vector3 normal(0,0,0); normal[bestAxis] = 1;
+	plane = Plane3(normal, nPosition[bestAxis]);
+
+	return nCostRatio[bestAxis];
+}
+
+
+bool FromPointVisibilityTree::SelectPlane(Plane3 &bestPlane,
+							 BspLeaf *leaf,
+							 VspBspTraversalData &data,							 
+							 VspBspTraversalData &frontData,
+							 VspBspTraversalData &backData,
+							 int &splitAxis)
+{
+	// HACK matt: subdivide regularily to certain depth
+	if (data.mDepth < 0)  	
+	{
+		cout << "d: " << data.mDepth << endl;
+		// return axis aligned split
+		AxisAlignedBox3 box;
+		box.Initialize();
+	
+		// create bounding box of region
+		data.mGeometry->GetBoundingBox(box);
+	
+		const int axis = box.Size().DrivingAxis();
+		const Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
+
+		Vector3 norm(0,0,0); norm[axis] = 1.0f;
+		bestPlane = Plane3(norm, position);
+		splitAxis = axis;
+		return true;
+	}
+
+	// simplest strategy: just take next polygon
+	if (mSplitPlaneStrategy & RANDOM_POLYGON)
+	{
+        if (!data.mPolygons->empty())
+		{
+			const int randIdx = 
+				(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
+			Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
+
+			bestPlane = nextPoly->GetSupportingPlane();
+			return true;
+		}
+	}
+
+	//-- use heuristics to find appropriate plane
+
+	// intermediate plane
+	Plane3 plane;
+	float lowestCost = MAX_FLOAT;
+	
+	// decides if the first few splits should be only axisAligned
+	const bool onlyAxisAligned  = 
+		(mSplitPlaneStrategy & AXIS_ALIGNED) &&
+		((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
+		((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
+	
+	const int limit = onlyAxisAligned ? 0 : 
+		Min((int)data.mPolygons->size(), mMaxPolyCandidates);
+
+	float candidateCost;
+
+	int maxIdx = (int)data.mPolygons->size();
+
+	for (int i = 0; i < limit; ++ i)
+	{
+		// the already taken candidates are stored behind maxIdx
+		// => assure that no index is taken twice
+		const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
+		Polygon3 *poly = (*data.mPolygons)[candidateIdx];
+
+		// swap candidate to the end to avoid testing same plane
+		std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
+		//Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
+
+		// evaluate current candidate
+		BspNodeGeometry fGeom, bGeom;
+		float fArea, bArea;
+		plane = poly->GetSupportingPlane();
+		candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
+		
+		if (candidateCost < lowestCost)
+		{
+			bestPlane = plane;
+			lowestCost = candidateCost;
+		}
+	}
+
+	//-- evaluate axis aligned splits
+	int axis;
+	BspNodeGeometry *fGeom, *bGeom;
+	float pFront, pBack;
+
+	candidateCost = 99999999.0f;
+
+	// option: axis aligned split only if no polygon available
+	if (!mUsePolygonSplitIfAvailable || data.mPolygons->empty())
+	{
+		candidateCost = SelectAxisAlignedPlane(plane, 
+											   data, 
+											   axis,
+											   &fGeom, 
+											   &bGeom, 
+											   pFront, 
+											   pBack,
+											   data.mIsKdNode);	 
+	}
+
+	splitAxis = 3;
+
+	if (candidateCost < lowestCost)
+	{	
+		bestPlane = plane;
+		lowestCost = candidateCost;
+		splitAxis = axis;
+	
+		// assign already computed values
+		// we can do this because we always save the
+		// computed values from the axis aligned splits		
+
+		if (fGeom && bGeom)
+		{
+			frontData.mGeometry = fGeom;
+			backData.mGeometry = bGeom;
+	
+			frontData.mProbability = pFront;
+			backData.mProbability = pBack;
+		}
+	}
+	else
+	{
+		DEL_PTR(fGeom);
+		DEL_PTR(bGeom);
+	}
+    
+#ifdef _DEBUG
+	Debug << "plane lowest cost: " << lowestCost << endl;
+#endif
+
+	// exeeded relative max cost ratio
+	if (lowestCost > mTermMaxCostRatio)
+	{
+		return false;
+	}
+
+	return true;
+}
+
+
+Plane3 FromPointVisibilityTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
+{
+	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+	const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
+	const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
+
+	const Vector3 pt = (maxPt + minPt) * 0.5;
+	const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
+
+	return Plane3(normal, pt);
+}
+
+
+Plane3 FromPointVisibilityTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
+{
+	Vector3 pt[3];
+
+	int idx[3];
+	int cmaxT = 0;
+	int cminT = 0;
+	bool chooseMin = false;
+
+	for (int j = 0; j < 3; ++ j)
+	{
+		idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
+
+		if (idx[j] >= (int)rays.size())
+		{
+			idx[j] -= (int)rays.size();
+
+			chooseMin = (cminT < 2);
+		}
+		else
+			chooseMin = (cmaxT < 2);
+
+		RayInfo rayInf = rays[idx[j]];
+		pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
+	}
+
+	return Plane3(pt[0], pt[1], pt[2]);
+}
+
+
+Plane3 FromPointVisibilityTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
+{
+	Vector3 pt[3];
+
+	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+	// check if rays different
+	if (idx1 == idx2)
+		idx2 = (idx2 + 1) % (int)rays.size();
+
+	const RayInfo ray1 = rays[idx1];
+	const RayInfo ray2 = rays[idx2];
+
+	// normal vector of the plane parallel to both lines
+	const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
+
+	// vector from line 1 to line 2
+	const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
+
+	// project vector on normal to get distance
+	const float dist = DotProd(vd, norm);
+
+	// point on plane lies halfway between the two planes
+	const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
+
+	return Plane3(norm, planePt);
+}
+
+
+inline void FromPointVisibilityTree::GenerateUniqueIdsForPvs()
+{
+	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
+	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
+	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
+}
+
+
+float FromPointVisibilityTree::EvalRenderCostDecrease(const Plane3 &candidatePlane,
+										 const VspBspTraversalData &data) const
+{
+	float pvsFront = 0;
+	float pvsBack = 0;
+	float totalPvs = 0;
+
+	// probability that view point lies in back / front node
+	float pOverall = data.mProbability;
+	float pFront = 0;
+	float pBack = 0;
+
+
+	// create unique ids for pvs heuristics
+	GenerateUniqueIdsForPvs();
+	
+	for (int i = 0; i < data.mRays->size(); ++ i)
+	{
+		RayInfo rayInf = (*data.mRays)[i];
+
+		float t;
+		VssRay *ray = rayInf.mRay;
+		const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+
+		// find front and back pvs for origing and termination object
+		AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+		AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+	}
+
+
+	BspNodeGeometry geomFront;
+	BspNodeGeometry geomBack;
+
+	// construct child geometry with regard to the candidate split plane
+	data.mGeometry->SplitGeometry(geomFront,
+								  geomBack,
+								  candidatePlane,
+								  mBox,
+								  //0.0f);
+								  mEpsilon);
+
+	if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
+	{
+		pFront = geomFront.GetVolume();
+		pBack = pOverall - pFront;
+
+		// something is wrong with the volume
+		if ((pFront < 0.0) || (pBack < 0.0))
+		{
+			Debug << "ERROR in volume:\n"
+				  << "volume f :" << pFront << " b: " << pBack << " p: " << pOverall 
+				  << ", real volume f: " << pFront << " b: " << geomBack.GetVolume()
+				  << ", #polygons f: " << geomFront.Size() << " b: " << geomBack.Size() << " p: " << data.mGeometry->Size() << endl;
+		}
+	}
+	else
+	{
+		pFront = geomFront.GetArea();
+		pBack = geomBack.GetArea();
+	}
+	
+
+	// -- pvs rendering heuristics
+	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+	// only render cost heuristics or combined with standard deviation
+	const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+			
+	const float oldRenderCost = pOverall * penaltyOld;
+	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
+	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
+	
+
+#if 1
+	// take render cost of node into account
+	const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
+	//Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl;
+	//return 0.5f * renderCostDecrease + 0.5f * normalizedOldRenderCost;
+	return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
+#else
+	return renderCostDecrease;
+#endif
+}
+
+
+float FromPointVisibilityTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
+									 const VspBspTraversalData &data,
+									 BspNodeGeometry &geomFront,
+									 BspNodeGeometry &geomBack,
+									 float &pFront,
+									 float &pBack) const
+{
+	float cost = 0;
+
+	float totalPvs = 0;
+	float pvsFront = 0;
+	float pvsBack = 0;
+	
+	// probability that view point lies in back / front node
+	float pOverall = 0;
+	pFront = 0;
+	pBack = 0;
+
+
+	int limit;
+	bool useRand;
+
+	// create unique ids for pvs heuristics
+	GenerateUniqueIdsForPvs();
+
+	// choose test rays randomly if too much
+	if ((int)data.mRays->size() > mMaxTests)
+	{
+		useRand = true;
+		limit = mMaxTests;
+	}
+	else
+	{
+		useRand = false;
+		limit = (int)data.mRays->size();
+	}
+	
+	for (int i = 0; i < limit; ++ i)
+	{
+		const int testIdx = useRand ? 
+			(int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
+		RayInfo rayInf = (*data.mRays)[testIdx];
+
+		float t;
+		VssRay *ray = rayInf.mRay;
+		const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+
+		// find front and back pvs for origing and termination object
+		AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+		AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+	}
+
+	// construct child geometry with regard to the candidate split plane
+	bool splitSuccessFull = data.mGeometry->SplitGeometry(geomFront,
+														  geomBack,
+														  candidatePlane,
+														  mBox,
+														  //0.0f);
+														  mEpsilon);
+
+	pOverall = data.mProbability;
+
+	if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
+	{
+		pFront = geomFront.GetVolume();
+		pBack = pOverall - pFront;
+		
+		// HACK: precision issues possible for unbalanced split => don't take this split!
+		if (1 && 
+			(!splitSuccessFull || (pFront <= 0) || (pBack <= 0) || 
+			!geomFront.Valid() || !geomBack.Valid()))
+		{
+			//Debug << "error f: " << pFront << " b: " << pBack << endl;
+			// high penalty for this split
+			return 99999.9f;
+		}
+	}
+	else
+	{
+		pFront = geomFront.GetArea();
+		pBack = geomBack.GetArea();
+	}
+	
+
+	// -- pvs rendering heuristics
+	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+	// only render cost heuristics or combined with standard deviation
+	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
+	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
+			
+	const float oldRenderCost = pOverall * penaltyOld;
+	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+	float oldCost, newCost;
+
+	// only render cost
+	if (1)
+	{
+		oldCost = oldRenderCost;
+		newCost = newRenderCost;
+	}
+	else // also considering standard deviation
+	{
+		// standard deviation is difference of back and front pvs
+		const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
+
+		const float newDeviation = 0.5f * 
+			fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
+
+		const float oldDeviation = penaltyOld;
+
+		newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
+		oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
+	}
+
+	cost += mPvsFactor * newCost / (oldCost + Limits::Small);
+		
+
+#ifdef _DEBUG
+  	Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
+  		  << " frontpvs: " << pvsFront << " pFront: " << pFront
+  		  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
+	Debug << "cost: " << cost << endl;
+#endif
+
+	return cost;
+}
+
+
+int FromPointVisibilityTree::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
+										ViewCellContainer &viewCells) const
+{
+	stack<bspNodePair> nodeStack;
+	BspNodeGeometry *rgeom = new BspNodeGeometry();
+
+	ConstructGeometry(mRoot, *rgeom);
+
+	nodeStack.push(bspNodePair(mRoot, rgeom));
+  
+	ViewCell::NewMail();
+
+	while (!nodeStack.empty()) 
+	{
+		BspNode *node = nodeStack.top().first;
+		BspNodeGeometry *geom = nodeStack.top().second;
+		nodeStack.pop();
+
+		const int side = geom->ComputeIntersection(box);
+		
+		switch (side)
+		{
+		case -1:
+			// node geometry is contained in box
+			CollectViewCells(node, true, viewCells, true);
+			break;
+
+		case 0:
+			if (node->IsLeaf())
+			{
+				BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+			
+				if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
+				{
+					leaf->GetViewCell()->Mail();
+					viewCells.push_back(leaf->GetViewCell());
+				}
+			}
+			else 
+			{
+				BspInterior *interior = dynamic_cast<BspInterior *>(node);
+			
+				BspNode *first = interior->GetFront();
+				BspNode *second = interior->GetBack();
+            
+				BspNodeGeometry *firstGeom = new BspNodeGeometry();
+				BspNodeGeometry *secondGeom = new BspNodeGeometry();
+
+				geom->SplitGeometry(*firstGeom,
+									*secondGeom,
+									interior->GetPlane(),
+									mBox,
+									//0.0000001f);
+									mEpsilon);
+
+				nodeStack.push(bspNodePair(first, firstGeom));
+				nodeStack.push(bspNodePair(second, secondGeom));
+			}
+			
+			break;
+		default:
+			// default: cull
+			break;
+		}
+		
+		DEL_PTR(geom);
+		
+	}
+
+	return (int)viewCells.size();
+}
+
+
+float FromPointVisibilityTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
+										   const AxisAlignedBox3 &box,
+										   const int axis,
+										   const float &position,										  
+										   float &pFront,
+										   float &pBack) const
+{
+	float pvsTotal = 0;
+	float pvsFront = 0;
+	float pvsBack = 0;
+	
+	// create unique ids for pvs heuristics
+	GenerateUniqueIdsForPvs();
+
+	const int pvsSize = data.mPvs;
+
+	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
+
+	// this is the main ray classification loop!
+	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
+	{
+		//if (!(*rit).mRay->IsActive())	continue;
+
+		// determine the side of this ray with respect to the plane
+		float t;
+		const int side = (*rit).ComputeRayIntersection(axis, position, t);
+	
+		AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
+		AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
+	}
+
+	//-- pvs heuristics
+	float pOverall;
+
+	//-- compute heurstics
+	//-- we take simplified computation for mid split
+		
+	pOverall = data.mProbability;
+
+	if (!mUseAreaForPvs)
+	{   // volume
+		pBack = pFront = pOverall * 0.5f;
+		
+#if 0
+		// box length substitute for probability
+		const float minBox = box.Min(axis);
+		const float maxBox = box.Max(axis);
+
+		pBack = position - minBox;
+		pFront = maxBox - position;
+		pOverall = maxBox - minBox;
+#endif
+	}
+	else //-- area substitute for probability
+	{
+		const int axis2 = (axis + 1) % 3;
+		const int axis3 = (axis + 2) % 3;
+
+		const float faceArea = 
+			(box.Max(axis2) - box.Min(axis2)) *
+			(box.Max(axis3) - box.Min(axis3));
+
+		pBack = pFront = pOverall * 0.5f + faceArea;
+	}
+
+#ifdef _DEBUG
+	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
+	Debug << pFront << " " << pBack << " " << pOverall << endl;
+#endif
+
+	
+	const float newCost = pvsBack * pBack + pvsFront * pFront;
+	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
+
+	return  (mCtDivCi + newCost) / oldCost;
+}
+
+
+void FromPointVisibilityTree::AddObjToPvs(Intersectable *obj,
+							 const int cf,
+							 float &frontPvs,
+							 float &backPvs,
+							 float &totalPvs) const
+{
+	if (!obj)
+		return;
+
+	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
+
+	// new object
+	if ((obj->mMailbox != sFrontId) &&
+		(obj->mMailbox != sBackId) &&
+		(obj->mMailbox != sFrontAndBackId))
+	{
+		totalPvs += renderCost;
+	}
+
+	// TODO: does this really belong to no pvs?
+	//if (cf == Ray::COINCIDENT) return;
+
+	// object belongs to both PVS
+	if (cf >= 0)
+	{
+		if ((obj->mMailbox != sFrontId) &&
+			(obj->mMailbox != sFrontAndBackId))
+		{
+			frontPvs += renderCost;
+		
+			if (obj->mMailbox == sBackId)
+				obj->mMailbox = sFrontAndBackId;
+			else
+				obj->mMailbox = sFrontId;
+		}
+	}
+
+	if (cf <= 0)
+	{
+		if ((obj->mMailbox != sBackId) &&
+			(obj->mMailbox != sFrontAndBackId))
+		{
+			backPvs += renderCost;
+		
+			if (obj->mMailbox == sFrontId)
+				obj->mMailbox = sFrontAndBackId;
+			else
+				obj->mMailbox = sBackId;
+		}
+	}
+}
+
+
+void FromPointVisibilityTree::CollectLeaves(vector<BspLeaf *> &leaves, 
+							   const bool onlyUnmailed,
+							   const int maxPvsSize) const
+{
+	stack<BspNode *> nodeStack;
+	nodeStack.push(mRoot);
+
+	while (!nodeStack.empty())
+	{
+		BspNode *node = nodeStack.top();
+		nodeStack.pop();
+		
+		if (node->IsLeaf())
+		{
+			// test if this leaf is in valid view space
+			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+			if (leaf->TreeValid() && 
+				(!onlyUnmailed || !leaf->Mailed()) &&
+				((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
+			{
+				leaves.push_back(leaf);
+			}
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+			nodeStack.push(interior->GetBack());
+			nodeStack.push(interior->GetFront());
+		}
+	}
+}
+
+
+AxisAlignedBox3 FromPointVisibilityTree::GetBoundingBox() const
+{
+	return mBox;
+}
+
+
+BspNode *FromPointVisibilityTree::GetRoot() const
+{
+	return mRoot;
+}
+
+
+void FromPointVisibilityTree::EvaluateLeafStats(const VspBspTraversalData &data)
+{
+	// the node became a leaf -> evaluate stats for leafs
+	BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
+
+
+	if (data.mPvs > mBspStats.maxPvs)
+	{
+		mBspStats.maxPvs = data.mPvs;
+	}
+
+	mBspStats.pvs += data.mPvs;
+
+	if (data.mDepth < mBspStats.minDepth)
+	{
+		mBspStats.minDepth = data.mDepth;
+	}
+	
+	if (data.mDepth >= mTermMaxDepth)
+	{
+        ++ mBspStats.maxDepthNodes;
+		//Debug << "new max depth: " << mBspStats.maxDepthNodes << endl;
+	}
+
+	// accumulate rays to compute rays /  leaf
+	mBspStats.accumRays += (int)data.mRays->size();
+
+	if (data.mPvs < mTermMinPvs)
+		++ mBspStats.minPvsNodes;
+
+	if ((int)data.mRays->size() < mTermMinRays)
+		++ mBspStats.minRaysNodes;
+
+	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
+		++ mBspStats.maxRayContribNodes;
+
+	if (data.mProbability <= mTermMinProbability)
+		++ mBspStats.minProbabilityNodes;
+	
+	// accumulate depth to compute average depth
+	mBspStats.accumDepth += data.mDepth;
+
+	++ mCreatedViewCells;
+
+#ifdef _DEBUG
+	Debug << "BSP stats: "
+		  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
+		  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
+	  //		  << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
+		  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
+		  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
+		  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
+#endif
+}
+
+
+int FromPointVisibilityTree::CastRay(Ray &ray)
+{
+	int hits = 0;
+
+	stack<BspRayTraversalData> tQueue;
+
+	float maxt, mint;
+
+	if (!mBox.GetRaySegment(ray, mint, maxt))
+		return 0;
+
+	Intersectable::NewMail();
+	ViewCell::NewMail();
+	Vector3 entp = ray.Extrap(mint);
+	Vector3 extp = ray.Extrap(maxt);
+
+	BspNode *node = mRoot;
+	BspNode *farChild = NULL;
+
+	while (1)
+	{
+		if (!node->IsLeaf())
+		{
+			BspInterior *in = dynamic_cast<BspInterior *>(node);
+
+			Plane3 splitPlane = in->GetPlane();
+			const int entSide = splitPlane.Side(entp);
+			const int extSide = splitPlane.Side(extp);
+
+			if (entSide < 0)
+			{
+				node = in->GetBack();
+
+				if(extSide <= 0) // plane does not split ray => no far child
+					continue;
+
+				farChild = in->GetFront(); // plane splits ray
+
+			} else if (entSide > 0)
+			{
+				node = in->GetFront();
+
+				if (extSide >= 0) // plane does not split ray => no far child
+					continue;
+
+				farChild = in->GetBack(); // plane splits ray
+			}
+			else // ray and plane are coincident
+			{
+				// WHAT TO DO IN THIS CASE ?
+				//break;
+				node = in->GetFront();
+				continue;
+			}
+
+			// push data for far child
+			tQueue.push(BspRayTraversalData(farChild, extp, maxt));
+
+			// find intersection of ray segment with plane
+			float t;
+			extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
+			maxt *= t;
+
+		} else // reached leaf => intersection with view cell
+		{
+			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+			if (!leaf->GetViewCell()->Mailed())
+			{
+				//ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
+				leaf->GetViewCell()->Mail();
+				++ hits;
+			}
+
+   			//-- fetch the next far child from the stack
+			if (tQueue.empty())
+				break;
+
+			entp = extp;
+			mint = maxt; // NOTE: need this?
+
+			if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+				break;
+
+			BspRayTraversalData &s = tQueue.top();
+
+			node = s.mNode;
+			extp = s.mExitPoint;
+			maxt = s.mMaxT;
+
+			tQueue.pop();
+		}
+	}
+
+	return hits;
+}
+
+
+void FromPointVisibilityTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
+{
+	ViewCell::NewMail();
+	
+	CollectViewCells(mRoot, onlyValid, viewCells, true);
+}
+
+
+void FromPointVisibilityTree::CollapseViewCells()
+{
+// TODO
+#if HAS_TO_BE_REDONE
+	stack<BspNode *> nodeStack;
+
+	if (!mRoot)
+		return;
+
+	nodeStack.push(mRoot);
+	
+	while (!nodeStack.empty()) 
+	{
+		BspNode *node = nodeStack.top();
+		nodeStack.pop();
+		
+		if (node->IsLeaf())
+        {
+			BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+
+			if (!viewCell->GetValid())
+			{
+				BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+	
+				ViewCellContainer leaves;
+				mViewCellsTree->CollectLeaves(viewCell, leaves);
+
+				ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+				for (it = leaves.begin(); it != it_end; ++ it)
+				{
+					BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+					l->SetViewCell(GetOrCreateOutOfBoundsCell());
+					++ mBspStats.invalidLeaves;
+				}
+
+				// add to unbounded view cell
+				GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
+				DEL_PTR(viewCell);
+			}
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+		
+			nodeStack.push(interior->GetFront());
+			nodeStack.push(interior->GetBack());
+		}
+	}
+
+	Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
+#endif
+}
+
+
+void FromPointVisibilityTree::CollectRays(VssRayContainer &rays)
+{
+	vector<BspLeaf *> leaves;
+
+	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
+
+	for (lit = leaves.begin(); lit != lit_end; ++ lit)
+	{
+		BspLeaf *leaf = *lit;
+		VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
+
+		for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
+			rays.push_back(*rit);
+	}
+}
+
+
+void FromPointVisibilityTree::ValidateTree()
+{
+	stack<BspNode *> nodeStack;
+
+	if (!mRoot)
+		return;
+
+	nodeStack.push(mRoot);
+	
+	mBspStats.invalidLeaves = 0;
+	while (!nodeStack.empty()) 
+	{
+		BspNode *node = nodeStack.top();
+		nodeStack.pop();
+		
+		if (node->IsLeaf())
+		{
+			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+			if (!leaf->GetViewCell()->GetValid())
+				++ mBspStats.invalidLeaves;
+
+			// validity flags don't match => repair
+			if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
+			{
+				leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
+				PropagateUpValidity(leaf);
+			}
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+		
+			nodeStack.push(interior->GetFront());
+			nodeStack.push(interior->GetBack());
+		}
+	}
+
+	Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
+}
+
+
+
+void FromPointVisibilityTree::CollectViewCells(BspNode *root,
+								  bool onlyValid,
+								  ViewCellContainer &viewCells,
+								  bool onlyUnmailed) const
+{
+	stack<BspNode *> nodeStack;
+
+	if (!root)
+		return;
+
+	nodeStack.push(root);
+	
+	while (!nodeStack.empty()) 
+	{
+		BspNode *node = nodeStack.top();
+		nodeStack.pop();
+		
+		if (node->IsLeaf())
+		{
+			if (!onlyValid || node->TreeValid())
+			{
+				ViewCell *leafVc = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+
+				ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
+						
+				if (!onlyUnmailed || !viewCell->Mailed()) 
+				{
+					viewCell->Mail();
+					viewCells.push_back(viewCell);
+				}
+			}
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+		
+			nodeStack.push(interior->GetFront());
+			nodeStack.push(interior->GetBack());
+		}
+	}
+
+}
+
+
+void FromPointVisibilityTree::PreprocessPolygons(PolygonContainer &polys)
+{
+	// preprocess: throw out polygons coincident to the view space box (not needed)
+	PolygonContainer boxPolys;
+	mBox.ExtractPolys(boxPolys);
+	vector<Plane3> boxPlanes;
+
+	PolygonContainer::iterator pit, pit_end = boxPolys.end();
+
+	// extract planes of box
+	// TODO: can be done more elegantly than first extracting polygons
+	// and take their planes
+	for (pit = boxPolys.begin(); pit != pit_end; ++ pit)
+	{
+		boxPlanes.push_back((*pit)->GetSupportingPlane());
+	}
+
+	pit_end = polys.end();
+
+	for (pit = polys.begin(); pit != pit_end; ++ pit)
+	{
+		vector<Plane3>::const_iterator bit, bit_end = boxPlanes.end();
+		
+		for (bit = boxPlanes.begin(); (bit != bit_end) && (*pit); ++ bit)
+		{
+			const int cf = (*pit)->ClassifyPlane(*bit, mEpsilon);
+
+			if (cf == Polygon3::COINCIDENT)
+			{
+				DEL_PTR(*pit);
+				//Debug << "coincident!!" << endl;
+			}
+		}
+	}
+
+	// remove deleted entries
+	for (int i = 0; i < (int)polys.size(); ++ i)
+	{
+		while (!polys[i] && (i < (int)polys.size()))
+		{
+			swap(polys[i], polys.back());
+			polys.pop_back();
+		}
+	}
+}
+
+
+float FromPointVisibilityTree::AccumulatedRayLength(const RayInfoContainer &rays) const
+{
+	float len = 0;
+
+	RayInfoContainer::const_iterator it, it_end = rays.end();
+
+	for (it = rays.begin(); it != it_end; ++ it)
+		len += (*it).SegmentLength();
+
+	return len;
+}
+
+
+int FromPointVisibilityTree::SplitRays(const Plane3 &plane,
+						  RayInfoContainer &rays,
+						  RayInfoContainer &frontRays,
+						  RayInfoContainer &backRays) const
+{
+	int splits = 0;
+
+	RayInfoContainer::const_iterator it, it_end = rays.end();
+
+	for (it = rays.begin(); it != it_end; ++ it)
+	{
+		RayInfo bRay = *it;
+		
+		VssRay *ray = bRay.mRay;
+		float t;
+
+		// get classification and receive new t
+		const int cf = bRay.ComputeRayIntersection(plane, t);
+
+		switch (cf)
+		{
+		case -1:
+			backRays.push_back(bRay);
+			break;
+		case 1:
+			frontRays.push_back(bRay);
+			break;
+		case 0:
+			{
+				//-- split ray
+				//   test if start point behind or in front of plane
+				const int side = plane.Side(bRay.ExtrapOrigin());
+
+				if (side <= 0)
+				{
+					backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+					frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+				}
+				else
+				{
+					frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+					backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+				}
+			}
+			break;
+		default:
+			Debug << "Should not come here" << endl;
+			break;
+		}
+	}
+
+	return splits;
+}
+
+
+void FromPointVisibilityTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
+{
+	BspNode *lastNode;
+
+	do
+	{
+		lastNode = n;
+
+		// want to get planes defining geometry of this node => don't take
+		// split plane of node itself
+		n = n->GetParent();
+
+		if (n)
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(n);
+			Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
+
+            if (interior->GetBack() != lastNode)
+				halfSpace.ReverseOrientation();
+
+			halfSpaces.push_back(halfSpace);
+		}
+	}
+	while (n);
+}
+
+
+void FromPointVisibilityTree::ConstructGeometry(BspNode *n,
+								   BspNodeGeometry &geom) const
+{
+	vector<Plane3> halfSpaces;
+	ExtractHalfSpaces(n, halfSpaces);
+
+	PolygonContainer candidatePolys;
+	vector<Plane3> candidatePlanes;
+
+	vector<Plane3>::const_iterator pit, pit_end = halfSpaces.end();
+
+	// bounded planes are added to the polygons
+	for (pit = halfSpaces.begin(); pit != pit_end; ++ pit)
+	{
+		Polygon3 *p = GetBoundingBox().CrossSection(*pit);
+
+		if (p->Valid(mEpsilon))
+		{
+			candidatePolys.push_back(p);
+			candidatePlanes.push_back(*pit);
+		}
+	}
+
+	// add faces of bounding box (also could be faces of the cell)
+	for (int i = 0; i < 6; ++ i)
+	{
+		VertexContainer vertices;
+
+		for (int j = 0; j < 4; ++ j)
+			vertices.push_back(mBox.GetFace(i).mVertices[j]);
+
+		Polygon3 *poly = new Polygon3(vertices);
+
+		candidatePolys.push_back(poly);
+		candidatePlanes.push_back(poly->GetSupportingPlane());
+	}
+
+	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
+	{
+		// polygon is split by all other planes
+		for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
+		{
+			if (i == j) // polygon and plane are coincident
+				continue;
+
+			VertexContainer splitPts;
+			Polygon3 *frontPoly, *backPoly;
+
+			const int cf =
+				candidatePolys[i]->ClassifyPlane(halfSpaces[j],
+												 mEpsilon);
+
+			switch (cf)
+			{
+				case Polygon3::SPLIT:
+					frontPoly = new Polygon3();
+					backPoly = new Polygon3();
+
+					candidatePolys[i]->Split(halfSpaces[j],
+											 *frontPoly,
+											 *backPoly,
+											 mEpsilon);
+
+					DEL_PTR(candidatePolys[i]);
+
+					if (backPoly->Valid(mEpsilon))
+						candidatePolys[i] = backPoly;
+					else
+						DEL_PTR(backPoly);
+
+					// outside, don't need this
+					DEL_PTR(frontPoly);
+					break;
+				// polygon outside of halfspace
+				case Polygon3::FRONT_SIDE:
+					DEL_PTR(candidatePolys[i]);
+					break;
+				// just take polygon as it is
+				case Polygon3::BACK_SIDE:
+				case Polygon3::COINCIDENT:
+				default:
+					break;
+			}
+		}
+
+		if (candidatePolys[i])
+		{
+			geom.Add(candidatePolys[i], candidatePlanes[i]);
+			//	geom.mPolys.push_back(candidates[i]);
+		}
+	}
+}
+
+
+void FromPointVisibilityTree::ConstructGeometry(ViewCell *vc, 
+								   BspNodeGeometry &vcGeom) const
+{
+	ViewCellContainer leaves;
+	
+	mViewCellsTree->CollectLeaves(vc, leaves);
+
+	ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+	for (it = leaves.begin(); it != it_end; ++ it)
+	{
+		BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+		
+		ConstructGeometry(l, vcGeom);
+	}
+}
+
+
+int FromPointVisibilityTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
+							  const bool onlyUnmailed) const
+{
+	stack<bspNodePair> nodeStack;
+	
+	BspNodeGeometry nodeGeom;
+	ConstructGeometry(n, nodeGeom);
+//	const float eps = 0.5f;
+	const float eps = 0.01f;
+	// split planes from the root to this node
+	// needed to verify that we found neighbor leaf
+	// TODO: really needed?
+	vector<Plane3> halfSpaces;
+	ExtractHalfSpaces(n, halfSpaces);
+
+
+	BspNodeGeometry *rgeom = new BspNodeGeometry();
+	ConstructGeometry(mRoot, *rgeom);
+
+	nodeStack.push(bspNodePair(mRoot, rgeom));
+
+	while (!nodeStack.empty())
+	{
+		BspNode *node = nodeStack.top().first;
+		BspNodeGeometry *geom = nodeStack.top().second;
+	
+		nodeStack.pop();
+
+		if (node->IsLeaf())
+		{
+			// test if this leaf is in valid view space
+			if (node->TreeValid() &&
+				(node != n) && 
+				(!onlyUnmailed || !node->Mailed()))
+			{
+				bool isAdjacent = true;
+
+				if (1)
+				{
+					// test all planes of current node if still adjacent
+					for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
+					{
+						const int cf =
+							Polygon3::ClassifyPlane(geom->GetPolys(),
+													halfSpaces[i],
+													eps);
+
+						if (cf == Polygon3::FRONT_SIDE)
+						{
+							isAdjacent = false;
+						}
+					}
+				}
+				else
+				{
+					// TODO: why is this wrong??
+					// test all planes of current node if still adjacent
+					for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i)
+					{
+						Polygon3 *poly = nodeGeom.GetPolys()[i];
+
+						const int cf =
+							Polygon3::ClassifyPlane(geom->GetPolys(),
+													poly->GetSupportingPlane(),
+													eps);
+
+						if (cf == Polygon3::FRONT_SIDE)
+						{
+							isAdjacent = false;
+						}
+					}
+				}
+				// neighbor was found
+				if (isAdjacent)
+				{	
+					neighbors.push_back(dynamic_cast<BspLeaf *>(node));
+				}
+			}
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+			const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
+												   interior->GetPlane(),
+												   eps);
+			
+			BspNode *front = interior->GetFront();
+			BspNode *back = interior->GetBack();
+            
+			BspNodeGeometry *fGeom = new BspNodeGeometry();
+			BspNodeGeometry *bGeom = new BspNodeGeometry();
+
+			geom->SplitGeometry(*fGeom,
+								*bGeom,
+								interior->GetPlane(),
+								mBox,
+								//0.0000001f);
+								eps);
+		
+			if (cf == Polygon3::BACK_SIDE)
+			{
+				nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
+				DEL_PTR(fGeom);
+			}
+			else
+			{
+				if (cf == Polygon3::FRONT_SIDE)
+				{
+					nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
+					DEL_PTR(bGeom);
+				}
+				else
+				{	// random decision
+					nodeStack.push(bspNodePair(front, fGeom));
+					nodeStack.push(bspNodePair(back, bGeom));
+				}
+			}
+		}
+	
+		DEL_PTR(geom);
+	}
+
+	return (int)neighbors.size();
+}
+
+
+
+int FromPointVisibilityTree::FindApproximateNeighbors(BspNode *n, 
+										 vector<BspLeaf *> &neighbors,
+										 const bool onlyUnmailed) const
+{
+	stack<bspNodePair> nodeStack;
+	
+	BspNodeGeometry nodeGeom;
+	ConstructGeometry(n, nodeGeom);
+	
+	float eps = 0.01f;
+	// split planes from the root to this node
+	// needed to verify that we found neighbor leaf
+	// TODO: really needed?
+	vector<Plane3> halfSpaces;
+	ExtractHalfSpaces(n, halfSpaces);
+
+
+	BspNodeGeometry *rgeom = new BspNodeGeometry();
+	ConstructGeometry(mRoot, *rgeom);
+
+	nodeStack.push(bspNodePair(mRoot, rgeom));
+
+	while (!nodeStack.empty())
+	{
+		BspNode *node = nodeStack.top().first;
+		BspNodeGeometry *geom = nodeStack.top().second;
+	
+		nodeStack.pop();
+
+		if (node->IsLeaf())
+		{
+			// test if this leaf is in valid view space
+			if (node->TreeValid() &&
+				(node != n) && 
+				(!onlyUnmailed || !node->Mailed()))
+			{
+				bool isAdjacent = true;
+
+				// neighbor was found
+				if (isAdjacent)
+				{	
+					neighbors.push_back(dynamic_cast<BspLeaf *>(node));
+				}
+			}
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+			const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
+												   interior->GetPlane(),
+												   eps);
+			
+			BspNode *front = interior->GetFront();
+			BspNode *back = interior->GetBack();
+            
+			BspNodeGeometry *fGeom = new BspNodeGeometry();
+			BspNodeGeometry *bGeom = new BspNodeGeometry();
+
+			geom->SplitGeometry(*fGeom,
+								*bGeom,
+								interior->GetPlane(),
+								mBox,
+								//0.0000001f);
+								eps);
+		
+			if (cf == Polygon3::BACK_SIDE)
+			{
+				nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
+				DEL_PTR(fGeom);
+				}
+			else
+			{
+				if (cf == Polygon3::FRONT_SIDE)
+				{
+					nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
+					DEL_PTR(bGeom);
+				}
+				else
+				{	// random decision
+					nodeStack.push(bspNodePair(front, fGeom));
+					nodeStack.push(bspNodePair(back, bGeom));
+				}
+			}
+		}
+	
+		DEL_PTR(geom);
+	}
+
+	return (int)neighbors.size();
+}
+
+
+
+BspLeaf *FromPointVisibilityTree::GetRandomLeaf(const Plane3 &halfspace)
+{
+    stack<BspNode *> nodeStack;
+  	nodeStack.push(mRoot);
+
+	int mask = rand();
+
+	while (!nodeStack.empty())
+	{
+		BspNode *node = nodeStack.top();
+		nodeStack.pop();
+
+		if (node->IsLeaf())
+		{
+			return dynamic_cast<BspLeaf *>(node);
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+			BspNode *next;
+			BspNodeGeometry geom;
+
+			// todo: not very efficient: constructs full cell everytime
+			ConstructGeometry(interior, geom);
+
+			const int cf = 
+				Polygon3::ClassifyPlane(geom.GetPolys(), halfspace, mEpsilon);
+
+			if (cf == Polygon3::BACK_SIDE)
+				next = interior->GetFront();
+			else
+				if (cf == Polygon3::FRONT_SIDE)
+					next = interior->GetFront();
+			else
+			{
+				// random decision
+				if (mask & 1)
+					next = interior->GetBack();
+				else
+					next = interior->GetFront();
+				mask = mask >> 1;
+			}
+
+			nodeStack.push(next);
+		}
+	}
+
+	return NULL;
+}
+
+
+BspLeaf *FromPointVisibilityTree::GetRandomLeaf(const bool onlyUnmailed)
+{
+	stack<BspNode *> nodeStack;
+
+	nodeStack.push(mRoot);
+
+	int mask = rand();
+
+	while (!nodeStack.empty())
+	{
+		BspNode *node = nodeStack.top();
+		nodeStack.pop();
+
+		if (node->IsLeaf())
+		{
+			if ( (!onlyUnmailed || !node->Mailed()) )
+				return dynamic_cast<BspLeaf *>(node);
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+			// random decision
+			if (mask & 1)
+				nodeStack.push(interior->GetBack());
+			else
+				nodeStack.push(interior->GetFront());
+
+			mask = mask >> 1;
+		}
+	}
+
+	return NULL;
+}
+
+
+int FromPointVisibilityTree::ComputePvsSize(const RayInfoContainer &rays) const
+{
+	int pvsSize = 0;
+
+	RayInfoContainer::const_iterator rit, rit_end = rays.end();
+
+	Intersectable::NewMail();
+
+	for (rit = rays.begin(); rit != rays.end(); ++ rit)
+	{
+		VssRay *ray = (*rit).mRay;
+
+		if (ray->mOriginObject)
+		{
+			if (!ray->mOriginObject->Mailed())
+			{
+				ray->mOriginObject->Mail();
+				++ pvsSize;
+			}
+		}
+		if (ray->mTerminationObject)
+		{
+			if (!ray->mTerminationObject->Mailed())
+			{
+				ray->mTerminationObject->Mail();
+				++ pvsSize;
+			}
+		}
+	}
+
+	return pvsSize;
+}
+
+
+float FromPointVisibilityTree::GetEpsilon() const
+{
+	return mEpsilon;
+}
+
+
+int FromPointVisibilityTree::SplitPolygons(const Plane3 &plane,
+							  PolygonContainer &polys,
+							  PolygonContainer &frontPolys,
+							  PolygonContainer &backPolys,
+							  PolygonContainer &coincident) const
+{
+	int splits = 0;
+
+	PolygonContainer::const_iterator it, it_end = polys.end();
+
+	for (it = polys.begin(); it != polys.end(); ++ it)	
+	{
+		Polygon3 *poly = *it;
+
+		// classify polygon
+		const int cf = poly->ClassifyPlane(plane, mEpsilon);
+
+		switch (cf)
+		{
+			case Polygon3::COINCIDENT:
+				coincident.push_back(poly);
+				break;
+			case Polygon3::FRONT_SIDE:
+				frontPolys.push_back(poly);
+				break;
+			case Polygon3::BACK_SIDE:
+				backPolys.push_back(poly);
+				break;
+			case Polygon3::SPLIT:
+				backPolys.push_back(poly);
+				frontPolys.push_back(poly);
+				++ splits;
+				break;
+			default:
+                Debug << "SHOULD NEVER COME HERE\n";
+				break;
+		}
+	}
+
+	return splits;
+}
+
+
+int FromPointVisibilityTree::CastLineSegment(const Vector3 &origin,
+								const Vector3 &termination,
+								vector<ViewCell *> &viewcells)
+{
+	int hits = 0;
+	stack<BspRayTraversalData> tStack;
+
+	float mint = 0.0f, maxt = 1.0f;
+
+	Intersectable::NewMail();
+	ViewCell::NewMail();
+
+	Vector3 entp = origin;
+	Vector3 extp = termination;
+
+	BspNode *node = mRoot;
+	BspNode *farChild = NULL;
+
+	float t;
+	const float thresh = 1e-6f; // matt: change this to adjustable value
+	
+	while (1)
+	{
+		if (!node->IsLeaf())
+		{
+			BspInterior *in = dynamic_cast<BspInterior *>(node);
+
+			Plane3 splitPlane = in->GetPlane();
+			
+			const int entSide = splitPlane.Side(entp, thresh);
+			const int extSide = splitPlane.Side(extp, thresh);
+
+			if (entSide < 0) 
+			{
+				node = in->GetBack();
+				
+				// plane does not split ray => no far child
+				if (extSide <= 0) 
+					continue;
+  
+				farChild = in->GetFront(); // plane splits ray
+			} 
+			else if (entSide > 0)
+			{
+				node = in->GetFront();
+
+				if (extSide >= 0) // plane does not split ray => no far child
+					continue;
+
+				farChild = in->GetBack(); // plane splits ray
+			}
+			else // one of the ray end points is on the plane
+			{	// NOTE: what to do if ray is coincident with plane?
+				if (extSide < 0)
+					node = in->GetBack();
+				else //if (extSide > 0)
+					node = in->GetFront();
+				//else break; // coincident => count no intersections
+
+				continue; // no far child
+			}
+
+			// push data for far child
+			tStack.push(BspRayTraversalData(farChild, extp));
+
+			// find intersection of ray segment with plane
+			extp = splitPlane.FindIntersection(origin, extp, &t);
+		} 
+		else
+		{
+			// reached leaf => intersection with view cell
+			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+			ViewCell *viewCell;
+			
+			if (0)
+				viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
+			else
+				viewCell = leaf->GetViewCell();
+
+			if (!viewCell->Mailed())
+			{
+				viewcells.push_back(viewCell);
+				viewCell->Mail();
+				++ hits;
+			}
+
+			//-- fetch the next far child from the stack
+			if (tStack.empty())
+				break;
+
+			entp = extp;
+			
+			const BspRayTraversalData &s = tStack.top();
+
+			node = s.mNode;
+			extp = s.mExitPoint;
+
+			tStack.pop();
+		}
+	}
+
+	return hits;
+}
+
+
+
+
+int FromPointVisibilityTree::TreeDistance(BspNode *n1, BspNode *n2) const
+{
+	std::deque<BspNode *> path1;
+	BspNode *p1 = n1;
+
+	// create path from node 1 to root
+	while (p1)
+	{
+		if (p1 == n2) // second node on path
+			return (int)path1.size();
+
+		path1.push_front(p1);
+		p1 = p1->GetParent();
+	}
+
+	int depth = n2->GetDepth();
+	int d = depth;
+
+	BspNode *p2 = n2;
+
+	// compare with same depth
+	while (1)
+	{
+		if ((d < (int)path1.size()) && (p2 == path1[d]))
+			return (depth - d) + ((int)path1.size() - 1 - d);
+
+		-- d;
+		p2 = p2->GetParent();
+	}
+
+	return 0; // never come here
+}
+
+
+BspNode *FromPointVisibilityTree::CollapseTree(BspNode *node, int &collapsed)
+{
+// TODO
+#if HAS_TO_BE_REDONE
+	if (node->IsLeaf())
+		return node;
+
+	BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+	BspNode *front = CollapseTree(interior->GetFront(), collapsed);
+	BspNode *back = CollapseTree(interior->GetBack(), collapsed);
+
+	if (front->IsLeaf() && back->IsLeaf())
+	{
+		BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
+		BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
+
+		//-- collapse tree
+		if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
+		{
+			BspViewCell *vc = frontLeaf->GetViewCell();
+
+			BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
+			leaf->SetTreeValid(frontLeaf->TreeValid());
+
+			// replace a link from node's parent
+			if (leaf->GetParent())
+				leaf->GetParent()->ReplaceChildLink(node, leaf);
+			else
+				mRoot = leaf;
+
+			++ collapsed;
+			delete interior;
+
+			return leaf;
+		}
+	}
+#endif
+	return node;
+}
+
+
+int FromPointVisibilityTree::CollapseTree()
+{
+	int collapsed = 0;
+	//TODO
+#if HAS_TO_BE_REDONE
+	(void)CollapseTree(mRoot, collapsed);
+
+	// revalidate leaves
+	RepairViewCellsLeafLists();
+#endif
+	return collapsed;
+}
+
+
+void FromPointVisibilityTree::RepairViewCellsLeafLists()
+{
+// TODO
+#if HAS_TO_BE_REDONE
+	// list not valid anymore => clear
+	stack<BspNode *> nodeStack;
+	nodeStack.push(mRoot);
+
+	ViewCell::NewMail();
+
+	while (!nodeStack.empty())
+	{
+		BspNode *node = nodeStack.top();
+		nodeStack.pop();
+
+		if (node->IsLeaf())
+		{
+			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+			BspViewCell *viewCell = leaf->GetViewCell();
+
+			if (!viewCell->Mailed())
+			{
+				viewCell->mLeaves.clear();
+				viewCell->Mail();
+			}
+	
+			viewCell->mLeaves.push_back(leaf);
+
+		}
+		else
+		{
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+			nodeStack.push(interior->GetFront());
+			nodeStack.push(interior->GetBack());
+		}
+	}
+// TODO
+#endif
+}
+
+
+typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
+
+
+int FromPointVisibilityTree::CastBeam(Beam &beam)
+{
+    stack<bspNodePair> nodeStack;
+	BspNodeGeometry *rgeom = new BspNodeGeometry();
+	ConstructGeometry(mRoot, *rgeom);
+
+	nodeStack.push(bspNodePair(mRoot, rgeom));
+  
+	ViewCell::NewMail();
+
+	while (!nodeStack.empty()) 
+	{
+		BspNode *node = nodeStack.top().first;
+		BspNodeGeometry *geom = nodeStack.top().second;
+		nodeStack.pop();
+		
+		AxisAlignedBox3 box;
+		geom->GetBoundingBox(box);
+
+		const int side = beam.ComputeIntersection(box);
+		
+		switch (side) 
+		{
+		case -1:
+			CollectViewCells(node, true, beam.mViewCells, true);
+			break;
+		case 0:
+			
+			if (node->IsLeaf())
+			{
+				BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+			
+				if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
+				{
+					leaf->GetViewCell()->Mail();
+					beam.mViewCells.push_back(leaf->GetViewCell());
+				}
+			}
+			else 
+			{
+				BspInterior *interior = dynamic_cast<BspInterior *>(node);
+			
+				BspNode *first = interior->GetFront();
+				BspNode *second = interior->GetBack();
+            
+				BspNodeGeometry *firstGeom = new BspNodeGeometry();
+				BspNodeGeometry *secondGeom = new BspNodeGeometry();
+
+				geom->SplitGeometry(*firstGeom,
+									*secondGeom,
+									interior->GetPlane(),
+									mBox,
+									//0.0000001f);
+									mEpsilon);
+
+				// decide on the order of the nodes
+				if (DotProd(beam.mPlanes[0].mNormal, 
+					interior->GetPlane().mNormal) > 0)
+				{
+					swap(first, second);
+					swap(firstGeom, secondGeom);
+				}
+
+				nodeStack.push(bspNodePair(first, firstGeom));
+				nodeStack.push(bspNodePair(second, secondGeom));
+			}
+			
+			break;
+		default:
+			// default: cull
+			break;
+		}
+		
+		DEL_PTR(geom);
+		
+	}
+
+	return (int)beam.mViewCells.size();
+}
+
+
+void FromPointVisibilityTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+	mViewCellsManager = vcm;
+}
+
+
+int FromPointVisibilityTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
+									   vector<MergeCandidate> &candidates)
+{
+	BspLeaf::NewMail();
+	
+	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+	int numCandidates = 0;
+
+	// find merge candidates and push them into queue
+	for (it = leaves.begin(); it != it_end; ++ it)
+	{
+		BspLeaf *leaf = *it;
+		
+		// the same leaves must not be part of two merge candidates
+		leaf->Mail();
+		
+		vector<BspLeaf *> neighbors;
+		
+		// appoximate neighbor search has slightl relaxed constraints
+		if (1)
+			FindNeighbors(leaf, neighbors, true);
+		else
+			FindApproximateNeighbors(leaf, neighbors, true);
+
+		vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
+
+		// TODO: test if at least one ray goes from one leaf to the other
+		for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+		{
+			if ((*nit)->GetViewCell() != leaf->GetViewCell())
+			{
+				MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
+
+				// dont't merge view cells if they are empty and not front and back leaf of the same parent
+				// in the tree?
+				if (mEmptyViewCellsMergeAllowed ||
+					!leaf->GetViewCell()->GetPvs().Empty() || 
+					!(*nit)->GetViewCell()->GetPvs().Empty() ||
+                    leaf->IsSibling(*nit))
+				{
+					candidates.push_back(mc);
+				}
+
+				++ numCandidates;
+				if ((numCandidates % 1000) == 0)
+				{
+					cout << "collected " << numCandidates << " merge candidates" << endl;
+				}
+			}
+		}
+	}
+
+	Debug << "merge queue: " << (int)candidates.size() << endl;
+	Debug << "leaves in queue: " << numCandidates << endl;
+	
+
+	return (int)leaves.size();
+}
+
+
+int FromPointVisibilityTree::CollectMergeCandidates(const VssRayContainer &rays, 
+									   vector<MergeCandidate> &candidates)
+{
+	ViewCell::NewMail();
+	long startTime = GetTime();
+	
+	map<BspLeaf *, vector<BspLeaf*> > neighborMap;
+	ViewCellContainer::const_iterator iit;
+
+	int numLeaves = 0;
+	
+	BspLeaf::NewMail();
+
+	for (int i = 0; i < (int)rays.size(); ++ i)
+	{  
+		VssRay *ray = rays[i];
+	
+		// traverse leaves stored in the rays and compare and 
+		// merge consecutive leaves (i.e., the neighbors in the tree)
+		if (ray->mViewCells.size() < 2)
+			continue;
+//TODO viewcellhierarchy
+		iit = ray->mViewCells.begin();
+		BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
+		BspLeaf *leaf = bspVc->mLeaf;
+		
+		// traverse intersections 
+		// consecutive leaves are neighbors => add them to queue
+		for (; iit != ray->mViewCells.end(); ++ iit)
+		{
+			// next pair
+			BspLeaf *prevLeaf = leaf;
+			bspVc = dynamic_cast<BspViewCell *>(*iit);
+            leaf = bspVc->mLeaf;
+
+			// view space not valid or same view cell
+			if (!leaf->TreeValid() || !prevLeaf->TreeValid() ||
+				(leaf->GetViewCell() == prevLeaf->GetViewCell()))
+				continue;
+
+           	vector<BspLeaf *> &neighbors = neighborMap[leaf];
+			
+			bool found = false;
+
+			// both leaves inserted in queue already =>
+			// look if double pair already exists
+			if (leaf->Mailed() && prevLeaf->Mailed())
+			{
+				vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
+				
+                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
+					if (*it == prevLeaf)
+						found = true; // already in queue
+			}
+		
+			if (!found)
+			{
+				// this pair is not in map yet
+				// => insert into the neighbor map and the queue
+				neighbors.push_back(prevLeaf);
+				neighborMap[prevLeaf].push_back(leaf);
+
+				leaf->Mail();
+				prevLeaf->Mail();
+		
+				MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
+				
+				candidates.push_back(mc);
+
+				if (((int)candidates.size() % 1000) == 0)
+				{
+					cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
+				}
+			}
+        }
+	}
+
+	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
+	Debug << "merge queue: " << (int)candidates.size() << endl;
+	Debug << "leaves in queue: " << numLeaves << endl;
+
+
+	//-- collect the leaves which haven't been found by ray casting
+	if (0)
+	{
+		cout << "finding additional merge candidates using geometry" << endl;
+		vector<BspLeaf *> leaves;
+		CollectLeaves(leaves, true);
+		Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
+		CollectMergeCandidates(leaves, candidates);
+	}
+
+	return numLeaves;
+}
+
+
+
+
+ViewCell *FromPointVisibilityTree::GetViewCell(const Vector3 &point)
+{
+  if (mRoot == NULL)
+	return NULL;
+  
+  stack<BspNode *> nodeStack;
+  nodeStack.push(mRoot);
+  
+  ViewCell *viewcell = NULL;
+  
+  while (!nodeStack.empty())  {
+	BspNode *node = nodeStack.top();
+	nodeStack.pop();
+	
+	if (node->IsLeaf()) {
+	  viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+	  break;
+	} else {
+	  
+	  BspInterior *interior = dynamic_cast<BspInterior *>(node);
+		
+	  // random decision
+	  if (interior->GetPlane().Side(point) < 0)
+		nodeStack.push(interior->GetBack());
+	  else
+		nodeStack.push(interior->GetFront());
+	}
+  }
+  
+  return viewcell;
+}
+
+
+bool FromPointVisibilityTree::ViewPointValid(const Vector3 &viewPoint) const
+{
+	BspNode *node = mRoot;
+
+	while (1)
+	{
+		// early exit
+		if (node->TreeValid())
+			return true;
+
+		if (node->IsLeaf())
+			return false;
+			
+		BspInterior *in = dynamic_cast<BspInterior *>(node);
+					
+		if (in->GetPlane().Side(viewPoint) <= 0) 
+		{
+			node = in->GetBack();
+		} 
+		else
+		{
+			node = in->GetFront();
+		}
+	}
+
+	// should never come here
+	return false;
+}
+
+
+void FromPointVisibilityTree::PropagateUpValidity(BspNode *node)
+{
+	const bool isValid = node->TreeValid();
+
+	// propagative up invalid flag until only invalid nodes exist over this node
+	if (!isValid)
+	{
+		while (!node->IsRoot() && node->GetParent()->TreeValid())
+		{
+			node = node->GetParent();
+			node->SetTreeValid(false);
+		}
+	}
+	else
+	{
+		// propagative up valid flag until one of the subtrees is invalid
+		while (!node->IsRoot() && !node->TreeValid())
+		{
+            node = node->GetParent();
+			BspInterior *interior = dynamic_cast<BspInterior *>(node);
+			
+			// the parent is valid iff both leaves are valid
+			node->SetTreeValid(interior->GetBack()->TreeValid() && 
+							   interior->GetFront()->TreeValid());
+		}
+	}
+}
+
+
+bool FromPointVisibilityTree::Export(ofstream &stream)
+{
+	ExportNode(mRoot, stream);
+
+	return true;
+}
+
+
+void FromPointVisibilityTree::ExportNode(BspNode *node, ofstream &stream)
+{
+	if (node->IsLeaf())
+	{
+		BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+		ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
+
+		int id = -1;
+		if (viewCell != mOutOfBoundsCell)
+			id = viewCell->GetId();
+
+		stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
+	}
+	else
+	{
+		BspInterior *interior = dynamic_cast<BspInterior *>(node);
+	
+		Plane3 plane = interior->GetPlane();
+		stream << "<Interior plane=\"" << plane.mNormal.x << " " 
+			   << plane.mNormal.y << " " << plane.mNormal.z << " " 
+			   << plane.mD << "\">" << endl;
+
+		ExportNode(interior->GetBack(), stream);
+		ExportNode(interior->GetFront(), stream);
+
+		stream << "</Interior>" << endl;
+	}
+}
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h	(revision 503)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h	(revision 810)
@@ -14,4 +14,6 @@
 class Ray;
 class Mesh;
+
+struct VisibilityPoint;
 
 /** Container storing polygons used during BSP tree construction.
@@ -45,4 +47,8 @@
 typedef vector<Mesh *> MeshContainer;
 
+/** Container storing visibility points, i.e. locations in space storing from point visibility
+	information.
+*/
+typedef vector<VisibilityPoint *> VisibilityPointsContainer;
 
 #endif // _Container_H__
