Index: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1002)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1006)
@@ -1,4 +1,4 @@
-#ifndef _VspBspTree_H__
-#define _VspBspTree_H__
+#ifndef _VspOspTree_H__
+#define _VspOspTree_H__
 
 #include "Mesh.h"
@@ -31,25 +31,50 @@
 
 /**
-	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.
+	This class implements a structure holding two different hierarchies,
+	one for object space partitioning and one for view space partitioning.
+
+	The object space and the view space are subdivided using a cost heuristics.
+	If an object space split or a view space split is chosen is also evaluated
+	based on the heuristics. 
+	
+	The view space heuristics is evaluated by weighting and adding the pvss of the back and
+	front node of each specific split. unlike for the standalone method vspbsp tree,
+	the pvs of an object would not be the pvs of single object but that of all objects
+	which are contained in the same leaf of the object subdivision. This could be done
+	by storing the pointer to the object space partition parent, which would allow access to all children.
+	Another possibility is to include traced kd-cells in the ray casing process.
+
+	Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object.
+	the contribution to an object to the pvs is the number of view cells it can be seen from.
+
+
+	There is a potential efficiency problem involved in a sense that once a certain type
+	of split is chosen for view space / object space, the candidates for the next split of 
+	object space / view space must be reevaluated.
+	
 */
-class VspBspTree 
+class VspOspTree 
 {
 	friend class ViewCellsParseHandlers;
 	friend class VspBspViewCellsManager;
+
 public:
 	
+	/** A definition for an axis aligned plane.
+	*/
+	struct AxisAlignedPlane
+	{
+	public:
+		int mAxis;
+		float mPosition;
+	};
+
 	/** Additional data which is passed down the BSP tree during traversal.
 	*/
-	class VspBspTraversalData
+	class VspOspTraversalData
 	{  
 	public:
 		/// the current node
 		BspNode *mNode;
-		/// polygonal data for splitting
-		PolygonContainer *mPolygons;
 		/// current depth
 		int mDepth;
@@ -58,12 +83,10 @@
 		/// the probability that this node contains view point
 		float mProbability;
-		/// geometry of node as induced by planes
-		BspNodeGeometry *mGeometry;
+		/// the bounding box of the node
+		AxisAlignedBox3 mBoundingBox;
 		/// 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;
@@ -80,52 +103,44 @@
 
 
-		VspBspTraversalData():
+		VspOspTraversalData():
 		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, 
+		VspOspTraversalData(BspNode *node, 
 							const int depth, 
 							RayInfoContainer *rays,
 							const int pvs,
 							const float p,
-							BspNodeGeometry *geom): 
+							const AxisAlignedBox3 &box): 
 		mNode(node), 
-		mPolygons(polys), 
 		mDepth(depth), 
 		mRays(rays),
 		mPvs(pvs),
 		mProbability(p),
-		mGeometry(geom),
+		mBoundingBox(box),
 		mMaxCostMisses(0),
-		mIsKdNode(false),
 		mPriority(0),
 		mAxis(0)
 		{}
 
-		VspBspTraversalData(PolygonContainer *polys, 
+		VspOspTraversalData(PolygonContainer *polys, 
 							const int depth, 
 							RayInfoContainer *rays,
-							BspNodeGeometry *geom): 
+							const AxisAlignedBox3 &box): 
 		mNode(NULL), 
-		mPolygons(polys), 
 		mDepth(depth), 
 		mRays(rays),
 		mPvs(0),
 		mProbability(0),
-		mGeometry(geom),
 		mMaxCostMisses(0),
-		mIsKdNode(false),
-		mAxis(0)
+		mAxis(0),
+		mBoundingBox(box)
 		{}
 
@@ -141,10 +156,8 @@
 		void Clear()
 		{
-			DEL_PTR(mPolygons);
 			DEL_PTR(mRays);
-			DEL_PTR(mGeometry);
-		}
-
-		friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
+		}
+
+		friend bool operator<(const VspOspTraversalData &a, const VspOspTraversalData &b)
 		{
 			return a.GetCost() < b.GetCost();
@@ -153,25 +166,22 @@
 	
 
-	typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
-	
-	
-	struct VspBspSplitCandidate
+	typedef std::priority_queue<VspOspTraversalData> VspOspTraversalQueue;
+	
+	
+	struct VspOspSplitCandidate
 	{  
-		/// the current node
-		Plane3 mSplitPlane;
-		/// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned)
-		int mSplitAxis;
+		/// the current plane
+		AxisAlignedPlane mSplitPlane;
 		/// the number of misses of max cost ratio until this split
 		int mMaxCostMisses;
-
-		// parent data
-		VspBspTraversalData mParentData;
-		// cost of applying this split
+		/// parent data
+		VspOspTraversalData mParentData;
+		/// cost of applying this split
 		float mRenderCost;
 
-		VspBspSplitCandidate(): mRenderCost(0) 
+		VspOspSplitCandidate(): mRenderCost(0) 
 		{};
 
-		VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
+		VspOspSplitCandidate(const AxisAlignedPlane &plane, const VspOspTraversalData &tData): 
 		mSplitPlane(plane), mParentData(tData), mRenderCost(0)
 		{}
@@ -189,5 +199,5 @@
 		}
 
-		friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b)
+		friend bool operator<(const VspOspSplitCandidate &a, const VspOspSplitCandidate &b)
 		{
 			return a.GetCost() < b.GetCost();
@@ -195,19 +205,13 @@
     };
 
-	typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue;
+	typedef std::priority_queue<VspOspSplitCandidate> VspOspSplitQueue;
 
 	/** Default constructor creating an empty tree.
 	*/ 
