Index: trunk/VUT/GtpVisibilityPreprocessor/scripts/preprocessor.pro
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/scripts/preprocessor.pro	(revision 65)
+++ trunk/VUT/GtpVisibilityPreprocessor/scripts/preprocessor.pro	(revision 177)
@@ -4,5 +4,5 @@
 TARGET = preprocessor
 
-INCLUDEPATH += ../include
+INCLUDEPATH += ../src 
 
 # debuc config
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.h	(revision 177)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.h	(revision 177)
@@ -0,0 +1,43 @@
+#ifndef __PVS_H
+#define __PVS_H
+
+#include <map>
+
+class KdNode;
+
+struct LtKdNode
+{
+  bool operator()(const KdNode *a,
+		  const KdNode *b) const
+  {
+    return a < b;
+  }
+  
+};
+
+struct KdPvsData {
+  int mVisibleSamples;
+  KdPvsData() {}
+  KdPvsData(const int samples):mVisibleSamples(samples) {}
+};
+
+typedef std::map<KdNode *, KdPvsData, LtKdNode> KdPvsMap;
+
+
+class KdPvs {
+public:
+  int mSamples;
+  KdPvsMap mEntries;
+  KdPvsData *Find(KdNode *node);
+  int AddNodeSample(KdNode *node);
+  int Compress() {return 0;}
+  int GetSize() { return mEntries.size(); }
+  void GetData(const int index,
+	       KdNode *&node,
+	       KdPvsData &data
+	       );
+  
+};
+
+#endif
+
Index: trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.h	(revision 176)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.h	(revision 177)
@@ -86,4 +86,12 @@
 class KdNode {
 public:
+  static int mailID;
+  int mailbox;
+  
+  void Mail() { mailbox = mailID; }
+  static void NewMail() { mailID++; }
+  bool Mailed() const { return mailbox == mailID; }
+
+
   KdNode(KdInterior *parent);
 
@@ -277,4 +285,15 @@
   }
 
+  KdNode *
+  FindRandomNeighbor(KdNode *n,
+		     bool onlyUnmailed
+		     );
+
+  int
+  FindNeighbors(KdNode *n,
+		vector<KdNode *> &neighbors,
+		bool onlyUnmailed
+		);
+  
 protected:
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h	(revision 170)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h	(revision 177)
@@ -104,4 +104,6 @@
 
   
+  int
+  Side(const Plane3 &plane) const;
 
   // Overlap returns 1 if the two axis-aligned boxes overlap .. even weakly
@@ -123,5 +125,5 @@
 
   virtual int IsInside(const Vector3 &v) const;
-
+  
   // Test if the box is really sensefull
   virtual bool IsCorrect();
@@ -167,4 +169,12 @@
   //    1 ... the cube contains fully the box
   int MutualPositionWithCube(const Vector3 &center, float halfSize) const;
+
+
+  Vector3 GetRandomPoint() {
+    Vector3 size = Size();
+    return mMin + Vector3(RandomValue(0, size.x),
+			  RandomValue(0, size.y),
+			  RandomValue(0, size.z)); 
+  }
   
   // Returns the smallest axis-aligned box that includes all points
@@ -181,4 +191,5 @@
 					  const Matrix4x4 &tform);
 
+  
   // returns true when two boxes are completely equal
   friend inline int operator== (const AxisAlignedBox3 &A, const AxisAlignedBox3 &B);
Index: trunk/VUT/GtpVisibilityPreprocessor/src/default.env
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/default.env	(revision 176)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/default.env	(revision 177)
@@ -8,6 +8,6 @@
 #	filename glasgow1.x3d
 #	filename vienna.x3d
-#	filename atlanta2.x3d
-	filename soda.dat
+	filename atlanta2.x3d
+#	filename soda.dat
 
 }
