Index: GTP/trunk/Lib/Vis/Preprocessing/scripts/generate_viewcells.sh
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/scripts/generate_viewcells.sh	(revision 2072)
+++ GTP/trunk/Lib/Vis/Preprocessing/scripts/generate_viewcells.sh	(revision 2073)
Index: GTP/trunk/Lib/Vis/Preprocessing/scripts/generate_viewcells.env
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/scripts/generate_viewcells.env	(revision 2072)
+++ GTP/trunk/Lib/Vis/Preprocessing/scripts/generate_viewcells.env	(revision 2073)
@@ -165,6 +165,6 @@
 	}
 
-	showVisualization true
-	#showVisualization false
+	#showVisualization true
+	showVisualization false
 	evaluateViewCells false
 	
@@ -247,5 +247,5 @@
 	Construction {
 
-		samples 2000000
+		samples 1500000
 
 		# type 0 = sequential computation, 1 = interleaved, 2 = gradient
Index: GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.vcproj
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.vcproj	(revision 2069)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.vcproj	(revision 2073)
@@ -854,4 +854,10 @@
 			</File>
 			<File
+				RelativePath=".\TraversalTree.cpp">
+			</File>
+			<File
+				RelativePath=".\TraversalTree.h">
+			</File>
+			<File
 				RelativePath="..\src\Triangle3.cpp">
 			</File>
Index: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h	(revision 2003)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h	(revision 2073)
@@ -511,4 +511,5 @@
 								   AxisAlignedBox3 *forcedViewSpace);
 
+	void CreateTraversalTree();
 
 	///////////////////////////
Index: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h	(revision 2015)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h	(revision 2073)
@@ -723,7 +723,5 @@
 	VspNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);
 
-	bool LineSegmentIntersects(const Vector3 &origin, 
-							   const Vector3 &termination, 
-							   ViewCell *viewCell);
+
 protected:
 
Index: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp	(revision 2072)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp	(revision 2073)
@@ -6565,6 +6565,5 @@
 												   ViewCell *viewCell)
 {
-	return mHierarchyManager->
-		GetVspTree()->LineSegmentIntersects(origin, termination, viewCell);
+	return false;
 }
 
