// ================================================================
// $Id$
// ****************************************************************
// 
// Initial coding by
/**
   @author Jiri Bittner
*/

#ifndef __RSSTREE_H__
#define __RSSTREE_H__

// Standard headers
#include <iomanip>
#include <vector>
#include <functional>
#include <stack>


// User headers
#include "VssRay.h"
#include "AxisAlignedBox3.h"
#include "Halton.h"
#include "Beam.h"
#include "Statistics.h"
#include "Ray.h"

#include "Containers.h"
#include "SamplingStrategy.h"

namespace GtpVisibilityPreprocessor {

#define USE_KDNODE_VECTORS 1
#define _RSS_STATISTICS
#define _RSS_TRAVERSAL_STATISTICS


// --------------------------------------------------------------
// Static statistics for kd-tree search
// --------------------------------------------------------------
class RssStatistics :
  public StatisticsBase
{
public:  
  // total number of nodes
  int nodes;
  // number of leaves
  int leaves;
  // number of splits along each of the axes
  int splits[7];
  // totals number of rays
  int rays;
  // initial size of the pvs
  int initialPvsSize;
  // total number of query domains
  int queryDomains;
  // total number of ray references
  int rayRefs;

  // max depth nodes
  int maxDepthNodes;
  // max depth nodes
  int minPvsNodes;
  int minRaysNodes;
  // max ray contribution nodes
  int maxRayContribNodes;
  // max depth nodes
  int minSizeNodes;
  int maxCostRatioNodes;

  // max number of rays per node
  int maxRayRefs;
  // number of dynamically added ray refs
  int addedRayRefs;
  // number of dynamically removed ray refs
  int removedRayRefs;



  // dynamically updated values
  float avgPvsSize;
  float avgRays;
  float avgRayContribution;
  float avgPvsEntropy;
  float avgRayLengthEntropy;
  float avgImportance;

  float avgWeightedRayContribution;

  // Constructor
  RssStatistics() {
    Reset();
  }

  int Nodes() const {return nodes;}
  int Interior() const { return nodes/2; }
  int Leaves() const { return Nodes() - Interior(); }

  void Reset() {
    nodes = 0;
    for (int i=0; i<7; i++)
      splits[i] = 0;
    rays = queryDomains = 0;
    rayRefs = 0;
    maxDepthNodes = 0;
    minPvsNodes = 0;
    minRaysNodes = 0;
    maxRayRefs = 0;
    addedRayRefs = removedRayRefs = 0;
	initialPvsSize = 0;
	maxRayContribNodes = 0;
	minSizeNodes = 0;
	maxCostRatioNodes = 0;
  }

  
  void
  Print(ostream &app) const;

  friend ostream &operator<<(ostream &s, const RssStatistics &stat) {
    stat.Print(s);
    return s;
  }
  
};




class RssTreeInterior;


// --------------------------------------------------------------
// KD-tree node - abstract class
// --------------------------------------------------------------
class RssTreeNode
{
public:


  struct RayInfo
  {
	// pointer to the actual ray
	VssRay *mRay;
	
	RayInfo():mRay(NULL) {}
	
	RayInfo(VssRay *r):mRay(r)
	{}
	
	enum {
	  SOURCE_RAY = 0,
	  TERMINATION_RAY,
	  PASSING_RAY,
	  CONTAINED_RAY
	};
	
	int GetRayClass() const {
	  return SOURCE_RAY;
	}
	
	friend bool operator<(const RayInfo &a, const RayInfo &b) {
	  return a.mRay < b.mRay;
	}

	
#define USE_ORIGIN 1
	
	Vector3 GetOrigin() const {
#if USE_ORIGIN
	  return mRay->GetOrigin();
#else
	  return mRay->GetTermination();
#endif
	}

	Vector3 GetTermination() const {
#if USE_ORIGIN
	  return mRay->GetTermination();
#else
	  return mRay->GetOrigin();
#endif
	}