@@ -52,6 +52,6 @@
 
 
-SamplingPreprocessor {
-
-
+Sampling {
+	totalSamples	500000
+	samplesPerPass  2
 }
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Makefile
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Makefile	(revision 177)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Makefile	(revision 177)
@@ -0,0 +1,458 @@
+#############################################################################
+# Makefile for building: preprocessor
+# Generated by qmake (1.07a) (Qt 3.3.2) on: Sat Jul 16 12:10:59 2005
+# Project:  preprocessor.pro
+# Template: app
+# Command: $(QMAKE) -o Makefile preprocessor.pro
+#############################################################################
+
+####### Compiler, tools and options
+
+CC		=	cl
+CXX		=	cl
+LEX		= flex
+YACC		= byacc
+CFLAGS	=	-nologo -Zm200 -W0 -MD -O2 -GX  -DUNICODE -DQT_DLL -DQT_THREAD_SUPPORT -DQT_NO_DEBUG
+CXXFLAGS	=	-nologo -Zm200 -W0 -MD -O2 -GX  -DUNICODE -DQT_DLL -DQT_THREAD_SUPPORT -DQT_NO_DEBUG
+LEXFLAGS	=
+YACCFLAGS	=-d
+INCPATH	=	 -I"..\src" -I"..\support\xerces\include" -I"..\support\zlib\include" -I"..\support\boost" -I"$(QTDIR)\include" -I"d:\gametools\svn\trunk\VUT\GtpVisibilityPreprocessor\src" -I"C:\Qt\3.3.2\mkspecs\win32-msvc"
+LINK	=	link
+LFLAGS	=	/NOLOGO delayimp.lib /DELAYLOAD:comdlg32.dll /DELAYLOAD:oleaut32.dll /DELAYLOAD:winmm.dll /DELAYLOAD:wsock32.dll /DELAYLOAD:winspool.dll /SUBSYSTEM:console /LIBPATH:"../support/expat/lib" /LIBPATH:"../support/xerces/lib" /LIBPATH:"$(QTDIR)\lib"
+LIBS	=	 "qt-mt332.lib" "qtmain.lib" "kernel32.lib" "user32.lib" "gdi32.lib" "comdlg32.lib" "advapi32.lib" "shell32.lib" "ole32.lib" "oleaut32.lib" "uuid.lib" "imm32.lib" "winmm.lib" "wsock32.lib" "winspool.lib" "xerces-c_2.lib" "opengl32.lib" "glu32.lib" "delayimp.lib"
+MOC		=	$(QTDIR)\bin\moc.exe
+UIC		=	$(QTDIR)\bin\uic.exe
+QMAKE		=	qmake
+IDC		=	$(QTDIR)\bin\idc.exe
+IDL		=	midl
+ZIP		=	zip -r -9
+COPY_FILE	=       copy
+COPY_DIR	=       copy
+DEL_FILE	=       del
+DEL_DIR	=       rmdir
+MOVE		=       move
+CHK_DIR_EXISTS =	if not exist
+MKDIR		=	mkdir
+INSTALL_FILE= $(COPY_FILE)
+INSTALL_DIR = $(COPY_DIR)
+
+####### Files
+
+HEADERS =	
+SOURCES =	Preprocessor.cpp \
+		SamplingPreprocessor.cpp \
+		ExactPreprocessor.cpp \
+		KdTree.cpp \
+		Environment.cpp \
+		gzstream.cpp \
+		common.cpp \
+		UnigraphicsParser.cpp \
+		X3dExporter.cpp \
+		SceneGraph.cpp \
+		Material.cpp \
+		Matrix4x4.cpp \
+		Vector3.cpp \
+		AxisAlignedBox3.cpp \
+		Ray.cpp \
+		main.cpp \
+		Mesh.cpp \
+		Exporter.cpp \
+		Camera.cpp \
+		X3dParser.cpp \
+		MeshKdTree.cpp \
+		Pvs.cpp
+OBJECTS =	Preprocessor.obj \
+		SamplingPreprocessor.obj \
+		ExactPreprocessor.obj \
+		KdTree.obj \
+		Environment.obj \
+		gzstream.obj \
+		common.obj \
+		UnigraphicsParser.obj \
+		X3dExporter.obj \
+		SceneGraph.obj \
+		Material.obj \
+		Matrix4x4.obj \
+		Vector3.obj \
+		AxisAlignedBox3.obj \
+		Ray.obj \
+		main.obj \
+		Mesh.obj \
+		Exporter.obj \
+		Camera.obj \
+		X3dParser.obj \
+		MeshKdTree.obj \
+		Pvs.obj
+FORMS =	
+UICDECLS =	
+UICIMPLS =	
+SRCMOC	=	
+OBJMOC	=	
+DIST	=	
+TARGET	=	preprocessor.exe
+
+####### Implicit rules
+
+.SUFFIXES: .c .cpp .cc .cxx .C
+
+{.}.cpp{}.obj::
+	$(CXX) -c $(CXXFLAGS) $(INCPATH) -Fo @<<
+	$<
+<<
+
+{.}.cc{}.obj::
+	$(CXX) -c $(CXXFLAGS) $(INCPATH) -Fo @<<
+	$<
+<<
+
+{.}.cxx{}.obj::
+	$(CXX) -c $(CXXFLAGS) $(INCPATH) -Fo @<<
+	$<
+<<
+
+{.}.C{}.obj::
+	$(CXX) -c $(CXXFLAGS) $(INCPATH) -Fo @<<
+	$<
+<<
+
+{.}.c{}.obj::
+	$(CC) -c $(CFLAGS) $(INCPATH) -Fo @<<
+	$<
+<<
+
+####### Build rules
+
+all: Makefile $(TARGET)
+
+$(TARGET):  $(UICDECLS) $(OBJECTS) $(OBJMOC) 
+	$(LINK) $(LFLAGS) /OUT:$(TARGET) @<< 
+	  $(OBJECTS) $(OBJMOC) $(LIBS)
+<<
+
+
+mocables: $(SRCMOC)
+uicables: $(UICIMPLS) $(UICDECLS)
+
+Makefile: preprocessor.pro  C:\Qt\3.3.2\mkspecs\win32-msvc\qmake.conf C:\Qt\3.3.2\lib\qtmain.prl
+	$(QMAKE) -o Makefile preprocessor.pro
+qmake: 
+	@$(QMAKE) -o Makefile preprocessor.pro
+
+dist:
+	$(ZIP) preprocessor.zip $(SOURCES) $(HEADERS) $(DIST) $(FORMS) d:/gametools/svn/trunk/VUT/GtpVisibilityPreprocessor/src/preprocessor.pro C:\Qt\3.3.2\lib\qtmain.prl  
+
+uiclean:
+mocclean:
+clean: uiclean mocclean
+	-$(DEL_FILE) Preprocessor.obj
+	-$(DEL_FILE) SamplingPreprocessor.obj
+	-$(DEL_FILE) ExactPreprocessor.obj
+	-$(DEL_FILE) KdTree.obj
+	-$(DEL_FILE) Environment.obj
+	-$(DEL_FILE) gzstream.obj
+	-$(DEL_FILE) common.obj
+	-$(DEL_FILE) UnigraphicsParser.obj
+	-$(DEL_FILE) X3dExporter.obj
+	-$(DEL_FILE) SceneGraph.obj
+	-$(DEL_FILE) Material.obj
+	-$(DEL_FILE) Matrix4x4.obj
+	-$(DEL_FILE) Vector3.obj
+	-$(DEL_FILE) AxisAlignedBox3.obj
+	-$(DEL_FILE) Ray.obj
+	-$(DEL_FILE) main.obj
+	-$(DEL_FILE) Mesh.obj
+	-$(DEL_FILE) Exporter.obj
+	-$(DEL_FILE) Camera.obj
+	-$(DEL_FILE) X3dParser.obj
+	-$(DEL_FILE) MeshKdTree.obj
+	-$(DEL_FILE) Pvs.obj
+
+
+
+FORCE:
+
+distclean: clean
+	-$(DEL_FILE) $(TARGET)
+
+####### Compile
+
+Preprocessor.obj: Preprocessor.cpp  \
+		SceneGraph.h \
+		Exporter.h \
+		UnigraphicsParser.h \
+		X3dParser.h \
+		Preprocessor.h \
+		Containers.h \
+		AxisAlignedBox3.h \
+		Matrix4x4.h \
+		Vector3.h \
+		Plane3.h \
+		common.h \
+		Material.h \
+		Parser.h \
+		Mesh.h \
+		KdTree.h \
+		ViewCellBsp.h \
+		Intersectable.h \
+		Pvs.h \
+		Ray.h \
+		
+
+SamplingPreprocessor.obj: SamplingPreprocessor.cpp  \
+		SceneGraph.h \
+		KdTree.h \
+		SamplingPreprocessor.h \
+		X3dExporter.h \
+		Environment.h \
+		Containers.h \
+		AxisAlignedBox3.h \
+		Matrix4x4.h \
+		Vector3.h \
+		Plane3.h \
+		common.h \
+		Ray.h \
+		Preprocessor.h \
+		Mesh.h \
+		ViewCellBsp.h \
+		Intersectable.h \
+		Material.h \
+		Pvs.h \
+		Exporter.h \
+		
+
+ExactPreprocessor.obj: ExactPreprocessor.cpp  \
+		ExactPreprocessor.h \
+		Preprocessor.h \
+		Containers.h \
+		Mesh.h \
+		KdTree.h \
+		ViewCellBsp.h \
+		Intersectable.h \
+		Plane3.h \
+		Matrix4x4.h \
+		AxisAlignedBox3.h \
+		Material.h \
+		Pvs.h \
+		Vector3.h \
+		common.h \
+		Ray.h \
+		
+
+KdTree.obj: KdTree.cpp  \
+		Environment.h \
+		Mesh.h \
+		KdTree.h \
+		common.h \
+		Intersectable.h \
+		Plane3.h \
+		Matrix4x4.h \
+		AxisAlignedBox3.h \
+		Material.h \
+		Pvs.h \
+		Vector3.h \
+		Containers.h \
+		Ray.h \
+		
+
+Environment.obj: Environment.cpp  \
+		gzstream.h \
+		common.h \
+		Environment.h \
+		Vector3.h \
+		
+
+gzstream.obj: gzstream.cpp  \
+		gzstream.h \
+		
+
+common.obj: common.cpp  \
+		common.h \
+		
+
+UnigraphicsParser.obj: UnigraphicsParser.cpp  \
+		Vector3.h \
+		Mesh.h \
+		SceneGraph.h \
+		UnigraphicsParser.h \
+		Material.h \
+		Environment.h \
+		common.h \
+		Intersectable.h \
+		Plane3.h \
+		Matrix4x4.h \
+		AxisAlignedBox3.h \
+		Pvs.h \
+		Containers.h \
+		Parser.h \
+		
+
+X3dExporter.obj: X3dExporter.cpp  \
+		common.h \
+		SceneGraph.h \
+		X3dExporter.h \
+		Mesh.h \
+		KdTree.h \
+		Containers.h \
+		AxisAlignedBox3.h \
+		Matrix4x4.h \
+		Vector3.h \
+		Plane3.h \
+		Exporter.h \
+		Material.h \
+		Intersectable.h \
+		Pvs.h \
+		Ray.h \
+		
+
+SceneGraph.obj: SceneGraph.cpp  \
+		SceneGraph.h \
+		X3dExporter.h \
+		Containers.h \
+		AxisAlignedBox3.h \
+		Matrix4x4.h \
+		Vector3.h \
+		Plane3.h \
+		common.h \
+		Exporter.h \
+		Material.h \
+		
+
+Material.obj: Material.cpp  \
+		common.h \
+		Material.h \
+		
+
+Matrix4x4.obj: Matrix4x4.cpp  \
+		Matrix4x4.h \
+		Vector3.h \
+		common.h \
+		
+
+Vector3.obj: Vector3.cpp  \
+		Matrix4x4.h \
+		Vector3.h \
+		common.h \
+		
+
+AxisAlignedBox3.obj: AxisAlignedBox3.cpp  \
+		AxisAlignedBox3.h \
+		Ray.h \
+		Matrix4x4.h \
+		Vector3.h \
+		Plane3.h \
+		common.h \
+		
+
+Ray.obj: Ray.cpp  \
+		Ray.h \
+		Matrix4x4.h \
+		Vector3.h \
+		common.h \
+		
+
+main.obj: main.cpp  \
+		SamplingPreprocessor.h \
+		ExactPreprocessor.h \
+		Parser.h \
+		UnigraphicsParser.h \
+		X3dParser.h \
+		Environment.h \
+		Camera.h \
+		MeshKdTree.h \
+		Preprocessor.h \
+		Containers.h \
+		Mesh.h \
+		KdTree.h \
+		ViewCellBsp.h \
+		Intersectable.h \
+		Plane3.h \
+		Matrix4x4.h \
+		AxisAlignedBox3.h \
+		Material.h \
+		Pvs.h \
+		Vector3.h \
+		common.h \
+		Ray.h \
+		
+
+Mesh.obj: Mesh.cpp  \
+		Ray.h \
+		Mesh.h \
+		MeshKdTree.h \
+		Matrix4x4.h \
+		Vector3.h \
+		common.h \
+		Intersectable.h \
+		Plane3.h \
+		AxisAlignedBox3.h \
+		Material.h \
+		Pvs.h \
+		Containers.h \
+		
+
+Exporter.obj: Exporter.cpp  \
+		X3dExporter.h \
+		Exporter.h \
+		Material.h \
+		
+
+Camera.obj: Camera.cpp  \
+		Camera.h \
+		Ray.h \
+		KdTree.h \
+		Mesh.h \
+		Exporter.h \
+		Vector3.h \
+		AxisAlignedBox3.h \
+		common.h \
+		Matrix4x4.h \
+		Plane3.h \
+		Containers.h \
+		Intersectable.h \
+		Material.h \
+		Pvs.h \
+		
+
+X3dParser.obj: X3dParser.cpp  \
+		X3dParser.h \
+		X3dParserXerces.h \
+		Mesh.h \
+		SceneGraph.h \
+		Parser.h \
+		Intersectable.h \
+		Plane3.h \
+		Matrix4x4.h \
+		AxisAlignedBox3.h \
+		Material.h \
+		Pvs.h \
+		Vector3.h \
+		common.h \
+		Containers.h \
+		
+
+MeshKdTree.obj: MeshKdTree.cpp  \
+		Environment.h \
+		Mesh.h \
+		MeshKdTree.h \
+		common.h \
+		Intersectable.h \
+		Plane3.h \
+		Matrix4x4.h \
+		AxisAlignedBox3.h \
+		Material.h \
+		Pvs.h \
+		Vector3.h \
+		Containers.h \
+		Ray.h \
+		
+
+Pvs.obj: Pvs.cpp  \
+		Pvs.h \
+		
+
+####### Install
+
+install:  
+
+uninstall:  
+
Index: trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.h	(revision 177)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.h	(revision 177)
@@ -0,0 +1,270 @@
+#ifndef _MeshKdTree_H__
+#define _MeshKdTree_H__
+
+#include <functional>
+using namespace std;
+
+#include "Containers.h"
+#include "AxisAlignedBox3.h"
+#include "Ray.h"
+
+  
+class MeshKdNode;
+class MeshKdLeaf;
+class MeshKdInterior;
+  
+/** Abstract class for kd-tree node */
+class MeshKdNode {
+public:
+  MeshKdNode() {}
+  
+  /** Determines whether this node is a leaf or interior node
+      @return true if leaf
+  */
+  virtual bool IsLeaf() const = 0;
+  virtual ~MeshKdNode() {}
+};
+
+/** Implementation of the kd-tree interior node */
+class MeshKdInterior : public MeshKdNode {
+  
+public:
+  MeshKdInterior():MeshKdNode(),
+		   mBack(NULL), mFront(NULL) {}
+  
+  /** \sa KdNode::IsLeaf() */
+  virtual bool IsLeaf() const { return false; }
+
+  /** splitting axis */
+  int mAxis;
+  /** splitting position, absolute position within the bounding box of this node */
+  float mPosition;
+  
+  /** back node */
+  MeshKdNode *mBack;
+  /** front node */
+  MeshKdNode *mFront;
+
+  void SetupChildLinks(MeshKdNode *b, MeshKdNode *f) {
+    mBack = b;
+    mFront = f;
+  }
+  
+  void ReplaceChildLink(MeshKdNode *oldChild, MeshKdNode *newChild) {
+    if (mBack == oldChild)
+      mBack = newChild;
+    else
+      mFront = newChild;
+  }
+  
+  ~MeshKdInterior() {
+    delete mBack;
+    delete mFront;
+  }
+};
+  
+  
+/** Implementation of the kd-tree leaf node */
+class MeshKdLeaf : public MeshKdNode {
+public:
+  MeshKdLeaf():MeshKdNode() {
+  }
+
+  MeshKdLeaf(const vector<int> &faces):MeshKdNode() {
+    mFaces = faces;
+  }
+  
+  /** \sa KdNode::IsLeaf() */
+  virtual bool IsLeaf() const { return true; }
+  
+  /** indices of contained faces */
+  vector<int> mFaces;
+  
+};
+
+
+
+/** KdTree for indexing scene entities - occluders/occludees/viewcells */
+class MeshKdTree {
+  
+protected:
+  struct TraversalData
+  {  
+    MeshKdNode *mNode;
+    MeshKdInterior *mParent;
+    AxisAlignedBox3 mBox;
+    int mDepth;
+    float mPriority;
+    
+    TraversalData() {}
+    
+    TraversalData(MeshKdNode *n, const float p):
+      mNode(n), mPriority(p)
+    {}
+    
+    TraversalData(MeshKdNode *n,
+		  MeshKdInterior *p,
+		  const AxisAlignedBox3 &b,
+		  const int d):
+      mNode(n), mParent(p), mBox(b), mDepth(d) {}
+    
+    
+    bool operator<(
+		   const TraversalData &b) const {
+      MeshKdLeaf *leafa = (MeshKdLeaf *) mNode;
+      MeshKdLeaf *leafb = (MeshKdLeaf *) b.mNode;
+      return 
+	leafa->mFaces.size()*mBox.SurfaceArea()
+	<
+	leafb->mFaces.size()*b.mBox.SurfaceArea();
+    }
+    
+  };
+
+  
+
+public:
+
+  enum {SPLIT_OBJECT_MEDIAN,
+	SPLIT_SPATIAL_MEDIAN,
+	SPLIT_SAH};
+  
+
+  MeshKdTree(Mesh *mesh);
+  ~MeshKdTree() {
+    if (mSplitCandidates)
+      delete mSplitCandidates;
+    
+    if (mRoot)
+      delete mRoot;
+  }
+  
+  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 MeshKdNode *Subdivide(const TraversalData &tdata);
+  
+  /** Get the root of the tree */
+  MeshKdNode *GetRoot() const {
+    return mRoot;
+  }
+  
+  AxisAlignedBox3 GetBox() const { return mMesh->mBox; }
+
+  int
+  CastRay(
+	  Ray &ray,
+	  MeshInstance *instance
+	  );
+
+
+protected:
+  
+  struct RayTraversalData {
+    MeshKdNode *mNode;
+    Vector3 mExitPoint;
+    float mMaxT;
+    
+    RayTraversalData() {}
+    RayTraversalData(MeshKdNode *n,
+		     const Vector3 &p,
+		     const float maxt):
+      mNode(n), mExitPoint(p), mMaxT(maxt) {}
+  };
+
+  // --------------------------------------------------------------
+  // For sorting objects
+  // --------------------------------------------------------------
+  struct  SortableEntry
+  {
+    enum {
+      FACE_MIN,
+      FACE_MAX
+    };
+    
+    int type;
+    float value;
+    int face;
+    
+    SortableEntry() {}
+    SortableEntry(const int t, const float v, const int f):type(t),
+							   value(v),
+							   face(f) {}
+    
+    bool operator<(const SortableEntry &b) const {
+      return value < b.value;
+    }
+    
+  };
+  
+
+  float
+  BestCostRatio(
+		MeshKdLeaf *node,
+		const AxisAlignedBox3 &box,
+		const int axis,
+		float &position,
+		int &objectsBack,
+		int &objectsFront
+		);
+
+  void
+  SortSplitCandidates(
+		      MeshKdLeaf *node,
+		      const int axis
+		      );
+
+  MeshKdNode *
+  SubdivideNode(
+		MeshKdLeaf *leaf,
+		MeshKdInterior *parent,
+		const AxisAlignedBox3 &box,
+		const int depth,
+		AxisAlignedBox3 &backBBox,
+		AxisAlignedBox3 &frontBBox
+		);
+
+  bool
+  TerminationCriteriaMet(const MeshKdLeaf *leaf, const int depth);
+  
+  int
+  SelectPlane(MeshKdLeaf *leaf,
+	      const AxisAlignedBox3 &box,
+	      float &position
+	      );
+
+  /// pointer to the mesh owning the tree
+  Mesh *mMesh;
+  
+  /// root of the tree
+  MeshKdNode *mRoot;
+  
+  /// reusable array of split candidates
+  vector<SortableEntry> *mSplitCandidates;
+
+public:
+  static void ParseEnvironment();
+  static float mSplitBorder;
+  static int mTermMaxDepth;
+  static int mTermMinCost;
+  static float mMaxCostRatio;
+  static float mCt_div_ci;
+  static int mSplitMethod;
+
+};
+  
+
+
+
+
+
+#endif
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 170)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 177)
@@ -1141,4 +1141,14 @@
 		 "0.1");
 
