1.1 --- a/src/scene.cc	Tue Aug 17 20:35:00 2010 +0100
     1.2 +++ b/src/scene.cc	Sat Aug 21 03:42:49 2010 +0100
     1.3 @@ -9,12 +9,12 @@
     1.4  static bool build_kdtree(KDNode *kd, int level = 0);
     1.5  static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis, float par_sarea = 1.0);
     1.6  static void free_kdtree(KDNode *node);
     1.7 -static int kdtree_depth(const KDNode *node);
     1.8 +static void kdtree_gpu_flatten(KDNodeGPU *kdbuf, int idx, const KDNode *node, const Face *facebuf);
     1.9  static void print_item_counts(const KDNode *node, int level);
    1.10  
    1.11  
    1.12  static int accel_param[NUM_ACCEL_PARAMS] = {
    1.13 -	75,	// max tree depth
    1.14 +	40,	// max tree depth
    1.15  	0,	// max items per node (0 means ignore limit)
    1.16  	5,	// estimated traversal cost
    1.17  	15	// estimated interseciton cost
    1.18 @@ -70,11 +70,15 @@
    1.19  	facebuf = 0;
    1.20  	num_faces = -1;
    1.21  	kdtree = 0;
    1.22 +	num_kdnodes = -1;
    1.23 +	kdbuf = 0;
    1.24  }
    1.25  
    1.26  Scene::~Scene()
    1.27  {
    1.28  	delete [] facebuf;
    1.29 +	delete [] kdbuf;
    1.30 +	free_kdtree(kdtree);
    1.31  }
    1.32  
    1.33  bool Scene::add_mesh(Mesh *m)
    1.34 @@ -158,6 +162,35 @@
    1.35  	return facebuf;
    1.36  }
    1.37  
    1.38 +const KDNodeGPU *Scene::get_kdtree_buffer() const
    1.39 +{
    1.40 +	if(kdbuf) {
    1.41 +		return kdbuf;
    1.42 +	}
    1.43 +
    1.44 +	if(!kdtree) {
    1.45 +		((Scene*)this)->build_kdtree();
    1.46 +	}
    1.47 +
    1.48 +	if(!get_num_kdnodes()) {
    1.49 +		return 0;
    1.50 +	}
    1.51 +
    1.52 +	kdbuf = new KDNodeGPU[num_kdnodes + 1];
    1.53 +	kdtree_gpu_flatten(kdbuf, 1, kdtree, get_face_buffer());
    1.54 +	return kdbuf;
    1.55 +}
    1.56 +
    1.57 +int Scene::get_num_kdnodes() const
    1.58 +{
    1.59 +	if(num_kdnodes >= 0) {
    1.60 +		return num_kdnodes;
    1.61 +	}
    1.62 +
    1.63 +	num_kdnodes = kdtree_nodes(kdtree);
    1.64 +	return num_kdnodes;
    1.65 +}
    1.66 +
    1.67  
    1.68  void Scene::draw_kdtree() const
    1.69  {
    1.70 @@ -175,22 +208,10 @@
    1.71  
    1.72  static float palette[][3] = {
    1.73  	{0, 1, 0},
    1.74 -	{0, 1, 0},
    1.75 -	{0, 1, 0},
    1.76 -	{1, 0, 0},
    1.77 -	{1, 0, 0},
    1.78  	{1, 0, 0},
    1.79  	{0, 0, 1},
    1.80 -	{0, 0, 1},
    1.81 -	{0, 0, 1},
    1.82 -	{1, 1, 0},
    1.83 -	{1, 1, 0},
    1.84  	{1, 1, 0},
    1.85  	{0, 0, 1},
    1.86 -	{0, 0, 1},
    1.87 -	{0, 0, 1},
    1.88 -	{1, 0, 1},
    1.89 -	{1, 0, 1},
    1.90  	{1, 0, 1}
    1.91  };
    1.92  static int pal_size = sizeof palette / sizeof *palette;
    1.93 @@ -291,10 +312,11 @@
    1.94  
    1.95  static bool build_kdtree(KDNode *kd, int level)
    1.96  {
    1.97 +	int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];
    1.98  	int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];
    1.99  	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
   1.100  
   1.101 -	if(kd->num_faces == 0) {
   1.102 +	if(kd->num_faces == 0 || level >= opt_max_depth) {
   1.103  		return true;
   1.104  	}
   1.105  
   1.106 @@ -410,7 +432,7 @@
   1.107  	}
   1.108  }
   1.109  
   1.110 -static int kdtree_depth(const KDNode *node)
   1.111 +int kdtree_depth(const KDNode *node)
   1.112  {
   1.113  	if(!node) return 0;
   1.114  
   1.115 @@ -419,6 +441,36 @@
   1.116  	return (left > right ? left : right) + 1;
   1.117  }
   1.118  
   1.119 +int kdtree_nodes(const KDNode *node)
   1.120 +{
   1.121 +	if(!node) return 0;
   1.122 +	return kdtree_nodes(node->left) + kdtree_nodes(node->right) + 1;
   1.123 +}
   1.124 +
   1.125 +#define MAX_FACES	(sizeof dest->face_idx / sizeof *dest->face_idx)
   1.126 +static void kdtree_gpu_flatten(KDNodeGPU *kdbuf, int idx, const KDNode *node, const Face *facebuf)
   1.127 +{
   1.128 +	KDNodeGPU *dest = kdbuf + idx;
   1.129 +
   1.130 +	dest->aabb = node->aabb;
   1.131 +	dest->num_faces = 0;
   1.132 +
   1.133 +	std::list<const Face*>::const_iterator it = node->faces.begin();
   1.134 +	while(it != node->faces.end()) {
   1.135 +		if(dest->num_faces >= (int)MAX_FACES) {
   1.136 +			fprintf(stderr, "kdtree_gpu_flatten WARNING: more than %d faces in node, skipping!\n", (int)MAX_FACES);
   1.137 +			break;
   1.138 +		}
   1.139 +		dest->face_idx[dest->num_faces++] = *it - facebuf;
   1.140 +	}
   1.141 +
   1.142 +	if(node->left) {
   1.143 +		assert(node->right);
   1.144 +		kdtree_gpu_flatten(kdbuf, idx * 2, node->left, facebuf);
   1.145 +		kdtree_gpu_flatten(kdbuf, idx * 2 + 1, node->right, facebuf);
   1.146 +	}
   1.147 +}
   1.148 +
   1.149  static void print_item_counts(const KDNode *node, int level)
   1.150  {
   1.151  	if(!node) return;