# HG changeset patch
# User John Tsiombikas <nuclear@member.fsf.org>
# Date 1282420317 -3600
# Node ID 353d801276278a170fa07784877bd5a4b450151a
# Parent  97cfd9675310f549f66df8d5479976d0e01157be
doh ... it doesn't work

diff -r 97cfd9675310 -r 353d80127627 rt.cl
--- a/rt.cl	Sat Aug 21 03:42:49 2010 +0100
+++ b/rt.cl	Sat Aug 21 20:51:57 2010 +0100
@@ -59,7 +59,7 @@
 };
 
 struct KDNode {
-	AABBox aabb;
+	struct AABBox aabb;
 	int face_idx[32];
 	int num_faces;
 	int padding[3];
@@ -161,9 +161,51 @@
 	return dcol + scol;
 }
 
+#define STACK_SIZE	128
 bool find_intersection(struct Ray ray, const struct Scene *scn, struct SurfPoint *spres)
 {
-	return false;
+	struct SurfPoint sp0;
+	sp0.t = 1.0;
+	sp0.obj = 0;
+
+	int idxstack[STACK_SIZE];
+	int sp = 0;			// points at the topmost element of the stack
+	idxstack[sp] = 1;	// root at tree[1] (heap)
+
+	while(sp >= 0) {
+		int idx = idxstack[sp--];	// remove this index from the stack and process it
+
+		global struct KDNode *node = scn->kdtree + idx;
+
+		if(intersect_aabb(ray, node->aabb)) {
+			// leaf node ...
+			if(node->num_faces) {
+				// check each face in turn and update the nearest intersection as needed
+				for(int i=0; i<node->num_faces; i++) {
+					struct SurfPoint sp;
+					int fidx = node->face_idx[i];
+
+					if(intersect(ray, scn->faces + fidx, &sp) && sp.t < sp0.t) {
+						sp0 = sp;
+					}
+				}
+			}
+		} else {
+			// internal node ... recurse to the children
+			idxstack[++sp] = idx * 2;
+			idxstack[++sp] = idx * 2 + 1;
+		}
+	}
+
+	if(!sp0.obj) {
+		return false;
+	}
+
+	if(spres) {
+		*spres = sp0;
+		spres->mat = scn->matlib[sp0.obj->matid];
+	}
+	return true;
 }
 
 /*bool find_intersection(struct Ray ray, const struct Scene *scn, struct SurfPoint *spres)
@@ -236,7 +278,10 @@
 		return true;
 	}
 
-	float4 bbox[2] = {aabb.min, aabb.max};
+	float4 bbox[2] = {
+		aabb.min.x, aabb.min.y, aabb.min.z, 0,
+		aabb.max.x, aabb.max.y, aabb.max.z, 0
+	};
 
 	int xsign = (int)(ray.dir.x < 0.0);
 	float invdirx = 1.0 / ray.dir.x;
@@ -264,7 +309,7 @@
 		return false;
 	}
 
-	return tmin < t1 && tmax > t0;
+	return tmin < 1.0 && tmax > 0.0;
 }
 
 float4 reflect(float4 v, float4 n)
diff -r 97cfd9675310 -r 353d80127627 src/clray.cc
--- a/src/clray.cc	Sat Aug 21 03:42:49 2010 +0100
+++ b/src/clray.cc	Sat Aug 21 20:51:57 2010 +0100
@@ -107,10 +107,6 @@
 	}
 	atexit(cleanup);
 
-	if(!scn.build_kdtree()) {
-		return 1;
-	}
-
 
 	/*glGenTextures(1, &tex);
 	glBindTexture(GL_TEXTURE_2D, tex);*/
diff -r 97cfd9675310 -r 353d80127627 src/rt.cc
--- a/src/rt.cc	Sat Aug 21 03:42:49 2010 +0100
+++ b/src/rt.cc	Sat Aug 21 20:51:57 2010 +0100
@@ -90,7 +90,6 @@
 		fprintf(stderr, "failed to create kdtree buffer\n");
 		return false;
 	}
-	int num_kdnodes = scn->get_num_kdnodes();
 
 	/* setup argument buffers */
 	prog->set_arg_buffer(KARG_FRAMEBUFFER, ARG_WR, xsz * ysz * 4 * sizeof(float));
@@ -101,7 +100,7 @@
 	prog->set_arg_buffer(KARG_PRIM_RAYS, ARG_RD, xsz * ysz * sizeof *prim_rays, prim_rays);
 	prog->set_arg_buffer(KARG_XFORM, ARG_RD, 16 * sizeof(float));
 	prog->set_arg_buffer(KARG_INVTRANS_XFORM, ARG_RD, 16 * sizeof(float));
