clray

annotate src/scene.cc @ 58:3d13924b22e6

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