+  RegisterOption("Sampling.totalSamples",
+		 optInt,
+		 "-total_samples=",
+		 "1000000");
+
+  RegisterOption("Sampling.samplesPerPass",
+		 optInt,
+		 "-total_samples=",
+		 "10");
+
   
 }
Index: trunk/VUT/GtpVisibilityPreprocessor/src/preprocessor.pro
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/preprocessor.pro	(revision 176)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/preprocessor.pro	(revision 177)
@@ -8,5 +8,5 @@
 INCLUDEPATH += ../src ../support/xerces/include  ../support/zlib/include ../support/boost
 
-win32:LIBPATH += ../support/expat/lib ../support/xerces/lib
+win32:LIBPATH += ../support/xerces/lib
 
 #win32:LIBPATH += c:/STLport-4.6.2/lib
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.cpp	(revision 177)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.cpp	(revision 177)
@@ -0,0 +1,44 @@
+#include <iostream>
+using namespace std;
+#include "Pvs.h"
+
+KdPvsData *
+KdPvs::Find(KdNode *node)
+{
+  KdPvsMap::iterator i = mEntries.find(node);
+  if (i != mEntries.end()) {
+    //    cout<<node<<" "<<(*i).first<<" "<<(*i).second.mVisibleSamples<<endl;
+    return &(*i).second;
+  } else
+    return NULL;
+}
+
+int
+KdPvs::AddNodeSample(KdNode *node)
+{
+  int result;
+  
+  KdPvsData *data = Find(node);
+  if (data) {
+    data->mVisibleSamples++;
+    result = 0;
+  } else {
+    mEntries[node] = KdPvsData(1);
+    result = 1;
+  }
+  return  result;
+}
+
+
+void
+KdPvs::GetData(const int index,
+	       KdNode *&node,
+	       KdPvsData &data
+	       )
+{
+  KdPvsMap::iterator i = mEntries.begin();
+  for (int k = 0; k!=index && i != mEntries.end(); i++, k++);
+
+  node = (*i).first;
+  data = (*i).second;
+}
Index: trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp	(revision 176)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp	(revision 177)
@@ -7,7 +7,8 @@
 
 
-
-
-KdNode::KdNode(KdInterior *parent):mParent(parent)
+int KdNode::mailID = 1;
+
+
+KdNode::KdNode(KdInterior *parent):mParent(parent), mailbox(0)
 {
   if (parent)
@@ -633,2 +634,42 @@
   }
 }