-	VspBspTree();
-
-	
-	/** Constructor creating an empty tree. Loads parameters 
-		from an environment file.
-	*/ 
-	VspBspTree(Environment *env);
+	VspOspTree();
 
 	/** Default destructor.
 	*/
-	~VspBspTree();
+	~VspOspTree();
 
 	/** Returns BSP Tree statistics.
@@ -252,6 +256,4 @@
 	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.
@@ -260,13 +262,4 @@
 					  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.
@@ -400,27 +393,27 @@
 	/** 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;
+	float EvalSplitCost(const VspOspTraversalData &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);
+	void EvalSplitCandidate(VspOspTraversalData &tData, VspOspSplitCandidate &splitData);
 
 	/** Computes priority of the traversal data and stores it in tData.
 	*/
-	void EvalPriority(VspBspTraversalData &tData) const;
+	void EvalPriority(VspOspTraversalData &tData) const;
 
 	/** Evaluates render cost decrease of next split.
 	*/
 	float EvalRenderCostDecrease(const Plane3 &candidatePlane,
-								 const VspBspTraversalData &data) const;
+								 const VspOspTraversalData &data) const;
 
 	/** Constructs tree using the split priority queue.
 	*/
-	void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays);
+	void Construct(RayInfoContainer *rays);
 
 	/** Collects view cells in the subtree under root.
@@ -451,5 +444,5 @@
 	/** Evaluates tree stats in the BSP tree leafs.
 	*/
-	void EvaluateLeafStats(const VspBspTraversalData &data);
+	void EvaluateLeafStats(const VspOspTraversalData &data);
 
 	/** Subdivides node with respect to the traversal data.
@@ -458,44 +451,8 @@
 		@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;
-
+	BspNode *Subdivide(VspOspSplitQueue &tQueue,
+					   VspOspSplitCandidate &splitCandidate);
+
+	
 	/** Subdivides leaf.
 		@param leaf the leaf to be subdivided
@@ -513,45 +470,15 @@
 
 	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);
+							   VspOspTraversalData &tData,
+							   VspOspTraversalData &frontData,
+                               VspOspTraversalData &backData);
 
 	/** 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);
+	float SelectPlane(const VspOspTraversalData &tData,
+					  AxisAlignedPlane &plane,
+					  float &pFront,
+					  float &pBack);
 
 	/** Sorts split candidates for surface area heuristics for axis aligned splits.
@@ -573,9 +500,4 @@
 								  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.
 		
@@ -593,9 +515,4 @@
 				  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.
 
@@ -618,30 +535,9 @@
 	/** Returns true if tree can be terminated.
 	*/
-	inline bool LocalTerminationCriteriaMet(const VspBspTraversalData &data) const;
+	inline bool LocalTerminationCriteriaMet(const VspOspTraversalData &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;
+	inline bool GlobalTerminationCriteriaMet(const VspOspTraversalData &data) const;
 
 	/** Adds ray sample contributions to the PVS.
@@ -655,41 +551,4 @@
 				  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.
 	*/
@@ -707,8 +566,11 @@
 	/** Returns estimated memory usage of tree.
 	*/
-	//float GetMemUsage(const VspBspTraversalQueue &tstack) const;
 	float GetMemUsage() const;
 
 
+protected:
+
+	ViewCellsManager *mViewCellsManager;
+	vector<SortableEntry> *mSplitCandidates;
 
 	/// Pointer to the root of the tree
@@ -716,18 +578,14 @@
 		
 	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
-		};
+	
+	/// View cell corresponding to the space outside the valid view space
+	BspViewCell *mOutOfBoundsCell;
 
 	/// box around the whole view domain
 	AxisAlignedBox3 mBox;
 
-	bool mUseCostHeuristics;
+
+
+	//-- local termination
 
 	/// minimal number of rays before subdivision termination
@@ -741,38 +599,4 @@
 	/// 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;
-
-	bool mUseDrivingAxisForMaxCost;
-	//-- axis aligned split criteria
-	float mAxisAlignedCtDivCi;
-	/// spezifies the split border of the axis aligned split
-	float mAxisAlignedSplitBorder;
-
 	/// maximal acceptable cost ratio
 	float mTermMaxCostRatio;
@@ -780,69 +604,60 @@
 	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;
+
+	//-- global criteria
+	float mTermMinGlobalCostRatio;
+	int mTermGlobalCostMissTolerance;
+	int mGlobalCostMisses;
+
 	/// 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;
+
+
+
+	//-- split heuristics based parameters
+	
+	bool mUseCostHeuristics;
+	/// balancing factor for PVS criterium
+	float mCtDivCi;	
+	/// if only driving axis should be used for split
+	bool mOnlyDrivingAxis;
 	/// if random split axis should be used
 	bool mUseRandomAxis;
-	/// use polygon split whenever there are polys left
-	bool mUsePolygonSplitIfAvailable;
+	/// if vsp bsp tree should simulate octree
+	bool mCirculatingAxis;
+	/// minimal relative position where the split axis can be placed
+	float mMinBand;
+	/// maximal relative position where the split axis can be placed
+	float mMaxBand;
+
+
 	/// current time stamp (used for keeping split history)
 	int mTimeStamp;
+	// if rays should be stored in leaves
+	bool mStoreRays;
+
+	/// epsilon for geometric comparisons
+	float mEpsilon;
+
+	/// if we should use breath first priority for the splits
+	int mNodePriorityQueueType;
+
+	// priority queue strategy
+	enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED};
+
+
+	/// subdivision stats output file
+	ofstream  mSubdivisionStats;
+	/// keeps track of cost during subdivision
+	float mTotalCost;
+	/// keeps track of overall pvs size during subdivision
+	int mTotalPvsSize;
 	/// 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:
 
