diff -r d8d596d26f25 -r bf17f9f84c91 src/kdtree.h
--- a/src/kdtree.h	Sun Nov 18 11:20:56 2007 +0100
+++ b/src/kdtree.h	Thu Nov 22 17:53:34 2007 +0100
@@ -5,47 +5,100 @@
 
 #include "scene.h"
 
-class SpaceDivider
+using namespace std;
+
+class ShapeList: public vector<Shape*>
+{
+};
+
+class SortableShape
 {
-	ShapeList *shapes;
 public:
-	SpaceDivider(ShapeList &shapelist): shapes(shapelist) {};
+	Shape *shape;
+	BBox bbox;
+	short axis;
+	short mark;
+
+	SortableShape(Shape *aShape, short &aAxis): shape(aShape), axis(aAxis), mark(0)
+		{ bbox = shape->get_bbox(); };
+	friend bool operator<(const SortableShape& a, const SortableShape& b)
+		{ return a.bbox.L.cell[a.axis] < b.bbox.L.cell[b.axis]; };
+	void setAxis(short aAxis) { axis = aAxis; };
+	void setMark() { mark = 1; };
+	short hasMark() { return mark; };
 };
 
-class KdNode:
+class SortableShapeList: public vector<SortableShape>
+{
+public:
+	SortableShapeList(ShapeList &shapes, short axis)
+	{
+		ShapeList::iterator shape;
+		for (shape = shapes.begin(); shape != shapes.end(); shape++)
+			push_back(SortableShape(*shape, axis));
+	};
+};
+
+class SplitPos
+{
+public:
+	float pos;
+	int lnum, rnum;
+	SplitPos(float &aPos): pos(aPos) {};
+	friend bool operator<(const SplitPos& a, const SplitPos& b)
+		{ return a.pos < b.pos; };
+};
+
+class SplitList: public vector<SplitPos>
+{
+};
+
+class Container
+{
+protected:
+	ShapeList shapes;
+	BBox bbox;
+public:
+	Container(): shapes(), bbox() {};
+	void addShape(Shape* aShape);
+	//void addShapeNoExtend(Shape* aShape) { shapes.push_back(aShape); };
+};
+
+class KdNode
 {
 	float split;
 	bool leaf; /* is this node a leaf? */
-	char axis; /* 0,1,2 => x,y,z */
-	KdNode *leftchild, *rightchild;
+	char axis; /* 1,2,3 => x,y,z */
+	KdNode *leftchild;
 public:
-	vector<Shape*> shapes;
+	ShapeList shapes;
 
 	KdNode() : leaf(true), axis(0), shapes() {};
 
-	setAxis(char aAxis) { axis = aAxis; };
+	void setAxis(char aAxis) { axis = aAxis; };
 	char getAxis() { return axis; };
 
-	setSplit(float aSplit) { split = aSplit; };
+	void setSplit(float aSplit) { split = aSplit; };
 	float getSplit() { return split; };
 
-	setLeaf(bool aLeaf) { leaf = aLeaf; };
+	void setLeaf(bool aLeaf) { leaf = aLeaf; };
 	bool isLeaf() { return leaf; };
 
-	setLeftChild(KdNode *aLeft) { leftchild = aLeft; };
+	void setLeftChild(KdNode *aLeft) { leftchild = aLeft; };
 	KdNode *getLeftChild() { return leftchild; };
-	setRightChild(KdNode *aRight) { rightchild = aRight; };
-	KdNode *getRightChild() { return rightchild; };
+	KdNode *getRightChild() { return leftchild+1; };
 
-	addShape(Shape* aShape) { shapes.push_back(aShape); };
+	void addShape(Shape* aShape) { shapes.push_back(aShape); };
+
+	void subdivide(BBox bbox, int depth, int count);
 };
 
-class KdTree: public SpaceDivider
+class KdTree: public Container
 {
-	KdNote *root;
+	KdNode *root;
 public:
-	KdTree(ShapeList &shapelist);
-	rebuild();
+	KdTree() {};
+	void build();
 };
 
 #endif