clray

annotate src/scene.cc @ 62:d9520da6b801

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