+
+// Find random neighbor which was not mailed
+KdNode *
+KdTree::FindRandomNeighbor(KdNode *n,
+			   bool onlyUnmailed
+			   )
+{
+  stack<KdNode *> nodeStack;
+  
+  nodeStack.push(mRoot);
+
+  AxisAlignedBox3 box = GetBox(n);
+  int mask = rand();
+
+  while (!nodeStack.empty()) {
+    KdNode *node = nodeStack.top();
+    nodeStack.pop();
+    if (node->IsLeaf()) {
+      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
+	return node;
+    } else {
+      KdInterior *interior = (KdInterior *)node;
+      if (interior->mPosition > box.Max(interior->mAxis))
+	nodeStack.push(interior->mBack);
+      else
+	if (interior->mPosition < box.Min(interior->mAxis))
+	  nodeStack.push(interior->mFront);
+	else {
+	  // random decision
+	  if (mask&1)
+	    nodeStack.push(interior->mBack);
+	  else
+	    nodeStack.push(interior->mFront);
+	  mask = mask>>1;
+	}
+    }
+  }
+  
+  return NULL;
+}
Index: trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp	(revision 176)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp	(revision 177)
@@ -3,11 +3,11 @@
 #include "SamplingPreprocessor.h"
 #include "X3dExporter.h"
