--- a/TODO	Fri Nov 23 01:24:33 2007 +0100
+++ b/TODO	Fri Nov 23 16:14:38 2007 +0100
@@ -1,5 +1,9 @@
- * kd-tree
+ * kd-tree:
+   - optimize structures
+   - optimize construction: do not use bounding boxes of shapes, instead implement box-shape intersection
  * transforms, camera
+ * update Python binding, new classes
+ * C++ demos
 
 New Classes?
 ============

--- a/src/kdtree.cc	Fri Nov 23 01:24:33 2007 +0100
+++ b/src/kdtree.cc	Fri Nov 23 16:14:38 2007 +0100
@@ -20,6 +20,17 @@
 	}
 };
 
+Shape *Container::nearest_intersection(const Shape *origin_shape, const Ray &ray,
+	float &nearest_distance)
+{
+	Shape *nearest_shape = NULL;
+	ShapeList::iterator shape;
+	for (shape = shapes.begin(); shape != shapes.end(); shape++)
+		if (*shape != origin_shape && (*shape)->intersect(ray, nearest_distance))
+			nearest_shape = *shape;
+	return nearest_shape;
+}
+
 void KdNode::subdivide(BBox bbox, int depth)
 {
 	if (depth >= 10 || shapes.size() <= 2)
@@ -219,7 +230,7 @@
 	children[1].subdivide(rbb, depth+1);
 }
 
-void KdTree::optimize()
+void KdTree::build()
 {
 	root = new KdNode();
 	root->shapes = shapes;
@@ -227,6 +238,7 @@
 	built = true;
 }
 
+// this should save whole kd-tree with triangles distributed into leaves
 void KdTree::save(ostream &str, KdNode *node)
 {
 	if (!built)
@@ -244,3 +256,9 @@
 		str << ";)";
 	}
 }
+
+// load kd-tree from file/stream
+void KdTree::load(istream &str, KdNode *node)
+{
+	
+}

--- a/src/kdtree.h	Fri Nov 23 01:24:33 2007 +0100
+++ b/src/kdtree.h	Fri Nov 23 16:14:38 2007 +0100
@@ -65,8 +65,11 @@
 public:
 	ShapeList shapes;
 	Container(): bbox(), shapes() {};
+	virtual ~Container() {};
 	virtual void addShape(Shape* aShape);
 	//void addShapeNoExtend(Shape* aShape) { shapes.push_back(aShape); };
+        virtual Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray,
+		float &nearest_distance);
 	virtual void optimize() {};
 };
 
@@ -105,8 +108,10 @@
 public:
 	KdTree() : Container(), built(false) {};
 	void addShape(Shape* aShape) { Container::addShape(aShape); built = false; };
-	void optimize(); // build kd-tree
+	void build();
+	void optimize() { build(); };
 	void save(ostream &str, KdNode *node = NULL);
+	void load(istream &str, KdNode *node = NULL);
 };
 
 #endif

--- a/src/raytracer.cc	Fri Nov 23 01:24:33 2007 +0100
+++ b/src/raytracer.cc	Fri Nov 23 16:14:38 2007 +0100
@@ -52,17 +52,6 @@
 	return Vector3(x, y, z);
 }
 
-inline Shape *Raytracer::nearest_intersection(const Shape *origin_shape, const Ray &ray,
-	float &nearest_distance)
-{
-	Shape *nearest_shape = NULL;
-	ShapeList::iterator shape;
-	for (shape = top->shapes.begin(); shape != top->shapes.end(); shape++)
-		if (*shape != origin_shape && (*shape)->intersect(ray, nearest_distance))
-			nearest_shape = *shape;
-	return nearest_shape;
-}
-
 // ---- tyto dve funkce budou v budouci verzi metody objektu PhongShader
 
 // calculate shader function
@@ -104,7 +93,7 @@
 Colour Raytracer::raytrace(Ray &ray, int depth, Shape *origin_shape)
 {
 	float nearest_distance = FLT_MAX; //Infinity
-	Shape *nearest_shape = nearest_intersection(origin_shape, ray, nearest_distance);
+	Shape *nearest_shape = top->nearest_intersection(origin_shape, ray, nearest_distance);
 
 	if (nearest_shape == NULL) {
 		return bg_colour;
@@ -124,7 +113,7 @@
 				if ((*light)->shadows) {
 					Ray shadow_ray = Ray(P, L);
 					float dist = FLT_MAX;
-					if (nearest_intersection(nearest_shape, shadow_ray, dist))
+					if (top->nearest_intersection(nearest_shape, shadow_ray, dist))
 						continue;
 				}
 
@@ -155,7 +144,7 @@
 				Vector3 dir = SphereDistribute(i, ao_samples, ao_angle, normal);
 				Ray ao_ray = Ray(P, dir);
 				float dist = ao_distance;
-				Shape *shape_in_way = nearest_intersection(nearest_shape, ao_ray, dist);
+				Shape *shape_in_way = top->nearest_intersection(nearest_shape, ao_ray, dist);
 				if (shape_in_way == NULL)
 					miss += 1.0;
 				else

--- a/src/raytracer.h	Fri Nov 23 01:24:33 2007 +0100
+++ b/src/raytracer.h	Fri Nov 23 16:14:38 2007 +0100
@@ -34,8 +34,6 @@
 	float ao_distance, ao_angle;
 
 	Vector3 SphereDistribute(int i, int n, float extent, Vector3 &normal);
-	inline Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray,
-		float &nearest_distance);
 public:
 	Raytracer(): lights(), bg_colour(0.0, 0.0, 0.0), ao_samples(0) { top = new KdTree(); };
 	~Raytracer() {};