# HG changeset patch
# User Radek Brich <radek.brich@devl.cz>
# Date 1208799327 -7200
# Node ID 3b60fd0bea64c71daf39909277466ade9642e74b
# Parent  20dee9819b17b188475a7b4f39d479cc76051f98
kd-tree: move recursive build subroutine from KdNode to KdTree

diff -r 20dee9819b17 -r 3b60fd0bea64 include/kdtree.h
--- a/include/kdtree.h	Mon Apr 21 09:05:09 2008 +0200
+++ b/include/kdtree.h	Mon Apr 21 19:35:27 2008 +0200
@@ -59,16 +59,14 @@
 	short getAxis() { return flags & 3; };
 
 	void setSplit(Float aSplit) { split = aSplit; };
-	Float getSplit() { return split; };
+	Float& getSplit() { return split; };
 
 	void setChildren(KdNode *node) { children = node; assert((flags & 3) == 0); };
-	KdNode *getLeftChild() { return (KdNode*)((off_t)children & ~3); };
-	KdNode *getRightChild() { return (KdNode*)((off_t)children & ~3) + 1; };
+	KdNode* getLeftChild() { return (KdNode*)((off_t)children & ~3); };
+	KdNode* getRightChild() { return (KdNode*)((off_t)children & ~3) + 1; };
 
-	ShapeList *getShapes() { return (ShapeList*)((off_t)shapes & ~3); };
+	ShapeList* getShapes() { return (ShapeList*)((off_t)shapes & ~3); };
 	void addShape(Shape* aShape) { getShapes()->push_back(aShape); };
-
-	void subdivide(BBox bbox, int maxdepth);
 };
 
 /**
@@ -79,6 +77,8 @@
 	KdNode *root;
 	bool built;
 	int max_depth;
+
+	void recursive_build(KdNode *node, BBox bbox, int maxdepth);
 public:
 	KdTree() : Container(), root(NULL), built(false), max_depth(32) {};
 	~KdTree() { if (root) delete root; };
diff -r 20dee9819b17 -r 3b60fd0bea64 src/kdtree.cc
--- a/src/kdtree.cc	Mon Apr 21 09:05:09 2008 +0200
+++ b/src/kdtree.cc	Mon Apr 21 19:35:27 2008 +0200
@@ -67,11 +67,13 @@
 }
 
 // kd-tree recursive build algorithm, inspired by PBRT (www.pbrt.org)
-void KdNode::subdivide(BBox bounds, int maxdepth)
+void KdTree::recursive_build(KdNode *node, BBox bounds, int maxdepth)
 {
-	if (maxdepth <= 0 || getShapes()->size() <= 2)
+	ShapeList *shapes = node->getShapes();
+
+	if (maxdepth <= 0 || shapes->size() <= 2)
 	{
-		setLeaf();
+		node->setLeaf();
 		return;
 	}
 
@@ -85,7 +87,7 @@
 	// create sorted list of shape bounds (= find all posible splits)
 	vector<ShapeBound> edges[3];
 	ShapeList::iterator shape;
-	for (shape = getShapes()->begin(); shape != getShapes()->end(); shape++)
+	for (shape = shapes->begin(); shape != shapes->end(); shape++)
 	{
 		BBox shapebounds = (*shape)->get_bbox();
 		for (int ax = 0; ax < 3; ax++)
@@ -101,13 +103,13 @@
 	const Float K = 1.4; // constant, K = cost of traversal / cost of ray-triangle intersection
 	Float SAV = (bounds.w()*bounds.h() +  // surface area of node
 		bounds.w()*bounds.d() + bounds.h()*bounds.d());
-	Float cost = SAV * (K + getShapes()->size()); // initial cost = non-split cost
+	Float cost = SAV * (K + shapes->size()); // initial cost = non-split cost
 
 	vector<ShapeBound>::iterator edge, splitedge = edges[2].end();
 	int axis = 0;
 	for (int ax = 0; ax < 3; ax++)
 	{
-		int lnum = 0, rnum = getShapes()->size();
+		int lnum = 0, rnum = shapes->size();
 		BBox lbb = bounds;
 		BBox rbb = bounds;
 		for (edge = edges[ax].begin(); edge != edges[ax].end(); edge++)
@@ -127,7 +129,6 @@
 				axis = ax;
 				splitedge = edge;
 				cost = splitcost;
-				split = edge->pos;
 			}
 
 			if (!edge->end)
@@ -137,17 +138,19 @@
 
 	if (splitedge == edges[2].end())
 	{
-		setLeaf();
+		node->setLeaf();
 		return;
 	}
 
+	node->setSplit(splitedge->pos);
+
 #if 0
 // export kd-tree as .obj for visualization
 // this would be hard to reconstruct later
 	static ofstream F("kdtree.obj");
 	Vector3 v;
 	static int f=0;
-	v.cell[axis] = split;
+	v.cell[axis] = node->getSplit();
 	v.cell[(axis+1)%3] = bounds.L.cell[(axis+1)%3];
 	v.cell[(axis+2)%3] = bounds.L.cell[(axis+2)%3];
 	F << "v " << v.x << " " << v.y << " " << v.z << endl;
@@ -165,24 +168,24 @@
 #endif
 
 	// split this node
-	delete getShapes();
+	delete shapes;
 
 	BBox lbb = bounds;
 	BBox rbb = bounds;
-	lbb.H.cell[axis] = split;
-	rbb.L.cell[axis] = split;
-	setChildren(new KdNode[2]);
-	setAxis(axis);
+	lbb.H.cell[axis] = node->getSplit();
+	rbb.L.cell[axis] = node->getSplit();
+	node->setChildren(new KdNode[2]);
+	node->setAxis(axis);
 
 	for (edge = edges[axis].begin(); edge != splitedge; edge++)
 		if (!edge->end && edge->shape->intersect_bbox(lbb))
-			getLeftChild()->addShape(edge->shape);
+			node->getLeftChild()->addShape(edge->shape);
 	for (edge = splitedge; edge < edges[axis].end(); edge++)
 		if (edge->end && edge->shape->intersect_bbox(rbb))
-			getRightChild()->addShape(edge->shape);
+			node->getRightChild()->addShape(edge->shape);
 
-	getLeftChild()->subdivide(lbb, maxdepth-1);
-	getRightChild()->subdivide(rbb, maxdepth-1);
+	recursive_build(node->getLeftChild(), lbb, maxdepth-1);
+	recursive_build(node->getRightChild(), rbb, maxdepth-1);
 }
 
 void KdTree::build()
@@ -192,7 +195,7 @@
 	ShapeList::iterator shape;
 	for (shape = shapes.begin(); shape != shapes.end(); shape++)
 		root->addShape(*shape);
-	root->subdivide(bbox, max_depth);
+	recursive_build(root, bbox, max_depth);
 	built = true;
 }