1.1 --- a/src/scene.cc	Thu Aug 26 20:33:27 2010 +0100
     1.2 +++ b/src/scene.cc	Fri Aug 27 01:00:04 2010 +0100
     1.3 @@ -7,6 +7,10 @@
     1.4  #include "ogl.h"
     1.5  
     1.6  
     1.7 +#define MIN(a, b)	((a) < (b) ? (a) : (b))
     1.8 +#define MAX(a, b)	((a) > (b) ? (a) : (b))
     1.9 +
    1.10 +
    1.11  static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap);
    1.12  static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap);
    1.13  static void draw_kdtree(const KDNode *node, int level = 0);
    1.14 @@ -341,7 +345,7 @@
    1.15  		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
    1.16  		glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);
    1.17  		break;
    1.18 -	
    1.19 +
    1.20  	case 1:
    1.21  		glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
    1.22  		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
    1.23 @@ -352,7 +356,7 @@
    1.24  		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
    1.25  		glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
    1.26  		break;
    1.27 -	
    1.28 +
    1.29  	case 2:
    1.30  		glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);
    1.31  		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
    1.32 @@ -427,47 +431,74 @@
    1.33  	return true;
    1.34  }
    1.35  
    1.36 +struct Split {
    1.37 +	int axis;
    1.38 +	float pos;
    1.39 +	float sum_cost;
    1.40 +	float cost_left, cost_right;
    1.41 +};
    1.42 +
    1.43 +static void find_best_split(const KDNode *node, int axis, const Face *faces, Split *split)
    1.44 +{
    1.45 +	Split best_split;
    1.46 +	best_split.sum_cost = FLT_MAX;
    1.47 +
    1.48 +	for(size_t i=0; i<node->face_idx.size(); i++) {
    1.49 +		const Face *face = faces + node->face_idx[i];
    1.50 +
    1.51 +		float splitpt[2];
    1.52 +		splitpt[0] = MIN(face->v[0].pos[axis], MIN(face->v[1].pos[axis], face->v[2].pos[axis]));
    1.53 +		splitpt[1] = MAX(face->v[0].pos[axis], MAX(face->v[1].pos[axis], face->v[2].pos[axis]));
    1.54 +
    1.55 +		for(int j=0; j<2; j++) {
    1.56 +			AABBox aabb_left, aabb_right;
    1.57 +			aabb_left = aabb_right = node->aabb;
    1.58 +			aabb_left.max[axis] = splitpt[j];
    1.59 +			aabb_right.min[axis] = splitpt[j];
    1.60 +
    1.61 +			float left_cost = eval_cost(faces, &node->face_idx[0], node->face_idx.size(), aabb_left, axis);
    1.62 +			float right_cost = eval_cost(faces, &node->face_idx[0], node->face_idx.size(), aabb_right, axis);
    1.63 +			float sum_cost = left_cost + right_cost - accel_param[ACCEL_PARAM_COST_TRAVERSE]; // tcost is added twice
    1.64 +
    1.65 +			if(sum_cost < best_split.sum_cost) {
    1.66 +				best_split.cost_left = left_cost;
    1.67 +				best_split.cost_right = right_cost;
    1.68 +				best_split.sum_cost = sum_cost;
    1.69 +				best_split.pos = splitpt[j];
    1.70 +			}
    1.71 +		}
    1.72 +	}
    1.73 +
    1.74 +	assert(split);
    1.75 +	*split = best_split;
    1.76 +	split->axis = axis;
    1.77 +}
    1.78 +
    1.79  static bool build_kdtree(KDNode *kd, const Face *faces, int level)
    1.80  {
    1.81  	int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];
    1.82  	int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];
    1.83 -	int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
    1.84  
    1.85  	if(kd->face_idx.empty() || level >= opt_max_depth) {
    1.86  		return true;
    1.87  	}
    1.88  
    1.89 -	int axis = level % 3;
    1.90 +	Split best_split;
    1.91 +	best_split.sum_cost = FLT_MAX;
    1.92  
    1.93 -	float best_cost[2], best_sum_cost = FLT_MAX;
    1.94 -	float best_split;
    1.95 +	for(int i=0; i<1; i++) {
    1.96 +		Split split;
    1.97 +		find_best_split(kd, i, faces, &split);
    1.98  
    1.99 -	for(size_t i=0; i<kd->face_idx.size(); i++) {
   1.100 -		const Face *face = faces + kd->face_idx[i];
   1.101 -
   1.102 -		for(int j=0; j<3; j++) {
   1.103 -			AABBox aabb_left, aabb_right;
   1.104 -			const float *split = face->v[j].pos;
   1.105 -
   1.106 -			aabb_left = aabb_right = kd->aabb;
   1.107 -			aabb_left.max[axis] = split[axis];
   1.108 -			aabb_right.min[axis] = split[axis];
   1.109 -
   1.110 -			float left_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_left, axis);
   1.111 -			float right_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_right, axis);
   1.112 -			float sum_cost = left_cost + right_cost - tcost;	// tcost is added twice
   1.113 -
   1.114 -			if(sum_cost < best_sum_cost) {
   1.115 -				best_cost[0] = left_cost;
   1.116 -				best_cost[1] = right_cost;
   1.117 -				best_sum_cost = sum_cost;
   1.118 -				best_split = split[axis];
   1.119 -			}
   1.120 +		if(split.sum_cost < best_split.sum_cost) {
   1.121 +			best_split = split;
   1.122  		}
   1.123  	}
   1.124  
   1.125 +	kd->axis = best_split.axis;
   1.126 +
   1.127  	//printf("current cost: %f,   best_cost: %f\n", kd->cost, best_sum_cost);
   1.128 -	if(best_sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) {
   1.129 +	if(best_split.sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) {
   1.130  		return true;	// stop splitting if it doesn't reduce the cost
   1.131  	}
   1.132  
   1.133 @@ -478,25 +509,25 @@
   1.134  
   1.135  	kdleft->aabb = kdright->aabb = kd->aabb;
   1.136  
   1.137 -	kdleft->aabb.max[axis] = best_split;
   1.138 -	kdright->aabb.min[axis] = best_split;
   1.139 +	kdleft->aabb.max[kd->axis] = best_split.pos;
   1.140 +	kdright->aabb.min[kd->axis] = best_split.pos;
   1.141  
   1.142 -	kdleft->cost = best_cost[0];
   1.143 -	kdright->cost = best_cost[1];
   1.144 +	kdleft->cost = best_split.cost_left;
   1.145 +	kdright->cost = best_split.cost_right;
   1.146  
   1.147  	// TODO would it be much better if we actually split faces that straddle the splitting plane?
   1.148  	for(size_t i=0; i<kd->face_idx.size(); i++) {
   1.149  		int fidx = kd->face_idx[i];
   1.150  		const Face *face = faces + fidx;
   1.151  
   1.152 -		if(face->v[0].pos[axis] < best_split ||
   1.153 -				face->v[1].pos[axis] < best_split ||
   1.154 -				face->v[2].pos[axis] < best_split) {
   1.155 +		if(face->v[0].pos[kd->axis] < best_split.pos ||
   1.156 +				face->v[1].pos[kd->axis] < best_split.pos ||
   1.157 +				face->v[2].pos[kd->axis] < best_split.pos) {
   1.158  			kdleft->face_idx.push_back(fidx);
   1.159  		}
   1.160 -		if(face->v[0].pos[axis] >= best_split ||
   1.161 -				face->v[1].pos[axis] >= best_split ||
   1.162 -				face->v[2].pos[axis] >= best_split) {
   1.163 +		if(face->v[0].pos[kd->axis] >= best_split.pos ||
   1.164 +				face->v[1].pos[kd->axis] >= best_split.pos ||
   1.165 +				face->v[2].pos[kd->axis] >= best_split.pos) {
   1.166  			kdright->face_idx.push_back(fidx);
   1.167  		}
   1.168  	}