Index: GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.h
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.h	(revision 2073)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.h	(revision 2073)
@@ -0,0 +1,630 @@
+#ifndef _TraversalTree_H__
+#define _TraversalTree_H__
+
+#include <functional>
+using namespace std;
+
+#include "Containers.h"
+#include "AxisAlignedBox3.h"
+#include "Ray.h"
+#include "Pvs.h"
+#include "Viewcell.h"
+#include "VssRay.h"
+#include "IntersectableWrapper.h"
+
+
+namespace GtpVisibilityPreprocessor {
+
+  
+  class TraversalNode;
+  class TraversalLeaf;
+  class TraversalInterior;
+  class Intersectable;
+  class Beam;
+
+  class TraversalTree;
+  
+  //  TraversalTree *SceneTraversalTree;
+
+// --------------------------------------------------------------
+// Static statistics for kd-tree search
+// --------------------------------------------------------------
+class TraversalTreeStatistics 
+{
+public:  
+  // total number of nodes
+  int nodes;
+  // number of splits along each of the axes
+  int splits[7];
+  // totals number of rays
+  int rays;
+  // total number of query domains
+  int queryDomains;
+  // total number of ray references
+  int rayRefs;
+  // refs in non empty leafs
+  int rayRefsNonZeroQuery;
+  // total number of query references
+  int objectRefs;
+  // nodes with zero queries
+  int zeroQueryNodes;
+  // max depth nodes
+  int maxDepthNodes;
+  // max depth nodes
+  int minCostNodes;
+  // max number of rays per node
+  int maxObjectRefs;
+  // number of dynamically added ray refs
+  int addedRayRefs;
+  // number of dynamically removed ray refs
+  int removedRayRefs;
+  
+  // Constructor
+  TraversalTreeStatistics() {
+    Reset();
+  }
+
+  int Nodes() const {return nodes;}
+  int Interior() const { return nodes / 2; }
+  int Leaves() const { return (nodes / 2) + 1; }
+
+  void Reset() {
+    nodes = 0;
+    for (int i=0; i<7; i++)
+      splits[i] = 0;
+    rays = queryDomains = 0;
+    rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
+    zeroQueryNodes = 0;
+    maxDepthNodes = 0;
+    minCostNodes = 0;
+    maxObjectRefs = 0;
+    addedRayRefs = removedRayRefs = 0;
+  }
+
+  void
+  Print(ostream &app) const;
+
+  friend ostream &operator<<(ostream &s, const TraversalTreeStatistics &stat) {
+    stat.Print(s);
+    return s;
+  }
+  
+};
+
+  
+class TraversalInterior;
+/** Abstract class for kd-tree node */
+class TraversalNode {
+public:
+  
+  static int sMailId;
+  static int sReservedMailboxes;
+  int mMailbox;
+
+  KdIntersectable *mIntersectable;
+  
+  void Mail() { mMailbox = sMailId; }
+  //static void NewMail() { sMailId ++; }
+  bool Mailed() const { return mMailbox == sMailId; }
+ 
+  static void NewMail(const int reserve = 1) {
+		sMailId += sReservedMailboxes;
+		sReservedMailboxes = reserve;
+	}
+	void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
+	bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
+
+  virtual ~TraversalNode(){};
+  TraversalNode(TraversalInterior *parent);
+
+  /** Determines whether this node is a leaf or interior node
+      @return true if leaf
+  */
+  virtual bool IsLeaf() const = 0;
+
+  /** Determines whether this node is the root of the tree
+      @return true if root
+  */
+  virtual bool IsRoot() const {
+    return mParent == NULL;
+  }
+
+  /** Parent of the node - the parent is a little overhead for maintanance of the tree,
+      but allows various optimizations of tree traversal algorithms */
+  TraversalInterior *mParent;
+  short mDepth;
+  short mPvsTermination;
+};
+
+/** Implementation of the kd-tree interior node */
+class TraversalInterior : public TraversalNode {
+
+public:
+    
+  TraversalInterior(TraversalInterior *parent):TraversalNode(parent), mBack(NULL), mFront(NULL) {}
+
+  ~TraversalInterior();
+
+  /** \sa TraversalNode::IsLeaf() */
+  virtual bool IsLeaf() const { return false; }
+
+  /** splitting axis */
+  int mAxis;
+  /** splitting position, absolute position within the bounding box of this node */
+  float mPosition;
+  /** bounding box of interior node */
+  AxisAlignedBox3 mBox;
+
+  /** back node */
+  TraversalNode *mBack;
+  /** front node */
+  TraversalNode *mFront;
+
+  void SetupChildLinks(TraversalNode *b, TraversalNode *f) {
+    mBack = b;
+    mFront = f;
+    b->mParent = f->mParent = this;
+  }
+  
+  void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild) {
+    if (mBack == oldChild)
+      mBack = newChild;
+    else
+      mFront = newChild;
+  }
+  
+  
+};
+  
+class SubdivisionCandidate;
+  
+/** Implementation of the kd-tree leaf node */
+class TraversalLeaf : public TraversalNode {
+public:
+  TraversalLeaf(TraversalInterior *parent, const int objects):
+	  TraversalNode(parent), mViewCell(NULL) {
+    mObjects.reserve(objects);
+  }
+  
+  void AddPassingRay(const Ray &ray, const int contributions) {
+    mPassingRays.AddRay(ray, contributions);
+		//		Debug << "adding passing ray" << endl;
+  }
+
+  ~TraversalLeaf();
+	
+	void AddPassingRay2(const Ray &ray,
+						const int objects,
+						const int viewcells
+						) {
+    mPassingRays.AddRay2(ray, objects, viewcells);
+		//		Debug << "adding passing ray" << endl;
+  }
+
+  /** \sa TraversalNode::IsLeaf() */
+  virtual bool IsLeaf() const { return true; }
+
+
+  /** pointers to occluders contained in this node */
+  ObjectContainer mObjects;
+
+  /** Ray set description of the rays passing through this node */
+  PassingRaySet mPassingRays;
+	
+  /** PVS consisting of visible TraversalTree nodes */
+  KdPvs mKdPvs;
+
+  /// pvs of view cells seeing this node.
+  SubdivisionCandidate *mSubdivisionCandidate;
+
+  /// pointer to view cell.
+  KdViewCell *mViewCell;
+
+  VssRayContainer mVssRays;
+
+   /// Objects that are referenced in more than one leaf.
+  ObjectContainer mMultipleObjects;
+
+  /// universal counter
+  int mCounter;
+};
+
+
+/** TraversalTree for indexing scene entities - occluders/occludees/viewcells */
+class TraversalTree {
+  
+protected:
+  struct TraversalData
+  {  
+    TraversalNode *mNode;
+    AxisAlignedBox3 mBox;
+    int mDepth;
+    float mPriority;
+    
+    TraversalData() {}
+
+    TraversalData(TraversalNode *n, const float p):
+      mNode(n), mPriority(p)
+    {}
+    
+    TraversalData(TraversalNode *n,
+		   const AxisAlignedBox3 &b,
+		   const int d):
+      mNode(n), mBox(b), mDepth(d) {}
+    
+
+    bool operator<(
+				   const TraversalData &b) const {
+      TraversalLeaf *leafa = (TraversalLeaf *) mNode;
+      TraversalLeaf *leafb = (TraversalLeaf *) b.mNode;
+      return 
+		leafa->mObjects.size()*mBox.SurfaceArea()
+		<
+		leafb->mObjects.size()*b.mBox.SurfaceArea();
+    }
+
+
+    // comparator for the 
+    struct less_priority : public
+    binary_function<const TraversalData, const TraversalData, bool> {
+      
+      bool operator()(const TraversalData a, const TraversalData b) {
+				return a.mPriority < b.mPriority;
+      }
+      
+    };
+
+  };
+
+  
+
+public:
+
+  enum {SPLIT_OBJECT_MEDIAN,
+	SPLIT_SPATIAL_MEDIAN,
+	SPLIT_SAH};
+  
+  TraversalTree();
+
+  ~TraversalTree();
+    
+  /** Insert view cell into the tree */
+  virtual void InsertViewCell(ViewCell *viewCell) {
+    //      mRoot->mViewcells.push_back(viewCell);
+  }
+
+  virtual bool Construct();
+
+  /** Check whether subdivision criteria are met for the given subtree.
+      If not subdivide the leafs of the subtree. The criteria are specified in
+      the environment as well as the subdivision method. By default surface area
+      heuristics is used.
+	
+      @param subtree root of the subtree
+
+      @return true if subdivision was performed, false if subdivision criteria
+      were already met
+  */
+  virtual TraversalNode *Subdivide(const TraversalData &tdata);
+
+  /** Get the root of the tree */
+  TraversalNode *GetRoot() const {
+    return mRoot;
+  }
+
+
+  AxisAlignedBox3 GetBox() const { return mBox; }
+
+  int
+  CastRay(
+		  Ray &ray
+		  );
+  
+
+  int
+  CastBeam(
+		   Beam &beam
+		   );
+  
+  
+  /** Casts line segment into tree.
+	  @returns intersected view cells.
+  */
+  int CastLineSegment(const Vector3 &origin,
+					  const Vector3 &termination,
+					  vector<ViewCell *> &viewcells);
+
+
+  const TraversalTreeStatistics &GetStatistics() const {
+    return mStat;
+  }
+
+  /** Returns or creates a new intersectable for use in a kd based pvs.
+	  The OspTree is responsible for destruction of the intersectable.
+  */
+  KdIntersectable *GetOrCreateKdIntersectable(TraversalNode *node);
+
+
+  void
+  SetPvsTerminationNodes(
+						 const float maxArea);
+  
+  TraversalNode *
+  GetPvsNode(const Vector3 &point) const;
+  
+
+  void
+  CollectKdObjects(const AxisAlignedBox3 &box,
+				   ObjectContainer &objects
+				   );
+
+  void
+  CollectObjects(TraversalNode *n, ObjectContainer &objects);
+
+  void
+  CollectObjects(const AxisAlignedBox3 &box,
+				 ObjectContainer &objects);
+
+  void
+  CollectLeaves(vector<TraversalLeaf *> &leaves);
+	
+  /** If the kd tree is used as view cell container, this
+	  methods creates the view cells.
+	  @returns the newly created view cells in a view cell container
+  */
+  void
+  CreateAndCollectViewCells(ViewCellContainer &viewCells) const;
+
+  AxisAlignedBox3 GetBox(const TraversalNode *node) const {
+    TraversalInterior *parent = node->mParent;
+    if (parent == NULL)
+      return mBox;
+    
+    if (!node->IsLeaf())
+      return ((TraversalInterior *)node)->mBox;
+    
+    AxisAlignedBox3 box(parent->mBox);
+    if (parent->mFront == node)
+      box.SetMin(parent->mAxis, parent->mPosition);
+    else
+      box.SetMax(parent->mAxis, parent->mPosition);
+    return box;
+  }
+
+  float GetSurfaceArea(const TraversalNode *node) const {
+	return GetBox(node).SurfaceArea();
+  }
+
+  
+  TraversalNode *
+  FindRandomNeighbor(TraversalNode *n,
+					 bool onlyUnmailed
+					 );
+  
+  TraversalNode *
+  TraversalTree::GetRandomLeaf(const Plane3 &halfspace);
+
+  TraversalNode *
+  GetRandomLeaf(const bool onlyUnmailed = false);
+
+
+  TraversalNode *
+  GetNode(const Vector3 &point, const float maxArea) const;
+
+  void GetBoxIntersections(const AxisAlignedBox3 &box, 
+						  vector<TraversalLeaf *> &leaves);
+
+  int
+  FindNeighbors(TraversalNode *n,
+				vector<TraversalNode *> &neighbors,
+				bool onlyUnmailed
+				);
+
+  int
+  CollectLeafPvs();
+
+  bool ExportBinTree(const string &filename);
+  bool LoadBinTree(const string &filename, ObjectContainer &object);
+
+protected:
+
+  struct RayData {
+    // pointer to the actual ray
+    Ray *ray;
+    
+    // endpoints  - do we need them?
+#if USE_FIXEDPOINT_T
+    short tmin, tmax;
+#else
+    float tmin, tmax;
+#endif
+
+    RayData():ray(NULL) {}
+    RayData(Ray *r):ray(r), tmin(0),
+
+#if USE_FIXEDPOINT_T
+#define FIXEDPOINT_ONE 0x7FFE
+			  //			  tmax(0xFFFF)
+			  tmax(FIXEDPOINT_ONE)
+#else
+      tmax(1.0f)
+#endif
+    {}
+
+    RayData(Ray *r,
+	    const float _min,
+	    const float _max
+	    ):ray(r) {
+      SetTMin(_min);
+      SetTMax(_max);
+    }
+
+    RayData(Ray *r,
+	    const short _min,
+	    const float _max
+	    ):ray(r), tmin(_min) {
+      SetTMax(_max);
+    }
+
+    RayData(Ray *r,
+	    const float _min,
+	    const short _max
+	    ):ray(r), tmax(_max) {
+      SetTMin(_min);
+    }
+
+    friend bool operator<(const RayData &a, const RayData &b) {
+      return a.ray < b.ray;
+    }
+    
+    
+    float ExtrapOrigin(const int axis) const {
+      return ray->GetLoc(axis) + GetTMin()*ray->GetDir(axis);
+    }
+    
+    float ExtrapTermination(const int axis) const {
+      return ray->GetLoc(axis) + GetTMax()*ray->GetDir(axis);
+    }
+    
+#if USE_FIXEDPOINT_T
+    float GetTMin () const { return tmin/(float)(FIXEDPOINT_ONE); }
+    float GetTMax () const { return tmax/(float)(FIXEDPOINT_ONE); }
+
+    void SetTMin (const float t) {
+      tmin = (short) (t*(float)(FIXEDPOINT_ONE));
+    }
+    
+    void SetTMax (const float t) {
+      tmax = (short) (t*(float)(FIXEDPOINT_ONE));
+      tmax++;
+      //      if (tmax!=0xFFFF)
+      //	tmax++;
+    }
+#else
+    float GetTMin () const { return tmin; }
+    float GetTMax () const { return tmax; }
+
+    void SetTMin (const float t) { tmin = t; }
+    void SetTMax (const float t) { tmax = t; }
+#endif 
+  };
+
+  struct RayTraversalData {
+    TraversalNode *mNode;
+    Vector3 mExitPoint;
+    float mMaxT;
+    
+    RayTraversalData() {}
+    RayTraversalData(TraversalNode *n,
+		     const Vector3 &p,
+		     const float maxt):
+      mNode(n), mExitPoint(p), mMaxT(maxt) {}
+  };
+
+  // --------------------------------------------------------------
+  // For sorting objects
+  // --------------------------------------------------------------
+  struct  SortableEntry
+  {
+    enum {
+      BOX_MIN,
+      BOX_MAX
+    };
+    
+    int type;
+    float value;
+    Intersectable *intersectable;
+    
+    SortableEntry() {}
+    SortableEntry(const int t, const float v, Intersectable *i):type(t),
+								value(v),
+								intersectable(i) {}
+    
+    bool operator<(const SortableEntry &b) const {
+      return value < b.value;
+    }
+    
+  };
+
+  inline static bool iltS(SortableEntry *a, SortableEntry *b)
+  {
+	  return a->value < b->value;
+  }
+
+  // reusable array of split candidates
+  vector<SortableEntry *> *splitCandidates;
+
+  float
+  BestCostRatio(
+		TraversalLeaf *node,
+		const AxisAlignedBox3 &box,
+		const int axis,
+		float &position,
+		int &objectsBack,
+		int &objectsFront
+		);
+
+  void
+  SortSubdivisionCandidates(
+		      TraversalLeaf *node,
+		      const int axis
+		      );
+
+  void
+  EvaluateLeafStats(const TraversalData &data);
+
+  TraversalNode *
+  SubdivideNode(
+		TraversalLeaf *leaf,
+		const AxisAlignedBox3 &box,
+		AxisAlignedBox3 &backBBox,
+		AxisAlignedBox3 &frontBBox
+		);
+
+  bool
+  TerminationCriteriaMet(const TraversalLeaf *leaf);
+  
+  int
+  SelectPlane(TraversalLeaf *leaf,
+	      const AxisAlignedBox3 &box,
+	      float &position
+	      );
+
+	/** does some post processing on the objects in the new child leaves.
+	*/
+	void ProcessMultipleRefs(TraversalLeaf *leaf) const;
+
+	void ExportBinLeaf(OUT_STREAM  &stream, TraversalLeaf *leaf);
+	void ExportBinInterior(OUT_STREAM &stream, TraversalInterior *interior);
+	TraversalLeaf *ImportBinLeaf(IN_STREAM &stream, TraversalInterior *parent, const ObjectContainer &objects);
+	TraversalInterior *ImportBinInterior(IN_STREAM  &stream, TraversalInterior *parent);
+	TraversalNode *LoadNextNode(IN_STREAM  &stream, TraversalInterior *parent, const ObjectContainer &objects);
+	
+	/** Adds this objects to the kd leaf objects.
+		@warning: Can corrupt the tree
+	*/
+	void InsertObjects(TraversalNode *node, const ObjectContainer &objects);
+
+  int mTermMaxNodes;
+  float mSplitBorder;
+  int mTermMaxDepth;
+  int mTermMinCost;
+  float mMaxCostRatio;
+  float mCt_div_ci;
+  int mSplitMethod;
+  bool mSahUseFaces;
+  /// root of the tree
+  TraversalNode *mRoot;
+  /// bounding box of the tree root
+  AxisAlignedBox3 mBox;
+  TraversalTreeStatistics mStat;
+public:
+  /// stores the kd node intersectables used for pvs
+  vector<KdIntersectable *> mKdIntersectables;
+  
+};
+
+
+}
+
+#endif
Index: GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.cpp
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.cpp	(revision 2073)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.cpp	(revision 2073)
@@ -0,0 +1,729 @@
+#include <stack>
+#include <algorithm>
+#include <queue>
+#include "Environment.h"
+#include "Mesh.h"
+#include "TraversalTree.h"
+#include "ViewCell.h"
+#include "Beam.h"
+
+
+// $$JB HACK
+#define KD_PVS_AREA (1e-5f)
+
+namespace GtpVisibilityPreprocessor {
+
+int TraversalNode::sMailId = 1;
+int TraversalNode::sReservedMailboxes = 1;
+
+
+inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
+{
+	return obj1->mId < obj2->mId;
+}
+
+
+TraversalNode::TraversalNode(TraversalInterior *parent):mParent(parent), mMailbox(0), mIntersectable(NULL)
+
+{
+  if (parent)
+    mDepth = parent->mDepth+1;
+  else
+    mDepth = 0;
+}
+
+
+TraversalInterior::~TraversalInterior()
+{
+	// recursivly destroy children
+	DEL_PTR(mFront);
+	DEL_PTR(mBack);
+}
+
+
+TraversalLeaf::~TraversalLeaf()
+{
+	DEL_PTR(mViewCell);  
+}
+
+
+TraversalTree::TraversalTree()
+{
+
+  
+  mRoot = new TraversalLeaf(NULL, 0);
+  Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxNodes", mTermMaxNodes);
+  Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxDepth", mTermMaxDepth);
+  Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.minCost", mTermMinCost);
+  Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.maxCostRatio", mMaxCostRatio);
+  Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.ct_div_ci", mCt_div_ci);
+  Environment::GetSingleton()->GetFloatValue("TraversalTree.splitBorder", mSplitBorder);
+
+  Environment::GetSingleton()->GetBoolValue("TraversalTree.sahUseFaces", mSahUseFaces);
+
+  char splitType[64];
+  Environment::GetSingleton()->GetStringValue("TraversalTree.splitMethod", splitType);
+  
+  mSplitMethod = SPLIT_SPATIAL_MEDIAN;
+  if (strcmp(splitType, "spatialMedian") == 0)
+    mSplitMethod = SPLIT_SPATIAL_MEDIAN;
+  else
+    if (strcmp(splitType, "objectMedian") == 0)
+      mSplitMethod = SPLIT_OBJECT_MEDIAN;
+    else
+      if (strcmp(splitType, "SAH") == 0)
+	mSplitMethod = SPLIT_SAH;
+      else {
+	cerr<<"Wrong kd split type "<<splitType<<endl;
+	exit(1);
+      }
+  splitCandidates = NULL;
+}
+
+
+TraversalTree::~TraversalTree()
+{
+    DEL_PTR(mRoot);
+
+	CLEAR_CONTAINER(mKdIntersectables);
+}
+
+
+bool
+TraversalTree::Construct()
+{
+
+  if (!splitCandidates)
+    splitCandidates = new vector<SortableEntry *>;
+
+  // first construct a leaf that will get subdivide
+  TraversalLeaf *leaf = (TraversalLeaf *) mRoot;
+
+  mStat.nodes = 1;
+
+  mBox.Initialize();
+  ObjectContainer::const_iterator mi;
+  for ( mi = leaf->mObjects.begin();
+	mi != leaf->mObjects.end();
+	mi++) {
+	//	cout<<(*mi)->GetBox()<<endl;
+	mBox.Include((*mi)->GetBox());
+  }
+
+  cout <<"TraversalTree Root Box:"<<mBox<<endl;
+  mRoot = Subdivide(TraversalData(leaf, mBox, 0));
+
+  // remove the allocated array
+  CLEAR_CONTAINER(*splitCandidates);
+  delete splitCandidates;
+
+  float area = GetBox().SurfaceArea()*KD_PVS_AREA;
+
+  SetPvsTerminationNodes(area);
+  
+  return true;
+}
+
+TraversalNode *
+TraversalTree::Subdivide(const TraversalData &tdata)
+{
+
+  TraversalNode *result = NULL;
+
+  priority_queue<TraversalData> tStack;
+  //  stack<STraversalData> tStack;
+  
+  tStack.push(tdata);
+  AxisAlignedBox3 backBox, frontBox;
+
+  while (!tStack.empty()) {
+	//	cout<<mStat.Nodes()<<" "<<mTermMaxNodes<<endl;
+	if (mStat.Nodes() > mTermMaxNodes) {
+	  //    if ( GetMemUsage() > maxMemory ) {
+      // count statistics on unprocessed leafs
+      while (!tStack.empty()) {
+		EvaluateLeafStats(tStack.top());
+		tStack.pop();
+      }
+      break;
+    }
+	  
+	
+    TraversalData data = tStack.top();
+    tStack.pop();
+    
+    TraversalNode *node = SubdivideNode((TraversalLeaf *) data.mNode,
+								 data.mBox,
+								 backBox,
+								 frontBox
+								 );
+
+	if (result == NULL)
+      result = node;
+    
+    if (!node->IsLeaf()) {
+
+      TraversalInterior *interior = (TraversalInterior *) node;
+      // push the children on the stack
+      tStack.push(TraversalData(interior->mBack, backBox, data.mDepth+1));
+      tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth+1));
+      
+    } else {
+      EvaluateLeafStats(data);
+    }
+  }
+  
+  return result;
+
+}
+
+
+bool
+TraversalTree::TerminationCriteriaMet(const TraversalLeaf *leaf)
+{
+	const bool criteriaMet =
+		((int)leaf->mObjects.size() <= mTermMinCost) ||
+		 (leaf->mDepth >= mTermMaxDepth);
+ 
+	if (criteriaMet)
+		cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl;
+
+	return criteriaMet;
+}
+
+
+int
+TraversalTree::SelectPlane(TraversalLeaf *leaf,
+					const AxisAlignedBox3 &box,
+					float &position
+					)
+{
+  int axis = -1;
+  
+  switch (mSplitMethod)
+    {
+    case SPLIT_SPATIAL_MEDIAN: {
+      axis = box.Size().DrivingAxis();
+      position = (box.Min()[axis] + box.Max()[axis])*0.5f;
+      break;
+    }
+    case SPLIT_SAH: {
+      int objectsBack, objectsFront;
+      float costRatio;
+      bool mOnlyDrivingAxis = true;
+
+	  if (mOnlyDrivingAxis) {
+		axis = box.Size().DrivingAxis();
+		costRatio = BestCostRatio(leaf,
+								  box,
+								  axis,
+								  position,
+								  objectsBack,
+								  objectsFront);
+      } else {
+		costRatio = MAX_FLOAT;
+		for (int i=0; i < 3; i++) {
+		  float p;
+		  float r = BestCostRatio(leaf,
+								  box,
+								  i,
+								  p,
+								  objectsBack,
+								  objectsFront);
+		  if (r < costRatio) {
+			costRatio = r;
+			axis = i;
+			position = p;
+		  }
+		}
+      }
+      
+      if (costRatio > mMaxCostRatio) {
+		//cout<<"Too big cost ratio "<<costRatio<<endl;
+		axis = -1;
+      }
+      break;
+    }
+    
+    }
+  return axis;
+}
+
+TraversalNode *TraversalTree::SubdivideNode(TraversalLeaf *leaf,
+											const AxisAlignedBox3 &box,
+											AxisAlignedBox3 &backBBox,
+											AxisAlignedBox3 &frontBBox
+											)
+{
+
+	if (TerminationCriteriaMet(leaf))
+		return leaf;
+
+	float position;
+
+	// select subdivision axis
+	int axis = SelectPlane( leaf, box, position );
+
+	if (axis == -1) {
+		return leaf;
+	}
+
+	mStat.nodes+=2;
+	mStat.splits[axis]++;
+
+	// add the new nodes to the tree
+	TraversalInterior *node = new TraversalInterior(leaf->mParent);
+
+	node->mAxis = axis;
+	node->mPosition = position;
+	node->mBox = box;
+
+	backBBox = box;
+	frontBBox = box;
+
+	// first count ray sides
+	int objectsBack = 0;
+	int objectsFront = 0;
+
+	backBBox.SetMax(axis, position);
+	frontBBox.SetMin(axis, position);
+
+	ObjectContainer::const_iterator mi;
+
+	for ( mi = leaf->mObjects.begin();
+		mi != leaf->mObjects.end();
+		mi++)
+	{
+		// determine the side of this ray with respect to the plane
+		AxisAlignedBox3 box = (*mi)->GetBox();
+		if (box.Max(axis) > position ) 
+			objectsFront++;
+
+		if (box.Min(axis) < position )
+			objectsBack++;
+	}
+
+
+	TraversalLeaf *back = new TraversalLeaf(node, objectsBack);
+	TraversalLeaf *front = new TraversalLeaf(node, objectsFront);
+
+
+	// replace a link from node's parent
+	if (  leaf->mParent )
+		leaf->mParent->ReplaceChildLink(leaf, node);
+
+	// and setup child links
+	node->SetupChildLinks(back, front);
+
+	for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++ mi) 
+	{
+		// determine the side of this ray with respect to the plane
+		AxisAlignedBox3 box = (*mi)->GetBox();
+
+		// matt: no more ref
+		// for handling multiple objects: keep track of references
+		//if (leaf->IsRoot()) 
+		//	(*mi)->mReferences = 1; // initialise references at root
+
+		// matt: no more ref
+		//-- (*mi)->mReferences; // remove parent ref
+
+
+		if (box.Max(axis) >= position )
+		{
+			front->mObjects.push_back(*mi);
+			//++ (*mi)->mReferences;
+		}
+
+		if (box.Min(axis) < position )
+		{
+			back->mObjects.push_back(*mi);
+			// matt: no more ref
+			//  ++ (*mi)->mReferences;
+		}
+
+		mStat.objectRefs -= (int)leaf->mObjects.size();
+		mStat.objectRefs += objectsBack + objectsFront;
+	}
+
+	// store objects referenced in more than one leaf
+	// for easy access
+	ProcessMultipleRefs(back);
+	ProcessMultipleRefs(front);
+
+	delete leaf;
+	return node;
+}
+
+
+void
+TraversalTreeStatistics::Print(ostream &app) const
+{
+  app << "===== TraversalTree statistics ===============\n";
+
+  app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+
+  app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+
+  app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz)\n";
+  for (int i=0; i<7; i++)
+    app << splits[i] <<" ";
+  app <<endl;
+
+  app << "#N_RAYREFS ( Number of rayRefs )\n" <<
+    rayRefs << "\n";
+
+  app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
+    rayRefs/(double)rays << "\n";
+
+  app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
+    rayRefs/(double)Leaves() << "\n";
+
+  app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" <<
+    maxObjectRefs << "\n";
+
+  app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
+    rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
+
+  app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
+    objectRefs/(double)Leaves() << "\n";
+
+  //  app << setprecision(4);
+
+  app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
+    zeroQueryNodes*100/(double)Leaves()<<endl;
+
+  app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
+    maxDepthNodes*100/(double)Leaves()<<endl;
+
+  app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
+    minCostNodes*100/(double)Leaves()<<endl;
+
+  app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
+    addedRayRefs<<endl;
+
+  app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
+    removedRayRefs<<endl;
+
+  //  app << setprecision(4);
+
+  //  app << "#N_CTIME  ( Construction time [s] )\n"
+  //      << Time() << " \n";
+
+  app << "===== END OF TraversalTree statistics ==========\n";
+
+}
+
+
+
+void
+TraversalTree::EvaluateLeafStats(const TraversalData &data)
+{
+
+  // the node became a leaf -> evaluate stats for leafs
+  TraversalLeaf *leaf = (TraversalLeaf *)data.mNode;
+
+  if (data.mDepth > mTermMaxDepth)
+    mStat.maxDepthNodes++;
+  
+  if ( (int)(leaf->mObjects.size()) < mTermMinCost)
+    mStat.minCostNodes++;
+  
+  
+  if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs)
+    mStat.maxObjectRefs = (int)leaf->mObjects.size();
+  
+}
+
+
+
+void
+TraversalTree::SortSubdivisionCandidates(
+			    TraversalLeaf *node,
+			    const int axis
+			    )
+{
+	CLEAR_CONTAINER(*splitCandidates);
+	//splitCandidates->clear();
+
+    int requestedSize = 2*(int)node->mObjects.size();
+	
+	// creates a sorted split candidates array
+	if (splitCandidates->capacity() > 500000 &&
+		requestedSize < (int)(splitCandidates->capacity()/10) ) {		
+			delete splitCandidates;
+			splitCandidates = new vector<SortableEntry *>;
+  }
+  
+  splitCandidates->reserve(requestedSize);
+  
+  // insert all queries 
+  for(ObjectContainer::const_iterator mi = node->mObjects.begin();
+      mi != node->mObjects.end();
+      mi++) 
+  {
+	  AxisAlignedBox3 box = (*mi)->GetBox();
+
+	  splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN,
+								 box.Min(axis),
+								 *mi)
+								 );
+    
+      splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
+								 box.Max(axis),
+								 *mi)
+								 );
+  }
+  
+  stable_sort(splitCandidates->begin(), splitCandidates->end(), iltS);
+}
+
+
+float
+TraversalTree::BestCostRatio(
+					  TraversalLeaf *node,
+					  const AxisAlignedBox3 &box,
+					  const int axis,
+					  float &position,
+					  int &objectsBack,
+					  int &objectsFront
+					  )
+{
+
+#define DEBUG_COST 0
+
+#if DEBUG_COST
+  static int nodeId = -1;
+  char filename[256];
+  
+  static int lastAxis = 100;
+  if (axis <= lastAxis)
+	nodeId++;
+
+  lastAxis = axis;
+  
+  sprintf(filename, "sah-cost%d-%d.log", nodeId, axis);
+  ofstream costStream;
+  
+  if (nodeId < 100)
+	costStream.open(filename);
+
+#endif
+  
+  SortSubdivisionCandidates(node, axis);
+  
+  // go through the lists, count the number of objects left and right
+  // and evaluate the following cost funcion:
+  // C = ct_div_ci  + (ol + or)/queries
+
+  float totalIntersections = 0.0f;
+  vector<SortableEntry *>::const_iterator ci;
+
+  for(ci = splitCandidates->begin();
+      ci < splitCandidates->end();
+      ci++) 
+    if ((*ci)->type == SortableEntry::BOX_MIN) {
+      totalIntersections += (*ci)->intersectable->IntersectionComplexity();
+    }
+	
+  float intersectionsLeft = 0;
+  float intersectionsRight = totalIntersections;
+	
+  int objectsLeft = 0, objectsRight = (int)node->mObjects.size();
+  
+  float minBox = box.Min(axis);
+  float maxBox = box.Max(axis);
+  float boxArea = box.SurfaceArea();
+  
+  float minBand = minBox + mSplitBorder*(maxBox - minBox);
+  float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
+  
+  float minSum = 1e20f;
+  
+  for(ci = splitCandidates->begin();
+      ci < splitCandidates->end();
+      ci++) {
+    switch ((*ci)->type) {
+    case SortableEntry::BOX_MIN:
+      objectsLeft++;
+      intersectionsLeft += (*ci)->intersectable->IntersectionComplexity();
+      break;
+    case SortableEntry::BOX_MAX:
+      objectsRight--;
+      intersectionsRight -= (*ci)->intersectable->IntersectionComplexity();
+      break;
+    }
+
+    if ((*ci)->value > minBand && (*ci)->value < maxBand) {
+      AxisAlignedBox3 lbox = box;
+      AxisAlignedBox3 rbox = box;
+      lbox.SetMax(axis, (*ci)->value);
+      rbox.SetMin(axis, (*ci)->value);
+
+      float sum;
+      if (mSahUseFaces)
+		sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
+      else
+		sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
+      
+      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+      //      cout<<"cost= "<<sum<<endl;
+
+#if DEBUG_COST
+  if (nodeId < 100) {
+	float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
+	float newCost = mCt_div_ci + sum/boxArea;
+	float ratio = newCost/oldCost;
+	costStream<<(*ci)->value<<" "<<ratio<<endl;
+  }
+#endif
+	  
+      if (sum < minSum) {
+		minSum = sum;
+		position = (*ci)->value;
+		
+		objectsBack = objectsLeft;
+		objectsFront = objectsRight;
+      }
+    }
+  }
+  
+  float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
+  float newCost = mCt_div_ci + minSum/boxArea;
+  float ratio = newCost/oldCost;
+  
+#if 0
+  cout<<"===================="<<endl;
+  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
+      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
+#endif
+  return ratio;
+}
+
+
+int TraversalTree::CastLineSegment(const Vector3 &origin,
+							const Vector3 &termination,
+							ViewCellContainer &viewcells)
+{
+	int hits = 0;
+
+	float mint = 0.0f, maxt = 1.0f;
+	const Vector3 dir = termination - origin;
+
+	stack<RayTraversalData> tStack;
+
+	Intersectable::NewMail();
+
+	//maxt += Limits::Threshold;
+
+	Vector3 entp = origin;
+	Vector3 extp = termination;
+
+	TraversalNode *node = mRoot;
+	TraversalNode *farChild;
+
+	float position;
+	int axis;
+
+	while (1)
+	{
+		if (!node->IsLeaf())
+		{
+			TraversalInterior *in = static_cast<TraversalInterior *>(node);
+			position = in->mPosition;
+			axis = in->mAxis;
+
+			if (entp[axis] <= position)
+			{
+				if (extp[axis] <= position)
+				{
+					node = in->mBack;
+					// cases N1,N2,N3,P5,Z2,Z3
+					continue;
+				} 
+				else
+				{
+					// case N4
+					node = in->mBack;
+					farChild = in->mFront;
+				}
+			}
+			else
+			{
+				if (position <= extp[axis])
+				{
+					node = in->mFront;
+					// cases P1,P2,P3,N5,Z1
+					continue;
+				}
+				else
+				{
+					node = in->mFront;
+					farChild = in->mBack;
+					// case P4
+				}
+			}
+
+ 			// $$ modification 3.5.2004 - hints from Kamil Ghais
+			// case N4 or P4
+			float tdist = (position - origin[axis]) / dir[axis];
+			//tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
+			extp = origin + dir * tdist;
+			maxt = tdist;
+		}
+		else
+		{
+			// compute intersection with all objects in this leaf
+			TraversalLeaf *leaf = static_cast<TraversalLeaf *>(node);
+
+			// add view cell to intersections
+			ViewCell *vc = leaf->mViewCell;
+
+			if (!vc->Mailed())
+			{
+				vc->Mail();
+				viewcells.push_back(vc);
+				++ hits;
+			}
+
+			// get the next node from the stack
+			if (tStack.empty())
+				break;
+
+			entp = extp;
+			mint = maxt;
+			
+			RayTraversalData &s  = tStack.top();
+			node = s.mNode;
+			extp = s.mExitPoint;
+			maxt = s.mMaxT;
+			tStack.pop();
+		}
+	}
+
+	return hits;
+}
+
+
+void
+TraversalTree::CollectLeaves(vector<TraversalLeaf *> &leaves)
+{
+  stack<TraversalNode *> nodeStack;
+  nodeStack.push(mRoot);
+
+  while (!nodeStack.empty()) {
+    TraversalNode *node = nodeStack.top();
+    nodeStack.pop();
+    if (node->IsLeaf()) {
+      TraversalLeaf *leaf = (TraversalLeaf *)node;
+      leaves.push_back(leaf);
+    } else {
+      TraversalInterior *interior = (TraversalInterior *)node;
+      nodeStack.push(interior->mBack);
+      nodeStack.push(interior->mFront);
+    }
+  }
+}
+
+
+}
Index: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp	(revision 2072)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp	(revision 2073)
@@ -3463,100 +3463,3 @@
 
 
-bool VspTree::LineSegmentIntersects(const Vector3 &origin, 
-									const Vector3 &termination, 
-									ViewCell *viewCell)
-{
-	/*float mint = 0.0f, maxt = 1.0f;
-	const Vector3 dir = termination - origin;
-
-	stack<LineTraversalData> tStack;
-
-	Vector3 entp = origin;
-	Vector3 extp = termination;
-
-	VspNode *node = mRoot;
-	VspNode *farChild;
-
-	float position;
-	int axis;
-
-	while (1)
-	{
-		if (!node->IsLeaf())
-		{
-			VspInterior *in = static_cast<VspInterior *>(node);
-			position = in->GetPosition();
-			axis = in->GetAxis();
-
-			if (entp[axis] <= position)
-			{
-				if (extp[axis] <= position)
-				{
-					node = in->GetBack();
-					// cases N1,N2,N3,P5,Z2,Z3
-					continue;
-				} else
-				{
-					// case N4
-					node = in->GetBack();
-					farChild = in->GetFront();
-				}
-			}
-			else
-			{
-				if (position <= extp[axis])
-				{
-					node = in->GetFront();
-					// cases P1,P2,P3,N5,Z1
-					continue;
-				}
-				else
-				{
-					node = in->GetFront();
-					farChild = in->GetBack();
-					// case P4
-				}
-			}
-
- 			// $$ modification 3.5.2004 - hints from Kamil Ghais
-			// case N4 or P4
-			const float tdist = (position - origin[axis]) / dir[axis];
-			tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
-
-			extp = origin + dir * tdist;
-			maxt = tdist;
-		}
-		else
-		{
-			// compute intersection with all objects in this leaf
-			VspLeaf *leaf = static_cast<VspLeaf *>(node);
-			ViewCell *viewCell;
-			if (0)
-				viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
-			else
-				viewCell = leaf->GetViewCell();
-
-			if (viewCell == currentViewCell)
-				return true;
-		
-			// get the next node from the stack
-			if (tStack.empty())
-				break;
-
-			entp = extp;
-			mint = maxt;
-			
-			LineTraversalData &s  = tStack.top();
-			node = s.mNode;
-			extp = s.mExitPoint;
-			maxt = s.mMaxT;
-
-			tStack.pop();
-		}
-	}
-*/
-	return false;
-}
-
-
-}
+}
Index: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp	(revision 2066)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp	(revision 2073)
@@ -2456,3 +2456,8 @@
 
 
-}
+void HierarchyManager::CreateTraversalTree()
+{
+}
+
+
+}
