Fix T49818: Crash when rendering with motion blur
[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 #include "curves.h"
22
23 #include "bvh.h"
24 #include "bvh_build.h"
25 #include "bvh_node.h"
26 #include "bvh_params.h"
27 #include "bvh_unaligned.h"
28
29 #include "util_debug.h"
30 #include "util_foreach.h"
31 #include "util_logging.h"
32 #include "util_map.h"
33 #include "util_progress.h"
34 #include "util_system.h"
35 #include "util_types.h"
36 #include "util_math.h"
37
38 CCL_NAMESPACE_BEGIN
39
40 /* Pack Utility */
41
42 struct BVHStackEntry
43 {
44         const BVHNode *node;
45         int idx;
46
47         BVHStackEntry(const BVHNode* n = 0, int i = 0)
48         : node(n), idx(i)
49         {
50         }
51
52         int encodeIdx() const
53         {
54                 return (node->is_leaf())? ~idx: idx;
55         }
56 };
57
58 /* BVH */
59
60 BVH::BVH(const BVHParams& params_, const vector<Object*>& objects_)
61 : params(params_), objects(objects_)
62 {
63 }
64
65 BVH *BVH::create(const BVHParams& params, const vector<Object*>& objects)
66 {
67         if(params.use_qbvh)
68                 return new QBVH(params, objects);
69         else
70                 return new RegularBVH(params, objects);
71 }
72
73 /* Building */
74
75 void BVH::build(Progress& progress)
76 {
77         progress.set_substatus("Building BVH");
78
79         /* build nodes */
80         BVHBuild bvh_build(objects,
81                            pack.prim_type,
82                            pack.prim_index,
83                            pack.prim_object,
84                            params,
85                            progress);
86         BVHNode *root = bvh_build.run();
87
88         if(progress.get_cancel()) {
89                 if(root) root->deleteSubtree();
90                 return;
91         }
92
93         /* pack triangles */
94         progress.set_substatus("Packing BVH triangles and strands");
95         pack_primitives();
96
97         if(progress.get_cancel()) {
98                 root->deleteSubtree();
99                 return;
100         }
101
102         /* pack nodes */
103         progress.set_substatus("Packing BVH nodes");
104         pack_nodes(root);
105
106         /* free build nodes */
107         root->deleteSubtree();
108 }
109
110 /* Refitting */
111
112 void BVH::refit(Progress& progress)
113 {
114         progress.set_substatus("Packing BVH primitives");
115         pack_primitives();
116
117         if(progress.get_cancel()) return;
118
119         progress.set_substatus("Refitting BVH nodes");
120         refit_nodes();
121 }
122
123 /* Triangles */
124
125 void BVH::pack_triangle(int idx, float4 tri_verts[3])
126 {
127         int tob = pack.prim_object[idx];
128         assert(tob >= 0 && tob < objects.size());
129         const Mesh *mesh = objects[tob]->mesh;
130
131         int tidx = pack.prim_index[idx];
132         Mesh::Triangle t = mesh->get_triangle(tidx);
133         const float3 *vpos = &mesh->verts[0];
134         float3 v0 = vpos[t.v[0]];
135         float3 v1 = vpos[t.v[1]];
136         float3 v2 = vpos[t.v[2]];
137
138         tri_verts[0] = float3_to_float4(v0);
139         tri_verts[1] = float3_to_float4(v1);
140         tri_verts[2] = float3_to_float4(v2);
141 }
142
143 void BVH::pack_primitives()
144 {
145         const size_t tidx_size = pack.prim_index.size();
146         size_t num_prim_triangles = 0;
147         /* Count number of triangles primitives in BVH. */
148         for(unsigned int i = 0; i < tidx_size; i++) {
149                 if((pack.prim_index[i] != -1)) {
150                         if ((pack.prim_type[i] & PRIMITIVE_ALL_TRIANGLE) != 0) {
151                                 ++num_prim_triangles;
152                         }
153                 }
154         }
155         /* Reserve size for arrays. */
156         pack.prim_tri_index.clear();
157         pack.prim_tri_index.resize(tidx_size);
158         pack.prim_tri_verts.clear();
159         pack.prim_tri_verts.resize(num_prim_triangles * 3);
160         pack.prim_visibility.clear();
161         pack.prim_visibility.resize(tidx_size);
162         /* Fill in all the arrays. */
163         size_t prim_triangle_index = 0;
164         for(unsigned int i = 0; i < tidx_size; i++) {
165                 if(pack.prim_index[i] != -1) {
166                         int tob = pack.prim_object[i];
167                         Object *ob = objects[tob];
168
169                         if((pack.prim_type[i] & PRIMITIVE_ALL_TRIANGLE) != 0) {
170                                 pack_triangle(i, (float4*)&pack.prim_tri_verts[3 * prim_triangle_index]);
171                                 pack.prim_tri_index[i] = 3 * prim_triangle_index;
172                                 ++prim_triangle_index;
173                         }
174                         else {
175                                 pack.prim_tri_index[i] = -1;
176                         }
177
178                         pack.prim_visibility[i] = ob->visibility;
179
180                         if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE)
181                                 pack.prim_visibility[i] |= PATH_RAY_CURVE;
182                 }
183                 else {
184                         pack.prim_tri_index[i] = -1;
185                         pack.prim_visibility[i] = 0;
186                 }
187         }
188 }
189
190 /* Pack Instances */
191
192 void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
193 {
194         /* The BVH's for instances are built separately, but for traversal all
195          * BVH's are stored in global arrays. This function merges them into the
196          * top level BVH, adjusting indexes and offsets where appropriate.
197          */
198         const bool use_qbvh = params.use_qbvh;
199
200         /* Adjust primitive index to point to the triangle in the global array, for
201          * meshes with transform applied and already in the top level BVH.
202          */
203         for(size_t i = 0; i < pack.prim_index.size(); i++)
204                 if(pack.prim_index[i] != -1) {
205                         if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE)
206                                 pack.prim_index[i] += objects[pack.prim_object[i]]->mesh->curve_offset;
207                         else
208                                 pack.prim_index[i] += objects[pack.prim_object[i]]->mesh->tri_offset;
209                 }
210
211         /* track offsets of instanced BVH data in global array */
212         size_t prim_offset = pack.prim_index.size();
213         size_t nodes_offset = nodes_size;
214         size_t nodes_leaf_offset = leaf_nodes_size;
215
216         /* clear array that gives the node indexes for instanced objects */
217         pack.object_node.clear();
218
219         /* reserve */
220         size_t prim_index_size = pack.prim_index.size();
221         size_t prim_tri_verts_size = pack.prim_tri_verts.size();
222
223         size_t pack_prim_index_offset = prim_index_size;
224         size_t pack_prim_tri_verts_offset = prim_tri_verts_size;
225         size_t pack_nodes_offset = nodes_size;
226         size_t pack_leaf_nodes_offset = leaf_nodes_size;
227         size_t object_offset = 0;
228
229         map<Mesh*, int> mesh_map;
230
231         foreach(Object *ob, objects) {
232                 Mesh *mesh = ob->mesh;
233                 BVH *bvh = mesh->bvh;
234
235                 if(mesh->need_build_bvh()) {
236                         if(mesh_map.find(mesh) == mesh_map.end()) {
237                                 prim_index_size += bvh->pack.prim_index.size();
238                                 prim_tri_verts_size += bvh->pack.prim_tri_verts.size();
239                                 nodes_size += bvh->pack.nodes.size();
240                                 leaf_nodes_size += bvh->pack.leaf_nodes.size();
241
242                                 mesh_map[mesh] = 1;
243                         }
244                 }
245         }
246
247         mesh_map.clear();
248
249         pack.prim_index.resize(prim_index_size);
250         pack.prim_type.resize(prim_index_size);
251         pack.prim_object.resize(prim_index_size);
252         pack.prim_visibility.resize(prim_index_size);
253         pack.prim_tri_verts.resize(prim_tri_verts_size);
254         pack.prim_tri_index.resize(prim_index_size);
255         pack.nodes.resize(nodes_size);
256         pack.leaf_nodes.resize(leaf_nodes_size);
257         pack.object_node.resize(objects.size());
258
259         int *pack_prim_index = (pack.prim_index.size())? &pack.prim_index[0]: NULL;
260         int *pack_prim_type = (pack.prim_type.size())? &pack.prim_type[0]: NULL;
261         int *pack_prim_object = (pack.prim_object.size())? &pack.prim_object[0]: NULL;
262         uint *pack_prim_visibility = (pack.prim_visibility.size())? &pack.prim_visibility[0]: NULL;
263         float4 *pack_prim_tri_verts = (pack.prim_tri_verts.size())? &pack.prim_tri_verts[0]: NULL;
264         uint *pack_prim_tri_index = (pack.prim_tri_index.size())? &pack.prim_tri_index[0]: NULL;
265         int4 *pack_nodes = (pack.nodes.size())? &pack.nodes[0]: NULL;
266         int4 *pack_leaf_nodes = (pack.leaf_nodes.size())? &pack.leaf_nodes[0]: NULL;
267
268         /* merge */
269         foreach(Object *ob, objects) {
270                 Mesh *mesh = ob->mesh;
271
272                 /* We assume that if mesh doesn't need own BVH it was already included
273                  * into a top-level BVH and no packing here is needed.
274                  */
275                 if(!mesh->need_build_bvh()) {
276                         pack.object_node[object_offset++] = 0;
277                         continue;
278                 }
279
280                 /* if mesh already added once, don't add it again, but used set
281                  * node offset for this object */
282                 map<Mesh*, int>::iterator it = mesh_map.find(mesh);
283
284                 if(mesh_map.find(mesh) != mesh_map.end()) {
285                         int noffset = it->second;
286                         pack.object_node[object_offset++] = noffset;
287                         continue;
288                 }
289
290                 BVH *bvh = mesh->bvh;
291
292                 int noffset = nodes_offset;
293                 int noffset_leaf = nodes_leaf_offset;
294                 int mesh_tri_offset = mesh->tri_offset;
295                 int mesh_curve_offset = mesh->curve_offset;
296
297                 /* fill in node indexes for instances */
298                 if(bvh->pack.root_index == -1)
299                         pack.object_node[object_offset++] = -noffset_leaf-1;
300                 else
301                         pack.object_node[object_offset++] = noffset;
302
303                 mesh_map[mesh] = pack.object_node[object_offset-1];
304
305                 /* merge primitive, object and triangle indexes */
306                 if(bvh->pack.prim_index.size()) {
307                         size_t bvh_prim_index_size = bvh->pack.prim_index.size();
308                         int *bvh_prim_index = &bvh->pack.prim_index[0];
309                         int *bvh_prim_type = &bvh->pack.prim_type[0];
310                         uint *bvh_prim_visibility = &bvh->pack.prim_visibility[0];
311                         uint *bvh_prim_tri_index = &bvh->pack.prim_tri_index[0];
312
313                         for(size_t i = 0; i < bvh_prim_index_size; i++) {
314                                 if(bvh->pack.prim_type[i] & PRIMITIVE_ALL_CURVE) {
315                                         pack_prim_index[pack_prim_index_offset] = bvh_prim_index[i] + mesh_curve_offset;
316                                         pack_prim_tri_index[pack_prim_index_offset] = -1;
317                                 }
318                                 else {
319                                         pack_prim_index[pack_prim_index_offset] = bvh_prim_index[i] + mesh_tri_offset;
320                                         pack_prim_tri_index[pack_prim_index_offset] =
321                                                 bvh_prim_tri_index[i] + pack_prim_tri_verts_offset;
322                                 }
323
324                                 pack_prim_type[pack_prim_index_offset] = bvh_prim_type[i];
325                                 pack_prim_visibility[pack_prim_index_offset] = bvh_prim_visibility[i];
326                                 pack_prim_object[pack_prim_index_offset] = 0;  // unused for instances
327                                 pack_prim_index_offset++;
328                         }
329                 }
330
331                 /* Merge triangle vertices data. */
332                 if(bvh->pack.prim_tri_verts.size()) {
333                         const size_t prim_tri_size = bvh->pack.prim_tri_verts.size();
334                         memcpy(pack_prim_tri_verts + pack_prim_tri_verts_offset,
335                                &bvh->pack.prim_tri_verts[0],
336                                prim_tri_size*sizeof(float4));
337                         pack_prim_tri_verts_offset += prim_tri_size;
338                 }
339
340                 /* merge nodes */
341                 if(bvh->pack.leaf_nodes.size()) {
342                         int4 *leaf_nodes_offset = &bvh->pack.leaf_nodes[0];
343                         size_t leaf_nodes_offset_size = bvh->pack.leaf_nodes.size();
344                         for(size_t i = 0, j = 0;
345                             i < leaf_nodes_offset_size;
346                             i += BVH_NODE_LEAF_SIZE, j++)
347                         {
348                                 int4 data = leaf_nodes_offset[i];
349                                 data.x += prim_offset;
350                                 data.y += prim_offset;
351                                 pack_leaf_nodes[pack_leaf_nodes_offset] = data;
352                                 for(int j = 1; j < BVH_NODE_LEAF_SIZE; ++j) {
353                                         pack_leaf_nodes[pack_leaf_nodes_offset + j] = leaf_nodes_offset[i + j];
354                                 }
355                                 pack_leaf_nodes_offset += BVH_NODE_LEAF_SIZE;
356                         }
357                 }
358
359                 if(bvh->pack.nodes.size()) {
360                         int4 *bvh_nodes = &bvh->pack.nodes[0];
361                         size_t bvh_nodes_size = bvh->pack.nodes.size();
362
363                         for(size_t i = 0, j = 0; i < bvh_nodes_size; j++) {
364                                 size_t nsize, nsize_bbox;
365                                 if(bvh_nodes[i].x & PATH_RAY_NODE_UNALIGNED) {
366                                         nsize = use_qbvh
367                                                     ? BVH_UNALIGNED_QNODE_SIZE
368                                                     : BVH_UNALIGNED_NODE_SIZE;
369                                         nsize_bbox = (use_qbvh)? 13: 0;
370                                 }
371                                 else {
372                                         nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
373                                         nsize_bbox = (use_qbvh)? 7: 0;
374                                 }
375
376                                 memcpy(pack_nodes + pack_nodes_offset,
377                                        bvh_nodes + i,
378                                        nsize_bbox*sizeof(int4));
379
380                                 /* Modify offsets into arrays */
381                                 int4 data = bvh_nodes[i + nsize_bbox];
382
383                                 data.z += (data.z < 0)? -noffset_leaf: noffset;
384                                 data.w += (data.w < 0)? -noffset_leaf: noffset;
385
386                                 if(use_qbvh) {
387                                         data.x += (data.x < 0)? -noffset_leaf: noffset;
388                                         data.y += (data.y < 0)? -noffset_leaf: noffset;
389                                 }
390
391                                 pack_nodes[pack_nodes_offset + nsize_bbox] = data;
392
393                                 /* Usually this copies nothing, but we better
394                                  * be prepared for possible node size extension.
395                                  */
396                                 memcpy(&pack_nodes[pack_nodes_offset + nsize_bbox+1],
397                                        &bvh_nodes[i + nsize_bbox+1],
398                                        sizeof(int4) * (nsize - (nsize_bbox+1)));
399
400                                 pack_nodes_offset += nsize;
401                                 i += nsize;
402                         }
403                 }
404
405                 nodes_offset += bvh->pack.nodes.size();
406                 nodes_leaf_offset += bvh->pack.leaf_nodes.size();
407                 prim_offset += bvh->pack.prim_index.size();
408         }
409 }
410
411 /* Regular BVH */
412
413 static bool node_bvh_is_unaligned(const BVHNode *node)
414 {
415         const BVHNode *node0 = node->get_child(0),
416                       *node1 = node->get_child(1);
417         return node0->is_unaligned() || node1->is_unaligned();
418 }
419
420 RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_)
421 : BVH(params_, objects_)
422 {
423 }
424
425 void RegularBVH::pack_leaf(const BVHStackEntry& e,
426                            const LeafNode *leaf)
427 {
428         assert(e.idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size());
429         float4 data[BVH_NODE_LEAF_SIZE];
430         memset(data, 0, sizeof(data));
431         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
432                 /* object */
433                 data[0].x = __int_as_float(~(leaf->m_lo));
434                 data[0].y = __int_as_float(0);
435         }
436         else {
437                 /* triangle */
438                 data[0].x = __int_as_float(leaf->m_lo);
439                 data[0].y = __int_as_float(leaf->m_hi);
440         }
441         data[0].z = __uint_as_float(leaf->m_visibility);
442         if(leaf->num_triangles() != 0) {
443                 data[0].w = __uint_as_float(pack.prim_type[leaf->m_lo]);
444         }
445
446         memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
447 }
448
449 void RegularBVH::pack_inner(const BVHStackEntry& e,
450                             const BVHStackEntry& e0,
451                             const BVHStackEntry& e1)
452 {
453         if (e0.node->is_unaligned() || e1.node->is_unaligned()) {
454                 pack_unaligned_inner(e, e0, e1);
455         } else {
456                 pack_aligned_inner(e, e0, e1);
457         }
458 }
459
460 void RegularBVH::pack_aligned_inner(const BVHStackEntry& e,
461                                     const BVHStackEntry& e0,
462                                     const BVHStackEntry& e1)
463 {
464         pack_aligned_node(e.idx,
465                           e0.node->m_bounds, e1.node->m_bounds,
466                           e0.encodeIdx(), e1.encodeIdx(),
467                           e0.node->m_visibility, e1.node->m_visibility);
468 }
469
470 void RegularBVH::pack_aligned_node(int idx,
471                                    const BoundBox& b0,
472                                    const BoundBox& b1,
473                                    int c0, int c1,
474                                    uint visibility0, uint visibility1)
475 {
476         assert(idx + BVH_NODE_SIZE <= pack.nodes.size());
477         assert(c0 < 0 || c0 < pack.nodes.size());
478         assert(c1 < 0 || c1 < pack.nodes.size());
479
480         int4 data[BVH_NODE_SIZE] = {
481                 make_int4(visibility0 & ~PATH_RAY_NODE_UNALIGNED,
482                           visibility1 & ~PATH_RAY_NODE_UNALIGNED,
483                           c0, c1),
484                 make_int4(__float_as_int(b0.min.x),
485                           __float_as_int(b1.min.x),
486                           __float_as_int(b0.max.x),
487                           __float_as_int(b1.max.x)),
488                 make_int4(__float_as_int(b0.min.y),
489                           __float_as_int(b1.min.y),
490                           __float_as_int(b0.max.y),
491                           __float_as_int(b1.max.y)),
492                 make_int4(__float_as_int(b0.min.z),
493                           __float_as_int(b1.min.z),
494                           __float_as_int(b0.max.z),
495                           __float_as_int(b1.max.z)),
496         };
497
498         memcpy(&pack.nodes[idx], data, sizeof(int4)*BVH_NODE_SIZE);
499 }
500
501 void RegularBVH::pack_unaligned_inner(const BVHStackEntry& e,
502                                       const BVHStackEntry& e0,
503                                       const BVHStackEntry& e1)
504 {
505         pack_unaligned_node(e.idx,
506                             e0.node->get_aligned_space(),
507                             e1.node->get_aligned_space(),
508                             e0.node->m_bounds,
509                             e1.node->m_bounds,
510                             e0.encodeIdx(), e1.encodeIdx(),
511                             e0.node->m_visibility, e1.node->m_visibility);
512 }
513
514 void RegularBVH::pack_unaligned_node(int idx,
515                                      const Transform& aligned_space0,
516                                      const Transform& aligned_space1,
517                                      const BoundBox& bounds0,
518                                      const BoundBox& bounds1,
519                                      int c0, int c1,
520                                      uint visibility0, uint visibility1)
521 {
522         assert(idx + BVH_UNALIGNED_NODE_SIZE <= pack.nodes.size());
523         assert(c0 < 0 || c0 < pack.nodes.size());
524         assert(c1 < 0 || c1 < pack.nodes.size());
525
526         float4 data[BVH_UNALIGNED_NODE_SIZE];
527         Transform space0 = BVHUnaligned::compute_node_transform(bounds0,
528                                                                 aligned_space0);
529         Transform space1 = BVHUnaligned::compute_node_transform(bounds1,
530                                                                 aligned_space1);
531         data[0] = make_float4(__int_as_float(visibility0 | PATH_RAY_NODE_UNALIGNED),
532                               __int_as_float(visibility1 | PATH_RAY_NODE_UNALIGNED),
533                               __int_as_float(c0),
534                               __int_as_float(c1));
535
536         data[1] = space0.x;
537         data[2] = space0.y;
538         data[3] = space0.z;
539         data[4] = space1.x;
540         data[5] = space1.y;
541         data[6] = space1.z;
542
543         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_NODE_SIZE);
544 }
545
546 void RegularBVH::pack_nodes(const BVHNode *root)
547 {
548         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
549         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
550         assert(num_leaf_nodes <= num_nodes);
551         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
552         size_t node_size;
553         if(params.use_unaligned_nodes) {
554                 const size_t num_unaligned_nodes =
555                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
556                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_NODE_SIZE) +
557                             (num_inner_nodes - num_unaligned_nodes) * BVH_NODE_SIZE;
558         }
559         else {
560                 node_size = num_inner_nodes * BVH_NODE_SIZE;
561         }
562         /* Resize arrays */
563         pack.nodes.clear();
564         pack.leaf_nodes.clear();
565         /* For top level BVH, first merge existing BVH's so we know the offsets. */
566         if(params.top_level) {
567                 pack_instances(node_size, num_leaf_nodes*BVH_NODE_LEAF_SIZE);
568         }
569         else {
570                 pack.nodes.resize(node_size);
571                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_NODE_LEAF_SIZE);
572         }
573
574         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
575
576         vector<BVHStackEntry> stack;
577         stack.reserve(BVHParams::MAX_DEPTH*2);
578         if(root->is_leaf()) {
579                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
580         }
581         else {
582                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
583                 nextNodeIdx += node_bvh_is_unaligned(root)
584                                        ? BVH_UNALIGNED_NODE_SIZE
585                                        : BVH_NODE_SIZE;
586         }
587
588         while(stack.size()) {
589                 BVHStackEntry e = stack.back();
590                 stack.pop_back();
591
592                 if(e.node->is_leaf()) {
593                         /* leaf node */
594                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
595                         pack_leaf(e, leaf);
596                 }
597                 else {
598                         /* innner node */
599                         int idx[2];
600                         for (int i = 0; i < 2; ++i) {
601                                 if (e.node->get_child(i)->is_leaf()) {
602                                         idx[i] = nextLeafNodeIdx++;
603                                 }
604                                 else {
605                                         idx[i] = nextNodeIdx;
606                                         nextNodeIdx += node_bvh_is_unaligned(e.node->get_child(i))
607                                                                ? BVH_UNALIGNED_NODE_SIZE
608                                                                : BVH_NODE_SIZE;
609                                 }
610                         }
611
612                         stack.push_back(BVHStackEntry(e.node->get_child(0), idx[0]));
613                         stack.push_back(BVHStackEntry(e.node->get_child(1), idx[1]));
614
615                         pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
616                 }
617         }
618         assert(node_size == nextNodeIdx);
619         /* root index to start traversal at, to handle case of single leaf node */
620         pack.root_index = (root->is_leaf())? -1: 0;
621 }
622
623 void RegularBVH::refit_nodes()
624 {
625         assert(!params.top_level);
626
627         BoundBox bbox = BoundBox::empty;
628         uint visibility = 0;
629         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
630 }
631
632 void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
633 {
634         if(leaf) {
635                 assert(idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size());
636                 const int4 *data = &pack.leaf_nodes[idx];
637                 const int c0 = data[0].x;
638                 const int c1 = data[0].y;
639                 /* refit leaf node */
640                 for(int prim = c0; prim < c1; prim++) {
641                         int pidx = pack.prim_index[prim];
642                         int tob = pack.prim_object[prim];
643                         Object *ob = objects[tob];
644
645                         if(pidx == -1) {
646                                 /* object instance */
647                                 bbox.grow(ob->bounds);
648                         }
649                         else {
650                                 /* primitives */
651                                 const Mesh *mesh = ob->mesh;
652
653                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
654                                         /* curves */
655                                         int str_offset = (params.top_level)? mesh->curve_offset: 0;
656                                         Mesh::Curve curve = mesh->get_curve(pidx - str_offset);
657                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
658
659                                         curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox);
660
661                                         visibility |= PATH_RAY_CURVE;
662
663                                         /* motion curves */
664                                         if(mesh->use_motion_blur) {
665                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
666
667                                                 if(attr) {
668                                                         size_t mesh_size = mesh->curve_keys.size();
669                                                         size_t steps = mesh->motion_steps - 1;
670                                                         float3 *key_steps = attr->data_float3();
671
672                                                         for(size_t i = 0; i < steps; i++)
673                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox);
674                                                 }
675                                         }
676                                 }
677                                 else {
678                                         /* triangles */
679                                         int tri_offset = (params.top_level)? mesh->tri_offset: 0;
680                                         Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset);
681                                         const float3 *vpos = &mesh->verts[0];
682
683                                         triangle.bounds_grow(vpos, bbox);
684
685                                         /* motion triangles */
686                                         if(mesh->use_motion_blur) {
687                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
688
689                                                 if(attr) {
690                                                         size_t mesh_size = mesh->verts.size();
691                                                         size_t steps = mesh->motion_steps - 1;
692                                                         float3 *vert_steps = attr->data_float3();
693
694                                                         for(size_t i = 0; i < steps; i++)
695                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
696                                                 }
697                                         }
698                                 }
699                         }
700
701                         visibility |= ob->visibility;
702                 }
703
704                 /* TODO(sergey): De-duplicate with pack_leaf(). */
705                 float4 leaf_data[BVH_NODE_LEAF_SIZE];
706                 leaf_data[0].x = __int_as_float(c0);
707                 leaf_data[0].y = __int_as_float(c1);
708                 leaf_data[0].z = __uint_as_float(visibility);
709                 leaf_data[0].w = __uint_as_float(data[0].w);
710                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
711         }
712         else {
713                 assert(idx + BVH_NODE_SIZE <= pack.nodes.size());
714
715                 const int4 *data = &pack.nodes[idx];
716                 const bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0;
717                 const int c0 = data[0].z;
718                 const int c1 = data[0].w;
719                 /* refit inner node, set bbox from children */
720                 BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
721                 uint visibility0 = 0, visibility1 = 0;
722
723                 refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
724                 refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
725
726                 if(is_unaligned) {
727                         Transform aligned_space = transform_identity();
728                         pack_unaligned_node(idx,
729                                             aligned_space, aligned_space,
730                                             bbox0, bbox1,
731                                             c0, c1,
732                                             visibility0,
733                                             visibility1);
734                 }
735                 else {
736                         pack_aligned_node(idx,
737                                           bbox0, bbox1,
738                                           c0, c1,
739                                           visibility0,
740                                           visibility1);
741                 }
742
743                 bbox.grow(bbox0);
744                 bbox.grow(bbox1);
745                 visibility = visibility0|visibility1;
746         }
747 }
748
749 /* QBVH */
750
751 /* Can we avoid this somehow or make more generic?
752  *
753  * Perhaps we can merge nodes in actual tree and make our
754  * life easier all over the place.
755  */
756 static bool node_qbvh_is_unaligned(const BVHNode *node)
757 {
758         const BVHNode *node0 = node->get_child(0),
759                       *node1 = node->get_child(1);
760         bool has_unaligned = false;
761         if(node0->is_leaf()) {
762                 has_unaligned |= node0->is_unaligned();
763         }
764         else {
765                 has_unaligned |= node0->get_child(0)->is_unaligned();
766                 has_unaligned |= node0->get_child(1)->is_unaligned();
767         }
768         if(node1->is_leaf()) {
769                 has_unaligned |= node1->is_unaligned();
770         }
771         else {
772                 has_unaligned |= node1->get_child(0)->is_unaligned();
773                 has_unaligned |= node1->get_child(1)->is_unaligned();
774         }
775         return has_unaligned;
776 }
777
778 QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_)
779 : BVH(params_, objects_)
780 {
781         params.use_qbvh = true;
782 }
783
784 void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
785 {
786         float4 data[BVH_QNODE_LEAF_SIZE];
787         memset(data, 0, sizeof(data));
788         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
789                 /* object */
790                 data[0].x = __int_as_float(~(leaf->m_lo));
791                 data[0].y = __int_as_float(0);
792         }
793         else {
794                 /* triangle */
795                 data[0].x = __int_as_float(leaf->m_lo);
796                 data[0].y = __int_as_float(leaf->m_hi);
797         }
798         data[0].z = __uint_as_float(leaf->m_visibility);
799         if(leaf->num_triangles() != 0) {
800                 data[0].w = __uint_as_float(pack.prim_type[leaf->m_lo]);
801         }
802
803         memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
804 }
805
806 void QBVH::pack_inner(const BVHStackEntry& e,
807                       const BVHStackEntry *en,
808                       int num)
809 {
810         bool has_unaligned = false;
811         /* Check whether we have to create unaligned node or all nodes are aligned
812          * and we can cut some corner here.
813          */
814         if(params.use_unaligned_nodes) {
815                 for(int i = 0; i < num; i++) {
816                         if(en[i].node->is_unaligned()) {
817                                 has_unaligned = true;
818                                 break;
819                         }
820                 }
821         }
822         if(has_unaligned) {
823                 /* There's no unaligned children, pack into AABB node. */
824                 pack_unaligned_inner(e, en, num);
825         }
826         else {
827                 /* Create unaligned node with orientation transform for each of the
828                  * children.
829                  */
830                 pack_aligned_inner(e, en, num);
831         }
832 }
833
834 void QBVH::pack_aligned_inner(const BVHStackEntry& e,
835                               const BVHStackEntry *en,
836                               int num)
837 {
838         BoundBox bounds[4];
839         int child[4];
840         for(int i = 0; i < num; ++i) {
841                 bounds[i] = en[i].node->m_bounds;
842                 child[i] = en[i].encodeIdx();
843         }
844         pack_aligned_node(e.idx,
845                           bounds,
846                           child,
847                           e.node->m_visibility,
848                           num);
849 }
850
851 void QBVH::pack_aligned_node(int idx,
852                              const BoundBox *bounds,
853                              const int *child,
854                              const uint visibility,
855                              const int num)
856 {
857         float4 data[BVH_QNODE_SIZE];
858         memset(data, 0, sizeof(data));
859
860         data[0].x = __uint_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED);
861         for(int i = 0; i < num; i++) {
862                 float3 bb_min = bounds[i].min;
863                 float3 bb_max = bounds[i].max;
864
865                 data[1][i] = bb_min.x;
866                 data[2][i] = bb_max.x;
867                 data[3][i] = bb_min.y;
868                 data[4][i] = bb_max.y;
869                 data[5][i] = bb_min.z;
870                 data[6][i] = bb_max.z;
871
872                 data[7][i] = __int_as_float(child[i]);
873         }
874
875         for(int i = num; i < 4; i++) {
876                 /* We store BB which would never be recorded as intersection
877                  * so kernel might safely assume there are always 4 child nodes.
878                  */
879                 data[1][i] = FLT_MAX;
880                 data[2][i] = -FLT_MAX;
881
882                 data[3][i] = FLT_MAX;
883                 data[4][i] = -FLT_MAX;
884
885                 data[5][i] = FLT_MAX;
886                 data[6][i] = -FLT_MAX;
887
888                 data[7][i] = __int_as_float(0);
889         }
890
891         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_QNODE_SIZE);
892 }
893
894 void QBVH::pack_unaligned_inner(const BVHStackEntry& e,
895                                 const BVHStackEntry *en,
896                                 int num)
897 {
898         Transform aligned_space[4];
899         BoundBox bounds[4];
900         int child[4];
901         for(int i = 0; i < num; ++i) {
902                 aligned_space[i] = en[i].node->get_aligned_space();
903                 bounds[i] = en[i].node->m_bounds;
904                 child[i] = en[i].encodeIdx();
905         }
906         pack_unaligned_node(e.idx,
907                             aligned_space,
908                             bounds,
909                             child,
910                             e.node->m_visibility,
911                             num);
912 }
913
914 void QBVH::pack_unaligned_node(int idx,
915                                const Transform *aligned_space,
916                                const BoundBox *bounds,
917                                const int *child,
918                                const uint visibility,
919                                const int num)
920 {
921         float4 data[BVH_UNALIGNED_QNODE_SIZE];
922         memset(data, 0, sizeof(data));
923
924         data[0].x = __uint_as_float(visibility | PATH_RAY_NODE_UNALIGNED);
925
926         for(int i = 0; i < num; i++) {
927                 Transform space = BVHUnaligned::compute_node_transform(
928                         bounds[i],
929                         aligned_space[i]);
930
931                 data[1][i] = space.x.x;
932                 data[2][i] = space.x.y;
933                 data[3][i] = space.x.z;
934
935                 data[4][i] = space.y.x;
936                 data[5][i] = space.y.y;
937                 data[6][i] = space.y.z;
938
939                 data[7][i] = space.z.x;
940                 data[8][i] = space.z.y;
941                 data[9][i] = space.z.z;
942
943                 data[10][i] = space.x.w;
944                 data[11][i] = space.y.w;
945                 data[12][i] = space.z.w;
946
947                 data[13][i] = __int_as_float(child[i]);
948         }
949
950         for(int i = num; i < 4; i++) {
951                 /* We store BB which would never be recorded as intersection
952                  * so kernel might safely assume there are always 4 child nodes.
953                  */
954
955                 data[1][i] = 1.0f;
956                 data[2][i] = 0.0f;
957                 data[3][i] = 0.0f;
958
959                 data[4][i] = 0.0f;
960                 data[5][i] = 0.0f;
961                 data[6][i] = 0.0f;
962
963                 data[7][i] = 0.0f;
964                 data[8][i] = 0.0f;
965                 data[9][i] = 0.0f;
966
967                 data[10][i] = -FLT_MAX;
968                 data[11][i] = -FLT_MAX;
969                 data[12][i] = -FLT_MAX;
970
971                 data[13][i] = __int_as_float(0);
972         }
973
974         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE);
975 }
976
977 /* Quad SIMD Nodes */
978
979 void QBVH::pack_nodes(const BVHNode *root)
980 {
981         /* Calculate size of the arrays required. */
982         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
983         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
984         assert(num_leaf_nodes <= num_nodes);
985         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
986         size_t node_size;
987         if(params.use_unaligned_nodes) {
988                 const size_t num_unaligned_nodes =
989                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_QNODE_COUNT);
990                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_QNODE_SIZE) +
991                             (num_inner_nodes - num_unaligned_nodes) * BVH_QNODE_SIZE;
992         }
993         else {
994                 node_size = num_inner_nodes * BVH_QNODE_SIZE;
995         }
996         /* Resize arrays. */
997         pack.nodes.clear();
998         pack.leaf_nodes.clear();
999         /* For top level BVH, first merge existing BVH's so we know the offsets. */
1000         if(params.top_level) {
1001                 pack_instances(node_size, num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
1002         }
1003         else {
1004                 pack.nodes.resize(node_size);
1005                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
1006         }
1007
1008         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
1009
1010         vector<BVHStackEntry> stack;
1011         stack.reserve(BVHParams::MAX_DEPTH*2);
1012         if(root->is_leaf()) {
1013                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
1014         }
1015         else {
1016                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
1017                 nextNodeIdx += node_qbvh_is_unaligned(root)
1018                                        ? BVH_UNALIGNED_QNODE_SIZE
1019                                        : BVH_QNODE_SIZE;
1020         }
1021
1022         while(stack.size()) {
1023                 BVHStackEntry e = stack.back();
1024                 stack.pop_back();
1025
1026                 if(e.node->is_leaf()) {
1027                         /* leaf node */
1028                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
1029                         pack_leaf(e, leaf);
1030                 }
1031                 else {
1032                         /* Inner node. */
1033                         const BVHNode *node = e.node;
1034                         const BVHNode *node0 = node->get_child(0);
1035                         const BVHNode *node1 = node->get_child(1);
1036                         /* Collect nodes. */
1037                         const BVHNode *nodes[4];
1038                         int numnodes = 0;
1039                         if(node0->is_leaf()) {
1040                                 nodes[numnodes++] = node0;
1041                         }
1042                         else {
1043                                 nodes[numnodes++] = node0->get_child(0);
1044                                 nodes[numnodes++] = node0->get_child(1);
1045                         }
1046                         if(node1->is_leaf()) {
1047                                 nodes[numnodes++] = node1;
1048                         }
1049                         else {
1050                                 nodes[numnodes++] = node1->get_child(0);
1051                                 nodes[numnodes++] = node1->get_child(1);
1052                         }
1053                         /* Push entries on the stack. */
1054                         for(int i = 0; i < numnodes; ++i) {
1055                                 int idx;
1056                                 if(nodes[i]->is_leaf()) {
1057                                         idx = nextLeafNodeIdx++;
1058                                 }
1059                                 else {
1060                                         idx = nextNodeIdx;
1061                                         nextNodeIdx += node_qbvh_is_unaligned(nodes[i])
1062                                                                ? BVH_UNALIGNED_QNODE_SIZE
1063                                                                : BVH_QNODE_SIZE;
1064                                 }
1065                                 stack.push_back(BVHStackEntry(nodes[i], idx));
1066                         }
1067                         /* Set node. */
1068                         pack_inner(e, &stack[stack.size()-numnodes], numnodes);
1069                 }
1070         }
1071         assert(node_size == nextNodeIdx);
1072         /* Root index to start traversal at, to handle case of single leaf node. */
1073         pack.root_index = (root->is_leaf())? -1: 0;
1074 }
1075
1076 void QBVH::refit_nodes()
1077 {
1078         assert(!params.top_level);
1079
1080         BoundBox bbox = BoundBox::empty;
1081         uint visibility = 0;
1082         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
1083 }
1084
1085 void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
1086 {
1087         if(leaf) {
1088                 int4 *data = &pack.leaf_nodes[idx];
1089                 int4 c = data[0];
1090                 /* Refit leaf node. */
1091                 for(int prim = c.x; prim < c.y; prim++) {
1092                         int pidx = pack.prim_index[prim];
1093                         int tob = pack.prim_object[prim];
1094                         Object *ob = objects[tob];
1095
1096                         if(pidx == -1) {
1097                                 /* Object instance. */
1098                                 bbox.grow(ob->bounds);
1099                         }
1100                         else {
1101                                 /* Primitives. */
1102                                 const Mesh *mesh = ob->mesh;
1103
1104                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
1105                                         /* Curves. */
1106                                         int str_offset = (params.top_level)? mesh->curve_offset: 0;
1107                                         Mesh::Curve curve = mesh->get_curve(pidx - str_offset);
1108                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
1109
1110                                         curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox);
1111
1112                                         visibility |= PATH_RAY_CURVE;
1113
1114                                         /* Motion curves. */
1115                                         if(mesh->use_motion_blur) {
1116                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
1117
1118                                                 if(attr) {
1119                                                         size_t mesh_size = mesh->curve_keys.size();
1120                                                         size_t steps = mesh->motion_steps - 1;
1121                                                         float3 *key_steps = attr->data_float3();
1122
1123                                                         for(size_t i = 0; i < steps; i++)
1124                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox);
1125                                                 }
1126                                         }
1127                                 }
1128                                 else {
1129                                         /* Triangles. */
1130                                         int tri_offset = (params.top_level)? mesh->tri_offset: 0;
1131                                         Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset);
1132                                         const float3 *vpos = &mesh->verts[0];
1133
1134                                         triangle.bounds_grow(vpos, bbox);
1135
1136                                         /* Motion triangles. */
1137                                         if(mesh->use_motion_blur) {
1138                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
1139
1140                                                 if(attr) {
1141                                                         size_t mesh_size = mesh->verts.size();
1142                                                         size_t steps = mesh->motion_steps - 1;
1143                                                         float3 *vert_steps = attr->data_float3();
1144
1145                                                         for(size_t i = 0; i < steps; i++)
1146                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
1147                                                 }
1148                                         }
1149                                 }
1150                         }
1151
1152                         visibility |= ob->visibility;
1153                 }
1154
1155                 /* TODO(sergey): This is actually a copy of pack_leaf(),
1156                  * but this chunk of code only knows actual data and has
1157                  * no idea about BVHNode.
1158                  *
1159                  * Would be nice to de-duplicate code, but trying to make
1160                  * making code more general ends up in much nastier code
1161                  * in my opinion so far.
1162                  *
1163                  * Same applies to the inner nodes case below.
1164                  */
1165                 float4 leaf_data[BVH_QNODE_LEAF_SIZE];
1166                 leaf_data[0].x = __int_as_float(c.x);
1167                 leaf_data[0].y = __int_as_float(c.y);
1168                 leaf_data[0].z = __uint_as_float(visibility);
1169                 leaf_data[0].w = __uint_as_float(c.w);
1170                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
1171         }
1172         else {
1173                 int4 *data = &pack.nodes[idx];
1174                 bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0;
1175                 int4 c;
1176                 if(is_unaligned) {
1177                         c = data[13];
1178                 }
1179                 else {
1180                         c = data[7];
1181                 }
1182                 /* Refit inner node, set bbox from children. */
1183                 BoundBox child_bbox[4] = {BoundBox::empty,
1184                                           BoundBox::empty,
1185                                           BoundBox::empty,
1186                                           BoundBox::empty};
1187                 uint child_visibility[4] = {0};
1188                 int num_nodes = 0;
1189
1190                 for(int i = 0; i < 4; ++i) {
1191                         if(c[i] != 0) {
1192                                 refit_node((c[i] < 0)? -c[i]-1: c[i], (c[i] < 0),
1193                                            child_bbox[i], child_visibility[i]);
1194                                 ++num_nodes;
1195                                 bbox.grow(child_bbox[i]);
1196                                 visibility |= child_visibility[i];
1197                         }
1198                 }
1199
1200                 if(is_unaligned) {
1201                         Transform aligned_space[4] = {transform_identity(),
1202                                                       transform_identity(),
1203                                                       transform_identity(),
1204                                                       transform_identity()};
1205                         pack_unaligned_node(idx,
1206                                             aligned_space,
1207                                             child_bbox,
1208                                             &c[0],
1209                                             visibility,
1210                                             4);
1211                 }
1212                 else {
1213                         pack_aligned_node(idx,
1214                                           child_bbox,
1215                                           &c[0],
1216                                           visibility,
1217                                           4);
1218                 }
1219         }
1220 }
1221
1222 CCL_NAMESPACE_END