-
+#include "Environment.h"
 SamplingPreprocessor::SamplingPreprocessor()
 {
   // this should increase coherence of the samples
-  mSamplesPerPass = 1;
-  mTotalSamples = 1e8;
-  mKdPvsDepth = 10;
+  environment->GetIntValue("Sampling.samplesPerPass", mSamplesPerPass);
+  environment->GetIntValue("Sampling.totalSamples", mTotalSamples);
+  mKdPvsDepth = 100;
 
 }
@@ -75,8 +75,68 @@
     
     for (i =0; i < objects.size(); i++) {
+      KdNode *nodeToSample = NULL;
+      Intersectable *object = objects[i];
+
+      int pvsSize = object->mKdPvs.GetSize();
+      
+      if (0 && pvsSize) {
+	// mail all nodes from the pvs
+	Intersectable::NewMail();
+	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
+	for (; i != object->mKdPvs.mEntries.end(); i++) {
+	  KdNode *node = (*i).first;
+	  node->Mail();
+	}
+	int maxTries = 2*pvsSize;
+	for (int tries = 0; tries < 10; tries++) {
+	  int index = RandomValue(0, pvsSize - 1);
+	  KdPvsData data;
+	  KdNode *visibleNode;
+	  object->mKdPvs.GetData(index, visibleNode, data);
+	  nodeToSample = mKdTree->FindRandomNeighbor(visibleNode, true);
+	  if (nodeToSample)
+	    break;
+	}
+      }
+
+      if (pvsSize) {
+	// mail all nodes from the pvs
+	Intersectable::NewMail();
+	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
+	for (; i != object->mKdPvs.mEntries.end(); i++) {
+	  KdNode *node = (*i).first;
+	  node->Mail();
+	}
+	vector<KdNode *> invisibleNeighbors;
+	// get all neighbors of all PVS nodes
+	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
+	for (; i != object->mKdPvs.mEntries.end(); i++) {
+	  KdNode *node = (*i).first;
+	  mKdTree->FindNeighbors(visibleNode, invisibleNeighbors, true);
+	}
+
+	KdPvsData data;
+	KdNode *visibleNode;
+	object->mKdPvs.GetData(index, visibleNode, data);
+	nodeToSample = mKdTree->FindRandomNeighbor(visibleNode, true);
+	if (nodeToSample)
+	  break;
+      }
+      
+
       for (int k=0; k < mSamplesPerPass; k++) {
-	Intersectable *object = objects[i];
 	object->GetRandomSurfacePoint(point, normal);
-	direction = UniformRandomVector(normal);
+	if (nodeToSample) {
+	  int maxTries = 5;
+	  for (int tries = 0; tries < maxTries; tries++) {
+	    direction = mKdTree->GetBox(nodeToSample).GetRandomPoint() - point;
+	    if (DotProd(direction, normal) > Limits::Small)
+	      break;
+	  }
+	  if (tries == maxTries)
+	    direction = UniformRandomVector(normal);
+	} else
+	  direction = UniformRandomVector(normal);
+	
 	// construct a ray
 	SetupRay(ray, point, direction);
@@ -114,5 +174,5 @@
     for (i=0; i < objects.size(); i++) {
       Intersectable *object = objects[i];
-      pvsSize += object->mKdPvs.mEntries.size();
+      pvsSize += object->mKdPvs.GetSize();
     }
     
@@ -120,6 +180,8 @@
     cout<<"#totalSamples="<<totalSamples/1000<<
       "k   #sampleContributions="<<passSampleContributions<<
-      " ("<<100*passContributingSamples/passSamples<<"%)"<<
-      " avgPVS="<<pvsSize/(float)objects.size()<<endl;
+      " ("<<100*passContributingSamples/(float)passSamples<<"%)"<<
+      " avgPVS="<<pvsSize/(float)objects.size()<<endl<<
+      "avg ray contrib="<<passSampleContributions/(float)passContributingSamples<<
+      endl;
   }
   bool exportRays = false;
Index: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp	(revision 162)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp	(revision 177)
@@ -1508,2 +1508,20 @@
 
 
+int
+AxisAlignedBox3::Side(const Plane3 &plane) const
+{
+  Vector3 v;
+  int i, m=3, M=-3, s;
+  
+  for (i=0;i<8;i++) {
+    GetVertex(i, v);
+    if((s = plane.Side(v)) < m)
+      m=s;
+    if(s > M)
+      M=s;
+    if (m && m==-M)
+      return 0;
+  }
+  
+  return (m == M) ? m : m + M;
+}
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h	(revision 162)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h	(revision 177)
@@ -23,4 +23,12 @@
   }
 
