ClangFormat: apply to source, most of intern
[blender.git] / intern / cycles / bvh / bvh8.cpp
1 /*
2 * Original code Copyright 2017, Intel Corporation
3 * Modifications Copyright 2018, Blender Foundation.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * * Neither the name of Intel Corporation nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
24 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "bvh/bvh8.h"
30
31 #include "render/mesh.h"
32 #include "render/object.h"
33
34 #include "bvh/bvh_node.h"
35 #include "bvh/bvh_unaligned.h"
36
37 CCL_NAMESPACE_BEGIN
38
39 BVH8::BVH8(const BVHParams &params_, const vector<Object *> &objects_) : BVH(params_, objects_)
40 {
41 }
42
43 namespace {
44
45 BVHNode *bvh_node_merge_children_recursively(const BVHNode *node)
46 {
47   if (node->is_leaf()) {
48     return new LeafNode(*reinterpret_cast<const LeafNode *>(node));
49   }
50   /* Collect nodes of two layer deeper, allowing us to have more childrem in
51    * an inner layer. */
52   assert(node->num_children() <= 2);
53   const BVHNode *children[8];
54   const BVHNode *child0 = node->get_child(0);
55   const BVHNode *child1 = node->get_child(1);
56   int num_children = 0;
57   if (child0->is_leaf()) {
58     children[num_children++] = child0;
59   }
60   else {
61     const BVHNode *child00 = child0->get_child(0), *child01 = child0->get_child(1);
62     if (child00->is_leaf()) {
63       children[num_children++] = child00;
64     }
65     else {
66       children[num_children++] = child00->get_child(0);
67       children[num_children++] = child00->get_child(1);
68     }
69     if (child01->is_leaf()) {
70       children[num_children++] = child01;
71     }
72     else {
73       children[num_children++] = child01->get_child(0);
74       children[num_children++] = child01->get_child(1);
75     }
76   }
77   if (child1->is_leaf()) {
78     children[num_children++] = child1;
79   }
80   else {
81     const BVHNode *child10 = child1->get_child(0), *child11 = child1->get_child(1);
82     if (child10->is_leaf()) {
83       children[num_children++] = child10;
84     }
85     else {
86       children[num_children++] = child10->get_child(0);
87       children[num_children++] = child10->get_child(1);
88     }
89     if (child11->is_leaf()) {
90       children[num_children++] = child11;
91     }
92     else {
93       children[num_children++] = child11->get_child(0);
94       children[num_children++] = child11->get_child(1);
95     }
96   }
97   /* Merge children in subtrees. */
98   BVHNode *children4[8];
99   for (int i = 0; i < num_children; ++i) {
100     children4[i] = bvh_node_merge_children_recursively(children[i]);
101   }
102   /* Allocate new node. */
103   BVHNode *node8 = new InnerNode(node->bounds, children4, num_children);
104   /* TODO(sergey): Consider doing this from the InnerNode() constructor.
105    * But in order to do this nicely need to think of how to pass all the
106    * parameters there. */
107   if (node->is_unaligned) {
108     node8->is_unaligned = true;
109     node8->aligned_space = new Transform();
110     *node8->aligned_space = *node->aligned_space;
111   }
112   return node8;
113 }
114
115 }  // namespace
116
117 BVHNode *BVH8::widen_children_nodes(const BVHNode *root)
118 {
119   if (root == NULL) {
120     return NULL;
121   }
122   if (root->is_leaf()) {
123     return const_cast<BVHNode *>(root);
124   }
125   BVHNode *root8 = bvh_node_merge_children_recursively(root);
126   /* TODO(sergey): Pack children nodes to parents which has less that 4
127    * children. */
128   return root8;
129 }
130
131 void BVH8::pack_leaf(const BVHStackEntry &e, const LeafNode *leaf)
132 {
133   float4 data[BVH_ONODE_LEAF_SIZE];
134   memset(data, 0, sizeof(data));
135   if (leaf->num_triangles() == 1 && pack.prim_index[leaf->lo] == -1) {
136     /* object */
137     data[0].x = __int_as_float(~(leaf->lo));
138     data[0].y = __int_as_float(0);
139   }
140   else {
141     /* triangle */
142     data[0].x = __int_as_float(leaf->lo);
143     data[0].y = __int_as_float(leaf->hi);
144   }
145   data[0].z = __uint_as_float(leaf->visibility);
146   if (leaf->num_triangles() != 0) {
147     data[0].w = __uint_as_float(pack.prim_type[leaf->lo]);
148   }
149
150   memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4) * BVH_ONODE_LEAF_SIZE);
151 }
152
153 void BVH8::pack_inner(const BVHStackEntry &e, const BVHStackEntry *en, int num)
154 {
155   bool has_unaligned = false;
156   /* Check whether we have to create unaligned node or all nodes are aligned
157    * and we can cut some corner here.
158    */
159   if (params.use_unaligned_nodes) {
160     for (int i = 0; i < num; i++) {
161       if (en[i].node->is_unaligned) {
162         has_unaligned = true;
163         break;
164       }
165     }
166   }
167   if (has_unaligned) {
168     /* There's no unaligned children, pack into AABB node. */
169     pack_unaligned_inner(e, en, num);
170   }
171   else {
172     /* Create unaligned node with orientation transform for each of the
173      * children.
174      */
175     pack_aligned_inner(e, en, num);
176   }
177 }
178
179 void BVH8::pack_aligned_inner(const BVHStackEntry &e, const BVHStackEntry *en, int num)
180 {
181   BoundBox bounds[8];
182   int child[8];
183   for (int i = 0; i < num; ++i) {
184     bounds[i] = en[i].node->bounds;
185     child[i] = en[i].encodeIdx();
186   }
187   pack_aligned_node(
188       e.idx, bounds, child, e.node->visibility, e.node->time_from, e.node->time_to, num);
189 }
190
191 void BVH8::pack_aligned_node(int idx,
192                              const BoundBox *bounds,
193                              const int *child,
194                              const uint visibility,
195                              const float time_from,
196                              const float time_to,
197                              const int num)
198 {
199   float8 data[8];
200   memset(data, 0, sizeof(data));
201
202   data[0].a = __uint_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED);
203   data[0].b = time_from;
204   data[0].c = time_to;
205
206   for (int i = 0; i < num; i++) {
207     float3 bb_min = bounds[i].min;
208     float3 bb_max = bounds[i].max;
209
210     data[1][i] = bb_min.x;
211     data[2][i] = bb_max.x;
212     data[3][i] = bb_min.y;
213     data[4][i] = bb_max.y;
214     data[5][i] = bb_min.z;
215     data[6][i] = bb_max.z;
216
217     data[7][i] = __int_as_float(child[i]);
218   }
219
220   for (int i = num; i < 8; i++) {
221     /* We store BB which would never be recorded as intersection
222      * so kernel might safely assume there are always 4 child nodes.
223      */
224     data[1][i] = FLT_MAX;
225     data[2][i] = -FLT_MAX;
226
227     data[3][i] = FLT_MAX;
228     data[4][i] = -FLT_MAX;
229
230     data[5][i] = FLT_MAX;
231     data[6][i] = -FLT_MAX;
232
233     data[7][i] = __int_as_float(0);
234   }
235
236   memcpy(&pack.nodes[idx], data, sizeof(float4) * BVH_ONODE_SIZE);
237 }
238
239 void BVH8::pack_unaligned_inner(const BVHStackEntry &e, const BVHStackEntry *en, int num)
240 {
241   Transform aligned_space[8];
242   BoundBox bounds[8];
243   int child[8];
244   for (int i = 0; i < num; ++i) {
245     aligned_space[i] = en[i].node->get_aligned_space();
246     bounds[i] = en[i].node->bounds;
247     child[i] = en[i].encodeIdx();
248   }
249   pack_unaligned_node(e.idx,
250                       aligned_space,
251                       bounds,
252                       child,
253                       e.node->visibility,
254                       e.node->time_from,
255                       e.node->time_to,
256                       num);
257 }
258
259 void BVH8::pack_unaligned_node(int idx,
260                                const Transform *aligned_space,
261                                const BoundBox *bounds,
262                                const int *child,
263                                const uint visibility,
264                                const float time_from,
265                                const float time_to,
266                                const int num)
267 {
268   float8 data[BVH_UNALIGNED_ONODE_SIZE];
269   memset(data, 0, sizeof(data));
270
271   data[0].a = __uint_as_float(visibility | PATH_RAY_NODE_UNALIGNED);
272   data[0].b = time_from;
273   data[0].c = time_to;
274
275   for (int i = 0; i < num; i++) {
276     Transform space = BVHUnaligned::compute_node_transform(bounds[i], aligned_space[i]);
277
278     data[1][i] = space.x.x;
279     data[2][i] = space.x.y;
280     data[3][i] = space.x.z;
281
282     data[4][i] = space.y.x;
283     data[5][i] = space.y.y;
284     data[6][i] = space.y.z;
285
286     data[7][i] = space.z.x;
287     data[8][i] = space.z.y;
288     data[9][i] = space.z.z;
289
290     data[10][i] = space.x.w;
291     data[11][i] = space.y.w;
292     data[12][i] = space.z.w;
293
294     data[13][i] = __int_as_float(child[i]);
295   }
296
297   for (int i = num; i < 8; i++) {
298     /* We store BB which would never be recorded as intersection
299      * so kernel might safely assume there are always 4 child nodes.
300      */
301
302     data[1][i] = NAN;
303     data[2][i] = NAN;
304     data[3][i] = NAN;
305
306     data[4][i] = NAN;
307     data[5][i] = NAN;
308     data[6][i] = NAN;
309
310     data[7][i] = NAN;
311     data[8][i] = NAN;
312     data[9][i] = NAN;
313
314     data[10][i] = NAN;
315     data[11][i] = NAN;
316     data[12][i] = NAN;
317
318     data[13][i] = __int_as_float(0);
319   }
320
321   memcpy(&pack.nodes[idx], data, sizeof(float4) * BVH_UNALIGNED_ONODE_SIZE);
322 }
323
324 /* Quad SIMD Nodes */
325
326 void BVH8::pack_nodes(const BVHNode *root)
327 {
328   /* Calculate size of the arrays required. */
329   const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
330   const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
331   assert(num_leaf_nodes <= num_nodes);
332   const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
333   size_t node_size;
334   if (params.use_unaligned_nodes) {
335     const size_t num_unaligned_nodes = root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
336     node_size = (num_unaligned_nodes * BVH_UNALIGNED_ONODE_SIZE) +
337                 (num_inner_nodes - num_unaligned_nodes) * BVH_ONODE_SIZE;
338   }
339   else {
340     node_size = num_inner_nodes * BVH_ONODE_SIZE;
341   }
342   /* Resize arrays. */
343   pack.nodes.clear();
344   pack.leaf_nodes.clear();
345   /* For top level BVH, first merge existing BVH's so we know the offsets. */
346   if (params.top_level) {
347     pack_instances(node_size, num_leaf_nodes * BVH_ONODE_LEAF_SIZE);
348   }
349   else {
350     pack.nodes.resize(node_size);
351     pack.leaf_nodes.resize(num_leaf_nodes * BVH_ONODE_LEAF_SIZE);
352   }
353
354   int nextNodeIdx = 0, nextLeafNodeIdx = 0;
355
356   vector<BVHStackEntry> stack;
357   stack.reserve(BVHParams::MAX_DEPTH * 2);
358   if (root->is_leaf()) {
359     stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
360   }
361   else {
362     stack.push_back(BVHStackEntry(root, nextNodeIdx));
363     nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_ONODE_SIZE : BVH_ONODE_SIZE;
364   }
365
366   while (stack.size()) {
367     BVHStackEntry e = stack.back();
368     stack.pop_back();
369
370     if (e.node->is_leaf()) {
371       /* leaf node */
372       const LeafNode *leaf = reinterpret_cast<const LeafNode *>(e.node);
373       pack_leaf(e, leaf);
374     }
375     else {
376       /* Inner node. */
377       /* Collect nodes. */
378       const BVHNode *children[8];
379       int num_children = e.node->num_children();
380       /* Push entries on the stack. */
381       for (int i = 0; i < num_children; ++i) {
382         int idx;
383         children[i] = e.node->get_child(i);
384         if (children[i]->is_leaf()) {
385           idx = nextLeafNodeIdx++;
386         }
387         else {
388           idx = nextNodeIdx;
389           nextNodeIdx += children[i]->has_unaligned() ? BVH_UNALIGNED_ONODE_SIZE : BVH_ONODE_SIZE;
390         }
391         stack.push_back(BVHStackEntry(children[i], idx));
392       }
393       /* Set node. */
394       pack_inner(e, &stack[stack.size() - num_children], num_children);
395     }
396   }
397
398   assert(node_size == nextNodeIdx);
399   /* Root index to start traversal at, to handle case of single leaf node. */
400   pack.root_index = (root->is_leaf()) ? -1 : 0;
401 }
402
403 void BVH8::refit_nodes()
404 {
405   assert(!params.top_level);
406
407   BoundBox bbox = BoundBox::empty;
408   uint visibility = 0;
409   refit_node(0, (pack.root_index == -1) ? true : false, bbox, visibility);
410 }
411
412 void BVH8::refit_node(int idx, bool leaf, BoundBox &bbox, uint &visibility)
413 {
414   if (leaf) {
415     int4 *data = &pack.leaf_nodes[idx];
416     int4 c = data[0];
417     /* Refit leaf node. */
418     for (int prim = c.x; prim < c.y; prim++) {
419       int pidx = pack.prim_index[prim];
420       int tob = pack.prim_object[prim];
421       Object *ob = objects[tob];
422
423       if (pidx == -1) {
424         /* Object instance. */
425         bbox.grow(ob->bounds);
426       }
427       else {
428         /* Primitives. */
429         const Mesh *mesh = ob->mesh;
430
431         if (pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
432           /* Curves. */
433           int str_offset = (params.top_level) ? mesh->curve_offset : 0;
434           Mesh::Curve curve = mesh->get_curve(pidx - str_offset);
435           int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
436
437           curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox);
438
439           visibility |= PATH_RAY_CURVE;
440
441           /* Motion curves. */
442           if (mesh->use_motion_blur) {
443             Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
444
445             if (attr) {
446               size_t mesh_size = mesh->curve_keys.size();
447               size_t steps = mesh->motion_steps - 1;
448               float3 *key_steps = attr->data_float3();
449
450               for (size_t i = 0; i < steps; i++) {
451                 curve.bounds_grow(k, key_steps + i * mesh_size, &mesh->curve_radius[0], bbox);
452               }
453             }
454           }
455         }
456         else {
457           /* Triangles. */
458           int tri_offset = (params.top_level) ? mesh->tri_offset : 0;
459           Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset);
460           const float3 *vpos = &mesh->verts[0];
461
462           triangle.bounds_grow(vpos, bbox);
463
464           /* Motion triangles. */
465           if (mesh->use_motion_blur) {
466             Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
467
468             if (attr) {
469               size_t mesh_size = mesh->verts.size();
470               size_t steps = mesh->motion_steps - 1;
471               float3 *vert_steps = attr->data_float3();
472
473               for (size_t i = 0; i < steps; i++) {
474                 triangle.bounds_grow(vert_steps + i * mesh_size, bbox);
475               }
476             }
477           }
478         }
479       }
480
481       visibility |= ob->visibility;
482     }
483
484     float4 leaf_data[BVH_ONODE_LEAF_SIZE];
485     leaf_data[0].x = __int_as_float(c.x);
486     leaf_data[0].y = __int_as_float(c.y);
487     leaf_data[0].z = __uint_as_float(visibility);
488     leaf_data[0].w = __uint_as_float(c.w);
489     memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4) * BVH_ONODE_LEAF_SIZE);
490   }
491   else {
492     float8 *data = (float8 *)&pack.nodes[idx];
493     bool is_unaligned = (__float_as_uint(data[0].a) & PATH_RAY_NODE_UNALIGNED) != 0;
494     /* Refit inner node, set bbox from children. */
495     BoundBox child_bbox[8] = {BoundBox::empty,
496                               BoundBox::empty,
497                               BoundBox::empty,
498                               BoundBox::empty,
499                               BoundBox::empty,
500                               BoundBox::empty,
501                               BoundBox::empty,
502                               BoundBox::empty};
503     int child[8];
504     uint child_visibility[8] = {0};
505     int num_nodes = 0;
506
507     for (int i = 0; i < 8; ++i) {
508       child[i] = __float_as_int(data[(is_unaligned) ? 13 : 7][i]);
509
510       if (child[i] != 0) {
511         refit_node((child[i] < 0) ? -child[i] - 1 : child[i],
512                    (child[i] < 0),
513                    child_bbox[i],
514                    child_visibility[i]);
515         ++num_nodes;
516         bbox.grow(child_bbox[i]);
517         visibility |= child_visibility[i];
518       }
519     }
520
521     if (is_unaligned) {
522       Transform aligned_space[8] = {transform_identity(),
523                                     transform_identity(),
524                                     transform_identity(),
525                                     transform_identity(),
526                                     transform_identity(),
527                                     transform_identity(),
528                                     transform_identity(),
529                                     transform_identity()};
530       pack_unaligned_node(
531           idx, aligned_space, child_bbox, child, visibility, 0.0f, 1.0f, num_nodes);
532     }
533     else {
534       pack_aligned_node(idx, child_bbox, child, visibility, 0.0f, 1.0f, num_nodes);
535     }
536   }
537 }
538
539 CCL_NAMESPACE_END