1.1 --- a/src/scene.cc	Tue Aug 17 01:19:43 2010 +0100
     1.2 +++ b/src/scene.cc	Tue Aug 17 20:35:00 2010 +0100
     1.3 @@ -2,11 +2,15 @@
     1.4  #include <float.h>
     1.5  #include <assert.h>
     1.6  #include "scene.h"
     1.7 +#include "ogl.h"
     1.8  
     1.9  
    1.10 -static int build_kdtree(KDNode *kd);
    1.11 -static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis);
    1.12 +static void draw_kdtree(const KDNode *node, int level = 0);
    1.13 +static bool build_kdtree(KDNode *kd, int level = 0);
    1.14 +static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis, float par_sarea = 1.0);
    1.15  static void free_kdtree(KDNode *node);
    1.16 +static int kdtree_depth(const KDNode *node);
    1.17 +static void print_item_counts(const KDNode *node, int level);
    1.18  
    1.19  
    1.20  static int accel_param[NUM_ACCEL_PARAMS] = {
    1.21 @@ -155,13 +159,91 @@
    1.22  }
    1.23  
    1.24  
    1.25 -void Scene::build_kdtree()
    1.26 +void Scene::draw_kdtree() const
    1.27 +{
    1.28 +	glPushAttrib(GL_ENABLE_BIT);
    1.29 +	glDisable(GL_LIGHTING);
    1.30 +	glDepthMask(0);
    1.31 +
    1.32 +	glBegin(GL_LINES);
    1.33 +	::draw_kdtree(kdtree, 0);
    1.34 +	glEnd();
    1.35 +
    1.36 +	glDepthMask(1);
    1.37 +	glPopAttrib();
    1.38 +}
    1.39 +
    1.40 +static float palette[][3] = {
    1.41 +	{0, 1, 0},
    1.42 +	{0, 1, 0},
    1.43 +	{0, 1, 0},
    1.44 +	{1, 0, 0},
    1.45 +	{1, 0, 0},
    1.46 +	{1, 0, 0},
    1.47 +	{0, 0, 1},
    1.48 +	{0, 0, 1},
    1.49 +	{0, 0, 1},
    1.50 +	{1, 1, 0},
    1.51 +	{1, 1, 0},
    1.52 +	{1, 1, 0},
    1.53 +	{0, 0, 1},
    1.54 +	{0, 0, 1},
    1.55 +	{0, 0, 1},
    1.56 +	{1, 0, 1},
    1.57 +	{1, 0, 1},
    1.58 +	{1, 0, 1}
    1.59 +};
    1.60 +static int pal_size = sizeof palette / sizeof *palette;
    1.61 +
    1.62 +static void draw_kdtree(const KDNode *node, int level)
    1.63 +{
    1.64 +	if(!node) return;
    1.65 +
    1.66 +	draw_kdtree(node->left, level + 1);
    1.67 +	draw_kdtree(node->right, level + 1);
    1.68 +
    1.69 +	glColor3fv(palette[level % pal_size]);
    1.70 +
    1.71 +	glVertex3fv(node->aabb.min);
    1.72 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
    1.73 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
    1.74 +	glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
    1.75 +	glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
    1.76 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
    1.77 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
    1.78 +	glVertex3fv(node->aabb.min);
    1.79 +
    1.80 +	glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
    1.81 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
    1.82 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
    1.83 +	glVertex3fv(node->aabb.max);
    1.84 +	glVertex3fv(node->aabb.max);
    1.85 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
    1.86 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
    1.87 +	glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
    1.88 +
    1.89 +	glVertex3fv(node->aabb.min);
    1.90 +	glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
    1.91 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
    1.92 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
    1.93 +	glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
    1.94 +	glVertex3fv(node->aabb.max);
    1.95 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
    1.96 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
    1.97 +}
    1.98 +
    1.99 +bool Scene::build_kdtree()
   1.100  {
   1.101  	const Face *faces = get_face_buffer();
   1.102  	int num_faces = get_num_faces();
   1.103  
   1.104  	printf("Constructing kd-tree out of %d faces ...\n", num_faces);
   1.105  
   1.106 +	int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];
   1.107 +	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
   1.108 +	printf("  max items per leaf: %d\n", accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]);
   1.109 +	printf("  SAH parameters - tcost: %d - icost: %d\n", tcost, icost);
   1.110 +
   1.111  	free_kdtree(kdtree);
   1.112  	kdtree = new KDNode;
   1.113  
   1.114 @@ -197,17 +279,27 @@
   1.115  	kdtree->cost = eval_cost(kdtree->faces, kdtree->aabb, kdtree->axis);
   1.116  
   1.117  	// now proceed splitting the root recursively
   1.118 -	::build_kdtree(kdtree);
   1.119 +	if(!::build_kdtree(kdtree)) {
   1.120 +		fprintf(stderr, "failed to build kdtree\n");
   1.121 +		return false;
   1.122 +	}
   1.123 +
   1.124 +	printf("  tree depth: %d\n", kdtree_depth(kdtree));
   1.125 +	print_item_counts(kdtree, 0);
   1.126 +	return true;
   1.127  }
   1.128  
   1.129 -static int build_kdtree(KDNode *kd)
   1.130 +static bool build_kdtree(KDNode *kd, int level)
   1.131  {
   1.132  	int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];
   1.133 -	if(kd->num_faces == 0 || (opt_max_items > 1 && kd->num_faces < opt_max_items)) {
   1.134 -		return 0;
   1.135 +	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
   1.136 +
   1.137 +	if(kd->num_faces == 0) {
   1.138 +		return true;
   1.139  	}
   1.140  
   1.141 -	int axis = (kd->axis + 1) % 3;
   1.142 +	int axis = level % 3;
   1.143 +	//float parent_sa = kd->aabb.calc_surface_area();
   1.144  
   1.145  	float best_cost[2], best_sum_cost = FLT_MAX;
   1.146  	float best_split;
   1.147 @@ -226,7 +318,7 @@
   1.148  
   1.149  			float left_cost = eval_cost(kd->faces, aabb_left, axis);
   1.150  			float right_cost = eval_cost(kd->faces, aabb_right, axis);
   1.151 -			float sum_cost = left_cost + right_cost;
   1.152 +			float sum_cost = left_cost + right_cost - tcost;	// tcost is added twice
   1.153  
   1.154  			if(sum_cost < best_sum_cost) {
   1.155  				best_cost[0] = left_cost;
   1.156 @@ -237,8 +329,9 @@
   1.157  		}
   1.158  	}
   1.159  
   1.160 -	if(best_sum_cost >= kd->cost) {
   1.161 -		return 0;	// stop splitting if it doesn't reduce the cost
   1.162 +	printf("current cost: %f,   best_cost: %f\n", kd->cost, best_sum_cost);
   1.163 +	if(best_sum_cost > kd->cost && (opt_max_items == 0 || kd->num_faces <= opt_max_items)) {
   1.164 +		return true;	// stop splitting if it doesn't reduce the cost
   1.165  	}
   1.166  	kd->pt = best_split;
   1.167  
   1.168 @@ -247,7 +340,6 @@
   1.169  	kdleft = new KDNode;
   1.170  	kdright = new KDNode;
   1.171  
   1.172 -	kdleft->axis = kdright->axis = axis;
   1.173  	kdleft->aabb = kdright->aabb = kd->aabb;
   1.174  
   1.175  	kdleft->aabb.max[axis] = best_split;
   1.176 @@ -256,6 +348,8 @@
   1.177  	kdleft->cost = best_cost[0];
   1.178  	kdright->cost = best_cost[1];
   1.179  
   1.180 +	//kdleft->axis = kdright->axis = (axis + 1) % 3;
   1.181 +
   1.182  	it = kd->faces.begin();
   1.183  	while(it != kd->faces.end()) {
   1.184  		const Face *face = *it++;
   1.185 @@ -273,13 +367,15 @@
   1.186  			kdright->num_faces++;
   1.187  		}
   1.188  	}
   1.189 +	kd->faces.clear();	// only leaves have faces
   1.190  
   1.191  	kd->left = kdleft;
   1.192  	kd->right = kdright;
   1.193 -	return 0;
   1.194 +
   1.195 +	return build_kdtree(kd->left, level + 1) && build_kdtree(kd->right, level + 1);
   1.196  }
   1.197  
   1.198 -static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis)
   1.199 +static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis, float par_sarea)
   1.200  {
   1.201  	int num_inside = 0;
   1.202  	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
   1.203 @@ -297,7 +393,12 @@
   1.204  		}
   1.205  	}
   1.206  
   1.207 -	return tcost + aabb.calc_surface_area() * num_inside * icost;
   1.208 +	float sarea = aabb.calc_surface_area();
   1.209 +	if(sarea < 1e-8) {
   1.210 +		return FLT_MAX;	// heavily penalize 0-area voxels
   1.211 +	}
   1.212 +
   1.213 +	return tcost + (sarea / par_sarea) * num_inside * icost;
   1.214  }
   1.215  
   1.216  static void free_kdtree(KDNode *node)
   1.217 @@ -308,3 +409,25 @@
   1.218  		delete node;
   1.219  	}
   1.220  }
   1.221 +
   1.222 +static int kdtree_depth(const KDNode *node)
   1.223 +{
   1.224 +	if(!node) return 0;
   1.225 +
   1.226 +	int left = kdtree_depth(node->left);
   1.227 +	int right = kdtree_depth(node->right);
   1.228 +	return (left > right ? left : right) + 1;
   1.229 +}
   1.230 +
   1.231 +static void print_item_counts(const KDNode *node, int level)
   1.232 +{
   1.233 +	if(!node) return;
   1.234 +
   1.235 +	for(int i=0; i<level; i++) {
   1.236 +		fputs("   ", stdout);
   1.237 +	}
   1.238 +	printf("- %d (cost: %f)\n", node->num_faces, node->cost);
   1.239 +
   1.240 +	print_item_counts(node->left, level + 1);
   1.241 +	print_item_counts(node->right, level + 1);
   1.242 +}