	float GetOrigin(const int axis) const {
#if USE_ORIGIN
	  return mRay->GetOrigin(axis);
#else
	  return mRay->GetTermination(axis);
#endif
	}

	Vector3 GetDir() const {
#if USE_ORIGIN
	  return mRay->GetDir();
#else
	  return -mRay->GetDir();
#endif
	}

	float GetDirParametrization(const int axis) const {
#if USE_ORIGIN
	  return mRay->GetDirParametrization(axis);
#else
	  return mRay->GetOpositeDirParametrization(axis);
#endif
	}

	
// 	Vector3 GetTermination() const {
// 	  return mRay->GetOrigin();
// 	}
	
// 	float GetTermination(const int axis) const {
// 	  return mRay->GetTermination(axis);
// 	}

	Intersectable *GetObject() const {
#if USE_ORIGIN
	  return mRay->mTerminationObject;
#else
	  return mRay->mOriginObject;
#endif
	}
	
	Intersectable *GetSourceObject() const {
#if USE_ORIGIN
	  return mRay->mOriginObject;
#else
	  return mRay->mTerminationObject;
#endif
	}

	//	Vector3 Extrap(const float t) const {
	//	  return mRay->Extrap(t);
	//	}
	
	int
	ComputeRaySide(const int axis,
				   const float position
				   ) const {
	  
	  // only compare the side of the origin
	  float rpos = (axis < 3) ? GetOrigin(axis) : GetDirParametrization(axis - 3);
	  return (rpos <= position) ? -1 : 1;
	}

	static bool GreaterWeightedPvsContribution(const RayInfo &a,
											   const RayInfo &b) {
	  return a.mRay->mWeightedPvsContribution > b.mRay->mWeightedPvsContribution;
	}

	static float Distance(const RayInfo &a,
						 const RayInfo &b)
	{
	  if (a.mRay->mTerminationObject == b.mRay->mTerminationObject)
		return MAX_FLOAT;
	  
	  return Min(a.mRay->SqrDistance(b.GetTermination()),
				 b.mRay->SqrDistance(a.GetTermination()));
	}

	
	static float SqrDistance5D(const RayInfo &a,
							   const RayInfo &b,
							   const Vector3 &spatialDerivative,
							   const Vector3 &directionalDerivative
							   )
	{
	  Vector3 spatialDiff = b.GetOrigin() - a.GetOrigin();
	  Vector3 directionalDiff = b.GetDir() - a.GetDir();
	  
	  return DotProd(spatialDiff, spatialDerivative) +
		DotProd(directionalDiff, directionalDerivative);
	}

	
  };

  struct SilhouetteRays {
	RayInfo *a;
	RayInfo *b;
	SilhouetteRays() {}
	SilhouetteRays(RayInfo *_a, RayInfo *_b):a(_a), b(_b) {
	}
  };
  
  typedef vector<RayInfo> RayInfoContainer;
	
  enum { EInterior, ELeaf };

  /////////////////////////////////
  // The actual data goes here
  
  // link to the parent
  RssTreeInterior *parent;

  enum {SPLIT_X=0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ};
  
  // splitting axis
  char axis;
	
  // depth
  unsigned char depth;
  
  //  short depth;
  //
  /////////////////////////////////
  

  // the bbox of the node
  AxisAlignedBox3 bbox;
  
  // the bbox of the node
  AxisAlignedBox3 dirBBox;

  // evaluated importance of this node
  float mImportance;

  // importance requires update
  //bool mRequiresUpdate;

  inline RssTreeNode(RssTreeInterior *p);

  
  virtual ~RssTreeNode() {};
  virtual int Type() const  = 0;
  

  bool IsLeaf() const { return axis == -1; }
  
  virtual void Print(ostream &s) const = 0;

  virtual int GetAccessTime() {
    return 0x7FFFFFF;
  }

