clray

annotate src/scene.cc @ 53:54a96b738afe

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