clray

annotate src/scene.cc @ 44:e7f79c6ad246

find changesets by author, revision, files, or words in the commit message
added maximum node face limit by default
author John Tsiombikas <nuclear@member.fsf.org>
date Sat, 28 Aug 2010 21:50:17 +0100
parents 4bcf78e572d6
children 54a96b738afe
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@35 17 static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap);
nuclear@35 18 static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap);
nuclear@27 19 static void draw_kdtree(const KDNode *node, int level = 0);
nuclear@32 20 static bool build_kdtree(KDNode *kd, const Face *faces, int level = 0);
nuclear@32 21 static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis);
nuclear@26 22 static void free_kdtree(KDNode *node);
nuclear@27 23 static void print_item_counts(const KDNode *node, int level);
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
John@14 113 int Scene::get_num_meshes() const
John@14 114 {
John@14 115 return (int)meshes.size();
John@14 116 }
John@14 117
nuclear@13 118 int Scene::get_num_faces() const
nuclear@13 119 {
nuclear@24 120 if(num_faces >= 0) {
nuclear@24 121 return num_faces;
nuclear@24 122 }
nuclear@24 123
nuclear@24 124 num_faces = 0;
nuclear@13 125 for(size_t i=0; i<meshes.size(); i++) {
nuclear@13 126 num_faces += meshes[i]->faces.size();
nuclear@13 127 }
nuclear@13 128 return num_faces;
nuclear@13 129 }
nuclear@13 130
John@14 131 int Scene::get_num_materials() const
John@14 132 {
John@14 133 return (int)matlib.size();
John@14 134 }
John@14 135
nuclear@35 136 int Scene::get_num_kdnodes() const
nuclear@35 137 {
nuclear@35 138 return kdtree_nodes(kdtree);
nuclear@35 139 }
nuclear@35 140
John@14 141 Material *Scene::get_materials()
John@14 142 {
John@14 143 if(matlib.empty()) {
John@14 144 return 0;
John@14 145 }
John@14 146 return &matlib[0];
John@14 147 }
John@14 148
John@14 149 const Material *Scene::get_materials() const
John@14 150 {
John@14 151 if(matlib.empty()) {
John@14 152 return 0;
John@14 153 }
John@14 154 return &matlib[0];
John@14 155 }
nuclear@24 156
nuclear@24 157 const Face *Scene::get_face_buffer() const
nuclear@24 158 {
nuclear@24 159 if(facebuf) {
nuclear@24 160 return facebuf;
nuclear@24 161 }
nuclear@24 162
nuclear@24 163 int num_meshes = get_num_meshes();
nuclear@24 164
nuclear@24 165 printf("constructing face buffer with %d faces (out of %d meshes)\n", get_num_faces(), num_meshes);
nuclear@24 166 facebuf = new Face[num_faces];
nuclear@24 167 Face *fptr = facebuf;
nuclear@24 168
nuclear@24 169 for(int i=0; i<num_meshes; i++) {
nuclear@24 170 for(size_t j=0; j<meshes[i]->faces.size(); j++) {
nuclear@24 171 *fptr++ = meshes[i]->faces[j];
nuclear@24 172 }
nuclear@24 173 }
nuclear@24 174 return facebuf;
nuclear@24 175 }
nuclear@24 176
nuclear@35 177 static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap);
nuclear@35 178
nuclear@35 179 static bool validate_flat_tree(const KDNode *node, const KDNodeGPU *kdbuf, int count, const std::map<const KDNode*, int> &flatmap)
nuclear@35 180 {
nuclear@35 181 if(!node) return true;
nuclear@35 182
nuclear@35 183 int idx = find_node_index(node, flatmap);
nuclear@35 184 int left_idx = find_node_index(node->left, flatmap);
nuclear@35 185 int right_idx = find_node_index(node->right, flatmap);
nuclear@35 186
nuclear@35 187 if(kdbuf[idx].left != left_idx) {
nuclear@35 188 fprintf(stderr, "%d's left should be %d. it's: %d\n", idx, left_idx, kdbuf[idx].left);
nuclear@35 189 return false;
nuclear@35 190 }
nuclear@35 191 if(kdbuf[idx].right != right_idx) {
nuclear@35 192 fprintf(stderr, "%d's right should be %d. it's: %d\n", idx, right_idx, kdbuf[idx].right);
nuclear@35 193 return false;
nuclear@35 194 }
nuclear@35 195 return validate_flat_tree(node->left, kdbuf, count, flatmap) && validate_flat_tree(node->right, kdbuf, count, flatmap);
nuclear@35 196 }
nuclear@35 197
nuclear@28 198 const KDNodeGPU *Scene::get_kdtree_buffer() const
nuclear@28 199 {
nuclear@28 200 if(kdbuf) {
nuclear@28 201 return kdbuf;
nuclear@28 202 }
nuclear@28 203
nuclear@28 204 if(!kdtree) {
nuclear@28 205 ((Scene*)this)->build_kdtree();
nuclear@28 206 }
nuclear@28 207
nuclear@35 208 /* we'll associate kdnodes with flattened array indices through this map as
nuclear@35 209 * we add them so that the second child-index pass, will be able to find
nuclear@35 210 * the children indices of each node.
nuclear@35 211 */
nuclear@35 212 std::map<const KDNode*, int> flatmap;
nuclear@35 213 flatmap[0] = -1;
nuclear@28 214
nuclear@35 215 int num_nodes = get_num_kdnodes();
nuclear@35 216 kdbuf = new KDNodeGPU[num_nodes];
nuclear@35 217
nuclear@35 218 int count = 0;
nuclear@35 219
nuclear@35 220 // first arrange the kdnodes into an array (flatten)
nuclear@35 221 flatten_kdtree(kdtree, kdbuf, &count, &flatmap);
nuclear@35 222
nuclear@35 223 // then fix all the left/right links to point to the correct nodes
nuclear@35 224 fix_child_links(kdtree, kdbuf, flatmap);
nuclear@35 225
nuclear@35 226 assert(validate_flat_tree(kdtree, kdbuf, count, flatmap));
nuclear@35 227
nuclear@28 228 return kdbuf;
nuclear@28 229 }
nuclear@28 230
nuclear@35 231 static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap)
nuclear@28 232 {
nuclear@38 233 const size_t max_node_items = sizeof kdbuf[0].face_idx / sizeof kdbuf[0].face_idx[0];
nuclear@35 234 int idx = (*count)++;
nuclear@29 235
nuclear@35 236 // copy the node
nuclear@35 237 kdbuf[idx].aabb = node->aabb;
nuclear@38 238 kdbuf[idx].num_faces = 0;
nuclear@38 239
nuclear@35 240 for(size_t i=0; i<node->face_idx.size(); i++) {
nuclear@38 241 if(i >= max_node_items) {
nuclear@38 242 fprintf(stderr, "WARNING too many faces per leaf node!\n");
nuclear@38 243 break;
nuclear@38 244 }
nuclear@35 245 kdbuf[idx].face_idx[i] = node->face_idx[i];
nuclear@38 246 kdbuf[idx].num_faces++;
nuclear@28 247 }
nuclear@35 248
nuclear@35 249 // update the node* -> array-position mapping
nuclear@35 250 (*flatmap)[node] = idx;
nuclear@35 251
nuclear@35 252 // recurse to the left/right (if we're not in a leaf node)
nuclear@35 253 if(node->left) {
nuclear@35 254 assert(node->right);
nuclear@35 255
nuclear@35 256 flatten_kdtree(node->left, kdbuf, count, flatmap);
nuclear@35 257 flatten_kdtree(node->right, kdbuf, count, flatmap);
nuclear@35 258 }
nuclear@28 259 }
nuclear@28 260
nuclear@35 261 static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap)
nuclear@29 262 {
nuclear@35 263 std::map<const KDNode*, int>::const_iterator it = flatmap.find(node);
nuclear@35 264 assert(it != flatmap.end());
nuclear@35 265 return it->second;
nuclear@35 266 }
nuclear@35 267
nuclear@35 268 static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap)
nuclear@35 269 {
nuclear@35 270 if(!node) return;
nuclear@35 271
nuclear@35 272 int idx = find_node_index(node, flatmap);
nuclear@35 273
nuclear@35 274 kdbuf[idx].left = find_node_index(node->left, flatmap);
nuclear@35 275 if(!node->left && kdbuf[idx].left != -1) abort();
nuclear@35 276 kdbuf[idx].right = find_node_index(node->right, flatmap);
nuclear@35 277 if(!node->right && kdbuf[idx].right != -1) abort();
nuclear@35 278
nuclear@35 279 fix_child_links(node->left, kdbuf, flatmap);
nuclear@35 280 fix_child_links(node->right, kdbuf, flatmap);
nuclear@29 281 }
nuclear@24 282
nuclear@27 283 void Scene::draw_kdtree() const
nuclear@27 284 {
nuclear@27 285 glPushAttrib(GL_ENABLE_BIT);
nuclear@27 286 glDisable(GL_LIGHTING);
nuclear@27 287 glDepthMask(0);
nuclear@27 288
nuclear@27 289 glBegin(GL_LINES);
nuclear@27 290 ::draw_kdtree(kdtree, 0);
nuclear@27 291 glEnd();
nuclear@27 292
nuclear@27 293 glDepthMask(1);
nuclear@27 294 glPopAttrib();
nuclear@27 295 }
nuclear@27 296
nuclear@27 297 static float palette[][3] = {
nuclear@27 298 {0, 1, 0},
nuclear@27 299 {1, 0, 0},
nuclear@27 300 {0, 0, 1},
nuclear@27 301 {1, 1, 0},
nuclear@27 302 {0, 0, 1},
nuclear@27 303 {1, 0, 1}
nuclear@27 304 };
nuclear@27 305 static int pal_size = sizeof palette / sizeof *palette;
nuclear@27 306
nuclear@27 307 static void draw_kdtree(const KDNode *node, int level)
nuclear@27 308 {
nuclear@27 309 if(!node) return;
nuclear@27 310
nuclear@27 311 draw_kdtree(node->left, level + 1);
nuclear@27 312 draw_kdtree(node->right, level + 1);
nuclear@27 313
nuclear@27 314 glColor3fv(palette[level % pal_size]);
nuclear@27 315
nuclear@27 316 glVertex3fv(node->aabb.min);
nuclear@27 317 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
nuclear@27 318 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
nuclear@27 319 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 320 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 321 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 322 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 323 glVertex3fv(node->aabb.min);
nuclear@27 324
nuclear@27 325 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 326 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 327 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 328 glVertex3fv(node->aabb.max);
nuclear@27 329 glVertex3fv(node->aabb.max);
nuclear@27 330 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
nuclear@27 331 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
nuclear@27 332 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 333
nuclear@27 334 glVertex3fv(node->aabb.min);
nuclear@27 335 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 336 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);
nuclear@27 337 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);
nuclear@27 338 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 339 glVertex3fv(node->aabb.max);
nuclear@27 340 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);
nuclear@27 341 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);
nuclear@34 342 /*if(!node->left) return;
nuclear@34 343
nuclear@34 344 AABBox *bleft = &node->left->aabb;
nuclear@34 345
nuclear@34 346 int axis = level % 3;
nuclear@34 347 switch(axis) {
nuclear@34 348 case 0:
nuclear@34 349 glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);
nuclear@34 350 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
nuclear@34 351 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
nuclear@34 352 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
nuclear@34 353 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
nuclear@34 354 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
nuclear@34 355 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
nuclear@34 356 glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);
nuclear@34 357 break;
nuclear@37 358
nuclear@34 359 case 1:
nuclear@34 360 glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
nuclear@34 361 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
nuclear@34 362 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
nuclear@34 363 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
nuclear@34 364 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
nuclear@34 365 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
nuclear@34 366 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);
nuclear@34 367 glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);
nuclear@34 368 break;
nuclear@37 369
nuclear@34 370 case 2:
nuclear@34 371 glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);
nuclear@34 372 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
nuclear@34 373 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);
nuclear@34 374 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
nuclear@34 375 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);
nuclear@34 376 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
nuclear@34 377 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);
nuclear@34 378 glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);
nuclear@34 379 break;
nuclear@34 380
nuclear@34 381 default:
nuclear@34 382 break;
nuclear@34 383 }*/
nuclear@27 384 }
nuclear@27 385
nuclear@27 386 bool Scene::build_kdtree()
nuclear@24 387 {
nuclear@29 388 assert(kdtree == 0);
nuclear@29 389
nuclear@24 390 const Face *faces = get_face_buffer();
nuclear@24 391 int num_faces = get_num_faces();
nuclear@24 392
nuclear@25 393 printf("Constructing kd-tree out of %d faces ...\n", num_faces);
nuclear@25 394
nuclear@27 395 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];
nuclear@27 396 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
nuclear@27 397 printf(" max items per leaf: %d\n", accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]);
nuclear@27 398 printf(" SAH parameters - tcost: %d - icost: %d\n", tcost, icost);
nuclear@27 399
nuclear@25 400 free_kdtree(kdtree);
nuclear@25 401 kdtree = new KDNode;
nuclear@25 402
nuclear@25 403 /* Start the construction of the kdtree by adding all faces of the scene
nuclear@25 404 * to the new root node. At the same time calculate the root's AABB.
nuclear@25 405 */
nuclear@25 406 kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX;
nuclear@25 407 kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX;
nuclear@25 408
nuclear@24 409 for(int i=0; i<num_faces; i++) {
nuclear@25 410 const Face *face = faces + i;
nuclear@25 411
nuclear@25 412 // for each vertex of the face ...
nuclear@25 413 for(int j=0; j<3; j++) {
nuclear@25 414 const float *pos = face->v[j].pos;
nuclear@25 415
nuclear@25 416 // for each element (xyz) of the position vector ...
nuclear@25 417 for(int k=0; k<3; k++) {
nuclear@25 418 if(pos[k] < kdtree->aabb.min[k]) {
nuclear@25 419 kdtree->aabb.min[k] = pos[k];
nuclear@25 420 }
nuclear@25 421 if(pos[k] > kdtree->aabb.max[k]) {
nuclear@25 422 kdtree->aabb.max[k] = pos[k];
nuclear@25 423 }
nuclear@25 424 }
nuclear@25 425 }
nuclear@25 426
nuclear@32 427 kdtree->face_idx.push_back(i); // add the face
nuclear@24 428 }
nuclear@24 429
nuclear@38 430 CHECK_AABB(kdtree->aabb);
nuclear@38 431
nuclear@26 432 // calculate the heuristic for the root
nuclear@32 433 kdtree->cost = eval_cost(faces, &kdtree->face_idx[0], kdtree->face_idx.size(), kdtree->aabb, 0);
nuclear@26 434
nuclear@25 435 // now proceed splitting the root recursively
nuclear@32 436 if(!::build_kdtree(kdtree, faces)) {
nuclear@27 437 fprintf(stderr, "failed to build kdtree\n");
nuclear@27 438 return false;
nuclear@27 439 }
nuclear@27 440
nuclear@27 441 printf(" tree depth: %d\n", kdtree_depth(kdtree));
nuclear@27 442 print_item_counts(kdtree, 0);
nuclear@27 443 return true;
nuclear@24 444 }
nuclear@24 445
nuclear@37 446 struct Split {
nuclear@37 447 int axis;
nuclear@37 448 float pos;
nuclear@37 449 float sum_cost;
nuclear@37 450 float cost_left, cost_right;
nuclear@37 451 };
nuclear@37 452
nuclear@37 453 static void find_best_split(const KDNode *node, int axis, const Face *faces, Split *split)
nuclear@37 454 {
nuclear@37 455 Split best_split;
nuclear@37 456 best_split.sum_cost = FLT_MAX;
nuclear@37 457
nuclear@37 458 for(size_t i=0; i<node->face_idx.size(); i++) {
nuclear@37 459 const Face *face = faces + node->face_idx[i];
nuclear@37 460
nuclear@37 461 float splitpt[2];
nuclear@37 462 splitpt[0] = MIN(face->v[0].pos[axis], MIN(face->v[1].pos[axis], face->v[2].pos[axis]));
nuclear@37 463 splitpt[1] = MAX(face->v[0].pos[axis], MAX(face->v[1].pos[axis], face->v[2].pos[axis]));
nuclear@37 464
nuclear@37 465 for(int j=0; j<2; j++) {
nuclear@38 466 if(splitpt[j] <= node->aabb.min[axis] || splitpt[j] >= node->aabb.max[axis]) {
nuclear@38 467 continue;
nuclear@38 468 }
nuclear@38 469
nuclear@37 470 AABBox aabb_left, aabb_right;
nuclear@37 471 aabb_left = aabb_right = node->aabb;
nuclear@37 472 aabb_left.max[axis] = splitpt[j];
nuclear@37 473 aabb_right.min[axis] = splitpt[j];
nuclear@37 474
nuclear@37 475 float left_cost = eval_cost(faces, &node->face_idx[0], node->face_idx.size(), aabb_left, axis);
nuclear@37 476 float right_cost = eval_cost(faces, &node->face_idx[0], node->face_idx.size(), aabb_right, axis);
nuclear@37 477 float sum_cost = left_cost + right_cost - accel_param[ACCEL_PARAM_COST_TRAVERSE]; // tcost is added twice
nuclear@37 478
nuclear@37 479 if(sum_cost < best_split.sum_cost) {
nuclear@37 480 best_split.cost_left = left_cost;
nuclear@37 481 best_split.cost_right = right_cost;
nuclear@37 482 best_split.sum_cost = sum_cost;
nuclear@37 483 best_split.pos = splitpt[j];
nuclear@37 484 }
nuclear@37 485 }
nuclear@37 486 }
nuclear@37 487
nuclear@37 488 assert(split);
nuclear@37 489 *split = best_split;
nuclear@37 490 split->axis = axis;
nuclear@37 491 }
nuclear@37 492
nuclear@32 493 static bool build_kdtree(KDNode *kd, const Face *faces, int level)
nuclear@24 494 {
nuclear@28 495 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];
nuclear@26 496 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];
nuclear@27 497
nuclear@32 498 if(kd->face_idx.empty() || level >= opt_max_depth) {
nuclear@27 499 return true;
nuclear@25 500 }
nuclear@25 501
nuclear@37 502 Split best_split;
nuclear@38 503 best_split.axis = -1;
nuclear@37 504 best_split.sum_cost = FLT_MAX;
nuclear@26 505
nuclear@38 506 for(int i=0; i<3; i++) {
nuclear@37 507 Split split;
nuclear@37 508 find_best_split(kd, i, faces, &split);
nuclear@26 509
nuclear@37 510 if(split.sum_cost < best_split.sum_cost) {
nuclear@37 511 best_split = split;
nuclear@26 512 }
nuclear@26 513 }
nuclear@26 514
nuclear@38 515 if(best_split.axis == -1) {
nuclear@38 516 return true; // can't split any more, only 0-area splits available
nuclear@38 517 }
nuclear@37 518
nuclear@29 519 //printf("current cost: %f, best_cost: %f\n", kd->cost, best_sum_cost);
nuclear@37 520 if(best_split.sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) {
nuclear@27 521 return true; // stop splitting if it doesn't reduce the cost
nuclear@26 522 }
nuclear@26 523
nuclear@38 524 kd->axis = best_split.axis;
nuclear@38 525
nuclear@26 526 // create the two children
nuclear@26 527 KDNode *kdleft, *kdright;
nuclear@26 528 kdleft = new KDNode;
nuclear@26 529 kdright = new KDNode;
nuclear@26 530
nuclear@26 531 kdleft->aabb = kdright->aabb = kd->aabb;
nuclear@26 532
nuclear@37 533 kdleft->aabb.max[kd->axis] = best_split.pos;
nuclear@37 534 kdright->aabb.min[kd->axis] = best_split.pos;
nuclear@26 535
nuclear@37 536 kdleft->cost = best_split.cost_left;
nuclear@37 537 kdright->cost = best_split.cost_right;
nuclear@26 538
nuclear@34 539 // TODO would it be much better if we actually split faces that straddle the splitting plane?
nuclear@32 540 for(size_t i=0; i<kd->face_idx.size(); i++) {
nuclear@32 541 int fidx = kd->face_idx[i];
nuclear@32 542 const Face *face = faces + fidx;
nuclear@26 543
nuclear@37 544 if(face->v[0].pos[kd->axis] < best_split.pos ||
nuclear@37 545 face->v[1].pos[kd->axis] < best_split.pos ||
nuclear@37 546 face->v[2].pos[kd->axis] < best_split.pos) {
nuclear@32 547 kdleft->face_idx.push_back(fidx);
nuclear@26 548 }
nuclear@37 549 if(face->v[0].pos[kd->axis] >= best_split.pos ||
nuclear@37 550 face->v[1].pos[kd->axis] >= best_split.pos ||
nuclear@37 551 face->v[2].pos[kd->axis] >= best_split.pos) {
nuclear@32 552 kdright->face_idx.push_back(fidx);
nuclear@26 553 }
nuclear@26 554 }
nuclear@32 555 kd->face_idx.clear(); // only leaves have faces
nuclear@26 556
nuclear@26 557 kd->left = kdleft;
nuclear@26 558 kd->right = kdright;
nuclear@27 559
nuclear@32 560 return build_kdtree(kd->left, faces, level + 1) && build_kdtree(kd->right, faces, level + 1);
nuclear@26 561 }
nuclear@26 562
nuclear@32 563 static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis)
nuclear@26 564 {
nuclear@26 565 int num_inside = 0;
nuclear@26 566 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
nuclear@26 567 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];
nuclear@26 568
nuclear@32 569 for(int i=0; i<num_faces; i++) {
nuclear@32 570 const Face *face = faces + face_idx[i];
nuclear@26 571
nuclear@32 572 for(int j=0; j<3; j++) {
nuclear@32 573 if(face->v[j].pos[axis] >= aabb.min[axis] && face->v[j].pos[axis] < aabb.max[axis]) {
nuclear@26 574 num_inside++;
nuclear@26 575 break;
nuclear@26 576 }
nuclear@26 577 }
nuclear@26 578 }
nuclear@26 579
nuclear@38 580 float dx = aabb.max[0] - aabb.min[0];
nuclear@38 581 float dy = aabb.max[1] - aabb.min[1];
nuclear@38 582 float dz = aabb.max[2] - aabb.min[2];
nuclear@38 583
nuclear@38 584 if(dx < 0.0) {
nuclear@38 585 fprintf(stderr, "FOO DX = %f\n", dx);
nuclear@38 586 abort();
nuclear@38 587 }
nuclear@38 588 if(dy < 0.0) {
nuclear@38 589 fprintf(stderr, "FOO DX = %f\n", dy);
nuclear@38 590 abort();
nuclear@38 591 }
nuclear@38 592 if(dz < 0.0) {
nuclear@38 593 fprintf(stderr, "FOO DX = %f\n", dz);
nuclear@38 594 abort();
nuclear@38 595 }
nuclear@38 596
nuclear@38 597 if(dx < 1e-6 || dy < 1e-6 || dz < 1e-6) {
nuclear@27 598 return FLT_MAX; // heavily penalize 0-area voxels
nuclear@27 599 }
nuclear@27 600
nuclear@38 601 float sarea = 2.0 * (dx + dy + dz);//aabb.calc_surface_area();
nuclear@32 602 return tcost + sarea * num_inside * icost;
nuclear@24 603 }
nuclear@25 604
nuclear@25 605 static void free_kdtree(KDNode *node)
nuclear@25 606 {
nuclear@25 607 if(node) {
nuclear@25 608 free_kdtree(node->left);
nuclear@25 609 free_kdtree(node->right);
nuclear@25 610 delete node;
nuclear@25 611 }
nuclear@25 612 }
nuclear@27 613
nuclear@28 614 int kdtree_depth(const KDNode *node)
nuclear@27 615 {
nuclear@27 616 if(!node) return 0;
nuclear@27 617
nuclear@27 618 int left = kdtree_depth(node->left);
nuclear@27 619 int right = kdtree_depth(node->right);
nuclear@27 620 return (left > right ? left : right) + 1;
nuclear@27 621 }
nuclear@27 622
nuclear@28 623 int kdtree_nodes(const KDNode *node)
nuclear@28 624 {
nuclear@28 625 if(!node) return 0;
nuclear@28 626 return kdtree_nodes(node->left) + kdtree_nodes(node->right) + 1;
nuclear@28 627 }
nuclear@28 628
nuclear@27 629 static void print_item_counts(const KDNode *node, int level)
nuclear@27 630 {
nuclear@27 631 if(!node) return;
nuclear@27 632
nuclear@30 633 for(int i=0; i<level; i++) {
nuclear@27 634 fputs(" ", stdout);
nuclear@27 635 }
nuclear@32 636 printf("- %d (cost: %f)\n", (int)node->face_idx.size(), node->cost);
nuclear@27 637
nuclear@27 638 print_item_counts(node->left, level + 1);
nuclear@27 639 print_item_counts(node->right, level + 1);
nuclear@27 640 }