Cycles: Remove odd definition from CMake file
[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         float4 data[BVH_NODE_LEAF_SIZE];
429         memset(data, 0, sizeof(data));
430         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
431                 /* object */
432                 data[0].x = __int_as_float(~(leaf->m_lo));
433                 data[0].y = __int_as_float(0);
434         }
435         else {
436                 /* triangle */
437                 data[0].x = __int_as_float(leaf->m_lo);
438                 data[0].y = __int_as_float(leaf->m_hi);
439         }
440         data[0].z = __uint_as_float(leaf->m_visibility);
441         if(leaf->num_triangles() != 0) {
442                 data[0].w = __uint_as_float(pack.prim_type[leaf->m_lo]);
443         }
444
445         memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
446 }
447
448 void RegularBVH::pack_inner(const BVHStackEntry& e,
449                             const BVHStackEntry& e0,
450                             const BVHStackEntry& e1)
451 {
452         if (e0.node->is_unaligned() || e1.node->is_unaligned()) {
453                 pack_unaligned_inner(e, e0, e1);
454         } else {
455                 pack_aligned_inner(e, e0, e1);
456         }
457 }
458
459 void RegularBVH::pack_aligned_inner(const BVHStackEntry& e,
460                                     const BVHStackEntry& e0,
461                                     const BVHStackEntry& e1)
462 {
463         pack_aligned_node(e.idx,
464                           e0.node->m_bounds, e1.node->m_bounds,
465                           e0.encodeIdx(), e1.encodeIdx(),
466                           e0.node->m_visibility, e1.node->m_visibility);
467 }
468
469 void RegularBVH::pack_aligned_node(int idx,
470                                    const BoundBox& b0,
471                                    const BoundBox& b1,
472                                    int c0, int c1,
473                                    uint visibility0, uint visibility1)
474 {
475         int4 data[BVH_NODE_SIZE] =
476         {
477                 make_int4(visibility0 & ~PATH_RAY_NODE_UNALIGNED,
478                           visibility1 & ~PATH_RAY_NODE_UNALIGNED, c0, c1),
479                 make_int4(__float_as_int(b0.min.x), __float_as_int(b1.min.x), __float_as_int(b0.max.x), __float_as_int(b1.max.x)),
480                 make_int4(__float_as_int(b0.min.y), __float_as_int(b1.min.y), __float_as_int(b0.max.y), __float_as_int(b1.max.y)),
481                 make_int4(__float_as_int(b0.min.z), __float_as_int(b1.min.z), __float_as_int(b0.max.z), __float_as_int(b1.max.z)),
482         };
483
484         memcpy(&pack.nodes[idx], data, sizeof(int4)*BVH_NODE_SIZE);
485 }
486
487 void RegularBVH::pack_unaligned_inner(const BVHStackEntry& e,
488                                       const BVHStackEntry& e0,
489                                       const BVHStackEntry& e1)
490 {
491         pack_unaligned_node(e.idx,
492                             e0.node->get_aligned_space(),
493                             e1.node->get_aligned_space(),
494                             e0.node->m_bounds,
495                             e1.node->m_bounds,
496                             e0.encodeIdx(), e1.encodeIdx(),
497                             e0.node->m_visibility, e1.node->m_visibility);
498 }
499
500 void RegularBVH::pack_unaligned_node(int idx,
501                                      const Transform& aligned_space0,
502                                      const Transform& aligned_space1,
503                                      const BoundBox& bounds0,
504                                      const BoundBox& bounds1,
505                                      int c0, int c1,
506                                      uint visibility0, uint visibility1)
507 {
508         float4 data[BVH_UNALIGNED_NODE_SIZE];
509         Transform space0 = BVHUnaligned::compute_node_transform(bounds0,
510                                                                 aligned_space0);
511         Transform space1 = BVHUnaligned::compute_node_transform(bounds1,
512                                                                 aligned_space1);
513         data[0] = make_float4(__int_as_float(visibility0 | PATH_RAY_NODE_UNALIGNED),
514                               __int_as_float(visibility1 | PATH_RAY_NODE_UNALIGNED),
515                               __int_as_float(c0),
516                               __int_as_float(c1));
517
518         data[1] = space0.x;
519         data[2] = space0.y;
520         data[3] = space0.z;
521         data[4] = space1.x;
522         data[5] = space1.y;
523         data[6] = space1.z;
524
525         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_NODE_SIZE);
526 }
527
528 void RegularBVH::pack_nodes(const BVHNode *root)
529 {
530         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
531         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
532         assert(num_leaf_nodes <= num_nodes);
533         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
534         size_t node_size;
535         if(params.use_unaligned_nodes) {
536                 const size_t num_unaligned_nodes =
537                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
538                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_NODE_SIZE) +
539                             (num_inner_nodes - num_unaligned_nodes) * BVH_NODE_SIZE;
540         }
541         else {
542                 node_size = num_inner_nodes * BVH_NODE_SIZE;
543         }
544         /* Resize arrays */
545         pack.nodes.clear();
546         pack.leaf_nodes.clear();
547         /* For top level BVH, first merge existing BVH's so we know the offsets. */
548         if(params.top_level) {
549                 pack_instances(node_size, num_leaf_nodes*BVH_NODE_LEAF_SIZE);
550         }
551         else {
552                 pack.nodes.resize(node_size);
553                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_NODE_LEAF_SIZE);
554         }
555
556         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
557
558         vector<BVHStackEntry> stack;
559         stack.reserve(BVHParams::MAX_DEPTH*2);
560         if(root->is_leaf()) {
561                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
562         }
563         else {
564                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
565                 nextNodeIdx += node_bvh_is_unaligned(root)
566                                        ? BVH_UNALIGNED_NODE_SIZE
567                                        : BVH_NODE_SIZE;
568         }
569
570         while(stack.size()) {
571                 BVHStackEntry e = stack.back();
572                 stack.pop_back();
573
574                 if(e.node->is_leaf()) {
575                         /* leaf node */
576                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
577                         pack_leaf(e, leaf);
578                 }
579                 else {
580                         /* innner node */
581                         int idx[2];
582                         for (int i = 0; i < 2; ++i) {
583                                 if (e.node->get_child(i)->is_leaf()) {
584                                         idx[i] = nextLeafNodeIdx++;
585                                 }
586                                 else {
587                                         idx[i] = nextNodeIdx;
588                                         nextNodeIdx += node_bvh_is_unaligned(e.node->get_child(i))
589                                                                ? BVH_UNALIGNED_NODE_SIZE
590                                                                : BVH_NODE_SIZE;
591                                 }
592                         }
593
594                         stack.push_back(BVHStackEntry(e.node->get_child(0), idx[0]));
595                         stack.push_back(BVHStackEntry(e.node->get_child(1), idx[1]));
596
597                         pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
598                 }
599         }
600         assert(node_size == nextNodeIdx);
601         /* root index to start traversal at, to handle case of single leaf node */
602         pack.root_index = (root->is_leaf())? -1: 0;
603 }
604
605 void RegularBVH::refit_nodes()
606 {
607         assert(!params.top_level);
608
609         BoundBox bbox = BoundBox::empty;
610         uint visibility = 0;
611         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
612 }
613
614 void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
615 {
616         if(leaf) {
617                 int4 *data = &pack.leaf_nodes[idx];
618                 int c0 = data[0].x;
619                 int c1 = data[0].y;
620                 /* refit leaf node */
621                 for(int prim = c0; prim < c1; prim++) {
622                         int pidx = pack.prim_index[prim];
623                         int tob = pack.prim_object[prim];
624                         Object *ob = objects[tob];
625
626                         if(pidx == -1) {
627                                 /* object instance */
628                                 bbox.grow(ob->bounds);
629                         }
630                         else {
631                                 /* primitives */
632                                 const Mesh *mesh = ob->mesh;
633
634                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
635                                         /* curves */
636                                         int str_offset = (params.top_level)? mesh->curve_offset: 0;
637                                         Mesh::Curve curve = mesh->get_curve(pidx - str_offset);
638                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
639
640                                         curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox);
641
642                                         visibility |= PATH_RAY_CURVE;
643
644                                         /* motion curves */
645                                         if(mesh->use_motion_blur) {
646                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
647
648                                                 if(attr) {
649                                                         size_t mesh_size = mesh->curve_keys.size();
650                                                         size_t steps = mesh->motion_steps - 1;
651                                                         float3 *key_steps = attr->data_float3();
652
653                                                         for(size_t i = 0; i < steps; i++)
654                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox);
655                                                 }
656                                         }
657                                 }
658                                 else {
659                                         /* triangles */
660                                         int tri_offset = (params.top_level)? mesh->tri_offset: 0;
661                                         Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset);
662                                         const float3 *vpos = &mesh->verts[0];
663
664                                         triangle.bounds_grow(vpos, bbox);
665
666                                         /* motion triangles */
667                                         if(mesh->use_motion_blur) {
668                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
669
670                                                 if(attr) {
671                                                         size_t mesh_size = mesh->verts.size();
672                                                         size_t steps = mesh->motion_steps - 1;
673                                                         float3 *vert_steps = attr->data_float3();
674
675                                                         for(size_t i = 0; i < steps; i++)
676                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
677                                                 }
678                                         }
679                                 }
680                         }
681
682                         visibility |= ob->visibility;
683                 }
684
685                 /* TODO(sergey): De-duplicate with pack_leaf(). */
686                 float4 leaf_data[BVH_NODE_LEAF_SIZE];
687                 leaf_data[0].x = __int_as_float(c0);
688                 leaf_data[0].y = __int_as_float(c1);
689                 leaf_data[0].z = __uint_as_float(visibility);
690                 leaf_data[0].w = __uint_as_float(data[0].w);
691                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
692         }
693         else {
694                 int4 *data = &pack.nodes[idx];
695                 int c0 = data[0].z;
696                 int c1 = data[0].w;
697                 /* refit inner node, set bbox from children */
698                 BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
699                 uint visibility0 = 0, visibility1 = 0;
700
701                 refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
702                 refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
703
704                 pack_aligned_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
705
706                 bbox.grow(bbox0);
707                 bbox.grow(bbox1);
708                 visibility = visibility0|visibility1;
709         }
710 }
711
712 /* QBVH */
713
714 /* Can we avoid this somehow or make more generic?
715  *
716  * Perhaps we can merge nodes in actual tree and make our
717  * life easier all over the place.
718  */
719 static bool node_qbvh_is_unaligned(const BVHNode *node)
720 {
721         const BVHNode *node0 = node->get_child(0),
722                       *node1 = node->get_child(1);
723         bool has_unaligned = false;
724         if(node0->is_leaf()) {
725                 has_unaligned |= node0->is_unaligned();
726         }
727         else {
728                 has_unaligned |= node0->get_child(0)->is_unaligned();
729                 has_unaligned |= node0->get_child(1)->is_unaligned();
730         }
731         if(node1->is_leaf()) {
732                 has_unaligned |= node1->is_unaligned();
733         }
734         else {
735                 has_unaligned |= node1->get_child(0)->is_unaligned();
736                 has_unaligned |= node1->get_child(1)->is_unaligned();
737         }
738         return has_unaligned;
739 }
740
741 QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_)
742 : BVH(params_, objects_)
743 {
744         params.use_qbvh = true;
745 }
746
747 void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
748 {
749         float4 data[BVH_QNODE_LEAF_SIZE];
750         memset(data, 0, sizeof(data));
751         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
752                 /* object */
753                 data[0].x = __int_as_float(~(leaf->m_lo));
754                 data[0].y = __int_as_float(0);
755         }
756         else {
757                 /* triangle */
758                 data[0].x = __int_as_float(leaf->m_lo);
759                 data[0].y = __int_as_float(leaf->m_hi);
760         }
761         data[0].z = __uint_as_float(leaf->m_visibility);
762         if(leaf->num_triangles() != 0) {
763                 data[0].w = __uint_as_float(pack.prim_type[leaf->m_lo]);
764         }
765
766         memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
767 }
768
769 void QBVH::pack_inner(const BVHStackEntry& e,
770                       const BVHStackEntry *en,
771                       int num)
772 {
773         bool has_unaligned = false;
774         /* Check whether we have to create unaligned node or all nodes are aligned
775          * and we can cut some corner here.
776          */
777         if(params.use_unaligned_nodes) {
778                 for(int i = 0; i < num; i++) {
779                         if(en[i].node->is_unaligned()) {
780                                 has_unaligned = true;
781                                 break;
782                         }
783                 }
784         }
785         if(has_unaligned) {
786                 /* There's no unaligned children, pack into AABB node. */
787                 pack_unaligned_inner(e, en, num);
788         }
789         else {
790                 /* Create unaligned node with orientation transform for each of the
791                  * children.
792                  */
793                 pack_aligned_inner(e, en, num);
794         }
795 }
796
797 void QBVH::pack_aligned_inner(const BVHStackEntry& e,
798                               const BVHStackEntry *en,
799                               int num)
800 {
801         float4 data[BVH_QNODE_SIZE];
802         memset(data, 0, sizeof(data));
803
804         data[0].x = __uint_as_float(e.node->m_visibility & ~PATH_RAY_NODE_UNALIGNED);
805         for(int i = 0; i < num; i++) {
806                 float3 bb_min = en[i].node->m_bounds.min;
807                 float3 bb_max = en[i].node->m_bounds.max;
808
809                 data[1][i] = bb_min.x;
810                 data[2][i] = bb_max.x;
811                 data[3][i] = bb_min.y;
812                 data[4][i] = bb_max.y;
813                 data[5][i] = bb_min.z;
814                 data[6][i] = bb_max.z;
815
816                 data[7][i] = __int_as_float(en[i].encodeIdx());
817         }
818
819         for(int i = num; i < 4; i++) {
820                 /* We store BB which would never be recorded as intersection
821                  * so kernel might safely assume there are always 4 child nodes.
822                  */
823                 data[1][i] = FLT_MAX;
824                 data[2][i] = -FLT_MAX;
825
826                 data[3][i] = FLT_MAX;
827                 data[4][i] = -FLT_MAX;
828
829                 data[5][i] = FLT_MAX;
830                 data[6][i] = -FLT_MAX;
831
832                 data[7][i] = __int_as_float(0);
833         }
834
835         memcpy(&pack.nodes[e.idx], data, sizeof(float4)*BVH_QNODE_SIZE);
836 }
837
838 void QBVH::pack_unaligned_inner(const BVHStackEntry& e,
839                                 const BVHStackEntry *en,
840                                 int num)
841 {
842         float4 data[BVH_UNALIGNED_QNODE_SIZE];
843         memset(data, 0, sizeof(data));
844
845         data[0].x = __uint_as_float(e.node->m_visibility | PATH_RAY_NODE_UNALIGNED);
846
847         for(int i = 0; i < num; i++) {
848                 Transform space = BVHUnaligned::compute_node_transform(
849                         en[i].node->m_bounds,
850                         en[i].node->get_aligned_space());
851
852                 data[1][i] = space.x.x;
853                 data[2][i] = space.x.y;
854                 data[3][i] = space.x.z;
855
856                 data[4][i] = space.y.x;
857                 data[5][i] = space.y.y;
858                 data[6][i] = space.y.z;
859
860                 data[7][i] = space.z.x;
861                 data[8][i] = space.z.y;
862                 data[9][i] = space.z.z;
863
864                 data[10][i] = space.x.w;
865                 data[11][i] = space.y.w;
866                 data[12][i] = space.z.w;
867
868                 data[13][i] = __int_as_float(en[i].encodeIdx());
869         }
870
871         for(int i = num; i < 4; i++) {
872                 /* We store BB which would never be recorded as intersection
873                  * so kernel might safely assume there are always 4 child nodes.
874                  */
875                 for(int j = 1; j < 13; ++j) {
876                         data[j][i] = 0.0f;
877                 }
878                 data[13][i] = __int_as_float(0);
879         }
880
881         memcpy(&pack.nodes[e.idx], data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE);
882 }
883
884 /* Quad SIMD Nodes */
885
886 void QBVH::pack_nodes(const BVHNode *root)
887 {
888         /* Calculate size of the arrays required. */
889         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
890         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
891         assert(num_leaf_nodes <= num_nodes);
892         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
893         size_t node_size;
894         if(params.use_unaligned_nodes) {
895                 const size_t num_unaligned_nodes =
896                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_QNODE_COUNT);
897                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_QNODE_SIZE) +
898                             (num_inner_nodes - num_unaligned_nodes) * BVH_QNODE_SIZE;
899         }
900         else {
901                 node_size = num_inner_nodes * BVH_QNODE_SIZE;
902         }
903         /* Resize arrays. */
904         pack.nodes.clear();
905         pack.leaf_nodes.clear();
906         /* For top level BVH, first merge existing BVH's so we know the offsets. */
907         if(params.top_level) {
908                 pack_instances(node_size, num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
909         }
910         else {
911                 pack.nodes.resize(node_size);
912                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
913         }
914
915         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
916
917         vector<BVHStackEntry> stack;
918         stack.reserve(BVHParams::MAX_DEPTH*2);
919         if(root->is_leaf()) {
920                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
921         }
922         else {
923                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
924                 nextNodeIdx += node_qbvh_is_unaligned(root)
925                                        ? BVH_UNALIGNED_QNODE_SIZE
926                                        : BVH_QNODE_SIZE;
927         }
928
929         while(stack.size()) {
930                 BVHStackEntry e = stack.back();
931                 stack.pop_back();
932
933                 if(e.node->is_leaf()) {
934                         /* leaf node */
935                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
936                         pack_leaf(e, leaf);
937                 }
938                 else {
939                         /* Inner node. */
940                         const BVHNode *node = e.node;
941                         const BVHNode *node0 = node->get_child(0);
942                         const BVHNode *node1 = node->get_child(1);
943                         /* Collect nodes. */
944                         const BVHNode *nodes[4];
945                         int numnodes = 0;
946                         if(node0->is_leaf()) {
947                                 nodes[numnodes++] = node0;
948                         }
949                         else {
950                                 nodes[numnodes++] = node0->get_child(0);
951                                 nodes[numnodes++] = node0->get_child(1);
952                         }
953                         if(node1->is_leaf()) {
954                                 nodes[numnodes++] = node1;
955                         }
956                         else {
957                                 nodes[numnodes++] = node1->get_child(0);
958                                 nodes[numnodes++] = node1->get_child(1);
959                         }
960                         /* Push entries on the stack. */
961                         for(int i = 0; i < numnodes; ++i) {
962                                 int idx;
963                                 if(nodes[i]->is_leaf()) {
964                                         idx = nextLeafNodeIdx++;
965                                 }
966                                 else {
967                                         idx = nextNodeIdx;
968                                         nextNodeIdx += node_qbvh_is_unaligned(nodes[i])
969                                                                ? BVH_UNALIGNED_QNODE_SIZE
970                                                                : BVH_QNODE_SIZE;
971                                 }
972                                 stack.push_back(BVHStackEntry(nodes[i], idx));
973                         }
974                         /* Set node. */
975                         pack_inner(e, &stack[stack.size()-numnodes], numnodes);
976                 }
977         }
978         assert(node_size == nextNodeIdx);
979         /* Root index to start traversal at, to handle case of single leaf node. */
980         pack.root_index = (root->is_leaf())? -1: 0;
981 }
982
983 void QBVH::refit_nodes()
984 {
985         assert(!params.top_level);
986
987         BoundBox bbox = BoundBox::empty;
988         uint visibility = 0;
989         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
990 }
991
992 void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
993 {
994         if(leaf) {
995                 int4 *data = &pack.leaf_nodes[idx];
996                 int4 c = data[0];
997                 /* Refit leaf node. */
998                 for(int prim = c.x; prim < c.y; prim++) {
999                         int pidx = pack.prim_index[prim];
1000                         int tob = pack.prim_object[prim];
1001                         Object *ob = objects[tob];
1002
1003                         if(pidx == -1) {
1004                                 /* Object instance. */
1005                                 bbox.grow(ob->bounds);
1006                         }
1007                         else {
1008                                 /* Primitives. */
1009                                 const Mesh *mesh = ob->mesh;
1010
1011                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
1012                                         /* Curves. */
1013                                         int str_offset = (params.top_level)? mesh->curve_offset: 0;
1014                                         Mesh::Curve curve = mesh->get_curve(pidx - str_offset);
1015                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
1016
1017                                         curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox);
1018
1019                                         visibility |= PATH_RAY_CURVE;
1020
1021                                         /* Motion curves. */
1022                                         if(mesh->use_motion_blur) {
1023                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
1024
1025                                                 if(attr) {
1026                                                         size_t mesh_size = mesh->curve_keys.size();
1027                                                         size_t steps = mesh->motion_steps - 1;
1028                                                         float3 *key_steps = attr->data_float3();
1029
1030                                                         for(size_t i = 0; i < steps; i++)
1031                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox);
1032                                                 }
1033                                         }
1034                                 }
1035                                 else {
1036                                         /* Triangles. */
1037                                         int tri_offset = (params.top_level)? mesh->tri_offset: 0;
1038                                         Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset);
1039                                         const float3 *vpos = &mesh->verts[0];
1040
1041                                         triangle.bounds_grow(vpos, bbox);
1042
1043                                         /* Motion triangles. */
1044                                         if(mesh->use_motion_blur) {
1045                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
1046
1047                                                 if(attr) {
1048                                                         size_t mesh_size = mesh->verts.size();
1049                                                         size_t steps = mesh->motion_steps - 1;
1050                                                         float3 *vert_steps = attr->data_float3();
1051
1052                                                         for(size_t i = 0; i < steps; i++)
1053                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
1054                                                 }
1055                                         }
1056                                 }
1057                         }
1058
1059                         visibility |= ob->visibility;
1060                 }
1061
1062                 /* TODO(sergey): This is actually a copy of pack_leaf(),
1063                  * but this chunk of code only knows actual data and has
1064                  * no idea about BVHNode.
1065                  *
1066                  * Would be nice to de-duplicate code, but trying to make
1067                  * making code more general ends up in much nastier code
1068                  * in my opinion so far.
1069                  *
1070                  * Same applies to the inner nodes case below.
1071                  */
1072                 float4 leaf_data[BVH_QNODE_LEAF_SIZE];
1073                 leaf_data[0].x = __int_as_float(c.x);
1074                 leaf_data[0].y = __int_as_float(c.y);
1075                 leaf_data[0].z = __uint_as_float(visibility);
1076                 leaf_data[0].w = __uint_as_float(c.w);
1077                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
1078         }
1079         else {
1080                 int4 *data = &pack.nodes[idx];
1081                 bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0;
1082                 int4 c;
1083                 if(is_unaligned) {
1084                         c = data[13];
1085                 }
1086                 else {
1087                         c = data[7];
1088                 }
1089                 /* Refit inner node, set bbox from children. */
1090                 BoundBox child_bbox[4] = {BoundBox::empty,
1091                                           BoundBox::empty,
1092                                           BoundBox::empty,
1093                                           BoundBox::empty};
1094                 uint child_visibility[4] = {0};
1095                 int num_nodes = 0;
1096
1097                 for(int i = 0; i < 4; ++i) {
1098                         if(c[i] != 0) {
1099                                 refit_node((c[i] < 0)? -c[i]-1: c[i], (c[i] < 0),
1100                                            child_bbox[i], child_visibility[i]);
1101                                 ++num_nodes;
1102                                 bbox.grow(child_bbox[i]);
1103                                 visibility |= child_visibility[i];
1104                         }
1105                 }
1106
1107                 /* TODO(sergey): To be de-duplicated with pack_inner(),
1108                  * but for that need some sort of pack_node(). which operates with
1109                  * direct data, not stack element.
1110                  */
1111                 if(is_unaligned) {
1112                         Transform aligned_space = transform_identity();
1113                         float4 inner_data[BVH_UNALIGNED_QNODE_SIZE];
1114                         inner_data[0] = make_float4(
1115                                 __int_as_float(visibility | PATH_RAY_NODE_UNALIGNED),
1116                                 0.0f,
1117                                 0.0f,
1118                                 0.0f);
1119                         for(int i = 0; i < 4; ++i) {
1120                                 Transform space = BVHUnaligned::compute_node_transform(
1121                                         child_bbox[i],
1122                                         aligned_space);
1123                                 inner_data[1][i] = space.x.x;
1124                                 inner_data[2][i] = space.x.y;
1125                                 inner_data[3][i] = space.x.z;
1126
1127                                 inner_data[4][i] = space.y.x;
1128                                 inner_data[5][i] = space.y.y;
1129                                 inner_data[6][i] = space.y.z;
1130
1131                                 inner_data[7][i] = space.z.x;
1132                                 inner_data[8][i] = space.z.y;
1133                                 inner_data[9][i] = space.z.z;
1134
1135                                 inner_data[10][i] = space.x.w;
1136                                 inner_data[11][i] = space.y.w;
1137                                 inner_data[12][i] = space.z.w;
1138
1139                                 inner_data[13][i] = __int_as_float(c[i]);
1140                         }
1141                         memcpy(&pack.nodes[idx], inner_data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE);
1142                 }
1143                 else {
1144                         float4 inner_data[BVH_QNODE_SIZE];
1145                         inner_data[0] = make_float4(
1146                                 __int_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED),
1147                                 0.0f,
1148                                 0.0f,
1149                                 0.0f);
1150                         for(int i = 0; i < 4; ++i) {
1151                                 float3 bb_min = child_bbox[i].min;
1152                                 float3 bb_max = child_bbox[i].max;
1153                                 inner_data[1][i] = bb_min.x;
1154                                 inner_data[2][i] = bb_max.x;
1155                                 inner_data[3][i] = bb_min.y;
1156                                 inner_data[4][i] = bb_max.y;
1157                                 inner_data[5][i] = bb_min.z;
1158                                 inner_data[6][i] = bb_max.z;
1159                                 inner_data[7][i] = __int_as_float(c[i]);
1160                         }
1161                         memcpy(&pack.nodes[idx], inner_data, sizeof(float4)*BVH_QNODE_SIZE);
1162                 }
1163         }
1164 }
1165
1166 CCL_NAMESPACE_END