-	prog->set_arg_buffer(KARG_KDTREE, ARG_RD, num_kdnodes * sizeof *kdbuf, kdbuf);
+	prog->set_arg_buffer(KARG_KDTREE, ARG_RD, scn->get_kdtree_buffer_size(), kdbuf);
 
 	if(prog->get_num_args() < NUM_KERNEL_ARGS) {
 		return false;
diff -r 97cfd9675310 -r 353d80127627 src/scene.cc
--- a/src/scene.cc	Sat Aug 21 03:42:49 2010 +0100
+++ b/src/scene.cc	Sat Aug 21 20:51:57 2010 +0100
@@ -70,7 +70,6 @@
 	facebuf = 0;
 	num_faces = -1;
 	kdtree = 0;
-	num_kdnodes = -1;
 	kdbuf = 0;
 }
 
@@ -172,25 +171,30 @@
 		((Scene*)this)->build_kdtree();
 	}
 
-	if(!get_num_kdnodes()) {
-		return 0;
-	}
+	int max_nodes = (int)pow(2, kdtree_depth(kdtree)) - 1;
+	printf("allocating storage for the complete tree (%d)\n", max_nodes);
 
-	kdbuf = new KDNodeGPU[num_kdnodes + 1];
+	kdbuf = new KDNodeGPU[max_nodes + 1];
 	kdtree_gpu_flatten(kdbuf, 1, kdtree, get_face_buffer());
 	return kdbuf;
 }
 
-int Scene::get_num_kdnodes() const
+static int ipow(int x, int n)
 {
-	if(num_kdnodes >= 0) {
-		return num_kdnodes;
+	assert(n >= 0);
+
+	int res = 1;
+	for(int i=0; i<n; i++) {
+		res *= x;
 	}
-
-	num_kdnodes = kdtree_nodes(kdtree);
-	return num_kdnodes;
+	return res;
 }
 
+int Scene::get_kdtree_buffer_size() const
+{
+	// 2**depth - 1 nodes for the complete tree + 1 for the unused heap item 0.
+	return ipow(2, kdtree_depth(kdtree)) * sizeof(KDNodeGPU);
+}
 
 void Scene::draw_kdtree() const
 {
@@ -255,6 +259,8 @@
 
 bool Scene::build_kdtree()
 {
+	assert(kdtree == 0);
+
 	const Face *faces = get_face_buffer();
 	int num_faces = get_num_faces();
 
@@ -351,7 +357,7 @@
 		}
 	}
 
-	printf("current cost: %f,   best_cost: %f\n", kd->cost, best_sum_cost);
+	//printf("current cost: %f,   best_cost: %f\n", kd->cost, best_sum_cost);
 	if(best_sum_cost > kd->cost && (opt_max_items == 0 || kd->num_faces <= opt_max_items)) {
 		return true;	// stop splitting if it doesn't reduce the cost
 	}
@@ -461,7 +467,7 @@
 			fprintf(stderr, "kdtree_gpu_flatten WARNING: more than %d faces in node, skipping!\n", (int)MAX_FACES);
 			break;
 		}
-		dest->face_idx[dest->num_faces++] = *it - facebuf;
+		dest->face_idx[dest->num_faces++] = *it++ - facebuf;
 	}
 
 	if(node->left) {
@@ -475,10 +481,10 @@
 {
 	if(!node) return;
 
-	for(int i=0; i<level; i++) {
+	/*for(int i=0; i<level; i++) {
 		fputs("   ", stdout);
 	}
-	printf("- %d (cost: %f)\n", node->num_faces, node->cost);
+	printf("- %d (cost: %f)\n", node->num_faces, node->cost);*/
 
 	print_item_counts(node->left, level + 1);
 	print_item_counts(node->right, level + 1);
diff -r 97cfd9675310 -r 353d80127627 src/scene.h
--- a/src/scene.h	Sat Aug 21 03:42:49 2010 +0100
+++ b/src/scene.h	Sat Aug 21 20:51:57 2010 +0100
@@ -73,7 +73,6 @@
 	mutable int num_faces;
 
 	mutable KDNodeGPU *kdbuf;
-	mutable int num_kdnodes;
 
 public:
 	std::vector<Mesh*> meshes;
@@ -96,7 +95,7 @@
 
 	const Face *get_face_buffer() const;
 	const KDNodeGPU *get_kdtree_buffer() const;
-	int get_num_kdnodes() const;
+	int get_kdtree_buffer_size() const;
 
 	void draw_kdtree() const;
 	bool build_kdtree();