1.1 --- a/src/clray.cc	Tue Aug 17 01:19:43 2010 +0100
     1.2 +++ b/src/clray.cc	Tue Aug 17 20:35:00 2010 +0100
     1.3 @@ -1,6 +1,7 @@
     1.4  #include <stdio.h>
     1.5  #include <stdlib.h>
     1.6  #include <string.h>
     1.7 +#include <ctype.h>
     1.8  #include <errno.h>
     1.9  #ifndef __APPLE__
    1.10  #include <GL/glut.h>
    1.11 @@ -25,7 +26,9 @@
    1.12  static float cam_theta, cam_phi = 25.0;
    1.13  static float cam_dist = 10.0;
    1.14  
    1.15 -static bool dbg_glrender = false;
    1.16 +static bool dbg_glrender = true;
    1.17 +static bool dbg_show_kdtree = false;
    1.18 +static bool dbg_show_obj = true;
    1.19  
    1.20  static Scene scn;
    1.21  
    1.22 @@ -36,11 +39,46 @@
    1.23  
    1.24  	int loaded = 0;
    1.25  	for(int i=1; i<argc; i++) {
    1.26 -		if(!scn.load(argv[i])) {
    1.27 -			fprintf(stderr, "failed to load scene: %s\n", argv[i]);
    1.28 -			return false;
    1.29 +		if(argv[i][0] == '-' && argv[i][2] == 0) {
    1.30 +			switch(argv[i][1]) {
    1.31 +			case 'i':
    1.32 +				if(!argv[++i] || !isdigit(argv[i][0])) {
    1.33 +					fprintf(stderr, "-i must be followed by the intersection cost\n");
    1.34 +					return 1;
    1.35 +				}
    1.36 +
    1.37 +				set_accel_param(ACCEL_PARAM_COST_INTERSECT, atoi(argv[i]));
    1.38 +				break;
    1.39 +
    1.40 +			case 't':
    1.41 +				if(!argv[++i] || !isdigit(argv[i][0])) {
    1.42 +					fprintf(stderr, "-t must be followed by the traversal cost\n");
    1.43 +					return 1;
    1.44 +				}
    1.45 +
    1.46 +				set_accel_param(ACCEL_PARAM_COST_TRAVERSE, atoi(argv[i]));
    1.47 +				break;
    1.48 +
    1.49 +			case 'c':
    1.50 +				if(!argv[++i] || !isdigit(argv[i][0])) {
    1.51 +					fprintf(stderr, "-c must be followed by the max number of items per leaf node\n");
    1.52 +					return 1;
    1.53 +				}
    1.54 +
    1.55 +				set_accel_param(ACCEL_PARAM_MAX_NODE_ITEMS, atoi(argv[i]));
    1.56 +				break;
    1.57 +
    1.58 +			default:
    1.59 +				fprintf(stderr, "unrecognized option: %s\n", argv[i]);
    1.60 +				return 1;
    1.61 +			}
    1.62 +		} else {
    1.63 +			if(!scn.load(argv[i])) {
    1.64 +				fprintf(stderr, "failed to load scene: %s\n", argv[i]);
    1.65 +				return false;
    1.66 +			}
    1.67 +			loaded++;
    1.68  		}
    1.69 -		loaded++;
    1.70  	}
    1.71  
    1.72  	if(!loaded) {
    1.73 @@ -69,6 +107,11 @@
    1.74  	}
    1.75  	atexit(cleanup);
    1.76  
    1.77 +	if(!scn.build_kdtree()) {
    1.78 +		return 1;
    1.79 +	}
    1.80 +
    1.81 +
    1.82  	/*glGenTextures(1, &tex);
    1.83  	glBindTexture(GL_TEXTURE_2D, tex);*/
    1.84  	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
    1.85 @@ -125,7 +168,7 @@
    1.86  	if(dbg_glrender) {
    1.87  		glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    1.88  		glLoadMatrixf(inv_mat.m);
    1.89 -		dbg_render_gl(&scn);
    1.90 +		dbg_render_gl(&scn, dbg_show_kdtree, dbg_show_obj);
    1.91  	} else {
    1.92  		glEnable(GL_TEXTURE_2D);
    1.93  		glDisable(GL_LIGHTING);
    1.94 @@ -175,6 +218,20 @@
    1.95  		glutPostRedisplay();
    1.96  		break;
    1.97  
    1.98 +	case 'k':
    1.99 +		dbg_show_kdtree = !dbg_show_kdtree;
   1.100 +		if(dbg_glrender) {
   1.101 +			glutPostRedisplay();
   1.102 +		}
   1.103 +		break;
   1.104 +
   1.105 +	case 'o':
   1.106 +		dbg_show_obj = !dbg_show_obj;
   1.107 +		if(dbg_glrender) {
   1.108 +			glutPostRedisplay();
   1.109 +		}
   1.110 +		break;
   1.111 +
   1.112  	default:
   1.113  		break;
   1.114  	}

     2.1 --- a/src/rt.cc	Tue Aug 17 01:19:43 2010 +0100
     2.2 +++ b/src/rt.cc	Tue Aug 17 20:35:00 2010 +0100
     2.3 @@ -135,6 +135,7 @@
     2.4  	return true;
     2.5  }
     2.6  
     2.7 +#define MIN(a, b)	((a) < (b) ? (a) : (b))
     2.8  static void dbg_set_gl_material(Material *mat)
     2.9  {
    2.10  	static Material def_mat = {{0.7, 0.7, 0.7, 1}, {0, 0, 0, 0}, 0, 0, 0};
    2.11 @@ -143,10 +144,10 @@
    2.12  
    2.13  	glMaterialfv(GL_FRONT_AND_BACK, GL_AMBIENT_AND_DIFFUSE, mat->kd);
    2.14  	glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, mat->ks);
    2.15 -	glMaterialf(GL_FRONT_AND_BACK, GL_SHININESS, mat->spow);
    2.16 +	glMaterialf(GL_FRONT_AND_BACK, GL_SHININESS, MIN(mat->spow, 128.0f));
    2.17  }
    2.18  
    2.19 -void dbg_render_gl(Scene *scn)
    2.20 +void dbg_render_gl(Scene *scn, bool show_tree, bool show_obj)
    2.21  {
    2.22  	glPushAttrib(GL_ENABLE_BIT | GL_TRANSFORM_BIT | GL_LIGHTING_BIT);
    2.23  
    2.24 @@ -170,27 +171,33 @@
    2.25  	glLoadIdentity();
    2.26  	gluPerspective(45.0, (float)rinf.xsz / (float)rinf.ysz, 0.5, 1000.0);
    2.27  
    2.28 -	Material *materials = scn->get_materials();
    2.29 +	if(show_obj) {
    2.30 +		Material *materials = scn->get_materials();
    2.31  
    2.32 -	int num_faces = scn->get_num_faces();
    2.33 -	int cur_mat = -1;
    2.34 +		int num_faces = scn->get_num_faces();
    2.35 +		int cur_mat = -1;
    2.36  
    2.37 -	for(int i=0; i<num_faces; i++) {
    2.38 -		if(faces[i].matid != cur_mat) {
    2.39 -			if(cur_mat != -1) {
    2.40 -				glEnd();
    2.41 +		for(int i=0; i<num_faces; i++) {
    2.42 +			if(faces[i].matid != cur_mat) {
    2.43 +				if(cur_mat != -1) {
    2.44 +					glEnd();
    2.45 +				}
    2.46 +				dbg_set_gl_material(materials ? materials + faces[i].matid : 0);
    2.47 +				cur_mat = faces[i].matid;
    2.48 +				glBegin(GL_TRIANGLES);
    2.49  			}
    2.50 -			dbg_set_gl_material(materials ? materials + faces[i].matid : 0);
    2.51 -			cur_mat = faces[i].matid;
    2.52 -			glBegin(GL_TRIANGLES);
    2.53 +
    2.54 +			for(int j=0; j<3; j++) {
    2.55 +				glNormal3fv(faces[i].v[j].normal);
    2.56 +				glVertex3fv(faces[i].v[j].pos);
    2.57 +			}
    2.58  		}
    2.59 +		glEnd();
    2.60 +	}
    2.61  
    2.62 -		for(int j=0; j<3; j++) {
    2.63 -			glNormal3fv(faces[i].v[j].normal);
    2.64 -			glVertex3fv(faces[i].v[j].pos);
    2.65 -		}
    2.66 +	if(show_tree) {
    2.67 +		scn->draw_kdtree();
    2.68  	}
    2.69 -	glEnd();
    2.70  
    2.71  	glPopMatrix();
    2.72  	glPopAttrib();

     3.1 --- a/src/rt.h	Tue Aug 17 01:19:43 2010 +0100
     3.2 +++ b/src/rt.h	Tue Aug 17 20:35:00 2010 +0100
     3.3 @@ -8,6 +8,6 @@
     3.4  bool render();
     3.5  void set_xform(float *matrix, float *invtrans);
     3.6  
     3.7 -void dbg_render_gl(Scene *scn);
     3.8 +void dbg_render_gl(Scene *scn, bool show_tree = false, bool show_obj = true);
     3.9  
    3.10  #endif	/* RT_H_ */

     4.1 --- a/src/scene.cc	Tue Aug 17 01:19:43 2010 +0100
     4.2 +++ b/src/scene.cc	Tue Aug 17 20:35:00 2010 +0100
     4.3 @@ -2,11 +2,15 @@
     4.4  #include <float.h>
     4.5  #include <assert.h>
     4.6  #include "scene.h"
     4.7 +#include "ogl.h"
     4.8  
     4.9  
    4.10 -static int build_kdtree(KDNode *kd);
    4.11 -static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis);
    4.12 +static void draw_kdtree(const KDNode *node, int level = 0);
    4.13 +static bool build_kdtree(KDNode *kd, int level = 0);
    4.14 +static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis, float par_sarea = 1.0);
    4.15  static void free_kdtree(KDNode *node);
    4.16 +static int kdtree_depth(const KDNode *node);
    4.17 +static void print_item_counts(const KDNode *node, int level);
    4.18  
    4.19  
    4.20  static int accel_param[NUM_ACCEL_PARAMS] = {
    4.21 @@ -155,13 +159,91 @@
    4.22  }
    4.23  
    4.24  
    4.25 -void Scene::build_kdtree()
    4.26 +void Scene::draw_kdtree() const
    4.27 +{
    4.28 +	glPushAttrib(GL_ENABLE_BIT);
    4.29 +	glDisable(GL_LIGHTING);
    4.30 +	glDepthMask(0);
    4.31 +
    4.32 +	glBegin(GL_LINES);
    4.33 +	::draw_kdtree(kdtree, 0);
    4.34 +	glEnd();
    4.35 +
    4.36 +	glDepthMask(1);
    4.37 +	glPopAttrib();
    4.38 +}
    4.39 +
    4.40 +static float palette[][3] = {
    4.41 +	{0, 1, 0},
    4.42 +	{0, 1, 0},
    4.43 +	{0, 1, 0},
    4.44 +	{1, 0, 0},
    4.45 +	{1, 0, 0},
    4.46 +	{1, 0, 0},
    4.47 +	{0, 0, 1},
    4.48 +	{0, 0, 1},
    4.49 +	{0, 0, 1},
    4.50 +	{1, 1, 0},
    4.51 +	{1, 1, 0},
    4.52 +	{1, 1, 0},
    4.53 +	{0, 0, 1},
    4.54 +	{0, 0, 1},
    4.55 +	{0, 0, 1},
    4.56 +	{1, 0, 1},
    4.57 +	{1, 0, 1},
    4.58 +	{1, 0, 1}
    4.59 +};
    4.60 +static int pal_size = sizeof palette / sizeof *palette;
    4.61 +
    4.62 +static void draw_kdtree(const KDNode *node, int level)
    4.63 +{
    4.64 +	if(!node) return;
    4.65 +
    4.66 +	draw_kdtree(node->left, level + 1);
    4.67 +	draw_kdtree(node->right, level + 1);
    4.68 +
    4.69 +	glColor3fv(palette[level % pal_size]);
    4.70 +
    4.71 +	glVertex3fv(node->aabb.min);
    4.72 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
    4.73 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
    4.74 +	glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
    4.75 +	glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
    4.76 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
    4.77 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
    4.78 +	glVertex3fv(node->aabb.min);
    4.79 +
    4.80 +	glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
    4.81 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
    4.82 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
    4.83 +	glVertex3fv(node->aabb.max);
    4.84 +	glVertex3fv(node->aabb.max);
    4.85 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
    4.86 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
    4.87 +	glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
    4.88 +
    4.89 +	glVertex3fv(node->aabb.min);
    4.90 +	glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
    4.91 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
    4.92 +	glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
    4.93 +	glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
    4.94 +	glVertex3fv(node->aabb.max);
    4.95 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
    4.96 +	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
    4.97 +}
    4.98 +
    4.99 +bool Scene::build_kdtree()
   4.100  {
   4.101  	const Face *faces = get_face_buffer();
   4.102  	int num_faces = get_num_faces();
   4.103  
   4.104  	printf("Constructing kd-tree out of %d faces ...\n", num_faces);
   4.105  
   4.106 +	int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];
   4.107 +	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
   4.108 +	printf("  max items per leaf: %d\n", accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]);
   4.109 +	printf("  SAH parameters - tcost: %d - icost: %d\n", tcost, icost);
   4.110 +
   4.111  	free_kdtree(kdtree);
   4.112  	kdtree = new KDNode;
   4.113  
   4.114 @@ -197,17 +279,27 @@
   4.115  	kdtree->cost = eval_cost(kdtree->faces, kdtree->aabb, kdtree->axis);
   4.116  
   4.117  	// now proceed splitting the root recursively
   4.118 -	::build_kdtree(kdtree);
   4.119 +	if(!::build_kdtree(kdtree)) {
   4.120 +		fprintf(stderr, "failed to build kdtree\n");
   4.121 +		return false;
   4.122 +	}
   4.123 +
   4.124 +	printf("  tree depth: %d\n", kdtree_depth(kdtree));
   4.125 +	print_item_counts(kdtree, 0);
   4.126 +	return true;
   4.127  }
   4.128  
   4.129 -static int build_kdtree(KDNode *kd)
   4.130 +static bool build_kdtree(KDNode *kd, int level)
   4.131  {
   4.132  	int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];
   4.133 -	if(kd->num_faces == 0 || (opt_max_items > 1 && kd->num_faces < opt_max_items)) {
   4.134 -		return 0;
   4.135 +	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
   4.136 +
   4.137 +	if(kd->num_faces == 0) {
   4.138 +		return true;
   4.139  	}
   4.140  
   4.141 -	int axis = (kd->axis + 1) % 3;
   4.142 +	int axis = level % 3;
   4.143 +	//float parent_sa = kd->aabb.calc_surface_area();
   4.144  
   4.145  	float best_cost[2], best_sum_cost = FLT_MAX;
   4.146  	float best_split;
   4.147 @@ -226,7 +318,7 @@
   4.148  
   4.149  			float left_cost = eval_cost(kd->faces, aabb_left, axis);
   4.150  			float right_cost = eval_cost(kd->faces, aabb_right, axis);
   4.151 -			float sum_cost = left_cost + right_cost;
   4.152 +			float sum_cost = left_cost + right_cost - tcost;	// tcost is added twice
   4.153  
   4.154  			if(sum_cost < best_sum_cost) {
   4.155  				best_cost[0] = left_cost;
   4.156 @@ -237,8 +329,9 @@
   4.157  		}
   4.158  	}
   4.159  
   4.160 -	if(best_sum_cost >= kd->cost) {
   4.161 -		return 0;	// stop splitting if it doesn't reduce the cost
   4.162 +	printf("current cost: %f,   best_cost: %f\n", kd->cost, best_sum_cost);
   4.163 +	if(best_sum_cost > kd->cost && (opt_max_items == 0 || kd->num_faces <= opt_max_items)) {
   4.164 +		return true;	// stop splitting if it doesn't reduce the cost
   4.165  	}
   4.166  	kd->pt = best_split;
   4.167  
   4.168 @@ -247,7 +340,6 @@
   4.169  	kdleft = new KDNode;
   4.170  	kdright = new KDNode;
   4.171  
   4.172 -	kdleft->axis = kdright->axis = axis;
   4.173  	kdleft->aabb = kdright->aabb = kd->aabb;
   4.174  
   4.175  	kdleft->aabb.max[axis] = best_split;
   4.176 @@ -256,6 +348,8 @@
   4.177  	kdleft->cost = best_cost[0];
   4.178  	kdright->cost = best_cost[1];
   4.179  
   4.180 +	//kdleft->axis = kdright->axis = (axis + 1) % 3;
   4.181 +
   4.182  	it = kd->faces.begin();
   4.183  	while(it != kd->faces.end()) {
   4.184  		const Face *face = *it++;
   4.185 @@ -273,13 +367,15 @@
   4.186  			kdright->num_faces++;
   4.187  		}
   4.188  	}
   4.189 +	kd->faces.clear();	// only leaves have faces
   4.190  
   4.191  	kd->left = kdleft;
   4.192  	kd->right = kdright;
   4.193 -	return 0;
   4.194 +
   4.195 +	return build_kdtree(kd->left, level + 1) && build_kdtree(kd->right, level + 1);
   4.196  }
   4.197  
   4.198 -static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis)
   4.199 +static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis, float par_sarea)
   4.200  {
   4.201  	int num_inside = 0;
   4.202  	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
   4.203 @@ -297,7 +393,12 @@
   4.204  		}
   4.205  	}
   4.206  
   4.207 -	return tcost + aabb.calc_surface_area() * num_inside * icost;
   4.208 +	float sarea = aabb.calc_surface_area();
   4.209 +	if(sarea < 1e-8) {
   4.210 +		return FLT_MAX;	// heavily penalize 0-area voxels
   4.211 +	}
   4.212 +
   4.213 +	return tcost + (sarea / par_sarea) * num_inside * icost;
   4.214  }
   4.215  
   4.216  static void free_kdtree(KDNode *node)
   4.217 @@ -308,3 +409,25 @@
   4.218  		delete node;
   4.219  	}
   4.220  }
   4.221 +
   4.222 +static int kdtree_depth(const KDNode *node)
   4.223 +{
   4.224 +	if(!node) return 0;
   4.225 +
   4.226 +	int left = kdtree_depth(node->left);
   4.227 +	int right = kdtree_depth(node->right);
   4.228 +	return (left > right ? left : right) + 1;
   4.229 +}
   4.230 +
   4.231 +static void print_item_counts(const KDNode *node, int level)
   4.232 +{
   4.233 +	if(!node) return;
   4.234 +
   4.235 +	for(int i=0; i<level; i++) {
   4.236 +		fputs("   ", stdout);
   4.237 +	}
   4.238 +	printf("- %d (cost: %f)\n", node->num_faces, node->cost);
   4.239 +
   4.240 +	print_item_counts(node->left, level + 1);
   4.241 +	print_item_counts(node->right, level + 1);
   4.242 +}

     5.1 --- a/src/scene.h	Tue Aug 17 01:19:43 2010 +0100
     5.2 +++ b/src/scene.h	Tue Aug 17 20:35:00 2010 +0100
     5.3 @@ -98,7 +98,9 @@
     5.4  	bool load(FILE *fp);
     5.5  
     5.6  	const Face *get_face_buffer() const;
     5.7 -	void build_kdtree();
     5.8 +
     5.9 +	void draw_kdtree() const;
    5.10 +	bool build_kdtree();
    5.11  };
    5.12  
    5.13  enum {