# HG changeset patch
# User John Tsiombikas <nuclear@member.fsf.org>
# Date 1281765604 -3600
# Node ID 58642a8316b74451e97be53b8a15ef8810f84ef0
# Parent  13091c00d7ca10bc42e8ede15f3722d50ac41b8a
continuing with the kdtree

diff -r 13091c00d7ca -r 58642a8316b7 src/scene.cc
--- a/src/scene.cc	Sat Aug 14 03:02:52 2010 +0100
+++ b/src/scene.cc	Sat Aug 14 07:00:04 2010 +0100
@@ -1,4 +1,5 @@
 #include <math.h>
+#include <float.h>
 #include "scene.h"
 
 #define FEQ(a, b)	(fabs((a) - (b)) < 1e-8)
@@ -20,6 +21,16 @@
 	return true;
 }
 
+float AABBox::calc_surface_area() const
+{
+	float area1 = (max[0] - min[0]) * (max[1] - min[1]);
+	float area2 = (max[3] - min[3]) * (max[1] - min[1]);
+	float area3 = (max[0] - min[0]) * (max[3] - min[3]);
+
+	return 2.0f * (area1 + area2 + area3);
+}
+
+
 Scene::Scene()
 {
 	facebuf = 0;
@@ -113,21 +124,66 @@
 	return facebuf;
 }
 
-static void build_kdtree(KDNode **kd, std::list<const Face*> *faces);
+static int build_kdtree(KDNode *kd);
+static void free_kdtree(KDNode *node);
 
 void Scene::build_kdtree()
 {
 	const Face *faces = get_face_buffer();
 	int num_faces = get_num_faces();
 
-	std::list<const Face*> facelist;
+	printf("Constructing kd-tree out of %d faces ...\n", num_faces);
+
+	free_kdtree(kdtree);
+	kdtree = new KDNode;
+	kdtree->left = kdtree->right = 0;
+
+	/* Start the construction of the kdtree by adding all faces of the scene
+	 * to the new root node. At the same time calculate the root's AABB.
+	 */
+	kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX;
+	kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX;
+
 	for(int i=0; i<num_faces; i++) {
-		facelist.push_back(faces + i);
+		const Face *face = faces + i;
+
+		// for each vertex of the face ...
+		for(int j=0; j<3; j++) {
+			const float *pos = face->v[j].pos;
+
+			// for each element (xyz) of the position vector ...
+			for(int k=0; k<3; k++) {
+				if(pos[k] < kdtree->aabb.min[k]) {
+					kdtree->aabb.min[k] = pos[k];
+				}
+				if(pos[k] > kdtree->aabb.max[k]) {
+					kdtree->aabb.max[k] = pos[k];
+				}
+			}
+		}
+
+		kdtree->faces.push_back(face);	// add the face
 	}
 
-	::build_kdtree(&kdtree, &facelist);
+	// now proceed splitting the root recursively
+	::build_kdtree(kdtree);
 }
 
-static void build_kdtree(KDNode **kd, std::list<const Face*> *faces)
+static int build_kdtree(KDNode *kd)
 {
+	if(kd->faces.empty()) {
+		return 0;
+	}
+
+	// XXX cont.
+	return -1;
 }
+
+static void free_kdtree(KDNode *node)
+{
+	if(node) {
+		free_kdtree(node->left);
+		free_kdtree(node->right);
+		delete node;
+	}
+}
diff -r 13091c00d7ca -r 58642a8316b7 src/scene.h
--- a/src/scene.h	Sat Aug 14 03:02:52 2010 +0100
+++ b/src/scene.h	Sat Aug 14 07:00:04 2010 +0100
@@ -33,6 +33,13 @@
 	int matid;
 };
 
+class AABBox {
+public:
+	float min[4], max[4];
+
+	float calc_surface_area() const;
+};
+
 enum {
 	KDAXIS_X,
 	KDAXIS_Y,
@@ -48,9 +55,10 @@
 struct KDNode {
 	int axis;
 	float pt;
+	AABBox aabb;
 
 	KDNode *left, *right;
-	std::list<Face*> faces;
+	std::list<const Face*> faces;
 };
 
 struct KDNodeGPU {