Update bundled version of minilzo
[blender-staging.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 #include "curves.h"
22
23 #include "bvh.h"
24 #include "bvh_build.h"
25 #include "bvh_node.h"
26 #include "bvh_params.h"
27
28 #include "util_cache.h"
29 #include "util_debug.h"
30 #include "util_foreach.h"
31 #include "util_map.h"
32 #include "util_progress.h"
33 #include "util_system.h"
34 #include "util_types.h"
35
36 CCL_NAMESPACE_BEGIN
37
38 /* Pack Utility */
39
40 struct BVHStackEntry
41 {
42         const BVHNode *node;
43         int idx;
44
45         BVHStackEntry(const BVHNode* n = 0, int i = 0)
46         : node(n), idx(i)
47         {
48         }
49
50         int encodeIdx() const
51         {
52                 return (node->is_leaf())? ~idx: idx;
53         }
54 };
55
56 /* BVH */
57
58 BVH::BVH(const BVHParams& params_, const vector<Object*>& objects_)
59 : params(params_), objects(objects_)
60 {
61 }
62
63 BVH *BVH::create(const BVHParams& params, const vector<Object*>& objects)
64 {
65         if(params.use_qbvh)
66                 return new QBVH(params, objects);
67         else
68                 return new RegularBVH(params, objects);
69 }
70
71 /* Cache */
72
73 bool BVH::cache_read(CacheData& key)
74 {
75         key.add(system_cpu_bits());
76         key.add(&params, sizeof(params));
77
78         foreach(Object *ob, objects) {
79                 key.add(ob->mesh->verts);
80                 key.add(ob->mesh->triangles);
81                 key.add(ob->mesh->curve_keys);
82                 key.add(ob->mesh->curves);
83                 key.add(&ob->bounds, sizeof(ob->bounds));
84                 key.add(&ob->visibility, sizeof(ob->visibility));
85                 key.add(&ob->mesh->transform_applied, sizeof(bool));
86         }
87
88         CacheData value;
89
90         if(Cache::global.lookup(key, value)) {
91                 cache_filename = key.get_filename();
92
93                 value.read(pack.root_index);
94                 value.read(pack.SAH);
95
96                 value.read(pack.nodes);
97                 value.read(pack.object_node);
98                 value.read(pack.tri_woop);
99                 value.read(pack.prim_segment);
100                 value.read(pack.prim_visibility);
101                 value.read(pack.prim_index);
102                 value.read(pack.prim_object);
103                 value.read(pack.is_leaf);
104
105                 return true;
106         }
107
108         return false;
109 }
110
111 void BVH::cache_write(CacheData& key)
112 {
113         CacheData value;
114
115         value.add(pack.root_index);
116         value.add(pack.SAH);
117
118         value.add(pack.nodes);
119         value.add(pack.object_node);
120         value.add(pack.tri_woop);
121         value.add(pack.prim_segment);
122         value.add(pack.prim_visibility);
123         value.add(pack.prim_index);
124         value.add(pack.prim_object);
125         value.add(pack.is_leaf);
126
127         Cache::global.insert(key, value);
128
129         cache_filename = key.get_filename();
130 }
131
132 void BVH::clear_cache_except()
133 {
134         set<string> except;
135
136         if(!cache_filename.empty())
137                 except.insert(cache_filename);
138
139         foreach(Object *ob, objects) {
140                 Mesh *mesh = ob->mesh;
141                 BVH *bvh = mesh->bvh;
142
143                 if(bvh && !bvh->cache_filename.empty())
144                         except.insert(bvh->cache_filename);
145         }
146
147         Cache::global.clear_except("bvh", except);
148 }
149
150 /* Building */
151
152 void BVH::build(Progress& progress)
153 {
154         progress.set_substatus("Building BVH");
155
156         /* cache read */
157         CacheData key("bvh");
158
159         if(params.use_cache) {
160                 progress.set_substatus("Looking in BVH cache");
161
162                 if(cache_read(key))
163                         return;
164         }
165
166         /* build nodes */
167         vector<int> prim_segment;
168         vector<int> prim_index;
169         vector<int> prim_object;
170
171         BVHBuild bvh_build(objects, prim_segment, prim_index, prim_object, params, progress);
172         BVHNode *root = bvh_build.run();
173
174         if(progress.get_cancel()) {
175                 if(root) root->deleteSubtree();
176                 return;
177         }
178
179         /* todo: get rid of this copy */
180         pack.prim_segment = prim_segment;
181         pack.prim_index = prim_index;
182         pack.prim_object = prim_object;
183
184         /* compute SAH */
185         if(!params.top_level)
186                 pack.SAH = root->computeSubtreeSAHCost(params);
187
188         if(progress.get_cancel()) {
189                 root->deleteSubtree();
190                 return;
191         }
192
193         /* pack triangles */
194         progress.set_substatus("Packing BVH triangles and strands");
195         pack_primitives();
196
197         if(progress.get_cancel()) {
198                 root->deleteSubtree();
199                 return;
200         }
201
202         /* pack nodes */
203         progress.set_substatus("Packing BVH nodes");
204         array<int> tmp_prim_object = pack.prim_object;
205         pack_nodes(tmp_prim_object, root);
206         
207         /* free build nodes */
208         root->deleteSubtree();
209
210         if(progress.get_cancel()) return;
211
212         /* cache write */
213         if(params.use_cache) {
214                 progress.set_substatus("Writing BVH cache");
215                 cache_write(key);
216
217                 /* clear other bvh files from cache */
218                 if(params.top_level)
219                         clear_cache_except();
220         }
221 }
222
223 /* Refitting */
224
225 void BVH::refit(Progress& progress)
226 {
227         progress.set_substatus("Packing BVH primitives");
228         pack_primitives();
229
230         if(progress.get_cancel()) return;
231
232         progress.set_substatus("Refitting BVH nodes");
233         refit_nodes();
234 }
235
236 /* Triangles */
237
238 void BVH::pack_triangle(int idx, float4 woop[3])
239 {
240         /* create Woop triangle */
241         int tob = pack.prim_object[idx];
242         const Mesh *mesh = objects[tob]->mesh;
243         int tidx = pack.prim_index[idx];
244         const int *vidx = mesh->triangles[tidx].v;
245         const float3* vpos = &mesh->verts[0];
246         float3 v0 = vpos[vidx[0]];
247         float3 v1 = vpos[vidx[1]];
248         float3 v2 = vpos[vidx[2]];
249
250         float3 r0 = v0 - v2;
251         float3 r1 = v1 - v2;
252         float3 r2 = cross(r0, r1);
253
254         if(dot(r0, r0) == 0.0f || dot(r1, r1) == 0.0f || dot(r2, r2) == 0.0f) {
255                 /* degenerate */
256                 woop[0] = make_float4(0.0f, 0.0f, 0.0f, 0.0f);
257                 woop[1] = make_float4(0.0f, 0.0f, 0.0f, 0.0f);
258                 woop[2] = make_float4(0.0f, 0.0f, 0.0f, 0.0f);
259         }
260         else {
261                 Transform t = make_transform(
262                         r0.x, r1.x, r2.x, v2.x,
263                         r0.y, r1.y, r2.y, v2.y,
264                         r0.z, r1.z, r2.z, v2.z,
265                         0.0f, 0.0f, 0.0f, 1.0f);
266
267                 t = transform_inverse(t);
268
269                 woop[0] = make_float4(t.z.x, t.z.y, t.z.z, -t.z.w);
270                 woop[1] = make_float4(t.x.x, t.x.y, t.x.z, t.x.w);
271                 woop[2] = make_float4(t.y.x, t.y.y, t.y.z, t.y.w);
272         }
273 }
274
275 /* Curves*/
276
277 void BVH::pack_curve_segment(int idx, float4 woop[3])
278 {
279         int tob = pack.prim_object[idx];
280         const Mesh *mesh = objects[tob]->mesh;
281         int tidx = pack.prim_index[idx];
282         int segment = pack.prim_segment[idx];
283         int k0 = mesh->curves[tidx].first_key + segment;
284         int k1 = mesh->curves[tidx].first_key + segment + 1;
285         float3 v0 = mesh->curve_keys[k0].co;
286         float3 v1 = mesh->curve_keys[k1].co;
287
288         float3 d0 = v1 - v0;
289         float l =  len(d0);
290         
291         /*Plan
292         *Transform tfm = make_transform(
293         *       location <3>    , l,
294         *       extra curve data <3>    , StrID,
295         *       nextkey, flags/tip?,    0, 0);
296         */
297         Attribute *attr_tangent = mesh->curve_attributes.find(ATTR_STD_CURVE_TANGENT);
298         float3 tg0 = make_float3(1.0f, 0.0f, 0.0f);
299         float3 tg1 = make_float3(1.0f, 0.0f, 0.0f);
300
301         if(attr_tangent) {
302                 const float3 *data_tangent = attr_tangent->data_float3();
303
304                 tg0 = data_tangent[k0];
305                 tg1 = data_tangent[k1];
306         }
307         
308         Transform tfm = make_transform(
309                 tg0.x, tg0.y, tg0.z, l,
310                 tg1.x, tg1.y, tg1.z, 0,
311                 0, 0, 0, 0,
312                 0, 0, 0, 1);
313
314         woop[0] = tfm.x;
315         woop[1] = tfm.y;
316         woop[2] = tfm.z;
317
318 }
319
320 void BVH::pack_primitives()
321 {
322         int nsize = TRI_NODE_SIZE;
323         size_t tidx_size = pack.prim_index.size();
324
325         pack.tri_woop.clear();
326         pack.tri_woop.resize(tidx_size * nsize);
327         pack.prim_visibility.clear();
328         pack.prim_visibility.resize(tidx_size);
329
330         for(unsigned int i = 0; i < tidx_size; i++) {
331                 if(pack.prim_index[i] != -1) {
332                         float4 woop[3];
333
334                         if(pack.prim_segment[i] != ~0)
335                                 pack_curve_segment(i, woop);
336                         else
337                                 pack_triangle(i, woop);
338                         
339                         memcpy(&pack.tri_woop[i * nsize], woop, sizeof(float4)*3);
340
341                         int tob = pack.prim_object[i];
342                         Object *ob = objects[tob];
343                         pack.prim_visibility[i] = ob->visibility;
344                 }
345                 else {
346                         memset(&pack.tri_woop[i * nsize], 0, sizeof(float4)*3);
347                         pack.prim_visibility[i] = 0;
348                 }
349         }
350 }
351
352 /* Pack Instances */
353
354 void BVH::pack_instances(size_t nodes_size)
355 {
356         /* The BVH's for instances are built separately, but for traversal all
357          * BVH's are stored in global arrays. This function merges them into the
358          * top level BVH, adjusting indexes and offsets where appropriate. */
359         bool use_qbvh = params.use_qbvh;
360         size_t nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
361
362         /* adjust primitive index to point to the triangle in the global array, for
363          * meshes with transform applied and already in the top level BVH */
364         for(size_t i = 0; i < pack.prim_index.size(); i++)
365                 if(pack.prim_index[i] != -1) {
366                         if(pack.prim_segment[i] != ~0)
367                                 pack.prim_index[i] += objects[pack.prim_object[i]]->mesh->curve_offset;
368                         else
369                                 pack.prim_index[i] += objects[pack.prim_object[i]]->mesh->tri_offset;
370                 }
371
372         /* track offsets of instanced BVH data in global array */
373         size_t prim_offset = pack.prim_index.size();
374         size_t nodes_offset = nodes_size;
375
376         /* clear array that gives the node indexes for instanced objects */
377         pack.object_node.clear();
378
379         /* reserve */
380         size_t prim_index_size = pack.prim_index.size();
381         size_t tri_woop_size = pack.tri_woop.size();
382
383         size_t pack_prim_index_offset = prim_index_size;
384         size_t pack_tri_woop_offset = tri_woop_size;
385         size_t pack_nodes_offset = nodes_size;
386         size_t object_offset = 0;
387
388         map<Mesh*, int> mesh_map;
389
390         foreach(Object *ob, objects) {
391                 Mesh *mesh = ob->mesh;
392                 BVH *bvh = mesh->bvh;
393
394                 if(!mesh->transform_applied) {
395                         if(mesh_map.find(mesh) == mesh_map.end()) {
396                                 prim_index_size += bvh->pack.prim_index.size();
397                                 tri_woop_size += bvh->pack.tri_woop.size();
398                                 nodes_size += bvh->pack.nodes.size()*nsize;
399
400                                 mesh_map[mesh] = 1;
401                         }
402                 }
403         }
404
405         mesh_map.clear();
406
407         pack.prim_index.resize(prim_index_size);
408         pack.prim_segment.resize(prim_index_size);
409         pack.prim_object.resize(prim_index_size);
410         pack.prim_visibility.resize(prim_index_size);
411         pack.tri_woop.resize(tri_woop_size);
412         pack.nodes.resize(nodes_size);
413         pack.object_node.resize(objects.size());
414
415         int *pack_prim_index = (pack.prim_index.size())? &pack.prim_index[0]: NULL;
416         int *pack_prim_segment = (pack.prim_segment.size())? &pack.prim_segment[0]: NULL;
417         int *pack_prim_object = (pack.prim_object.size())? &pack.prim_object[0]: NULL;
418         uint *pack_prim_visibility = (pack.prim_visibility.size())? &pack.prim_visibility[0]: NULL;
419         float4 *pack_tri_woop = (pack.tri_woop.size())? &pack.tri_woop[0]: NULL;
420         int4 *pack_nodes = (pack.nodes.size())? &pack.nodes[0]: NULL;
421
422         /* merge */
423         foreach(Object *ob, objects) {
424                 Mesh *mesh = ob->mesh;
425
426                 /* if mesh transform is applied, that means it's already in the top
427                  * level BVH, and we don't need to merge it in */
428                 if(mesh->transform_applied) {
429                         pack.object_node[object_offset++] = 0;
430                         continue;
431                 }
432
433                 /* if mesh already added once, don't add it again, but used set
434                  * node offset for this object */
435                 map<Mesh*, int>::iterator it = mesh_map.find(mesh);
436
437                 if(mesh_map.find(mesh) != mesh_map.end()) {
438                         int noffset = it->second;
439                         pack.object_node[object_offset++] = noffset;
440                         continue;
441                 }
442
443                 BVH *bvh = mesh->bvh;
444
445                 int noffset = nodes_offset/nsize;
446                 int mesh_tri_offset = mesh->tri_offset;
447                 int mesh_curve_offset = mesh->curve_offset;
448
449                 /* fill in node indexes for instances */
450                 if((bvh->pack.is_leaf.size() != 0) && bvh->pack.is_leaf[0])
451                         pack.object_node[object_offset++] = -noffset-1;
452                 else
453                         pack.object_node[object_offset++] = noffset;
454
455                 mesh_map[mesh] = pack.object_node[object_offset-1];
456
457                 /* merge primitive and object indexes */
458                 if(bvh->pack.prim_index.size()) {
459                         size_t bvh_prim_index_size = bvh->pack.prim_index.size();
460                         int *bvh_prim_index = &bvh->pack.prim_index[0];
461                         int *bvh_prim_segment = &bvh->pack.prim_segment[0];
462                         uint *bvh_prim_visibility = &bvh->pack.prim_visibility[0];
463
464                         for(size_t i = 0; i < bvh_prim_index_size; i++) {
465                                 if(bvh->pack.prim_segment[i] != ~0)
466                                         pack_prim_index[pack_prim_index_offset] = bvh_prim_index[i] + mesh_curve_offset;
467                                 else
468                                         pack_prim_index[pack_prim_index_offset] = bvh_prim_index[i] + mesh_tri_offset;
469
470                                 pack_prim_segment[pack_prim_index_offset] = bvh_prim_segment[i];
471                                 pack_prim_visibility[pack_prim_index_offset] = bvh_prim_visibility[i];
472                                 pack_prim_object[pack_prim_index_offset] = 0;  // unused for instances
473                                 pack_prim_index_offset++;
474                         }
475                 }
476
477                 /* merge triangle intersection data */
478                 if(bvh->pack.tri_woop.size()) {
479                         memcpy(pack_tri_woop + pack_tri_woop_offset, &bvh->pack.tri_woop[0],
480                                 bvh->pack.tri_woop.size()*sizeof(float4));
481                         pack_tri_woop_offset += bvh->pack.tri_woop.size();
482                 }
483
484                 /* merge nodes */
485                 if(bvh->pack.nodes.size()) {
486                         size_t nsize_bbox = (use_qbvh)? nsize-2: nsize-1;
487                         int4 *bvh_nodes = &bvh->pack.nodes[0];
488                         size_t bvh_nodes_size = bvh->pack.nodes.size(); 
489                         int *bvh_is_leaf = (bvh->pack.is_leaf.size() != 0) ? &bvh->pack.is_leaf[0] : NULL;
490
491                         for(size_t i = 0, j = 0; i < bvh_nodes_size; i+=nsize, j++) {
492                                 memcpy(pack_nodes + pack_nodes_offset, bvh_nodes + i, nsize_bbox*sizeof(int4));
493
494                                 /* modify offsets into arrays */
495                                 int4 data = bvh_nodes[i + nsize_bbox];
496
497                                 if(bvh_is_leaf && bvh_is_leaf[j]) {
498                                         data.x += prim_offset;
499                                         data.y += prim_offset;
500                                 }
501                                 else {
502                                         data.x += (data.x < 0)? -noffset: noffset;
503                                         data.y += (data.y < 0)? -noffset: noffset;
504
505                                         if(use_qbvh) {
506                                                 data.z += (data.z < 0)? -noffset: noffset;
507                                                 data.w += (data.w < 0)? -noffset: noffset;
508                                         }
509                                 }
510
511                                 pack_nodes[pack_nodes_offset + nsize_bbox] = data;
512
513                                 if(use_qbvh)
514                                         pack_nodes[pack_nodes_offset + nsize_bbox+1] = bvh_nodes[i + nsize_bbox+1];
515
516                                 pack_nodes_offset += nsize;
517                         }
518                 }
519
520                 nodes_offset += bvh->pack.nodes.size();
521                 prim_offset += bvh->pack.prim_index.size();
522         }
523 }
524
525 /* Regular BVH */
526
527 RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_)
528 : BVH(params_, objects_)
529 {
530 }
531
532 void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
533 {
534         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1)
535                 /* object */
536                 pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, ~(leaf->m_lo), 0, leaf->m_visibility, leaf->m_visibility);
537         else
538                 /* triangle */
539                 pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, leaf->m_lo, leaf->m_hi, leaf->m_visibility, leaf->m_visibility);
540 }
541
542 void RegularBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry& e0, const BVHStackEntry& e1)
543 {
544         pack_node(e.idx, e0.node->m_bounds, e1.node->m_bounds, e0.encodeIdx(), e1.encodeIdx(), e0.node->m_visibility, e1.node->m_visibility);
545 }
546
547 void RegularBVH::pack_node(int idx, const BoundBox& b0, const BoundBox& b1, int c0, int c1, uint visibility0, uint visibility1)
548 {
549         int4 data[BVH_NODE_SIZE] =
550         {
551                 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)),
552                 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)),
553                 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)),
554                 make_int4(c0, c1, visibility0, visibility1)
555         };
556
557         memcpy(&pack.nodes[idx * BVH_NODE_SIZE], data, sizeof(int4)*BVH_NODE_SIZE);
558 }
559
560 void RegularBVH::pack_nodes(const array<int>& prims, const BVHNode *root)
561 {
562         size_t node_size = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
563
564         /* resize arrays */
565         pack.nodes.clear();
566         pack.is_leaf.clear();
567         pack.is_leaf.resize(node_size);
568
569         /* for top level BVH, first merge existing BVH's so we know the offsets */
570         if(params.top_level)
571                 pack_instances(node_size*BVH_NODE_SIZE);
572         else
573                 pack.nodes.resize(node_size*BVH_NODE_SIZE);
574
575         int nextNodeIdx = 0;
576
577         vector<BVHStackEntry> stack;
578         stack.push_back(BVHStackEntry(root, nextNodeIdx++));
579
580         while(stack.size()) {
581                 BVHStackEntry e = stack.back();
582                 stack.pop_back();
583
584                 pack.is_leaf[e.idx] = e.node->is_leaf();
585
586                 if(e.node->is_leaf()) {
587                         /* leaf node */
588                         const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
589                         pack_leaf(e, leaf);
590                 }
591                 else {
592                         /* innner node */
593                         stack.push_back(BVHStackEntry(e.node->get_child(0), nextNodeIdx++));
594                         stack.push_back(BVHStackEntry(e.node->get_child(1), nextNodeIdx++));
595
596                         pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
597                 }
598         }
599
600         /* root index to start traversal at, to handle case of single leaf node */
601         pack.root_index = (pack.is_leaf[0])? -1: 0;
602 }
603
604 void RegularBVH::refit_nodes()
605 {
606         assert(!params.top_level);
607
608         BoundBox bbox = BoundBox::empty;
609         uint visibility = 0;
610         refit_node(0, (pack.is_leaf[0])? true: false, bbox, visibility);
611 }
612
613 void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
614 {
615         int4 *data = &pack.nodes[idx*4];
616
617         int c0 = data[3].x;
618         int c1 = data[3].y;
619
620         if(leaf) {
621                 /* refit leaf node */
622                 for(int prim = c0; prim < c1; prim++) {
623                         int pidx = pack.prim_index[prim];
624                         int tob = pack.prim_object[prim];
625                         Object *ob = objects[tob];
626
627                         if(pidx == -1) {
628                                 /* object instance */
629                                 bbox.grow(ob->bounds);
630                         }
631                         else {
632                                 /* primitives */
633                                 const Mesh *mesh = ob->mesh;
634
635                                 if(pack.prim_segment[prim] != ~0) {
636                                         /* curves */
637                                         int str_offset = (params.top_level)? mesh->curve_offset: 0;
638                                         int k0 = mesh->curves[pidx - str_offset].first_key + pack.prim_segment[prim]; // XXX!
639                                         int k1 = k0 + 1;
640
641                                         float3 p[4];
642                                         p[0] = mesh->curve_keys[max(k0 - 1,mesh->curves[pidx - str_offset].first_key)].co;
643                                         p[1] = mesh->curve_keys[k0].co;
644                                         p[2] = mesh->curve_keys[k1].co;
645                                         p[3] = mesh->curve_keys[min(k1 + 1,mesh->curves[pidx - str_offset].first_key + mesh->curves[pidx - str_offset].num_keys - 1)].co;
646                                         float3 lower;
647                                         float3 upper;
648                                         curvebounds(&lower.x, &upper.x, p, 0);
649                                         curvebounds(&lower.y, &upper.y, p, 1);
650                                         curvebounds(&lower.z, &upper.z, p, 2);
651                                         float mr = max(mesh->curve_keys[k0].radius,mesh->curve_keys[k1].radius);
652                                         bbox.grow(lower, mr);
653                                         bbox.grow(upper, mr);
654                                 }
655                                 else {
656                                         /* triangles */
657                                         int tri_offset = (params.top_level)? mesh->tri_offset: 0;
658                                         const int *vidx = mesh->triangles[pidx - tri_offset].v;
659                                         const float3 *vpos = &mesh->verts[0];
660
661                                         bbox.grow(vpos[vidx[0]]);
662                                         bbox.grow(vpos[vidx[1]]);
663                                         bbox.grow(vpos[vidx[2]]);
664                                 }
665                         }
666
667                         visibility |= ob->visibility;
668                 }
669
670                 pack_node(idx, bbox, bbox, c0, c1, visibility, visibility);
671         }
672         else {
673                 /* refit inner node, set bbox from children */
674                 BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
675                 uint visibility0 = 0, visibility1 = 0;
676
677                 refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
678                 refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
679
680                 pack_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
681
682                 bbox.grow(bbox0);
683                 bbox.grow(bbox1);
684                 visibility = visibility0|visibility1;
685         }
686 }
687
688 /* QBVH */
689
690 QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_)
691 : BVH(params_, objects_)
692 {
693         params.use_qbvh = true;
694
695         /* todo: use visibility */
696 }
697
698 void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
699 {
700         float4 data[BVH_QNODE_SIZE];
701
702         memset(data, 0, sizeof(data));
703
704         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
705                 /* object */
706                 data[6].x = __int_as_float(~(leaf->m_lo));
707                 data[6].y = __int_as_float(0);
708         }
709         else {
710                 /* triangle */
711                 data[6].x = __int_as_float(leaf->m_lo);
712                 data[6].y = __int_as_float(leaf->m_hi);
713         }
714
715         memcpy(&pack.nodes[e.idx * BVH_QNODE_SIZE], data, sizeof(float4)*BVH_QNODE_SIZE);
716 }
717
718 void QBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num)
719 {
720         float4 data[BVH_QNODE_SIZE];
721
722         for(int i = 0; i < num; i++) {
723                 float3 bb_min = en[i].node->m_bounds.min;
724                 float3 bb_max = en[i].node->m_bounds.max;
725
726                 data[0][i] = bb_min.x;
727                 data[1][i] = bb_max.x;
728                 data[2][i] = bb_min.y;
729                 data[3][i] = bb_max.y;
730                 data[4][i] = bb_min.z;
731                 data[5][i] = bb_max.z;
732
733                 data[6][i] = __int_as_float(en[i].encodeIdx());
734                 data[7][i] = 0.0f;
735         }
736
737         for(int i = num; i < 4; i++) {
738                 data[0][i] = 0.0f;
739                 data[1][i] = 0.0f;
740                 data[2][i] = 0.0f;
741
742                 data[3][i] = 0.0f;
743                 data[4][i] = 0.0f;
744                 data[5][i] = 0.0f;
745
746                 data[6][i] = __int_as_float(0);
747                 data[7][i] = 0.0f;
748         }
749
750         memcpy(&pack.nodes[e.idx * BVH_QNODE_SIZE], data, sizeof(float4)*BVH_QNODE_SIZE);
751 }
752
753 /* Quad SIMD Nodes */
754
755 void QBVH::pack_nodes(const array<int>& prims, const BVHNode *root)
756 {
757         size_t node_size = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
758
759         /* resize arrays */
760         pack.nodes.clear();
761         pack.is_leaf.clear();
762         pack.is_leaf.resize(node_size);
763
764         /* for top level BVH, first merge existing BVH's so we know the offsets */
765         if(params.top_level)
766                 pack_instances(node_size*BVH_QNODE_SIZE);
767         else
768                 pack.nodes.resize(node_size*BVH_QNODE_SIZE);
769
770         int nextNodeIdx = 0;
771
772         vector<BVHStackEntry> stack;
773         stack.push_back(BVHStackEntry(root, nextNodeIdx++));
774
775         while(stack.size()) {
776                 BVHStackEntry e = stack.back();
777                 stack.pop_back();
778
779                 pack.is_leaf[e.idx] = e.node->is_leaf();
780
781                 if(e.node->is_leaf()) {
782                         /* leaf node */
783                         const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
784                         pack_leaf(e, leaf);
785                 }
786                 else {
787                         /* inner node */
788                         const BVHNode *node = e.node;
789                         const BVHNode *node0 = node->get_child(0);
790                         const BVHNode *node1 = node->get_child(1);
791
792                         /* collect nodes */
793                         const BVHNode *nodes[4];
794                         int numnodes = 0;
795
796                         if(node0->is_leaf()) {
797                                 nodes[numnodes++] = node0;
798                         }
799                         else {
800                                 nodes[numnodes++] = node0->get_child(0);
801                                 nodes[numnodes++] = node0->get_child(1);
802                         }
803
804                         if(node1->is_leaf()) {
805                                 nodes[numnodes++] = node1;
806                         }
807                         else {
808                                 nodes[numnodes++] = node1->get_child(0);
809                                 nodes[numnodes++] = node1->get_child(1);
810                         }
811
812                         /* push entries on the stack */
813                         for(int i = 0; i < numnodes; i++)
814                                 stack.push_back(BVHStackEntry(nodes[i], nextNodeIdx++));
815
816                         /* set node */
817                         pack_inner(e, &stack[stack.size()-numnodes], numnodes);
818                 }
819         }
820
821         /* root index to start traversal at, to handle case of single leaf node */
822         pack.root_index = (pack.is_leaf[0])? -1: 0;
823 }
824
825 void QBVH::refit_nodes()
826 {
827         assert(0); /* todo */
828 }
829
830 CCL_NAMESPACE_END
831