intern/cycles/bvh/bvh.cpp

   1 /*
   2  * Adapted from code copyright 2009-2010 NVIDIA Corporation
   3  * Modifications Copyright 2011, Blender Foundation.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 #include "mesh.h"
  19 #include "object.h"
  20 #include "scene.h"
  21
  22 #include "bvh.h"
  23 #include "bvh_build.h"
  24 #include "bvh_node.h"
  25 #include "bvh_params.h"
  26
  27 #include "util_cache.h"
  28 #include "util_debug.h"
  29 #include "util_foreach.h"
  30 #include "util_map.h"
  31 #include "util_progress.h"
  32 #include "util_types.h"
  33
  34 CCL_NAMESPACE_BEGIN
  35
  36 /* Pack Utility */
  37
  38 struct BVHStackEntry
  39 {
  40         const BVHNode *node;
  41         int idx;
  42
  43         BVHStackEntry(const BVHNode* n = 0, int i = 0)
  44         : node(n), idx(i)
  45         {
  46         }
  47
  48         int encodeIdx() const
  49         {
  50                 return (node->is_leaf())? ~idx: idx;
  51         }
  52 };
  53
  54 /* BVH */
  55
  56 BVH::BVH(const BVHParams& params_, const vector<Object*>& objects_)
  57 : params(params_), objects(objects_)
  58 {
  59 }
  60
  61 BVH *BVH::create(const BVHParams& params, const vector<Object*>& objects)
  62 {
  63         if(params.use_qbvh)
  64                 return new QBVH(params, objects);
  65         else
  66                 return new RegularBVH(params, objects);
  67 }
  68
  69 /* Cache */
  70
  71 bool BVH::cache_read(CacheData& key)
  72 {
  73         key.add(&params, sizeof(params));
  74
  75         foreach(Object *ob, objects) {
  76                 key.add(ob->mesh->verts);
  77                 key.add(ob->mesh->triangles);
  78         }
  79
  80         CacheData value;
  81
  82         if(Cache::global.lookup(key, value)) {
  83                 value.read(pack.root_index);
  84
  85                 value.read(pack.nodes);
  86                 value.read(pack.object_node);
  87                 value.read(pack.tri_woop);
  88                 value.read(pack.prim_visibility);
  89                 value.read(pack.prim_index);
  90                 value.read(pack.prim_object);
  91                 value.read(pack.is_leaf);
  92
  93                 return true;
  94         }
  95
  96         return false;
  97 }
  98
  99 void BVH::cache_write(CacheData& key)
 100 {
 101         CacheData value;
 102
 103         value.add(pack.root_index);
 104
 105         value.add(pack.nodes);
 106         value.add(pack.object_node);
 107         value.add(pack.tri_woop);
 108         value.add(pack.prim_visibility);
 109         value.add(pack.prim_index);
 110         value.add(pack.prim_object);
 111         value.add(pack.is_leaf);
 112
 113         Cache::global.insert(key, value);
 114 }
 115
 116 /* Building */
 117
 118 void BVH::build(Progress& progress)
 119 {
 120         progress.set_substatus("Building BVH");
 121
 122         /* cache read */
 123         CacheData key("bvh");
 124
 125         if(params.use_cache) {
 126                 progress.set_substatus("Looking in BVH cache");
 127
 128                 if(cache_read(key))
 129                         return;
 130         }
 131
 132         /* build nodes */
 133         vector<int> prim_index;
 134         vector<int> prim_object;
 135
 136         BVHBuild bvh_build(objects, prim_index, prim_object, params, progress);
 137         BVHNode *root = bvh_build.run();
 138
 139         if(progress.get_cancel()) {
 140                 if(root) root->deleteSubtree();
 141                 return;
 142         }
 143
 144         /* todo: get rid of this copy */
 145         pack.prim_index = prim_index;
 146         pack.prim_object = prim_object;
 147
 148         /* compute SAH */
 149         if(!params.top_level)
 150                 pack.SAH = root->computeSubtreeSAHCost(params);
 151
 152         if(progress.get_cancel()) {
 153                 root->deleteSubtree();
 154                 return;
 155         }
 156
 157         /* pack triangles */
 158         progress.set_substatus("Packing BVH triangles");
 159         pack_triangles();
 160
 161         if(progress.get_cancel()) {
 162                 root->deleteSubtree();
 163                 return;
 164         }
 165
 166         /* pack nodes */
 167         progress.set_substatus("Packing BVH nodes");
 168         array<int> tmp_prim_object = pack.prim_object;
 169         pack_nodes(tmp_prim_object, root);
 170
 171         /* free build nodes */
 172         root->deleteSubtree();
 173
 174         if(progress.get_cancel()) return;
 175
 176         /* cache write */
 177         if(params.use_cache) {
 178                 progress.set_substatus("Writing BVH cache");
 179                 cache_write(key);
 180         }
 181 }
 182
 183 /* Refitting */
 184
 185 void BVH::refit(Progress& progress)
 186 {
 187         progress.set_substatus("Packing BVH triangles");
 188         pack_triangles();
 189
 190         if(progress.get_cancel()) return;
 191
 192         progress.set_substatus("Refitting BVH nodes");
 193         refit_nodes();
 194 }
 195
 196 /* Triangles */
 197
 198 void BVH::pack_triangle(int idx, float4 woop[3])
 199 {
 200         /* create Woop triangle */
 201         int tob = pack.prim_object[idx];
 202         const Mesh *mesh = objects[tob]->mesh;
 203         int tidx = pack.prim_index[idx];
 204         const int *vidx = mesh->triangles[tidx].v;
 205         const float3* vpos = &mesh->verts[0];
 206         float3 v0 = vpos[vidx[0]];
 207         float3 v1 = vpos[vidx[1]];
 208         float3 v2 = vpos[vidx[2]];
 209
 210         float3 r0 = v0 - v2;
 211         float3 r1 = v1 - v2;
 212         float3 r2 = cross(r0, r1);
 213
 214         if(dot(r0, r0) == 0.0f || dot(r1, r1) == 0.0f || dot(r2, r2) == 0.0f) {
 215                 /* degenerate */
 216                 woop[0] = make_float4(0.0f, 0.0f, 0.0f, 0.0f);
 217                 woop[1] = make_float4(0.0f, 0.0f, 0.0f, 0.0f);
 218                 woop[2] = make_float4(0.0f, 0.0f, 0.0f, 0.0f);
 219         }
 220         else {
 221                 Transform t = make_transform(
 222                         r0.x, r1.x, r2.x, v2.x,
 223                         r0.y, r1.y, r2.y, v2.y,
 224                         r0.z, r1.z, r2.z, v2.z,
 225                         0.0f, 0.0f, 0.0f, 1.0f);
 226
 227                 t = transform_inverse(t);
 228
 229                 woop[0] = make_float4(t.z.x, t.z.y, t.z.z, -t.z.w);
 230                 woop[1] = make_float4(t.x.x, t.x.y, t.x.z, t.x.w);
 231                 woop[2] = make_float4(t.y.x, t.y.y, t.y.z, t.y.w);
 232         }
 233 }
 234
 235 void BVH::pack_triangles()
 236 {
 237         int nsize = TRI_NODE_SIZE;
 238         size_t tidx_size = pack.prim_index.size();
 239
 240         pack.tri_woop.clear();
 241         pack.tri_woop.resize(tidx_size * nsize);
 242         pack.prim_visibility.clear();
 243         pack.prim_visibility.resize(tidx_size);
 244
 245         for(unsigned int i = 0; i < tidx_size; i++) {
 246                 if(pack.prim_index[i] != -1) {
 247                         float4 woop[3];
 248
 249                         pack_triangle(i, woop);
 250                         memcpy(&pack.tri_woop[i * nsize], woop, sizeof(float4)*3);
 251
 252                         int tob = pack.prim_object[i];
 253                         Object *ob = objects[tob];
 254                         pack.prim_visibility[i] = ob->visibility;
 255                 }
 256         }
 257 }
 258
 259 /* Pack Instances */
 260
 261 void BVH::pack_instances(size_t nodes_size)
 262 {
 263         /* The BVH's for instances are built separately, but for traversal all
 264            BVH's are stored in global arrays. This function merges them into the
 265            top level BVH, adjusting indexes and offsets where appropriate. */
 266         bool use_qbvh = params.use_qbvh;
 267         size_t nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
 268
 269         /* adjust primitive index to point to the triangle in the global array, for
 270            meshes with transform applied and already in the top level BVH */
 271         for(size_t i = 0; i < pack.prim_index.size(); i++)
 272                 if(pack.prim_index[i] != -1)
 273                         pack.prim_index[i] += objects[pack.prim_object[i]]->mesh->tri_offset;
 274
 275         /* track offsets of instanced BVH data in global array */
 276         size_t tri_offset = pack.prim_index.size();
 277         size_t nodes_offset = nodes_size;
 278
 279         /* clear array that gives the node indexes for instanced objects */
 280         pack.object_node.clear();
 281
 282         /* reserve */
 283         size_t prim_index_size = pack.prim_index.size();
 284         size_t tri_woop_size = pack.tri_woop.size();
 285
 286         size_t pack_prim_index_offset = prim_index_size;
 287         size_t pack_tri_woop_offset = tri_woop_size;
 288         size_t pack_nodes_offset = nodes_size;
 289         size_t object_offset = 0;
 290
 291         map<Mesh*, int> mesh_map;
 292
 293         foreach(Object *ob, objects) {
 294                 Mesh *mesh = ob->mesh;
 295                 BVH *bvh = mesh->bvh;
 296
 297                 if(!mesh->transform_applied) {
 298                         if(mesh_map.find(mesh) == mesh_map.end()) {
 299                                 prim_index_size += bvh->pack.prim_index.size();
 300                                 tri_woop_size += bvh->pack.tri_woop.size();
 301                                 nodes_size += bvh->pack.nodes.size()*nsize;
 302
 303                                 mesh_map[mesh] = 1;
 304                         }
 305                 }
 306         }
 307
 308         mesh_map.clear();
 309
 310         pack.prim_index.resize(prim_index_size);
 311         pack.prim_object.resize(prim_index_size);
 312         pack.prim_visibility.resize(prim_index_size);
 313         pack.tri_woop.resize(tri_woop_size);
 314         pack.nodes.resize(nodes_size);
 315         pack.object_node.resize(objects.size());
 316
 317         int *pack_prim_index = &pack.prim_index[0];
 318         int *pack_prim_object = &pack.prim_object[0];
 319         uint *pack_prim_visibility = &pack.prim_visibility[0];
 320         float4 *pack_tri_woop = &pack.tri_woop[0];
 321         int4 *pack_nodes = &pack.nodes[0];
 322
 323         /* merge */
 324         foreach(Object *ob, objects) {
 325                 Mesh *mesh = ob->mesh;
 326
 327                 /* if mesh transform is applied, that means it's already in the top
 328                    level BVH, and we don't need to merge it in */
 329                 if(mesh->transform_applied) {
 330                         pack.object_node[object_offset++] = 0;
 331                         continue;
 332                 }
 333
 334                 /* if mesh already added once, don't add it again, but used set
 335                    node offset for this object */
 336                 map<Mesh*, int>::iterator it = mesh_map.find(mesh);
 337
 338                 if(mesh_map.find(mesh) != mesh_map.end()) {
 339                         int noffset = it->second;
 340                         pack.object_node[object_offset++] = noffset;
 341                         continue;
 342                 }
 343
 344                 BVH *bvh = mesh->bvh;
 345
 346                 int noffset = nodes_offset/nsize;
 347                 int mesh_tri_offset = mesh->tri_offset;
 348
 349                 /* fill in node indexes for instances */
 350                 if(bvh->pack.is_leaf[0])
 351                         pack.object_node[object_offset++] = -noffset-1;
 352                 else
 353                         pack.object_node[object_offset++] = noffset;
 354
 355                 mesh_map[mesh] = pack.object_node[object_offset-1];
 356
 357                 /* merge primitive and object indexes */
 358                 {
 359                         size_t bvh_prim_index_size = bvh->pack.prim_index.size();
 360                         int *bvh_prim_index = &bvh->pack.prim_index[0];
 361                         uint *bvh_prim_visibility = &bvh->pack.prim_visibility[0];
 362
 363                         for(size_t i = 0; i < bvh_prim_index_size; i++) {
 364                                 pack_prim_index[pack_prim_index_offset] = bvh_prim_index[i] + mesh_tri_offset;
 365                                 pack_prim_visibility[pack_prim_index_offset] = bvh_prim_visibility[i];
 366                                 pack_prim_object[pack_prim_index_offset] = 0;  // unused for instances
 367                                 pack_prim_index_offset++;
 368                         }
 369                 }
 370
 371                 /* merge triangle intersection data */
 372                 {
 373                         memcpy(pack_tri_woop+pack_tri_woop_offset, &bvh->pack.tri_woop[0],
 374                                 bvh->pack.tri_woop.size()*sizeof(float4));
 375                         pack_tri_woop_offset += bvh->pack.tri_woop.size();
 376                 }
 377
 378                 /* merge nodes */
 379                 {
 380                         size_t nsize_bbox = (use_qbvh)? nsize-2: nsize-1;
 381                         int4 *bvh_nodes = &bvh->pack.nodes[0];
 382                         size_t bvh_nodes_size = bvh->pack.nodes.size();
 383                         int *bvh_is_leaf = &bvh->pack.is_leaf[0];
 384
 385                         for(size_t i = 0, j = 0; i < bvh_nodes_size; i+=nsize, j++) {
 386                                 memcpy(pack_nodes + pack_nodes_offset, bvh_nodes + i, nsize_bbox*sizeof(int4));
 387
 388                                 /* modify offsets into arrays */
 389                                 int4 data = bvh_nodes[i + nsize_bbox];
 390
 391                                 if(bvh_is_leaf[j]) {
 392                                         data.x += tri_offset;
 393                                         data.y += tri_offset;
 394                                 }
 395                                 else {
 396                                         data.x += (data.x < 0)? -noffset: noffset;
 397                                         data.y += (data.y < 0)? -noffset: noffset;
 398
 399                                         if(use_qbvh) {
 400                                                 data.z += (data.z < 0)? -noffset: noffset;
 401                                                 data.w += (data.w < 0)? -noffset: noffset;
 402                                         }
 403                                 }
 404
 405                                 pack_nodes[pack_nodes_offset + nsize_bbox] = data;
 406
 407                                 if(use_qbvh)
 408                                         pack_nodes[pack_nodes_offset + nsize_bbox+1] = bvh_nodes[i + nsize_bbox+1];
 409
 410                                 pack_nodes_offset += nsize;
 411                         }
 412                 }
 413
 414                 nodes_offset += bvh->pack.nodes.size();
 415                 tri_offset += bvh->pack.prim_index.size();
 416         }
 417 }
 418
 419 /* Regular BVH */
 420
 421 RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_)
 422 : BVH(params_, objects_)
 423 {
 424 }
 425
 426 void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 427 {
 428         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1)
 429                 /* object */
 430                 pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, ~(leaf->m_lo), 0, leaf->m_visibility, leaf->m_visibility);
 431         else
 432                 /* triangle */
 433                 pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, leaf->m_lo, leaf->m_hi, leaf->m_visibility, leaf->m_visibility);
 434 }
 435
 436 void RegularBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry& e0, const BVHStackEntry& e1)
 437 {
 438         pack_node(e.idx, e0.node->m_bounds, e1.node->m_bounds, e0.encodeIdx(), e1.encodeIdx(), e0.node->m_visibility, e1.node->m_visibility);
 439 }
 440
 441 void RegularBVH::pack_node(int idx, const BoundBox& b0, const BoundBox& b1, int c0, int c1, uint visibility0, uint visibility1)
 442 {
 443         int4 data[BVH_NODE_SIZE] =
 444         {
 445                 make_int4(__float_as_int(b0.min.x), __float_as_int(b0.max.x), __float_as_int(b0.min.y), __float_as_int(b0.max.y)),
 446                 make_int4(__float_as_int(b1.min.x), __float_as_int(b1.max.x), __float_as_int(b1.min.y), __float_as_int(b1.max.y)),
 447                 make_int4(__float_as_int(b0.min.z), __float_as_int(b0.max.z), __float_as_int(b1.min.z), __float_as_int(b1.max.z)),
 448                 make_int4(c0, c1, visibility0, visibility1)
 449         };
 450
 451         memcpy(&pack.nodes[idx * BVH_NODE_SIZE], data, sizeof(int4)*BVH_NODE_SIZE);
 452 }
 453
 454 void RegularBVH::pack_nodes(const array<int>& prims, const BVHNode *root)
 455 {
 456         size_t node_size = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
 457
 458         /* resize arrays */
 459         pack.nodes.clear();
 460         pack.is_leaf.clear();
 461         pack.is_leaf.resize(node_size);
 462
 463         /* for top level BVH, first merge existing BVH's so we know the offsets */
 464         if(params.top_level)
 465                 pack_instances(node_size*BVH_NODE_SIZE);
 466         else
 467                 pack.nodes.resize(node_size*BVH_NODE_SIZE);
 468
 469         int nextNodeIdx = 0;
 470
 471         vector<BVHStackEntry> stack;
 472         stack.push_back(BVHStackEntry(root, nextNodeIdx++));
 473
 474         while(stack.size()) {
 475                 BVHStackEntry e = stack.back();
 476                 stack.pop_back();
 477
 478                 pack.is_leaf[e.idx] = e.node->is_leaf();
 479
 480                 if(e.node->is_leaf()) {
 481                         /* leaf node */
 482                         const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
 483                         pack_leaf(e, leaf);
 484                 }
 485                 else {
 486                         /* innner node */
 487                         stack.push_back(BVHStackEntry(e.node->get_child(0), nextNodeIdx++));
 488                         stack.push_back(BVHStackEntry(e.node->get_child(1), nextNodeIdx++));
 489
 490                         pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
 491                 }
 492         }
 493
 494         /* root index to start traversal at, to handle case of single leaf node */
 495         pack.root_index = (pack.is_leaf[0])? -1: 0;
 496 }
 497
 498 void RegularBVH::refit_nodes()
 499 {
 500         assert(!params.top_level);
 501
 502         BoundBox bbox;
 503         uint visibility = 0;
 504         refit_node(0, (pack.is_leaf[0])? true: false, bbox, visibility);
 505 }
 506
 507 void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
 508 {
 509         int4 *data = &pack.nodes[idx*4];
 510
 511         int c0 = data[3].x;
 512         int c1 = data[3].y;
 513
 514         if(leaf) {
 515                 /* refit leaf node */
 516                 for(int tri = c0; tri < c1; tri++) {
 517                         int tidx = pack.prim_index[tri];
 518                         int tob = pack.prim_object[tri];
 519                         Object *ob = objects[tob];
 520
 521                         if(tidx == -1) {
 522                                 /* object instance */
 523                                 bbox.grow(ob->bounds);
 524                         }
 525                         else {
 526                                 /* triangles */
 527                                 const Mesh *mesh = ob->mesh;
 528                                 int tri_offset = (params.top_level)? mesh->tri_offset: 0;
 529                                 const int *vidx = mesh->triangles[tidx - tri_offset].v;
 530                                 const float3 *vpos = &mesh->verts[0];
 531
 532                                 bbox.grow(vpos[vidx[0]]);
 533                                 bbox.grow(vpos[vidx[1]]);
 534                                 bbox.grow(vpos[vidx[2]]);
 535                         }
 536
 537                         visibility |= ob->visibility;
 538                 }
 539
 540                 pack_node(idx, bbox, bbox, c0, c1, visibility, visibility);
 541         }
 542         else {
 543                 /* refit inner node, set bbox from children */
 544                 BoundBox bbox0, bbox1;
 545                 uint visibility0 = 0, visibility1 = 0;
 546
 547                 refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
 548                 refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
 549
 550                 pack_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
 551
 552                 bbox.grow(bbox0);
 553                 bbox.grow(bbox1);
 554                 visibility = visibility0|visibility1;
 555         }
 556 }
 557
 558 /* QBVH */
 559
 560 QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_)
 561 : BVH(params_, objects_)
 562 {
 563         params.use_qbvh = true;
 564
 565         /* todo: use visibility */
 566 }
 567
 568 void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 569 {
 570         float4 data[BVH_QNODE_SIZE];
 571
 572         memset(data, 0, sizeof(data));
 573
 574         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
 575                 /* object */
 576                 data[6].x = __int_as_float(~(leaf->m_lo));
 577                 data[6].y = __int_as_float(0);
 578         }
 579         else {
 580                 /* triangle */
 581                 data[6].x = __int_as_float(leaf->m_lo);
 582                 data[6].y = __int_as_float(leaf->m_hi);
 583         }
 584
 585         memcpy(&pack.nodes[e.idx * BVH_QNODE_SIZE], data, sizeof(float4)*BVH_QNODE_SIZE);
 586 }
 587
 588 void QBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num)
 589 {
 590         float4 data[BVH_QNODE_SIZE];
 591
 592         for(int i = 0; i < num; i++) {
 593                 float3 bb_min = en[i].node->m_bounds.min;
 594                 float3 bb_max = en[i].node->m_bounds.max;
 595
 596                 data[0][i] = bb_min.x;
 597                 data[1][i] = bb_max.x;
 598                 data[2][i] = bb_min.y;
 599                 data[3][i] = bb_max.y;
 600                 data[4][i] = bb_min.z;
 601                 data[5][i] = bb_max.z;
 602
 603                 data[6][i] = __int_as_float(en[i].encodeIdx());
 604                 data[7][i] = 0.0f;
 605         }
 606
 607         for(int i = num; i < 4; i++) {
 608                 data[0][i] = 0.0f;
 609                 data[1][i] = 0.0f;
 610                 data[2][i] = 0.0f;
 611
 612                 data[3][i] = 0.0f;
 613                 data[4][i] = 0.0f;
 614                 data[5][i] = 0.0f;
 615
 616                 data[6][i] = __int_as_float(0);
 617                 data[7][i] = 0.0f;
 618         }
 619
 620         memcpy(&pack.nodes[e.idx * BVH_QNODE_SIZE], data, sizeof(float4)*BVH_QNODE_SIZE);
 621 }
 622
 623 /* Quad SIMD Nodes */
 624
 625 void QBVH::pack_nodes(const array<int>& prims, const BVHNode *root)
 626 {
 627         size_t node_size = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
 628
 629         /* resize arrays */
 630         pack.nodes.clear();
 631         pack.is_leaf.clear();
 632         pack.is_leaf.resize(node_size);
 633
 634         /* for top level BVH, first merge existing BVH's so we know the offsets */
 635         if(params.top_level)
 636                 pack_instances(node_size*BVH_QNODE_SIZE);
 637         else
 638                 pack.nodes.resize(node_size*BVH_QNODE_SIZE);
 639
 640         int nextNodeIdx = 0;
 641
 642         vector<BVHStackEntry> stack;
 643         stack.push_back(BVHStackEntry(root, nextNodeIdx++));
 644
 645         while(stack.size()) {
 646                 BVHStackEntry e = stack.back();
 647                 stack.pop_back();
 648
 649                 pack.is_leaf[e.idx] = e.node->is_leaf();
 650
 651                 if(e.node->is_leaf()) {
 652                         /* leaf node */
 653                         const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
 654                         pack_leaf(e, leaf);
 655                 }
 656                 else {
 657                         /* inner node */
 658                         const BVHNode *node = e.node;
 659                         const BVHNode *node0 = node->get_child(0);
 660                         const BVHNode *node1 = node->get_child(1);
 661
 662                         /* collect nodes */
 663                         const BVHNode *nodes[4];
 664                         int numnodes = 0;
 665
 666                         if(node0->is_leaf()) {
 667                                 nodes[numnodes++] = node0;
 668                         }
 669                         else {
 670                                 nodes[numnodes++] = node0->get_child(0);
 671                                 nodes[numnodes++] = node0->get_child(1);
 672                         }
 673
 674                         if(node1->is_leaf()) {
 675                                 nodes[numnodes++] = node1;
 676                         }
 677                         else {
 678                                 nodes[numnodes++] = node1->get_child(0);
 679                                 nodes[numnodes++] = node1->get_child(1);
 680                         }
 681
 682                         /* push entries on the stack */
 683                         for(int i = 0; i < numnodes; i++)
 684                                 stack.push_back(BVHStackEntry(nodes[i], nextNodeIdx++));
 685
 686                         /* set node */
 687                         pack_inner(e, &stack[stack.size()-numnodes], numnodes);
 688                 }
 689         }
 690
 691         /* root index to start traversal at, to handle case of single leaf node */
 692         pack.root_index = (pack.is_leaf[0])? -1: 0;
 693 }
 694
 695 void QBVH::refit_nodes()
 696 {
 697         assert(0); /* todo */
 698 }
 699
 700 CCL_NAMESPACE_END
 701