  float GetImportance() const;

	
};

// --------------------------------------------------------------
// KD-tree node - interior node
// --------------------------------------------------------------
class RssTreeInterior :
  public RssTreeNode
{
public:
  // plane in world coordinates
  float position;

  // pointers to children
  RssTreeNode *back, *front;


  // data for caching
  long accesses;
  long lastAccessTime;
  
  RssTreeInterior(RssTreeInterior *p):RssTreeNode(p),
									  back(NULL),
									  front(NULL),
									  accesses(0),
									  lastAccessTime(-1)
  { }

  virtual int GetAccessTime() {
    return lastAccessTime;
  }

  float GetRelativePosition() const {
	if (axis < 3)
	  return (position - bbox.Min(axis))/bbox.Size(axis);
	else
	  return (position - dirBBox.Min(axis-3))/dirBBox.Size(axis-3);
  }

  void SetupChildLinks(RssTreeNode *b, RssTreeNode *f) {
    back = b;
    front = f;
    b->parent = f->parent = this;
  }

  void ReplaceChildLink(RssTreeNode *oldChild, RssTreeNode *newChild) {
    if (back == oldChild)
      back = newChild;
    else
      front = newChild;
  }

  virtual int Type() const  { return EInterior; }
  
  virtual ~RssTreeInterior() {
    if (back)
      delete back;
    if (front)
      delete front;
  }
  
  virtual void Print(ostream &s) const {
    if (axis == 0)
      s<<"x ";
    else
      if (axis == 1)
		s<<"y ";
      else
		s<<"z ";
    s<<position<<" ";
    back->Print(s);
    front->Print(s);
  }

  
	
  int ComputeRaySide(const
					 RayInfo &rayData
					 ) {
	return rayData.ComputeRaySide(axis, position);
  }

};


// --------------------------------------------------------------
// KD-tree node - leaf node
// --------------------------------------------------------------
class RssTreeLeaf :
  public RssTreeNode
{
private:
  int mPvsSize;
public:
  static int mailID;
  int mailbox;
  
  RayInfoContainer rays;
  int mTotalRays;
  float mTotalContribution;
  
  bool mValidPvs;
  
  Beam mBeam;
  
  RssTreeLeaf(RssTreeInterior *p,
			  const int nRays
			  ):RssTreeNode(p), rays(), mPvsSize(0), mTotalRays(0),
				mTotalContribution(0.0f), mValidPvs(false) {
    rays.reserve(nRays);
  }
  
  virtual ~RssTreeLeaf() { }

  virtual int Type() const  { return ELeaf; }

  virtual void Print(ostream &s) const {
    s<<
	  "L: rays="<<(int)rays.size()<<
	  " pvs="<<mPvsSize<<" importance="<<mImportance<<endl;
  };
  
  void AddRay(const RayInfo &data) {
	mValidPvs = false;
	rays.push_back(data);
	mTotalRays++;
	mTotalContribution +=
	  ABS_CONTRIBUTION_WEIGHT*data.mRay->mPvsContribution +
	  (1.0f - ABS_CONTRIBUTION_WEIGHT)*data.mRay->mRelativePvsContribution;
	data.mRay->Ref();
  }
	
  int GetPvsSize() const {
	return mPvsSize;
  }

  void SetPvsSize(const int s) {
	mPvsSize = s;
	mValidPvs = true;
  }


  float
  ComputePvsEntropy() const;
  
  float
  ComputeRayLengthEntropy() const;
  
  float
  ComputeRayTerminationEntropy() const;
  

  float
  ComputeEntropyImportance() const;
  
  float
  ComputeRayContributionImportance() const;

  void Mail() { mailbox = mailID; }
  static void NewMail() { mailID++; }
  bool Mailed() const { return mailbox == mailID; }
  
  bool Mailed(const int mail) {
    return mailbox >= mailID + mail;
  }

  float GetAvgRayContribution() const {
	return GetPvsSize()/((float)rays.size() + Limits::Small);
  }

  
  float GetSqrRayContribution() const {
	return sqr(GetPvsSize()/((float)rays.size() + Limits::Small));
  }
  
  // comparator for the 
  struct less_contribution : public
  binary_function<const RssTreeLeaf *, const RssTreeLeaf *, bool> {
	
	bool operator()(const RssTreeLeaf * a, const RssTreeLeaf *b) {
	  return a->GetAvgRayContribution() < b->GetAvgRayContribution();
	}
  };
  
  struct greater_contribution : public
  binary_function<const RssTreeLeaf *, const RssTreeLeaf *, bool> {
	
	bool operator()(const RssTreeLeaf * a, const RssTreeLeaf *b) {
	  return a->GetAvgRayContribution() > b->GetAvgRayContribution();
	}
  };
  
  friend bool GreaterContribution(const RssTreeLeaf * a, const RssTreeLeaf *b) {
	return a->GetAvgRayContribution() > b->GetAvgRayContribution();
  }

  
};

// Inline functions
inline
RssTreeNode::RssTreeNode(RssTreeInterior *p):
  parent(p), axis(-1), depth(p ? p->depth + 1 : 0) {}



// ---------------------------------------------------------------
// Main LSDS search class
// ---------------------------------------------------------------
class RssTree
{
  struct TraversalData
  {  
    RssTreeNode *node;
    AxisAlignedBox3 bbox;
    int depth;
    float priority;
    
