clray

annotate src/scene.cc @ 35:7d77ded5f890

find changesets by author, revision, files, or words in the commit message
stopped using a heap to flatten the kdtree. added explicit left/right indices
author John Tsiombikas <nuclear@member.fsf.org>
date Thu, 26 Aug 2010 20:24:07 +0100
parents 4cf4919c3812
children 4dec8853bf75
rev   line source
nuclear@35 1 #include <stdlib.h>
John@15 2 #include <math.h>
nuclear@25 3 #include <float.h>
nuclear@26 4 #include <assert.h>
nuclear@35 5 #include <map>
nuclear@22 6 #include "scene.h"
nuclear@27 7 #include "ogl.h"
nuclear@6 8
nuclear@26 9
nuclear@35 10 static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap);
nuclear@35 11 static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap);
nuclear@27 12 static void draw_kdtree(const KDNode *node, int level = 0);
nuclear@32 13 static bool build_kdtree(KDNode *kd, const Face *faces, int level = 0);
nuclear@32 14 static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis);
nuclear@26 15 static void free_kdtree(KDNode *node);
nuclear@27 16 static void print_item_counts(const KDNode *node, int level);
nuclear@26 17
nuclear@26 18
nuclear@26 19 static int accel_param[NUM_ACCEL_PARAMS] = {
nuclear@28 20 40, // max tree depth
nuclear@26 21 0, // max items per node (0 means ignore limit)
nuclear@26 22 5, // estimated traversal cost
nuclear@26 23 15 // estimated interseciton cost
nuclear@26 24 };
nuclear@26 25
nuclear@26 26
nuclear@26 27 void set_accel_param(int p, int v)
nuclear@26 28 {
nuclear@26 29 assert(p >= 0 && p < NUM_ACCEL_PARAMS);
nuclear@26 30 accel_param[p] = v;
nuclear@26 31 }
nuclear@26 32
nuclear@26 33
John@15 34 #define FEQ(a, b) (fabs((a) - (b)) < 1e-8)
John@15 35 bool Face::operator ==(const Face &f) const
John@15 36 {
John@15 37 for(int i=0; i<3; i++) {
John@15 38 for(int j=0; j<3; j++) {
John@15 39 if(!FEQ(v[i].pos[j], f.v[i].pos[j])) {
John@15 40 return false;
John@15 41 }
John@15 42 if(!FEQ(v[i].normal[j], f.v[i].normal[j])) {
John@15 43 return false;
John@15 44 }
John@15 45 }
John@15 46 if(!FEQ(normal[i], f.normal[i])) {
John@15 47 return false;
John@15 48 }
John@15 49 }
John@15 50 return true;
John@15 51 }
John@15 52
nuclear@25 53 float AABBox::calc_surface_area() const
nuclear@25 54 {
nuclear@25 55 float area1 = (max[0] - min[0]) * (max[1] - min[1]);
nuclear@25 56 float area2 = (max[3] - min[3]) * (max[1] - min[1]);
nuclear@25 57 float area3 = (max[0] - min[0]) * (max[3] - min[3]);
nuclear@25 58
nuclear@25 59 return 2.0f * (area1 + area2 + area3);
nuclear@25 60 }
nuclear@25 61
nuclear@26 62 KDNode::KDNode()
nuclear@26 63 {
nuclear@26 64 left = right = 0;
nuclear@32 65 cost = 0.0;
nuclear@26 66 }
nuclear@26 67
nuclear@25 68
nuclear@24 69 Scene::Scene()
nuclear@24 70 {
nuclear@24 71 facebuf = 0;
nuclear@24 72 num_faces = -1;
nuclear@24 73 kdtree = 0;
nuclear@28 74 kdbuf = 0;
nuclear@24 75 }
nuclear@24 76
nuclear@24 77 Scene::~Scene()
nuclear@24 78 {
nuclear@24 79 delete [] facebuf;
nuclear@28 80 delete [] kdbuf;
nuclear@28 81 free_kdtree(kdtree);
nuclear@24 82 }
nuclear@24 83
nuclear@13 84 bool Scene::add_mesh(Mesh *m)
nuclear@13 85 {
nuclear@13 86 // make sure triangles have material ids
nuclear@13 87 for(size_t i=0; i<m->faces.size(); i++) {
nuclear@13 88 m->faces[i].matid = m->matid;
nuclear@13 89 }
nuclear@24 90
nuclear@24 91 try {
nuclear@24 92 meshes.push_back(m);
nuclear@24 93 }
nuclear@24 94 catch(...) {
nuclear@24 95 return false;
nuclear@24 96 }
nuclear@24 97
nuclear@24 98 // invalidate facebuffer and count
nuclear@24 99 delete [] facebuf;
nuclear@24 100 facebuf = 0;
nuclear@24 101 num_faces = -1;
nuclear@24 102
nuclear@13 103 return true;
nuclear@13 104 }
nuclear@13 105
John@14 106 int Scene::get_num_meshes() const
John@14 107 {
John@14 108 return (int)meshes.size();
John@14 109 }
John@14 110
nuclear@13 111 int Scene::get_num_faces() const
nuclear@13 112 {
nuclear@24 113 if(num_faces >= 0) {
nuclear@24 114 return num_faces;
nuclear@24 115 }
nuclear@24 116
nuclear@24 117 num_faces = 0;
nuclear@13 118 for(size_t i=0; i<meshes.size(); i++) {
nuclear@13 119 num_faces += meshes[i]->faces.size();
nuclear@13 120 }
nuclear@13 121 return num_faces;
nuclear@13 122 }
nuclear@13 123
John@14 124 int Scene::get_num_materials() const
John@14 125 {
John@14 126 return (int)matlib.size();
John@14 127 }
John@14 128
nuclear@35 129 int Scene::get_num_kdnodes() const
nuclear@35 130 {
nuclear@35 131 return kdtree_nodes(kdtree);
nuclear@35 132 }
nuclear@35 133
John@14 134 Material *Scene::get_materials()
John@14 135 {
John@14 136 if(matlib.empty()) {
John@14 137 return 0;
John@14 138 }
John@14 139 return &matlib[0];
John@14 140 }
John@14 141
John@14 142 const Material *Scene::get_materials() const
John@14 143 {
John@14 144 if(matlib.empty()) {
John@14 145 return 0;
John@14 146 }
John@14 147 return &matlib[0];
John@14 148 }
nuclear@24 149
nuclear@24 150 const Face *Scene::get_face_buffer() const
nuclear@24 151 {
nuclear@24 152 if(facebuf) {
nuclear@24 153 return facebuf;
nuclear@24 154 }
nuclear@24 155
nuclear@24 156 int num_meshes = get_num_meshes();
nuclear@24 157
nuclear@24 158 printf("constructing face buffer with %d faces (out of %d meshes)\n", get_num_faces(), num_meshes);
nuclear@24 159 facebuf = new Face[num_faces];
nuclear@24 160 Face *fptr = facebuf;
nuclear@24 161
nuclear@24 162 for(int i=0; i<num_meshes; i++) {
nuclear@24 163 for(size_t j=0; j<meshes[i]->faces.size(); j++) {
nuclear@24 164 *fptr++ = meshes[i]->faces[j];
nuclear@24 165 }
nuclear@24 166 }
nuclear@24 167 return facebuf;
nuclear@24 168 }
nuclear@24 169
nuclear@35 170 static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap);
nuclear@35 171
nuclear@35 172 static bool validate_flat_tree(const KDNode *node, const KDNodeGPU *kdbuf, int count, const std::map<const KDNode*, int> &flatmap)
nuclear@35 173 {
nuclear@35 174 if(!node) return true;
nuclear@35 175
nuclear@35 176 int idx = find_node_index(node, flatmap);
nuclear@35 177 int left_idx = find_node_index(node->left, flatmap);
nuclear@35 178 int right_idx = find_node_index(node->right, flatmap);
nuclear@35 179
nuclear@35 180 if(kdbuf[idx].left != left_idx) {
nuclear@35 181 fprintf(stderr, "%d's left should be %d. it's: %d\n", idx, left_idx, kdbuf[idx].left);
nuclear@35 182 return false;
nuclear@35 183 }
nuclear@35 184 if(kdbuf[idx].right != right_idx) {
nuclear@35 185 fprintf(stderr, "%d's right should be %d. it's: %d\n", idx, right_idx, kdbuf[idx].right);
nuclear@35 186 return false;
nuclear@35 187 }
nuclear@35 188 return validate_flat_tree(node->left, kdbuf, count, flatmap) && validate_flat_tree(node->right, kdbuf, count, flatmap);
nuclear@35 189 }
nuclear@35 190
nuclear@28 191 const KDNodeGPU *Scene::get_kdtree_buffer() const
nuclear@28 192 {
nuclear@28 193 if(kdbuf) {
nuclear@28 194 return kdbuf;
nuclear@28 195 }
nuclear@28 196
nuclear@28 197 if(!kdtree) {
nuclear@28 198 ((Scene*)this)->build_kdtree();
nuclear@28 199 }
nuclear@28 200
nuclear@35 201 /* we'll associate kdnodes with flattened array indices through this map as
nuclear@35 202 * we add them so that the second child-index pass, will be able to find
nuclear@35 203 * the children indices of each node.
nuclear@35 204 */
nuclear@35 205 std::map<const KDNode*, int> flatmap;
nuclear@35 206 flatmap[0] = -1;
nuclear@28 207
nuclear@35 208 int num_nodes = get_num_kdnodes();
nuclear@35 209 kdbuf = new KDNodeGPU[num_nodes];
nuclear@35 210
nuclear@35 211 int count = 0;
nuclear@35 212
nuclear@35 213 // first arrange the kdnodes into an array (flatten)
nuclear@35 214 flatten_kdtree(kdtree, kdbuf, &count, &flatmap);
nuclear@35 215
nuclear@35 216 // then fix all the left/right links to point to the correct nodes
nuclear@35 217 fix_child_links(kdtree, kdbuf, flatmap);
nuclear@35 218
nuclear@35 219 assert(validate_flat_tree(kdtree, kdbuf, count, flatmap));
nuclear@35 220
nuclear@28 221 return kdbuf;
nuclear@28 222 }
nuclear@28 223
nuclear@35 224 static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap)
nuclear@28 225 {
nuclear@35 226 int idx = (*count)++;
nuclear@29 227
nuclear@35 228 // copy the node
nuclear@35 229 kdbuf[idx].aabb = node->aabb;
nuclear@35 230 for(size_t i=0; i<node->face_idx.size(); i++) {
nuclear@35 231 kdbuf[idx].face_idx[i] = node->face_idx[i];
nuclear@28 232 }
nuclear@35 233 kdbuf[idx].num_faces = node->face_idx.size();
nuclear@35 234
nuclear@35 235 // update the node* -> array-position mapping
nuclear@35 236 (*flatmap)[node] = idx;
nuclear@35 237
nuclear@35 238 // recurse to the left/right (if we're not in a leaf node)
nuclear@35 239 if(node->left) {
nuclear@35 240 assert(node->right);
nuclear@35 241
nuclear@35 242 flatten_kdtree(node->left, kdbuf, count, flatmap);
nuclear@35 243 flatten_kdtree(node->right, kdbuf, count, flatmap);
nuclear@35 244 }
nuclear@28 245 }
nuclear@28 246
nuclear@35 247 static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap)
nuclear@29 248 {
nuclear@35 249 std::map<const KDNode*, int>::const_iterator it = flatmap.find(node);
nuclear@35 250 assert(it != flatmap.end());
nuclear@35 251 return it->second;
nuclear@35 252 }
nuclear@35 253
nuclear@35 254 static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap)
nuclear@35 255 {
nuclear@35 256 if(!node) return;
nuclear@35 257
nuclear@35 258 int idx = find_node_index(node, flatmap);
nuclear@35 259
nuclear@35 260 kdbuf[idx].left = find_node_index(node->left, flatmap);
nuclear@35 261 if(!node->left && kdbuf[idx].left != -1) abort();
nuclear@35 262 kdbuf[idx].right = find_node_index(node->right, flatmap);
nuclear@35 263 if(!node->right && kdbuf[idx].right != -1) abort();
nuclear@35 264
nuclear@35 265 fix_child_links(node->left, kdbuf, flatmap);
nuclear@35 266 fix_child_links(node->right, kdbuf, flatmap);
nuclear@29 267 }
nuclear@24 268
nuclear@27 269 void Scene::draw_kdtree() const
nuclear@27 270 {
nuclear@27 271 glPushAttrib(GL_ENABLE_BIT);
nuclear@27 272 glDisable(GL_LIGHTING);
nuclear@27 273 glDepthMask(0);
nuclear@27 274
nuclear@27 275 glBegin(GL_LINES);
nuclear@27 276 ::draw_kdtree(kdtree, 0);
nuclear@27 277 glEnd();
nuclear@27 278
nuclear@27 279 glDepthMask(1);
nuclear@27 280 glPopAttrib();
nuclear@27 281 }
nuclear@27 282
nuclear@27 283 static float palette[][3] = {
nuclear@27 284 {0, 1, 0},
nuclear@27 285 {1, 0, 0},
nuclear@27 286 {0, 0, 1},
nuclear@27 287 {1, 1, 0},
nuclear@27 288 {0, 0, 1},
nuclear@27 289 {1, 0, 1}
nuclear@27 290 };
nuclear@27 291 static int pal_size = sizeof palette / sizeof *palette;
nuclear@27 292
nuclear@27 293 static void draw_kdtree(const KDNode *node, int level)
nuclear@27 294 {
nuclear@27 295 if(!node) return;
nuclear@27 296
nuclear@27 297 draw_kdtree(node->left, level + 1);
nuclear@27 298 draw_kdtree(node->right, level + 1);
nuclear@27 299
nuclear@27 300 glColor3fv(palette[level % pal_size]);
nuclear@27 301
nuclear@27 302 glVertex3fv(node->aabb.min);
nuclear@27 303 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
nuclear@27 304 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
nuclear@27 305 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 306 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 307 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 308 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 309 glVertex3fv(node->aabb.min);
nuclear@27 310
nuclear@27 311 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 312 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 313 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 314 glVertex3fv(node->aabb.max);
nuclear@27 315 glVertex3fv(node->aabb.max);
nuclear@27 316 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
nuclear@27 317 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
nuclear@27 318 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 319
nuclear@27 320 glVertex3fv(node->aabb.min);
nuclear@27 321 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 322 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
nuclear@27 323 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 324 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 325 glVertex3fv(node->aabb.max);
nuclear@27 326 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 327 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
nuclear@27 328 }
nuclear@27 329
nuclear@27 330 bool Scene::build_kdtree()
nuclear@24 331 {
nuclear@29 332 assert(kdtree == 0);
nuclear@29 333
nuclear@24 334 const Face *faces = get_face_buffer();
nuclear@24 335 int num_faces = get_num_faces();
nuclear@24 336
nuclear@25 337 printf("Constructing kd-tree out of %d faces ...\n", num_faces);
nuclear@25 338
nuclear@27 339 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];
nuclear@27 340 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
nuclear@27 341 printf(" max items per leaf: %d\n", accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]);
nuclear@27 342 printf(" SAH parameters - tcost: %d - icost: %d\n", tcost, icost);
nuclear@27 343
nuclear@25 344 free_kdtree(kdtree);
nuclear@25 345 kdtree = new KDNode;
nuclear@25 346
nuclear@25 347 /* Start the construction of the kdtree by adding all faces of the scene
nuclear@25 348 * to the new root node. At the same time calculate the root's AABB.
nuclear@25 349 */
nuclear@25 350 kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX;
nuclear@25 351 kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX;
nuclear@25 352
nuclear@24 353 for(int i=0; i<num_faces; i++) {
nuclear@25 354 const Face *face = faces + i;
nuclear@25 355
nuclear@25 356 // for each vertex of the face ...
nuclear@25 357 for(int j=0; j<3; j++) {
nuclear@25 358 const float *pos = face->v[j].pos;
nuclear@25 359
nuclear@25 360 // for each element (xyz) of the position vector ...
nuclear@25 361 for(int k=0; k<3; k++) {
nuclear@25 362 if(pos[k] < kdtree->aabb.min[k]) {
nuclear@25 363 kdtree->aabb.min[k] = pos[k];
nuclear@25 364 }
nuclear@25 365 if(pos[k] > kdtree->aabb.max[k]) {
nuclear@25 366 kdtree->aabb.max[k] = pos[k];
nuclear@25 367 }
nuclear@25 368 }
nuclear@25 369 }
nuclear@25 370
nuclear@32 371 kdtree->face_idx.push_back(i); // add the face
nuclear@24 372 }
nuclear@24 373
nuclear@26 374 // calculate the heuristic for the root
nuclear@32 375 kdtree->cost = eval_cost(faces, &kdtree->face_idx[0], kdtree->face_idx.size(), kdtree->aabb, 0);
nuclear@26 376
nuclear@25 377 // now proceed splitting the root recursively
nuclear@32 378 if(!::build_kdtree(kdtree, faces)) {
nuclear@27 379 fprintf(stderr, "failed to build kdtree\n");
nuclear@27 380 return false;
nuclear@27 381 }
nuclear@27 382
nuclear@27 383 printf(" tree depth: %d\n", kdtree_depth(kdtree));
nuclear@27 384 print_item_counts(kdtree, 0);
nuclear@27 385 return true;
nuclear@24 386 }
nuclear@24 387
nuclear@32 388 static bool build_kdtree(KDNode *kd, const Face *faces, int level)
nuclear@24 389 {
nuclear@28 390 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];
nuclear@26 391 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];
nuclear@27 392 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
nuclear@27 393
nuclear@32 394 if(kd->face_idx.empty() || level >= opt_max_depth) {
nuclear@27 395 return true;
nuclear@25 396 }
nuclear@25 397
nuclear@27 398 int axis = level % 3;
nuclear@26 399
nuclear@26 400 float best_cost[2], best_sum_cost = FLT_MAX;
nuclear@26 401 float best_split;
nuclear@26 402
nuclear@32 403 for(size_t i=0; i<kd->face_idx.size(); i++) {
nuclear@32 404 const Face *face = faces + kd->face_idx[i];
nuclear@26 405
nuclear@32 406 for(int j=0; j<3; j++) {
nuclear@26 407 AABBox aabb_left, aabb_right;
nuclear@32 408 const float *split = face->v[j].pos;
nuclear@26 409
nuclear@26 410 aabb_left = aabb_right = kd->aabb;
nuclear@26 411 aabb_left.max[axis] = split[axis];
nuclear@26 412 aabb_right.min[axis] = split[axis];
nuclear@26 413
nuclear@32 414 float left_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_left, axis);
nuclear@32 415 float right_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_right, axis);
nuclear@27 416 float sum_cost = left_cost + right_cost - tcost; // tcost is added twice
nuclear@26 417
nuclear@26 418 if(sum_cost < best_sum_cost) {
nuclear@26 419 best_cost[0] = left_cost;
nuclear@26 420 best_cost[1] = right_cost;
nuclear@26 421 best_sum_cost = sum_cost;
nuclear@26 422 best_split = split[axis];
nuclear@26 423 }
nuclear@26 424 }
nuclear@26 425 }
nuclear@26 426
nuclear@29 427 //printf("current cost: %f, best_cost: %f\n", kd->cost, best_sum_cost);
nuclear@32 428 if(best_sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) {
nuclear@27 429 return true; // stop splitting if it doesn't reduce the cost
nuclear@26 430 }
nuclear@26 431
nuclear@26 432 // create the two children
nuclear@26 433 KDNode *kdleft, *kdright;
nuclear@26 434 kdleft = new KDNode;
nuclear@26 435 kdright = new KDNode;
nuclear@26 436
nuclear@26 437 kdleft->aabb = kdright->aabb = kd->aabb;
nuclear@26 438
nuclear@26 439 kdleft->aabb.max[axis] = best_split;
nuclear@26 440 kdright->aabb.min[axis] = best_split;
nuclear@26 441
nuclear@26 442 kdleft->cost = best_cost[0];
nuclear@26 443 kdright->cost = best_cost[1];
nuclear@26 444
nuclear@32 445 for(size_t i=0; i<kd->face_idx.size(); i++) {
nuclear@32 446 int fidx = kd->face_idx[i];
nuclear@32 447 const Face *face = faces + fidx;
nuclear@26 448
nuclear@26 449 if(face->v[0].pos[axis] < best_split ||
nuclear@26 450 face->v[1].pos[axis] < best_split ||
nuclear@26 451 face->v[2].pos[axis] < best_split) {
nuclear@32 452 kdleft->face_idx.push_back(fidx);
nuclear@26 453 }
nuclear@26 454 if(face->v[0].pos[axis] >= best_split ||
nuclear@26 455 face->v[1].pos[axis] >= best_split ||
nuclear@26 456 face->v[2].pos[axis] >= best_split) {
nuclear@32 457 kdright->face_idx.push_back(fidx);
nuclear@26 458 }
nuclear@26 459 }
nuclear@32 460 kd->face_idx.clear(); // only leaves have faces
nuclear@26 461
nuclear@26 462 kd->left = kdleft;
nuclear@26 463 kd->right = kdright;
nuclear@27 464
nuclear@32 465 return build_kdtree(kd->left, faces, level + 1) && build_kdtree(kd->right, faces, level + 1);
nuclear@26 466 }
nuclear@26 467
nuclear@32 468 static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis)
nuclear@26 469 {
nuclear@26 470 int num_inside = 0;
nuclear@26 471 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
nuclear@26 472 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];
nuclear@26 473
nuclear@32 474 for(int i=0; i<num_faces; i++) {
nuclear@32 475 const Face *face = faces + face_idx[i];
nuclear@26 476
nuclear@32 477 for(int j=0; j<3; j++) {
nuclear@32 478 if(face->v[j].pos[axis] >= aabb.min[axis] && face->v[j].pos[axis] < aabb.max[axis]) {
nuclear@26 479 num_inside++;
nuclear@26 480 break;
nuclear@26 481 }
nuclear@26 482 }
nuclear@26 483 }
nuclear@26 484
nuclear@27 485 float sarea = aabb.calc_surface_area();
nuclear@27 486 if(sarea < 1e-8) {
nuclear@27 487 return FLT_MAX; // heavily penalize 0-area voxels
nuclear@27 488 }
nuclear@27 489
nuclear@32 490 return tcost + sarea * num_inside * icost;
nuclear@24 491 }
nuclear@25 492
nuclear@25 493 static void free_kdtree(KDNode *node)
nuclear@25 494 {
nuclear@25 495 if(node) {
nuclear@25 496 free_kdtree(node->left);
nuclear@25 497 free_kdtree(node->right);
nuclear@25 498 delete node;
nuclear@25 499 }
nuclear@25 500 }
nuclear@27 501
nuclear@28 502 int kdtree_depth(const KDNode *node)
nuclear@27 503 {
nuclear@27 504 if(!node) return 0;
nuclear@27 505
nuclear@27 506 int left = kdtree_depth(node->left);
nuclear@27 507 int right = kdtree_depth(node->right);
nuclear@27 508 return (left > right ? left : right) + 1;
nuclear@27 509 }
nuclear@27 510
nuclear@28 511 int kdtree_nodes(const KDNode *node)
nuclear@28 512 {
nuclear@28 513 if(!node) return 0;
nuclear@28 514 return kdtree_nodes(node->left) + kdtree_nodes(node->right) + 1;
nuclear@28 515 }
nuclear@28 516
nuclear@27 517 static void print_item_counts(const KDNode *node, int level)
nuclear@27 518 {
nuclear@27 519 if(!node) return;
nuclear@27 520
nuclear@30 521 for(int i=0; i<level; i++) {
nuclear@27 522 fputs(" ", stdout);
nuclear@27 523 }
nuclear@32 524 printf("- %d (cost: %f)\n", (int)node->face_idx.size(), node->cost);
nuclear@27 525
nuclear@27 526 print_item_counts(node->left, level + 1);
nuclear@27 527 print_item_counts(node->right, level + 1);
nuclear@27 528 }