1.1 --- a/src/scene.cc	Sat Aug 14 03:02:52 2010 +0100
     1.2 +++ b/src/scene.cc	Sat Aug 14 07:00:04 2010 +0100
     1.3 @@ -1,4 +1,5 @@
     1.4  #include <math.h>
     1.5 +#include <float.h>
     1.6  #include "scene.h"
     1.7  
     1.8  #define FEQ(a, b)	(fabs((a) - (b)) < 1e-8)
     1.9 @@ -20,6 +21,16 @@
    1.10  	return true;
    1.11  }
    1.12  
    1.13 +float AABBox::calc_surface_area() const
    1.14 +{
    1.15 +	float area1 = (max[0] - min[0]) * (max[1] - min[1]);
    1.16 +	float area2 = (max[3] - min[3]) * (max[1] - min[1]);
    1.17 +	float area3 = (max[0] - min[0]) * (max[3] - min[3]);
    1.18 +
    1.19 +	return 2.0f * (area1 + area2 + area3);
    1.20 +}
    1.21 +
    1.22 +
    1.23  Scene::Scene()
    1.24  {
    1.25  	facebuf = 0;
    1.26 @@ -113,21 +124,66 @@
    1.27  	return facebuf;
    1.28  }
    1.29  
    1.30 -static void build_kdtree(KDNode **kd, std::list<const Face*> *faces);
    1.31 +static int build_kdtree(KDNode *kd);
    1.32 +static void free_kdtree(KDNode *node);
    1.33  
    1.34  void Scene::build_kdtree()
    1.35  {
    1.36  	const Face *faces = get_face_buffer();
    1.37  	int num_faces = get_num_faces();
    1.38  
    1.39 -	std::list<const Face*> facelist;
    1.40 +	printf("Constructing kd-tree out of %d faces ...\n", num_faces);
    1.41 +
    1.42 +	free_kdtree(kdtree);
    1.43 +	kdtree = new KDNode;
    1.44 +	kdtree->left = kdtree->right = 0;
    1.45 +
    1.46 +	/* Start the construction of the kdtree by adding all faces of the scene
    1.47 +	 * to the new root node. At the same time calculate the root's AABB.
    1.48 +	 */
    1.49 +	kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX;
    1.50 +	kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX;
    1.51 +
    1.52  	for(int i=0; i<num_faces; i++) {
    1.53 -		facelist.push_back(faces + i);
    1.54 +		const Face *face = faces + i;
    1.55 +
    1.56 +		// for each vertex of the face ...
    1.57 +		for(int j=0; j<3; j++) {
    1.58 +			const float *pos = face->v[j].pos;
    1.59 +
    1.60 +			// for each element (xyz) of the position vector ...
    1.61 +			for(int k=0; k<3; k++) {
    1.62 +				if(pos[k] < kdtree->aabb.min[k]) {
    1.63 +					kdtree->aabb.min[k] = pos[k];
    1.64 +				}
    1.65 +				if(pos[k] > kdtree->aabb.max[k]) {
    1.66 +					kdtree->aabb.max[k] = pos[k];
    1.67 +				}
    1.68 +			}
    1.69 +		}
    1.70 +
    1.71 +		kdtree->faces.push_back(face);	// add the face
    1.72  	}
    1.73  
    1.74 -	::build_kdtree(&kdtree, &facelist);
    1.75 +	// now proceed splitting the root recursively
    1.76 +	::build_kdtree(kdtree);
    1.77  }
    1.78  
    1.79 -static void build_kdtree(KDNode **kd, std::list<const Face*> *faces)
    1.80 +static int build_kdtree(KDNode *kd)
    1.81  {
    1.82 +	if(kd->faces.empty()) {
    1.83 +		return 0;
    1.84 +	}
    1.85 +
    1.86 +	// XXX cont.
    1.87 +	return -1;
    1.88  }
    1.89 +
    1.90 +static void free_kdtree(KDNode *node)
    1.91 +{
    1.92 +	if(node) {
    1.93 +		free_kdtree(node->left);
    1.94 +		free_kdtree(node->right);
    1.95 +		delete node;
    1.96 +	}
    1.97 +}

     2.1 --- a/src/scene.h	Sat Aug 14 03:02:52 2010 +0100
     2.2 +++ b/src/scene.h	Sat Aug 14 07:00:04 2010 +0100
     2.3 @@ -33,6 +33,13 @@
     2.4  	int matid;
     2.5  };
     2.6  
     2.7 +class AABBox {
     2.8 +public:
     2.9 +	float min[4], max[4];
    2.10 +
    2.11 +	float calc_surface_area() const;
    2.12 +};
    2.13 +
    2.14  enum {
    2.15  	KDAXIS_X,
    2.16  	KDAXIS_Y,
    2.17 @@ -48,9 +55,10 @@
    2.18  struct KDNode {
    2.19  	int axis;
    2.20  	float pt;
    2.21 +	AABBox aabb;
    2.22  
    2.23  	KDNode *left, *right;
    2.24 -	std::list<Face*> faces;
    2.25 +	std::list<const Face*> faces;
    2.26  };
    2.27  
    2.28  struct KDNodeGPU {