    TraversalData() {}

    TraversalData(RssTreeNode *n, const float p):
      node(n), priority(p)
    {}

    TraversalData(RssTreeNode *n,
				  const AxisAlignedBox3 &b,
				  const int d):
      node(n), bbox(b), depth(d) {}
    
		
    // comparator for the 
    struct less_priority : public
    binary_function<const TraversalData, const TraversalData, bool> {
			
      bool operator()(const TraversalData a, const TraversalData b) {
		return a.priority < b.priority;
      }
      
    };

    //    ~TraversalData() {}
    //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
    
    friend bool operator<(const TraversalData &a,
						  const TraversalData &b) {
      //      return a.node->queries.size() < b.node->queries.size();
      RssTreeLeaf *leafa = (RssTreeLeaf *) a.node;
      RssTreeLeaf *leafb = (RssTreeLeaf *) b.node;
#if 0
	  return
		leafa->rays.size()*a.bbox.GetVolume()
		<
		leafb->rays.size()*b.bbox.GetVolume();
#endif
#if 0
	  return
		leafa->GetPvsSize()*a.bbox.GetVolume()
		<
		leafb->GetPvsSize()*b.bbox.GetVolume();
#endif
#if 0
	  return
		leafa->GetPvsSize()
		<
		leafb->GetPvsSize();
#endif
#if 0
	  return
		leafa->GetPvsSize()/(leafa->rays.size()+1)
		>
		leafb->GetPvsSize()/(leafb->rays.size()+1);
#endif
#if 1
	  return
		leafa->GetPvsSize()*leafa->rays.size()
		<
		leafb->GetPvsSize()*leafb->rays.size();
#endif
    }
  };
  
  // simplified data for ray traversal only...

  struct RayTraversalData {
    
    RssTreeNode::RayInfo rayData;
    RssTreeNode *node;
    
    RayTraversalData() {}
    RayTraversalData(RssTreeNode *n,
					 const RssTreeNode::RayInfo &data):
      rayData(data), node(n) {}
  };
	
public:
  /////////////////////////////
  // The core pointer
  vector<RssTreeNode *> mRoots;
  
  
  HaltonSequence mHalton;
  

  /////////////////////////////
  // Basic properties

  // total number of nodes of the tree
  int nodes;

  // axis aligned bounding box of the scene
  AxisAlignedBox3 bbox;

  // axis aligned bounding box of directions
  AxisAlignedBox3 dirBBox;