+  float Distance(const Vector3 &v) const {
+    return DotProd(v, mNormal) + mD;
+  }
+
+  int Side(const Vector3 &v, const float threshold = 1e-6) const {
+    return signum(Distance(v), threshold);
+  }
+  
   friend ostream &operator<<(ostream &s, const Plane3 p) {
     s<<p.mNormal<<" "<<p.mD;
Index: trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.cpp	(revision 177)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.cpp	(revision 177)
@@ -0,0 +1,451 @@
+#include <stack>
+#include <algorithm>
+#include <queue>
+#include "Environment.h"
+#include "Mesh.h"
+#include "MeshKdTree.h"
+
+float MeshKdTree::mSplitBorder;
+int MeshKdTree::mTermMaxDepth;
+int MeshKdTree::mTermMinCost;
+float MeshKdTree::mMaxCostRatio;
+float MeshKdTree::mCt_div_ci;
+int MeshKdTree::mSplitMethod;
+
+MeshKdTree::MeshKdTree(Mesh *mesh):mMesh(mesh)
+{
+  mRoot = new MeshKdLeaf;
+  mSplitCandidates = NULL;
+}
+
+void
+MeshKdTree::ParseEnvironment()
+{
+  environment->GetIntValue("MeshKdTree.Termination.maxDepth", mTermMaxDepth);
+  environment->GetIntValue("MeshKdTree.Termination.minCost", mTermMinCost);
+  environment->GetFloatValue("MeshKdTree.Termination.maxCostRatio", mMaxCostRatio);
+  environment->GetFloatValue("MeshKdTree.Termination.ct_div_ci", mCt_div_ci);
+  environment->GetFloatValue("MeshKdTree.splitBorder", mSplitBorder);
+  
+  char splitType[64];
+  environment->GetStringValue("MeshKdTree.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);
+      }
+}
+
+
+
+int
+MeshKdTree::SelectPlane(MeshKdLeaf *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 = false;
+      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;
+}
+
+MeshKdNode *
+MeshKdTree::SubdivideNode(
+			  MeshKdLeaf *leaf,
+			  MeshKdInterior *parent,
+			  const AxisAlignedBox3 &box,
+			  const int depth,
+			  AxisAlignedBox3 &backBBox,
+			  AxisAlignedBox3 &frontBBox
+			  )
+{
+  
+  if (TerminationCriteriaMet(leaf, depth))
+    return leaf;
+  
+  float position;
+  // select subdivision axis
+  int axis = SelectPlane( leaf, box, position );
+  
+  if (axis == -1) {
+    return leaf;
+  }
+  
+  // add the new nodes to the tree
+  MeshKdInterior *node = new MeshKdInterior;
+  
+  node->mAxis = axis;
+  node->mPosition = position;
+  
+  backBBox = box;
+  frontBBox = box;
+  
+  // first count ray sides
+  
+  backBBox.SetMax(axis, position);
+  frontBBox.SetMin(axis, position);
+
+  vector<int>::const_iterator fi;
+  vector<int> objectsFront, objectsBack;
+  
+  for ( fi = leaf->mFaces.begin();
+	fi != leaf->mFaces.end();
+	fi++) {
+    // determine the side of this ray with respect to the plane
+    AxisAlignedBox3 box = mMesh->GetFaceBox(*fi);
+
+    if (box.Max(axis) > position ) 
+      objectsFront.push_back(*fi);
+    
+    if (box.Min(axis) < position )
+      objectsBack.push_back(*fi);
+  }
+  
+  MeshKdLeaf *back = new MeshKdLeaf(objectsBack);
+  MeshKdLeaf *front = new MeshKdLeaf(objectsFront);
+
+  // replace a link from node's parent
+  if (  parent )
+    parent->ReplaceChildLink(leaf, node);
+  
+  // and setup child links
+  node->SetupChildLinks(back, front);
+  
+  delete leaf;
+  return node;
+}
+
+
+
+
+void
+MeshKdTree::SortSplitCandidates(
+			    MeshKdLeaf *node,
+			    const int axis
+			    )
+{
+  mSplitCandidates->clear();
+  
+  int requestedSize = 2*node->mFaces.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);
+  
+  vector<int>::const_iterator fi;
+  // insert all queries 
+  for(fi = node->mFaces.begin();
+      fi < node->mFaces.end();
+      fi++) {
+    
+    AxisAlignedBox3 box = mMesh->GetFaceBox(*fi);
+    
+    mSplitCandidates->push_back(SortableEntry(SortableEntry::FACE_MIN,
+					     box.Min(axis),
+					     *fi)
+			       );
+    
+    
+    mSplitCandidates->push_back(SortableEntry(SortableEntry::FACE_MAX,
+					     box.Max(axis),
+					     *fi)
+			       );
+  }
+  
+  stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
+}
+
+
+float
+MeshKdTree::BestCostRatio(
+			  MeshKdLeaf *node,
+			  const AxisAlignedBox3 &box,
+			  const int axis,
+			  float &position,
+			  int &objectsBack,
+			  int &objectsFront
+			  )
+{
+
+  SortSplitCandidates(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
+
+  int objectsLeft = 0, objectsRight = node->mFaces.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 = 1e20;
+  vector<SortableEntry>::const_iterator ci;
+
+  for(ci = mSplitCandidates->begin();
+      ci != mSplitCandidates->end();
+      ci++) {
+    switch ((*ci).type) {
+    case SortableEntry::FACE_MIN:
+      objectsLeft++;
+      break;
+    case SortableEntry::FACE_MAX:
+      objectsRight--;
+      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 = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
+      
+      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+      //      cout<<"cost= "<<sum<<endl;
+      
+      if (sum < minSum) {
+	minSum = sum;
+	position = (*ci).value;
+	
+	objectsBack = objectsLeft;
+	objectsFront = objectsRight;
+      }
+    }
+  }
+  
+  float oldCost = node->mFaces.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
+MeshKdTree::CastRay(
+		    Ray &ray,
+		    MeshInstance *instance
+		    )
+{
+  int hits = 0;
+  
+  stack<RayTraversalData> tStack;
+  
+  float maxt = 1e6;
+  float mint = 0;
+  
+  AxisAlignedBox3 box = GetBox();
+  if (!box.GetMinMaxT(ray, &mint, &maxt))
+    return 0;
+
+  if (mint < 0)
+    mint = 0;
+  
+  maxt += Limits::Threshold;
+  
+  Vector3 entp = ray.Extrap(mint);
+  Vector3 extp = ray.Extrap(maxt);
+  
+  MeshKdNode *node = mRoot;
+  MeshKdNode *farChild;
+  float position;
+  int axis;
+  
+  while (1) {
+    if (!node->IsLeaf()) {
+      MeshKdInterior *in = (MeshKdInterior *) 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 - ray.GetLoc(axis)) / ray.GetDir(axis);
+      tStack.push(RayTraversalData(farChild, extp, maxt));
+      extp = ray.GetLoc() + ray.GetDir()*tdist;
+      maxt = tdist;
+    } else {
+      // compute intersection with all objects in this leaf
+      MeshKdLeaf *leaf = (MeshKdLeaf *) node;
+      //      cout<<"leaf mfaces size="<<leaf->mFaces.size()<<endl<<flush;
+      hits += instance->CastRay(ray, leaf->mFaces);
+      
+      if (hits && ray.GetType() == Ray::LOCAL_RAY)
+	if (ray.intersections[0].mT <= maxt)
+	  break;
+      
+      // 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;
+}
+
+bool
+MeshKdTree::TerminationCriteriaMet(const MeshKdLeaf *leaf, const int depth)
+{
+  //  cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl;
+  return
+    (leaf->mFaces.size() <= mTermMinCost) ||
+    (depth >= mTermMaxDepth);
+  
+}
+
+bool
+MeshKdTree::Construct()
+{
+  if (!mSplitCandidates)
+    mSplitCandidates = new vector<SortableEntry>;
+  
+  // first construct a leaf that will get subdivide
+  MeshKdLeaf *leaf = (MeshKdLeaf *) mRoot;
+
+  mRoot = Subdivide(TraversalData(leaf, NULL, GetBox(), 0));
+  
+  // remove the allocated array
+  delete mSplitCandidates;
+  mSplitCandidates = NULL;
+  
+  return true;
+}
+
+
+MeshKdNode *
+MeshKdTree::Subdivide(const TraversalData &tdata)
+{
+  MeshKdNode *result = NULL;
+  
+  priority_queue<TraversalData> tStack;
+  //  stack<STraversalData> tStack;
+  
+  tStack.push(tdata);
+  AxisAlignedBox3 backBox, frontBox;
+
+  
+  while (!tStack.empty()) {
+
+    TraversalData data = tStack.top();
+    tStack.pop();
+    
+    MeshKdNode *node = SubdivideNode((MeshKdLeaf *) data.mNode,
+				     data.mParent,
+				     data.mBox,
+				     data.mDepth,
+				     backBox,
+				     frontBox
+				     );
+    if (result == NULL)
+      result = node;
+    
+    if (!node->IsLeaf()) {
+
+      MeshKdInterior *interior = (MeshKdInterior *) node;
+      // push the children on the stack
+      tStack.push(TraversalData(interior->mBack, interior, backBox, data.mDepth+1));
+      tStack.push(TraversalData(interior->mFront, interior, frontBox, data.mDepth+1));
+      
+    }
+  }
+  
+  return result;
+
+}
