Cycles: svn merge -r41225:41232 ^/trunk/blender
[blender.git] / 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.size())? &pack.prim_index[0]: NULL;
318         int *pack_prim_object = (pack.prim_object.size())? &pack.prim_object[0]: NULL;
319         uint *pack_prim_visibility = (pack.prim_visibility.size())? &pack.prim_visibility[0]: NULL;
320         float4 *pack_tri_woop = (pack.tri_woop.size())? &pack.tri_woop[0]: NULL;
321         int4 *pack_nodes = (pack.nodes.size())? &pack.nodes[0]: NULL;
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                 if(bvh->pack.prim_index.size()) {
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                 if(bvh->pack.tri_woop.size()) {
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                 if( bvh->pack.nodes.size()) {
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