  // forced bounding box for from viewcell visibility
  //  AxisAlignedBox3 *mForcedBoundingBox;

  /////////////////////////////
  // Construction parameters

  // epsilon used for the construction
  float epsilon;

  // ratio between traversal and intersection costs
  float ct_div_ci;
  // max depth of the tree
  int termMaxDepth;
  // minimal ratio of the volume of the cell and the query volume
  float termMinSize;

  // minimal pvs per node to still get subdivided
  int termMinPvs;

  // minimal ray number per node to still get subdivided
  int termMinRays;
	
  // maximal cost ration to subdivide a node
  float termMaxCostRatio;
	
  // maximal contribution per ray to subdivide the node
  float termMaxRayContribution;

  // randomized construction
  bool randomize;

  // use a root per object in the tree
  bool mPerObjectTree;
  
  // type of the splitting to use fo rthe tree construction
  enum {ESplitRegular, ESplitHeuristic, ESplitHybrid };
  int splitType;

  bool mSplitUseOnlyDrivingAxis;
  

  // interleave directional and spatial splits based on their costs
  // if false directional splits are only performed after spatial splits
  bool mInterleaveDirSplits;

  // depth at which directional splits are performed if mInterleaveDirSplits is false
  int mDirSplitDepth;

  // depth till which the regular splits are applied for hybrid split type
  int mHybridDepth;
  
  // maximal number of rays maintained in the rss tree
  int mMaxRays;
  
  // maximal size of the box on which the refdir splitting can be performed
  // (relative to the scene bbox
  float refDirBoxMaxSize;
  
  // maximum alovable memory in MB
  float maxTotalMemory;

  // maximum alovable memory for static kd tree in MB
  float maxStaticMemory;

  // this is used during the construction depending
  // on the type of the tree and queries...
  float maxMemory;


  // minimal acess time for collapse
  int accessTimeThreshold;

  // minimal depth at which to perform collapse
  int minCollapseDepth;

  bool mImportanceBasedCost;

  // sampling pass
  int mCurrentPass;
  
  // reusable array of split candidates
  vector<SortableEntry> *splitCandidates;
  /////////////////////////////

  RssStatistics stat;
	
  
  RssTree();
  virtual ~RssTree();

  virtual void
  Construct(
			ObjectContainer &objects,
			VssRayContainer &rays
			//			AxisAlignedBox3 *forcedBoundingBox = NULL
			);
	
  // incemental construction
  virtual void UpdateRays(VssRayContainer &remove,
						  VssRayContainer &add
						  );

  virtual void AddRays(
					   VssRayContainer &add
					   )
  {
	VssRayContainer remove;
	UpdateRays(remove, add);
  }

  
	
  RssTreeNode *
  Locate(const Vector3 &v);
	
  RssTreeNode *
  SubdivideNode(RssTreeLeaf *leaf,
				const AxisAlignedBox3 &box,
				AxisAlignedBox3 &backBox,
				AxisAlignedBox3 &frontBox
				);
	
  RssTreeNode *
  Subdivide(const TraversalData &tdata);
	

  void
  SortSubdivisionCandidates(
					  RssTreeLeaf *node,
					  const int axis
					  );
	
  
  // return memory usage in MB
  float GetMemUsage() const {
    return 
      (sizeof(RssTree) +
       stat.Leaves()*sizeof(RssTreeLeaf) +
       stat.Interior()*sizeof(RssTreeInterior) +
       stat.rayRefs*sizeof(RssTreeNode::RayInfo))/(1024.0f*1024.0f);
  }
	
  float GetRayMemUsage() const {
    return 
      stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f);
  }
  
  struct SplitInfo {
	
	int axis;
	float position;
	float costRatio;
	
	int rays;
	int raysBack;
	int raysFront;

	int pvs;
	int pvsBack;
	int pvsFront;

	float contribution;
	float contributionBack;
	float contributionFront;

	int viewCells;
	int viewCellsBack;
	int viewCellsFront;

