clray

changeset 53:54a96b738afe

removed the unnecessary second pass for the kdtree flattening
author John Tsiombikas <nuclear@member.fsf.org>
date Sun, 05 Sep 2010 16:43:55 +0100
parents 55b30d8b6805
children 6a30f27fa1e6 e3b4457dc4d2
files src/rt.cc src/scene.cc
diffstat 2 files changed, 9 insertions(+), 106 deletions(-) [+]
line diff
     1.1 --- a/src/rt.cc	Sat Sep 04 23:57:20 2010 +0100
     1.2 +++ b/src/rt.cc	Sun Sep 05 16:43:55 2010 +0100
     1.3 @@ -50,7 +50,7 @@
     1.4  static int global_size;
     1.5  
     1.6  static Light lightlist[] = {
     1.7 -	{{-0.402, 0.696, 1.713, 0}, {1, 1, 1, 1}}
     1.8 +	{{-8, 15, 18, 0}, {1, 1, 1, 1}}
     1.9  };
    1.10  
    1.11  
     2.1 --- a/src/scene.cc	Sat Sep 04 23:57:20 2010 +0100
     2.2 +++ b/src/scene.cc	Sun Sep 05 16:43:55 2010 +0100
     2.3 @@ -14,8 +14,7 @@
     2.4  #define MAX(a, b)	((a) > (b) ? (a) : (b))
     2.5  
     2.6  
     2.7 -static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap);
     2.8 -static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap);
     2.9 +static int flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count);
    2.10  static void draw_kdtree(const KDNode *node, int level = 0);
    2.11  static bool build_kdtree(KDNode *kd, const Face *faces, int level = 0);
    2.12  static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis);
    2.13 @@ -174,27 +173,6 @@
    2.14  	return facebuf;
    2.15  }
    2.16  
    2.17 -static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap);
    2.18 -
    2.19 -static bool validate_flat_tree(const KDNode *node, const KDNodeGPU *kdbuf, int count, const std::map<const KDNode*, int> &flatmap)
    2.20 -{
    2.21 -	if(!node) return true;
    2.22 -
    2.23 -	int idx = find_node_index(node, flatmap);
    2.24 -	int left_idx = find_node_index(node->left, flatmap);
    2.25 -	int right_idx = find_node_index(node->right, flatmap);
    2.26 -
    2.27 -	if(kdbuf[idx].left != left_idx) {
    2.28 -		fprintf(stderr, "%d's left should be %d. it's: %d\n", idx, left_idx, kdbuf[idx].left);
    2.29 -		return false;
    2.30 -	}
    2.31 -	if(kdbuf[idx].right != right_idx) {
    2.32 -		fprintf(stderr, "%d's right should be %d. it's: %d\n", idx, right_idx, kdbuf[idx].right);
    2.33 -		return false;
    2.34 -	}
    2.35 -	return validate_flat_tree(node->left, kdbuf, count, flatmap) && validate_flat_tree(node->right, kdbuf, count, flatmap);
    2.36 -}
    2.37 -
    2.38  const KDNodeGPU *Scene::get_kdtree_buffer() const
    2.39  {
    2.40  	if(kdbuf) {
    2.41 @@ -205,30 +183,18 @@
    2.42  		((Scene*)this)->build_kdtree();
    2.43  	}
    2.44  
    2.45 -	/* we'll associate kdnodes with flattened array indices through this map as
    2.46 -	 * we add them so that the second child-index pass, will be able to find
    2.47 -	 * the children indices of each node.
    2.48 -	 */
    2.49 -	std::map<const KDNode*, int> flatmap;
    2.50 -	flatmap[0] = -1;
    2.51 -
    2.52  	int num_nodes = get_num_kdnodes();
    2.53  	kdbuf = new KDNodeGPU[num_nodes];
    2.54  
    2.55  	int count = 0;
    2.56  
    2.57  	// first arrange the kdnodes into an array (flatten)
    2.58 -	flatten_kdtree(kdtree, kdbuf, &count, &flatmap);
    2.59 -
    2.60 -	// then fix all the left/right links to point to the correct nodes
    2.61 -	fix_child_links(kdtree, kdbuf, flatmap);
    2.62 -
    2.63 -	assert(validate_flat_tree(kdtree, kdbuf, count, flatmap));
    2.64 +	flatten_kdtree(kdtree, kdbuf, &count);
    2.65  
    2.66  	return kdbuf;
    2.67  }
    2.68  
    2.69 -static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap)
    2.70 +static int flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count)
    2.71  {
    2.72  	const size_t max_node_items = sizeof kdbuf[0].face_idx / sizeof kdbuf[0].face_idx[0];
    2.73  	int idx = (*count)++;
    2.74 @@ -246,38 +212,17 @@
    2.75  		kdbuf[idx].num_faces++;
    2.76  	}
    2.77  
    2.78 -	// update the node* -> array-position mapping
    2.79 -	(*flatmap)[node] = idx;
    2.80 -
    2.81  	// recurse to the left/right (if we're not in a leaf node)
    2.82  	if(node->left) {
    2.83  		assert(node->right);
    2.84  
    2.85 -		flatten_kdtree(node->left, kdbuf, count, flatmap);
    2.86 -		flatten_kdtree(node->right, kdbuf, count, flatmap);
    2.87 +		kdbuf[idx].left = flatten_kdtree(node->left, kdbuf, count);
    2.88 +		kdbuf[idx].right = flatten_kdtree(node->right, kdbuf, count);
    2.89 +	} else {
    2.90 +		kdbuf[idx].left = kdbuf[idx].right = -1;
    2.91  	}
    2.92 -}
    2.93  
    2.94 -static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap)
    2.95 -{
    2.96 -	std::map<const KDNode*, int>::const_iterator it = flatmap.find(node);
    2.97 -	assert(it != flatmap.end());
    2.98 -	return it->second;
    2.99 -}
   2.100 -
   2.101 -static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap)
   2.102 -{
   2.103 -	if(!node) return;
   2.104 -
   2.105 -	int idx = find_node_index(node, flatmap);
   2.106 -
   2.107 -	kdbuf[idx].left = find_node_index(node->left, flatmap);
   2.108 -	if(!node->left && kdbuf[idx].left != -1) abort();
   2.109 -	kdbuf[idx].right = find_node_index(node->right, flatmap);
   2.110 -	if(!node->right && kdbuf[idx].right != -1) abort();
   2.111 -
   2.112 -	fix_child_links(node->left, kdbuf, flatmap);
   2.113 -	fix_child_links(node->right, kdbuf, flatmap);
   2.114 +	return idx;
   2.115  }
   2.116  
   2.117  void Scene::draw_kdtree() const
   2.118 @@ -339,48 +284,6 @@
   2.119  	glVertex3fv(node->aabb.max);
   2.120  	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
   2.121  	glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
   2.122 -	/*if(!node->left) return;
   2.123 -
   2.124 -	AABBox *bleft = &node->left->aabb;
   2.125 -
   2.126 -	int axis = level % 3;
   2.127 -	switch(axis) {
   2.128 -	case 0:
   2.129 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);
   2.130 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   2.131 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   2.132 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   2.133 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   2.134 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   2.135 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   2.136 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);
   2.137 -		break;
   2.138 -
   2.139 -	case 1:
   2.140 -		glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
   2.141 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   2.142 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   2.143 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   2.144 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   2.145 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   2.146 -		glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
   2.147 -		glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
   2.148 -		break;
   2.149 -
   2.150 -	case 2:
   2.151 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);
   2.152 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   2.153 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
   2.154 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   2.155 -		glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
   2.156 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   2.157 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
   2.158 -		glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);
   2.159 -		break;
   2.160 -
   2.161 -	default:
   2.162 -		break;
   2.163 -	}*/
   2.164  }
   2.165  
   2.166  bool Scene::build_kdtree()