clray

changeset 38:4bcf78e572d6

fixed the damned kdtree
author John Tsiombikas <nuclear@member.fsf.org>
date Fri, 27 Aug 2010 02:22:08 +0100
parents ca445da26588
children 980bc07be868
files src/scene.cc
diffstat 1 files changed, 43 insertions(+), 5 deletions(-) [+]
line diff
     1.1 --- a/src/scene.cc	Fri Aug 27 01:00:04 2010 +0100
     1.2 +++ b/src/scene.cc	Fri Aug 27 02:22:08 2010 +0100
     1.3 @@ -6,6 +6,9 @@
     1.4  #include "scene.h"
     1.5  #include "ogl.h"
     1.6  
     1.7 +#define CHECK_AABB(aabb)	\
     1.8 +	assert(aabb.max[0] >= aabb.min[0] && aabb.max[1] >= aabb.min[1] && aabb.max[2] >= aabb.min[2])
     1.9 +
    1.10  
    1.11  #define MIN(a, b)	((a) < (b) ? (a) : (b))
    1.12  #define MAX(a, b)	((a) > (b) ? (a) : (b))
    1.13 @@ -227,14 +230,21 @@
    1.14  
    1.15  static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap)
    1.16  {
    1.17 +	const size_t max_node_items = sizeof kdbuf[0].face_idx / sizeof kdbuf[0].face_idx[0];
    1.18  	int idx = (*count)++;
    1.19  
    1.20  	// copy the node
    1.21  	kdbuf[idx].aabb = node->aabb;
    1.22 +	kdbuf[idx].num_faces = 0;
    1.23 +
    1.24  	for(size_t i=0; i<node->face_idx.size(); i++) {
    1.25 +		if(i >= max_node_items) {
    1.26 +			fprintf(stderr, "WARNING too many faces per leaf node!\n");
    1.27 +			break;
    1.28 +		}
    1.29  		kdbuf[idx].face_idx[i] = node->face_idx[i];
    1.30 +		kdbuf[idx].num_faces++;
    1.31  	}
    1.32 -	kdbuf[idx].num_faces = node->face_idx.size();
    1.33  
    1.34  	// update the node* -> array-position mapping
    1.35  	(*flatmap)[node] = idx;
    1.36 @@ -417,6 +427,8 @@
    1.37  		kdtree->face_idx.push_back(i);	// add the face
    1.38  	}
    1.39  
    1.40 +	CHECK_AABB(kdtree->aabb);
    1.41 +
    1.42  	// calculate the heuristic for the root
    1.43  	kdtree->cost = eval_cost(faces, &kdtree->face_idx[0], kdtree->face_idx.size(), kdtree->aabb, 0);
    1.44  
    1.45 @@ -451,6 +463,10 @@
    1.46  		splitpt[1] = MAX(face->v[0].pos[axis], MAX(face->v[1].pos[axis], face->v[2].pos[axis]));
    1.47  
    1.48  		for(int j=0; j<2; j++) {
    1.49 +			if(splitpt[j] <= node->aabb.min[axis] || splitpt[j] >= node->aabb.max[axis]) {
    1.50 +				continue;
    1.51 +			}
    1.52 +
    1.53  			AABBox aabb_left, aabb_right;
    1.54  			aabb_left = aabb_right = node->aabb;
    1.55  			aabb_left.max[axis] = splitpt[j];
    1.56 @@ -484,9 +500,10 @@
    1.57  	}
    1.58  
    1.59  	Split best_split;
    1.60 +	best_split.axis = -1;
    1.61  	best_split.sum_cost = FLT_MAX;
    1.62  
    1.63 -	for(int i=0; i<1; i++) {
    1.64 +	for(int i=0; i<3; i++) {
    1.65  		Split split;
    1.66  		find_best_split(kd, i, faces, &split);
    1.67  
    1.68 @@ -495,13 +512,17 @@
    1.69  		}
    1.70  	}
    1.71  
    1.72 -	kd->axis = best_split.axis;
    1.73 +	if(best_split.axis == -1) {
    1.74 +		return true;	// can't split any more, only 0-area splits available
    1.75 +	}
    1.76  
    1.77  	//printf("current cost: %f,   best_cost: %f\n", kd->cost, best_sum_cost);
    1.78  	if(best_split.sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) {
    1.79  		return true;	// stop splitting if it doesn't reduce the cost
    1.80  	}
    1.81  
    1.82 +	kd->axis = best_split.axis;
    1.83 +
    1.84  	// create the two children
    1.85  	KDNode *kdleft, *kdright;
    1.86  	kdleft = new KDNode;
    1.87 @@ -556,11 +577,28 @@
    1.88  		}
    1.89  	}
    1.90  
    1.91 -	float sarea = aabb.calc_surface_area();
    1.92 -	if(sarea < 1e-6) {
    1.93 +	float dx = aabb.max[0] - aabb.min[0];
    1.94 +	float dy = aabb.max[1] - aabb.min[1];
    1.95 +	float dz = aabb.max[2] - aabb.min[2];
    1.96 +
    1.97 +	if(dx < 0.0) {
    1.98 +		fprintf(stderr, "FOO DX = %f\n", dx);
    1.99 +		abort();
   1.100 +	}
   1.101 +	if(dy < 0.0) {
   1.102 +		fprintf(stderr, "FOO DX = %f\n", dy);
   1.103 +		abort();
   1.104 +	}
   1.105 +	if(dz < 0.0) {
   1.106 +		fprintf(stderr, "FOO DX = %f\n", dz);
   1.107 +		abort();
   1.108 +	}
   1.109 +
   1.110 +	if(dx < 1e-6 || dy < 1e-6 || dz < 1e-6) {
   1.111  		return FLT_MAX;	// heavily penalize 0-area voxels
   1.112  	}
   1.113  
   1.114 +	float sarea = 2.0 * (dx + dy + dz);//aabb.calc_surface_area();
   1.115  	return tcost + sarea * num_inside * icost;
   1.116  }
   1.117