	float volume;
	float volumeBack;
	float volumeFront;
	
  };
  
  void
  BestCostRatio(
				RssTreeLeaf *node,
				SplitInfo &info
// 				int &axis,
// 				float &position,
// 				int &raysBack,
// 				int &raysFront,
// 				int &pvsBack,
// 				int &pvsFront
				);
	
  
  void
  EvalCostRatio(
				RssTreeLeaf *node,
				SplitInfo &info
// 				const int axis,
// 				const float position,
// 				int &raysBack,
// 				int &raysFront,
// 				int &pvsBack,
// 				int &pvsFront
				);

  void
  EvalCostRatioHeuristic(
						 RssTreeLeaf *node,
						 SplitInfo &info
// 						 const int axis,
// 						 float &position,
// 						 int &raysBack,
// 						 int &raysFront,
// 						 int &pvsBack,
// 						 int &pvsFront
						 );

  int
  SelectPlane(RssTreeLeaf *leaf,
			  const AxisAlignedBox3 &box,
			  SplitInfo &info
			  );
  
  void
  GetCostRatio(
			   RssTreeLeaf *leaf,
			   SplitInfo &info
			   // 			   const int axis,
			   // 			   const float position,
			   // 			   const int raysBack,
			   // 			   const int raysFront,
			   // 			   const int pvsBack,
			   // 			   const int pvsFront
			   );
  
  AxisAlignedBox3 GetBBox(const RssTreeNode *node) const {
	return node->bbox;

//     if (node->parent == NULL)
//       return bbox;

//     if (!node->IsLeaf())
//       return ((RssTreeInterior *)node)->bbox;

//     if (node->parent->axis >= 3)
//       return node->parent->bbox;
      
//     AxisAlignedBox3 box(node->parent->bbox);
//     if (node->parent->front == node)
//       box.SetMin(node->parent->axis, node->parent->position);
//     else
//       box.SetMax(node->parent->axis, node->parent->position);
//     return box;
  }

  AxisAlignedBox3 GetShrankedBBox(const RssTreeNode *node) const;

  AxisAlignedBox3 GetDirBBox(const RssTreeNode *node) const {
	return node->dirBBox;
//     if (node->parent == NULL)
//       return dirBBox;
    
//     if (!node->IsLeaf() )
//       return ((RssTreeInterior *)node)->dirBBox;

//     if (node->parent->axis < 3)
//       return node->parent->dirBBox;
    
//     AxisAlignedBox3 dBBox(node->parent->dirBBox);

//     if (node->parent->front == node)
//       dBBox.SetMin(node->parent->axis - 3, node->parent->position);
//     else
//       dBBox.SetMax(node->parent->axis - 3, node->parent->position);
//     return dBBox;
  }
  
  int
  ReleaseMemory(const int time);

  int
  CollapseSubtree(RssTreeNode *node, const int time);

  void
  CountAccess(RssTreeInterior *node, const long time) {
    node->accesses++;
    node->lastAccessTime = time;
  }

  RssTreeNode *
  SubdivideLeaf(
				RssTreeLeaf *leaf
				);

  void
  RemoveRay(VssRay *ray,
			vector<RssTreeLeaf *> *affectedLeaves,
			const bool removeAllScheduledRays
			);

  //  void
  //  AddRay(VssRay *ray);
  void
  AddRay(RssTreeNode::RayInfo &info);
  
  void
  TraverseInternalNode(
					   RayTraversalData &data,
					   stack<RayTraversalData> &tstack);

  void
  EvaluateLeafStats(const TraversalData &data);


  int
  GetRootPvsSize() const {
	return GetPvsSize(bbox);
  }
  
  int
  GetPvsSize(const AxisAlignedBox3 &box) const;

  int
  CollectPvs(const AxisAlignedBox3 &box,
			 ObjectContainer &pvs
			 ) const;

