1.1 --- a/src/scene.cc	Tue Aug 24 05:47:04 2010 +0100
     1.2 +++ b/src/scene.cc	Thu Aug 26 20:24:07 2010 +0100
     1.3 @@ -1,15 +1,18 @@
     1.4 +#include <stdlib.h>
     1.5  #include <math.h>
     1.6  #include <float.h>
     1.7  #include <assert.h>
     1.8 +#include <map>
     1.9  #include "scene.h"
    1.10  #include "ogl.h"
    1.11  
    1.12  
    1.13 +static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap);
    1.14 +static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap);
    1.15  static void draw_kdtree(const KDNode *node, int level = 0);
    1.16  static bool build_kdtree(KDNode *kd, const Face *faces, int level = 0);
    1.17  static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis);
    1.18  static void free_kdtree(KDNode *node);
    1.19 -static void kdtree_gpu_flatten(KDNodeGPU *kdbuf, int idx, const KDNode *node);
    1.20  static void print_item_counts(const KDNode *node, int level);
    1.21  
    1.22  
    1.23 @@ -123,6 +126,11 @@
    1.24  	return (int)matlib.size();
    1.25  }
    1.26  
    1.27 +int Scene::get_num_kdnodes() const
    1.28 +{
    1.29 +	return kdtree_nodes(kdtree);
    1.30 +}
    1.31 +
    1.32  Material *Scene::get_materials()
    1.33  {
    1.34  	if(matlib.empty()) {
    1.35 @@ -159,6 +167,27 @@
    1.36  	return facebuf;
    1.37  }
    1.38  
    1.39 +static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap);
    1.40 +
    1.41 +static bool validate_flat_tree(const KDNode *node, const KDNodeGPU *kdbuf, int count, const std::map<const KDNode*, int> &flatmap)
    1.42 +{
    1.43 +	if(!node) return true;
    1.44 +
    1.45 +	int idx = find_node_index(node, flatmap);
    1.46 +	int left_idx = find_node_index(node->left, flatmap);
    1.47 +	int right_idx = find_node_index(node->right, flatmap);
    1.48 +
    1.49 +	if(kdbuf[idx].left != left_idx) {
    1.50 +		fprintf(stderr, "%d's left should be %d. it's: %d\n", idx, left_idx, kdbuf[idx].left);
    1.51 +		return false;
    1.52 +	}
    1.53 +	if(kdbuf[idx].right != right_idx) {
    1.54 +		fprintf(stderr, "%d's right should be %d. it's: %d\n", idx, right_idx, kdbuf[idx].right);
    1.55 +		return false;
    1.56 +	}
    1.57 +	return validate_flat_tree(node->left, kdbuf, count, flatmap) && validate_flat_tree(node->right, kdbuf, count, flatmap);
    1.58 +}
    1.59 +
    1.60  const KDNodeGPU *Scene::get_kdtree_buffer() const
    1.61  {
    1.62  	if(kdbuf) {
    1.63 @@ -169,29 +198,72 @@
    1.64  		((Scene*)this)->build_kdtree();
    1.65  	}
    1.66  
    1.67 -	int max_nodes = (int)pow(2, kdtree_depth(kdtree)) - 1;
    1.68 -	printf("allocating storage for the complete tree (%d)\n", max_nodes);
    1.69 +	/* we'll associate kdnodes with flattened array indices through this map as
    1.70 +	 * we add them so that the second child-index pass, will be able to find
    1.71 +	 * the children indices of each node.
    1.72 +	 */
    1.73 +	std::map<const KDNode*, int> flatmap;
    1.74 +	flatmap[0] = -1;
    1.75  
    1.76 -	kdbuf = new KDNodeGPU[max_nodes + 1];
    1.77 -	kdtree_gpu_flatten(kdbuf, 1, kdtree);
    1.78 +	int num_nodes = get_num_kdnodes();
    1.79 +	kdbuf = new KDNodeGPU[num_nodes];
    1.80 +
    1.81 +	int count = 0;
    1.82 +
    1.83 +	// first arrange the kdnodes into an array (flatten)
    1.84 +	flatten_kdtree(kdtree, kdbuf, &count, &flatmap);
    1.85 +
    1.86 +	// then fix all the left/right links to point to the correct nodes
    1.87 +	fix_child_links(kdtree, kdbuf, flatmap);
    1.88 +
    1.89 +	assert(validate_flat_tree(kdtree, kdbuf, count, flatmap));
    1.90 +
    1.91  	return kdbuf;
    1.92  }
    1.93  
    1.94 -static int ipow(int x, int n)
    1.95 +static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap)
    1.96  {
    1.97 -	assert(n >= 0);
    1.98 +	int idx = (*count)++;
    1.99  
   1.100 -	int res = 1;
   1.101 -	for(int i=0; i<n; i++) {
   1.102 -		res *= x;
   1.103 +	// copy the node
   1.104 +	kdbuf[idx].aabb = node->aabb;
   1.105 +	for(size_t i=0; i<node->face_idx.size(); i++) {
   1.106 +		kdbuf[idx].face_idx[i] = node->face_idx[i];
   1.107  	}
   1.108 -	return res;
   1.109 +	kdbuf[idx].num_faces = node->face_idx.size();
   1.110 +
   1.111 +	// update the node* -> array-position mapping
   1.112 +	(*flatmap)[node] = idx;
   1.113 +
   1.114 +	// recurse to the left/right (if we're not in a leaf node)
   1.115 +	if(node->left) {
   1.116 +		assert(node->right);
   1.117 +
   1.118 +		flatten_kdtree(node->left, kdbuf, count, flatmap);
   1.119 +		flatten_kdtree(node->right, kdbuf, count, flatmap);
   1.120 +	}
   1.121  }
   1.122  
   1.123 -int Scene::get_kdtree_buffer_size() const
   1.124 +static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap)
   1.125  {
   1.126 -	// 2**depth - 1 nodes for the complete tree + 1 for the unused heap item 0.
   1.127 -	return ipow(2, kdtree_depth(kdtree)) * sizeof(KDNodeGPU);
   1.128 +	std::map<const KDNode*, int>::const_iterator it = flatmap.find(node);
   1.129 +	assert(it != flatmap.end());
   1.130 +	return it->second;
   1.131 +}
   1.132 +
   1.133 +static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap)
   1.134 +{
   1.135 +	if(!node) return;
   1.136 +
   1.137 +	int idx = find_node_index(node, flatmap);
   1.138 +
   1.139 +	kdbuf[idx].left = find_node_index(node->left, flatmap);
   1.140 +	if(!node->left && kdbuf[idx].left != -1) abort();
   1.141 +	kdbuf[idx].right = find_node_index(node->right, flatmap);
   1.142 +	if(!node->right && kdbuf[idx].right != -1) abort();
   1.143 +
   1.144 +	fix_child_links(node->left, kdbuf, flatmap);
   1.145 +	fix_child_links(node->right, kdbuf, flatmap);
   1.146  }
   1.147  
   1.148  void Scene::draw_kdtree() const
   1.149 @@ -442,33 +514,6 @@
   1.150  	return kdtree_nodes(node->left) + kdtree_nodes(node->right) + 1;
   1.151  }
   1.152  
   1.153 -#define MAX_FACES	(sizeof dest->face_idx / sizeof *dest->face_idx)
   1.154 -static void kdtree_gpu_flatten(KDNodeGPU *kdbuf, int idx, const KDNode *node)
   1.155 -{
   1.156 -	KDNodeGPU *dest = kdbuf + idx;
   1.157 -
   1.158 -	dest->aabb = node->aabb;
   1.159 -	dest->num_faces = 0;
   1.160 -
   1.161 -	for(size_t i=0; i<node->face_idx.size(); i++) {
   1.162 -		if(dest->num_faces >= (int)MAX_FACES) {
   1.163 -			fprintf(stderr, "kdtree_gpu_flatten WARNING: more than %d faces in node, skipping!\n", (int)MAX_FACES);
   1.164 -			break;
   1.165 -		}
   1.166 -		dest->face_idx[dest->num_faces++] = node->face_idx[i];
   1.167 -	}
   1.168 -
   1.169 -	if(node->left) {
   1.170 -		assert(node->right);
   1.171 -		assert(!dest->num_faces);
   1.172 -
   1.173 -		dest->num_faces = -1;
   1.174 -
   1.175 -		kdtree_gpu_flatten(kdbuf, idx * 2, node->left);
   1.176 -		kdtree_gpu_flatten(kdbuf, idx * 2 + 1, node->right);
   1.177 -	}
   1.178 -}
   1.179 -
   1.180  static void print_item_counts(const KDNode *node, int level)
   1.181  {
   1.182  	if(!node) return;