1.1 --- a/src/scene.cc	Sat Sep 04 23:57:20 2010 +0100
     1.2 +++ b/src/scene.cc	Sun Sep 05 16:43:55 2010 +0100
     1.3 @@ -14,8 +14,7 @@
     1.4  #define MAX(a, b)	((a) > (b) ? (a) : (b))
     1.5  
     1.6  
     1.7 -static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap);
     1.8 -static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap);
     1.9 +static int flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count);
    1.10  static void draw_kdtree(const KDNode *node, int level = 0);
    1.11  static bool build_kdtree(KDNode *kd, const Face *faces, int level = 0);
    1.12  static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis);
    1.13 @@ -174,27 +173,6 @@
    1.14  	return facebuf;
    1.15  }
    1.16  
    1.17 -static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap);
    1.18 -
    1.19 -static bool validate_flat_tree(const KDNode *node, const KDNodeGPU *kdbuf, int count, const std::map<const KDNode*, int> &flatmap)
    1.20 -{
    1.21 -	if(!node) return true;
    1.22 -
    1.23 -	int idx = find_node_index(node, flatmap);
    1.24 -	int left_idx = find_node_index(node->left, flatmap);
    1.25 -	int right_idx = find_node_index(node->right, flatmap);
    1.26 -
    1.27 -	if(kdbuf[idx].left != left_idx) {
    1.28 -		fprintf(stderr, "%d's left should be %d. it's: %d\n", idx, left_idx, kdbuf[idx].left);
    1.29 -		return false;
    1.30 -	}
    1.31 -	if(kdbuf[idx].right != right_idx) {
    1.32 -		fprintf(stderr, "%d's right should be %d. it's: %d\n", idx, right_idx, kdbuf[idx].right);
    1.33 -		return false;
    1.34 -	}
    1.35 -	return validate_flat_tree(node->left, kdbuf, count, flatmap) && validate_flat_tree(node->right, kdbuf, count, flatmap);
    1.36 -}
    1.37 -
    1.38  const KDNodeGPU *Scene::get_kdtree_buffer() const
    1.39  {
    1.40  	if(kdbuf) {
    1.41 @@ -205,30 +183,18 @@
    1.42  		((Scene*)this)->build_kdtree();
    1.43  	}
    1.44  
    1.45 -	/* we'll associate kdnodes with flattened array indices through this map as
    1.46 -	 * we add them so that the second child-index pass, will be able to find
    1.47 -	 * the children indices of each node.
    1.48 -	 */
    1.49 -	std::map<const KDNode*, int> flatmap;
    1.50 -	flatmap[0] = -1;
    1.51 -
    1.52  	int num_nodes = get_num_kdnodes();
    1.53  	kdbuf = new KDNodeGPU[num_nodes];
    1.54  
    1.55  	int count = 0;
    1.56  
    1.57  	// first arrange the kdnodes into an array (flatten)
    1.58 -	flatten_kdtree(kdtree, kdbuf, &count, &flatmap);
    1.59 -
    1.60 -	// then fix all the left/right links to point to the correct nodes
    1.61 -	fix_child_links(kdtree, kdbuf, flatmap);
    1.62 -
    1.63 -	assert(validate_flat_tree(kdtree, kdbuf, count, flatmap));
    1.64 +	flatten_kdtree(kdtree, kdbuf, &count);
    1.65  
    1.66  	return kdbuf;
    1.67  }
    1.68  
    1.69 -static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap)
    1.70 +static int flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count)
    1.71  {
    1.72  	const size_t max_node_items = sizeof kdbuf[0].face_idx / sizeof kdbuf[0].face_idx[0];
    1.73  	int idx = (*count)++;
    1.74 @@ -246,38 +212,17 @@
    1.75  		kdbuf[idx].num_faces++;
    1.76  	}
    1.77  
    1.78 -	// update the node* -> array-position mapping
    1.79 -	(*flatmap)[node] = idx;
    1.80 -
    1.81  	// recurse to the left/right (if we're not in a leaf node)
    1.82  	if(node->left) {
    1.83  		assert(node->right);
    1.84  
    1.85 -		flatten_kdtree(node->left, kdbuf, count, flatmap);
    1.86 -		flatten_kdtree(node->right, kdbuf, count, flatmap);
    1.87 +		kdbuf[idx].left = flatten_kdtree(node->left, kdbuf, count);
    1.88 +		kdbuf[idx].right = flatten_kdtree(node->right, kdbuf, count);
    1.89 +	} else {
    1.90 +		kdbuf[idx].left = kdbuf[idx].right = -1;
    1.91  	}
    1.92 -}
    1.93  
    1.94 -static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap)
    1.95 -{
    1.96 -	std::map<const KDNode*, int>::const_iterator it = flatmap.find(node);
    1.97 -	assert(it != flatmap.end());
    1.98 -	return it->second;
    1.99 -}
   1.100 -
   1.101 -static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap)
   1.102 -{
   1.103 -	if(!node) return;
   1.104 -
   1.105 -	int idx = find_node_index(node, flatmap);
   1.106 -
   1.107 -	kdbuf[idx].left = find_node_index(node->left, flatmap);
   1.108 -	if(!node->left && kdbuf[idx].left != -1) abort();
   1.109 -	kdbuf[idx].right = find_node_index(node->right, flatmap);
   1.110 -	if(!node->right && kdbuf[idx].right != -1) abort();
   1.111 -
   1.112 -	fix_child_links(node->left, kdbuf, flatmap);
   1.113 -	fix_child_links(node->right, kdbuf, flatmap);
   1.114 +	return idx;
   1.115  }
   1.116  
   1.117  void Scene::draw_kdtree() const
   1.118 @@ -339,48 +284,6 @@
   1.119  	glVertex3fv(node->aabb.max);
   1.120  	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
   1.121  	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
   1.122 -	/*if(!node->left) return;
   1.123 -
   1.124 -	AABBox *bleft = &node->left->aabb;
   1.125 -
   1.126 -	int axis = level % 3;
   1.127 -	switch(axis) {
   1.128 -	case 0:
   1.129 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);
   1.130 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   1.131 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   1.132 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   1.133 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   1.134 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   1.135 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   1.136 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);
   1.137 -		break;
   1.138 -
   1.139 -	case 1:
   1.140 -		glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
   1.141 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   1.142 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   1.143 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   1.144 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   1.145 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   1.146 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   1.147 -		glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
   1.148 -		break;
   1.149 -
   1.150 -	case 2:
   1.151 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);
   1.152 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   1.153 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   1.154 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   1.155 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   1.156 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   1.157 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   1.158 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);
   1.159 -		break;
   1.160 -
   1.161 -	default:
   1.162 -		break;
   1.163 -	}*/
   1.164  }
   1.165  
   1.166  bool Scene::build_kdtree()