  int
  CollectRootPvs(
				 ObjectContainer &pvs
				 ) const
  {
	return CollectPvs(bbox, pvs);
  }
  
	
  void
  UpdateTreeStatistics();


  int
  GenerateRays(const float ratioPerLeaf,
			   SimpleRayContainer &rays);

  int
  GenerateRays(const int numberOfRays,
			   const int numberOfLeaves,
			   SimpleRayContainer &rays);
		
  float
  GetAvgPvsSize();

  int
  UpdateSubdivision();

  bool
  TerminationCriteriaSatisfied(RssTreeLeaf *leaf);

  void
  CollectLeaves(vector<RssTreeLeaf *> &leaves);

  bool
  ClipRay(
		  RssTreeNode::RayInfo &rayInfo,
		  const AxisAlignedBox3 &box
		  );

  RssTreeNode *GetRoot(Intersectable *object = NULL) const;

  bool
  ValidLeaf(RssTreeLeaf *leaf) const;

  void
  GenerateLeafRays(RssTreeLeaf *leaf,
				   const int numberOfRays,
				   SimpleRayContainer &rays);

  void
  GenerateLeafRaysSimple(RssTreeLeaf *leaf,
						 const int numberOfRays,
						 SimpleRayContainer &rays);
	

  void
  PickEdgeRays(RssTreeLeaf *leaf,
			   int &r1,
			   int &r2
			   );

  int
  CollectRays(VssRayContainer &rays,
			  const int number);

  int
  CollectRays(VssRayContainer &rays
			  );

  void
  UpdatePvsSize(RssTreeLeaf *leaf);

  void
  ComputeImportance(RssTreeLeaf *leaf);
  
  void
  SetPass(const int p) {
	mCurrentPass = p;
  }
  
  void GetRayContribution(const RssTreeNode::RayInfo &info,
						  float &weight,
						  float &contribution);

  float
  GetSampleWeight(const int pass);

  int
  RemoveInteriorRays(
					 RssTreeLeaf *leaf
					 );

  bool
  IsRayConvexCombination(const RssTreeNode::RayInfo &ray,
						 const RssTreeNode::RayInfo &r1,
						 const RssTreeNode::RayInfo &r2,
						 const RssTreeNode::RayInfo &r3);

  int
  PruneRaysRandom(RssTreeLeaf *leaf,
				  const float ratio);

  int
  PruneRaysContribution(RssTreeLeaf *leaf,
						const float ratio);

  int
  PruneRays(
			const int desired
			);
  

  void
  FindSilhouetteRays(RssTreeLeaf *leaf,
					 vector<RssTreeLeaf::SilhouetteRays> &rays
					 );

  void
  PushRoots(priority_queue<TraversalData> &stack) const;

  void
  PushRoots(stack<RssTreeNode *> &st) const;

  void
  PushRoots(stack<RayTraversalData> &st, RssTreeNode::RayInfo &info) const;

  void
  UpdateImportance(
				   RssTreeNode *node);

  void
  GenerateRay(float *params, SimpleRayContainer &rays);

  void
  GenerateLeafRay(
				  float *params,
				  SimpleRayContainer &rays,
				  const AxisAlignedBox3 &box,
				  const AxisAlignedBox3 &dirBBox
				  );
	
};


class RssBasedDistribution: public SamplingStrategy
{
 public:
  HaltonSequence mHalton;
  RssTree *mRssTree;
  // id of sampling pass (a pass is defined by two consecutive updates)
  int mPass;

  RssBasedDistribution(Preprocessor &preprocessor):
	SamplingStrategy(preprocessor){
	mType = RSS_BASED_DISTRIBUTION;
	mRssTree = NULL;
	mPass = 0;
  }
  
  virtual void Update(VssRayContainer &vssRays);
  virtual bool RequiresRays() { return true; }
  
private:

  virtual bool GenerateSample(SimpleRay &ray);
  
};


};

#endif // __RSSTREE_H__